Back to results
US 9,438,426 B2Granted
Key-value data storage device with hybrid architecture
AssigneeSeagate Technology LLC
InventorsPeng Li, Frank R. Dropps
Life of this patent
Estimating the term…
Abstract
A key-value storage device and method of using the same. In some embodiments, keys are stored in a key store in a first non-volatile memory and corresponding values associated with the keys are stored in a value store of a second non-volatile memory. An input command is received from a host device, the input command having a key associated with a value. Different first and second hash values are generated by applying a hash function to the key. The input command is executed responsive to the first and second hash values.
Claims20
A method of accessing data in a key value storage device, comprising:
- storing keys in a key store in a first non-volatile memory and corresponding values associated with the keys in a value store of a second non-volatile memory;
- receiving an input command from a host device, the command having a key associated with a value;
- generating different first and second hash values by applying a hash function to the key received as a portion of the input command;
- using the first hash value as an index into a hash table, the hash table stored in a local memory and comprising a plurality of entries each corresponding to a different first hash value;
- identifying a selected entry in the hash table corresponding to the first hash value, the selected entry in the hash table comprising a copy of the second hash value;
- comparing the copy of the second hash value in the selected entry to the second hash value obtained during the generating step;
- retrieving a copy of the key from the first non-volatile memory at a selected address identified by the selected entry responsive to a match between the copy of the second hash value in the selected entry to the second hash value obtained during the generating step;
- and
- executing the input command responsive to a match between the key and the copy of the key retrieved from the first non-volatile memory.
6 more elements
A key-value storage device comprising:
- a first non-volatile memory which stores a key store of copies of key-values available for use in identifying data stored by the storage device;
- a second non-volatile memory module which stores a value store, the value store comprising a plurality of data blocks, each data block storing a fixed amount of user data, the key store providing a unique key-value for each of the data blocks in the value store;
- a local memory which stores a hash table comprising a plurality of entries, each entry corresponding to a different one of the key-values and comprising copies of different first and second hashes of the associated key-value;
- and
- a command processing circuit configured to receive an input command to transfer data between the storage device and a host device, the input command having a selected key-value, the command processing circuit further configured to generate different first and second hash values by applying at least one hash function to the key-value, to use the first hash value as an index into the hash table to locate a selected entry, to retrieve the copy of the second hash value stored in the selected entry and to compare said copy of the second hash value to the second hash value generated by the command processing circuit, to retrieve a selected copy of a key-value from the first non-volatile memory responsive to a match between said copy of the second hash value and the second hash value generated by the command processing circuit, to compare the selected copy of the key-value to the key value associated with the input command, and to execute the input command responsive to a match between the selected copy of the key-value and the key value associated with the input command.
2 more elements
A key-value storage device comprising:
- a first non-volatile memory module which stores a key store;
- a second non-volatile memory module which stores a value store comprising a plurality of data blocks each storing an amount of user data, the key store comprising a plurality of keys and physical addresses of the data blocks in the value store associated with the keys;
- a host interface module adapted to receive an input command from a host device coupled to the key value storage device, the input command having an associated key;
- a hash function module adapted to generate different first and second hash values by applying a cryptographic hash function to the associated key;
- a local memory module which stores a hash table and a key linked list, the hash table comprising a plurality of entries each comprising to a different possible value of the first hash value and a corresponding possible value of the second hash value, the key linked list comprising a plurality of entries linked to the entries of the hash table and having additional possible values of the second hash value;
- and
- a control circuit adapted to use the first hash value generated by the hash function module to index the hash table to locate a first matching entry, to evaluate the located matching entry and one or more of the key linked list entries to locate a second matching entry that matches the second hash value generated by the hash function module, to access the key store and retrieve a copy of the associated key from a location identified by the second matching entry, to compare the retrieved copy of the associated key and the received associated key from the received command, and to execute the input command to transfer data between the key value storage device and the host device responsive to a match between the retrieved copy of the associated key and the received associated key from the received command.
4 more elements
Dependencies are inferred from the claim text.