IPC분류정보
국가/구분 |
United States(US) Patent
등록
|
국제특허분류(IPC7판) |
|
출원번호 |
US-0316674
(2014-06-26)
|
등록번호 |
US-9619544
(2017-04-11)
|
발명자
/ 주소 |
- Vermeulen, Allan Henry
- Ho, Chi Hai
- Deardeuff, Michael Benjamin
|
출원인 / 주소 |
- Amazon Technologies, Inc.
|
대리인 / 주소 |
|
인용정보 |
피인용 횟수 :
5 인용 특허 :
11 |
초록
▼
A sequence of configuration-delta messages from a configuration manager of a replication graph established for replicating state information of an application is received at a particular node of the graph. Representations of the messages are stored in a local configuration change repository. Using t
A sequence of configuration-delta messages from a configuration manager of a replication graph established for replicating state information of an application is received at a particular node of the graph. Representations of the messages are stored in a local configuration change repository. Using the repository, the node identifies neighbor source nodes and destination nodes of the graph. Subsequent to receiving a particular configuration-delta message indicating that a neighbor source node has been removed from the graph, a different source node is identified by the particular node, and a request is sent to the different source node to transmit a set of state transition messages pertaining to the application.
대표청구항
▼
1. A system, comprising: one or more computing devices configured to: identify, at a first non-committer node of a directed acyclic graph (DAG) of nodes designated to replicate a state of an application, at least a portion of a first replication pathway to a first committer node of the DAG, based at
1. A system, comprising: one or more computing devices configured to: identify, at a first non-committer node of a directed acyclic graph (DAG) of nodes designated to replicate a state of an application, at least a portion of a first replication pathway to a first committer node of the DAG, based at least in part on a first sequence of configuration-delta messages received from a fault-tolerant DAG configuration manager, wherein at least one other node of the DAG has received a different sequence of configuration-delta messages from the fault-tolerant DAG configuration manager;transmit, from the first non-committer node, for replication at respective local storage devices of one or more nodes along the first replication pathway, a state transition message indicating (a) approval of a first candidate state transition requested by a client and (b) a sequence number indicative of an order in which the first candidate state transition is processed at the first non-committer node relative to other candidate state transitions;in response to a determination, by the fault-tolerant DAG configuration manager, that a particular node of the first replication pathway is to be removed from the DAG, initiate a transmission, from the fault-tolerant DAG configuration manager to one or more remaining nodes of the DAG, of a respective configuration-delta message indicating a removal of the particular node from the DAG, without directing the one or more remaining nodes to pause processing of state transitions. 2. The system as recited in claim 1, wherein a particular configuration-delta message received by a first remaining node of the one or more remaining nodes does not indicate a complete membership of the DAG. 3. The system as recited in claim 1, wherein the fault-tolerant DAG configuration manager comprises a plurality of configuration nodes that use a consensus-based protocol to determine that the particular node is to be removed from the DAG. 4. The system as recited in claim 1, wherein the one or more computing devices are further configured to: store, at the first committer node in response to a determination that a threshold number of replicas of records of the candidate state transition have been created, an indication that the candidate state transition has been committed;notify at least the first non-committer node that the candidate state transition has been committed; andnotify the client that the candidate state transition has been committed. 5. The system as recited in claim 1, wherein the first sequence of configuration-delta messages comprises a first configuration-delta message followed by a second configuration-delta message, and wherein the second sequence of configuration-delta messages comprises the second configuration-delta message followed by the first configuration-delta message. 6. A method, comprising: performing, by one or more computing devices: propagating a state transition message corresponding to a requested state transition from a first non-committer node of a directed acyclic graph (DAG) of replication nodes to a first committer node of the DAG, wherein the state transition message includes a sequence number indicative of an order in which the requested state transition was approved relative to other requested state transitions;in response to determining, by a DAG configuration manager, that a particular node is to be added to the DAG, initiating a propagation, from the DAG configuration manager to one or more other nodes of the DAG, of a configuration-delta message indicating the addition of the particular node to the DAG, without directing the one or more other nodes to pause processing of state transition messages. 7. The method as recited in claim 6, wherein the configuration-delta message does not indicate a complete membership of the DAG. 8. The method as recited in claim 6, further comprising performing, by the one or more computing devices: in response to determining, by the DAG configuration manager, that a different node is to be removed from the DAG, propagating from the DAG configuration manager to at least a first remaining node of the DAG, a second configuration-delta message indicating the removal of the different node from the DAG, without directing the first remaining node to pause processing of state transition messages. 9. The method as recited in claim 8, wherein the different node is an immediate predecessor of the first remaining node, further comprising: determining, at the first remaining node, a highest-received sequence number indicative of the most recent state transition message received from the different node; andtransmitting, from the first remaining node to a second remaining node of the DAG, wherein the second remaining node was an immediate predecessor of the different node prior to a removal of the different node, a request to transmit state transition messages with sequence numbers within a range based at least in part on the highest-received sequence number. 10. The method as recited in claim 6, wherein the requested state transition comprises a write operation to a data object stored at a database service. 11. The method as recited in claim 6, wherein the requested state transition comprises an insertion of a log message into a particular log of a logging service. 12. The method as recited in claim 6, wherein the DAG configuration manager comprises a plurality of configuration nodes, wherein said determining that the particular node is to be added comprises using a consensus-based protocol by the plurality of configuration nodes. 13. The method as recited in claim 6, wherein the one or more other nodes include a first node and a second node, further comprising performing, by the one or more computing devices: prior to receiving, at the first node, a configuration-delta message indicating a removal of a different node of the DAG, and subsequent to receiving, at the second node, a configuration-delta message indicating the removal of the different node: receiving, by the different node, a different state transition message from the second node;replicating, at the different node, a record corresponding to the different state transition message; andtransmitting, by the different node to the first node, the different state transition message. 14. The method as recited in claim 6, further comprising performing, by the one or more computing devices: storing, at the first committer node in response to a determination that a threshold number of replicas of representations of the requested state transition have been created, an indication that the requested state transition has been committed;notifying at least the first non-committer node that the requested state transition has been committed; andnotifying a client from which a request to implement the state transition was received that the state transition has been committed. 15. The method as recited in claim 6, further comprising performing, by the one or more computing devices: instantiating one or more standby nodes of the DAG;transmitting, to a particular standby node of the one or more standby nodes after respective representations of the requested state transition have been replicated at a threshold number of DAG nodes, the state transition message;storing, at the particular standby node, a record of the requested state transition; andselecting the particular standby node as a replacement for one of: (a) a failed non-committer node of the DAG or (b) a failed committer node of the DAG. 16. The method as recited in claim 6, wherein the first non-committer node comprises a process executing at a first host at a first data center of a provider network, and wherein the first committer node comprises a different process executing at a different host at a different data center of the provider network. 17. A non-transitory computer-accessible storage medium storing program instructions that when executed on one or more processors implement a particular node of a DAG established to replicate state information, wherein the particular node is configured to: receive, from a DAG configuration manager, a plurality of configuration-delta messages, wherein a particular configuration-delta message of the plurality of configuration-delta messages indicates one or more of: (a) an addition of a node to the DAG, or (b) a removal of a node from the DAG;subsequent to receiving the particular configuration-delta message from the DAG configuration manager, indicating that an immediate predecessor node from which a state transition message was received at the particular node has been removed from the DAG, identify, using at least the particular configuration-delta message, a different immediate predecessor node, andtransmit, to the different immediate predecessor node, a request for state transition messages. 18. The non-transitory computer-accessible storage medium as recited in claim 17, wherein the particular node is configured to: subsequent to receiving the particular configuration-delta message and prior to receiving a response to the request for state transition messages, transmit a particular state transition message to an immediate successor node of the particular node. 19. The non-transitory computer-accessible storage medium as recited in claim 17, wherein the particular node is configured to: subsequent to receiving a different configuration-delta message from the DAG configuration manager, indicating that an immediate successor node has been removed from the DAG, identify, using at least the different configuration-delta message, a different immediate successor node to which state transition messages are to be sent from the particular node, andinitiate an establishment of a network connection to the different immediate successor node. 20. A non-transitory computer-accessible storage medium storing program instructions that when executed on one or more processors implement a configuration manager of a DAG of nodes established to replicate state information, wherein the configuration manager is configured to: determine, based at least in part on a consensus protocol, that a particular node of the DAG is to be removed from the DAG, wherein the particular node occupies a particular position within the DAG;remove, from a persistent representation of a configuration of the DAG stored at the configuration manager, the particular node; andtransmit, to one or more remaining nodes of the DAG, a configuration-delta message indicating that the particular node has been removed from the DAG, without requesting the one or more remaining nodes to pause processing related to state transitions of the application. 21. The non-transitory computer-accessible storage medium storing program instructions as recited in claim 20, wherein the configuration manager is configured to: in response to a determination that the particular node is available for service as a member of the DAG, identify a different position within the DAG for the particular node; andtransmit, to the one or more remaining nodes of the DAG, another configuration-delta message indicating that the particular node has been added to the DAG at the different position within the DAG, without requesting the one or more remaining nodes to pause processing related to state transitions of the application. 22. The non-transitory computer-accessible storage medium as recited in claim 20, wherein the configuration-delta message does not indicate a complete membership of the DAG. 23. The non-transitory computer-accessible storage medium as recited in claim 20, wherein the configuration manager is configured to: identify a particular role that is assigned to the particular node prior to its removal from the DAG, wherein the role comprises one of: an acceptor node, an intermediate node, or a committer node; andassign the particular role to a different node of the DAG, wherein the different node comprises one of: (a) a successor node of the particular node prior to the removal or (b) a standby node of the DAG.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.