Scaling events for hosting hierarchical data structures

• US 10,423,342 B1
• Filed: 03/30/2017
• Issued: 09/24/2019
• 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: Chheda, Mahendra Manshi, Mandadi, Srikanth, Acheson, Alazel, Baker, Christopher Ryan, Berry, Jr., Matthew William
• Primary Examiner(s): Padmanabhan, Mano
• Assistant Examiner(s): Baughman, William E.
• Application Number:
  US15/475,034
• Time in Patent Office: 908 Days
• CPC Class Codes: G06F 2206/1012 Load balancing
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/0653 Monitoring storage devices or systems
• CPC Class Codes: G06F 3/0685 Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays

Abstract

Scaling events may be detected for hosting hierarchical data structures. Scaling events may be detected to modify the capacity of a data store for hierarchical data structures to handle changing write workloads, read workloads, or storage capacity. Hierarchical data structures may be moved from one group of storage hosts to another group of storage hosts according to a filtered snapshot that includes the hierarchical data structures to be moved that is provided to the destination storage hosts. Changes made to the hierarchical data structures made at the source storage hosts during the move can be applied to the filtered snapshot so that the hierarchical data structures may be made available at the destination storage hosts inclusive of the changes.

Claims

1. A system, comprising:

one or more compute nodes, respectively comprising at least one processor and a memory, configured to;

detect an event to move one or more of a plurality of hierarchical data structures stored at a plurality of storage hosts to a plurality of destination storage hosts, wherein updates to the hierarchical data structures are applied to the hierarchical data structures amongst the storage hosts according to, and dependent upon the updates being successfully committed to, a separately hosted transaction log that commits updates to the hierarchical data structures;

generate a filtered snapshot of the hierarchical data structures stored at the storage hosts that excludes those hierarchical data structures not to be moved from the storage hosts;

provide the filtered snapshot to the destination storage hosts;

register the destination storage hosts with the transaction log to receive updates for the one or more hierarchical data structures committed to the transaction log;

commit an update to the transaction log indicating the movement of the one or more hierarchical data structures to the destination storage hosts that is applied by the storage hosts to block processing of subsequently received access requests for the one or more hierarchical data structures at the storage hosts; and

update mapping information to direct access requests for the one or more hierarchical data structures to the destination storage hosts.

2. The system of claim 1, wherein the one or more compute nodes are further configured to commit a transition to the transaction log to move the one or more hierarchical data structures to a different transaction log, wherein the destination storage hosts obtain the transition from the transaction log and apply the transition at the destination storage host to direct subsequent requests to commit updates to the one or more hierarchical data structures to the different transaction log.

3. The system of claim 1, wherein the one or more compute nodes are further configured to:

detect an event to add at least one storage host to the destination hosts for processing access requests to the one or more hierarchical data structures; and

provision the at least one storage host to include with the destination storage hosts, wherein the at least one storage host gets a snapshot of the one or more hierarchical data structures at the destination storage hosts and connects with the transaction log for the one or more hierarchical data structures.

4. The system of claim 1, wherein the one or more compute nodes are implemented as part of a network-based directory storage service, wherein each of the hierarchical data structures is a different directory structure hosted on behalf of a different client of the directory storage service.

5. A method, comprising:

performing, by one or more computing devices;

identifying one or more hierarchical data structures stored at a plurality of storage hosts to move to a plurality of destination storage hosts, wherein updates to the hierarchical data structures are applied to the hierarchical data structures amongst the storage hosts according to, and dependent upon the updates being successfully committed to, a transaction log that commits updates to the hierarchical data structures;

generating a filtered snapshot of the hierarchical data structures stored at the storage hosts that excludes those hierarchical data structures not to be moved from the storage hosts;

providing the filtered snapshot to the destination storage hosts;

updating the transaction log to commit the movement of the one or more hierarchical data structures to the destination storage hosts; and

making the one or more hierarchical data structures available for processing access requests at the destination storage hosts.

