Atomic application of multiple updates to a hierarchical data structure

Patent metadata

Field	Value
Publication number	US-10545950-B2
Application number	US-201615276714-A
Country	US
Kind code	B2
Filing date	Sep 26, 2016
Priority date	Sep 26, 2016
Publication date	Jan 28, 2020
Grant date	Jan 28, 2020

Abstract

Multiple edits to a hierarchical data structure may be atomically applied. A request to perform modifications with respect to a portion or the entire hierarchical data structure may be received. A copy of the requested portion of the hierarchical data structure may be created separate from the hierarchical data structure. The portion of the hierarchical data structure may remain available for read access. Modifications may be applied to the copy of the portion of the hierarchical data structure. In response to a request to commit the modifications to the portion of the hierarchical data structure, the copy of the portion of the hierarchical data structure may atomically replace the portion of the hierarchical data structure.

First claim

What is claimed is:

1. A system, comprising:
a hierarchical data store that stores a hierarchical data structure;
at least one processor and a memory storing program instructions that cause the at least one processor to implement a storage engine, configured to:
receive, via an interface, a request to initiate a bulk edit for at least a portion of the hierarchical data structure;
create a copy of the portion of the hierarchical data structure in the hierarchical data store that is separate from the hierarchical data structure, wherein the portion of the hierarchical data structure remains available for read access;
receive one or more requests to modify the portion of the hierarchical data structure;
access the hierarchical data store to perform one or more operations corresponding to the modification requests to modify the copy of the portion of the hierarchical data structure;
receive a request to commit the bulk edit for the portion of the hierarchical data structure; and
perform a transaction that atomically replaces the portion of the hierarchical data structure with the copy of the portion of the hierarchical data structure that includes the one or more modifications to the hierarchical data structure such that the modified portion of the hierarchical data structure becomes available for read and write access.

2. The system of claim 1 , wherein the storage engine is further configured to:
in response to the receipt of the request to initiate the bulk edit for the portion of the hierarchical data structure, block write access to the portion of the hierarchical data structure; and
upon performance of the transaction to atomically replace the portion of the hierarchical data structure with the copy of the portion of the hierarchical data structure, allow write access to the copy of the portion in the hierarchical data structure.

3. The system of claim 1 , wherein to perform the transaction to atomically replace the portion of the hierarchical data structure with the copy of the portion of the hierarchical data structure, the storage engine is configured to:
remove a link from the portion of the hierarchical data structure from the parent node; and
add a link from the copy of the portion of the hierarchical data structure to a parent node for the portion of the hierarchical data structure.

4. The system of claim 1 , wherein the storage engine is implemented as part of a resource management service for a provider network, wherein the provider network implements a plurality of different network-based services, wherein the hierarchical data structure comprises resource data objects that identify policies applicable to the behavior of resources corresponding to the resource data objects, and wherein the resources are implemented as part of the different network-based services.

5. A method, comprising:
performing, by one or more computing devices:
receiving a request to perform a plurality of modifications to at least a portion of a hierarchical data structure, wherein the hierarchical data structure comprises resource data objects that identify policies applicable to the behavior of a plurality of resources in a system that correspond to the resource data objects;
creating a copy of the portion of the hierarchical data structure that is separate from the hierarchical data structure, wherein the portion of the hierarchical data structure remains available for read access;
performing one or more operations to apply the modifications to the copy of the portion of the hierarchical data structure;
receiving a request to commit the modifications to the portion of the hierarchical data structure; and
atomically replacing the portion of the hierarchical data structure with the copy of the portion of the hierarchical data structure that includes the modification to the hierarchical data structure such that the modified portion of the hierarchical data structure becomes available for read and write access.

6. The method of claim 5 , further comprising:
in response to receiving the request to perform the modifications to the portion of the hierarchical data structure, blocking write access to the portion of the hierarchical data structure; and
upon atomically replacing the portion of the hierarchical data structure with the copy of the portion of the hierarchical data structure, allowing write access to the copy of the portion in the hierarchical data structure.

7. The method of claim 6 ,
wherein blocking write access to the portion of the hierarchical data structure comprises removing a lock indication for the portion of the data structure from a lock structure in the hierarchical data structure; and
wherein allowing write access to the copy of the portion in the hierarchical data structure comprises adding the lock indication for the portion of the data structure back to the lock structure in the hierarchical data structure.

8. The method of claim 5 , wherein the portion of the hierarchical data structure remains available for write access, and wherein the method further comprises:
prior to committing the modifications to the portion of the hierarchical data structure, replicating one or more writes received for the portion of the hierarchical data structure to the copy of the hierarchical data structure.

9. The method of claim 5 , wherein the request to perform the modifications to the portion of the hierarchical data structure is one of a plurality of received requests to perform respective modifications to the same portion of the hierarchical data structure.

10. The method of claim 9 , wherein atomically replacing the portion of the hierarchical data structure with the copy of the portion of the hierarchical data structure is further performed in response to determining that the modifications to commit do not conflict with the plurality of received requests for the same portion of the hierarchical data structure.

11. The method of claim 5 , further comprising:
wherein atomically replacing the portion of the hierarchical data structure with the copy of the portion of the hierarchical data structure comprises removing a link from the portion of the hierarchical data structure from the parent node; and
subsequent to atomically replacing the portion of the hierarchical data structure with the copy of the portion of the hierarchical data structure, reclaiming storage space in one or more storage devices maintaining the unlinked portion of the hierarchical data structure.

12. The method of claim 5 , wherein the request to perform the modifications to the portion of the hierarchical data structure and the request to commit the modifications are received via a programmatic interface, and wherein the method further comprises:
receiving, via the programmatic interface, one or more requests identifying the modifications to perform to the portion of the hierarchical data structure, wherein the one or more operations to apply the modifications to the copy of the portion of the hierarchical data structure are performed in response to receiving the requests identifying the modifications.

13. The method of claim 12 , wherein the one or more computing devices implement a system resource manager for the system.

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 a request to perform a plurality of modifications to at least a portion of a hierarchical data structure, wherein the hierarchical data structure comprises resource data objects that identify policies applicable to the behavior

Assignees

• Amazon Tech Inc

Inventors

• Collins Brian
• Shalla Zachary Mohamed
• Theimer Marvin Michael
• Petry John
• Hart Michael
• Hairanian Serge
• Samuelsson Anders
• Sepulveda Salvador Salazar
• Luo Ji

Classifications

• G06F16/2365 Primary

  Ensuring data consistency and integrity · CPC title

• G06F16/211

  Schema design and management · CPC title

• G06F16/282

  Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes · CPC title

• G06F16/2343

  Locking methods, e.g. distributed locking or locking implementation details · CPC title