Set-associative hash table organization for efficient storage and retrieval of data in a storage system
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.
1 Assignment
0 Petitions
Accused Products
Abstract
In one embodiment, an extent key reconstruction technique is provided for use with a set of hash tables embodying metadata. The metadata includes an extent key associated with a storage location on storage devices for write data of one or more write requests organized into an extent. Each hash table has a plurality of entries, and each entry includes a plurality of slots. A first field of the extent key is recreated implicitly from an entry in a first address space portion of a hash table. A second field of the extent key is stored in the slot. A third field of the extent key is stored in the slot. A fourth field of the extent key is recreated implicitly from the hash table of the set of hash tables.
89 Citations
20 Claims
-
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 Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A non-transitory computer readable medium including program instructions for execution on one or more processors of a distributed storage architecture, the program instructions when executed operable to:
-
store a set of hash tables embodying metadata including an extent key associated with a storage location on storage devices 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; recreate 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; store 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; store 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 recreate 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 Dependent Claims (9, 10, 11, 12, 13)
-
-
14. A system comprising:
-
a central processing unit (CPU) of a node of a cluster having a plurality of nodes, each node coupled to a plurality of storage devices; and a memory coupled to the CPU and configured to store a set of hash tables embodying metadata including an extent key associated with a storage location on the storage devices 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, the memory further configured to store a storage input/output (I/O) stack having a plurality of layers implemented as one or more instances executable by the CPU, the one or more instances when executed operable to implement an extent key reconstruction technique to; recreate 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; store 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; store 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 recreate 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 Dependent Claims (15, 16, 17, 18, 19, 20)
-
Specification