Replication protocol with consensus for a decentralized control plane in a computer system

• US 10,481,821 B2
• Filed: 06/28/2016
• Issued: 11/19/2019
• Est. Priority Date: 06/28/2016
• Status: Active Grant

• Current Assignee: Vmware LLC (Broadcom, Inc.)
• Original Assignee: VMware, Inc. (Broadcom, Inc.)
• Inventors: Chrysanthakopoulos, Georgios, Noordhuis, Pieter
• Primary Examiner(s): Chea, Philip J
• Assistant Examiner(s): Ahmed, Mohammed
• Application Number:
  US15/195,489
• Publication Number:
  US 20170374145A1
• Time in Patent Office: 1,239 Days
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/23 Updating
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 2209/5011 Pool
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0647 Migration mechanisms
• CPC Class Codes: G06F 3/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/0673 Single storage device
• CPC Class Codes: G06F 8/315 Object-oriented languages
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals
• CPC Class Codes: G06F 9/541 via adapters, e.g. between incompatible applications
• CPC Class Codes: G06F 9/542 Event management; Broadcasting; Multicasting; Notifications
• CPC Class Codes: H04L 41/0893 Assignment of logical groups to network elements
• CPC Class Codes: H04L 41/20 Network management software packages
• CPC Class Codes: H04L 67/01 Protocols
• CPC Class Codes: H04L 67/02 based on web technology, e.g. hypertext transfer protocol [HTTP]
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1095 : Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04L 67/51 : Discovery or management thereof, e.g. service location protocol [SLP] or web services
• CPC Class Codes: H04L 67/60 : Scheduling or organising the servicing of application requests, e.g. requests for application data transmissions using the analysis and optimisation of the required network resources admission control or resource allocation H04L47/70
• CPC Class Codes: H04L 67/63 : Routing a service request depending on the request content or context

Abstract

A method of replicating service state among a plurality of nodes in a computer system includes sending a request for a service to an owner node, the owner node being selected based on the service targeted by the request; receiving a completion of the request after execution of a handler of a service instance on the owner node, where the service instance is an instance of the service and the completion indicates that the handler successfully updated a state of the service on the owner node; replicating the updated state of the service as a proposed state among a plurality of peer nodes and receiving replies from the plurality of peer nodes about verification of the proposed state; and providing a response to the request, from the owner node, for transmission to a client that originated the request, the response being generated based on the replies.

Claims

1. A method of replicating service state among a plurality of nodes in a computer system, comprising:

sending a request for a service to an owner node of the plurality of nodes, the owner node being selected based on the service targeted by the request;

receiving a completion of the request after execution of a handler of a service instance on the owner node, where the service instance is an instance of the service and the completion indicates that the handler successfully updated a state of the service on the owner node;

replicating the updated state of the service as a proposed state among a plurality of peer nodes of the plurality of nodes and receiving replies from the plurality of peer nodes about verification of the proposed state at each of the peer nodes;

determining whether success replies in the replies have been received from a quorum of the plurality of peer nodes, sending requests to commit the proposed state at each of the peer nodes in response to achieving the quorum, and initiating synchronization of state among the plurality of peer nodes in response to not achieving the quorum; and

providing a response to the request for the service, from the owner node, for transmission to a client that originated the request.

2. The method of claim 1, wherein the step of sending the request comprises:

generating a key based on a property of the service; and

selecting the owner node from the plurality of nodes based on the key.

3. The method of claim 2, wherein the step of generating the key comprises computing a hash of a uniform resource indicator (URI) of the service as the key, and wherein the step of selecting the owner node comprises comparing the hash of the URI with hashed identifiers of the plurality of nodes and selecting a node of the plurality of nodes having a hashed identifier nearest the hash of the URI.

4. The method of claim 1, wherein the request is received from the client at a predetermined peer node of the plurality of peer nodes, and wherein the step of sending the request comprises forwarding the request from the predetermined peer node to the owner node.

5. The method of claim 4, wherein the step of providing the response comprises:

forwarding the response from the owner node to the predetermined peer node; and

sending the response from the predetermined peer node to the client.

6. The method of claim 1, further comprising:

verifying the proposed state of the service at each peer node of the plurality of peer nodes.

7. The method of claim 6, wherein the owner node provides an owner of the service, a version of the proposed state, and an epoch to the plurality of peer nodes, and wherein the step of verifying the proposed state at each peer node of the plurality peer nodes comprises:

determining whether an owner, a version, and an epoch associated with a current state of the service at the peer node agrees with the owner, the version, and the epoch received from the owner node;

sending a success reply from the peer node to the owner node in response to a determined agreement; and

