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

摘要

In one embodiment, use of hashing in a file system metadata arrangement reduces an amount of metadata stored in a memory of a node in a cluster and reduces the amount of metadata needed to process an input/output (I/O) request at the node. Illustratively, cuckoo hashing may be modified and applied to construct the file system metadata arrangement. The file system metadata arrangement may be illustratively configured as a key-value extent store embodied as a data structure, e.g., a cuckoo hash table, wherein a value, such as a hash table index, may be configured as an index and applied to the cuckoo hash table to obtain a key, such as an extent key, configured to reference a location of an extent on one or more storage devices, such as solid state drives.

主权项

1. A method comprising:
receiving a write request having an extent, the write request processed at a storage system having a processor and a memory, the storage system coupled to a solid state drive (SSD); applying a hash function to the extent to generate a hash value, the hash value including a hash table selector, a first hash table index, and a second hash table index; selecting a hash table from a set of hash tables using the hash table selector, each hash table divided into a plurality of index address spaces; selecting a first entry in an upper index address space of the hash table using the first hash table index as a first index, the first entry including a first set of slots, each slot of the first set of slots including a first key and a first location field; searching each of the first keys of the first set of slots using the second hash table index; determining whether a first free slot exists within the first set of slots; and in response to determining that the first free slot exists, storing an SSD offset in the first location field of the first free slot, storing the second hash table index as the first key of the first free slot, and storing the extent on the SSD at the SSD offset.