Hash based key value to block translation methods and systems
AssigneeSamsung Electronics Co., Ltd.
InventorSomnath Roy
Life of this patent
Estimating the term…
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.
Claims22
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.
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.
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.
Dependencies are inferred from the claim text.