sending a failure reply from the peer node to the owner node in response to a determined disagreement.

8. The method of claim 7, further comprising, in response to a determined agreement, storing the proposed state in a document store at the peer node.

9. The method of claim 1, further comprising:

setting a body of the response to indicate a failure to update the state of the service in response to a number of success replies in the replies from the plurality of peer nodes failing to satisfy the quorum of the plurality of peer nodes.

10. The method of claim 1, further comprising:

committing the updated state at the owner node and the proposed state at the plurality of peer nodes in response to a number of success replies in the replies from the plurality of peer nodes satisfying the quorum of the plurality of peer nodes.

11. A computer system, comprising:

a plurality of host computers supporting execution of a plurality of nodes, the plurality of nodes supporting execution of a plurality of services and a framework, the framework executable by the plurality of host computers to;

send a request for a service of the plurality of services, to an owner node of the plurality of nodes, the owner node being selected based on the service targeted by the request;

receive a completion of the request after execution of a handler of a service instance on the owner node, where the service instance is an instance of the service and the completion indicates that the handler successfully updated a state of the service on the owner node;

replicate the updated state of the service as a proposed state among a plurality of peer nodes of the plurality of nodes and receiving replies from the plurality of peer nodes about verification of the proposed state at each of the peer nodes;

determine whether success replies in the replies have been received from a quorum of the plurality of peer nodes, sending requests to commit the proposed state at each of the peer nodes in response to achieving the quorum, and initiating synchronization of state among the plurality of peer nodes in response to not achieving the quorum; and

provide a response to the request for the service, from the owner node, for transmission to a client that originated the request.

12. The computer system of claim 11, wherein the framework is executable by the plurality of host computers to:

generate a key based on a property of the service; and

select the owner node from the plurality of nodes based on the key.

13. The computer system of claim 12, wherein the framework is executable by the plurality of host computers to compute a hash of a uniform resource indicator (URI) of the service as the key, compare the hash of the URI with hashed identifiers of the plurality of nodes, and select a node of the plurality of nodes having a hashed identifier nearest the hash of the URI.

14. The computer system of claim 11, wherein the request is received from the client at a predetermined peer node of the plurality of peer nodes, and wherein the framework is executable by the plurality of host computers to forward the request from the predetermined peer node to the owner node.

15. The computer system of claim 14, wherein the framework is executable by the plurality of host computers to:

forward the response from the owner node to the predetermined peer node; and

send the response from the predetermined peer node to the client.

16. The computer system of claim 11, wherein the framework is executable by the plurality of host computers to:

verify the proposed state of the service at each peer node of the plurality of peer nodes.

17. The computer system of claim 16, wherein the framework is executable by the plurality of host computers to:

setting a body of the response to indicate a failure to update the state of the service in response to a number of success replies in the replies from the plurality of peer nodes failing to satisfy the quorum of the plurality of peer nodes.

18. The computer system of claim 16, wherein the framework is executable by the plurality of host computers to:

commit the updated state at the owner node and the proposed state at the plurality of peer nodes in response to a number of success replies in the replies from the plurality of peer nodes satisfying the quorum of the plurality of peer nodes.

19. A non-transitory computer readable medium comprising instructions, which when executed in a computer system, causes the computer system to carry out a method of replicating service state among a plurality of nodes in a computer system, comprising:

sending a request for a service to an owner node of the plurality of nodes, the owner node being selected based on the service targeted by the request;

receiving a completion of the request after execution of a handler of a service instance on the owner node, where the service instance is an instance of the service and the completion indicates that the handler successfully updated a state of the service on the owner node;

replicating the updated state of the service as a proposed state among a plurality of peer nodes of the plurality of nodes and receiving replies from the plurality of peer nodes about verification of the proposed state at each of the peer nodes;

determining whether success replies in the replies have been received from a quorum of the plurality of peer nodes, sending requests to commit the proposed state at each of the peer nodes in response to achieving the quorum, and initiating synchronization of state among the plurality of peer nodes in response to not achieving the quorum; and

providing a response to the request for the service, from the owner node, for transmission to a client that originated the request.

20. The non-transitory computer readable medium of claim 19, wherein the step of sending the request comprises:

generating a key based on a property of the service; and

selecting the owner node from the plurality of nodes based on the key; and

wherein the step of generating the key comprises computing a hash of a uniform resource indicator (URI) of the service as the key, and wherein the step of selecting the owner node comprises comparing the hash of the URI with hashed identifiers of the plurality of nodes and selecting a node of the plurality of nodes having a hashed identifier nearest the hash of the URI.