Selectively replicating changes to hierarchial data structures

• US 10,671,639 B1
• Filed: 03/30/2017
• Issued: 06/02/2020
• Est. Priority Date: 03/30/2017
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Acheson, Alazel, Baker, Christopher Ryan, Chheda, Mahendra Manshi, Englert, James Robert, Li, Meng, Mandadi, Srikanth, Praus, Slavka, Watson, Colin
• Primary Examiner(s): Vy, Hung T
• Application Number:
  US15/475,031
• Time in Patent Office: 1,160 Days
• Field of Search: 707626, 707648, 707615
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2379 Updates performed during online database operations; commit processing
• CPC Class Codes: G06F 16/273 Asynchronous replication or reconciliation

Abstract

Updates to a hierarchical data structure may be selectively replicated to other replicas of the hierarchical data structure. An update for a hierarchical data structure may be received and committed to the hierarchical data structure. A determination as to whether any other replicas of the hierarchical data structure have permission to receive the update may be made. For those replicas of the hierarchical data structure with permission to receive the update, the update may be provided to the replicas and committed to the replicas. Different types of replication techniques may be implemented, such as pull-based replication techniques or push-based replication techniques. Replication permissions for objects of the hierarchical data structure may be individually defined, in some embodiments.

Claims

1. A system, comprising:

a plurality of distributed data stores, respectively comprising a plurality of compute nodes and respectively located in separate networks that are accessible to other ones of the distributed data stores via a network connection;

the distributed data stores, configured to;

receive an update to an object of a hierarchal data structure stored in one of the distributed data stores;

commit the update to a transaction log for the hierarchical data structure to apply the update to the object of the hierarchical data structure in the one distributed data store;

determine one or more replicas of the hierarchical data structure stored in different ones of the distributed data stores that are eligible to apply the update to the object according to a replication permission determined for the object;

send the update to the different distributed data stores; and

commit the update to respective transaction logs for the identified replicas of the hierarchical data structure to apply the update to corresponding objects of the identified replicas of the hierarchical data structure.

2. The system of claim 1, wherein the distributed data stores are further configured to receive at the one distributed data store a request to specify the different distributed data stores in the replication permission as eligible to receive updates to the object from a client of the one distributed data store.

3. The system of claim 1, wherein the distributed data stores are further configured to:

receive a request, at one of the different distributed data stores, to create a new object in the replica of the hierarchical data structure;

create the new object in the replica of the hierarchical data structure at the one different distributed data store;

receive a request to attach the new object in the one different distributed data store to the object in the one distributed data store;

send a request to attach the new object to the object to the one distributed data store;

attach the new object to the object at the one distributed data store; and

send an update from the one distributed data store to the one different distributed data store indicating the attachment of the new object to the object.

4. The system of claim 1, wherein the plurality of distributed data stores are implemented as part of a network-based directory storage service, wherein the directory storage service is separately hosted in the different networks as part of different regions offered by a provider network that offers the directory storage service.

5. A method, comprising:

performing, by one or more computing devices;

performing an update to an object of a hierarchal data structure stored in a distributed data store, wherein the update is committed to the object according to a transaction log for the hierarchical data structure;

identifying one or more replicas of the hierarchical data structure stored in respective remote distributed data stores that are eligible to apply the update to the object according to a replication permission determined for the object;

providing the update to the respective remote distributed data stores for the identified replicas of the hierarchical data structure; and

committing the update to respective transaction logs for the identified replicas of the hierarchical data structure to apply the update to corresponding objects of the identified replicas of the hierarchical data structure.

6. The method of claim 5, wherein the update to the object is provided to the respective remote distributed data stores in response to respective requests for updates received at the distributed data store from the remote distributed data stores.

7. The method of claim 5, wherein committing the update to respective transaction logs for the identified replicas of the hierarchical data structure comprises:

determining that the update to the object has not already been applied; and

determining that prior eligible updates received for the hierarchical data structure have been applied.

8. The method of claim 5, wherein identifying the one or more replicas of the hierarchical data structure stored in respective remote distributed data stores that are eligible to apply the update comprises evaluating one or more characteristics of a plurality of remote distributed data stores to select the respective remote distributed stores according to a characteristic for eligible remote distributed data stores for the object.

9. The method of claim 5, further comprising:

receiving a request to update another object in the hierarchical data structure at the distributed data store;

determining that mastery for the other object is limited to a replica of the hierarchical data structure stored in another remote distributed data store; and

blocking performance of the update to the other object in the hierarchical data structure at the distributed data store.

10. The method of claim 5, wherein another remote distributed data set that stores a replica of the hierarchical data structure is not eligible to apply the update to the object, and wherein the other remote distributed data set does not apply the update to the object.

11. The method of claim 5, further comprising receiving at the distributed data store a request to specify the respective remote distributed data stores in the replication permission as eligible to receive updates to the object from a client of the distributed data store.

12. The method of claim 5, further comprising attaching a new object created at one of the respective remote distributed data stores to the object at the distributed data store in response to a request to attach the new object to the object received at the one respective remote distributed data store.

13. The method of claim 5, wherein the distributed data store and the respective remote distributed data stores are implemented as part of a network-based directory storage service, wherein the distributed data store and the respective remote distributed data stores of the directory storage service are separately hosted in different networks as part of different regions offered by a provider network that offers the directory storage service.

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:

receiving an update to an object of a hierarchal data structure stored in a distributed data store;

committing the update to a transaction log for the hierarchical data structure to apply the update to the object of the hierarchical data structure in the distributed data store;

identifying one or more replicas of the hierarchical data structure stored in respective remote distributed data stores that are eligible to apply the update to the object according to a replication permission determined for the object;

providing the update to the respective remote distributed data stores for the identified replicas of the hierarchical data structure; and

committing the update to respective transaction logs for the identified replicas of the hierarchical data structure to apply the update to corresponding objects of the identified replicas of the hierarchical data structure.

15. The non-transitory, computer-readable storage medium of claim 14, wherein, in committing the update to respective transaction logs for the identified replicas of the hierarchical data structure comprises:

determining that the update to the object has not already been applied; and

determining that prior eligible updates received for the hierarchical data structure have been applied.

16. The non-transitory, computer-readable storage medium of claim 14, wherein providing the update to the respective remote distributed data stores is performed in response to applying the update to the object in the hierarchical data structure and identifying the one or more replicas of the hierarchical data structure that are eligible to apply the update.

17. The non-transitory, computer-readable storage medium of claim 14, wherein, in determining the replication permission to identify the one or more replicas of the hierarchical data structure stored in respective remote distributed data stores that are eligible to apply the update, the program instructions cause the one or more computing devices to implement evaluating one or more characteristics of a plurality of remote distributed data stores to select the respective remote distributed stores according to a common characteristic for eligible remote distributed data stores for the object.

18. The non-transitory, computer-readable storage medium of claim 14, wherein the program instructions further cause the one or more computing devices to implement receiving at the distributed data store a request to specify the respective remote distributed data stores in the replication permission as eligible to receive updates to the object from a client of the distributed data store.

19. The non-transitory, computer-readable storage medium of claim 14, wherein the program instructions further cause the one or more computing devices to implement receiving at the distributed data store a request to specify in the replication permission that at least one of the respective remote distributed data stores is no longer eligible to receive updates to the object from a client of the distributed data store.

20. The non-transitory, computer-readable storage medium of claim 14, wherein the program instructions cause the one or more computing devices to implement attaching a new object created at one of the respective remote distributed data stores to the object at the distributed data store in response to a request to attach the new object to the object received at the one respective remote distributed data store.