# US 12,010,214 B2 · Hash based key value to block translation methods and systems > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,010,214 B2 - Document ID: US12010214B2 - Status: Granted - Kind: B2 - Application number: 17/321,326 - Filed: 2021-05-14 - Published: 2022-07-21 - Granted: 2024-06-11 - Earliest claimed: 2021-01-20 - Assignees: Samsung Electronics Co., Ltd. - Applicants: Samsung Electronics Co., Ltd. - Inventors: Somnath Roy - Web page: https://patentgrep.com/patent/US12010214B2 ## CPC - G06F 16/2255: {Hash tables} - H04L 9/0643: {Hash functions, e.g. MD5, SHA, HMAC or f9 MAC} - H04L 9/0861: {Generation of secret information including derivation or calculation of cryptographic keys or passwords} - H04L 9/0891: {Revocation or update of secret information, e.g. encryption key update or rekeying} - H04L 9/0894: {Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract A method is described that includes computing a first index based on a hash of a first key for a first object to be stored in a memory device, determining an availability of a first segment on the memory device corresponding to the first index, computing a second index based on the hash of the first key for the first object, in response to determining that the first segment corresponding to the first index is unavailable for storage, determining an availability of a second segment on the memory device corresponding to the second index, and adding an indicator of a location of the second segment to a collision table in a first metadata of the first segment. ## Claims ### Claim 1 A method comprising: computing a first index based on a hash of a first key for a first object to be stored in a memory device; determining an availability of a first segment on the memory device corresponding to the first index; computing a second index based on the hash of the first key for the first object, in response to determining that the first segment corresponding to the first index is unavailable for storage based on determining that a second object is stored in the first segment; determining an availability of a second segment on the memory device corresponding to the second index; and adding an indicator of a location of the second segment to a collision table in a first metadata of the first segment, wherein the first object is stored in the second segment, and wherein the collision table in the first segment comprises information related to the first object stored in the second segment based on determining that a common index corresponding to the first segment is generated for both the first and second objects. ### Claim 2 (depends on 1) The method of claim 1, further comprising writing the first object to the second segment in response to determining that the second segment is available. ### Claim 3 (depends on 2) The method of claim 2, wherein the computing the second index comprises extracting a bit from every byte of the hash to form the second index. ### Claim 4 (depends on 2) The method of claim 2, wherein the determining the availability of the first segment comprises reading a status identifier from the first metadata, wherein the status identifier indicates a status that corresponds to the first segment being unavailable for storage. ### Claim 5 (depends on 4) The method of claim 4, further comprising writing, to the collision table, an association between the hash of the first key and the indicator of the location of the second segment, in response to the collision table being empty. ### Claim 6 (depends on 1) The method of claim 1, wherein the computing the hash of the first key comprises computing using a Secure Hash Algorithm 256 (SHA-256). ### Claim 7 (depends on 4) The method of claim 4, further comprising: receiving a get request indicating the first key; computing the first index based on the hash of the first key; reading the first metadata of the first segment corresponding to the first index; determining that the hash of the first key is inconsistent with a stored hash stored in the first metadata, in response to reading the first metadata; reading the collision table in the first metadata to determine that the first object is stored in the second segment; and retrieving the first object from the second segment, in response to reading the collision table. ### Claim 8 (depends on 4) The method of claim 4, further comprising: receiving a delete request identifying the first key; computing the first index based on the hash of the first key; reading the first metadata of the first segment corresponding to the first index; determining that the hash of the first key is inconsistent with a stored hash stored in the first metadata, in response to reading the first metadata; reading the collision table in the first metadata to determine that that the first object is stored in the second segment; and deleting the first object from the second segment, in response to reading the collision table. ### Claim 9 (depends on 4) The method of claim 4, further comprising: receiving a delete request identifying the first key; computing the first index based on the hash of the first key; reading the first metadata of the first segment corresponding to the first index; determining that the hash of the first key is consistent with a stored hash stored in the first metadata, in response to reading the first metadata; determining that the collision table in the first metadata comprises the indicator of the location of the second segment; setting a value size of the collision table to zero; and deleting the first object from the second segment. ### Claim 10 (depends on 4) The method of claim 4, further comprising: receiving a delete request identifying the first key; computing the first index based on the hash of the first key; reading the first metadata of the first segment corresponding to the first index; determining that the hash of the first key is consistent with a stored hash stored in the first metadata, in response to reading the first metadata; determining that the collision table in the first metadata is empty, in response to determining that the hash of the first key is consistent with the stored hash stored in the first metadata; and deleting the first object from the second segment, in response to reading the collision table. ### Claim 11 An object storage system configured to store objects, the object storage system comprising a memory device that is divided into segments, the memory device configured to: compute a first index based on a hash of a first key for a first object to be stored in the memory device; determine an availability of a first segment on the memory device corresponding to the first index; compute a second index based on the hash of the first key for the first object, in response to determining that the first segment corresponding to the first index is unavailable for storage based on determining that a second object is stored in the first segment; determine an availability of a second segment on the memory device corresponding to the second index; and adding an indicator of a location of the second segment to a collision table in a first metadata of the first segment, wherein the first object is stored in the second segment, and wherein the collision table in the first segment comprises information related to the first object stored in the second segment based on determining that a common index corresponding to the first segment is generated for both the first and second objects. ### Claim 12 (depends on 11) The system of claim 11, wherein the memory device is further configured to write the first object to the second segment in response to determining that the second segment is available. ### Claim 13 (depends on 12) The system of claim 12, wherein the computing the second index comprises extracting a bit from every byte of the hash to form the second index. ### Claim 14 (depends on 12) The system of claim 12, wherein the determining the availability of the first segment comprises reading a status identifier from the first metadata, wherein the status identifier indicates a status that corresponds to the first segment being unavailable for storage. ### Claim 15 (depends on 14) The system of claim 14, wherein the memory device is further configured to write to the collision table, an association between the hash of the first key and the indicator of the location of the second segment, in response to the collision table being empty. ### Claim 16 (depends on 11) The system of claim 11, wherein computing the hash of the first key comprises computing using a Secure Hash Algorithm 256 (SHA-256). ### Claim 17 (depends on 14) The system of claim 14, wherein the memory device is further configured to: receive a get request indicating the first key; compute the first index based on the hash of the first key; read the first metadata of the first segment corresponding to the first index; determine that the hash of the first key is inconsistent with a stored hash stored in the first metadata, in response to reading the first metadata; read the collision table in the first metadata to determine that the first object is stored in the second segment; and retrieve the first object from the second segment, in response to reading the collision table. ### Claim 18 (depends on 14) The system of claim 14, wherein the memory device is further configured to: receive a delete request identifying the first key; compute the first index based on the hash of the first key; read the first metadata of the first segment corresponding to the first index; determine that the hash of the first key is inconsistent with a stored hash stored in the first metadata, in response to reading the first metadata; read the collision table in the first metadata to determine that that the first object is stored in the second segment; and delete the first object from the second segment, in response to reading the collision table. ### Claim 19 (depends on 14) The system of claim 14, wherein the memory device is further configured to: receive a delete request identifying the first key; compute the first index based on the hash of the first key; read the first metadata of the first segment corresponding to the first index; determine that the hash of the first key is consistent with a stored hash stored in the first metadata, in response to reading the first metadata; determine that the collision table in the first metadata is comprises the indicator of the location of the second segment; set a value size of the collision table to zero; and delete the first object from the second segment. ### Claim 20 (depends on 14) The system of claim 14, wherein the memory device is further configured to: receive a delete request identifying the first key; compute the first index based on the hash of the first key; read the first metadata of the first segment corresponding to the first index; determine that the hash of the first key is inconsistent with a stored hash stored in the first metadata, in response to reading the first metadata; determine that the collision table in the first metadata is empty, in response to determining that the hash of the first key is consistent with the stored hash stored in the first metadata; and delete the first object from the second segment, in response to reading the collision table. ### Claim 21 A method comprising: receiving a get request indicating a first key; computing a first index based on a hash of the first key for an object to be retrieved from a memory device; reading a first metadata of a first segment corresponding to the first index; determining that the hash of the first key is inconsistent with a stored hash stored in the first metadata, in response to reading the first metadata; reading a collision table in the first metadata to determine that the object is stored in a second segment; and retrieving the object from the second segment, in response to reading the collision table, wherein the collision table in the first segment comprises information related to the object stored in the second segment based on determining that a common index corresponding to the first segment is generated for both the object stored in the second segment and another object stored in the first segment. ### Claim 22 (depends on 21) The method of claim 21, wherein the collision table comprises a second index based on the hash of the first key and an offset of the object that is stored in the first segment being an association between the hash of the first key and an indicator of a location of the second segment.