Scaling stateful clusters while maintaining access

• US 10,216,770 B1
• Filed: 10/31/2014
• Issued: 02/26/2019
• Est. Priority Date: 10/31/2014
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Kulesza, Jakub, Srinivasan, Srividhya, Agarwal, Deepak, Gupta, Anurag Windlass
• Primary Examiner(s): Phillips, III, Albert M
• Assistant Examiner(s): Onat, Alp
• Application Number:
  US14/530,480
• Time in Patent Office: 1,579 Days
• CPC Class Codes: G06F 16/182 Distributed file systems
• CPC Class Codes: G06F 16/21 Design, administration or maintenance of databases
• CPC Class Codes: G06F 9/50 Allocation of resources, e.g. of the central processing unit [CPU]
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: G06F 9/5072 Grid computing

Abstract

A stateful cluster may implement scaling of the stateful cluster while maintaining access to the state of the stateful cluster. A scaling event for a stateful cluster may be detected, and in response the stateful cluster may be adjusted to include a different number of nodes. The state of the cluster may then be logically distributed among the different number of nodes according to a monotone distribution scheme. The adjusted node may then service access requests according to the monotone distribution scheme. Prior to making the adjusted storage cluster available for servicing access requests, the nodes from the original cluster may still service access requests for state.

Claims

1. A distributed storage system, comprising:

a first plurality of storage nodes implemented via respective processors and memory that together implement a storage cluster that stores data for a client, wherein the data is segmented across the plurality of storage nodes;

a control plane for the distributed storage system, implemented via one or more processors and memory to;

detect a scaling event for the storage cluster;

in response to the detection of the scaling event;

adjust the storage cluster to include an adjusted number of storage nodes that is different than the first plurality of storage nodes according to the scaling event;

provide an indication of the scaling event to a leader node for the storage cluster;

the leader node for the storage cluster, implemented via one or more processors and memory to;

receive the indication of the scaling event;

in response to the receipt of the scaling event,

logically reassign responsibility for processing access requests for the data across the adjusted number of storage nodes in the adjusted storage cluster according to a monotone distribution scheme before the data is moved to the adjusted number of storage nodes;

at least one of the adjusted number of storage nodes in the adjusted storage cluster to physically redistribute the data, comprising;

obtain, in response to receipt of an access request distributed according to the logically reassigned responsibility, a portion of data from at least one of the first plurality of storage nodes that maintains a segment of the data in order to process the access request; and

store the obtained portion of the data;

the adjusted storage cluster to process access requests for the data at the number of storage nodes in the adjusted storage cluster according to the monotone distribution scheme, wherein prior to making the adjusted storage cluster available, the plurality of storage nodes are available to process other access requests for the data as segmented across the plurality of storage nodes.

2. The system of claim 1,

wherein the scaling event for the storage cluster indicates a size increase such that the number of storage nodes included in the adjusted storage cluster is greater than the first plurality of storage nodes;

wherein another scaling event is detected for the storage cluster at the control plane;

wherein the control plane is further configured to perform another adjustment of the storage cluster, and another provision of the indication of the other scaling event to the leader node in response to the detection of the other scaling event; and

wherein the leader node is further configured to perform another the logically reassign responsibility for processing access requests for the data, wherein the other scaling event indicates a size decrease such that the number of storage nodes included in the storage cluster in response to the other scaling event is less than the adjusted number of storage nodes.

3. The system of claim 1,

wherein the leader node is further configured to direct physical distribution of the data across the adjusted number of storage nodes in the adjusted storage cluster according to the monotone distribution scheme, in response to receipt of the indication of the scaling event, wherein upon completion of the physical distribution the at least one storage node of the adjusted number of storage nodes included in the adjusted storage cluster processes subsequent access requests based, at least in part, on a portion of data obtained from local storage.

4. The system of claim 1, wherein the distributed storage system is a network-based data warehouse, wherein the client is one of a plurality of clients of the network-based data warehouse, and wherein the storage cluster is one of a plurality of storage clusters.

5. A method, comprising:

performing, by a plurality of computing devices;

maintaining state segmented across a stateful cluster that comprises a first plurality of nodes maintaining the state;

detecting a scaling event for the stateful cluster;

in response to detecting the scaling event;

adjusting the stateful cluster to include a number of nodes that is different than the first plurality of nodes according to the scaling event;

logically reassigning responsibility for the state across the number of nodes in the adjusted stateful cluster according to a monotone distribution scheme before moving the state to the number of nodes;

physically redistributing, by at least one node of the adjusted stateful cluster, the state, comprising;

obtaining, in response to receiving an access request distributed according to the logically reassigned responsibility, a portion of state from at least one of the first plurality of nodes according to a segmentation of the state across the first plurality of nodes as maintained prior to the scaling event in order to process access requests; and

storing the obtained portion of the state; and