6. The method of claim 5, wherein the identifying the one or more hierarchical data structures stored at the plurality of storage hosts to move comprises evaluating one or more characteristics of the hierarchical data structures to select the one or more hierarchical data structures out of a plurality of hierarchal data structures stored at the plurality of storage hosts.

7. The method of claim 5, further comprising:

detecting an event to move the one or more hierarchical data structures to the destination storage hosts; and

provisioning the destination storage hosts to store the one or more hierarchical data structures.

8. The method of claim 5, further comprising reclaiming storage for the one or more hierarchical data structures at the storage hosts subsequent to making the destination storage hosts available for processing access requests to the one or more hierarchical data structures.

9. The method of claim 5, further comprising:

obtaining the commitment of the movement of the one or more hierarchal data structures from the transaction log at the storage hosts; and

blocking subsequently received access requests for the one or more hierarchical data structures at the storage hosts.

10. The method of claim 5, further comprising applying one or more changes obtained from the transaction log to a version of the one or more hierarchal data structures in the filtered snapshot at the destination storage hosts.

11. The method of claim 5, further comprising:

committing a transition to the transaction log to move the one or more hierarchical data structures to a different transaction log;

obtaining, at the destination storage hosts, the transition to the different transaction log from the transaction log; and

applying the transition at the destination storage hosts to direct subsequent requests to commit updates to the one or more hierarchal data structures to the different transaction log.

12. The method of claim 5, wherein the generating of the filtered snapshot is performed by a resource that is separate from the storage hosts.

13. The method of claim 5, wherein the identifying, the generating, the providing, the updating, and the making are performed as part of a network-based directory storage service, wherein each of the hierarchical data structures is a different directory structure hosted on behalf of a different client of 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:

detecting an event to move one or more of a plurality of hierarchical data structures stored at a plurality of storage hosts to a plurality of destination storage hosts, wherein updates to the hierarchical data structures are applied to the hierarchical data structures amongst the storage hosts according to, and dependent upon the updates being successfully committed to, a transaction log that commits updates to the hierarchical data structures;

generating a filtered snapshot of the hierarchical data structures stored at the storage hosts that excludes those hierarchical data structures not to be moved from the storage hosts;

providing the filtered snapshot to the destination storage hosts;

updating the transaction log to commit the movement of the one or more hierarchical data structures to the destination storage hosts; and

making the one or more hierarchical data structures available for processing access requests at the destination storage hosts.

15. The non-transitory, computer-readable storage medium of claim 14, wherein, in detecting the event to move the one or more of the plurality of hierarchical data structures, the program instructions cause the one or more computing devices to implement receiving a request to move the one or more hierarchal data structures that specifies the hierarchical data structures.

16. The non-transitory, computer-readable storage medium of claim 14, wherein, in detecting the event to move the one or more of the plurality of hierarchical data structures, the program instructions cause the one or more computing devices to implement monitoring one or more performance metrics for the storage hosts to detect the event.

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 applying one or more changes obtained from the transaction log to a version of the one or more hierarchal data structures in the filtered snapshot at the destination storage hosts.

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

committing a transition to the transaction log to move the one or more hierarchical data structures to a different transaction log;

obtaining, at the destination storage hosts, the transition to the different transaction log from the transaction log; and

applying the transition at the destination storage hosts to direct subsequent requests to commit updates to the one or more hierarchal data structures to the different transaction log.

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

detecting an event to add at least one storage host to the destination hosts for processing access requests to the one or more hierarchical data structures;

provisioning the at least one storage host to include with the destination storage hosts;

obtaining, at the at least one storage host, a snapshot of the one or more hierarchical data structures at the destination storage hosts; and

connecting the at least one storage host with the transaction log for the one or more hierarchical data structures to allow processing of access requests at the at least one storage host.

20. The non-transitory, computer-readable storage medium of claim 14, wherein the detecting, the generating, the providing, the updating, and the making are performed as part of a network-based directory storage service, wherein each of the hierarchical data structures is a different directory structure hosted on behalf of a different client of the directory storage service.