Scaling events for hosting hierarchical data structures

Patent metadata

Field	Value
Publication number	US-10423342-B1
Application number	US-201715475034-A
Country	US
Kind code	B1
Filing date	Mar 30, 2017
Priority date	Mar 30, 2017
Publication date	Sep 24, 2019
Grant date	Sep 24, 2019

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.

First claim

What is claimed is:

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

Assignees

• Amazon Tech Inc

Inventors

• Chheda Mahendra Manshi
• Mandadi Srikanth
• Acheson Alazel
• Baker Christopher Ryan
• Berry Jr Matthew William

Classifications

• G06F2206/1012

  Load balancing · CPC title

• G06F3/0685 Primary

  Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays · CPC title

• G06F3/0653

  Monitoring storage devices or systems · CPC title

• G06F3/065

  Replication mechanisms · CPC title

• G06F3/0619 Primary

  in relation to data integrity, e.g. data losses, bit errors · CPC title