Storing a non-ordered associative array of pairs using an append-only storage medium
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.
1. 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.
2. The method of claim 1 , wherein the update request comprises a compare version value, and further comprising:
validating, by the system, the compare version value with respect to an expected version value, and based on the validating, allowing the appending and the updating to proceed.
3. The method of claim 2 , further comprising:
waiting, by the system, for another update request to complete.
4. The method of claim 2 , further comprising:
looking, by the system, for the expected version value in the memory key index; and
in response to the expected version value being determined not to be present in the memory key index, using, by the system, 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 expected version value is able to be obtained.
5. The method of claim 4 , wherein the expected version value is not found in the memory key index, and further comprising:
adding, by the system, the expected version value to the memory key index before the updating of the memory key index with the offset location of the table key.
6. The method of claim 4 , wherein the expected version value is not found in the memory key index, wherein the attribute index is configured as a tree structure, and wherein the using the table key to access the attribute index comprises:
hashing, by the system, the table key into a hash value that corresponds to a node in the tree structure that comprises the offset location in the table segment from which the expected version value is able to be obtained.
7. The method of claim 1 , wherein the asynchronously indexing the memory key index to the attribute index comprises:
hashing, by the system, a set of table keys in the memory key index into a series of hash parts corresponding to each table key of the set of table keys;
grouping, by the system, data in the memory key index into subgroups based on the series of hash parts for each table key of the set of table keys; and
using, by the system, the subgroups for indexing the memory key index to the attribute index.
8. The method of claim 1 , wherein the using the table key to access the attribute index comprises:
hashing, by the system, the table key into a hash value that corresponds to a node in a tree structure that comprises the offset location in the table segment from which the requested value is able to be obtained.
9. 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.
10. The system of claim 9 , wherein the using the offset location data to return the requested value from the table segment in response to the read request comprises:
issuing a segment read request in conjunction with the offset location data.
11. The system of claim 9 , wherein the requested value is absent from the memory key index, wherein the attribute index is configured as a tree structure, and wherein the using the table key to access the attribute index comprises:
hashing the table key into a hash value that corresponds to a node in the tree structure that comprises the offset location data from which the requested value is able to be obtained.
12. The system of claim 11 , wherein the hashing the table key into the hash value comprises:
using a hash function to obtain the hash value, and dividing the hash value into a series of hash value parts, comprising a primary hash value part that corresponds to the node in the tree structure; and
in response to a collision with another primary hash value part of another hash value of another table key, a secondary hash value part that corresponds to a child node of the node in the tree structure.
13. The system of claim 9 , wherein the update request comprises a compare version value, and wherein the operations further comprise:
validating the compare version value with respect to an expected version value, and based on the validating, allowing the appending and the updating to proceed.
14. 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.
15. The non-transitory computer-readable medium of claim 14 , wherein the using the offset location data to return the requested value from the table segment in response to the read request comprises:
issuing a segment read request in conjunction with the offset location data.
16. The non-transitory computer-readable medium of claim 14 , wherein the requested value is absent from the memory key index, wherein the attribute index is configured as a tree structure, and wherein the using the table key to access the attribute index comprises:
hashing the table key into a hash value that corresponds to a node in the tree structure that comprises the offset location data from which the requested value is able to be obtained.
17. The non-transitory computer-readable medium of claim 16 , wherein the hashing the table key into the hash value comprises:
using a hash function to obtain the hash value, and dividing the hash value into a series of hash value parts, comprising a primary hash value part that corresponds to the node in the tree structure; and
in response to a collision with another primary hash value part of another hash value of another table key, a secondary hash value part that corresponds to a child node of the node in the tree structure.
18. The non-transitory computer-readable medium of claim 14 , wherein the operations further comprise:
asynchronously indexing the memory key index to the attribute index, relative to storing data in the append-only storage medium.
19. The non-transitory computer-readable medium of claim 18 , wherein the asynchronously indexing the memory key index to the attribute index comprises:
hashing a set of table keys in the memory key index into a series of hash parts corresponding to each table key of the set of table keys;
grouping data in the memory key index into subgroups based on the series of hash parts for each table key of the set of table keys; and
using the subgroups for indexing the memory key index to the attribute index.
20. The non-transitory computer-readable medium of claim 14 , wherein the update request comprises a compare version value, and wherein the operations further comprise:
validating the compare version value with respect to an expected version value, and based on the validating, allowing the appending and the updating to proceed.