Cross-data center hierarchical consensus scheme with geo-aware leader election

Patent metadata

Field	Value
Publication number	US-10749954-B2
Application number	US-201615385475-A
Country	US
Kind code	B2
Filing date	Dec 20, 2016
Priority date	Dec 20, 2016
Publication date	Aug 18, 2020
Grant date	Aug 18, 2020

Abstract

A device comprises a non-transitory memory storage comprising instructions, a network interface, and one or more processors in communication with the memory storage and the network interface. The one or more processors execute the instructions to receive, via the network interface, a write request from a client device; send, via the network interface, the received write request to a set of follower devices; receive, via the network interface, a first acknowledgment from a majority of the follower devices of the set of follower devices that the write request was processed; send, via the network interface, the received write request to a set of peer devices; receive, via the network interface, second acknowledgments from a majority of the set of peer devices that the write request was processed; and send an acknowledgment of the write request to the client device in response to the receipt of the first acknowledgments and the second acknowledgments.

First claim

What is claimed is:

1. A device comprising:
a non-transitory memory storage comprising instructions;
a network interface; and
one or more processors in communication with the memory storage and the network interface, wherein the one or more processors execute the instructions to:
receive, via the network interface, a write request from a client device;
send, via the network interface, the received write request to a set of follower devices;
receive, via the network interface, first acknowledgments from a majority of follower devices of the set of follower devices that the write request was processed; and
based on the receipt of the first acknowledgments, send, via the network interface, the received write request to a set of peer devices different from the set of follower devices.

2. The device of claim 1 , wherein the one or more processors further execute the instructions to:
receive, via the network interface, write commits from a first majority of the set of peer devices;
send, via the network interface, a commit request to the set of peer devices in response to the receipt of the write commits;
receive, via the network interface, second acknowledgments from a second majority of the set of peer devices that the write request was processed;
prior to receiving at least one of the second acknowledgments:
receive, via the network interface, from a first peer device of the set of peer devices, a prior write request;
process the prior write request;
send, via the network interface, an acknowledgment of the prior write request; and
send an acknowledgment of the write request to the client device in response to the receipt of the first acknowledgments and the second acknowledgments.

3. The device of claim 1 , wherein the one or more processors further execute the instructions to:
receive, via the network interface, leader requests from a second majority of follower devices of the set of follower devices; and
become a replacement leader device based on the receipt of the leader requests.

4. The device of claim 1 , wherein the one or more processors further execute the instructions to:
determine that a leader device is not available based on detecting that a heartbeat signal from the leader device has not been received.

5. The device of claim 1 , wherein the one or more processors further execute the instructions to:
determine that a leader device is not available;
send, via the network interface, first usage data to each follower device of the set of follower devices;
receive, via the network interface, second usage data from each follower device of the set of follower devices;
receive, via the network interface, first leader requests from less than a majority of the follower devices of the set of follower devices;
resend, via the network interface, the first usage data to each follower device of the set of follower devices in response to an elapse of a predetermined period of time without detecting a message from a replacement leader device;
receive, via the network interface, second leader requests from a second majority of the follower devices of the set of follower devices; and
become a replacement leader device based on the first usage data, the second usage data, and the receipt of the second leader requests.

6. The device of claim 2 , wherein:
an average geographic distance from the device to each of the follower devices of the set of follower devices is less than an average geographic distance from the device to each of the peer devices of the set of peer devices.

7. A computer-implemented method for maintaining data consistency across multiple data centers, comprising:
receiving, by one or more processors and via a network interface, a write request from a client device;
sending, by the one or more processors and via the network interface, the received write request to a set of follower devices;
receiving, by the one or more processors and via the network interface, first acknowledgments from a majority of follower devices of the set of follower devices that the write request was processed; and
based on the receipt of the first acknowledgments, sending, by the one or more processors and via the network interface, the received write request to a set of peer devices different from the set of follower devices.

8. The method of claim 7 , further comprising:
receiving, by the one or more processors and via the network interface, write commits from a first majority of the set of peer devices;
in response to the receipt of the write commits, sending, by the one or more processors and via the network interface, a commit request to the set of peer devices;
receiving, by the one or more processors and via the network interface, second acknowledgments from a second majority of the set of peer devices that the write request was processed;
prior to receiving at least one of the second acknowledgments:
receiving, via the network interface, from a first peer device of the set of peer devices, a prior write request;
processing the prior write request; and
sending, via the network interface, an acknowledgment of the prior write request; and

in response to the receipt of the first acknowledgments and the second acknowledgments, sending an acknowledgment of the write request to the client device.

9. The method of claim 7 , further comprising:
receiving, via the network interface, leader requests from a second majority of follower devices of the set of follower devices; and
becoming a replacement leader device based on the receipt of the leader requests.

10. The method of claim 7 , further comprising determining that a leader device is not available based on detecting that a heartbeat signal from the leader device has not been received.

11. The method of claim 7 , further comprising:
determining, by the one or more processors, that a leader device is not available;
sending, via the network interface, first usage data to each follower device of the set of follower devices;
receiving, via the network interface, second usage data from each follower device of the set of follower devices; and
receiving, via the network interface, first leader requests from less than a majority of the follower devices of the set of follower devices;
in response to an elapse of a predetermined period of time without detecting a message from a replacement leader device, resending, via the network interface, the first usage data to each follower device of the set of follower devices;
receiving, via the network interface, second leader requests from a second majority of the follower devices of the set of follower devices; and
becoming a replacement leader device based on the first usage data, the second usage data, and the receipt of the second leader requests.

12. The method of claim 8 , wherein:
an average geographic distance from the network interface to each of the follower devices of the set of follower devices is less than an average geographic distance from the network interface to each of the peer devices of the set of peer devices.

13. A non-transitory computer-readable medium storing computer instructions that, when executed by one or more processors, cause the one or more processors to perform steps of:
receiving, via a network interface, a write request from a client device;
sending, via the network interface, the received write request to a set of follower devices;
receiving, via the network interface, first acknowledgments from a majority of follower devices of the set of follower devices that the write request was processed; and
based on the receipt of the first acknowledgments, sending, via the networ

Assignees

• Futurewei Technologies Inc

Inventors

• Chen Shen Chi
• Chen Liya
• Tian Chen
• Lin Zongfang
• Lasater Robert

Classifications

• H04L41/0893 Primary

  Assignment of logical groups to network elements · CPC title

• H04L67/1095 Primary

  Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes · CPC title

• H04L43/10

  Active monitoring, e.g. heartbeat, ping or trace-route · CPC title

• H04L67/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] · CPC title