VERSIONED HIERARCHICAL DATA STRUCTURES IN A DISTRIBUTED DATA STORE

• US 20170300552A1
• Filed: 04/18/2016
• Published: 10/19/2017
• Est. Priority Date: 04/18/2016
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Mandadi, Srikanth, Berry, Matthew, Praus, Slavka, Baker, Chris, Theimer, Marvin Michael, Samuelsson, Anders, Sedky, Khaled Salah
• Granted Patent: US 11,157,517 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/1873 Versioning file systems, temporal file systems, e.g. file system supporting different historic versions of files
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/273 Asynchronous replication or reconciliation
• CPC Class Codes: G06F 16/282 Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

A distributed data store may maintain versioned hierarchical data structures. Different versions of a hierarchical data structure may be maintained consistent with a transaction log for the hierarchical data structure. When access requests directed to the hierarchical data structure are received, a version of the hierarchical data structure may be identified for processing an access request. For access requests with snapshot isolation, the identified version alone may be sufficient to consistently process the access request. For access requests with higher isolation requirements, such as serializable isolation, transactions based on the access request may be submitted to the transaction log so that access requests resulting in committed transactions may be allowed, whereas access requests resulting in conflicting transactions may be denied.

Claims

1. A system, comprising:

a plurality of storage nodes, comprising a processor and a memory, that store respective versions of a hierarchical data structure consistent with a transaction log for the hierarchical data structure;

a transaction log store, that maintains a transaction log for the hierarchical data structure;

individual ones of the storage nodes, configured to;

receive a read request for specified data stored as part of the hierarchical data structure from a client;

identify one of the respective versions of the hierarchical data structure maintained at the storage node for service of the read request;

access one or more locations at the storage node that store the specified data included in the identified version to obtain the specified data; and

return the specified data included in the identified version to the client.

2. The system of claim 1, wherein the individual ones of the storage nodes are further configured to:

receive a write request directed to the hierarchical data structure from another client;

identify one of the respective versions of the hierarchical data structure maintained at the storage node for service of the read request;

perform the write request with respect to the identified version of the hierarchical data structure at the storage node;

send a transaction to the transaction log store for the hierarchical data structure based on the write request, wherein the transaction indicates the identified version of the hierarchical data structure; and

in response to receipt of an indication from the transaction log store that the transaction is committed to the transaction log for the hierarchical data structure, send an acknowledgment of the write request to the other client.

3. The system of claim 2, wherein the individual ones of the storage nodes are further configured to:

obtain the transaction from the transaction log store;

apply the transaction to a current version of the hierarchical data structure maintained at the storage node; and

update historical version data for the hierarchical data structure maintained at the storage node to describe changes applied to the hierarchical data structure as a result of the transaction.

4. The system of claim 1, wherein the system is a network-based directory service, wherein the client is a client of the network-based directory service, wherein the storage nodes are multi-tenant storing one or more other hierarchical data structures maintained on behalf of one or more other clients of the network-based directory service, and wherein the identified version of the hierarchical data structure is maintained in the memory of the storage node.

5. A method, comprising:

performing, by one or more computing devices;

receiving an access request directed to a hierarchical data structure maintained as part of a distributed data store from a client;

identifying one of a plurality of versions of the hierarchical data structure for servicing the access request, wherein the plurality of versions of the hierarchical data structure are maintained in the distributed data store consistent with a transaction log for the hierarchical data structure that describes committed changes to the hierarchical data structure; and

servicing the access request utilizing the identified version of the hierarchical data structure.

6. The method of claim 5,

wherein the receiving, the identifying and the servicing of the access request are performed by one of a plurality of storage nodes that store versions of the hierarchical data structure in the distributed data store;

wherein the method further comprises;

prior to receiving the access request;

reading, by the one storage node, one or more transactions from the transaction log, wherein the one or more transactions to the transaction log were submitted to the transaction log by a different one of the plurality of storage nodes;

applying, by the one storage node, the one or more transactions to a current version of the hierarchical data structure maintained at the one storage node; and

wherein the identified version of the hierarchical data structure includes the one or more transactions.

7. The method of claim 5,

wherein the method further comprises sending a transaction to the transaction log for the hierarchical data structure based on the access request, wherein the transaction indicates the identified version of the hierarchical data structure;

wherein servicing the access request is performed in response to receiving an indication that the transaction is committed for the hierarchical data structure from the transaction log; and

wherein servicing the access request comprises sending an acknowledgment of the access request to the client.

8. The method of claim 7, wherein the access request directs performance of a plurality of operations performed with respect to different respective nodes of the hierarchical data structure, wherein the transaction sent to the transaction log includes the plurality of operations, and wherein the indication that the transaction is committed indicates that the plurality of operations are committed.

9. The method of claim 8, wherein at least one of the plurality of operations is dependent on the success of another one of the plurality of operations in the access request to be performed.

10. The method of claim 5, wherein the access request includes at least one of a specified isolation level or a specified consistency level for processing the access request, wherein servicing of the access request is performed according to the at least one specified isolation level or a specified consistency level.

