×

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

  • US 9,256,549 B2
  • Filed: 01/17/2014
  • Issued: 02/09/2016
  • Est. Priority Date: 01/17/2014
  • Status: Active Grant
First Claim
Patent Images

1. A method comprising:

  • storing a set of hash tables embodying metadata including an extent key associated with a storage location on storage devices of a cluster for write data of one or more write requests organized into an extent, each hash table having a plurality of entries, wherein each entry includes a plurality of slots;

    recreating, by a node of the cluster, a first field of the extent key implicitly from an entry in a first address space portion of a hash table, the first field having first bits used as a first hash table index to address the first address space portion of the hash table to select the entry and to determine a slot;

    storing a second field of the extent key in the slot, the second field having second bits used as a second hash table index to address a second address space portion of the hash table;

    storing a third field of the extent key in the slot, the third field having third bits used to realize uniqueness in an event of a collision in the hash table; and

    recreating, by the node of the cluster, a fourth field of the extent key implicitly from the hash table of the set of hash tables, the fourth field having fourth bits used as a hash table selector to select the hash table from the set of hash tables, wherein the first through fourth fields of the extent key are separate fields.

View all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×