Storing a non-ordered associative array of pairs using an append-only storage medium
AssigneeEMC IP Holding Company LLC
InventorAndrei Paduroiu
Life of this patent
Estimating the term…
Abstract
The described technology is generally directed towards efficiently organizing data in a single, non-distributed database as an associated array of key-value pairs implemented on top of a storage medium that allows only data appends. A table segment in an append-only storage medium is accessed by table keys. The table keys are hashed into key values used to access information in an attribute index (a search tree) that contains offsets to the table segment entries. Hashing the table keys can result in a series of hash parts, including a primary hash part corresponding to a node in the attribute index, and as needed in the event of hash collisions, secondary hash parts that map to child nodes in the attribute index.
Claims20
A method, comprising:
- receiving, by a system comprising a processor, an update request comprising a table key and value corresponding to a table segment implemented in an append-only storage medium;
- appending, by the system, the update request to the table segment by serializing the update request at an offset location in the table segment;
- updating, by the system, a memory key index that is stored in memory with the offset location corresponding to the update request;
- asynchronously indexing, by the system, the memory key index to an attribute index stored in an extended append-only storage medium;
- receiving, by the system, a read request comprising the table key, the read request being for a requested value paired with the table key;
- in response to the receiving the read request, looking, by the system, for the requested value in the memory key index using the table key;
- and
- in response to the requested value being determined not to be present in the memory key index, using, by the system, a hash of the table key to access the attribute index to obtain the offset location in the table segment corresponding to the offset location from which the requested value is able to be obtained.
A system, comprising:
- a processor;
- and
- a memory that stores executable instructions that, when executed by the processor, facilitate performance of operations, the operations comprising:
- receiving an update request comprising a table key and value corresponding to a table segment implemented in an append-only storage medium;
- appending the update request to the table segment by serializing the update request at an offset location in the table segment;
- updating a memory key index that is stored in memory with the offset location corresponding to the update request;
- asynchronously indexing the memory key index to an attribute index stored in an extended append-only storage medium;
- receiving a read request comprising the table key, the read request being for a requested value paired with the table key;
- in response to the receiving the read request, looking for the requested value in the memory key index, using the table key;
- and
- in response to the requested value being determined not to be present in the memory key index, using a hash of the table key to access the attribute index to obtain the offset location
- in the table segment corresponding to the offset location from which the requested value is able to be obtained.
A non-transitory computer-readable medium comprising instructions that, in response to execution, cause a system comprising a processor to perform operations, comprising:
- receiving an update request comprising a table key and value corresponding to a table segment implemented in an append-only storage medium;
- appending the update request to the table segment by serializing the update request at an offset location in the table segment;
- updating a memory key index that is stored in memory with the offset location corresponding to the update request;
- asynchronously indexing the memory key index to an attribute index stored in an extended append-only storage medium;
- receiving a read request comprising the table key, the read request being for a requested value paired with the table key;
- in response to the receiving the read request, looking for the requested value in the memory key index using the table key;
- and
- in response to the requested value being determined not to be present in the memory key index, using a hash of the table key to access the attribute index to obtain the offset location in the table segment corresponding to the offset location from which the requested value is able to be obtained.
Dependencies are inferred from the claim text.