11. The method of claim 5,

wherein the receiving, the identifying and the servicing of the access request are performed by one of a plurality of storage nodes that store versions of the hierarchical data structure in the distributed data store;

wherein the access request is read request;

wherein servicing the access request comprises sending, from the one storage node, a portion of the results generated for servicing the read request and a pagination token to the client, wherein the pagination token indicates remaining results to be sent to the client; and

wherein the method further comprises;

receiving at a different one of the storage nodes another read request from the client, wherein the other read request includes the pagination token;

in response to receiving the other read request at the different storage node, sending additional ones of the remaining results of the other read request to the client as indicated by the pagination token.

12. The method of claim 5,

wherein the access request specifies snapshot isolation for processing the access request;

wherein the method further comprises the further comprises

determining that the access request is processed according to snapshot isolation; and

wherein servicing the access request is performed in response to determining that the access request is processed according to snapshot isolation.

13. The method of claim 5,

wherein the receiving, the identifying and the servicing of the access request are performed by one of a plurality of storage nodes that store versions of the hierarchical data structure in the distributed data store;

wherein the access request indicates the beginning of a transaction and one or more operations;

wherein servicing the access request comprises sending, from the one storage node, performing the one or more operations and a transaction state token to the client, wherein the transaction state token indicates changes applied to the identified version of the hierarchical data structure as a result of the one or more operations; and

wherein the method further comprises;

receiving at a different one of the storage nodes another access request including one or more additional operations to be performed as part of the transaction from the client, wherein the other access request includes the transaction state token, wherein the other access request indicates that the transaction is to be committed;

in response to receiving the other access request at the different storage node;

modifying the identified version of the hierarchical data structure at the different storage node according to the changes indicated in the transaction state token; and

performing the one or more additional operations with respect to the modified version of the hierarchical data structure;

sending the transaction to the transaction log for the hierarchical data structure;

receiving an indication that the transaction is committed for the hierarchical data structure from the transaction log; and

in response to receiving the indication that the transaction is committed from the transaction log, sending an acknowledgment of the access request to the client.

14. A non-transitory, computer-readable storage medium, storing program instructions that when executed by one or more computing devices cause the one or more computing devices to implement:

maintaining respective versions of a hierarchical data structure at a plurality of storage nodes in a distributed data store consistent with a transaction log for the hierarchical data structure that describes committed changes to the hierarchical data structure;

receiving an access request directed to the hierarchical data structure at one of the storage nodes;

identifying one of the respective versions of the hierarchical data structure maintained at the one storage node for servicing the access request; and

servicing the access request utilizing the identified version of the hierarchical data structure.

15. The non-transitory, computer-readable storage medium of claim 14,

wherein the program instructions cause the one or more computing devices to further implement sending, from the storage node, a transaction to the transaction log for the hierarchical data structure based on the access request, wherein the transaction indicates the identified version of the hierarchical data structure;

wherein servicing the access request is performed in response to receiving an indication that the transaction is committed for the hierarchical data structure from the transaction log; and

wherein in servicing the access request, the program instructions cause the one or more computing devices to implement sending an acknowledgment of the access request.

16. The non-transitory, computer-readable storage medium of claim 15, wherein the program instructions cause the one or more computing devices to further implement:

respectively obtaining the transaction at the plurality of storage nodes;

applying the transaction to respective current versions of the hierarchical data structure maintained at the storage nodes; and

updating respective historical version data for the hierarchical data structure maintained at the storage nodes to describe changes applied to the hierarchical data structure as a result of the transaction.

17. The non-transitory, computer-readable storage medium of claim 14, wherein the program instructions cause the one or more computing devices to further implement:

copying the transaction log to an archived version of the transaction log stored in a remote data store; and

applying one or more transactions from the remote transaction log to a version of the hierarchical data structure at one of the plurality of storage nodes to generate a version of the hierarchical data structure at a specified point-in-time.

18. The non-transitory, computer-readable storage medium of claim 15,

wherein the access request comprises an expected condition for the hierarchical data structure;

wherein the program instructions cause the one or more computing devices to further implement evaluating the expected condition with respect to the identified version of the hierarchical data structure to determined that the expected condition is satisfied;

wherein sending the transaction to the transaction log is performed in response to determining that the expected condition is satisfied, wherein access requests including expected conditions that are not determined to be satisfied are denied.

19. The non-transitory, computer-readable storage medium of claim 14, wherein the access request comprises a read request, wherein the version identified is not a current version of the hierarchical data structure, and wherein in servicing the access request, the program instructions cause the one or more computing devices to implement accessing historical version data for the hierarchical data structure to read a prior version of one or more nodes of the hierarchical data structure.

20. The non-transitory, computer-readable storage medium of claim 14, wherein the distributed data store is a network-based storage service that offers a plurality of different service level agreements for different access requests to the network-based storage service, and wherein the program instructions cause the one or more computing devices to further implement routing the access request to the storage node according to one of the different service level agreements identified for processing the access request, wherein the storage node is configured to process the access request according to the identified service level agreement.