LEADERLESS CONSISTENCY PROTOCOL

• US 20180219946A1
• Filed: 07/25/2016
• Published: 08/02/2018
• Est. Priority Date: 07/23/2015
• Status: Abandoned Application

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: FARRAHI MOGHADDAM, Fereydoun, KANSO, Ali
• Application Number:
  US15/746,645
• Publication Number:
  US 20180219946A1
• Time in Patent Office: Days
• CPC Class Codes: G06F 11/1474 in transactions G06F16/20 takes precedence
• CPC Class Codes: G06F 11/18 using passive fault-masking of the redundant circuits error detection by comparing the output of redundant processing systems with continued operation after detection of the error G06F11/165
• CPC Class Codes: G06F 11/183 by voting, the voting not being performed by the redundant components
• CPC Class Codes: G06F 9/466 Transaction processing
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• 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/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

Systems and methods are provided for processing requests, received from clients and peer nodes, in a leaderless cluster of nodes. A node can initiate a read or a write operation in the cluster. The node can solicit votes from its peer nodes in order to confirm that the requested operation should be performed. A threshold number of positive responses, such as a supermajority of the nodes in the cluster, can be required in order to confirm the requested operation.

Claims

1. A method for performing a write operation by a first node in a leaderless cluster of nodes, the method comprising:

receiving a write operation request, including data to be stored, from a client device;

assigning a first sequence number to the received write operation request;

transmitting a write command, including the data and the first sequence number, to a plurality of peer nodes in the cluster;

receiving at least one sequence number validation message from at least one peer node in response to the write command, the sequence number validation message indicating one of a confirmation of the first sequence number or a proposal for a second sequence number; and

responsive to determining that a threshold number of confirmations of the first sequence number or proposals for the second sequence number have been received from peer nodes, transmitting an acknowledgement of the write operation to the client device.

2. The method of claim 1, further comprising, responsive to determining that a threshold number of proposals for the second sequence number have been received, assigning the second sequence number to the write operation request and storing the data associated with the second sequence number.

3. The method of claim 2, further comprising transmitting an acknowledgement of the write operation to the plurality of peer nodes indicating that the data was stored associated with the second sequence number.

4. The method of claim 1, further comprising, responsive to determining that a threshold number of confirmations of the first sequence number have been received, transmitting an acknowledgement of the write operation to the plurality of peer nodes indicating that the data was stored associated with the first sequence number.

5. The method of claim 1, wherein assigning the first sequence number includes determining a largest sequence number associated with the first node, and incrementing the largest sequence number.

6. The method of claim 1, wherein the write command is multicast to all peer nodes in the cluster.

7. The method of claim 1, further comprising defining the threshold number in accordance with a number of nodes in the cluster.

8. The method of claim 7, wherein the threshold number is defined in accordance with a value associated with a supermajority of nodes in the cluster.

9. The method of claim 7, wherein the threshold number is defined in accordance with a number of nodes that are permitted to be separated from the cluster.

10. A first network node, in a leaderless cluster of nodes, comprising circuitry including a processor and a memory, the memory containing instructions executable by the processor whereby the first network node is operative to:

receive a write operation request, including data to be stored, from a client device;

assign a first sequence number to the received write operation request;

transmit a write command, including the data and the first sequence number, to a plurality of peer nodes in the cluster;

receive at least one sequence number validation message from at least one peer node in response to the write command, the sequence number validation message indicating one of a confirmation of the first sequence number or a proposal for a second sequence number; and

responsive to determining that a threshold number of confirmations of the first sequence number or proposals for the second sequence number have been received from peer nodes, transmit a confirmation of successful write operation to the client device.

11. The first network node of claim 10, further operative to, responsive to determining that a threshold number of proposals for the second sequence number have been received, assign the second sequence number to the write operation request and store the data associated with the second sequence number.

12. The first network node of claim 11, further operative to transmit an acknowledgement of the write operation to the plurality of peer nodes indicating that the data was stored associated with the second sequence number.

13. The first network node of claim 10, further operative to, responsive to determining that a threshold number of confirmations of the first sequence number have been received, transmit an acknowledgement of the write operation to the plurality of peer nodes indicating that the data was stored associated with the first sequence number.

14. The first network node of claim 10, wherein assigning the first sequence number includes determining a largest sequence number associated with the first node, and incrementing the largest sequence number.

15. The first network node of claim 10, wherein the write command is multicast to all peer nodes in the cluster.

16. The first network node of claim 10, further operative to define the threshold number in accordance with a number of nodes in the cluster.

17. The first network node of claim 16, wherein the threshold number is defined in accordance with a value associated with a supermajority of nodes in the cluster.

18. The first network node of claim 16, wherein the threshold number is defined in accordance with a number of nodes that are permitted to be separated from the cluster.

19. A first cluster node in a leaderless cluster of nodes, the first cluster node comprising:

a client interface module for receiving a write operation request, including data to be stored, from a client device, and for assigning a first sequence number to the received write operation request;

a cluster interface module for transmitting a write command, including the data and the first sequence number, to a plurality of peer nodes in the cluster, and for receiving at least one sequence number validation message from at least one peer node in response to the write command, the sequence number validation message indicating one of a confirmation of the first sequence number or a proposal for a second sequence number; and

a vote handling module for, responsive to determining that a threshold number of confirmations of the first sequence number or proposals for the second sequence number have been received from peer nodes, initiating transmission of an acknowledgement of the write operation to the client device.