Hash map support in a storage device

Abstract

In an embodiment, a storage device may include device processing logic. The device processing logic may acquire a command associated with a key-value pair (KVP). The command may be, for example, a get, set, or delete command. The KVP may include a hash value and an item. The hash value may be a key in the KVP and the item may be a value in the KVP. The device processing logic may translate the acquired command into one or more block-oriented commands which may be executed by the device processing logic to perform various operations on the storage device.

What is claimed is: 
     
         1 . A storage device comprising:
 device processing logic for:
 acquiring a command associated with a key-value pair (KVP), the KVP including a hash value and an item, the hash value being a key of the KVP and the item being a value of the KVP, 
 translating the acquired command into one or more block-oriented commands, and 
 performing the one or more block-oriented commands to access at least one of the hash value or the item in a storage area contained in the storage device, the storage area containing one or more non-volatile random access memory devices for storing the at least one of the hash value or the item. 
   
     
     
         2 . The storage device of  claim 1 , wherein the command is a get command, and wherein the device processing logic further:
 acquires the hash value, and   performs one or more of the block-oriented commands to retrieve the item from the storage device based on the hash value.   
     
     
         3 . The storage device of  claim 2 , wherein the device processing logic further:
 determines that an index entry associated with the acquired hash value exists in an index portion of a storage area in the storage device,   performs one or more of the block-oriented commands to retrieve the index entry from the index portion.   identifies a logical block in a data portion of the storage area, the logical block containing the item, the logical block being identified based on a logical block address (LBA) contained in the index entry, and   performs one or more of the block-oriented commands to retrieve the item from the identified logical block in the data portion.   
     
     
         4 . The storage device of  claim 3 , wherein the device processing logic further:
 identifies a logical block in the index portion that contains the index entry, and   performs one or more of the block-oriented commands to retrieve the index entry from the identified logical block in the index portion.   
     
     
         5 . The storage device of  claim 1 , wherein the command is a set command, and the device processing logic further:
 acquires the hash value and the item, and   performs one or more of the block-oriented commands to store the item in the storage device based on the hash value.   
     
     
         6 . The storage device of  claim 5 , wherein the device processing logic further:
 determines that an index entry associated with the acquired hash value exists in an index portion of a storage area in the storage device;   performs one or more of the block-oriented commands to retrieve the index entry from the index portion,   identifies a logical block in a data portion of the storage area, the logical block containing the item, the logical block being identified based on a logical block address (LBA) contained in the index entry, and   performs one or more of the block-oriented commands store the item in the identified logical block in the data portion.   
     
     
         7 . The storage device of  claim 5 , wherein the device processing logic further:
 determines that an index entry associated with the acquired hash value exists in an index portion of a storage area in the storage device,   performs one or more of the block-oriented commands to retrieve the index entry from the index portion.   determines based on a flag contained in the index entry that the item is to be stored in the index portion, and   performs one or more of the block-oriented commands to store the item in the index portion.   
     
     
         8 . The storage device of  claim 5 , wherein the device processing logic further:
 determines that an index entry associated with the acquired hash value does not exist in an index portion of a storage area in the storage device,   generates an index entry for the acquired has value,   allocates a logical block contained in a data portion of the storage area,   performs one or more of the block-oriented command to store the item in the allocated logical block,   associates the hash value with the item in the index entry, and   performs one or more of the block-oriented commands to store the index entry in the index portion of the storage area.   
     
     
         9 . The storage device of  claim 8 , wherein the logical block is associated with an LBA that identifies a location of the logical block in the storage area, and wherein associating the hash value with the index entry includes:
 the device processing logic setting an item LBA field contained in the index entry to a value that represents the LBA, and   the device processing logic setting the hash value in a hash value field contained in the index entry.   
     
     
         10 . The storage device of  claim 5 , wherein the device processing logic further:
 sets an item size field contained in the index entry to a value that represents a length of the item.   
     
     
         11 . The storage device of  claim 10 , wherein the item is stored in a data storage area of the storage device and wherein the value that represents the length of the item represents a number of logical blocks in the data storage area that the item occupies. 
     
     
         12 . The storage device of  claim 1 , wherein the command is a delete command, and wherein the device processing logic further:
 acquires a hash value associated with an item stored in the storage device, the KVP associated with the delete command including a hash value and an item, the hash value representing a key in the KVP and the item representing a value in the KVP associated with the delete command, and   performs one or more of the block-oriented commands to delete the item from the storage device based on the hash value.   
     
     
         13 . A method comprising:
 acquiring, at a storage device, a command associated with a key-value pair (KVP), the KVP including a hash value and an item, the hash value being a key of the KVP and the item being a value of the KVP;   translating, at the storage device, the acquired command into one or more block-oriented commands; and   performing, at the storage device, the one or more block-oriented commands to access at least one of the hash value or the item in a storage area contained in the storage device, the storage area containing one or more non-volatile random access memory devices for storing the at least one of the hash value or the item.   
     
     
         14 . The method of  claim 13 , wherein the command is a get command, and wherein the method further comprises:
 acquiring, at the storage device, the hash value; and   performing, at the storage device, one or more of the block-oriented commands to retrieve the item from the storage device based on the hash value.   
     
     
         15 . The method of  claim 14 , further comprising:
 determining, at the storage device, that an index entry associated with the acquired hash value exists in an index portion of a storage area in the storage device;   performing, at the storage device, one or more of the block-oriented commands to retrieve the index entry from the index portion;   identifying, at the storage device, a logical block in a data portion of the storage area, the logical block containing the item, the logical block being identified based on a logical block address (LBA) contained in the index entry; and   performing, at the storage device, one or more of the block-oriented commands to retrieve the item from the identified logical block in the data portion.   
     
     
         16 . The method of  claim 15 , further comprising:
 identifying, at the storage device, a logical block in the index portion that contains the index entry; and   performing, at the storage device, one or more of the block-oriented commands to retrieve the index entry from the identified logical block in the index portion.   
     
     
         17 . The method of  claim 13 , wherein the command is a set command, and wherein the method further comprises:
 acquiring, at the storage device, the hash value and the item; and   performing, at the storage device, one or more of the block-oriented commands to store the item in the storage device based on the hash value.   
     
     
         18 . The method of  claim 17 , further comprising:
 determining, at the storage device, that an index entry associated with the acquired hash value exists in an index portion of a storage area in the storage device;   performing, at the storage device, one or more of the block-oriented commands to retrieve the index entry from the index portion;   identifying, at the storage device, a logical block in a data portion of the storage area, the logical block containing the item, the logical block being identified based on a logical block address (LBA) contained in the index entry; and   performing, at the storage device, one or more of the block-oriented commands to store the item in the identified logical block in the data portion.   
     
     
         19 . The method of  claim 17 , further comprising:
 determining, at the storage device, that an index entry associated with the acquired hash value exists in an index portion of a storage area in the storage device;   performing, at the storage device, one or more of the block-oriented commands to retrieve the index entry from the index portion;   determining, at the storage device, based on a flag contained in the index entry that the item is to be stored in the index portion; and   performing, at the storage device, one or more of the block-oriented commands to store the item in the index portion.   
     
     
         20 . The method of  claim 17 , further comprising:
 determining, at the storage device, that an index entry associated with the acquired hash value does not exist in an index portion of a storage area in the storage device;   generating, at the storage device, the index entry;   allocating, at the storage device, a logical block contained in a data portion of the storage area; and   performing, at the storage device, one or more of the block-oriented commands to store the item in the allocated logical block.