processing access requests for the state at the number of nodes in the adjusted stateful cluster according to the monotone distribution scheme, wherein prior to making the adjusted stateful cluster available, the plurality of nodes are available to process other access requests for the state as segmented across the plurality of nodes.

6. The method of claim 5, wherein the scaling event for the stateful cluster indicates a size increase such that the number of nodes included in the adjusted stateful cluster is greater than the plurality of nodes.

7. The method of claim 6, wherein another scaling event is detected for the stateful cluster, and wherein the method further comprises:

performing another adjusting of the stateful cluster, and another logically distributing the state, wherein the other scaling event indicates a size decrease such that the number of nodes included in the stateful cluster in response to the other scaling event is less than the number of nodes included in response to the scaling event.

8. The method of claim 5, wherein the method further comprises:

in response to detecting the scaling event, physically distributing the state across the number of nodes in the adjusted stateful cluster according to the monotone distribution scheme, wherein upon completion of the physical distribution the at least one node of the number of nodes included in the adjusted stateful cluster processes subsequent access requests without obtaining a portion of state from a node in the plurality of nodes.

9. The method of claim 8, wherein physically distributing the state across the number of nodes is performed as part of background processing, and wherein processing the access requests at the number of nodes included in the adjusted stateful cluster is performed as part of foreground processing.

10. The method of claim 5, wherein detecting the scaling event for the stateful cluster comprises receiving a scaling request from a client via a network-based interface for the stateful cluster.

11. The method of claim 5, wherein detecting the scaling event for the stateful cluster is based, at least in part, on processing utilization, storage capacity, or networking bandwidth for the plurality of nodes.

12. The method of claim 5, further comprising:

receiving, at the at least one node of the number of nodes included in the adjusted stateful cluster, an access request for a select portion of the state;

in response to receiving the access request;

obtaining the select portion of the state from the at least one node of the plurality of nodes in the stateful cluster; and

servicing the access request at the at least one node of the number of nodes based, at least in part, on the obtained select portion.

13. The method of claim 5, wherein the stateful cluster is a distributed data store and wherein the state is data maintained for a client of the distributed data store.

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 data for a storage client that is segmented across a storage cluster that comprises a first plurality of storage nodes;

detecting a scaling event for the storage cluster; and

in response to detecting the scaling event;

adjusting the storage cluster to include a number of storage nodes that is different than the plurality of storage nodes according to the scaling event;

logically reassigning responsibility for the data across the number of storage nodes in the adjusted storage cluster according to a monotone distribution scheme before moving the data to the number of storage nodes;

physically redistributing the data, comprising;

obtaining, in response to receiving an access request distributed according to the logically reassigned responsibility, by at least one of the number of storage nodes in the adjusted storage cluster, a portion of data from at least one of the first plurality of storage nodes maintaining a segment of the data in order to process access requests; and

storing, by the at least one storage node, the portion of the data; and

processing access requests for the data at the number of storage nodes in the adjusted storage cluster according to the monotone distribution scheme, wherein prior to making the adjusted storage cluster available, the plurality of storage nodes are available to process other access requests for the data as segmented across the plurality of storage nodes.

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

wherein the scaling event for the storage cluster indicates a size increase such that the number of storage nodes included in the adjusted storage cluster is greater than the first plurality of storage nodes;

wherein another scaling event is detected for the storage cluster; and

wherein the program instructions cause the one or more computing devices to further implement performing another adjusting of the storage cluster, another logically distributing of the data, and wherein the other scaling event indicates a size decrease such that the number of storage nodes included in the adjusted storage cluster in response to the other scaling event is less than the number of storage nodes included in response to the scaling event.

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

in response to detecting the scaling event, physically distributing the data across the number of storage nodes in the adjusted storage cluster according to the monotone distribution scheme, wherein upon completion of the physical distribution the at least one storage node of the number of storage nodes included in the adjusted storage cluster processes subsequent access requests without obtaining a portion of data from a storage node in the plurality of storage nodes.

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

upon completion of the physical distribution of the data across the number of storage nodes in the adjusted storage cluster;

receiving at a storage node of the number of storage nodes included in the adjusted storage cluster, an access request for a select portion of the data;

in response to receiving the access request;

obtaining the select portion of the state from storage local to the storage node; and

servicing the access request at the storage node based, at least in part, on the obtained select portion.

18. The non-transitory, computer-readable storage medium of claim 14, wherein the scaling event for the storage cluster indicates a size decrease such that the number of storage nodes included in the adjusted storage cluster is less than the plurality of storage nodes.

19. The non-transitory, computer-readable storage medium of claim 14, wherein, in detecting the scaling event for the storage cluster, the program instructions cause the one or more computing devices to implement receiving a scaling request from the client via a network-based interface for the storage cluster.

20. The non-transitory, computer-readable storage medium of claim 14, wherein the storage cluster is implemented as part of a network-based storage service, and wherein the client is one of a plurality of clients of the network-based storage service.