×

Set-associative hash table organization for efficient storage and retrieval of data in a storage system

  • US 9,639,278 B2
  • Filed: 10/29/2015
  • Issued: 05/02/2017
  • Est. Priority Date: 01/17/2014
  • Status: Active Grant
First Claim
Patent Images

1. A method comprising:

  • receiving write requests having a plurality of extents at a cluster of nodes, each write request processed at a node having a processor and a memory, the memory configured to store a storage input/output (I/O) stack having a plurality of layers implemented as one or more instances executable by the processor, the node coupled to one or more solid state drives (SSDs);

    applying a hash function to an extent of the plurality of extents to generate a hash value, the hash value including a hash table selector, a first hash table index, and a second hash table index;

    mapping the hash value to an extent store instance of the storage I/O stack that is responsible for storing the extent on a SSD of the one or more SSDs;

    selecting a hash table from a set of hash tables served by the extent store instance using the hash table selector, each hash table divided into one or more index address spaces;

    selecting a first entry in an index address space of the hash table using the first hash table index, the first entry including a first set of slots having first keys;

    matching one of the first keys of the first set of slots to the second hash table index; and

    in response to matching one of the first keys, generating a candidate extent key including a candidate hash table index used to select a second entry of the set of hash tables for storing an identification of a storage location on SSD for the extent, the candidate hash table index resolving to the extent store instance serving the set of hash tables.

View all claims
  • 0 Assignments
Timeline View
Assignment View
    ×
    ×