Method for voting with secret shares in a distributed system

• US 8,234,518 B2
• Filed: 07/21/2009
• Issued: 07/31/2012
• Est. Priority Date: 07/21/2009
• Status: Active Grant

• Current Assignee: Vmware LLC (Broadcom, Inc.)
• Original Assignee: VMware, Inc. (Broadcom, Inc.)
• Inventors: Hansen, Jacob Gorm
• Primary Examiner(s): Baderman, Scott
• Assistant Examiner(s): KO, CHAE M
• Application Number:
  US12/507,013
• Publication Number:
  US 20110022883A1
• Time in Patent Office: 1,106 Days
• Field of Search: 714/4.11, 380/281, 380/286, 707/698
• US Class Current: 714/4.11
• CPC Class Codes: G06F 11/1484 involving virtual machines
• CPC Class Codes: G06F 11/2028 eliminating a faulty processor or activating a spare
• CPC Class Codes: G06F 11/2035 without idle spare hardware
• CPC Class Codes: G06F 11/2097 maintaining the standby controller/processing unit updated initialisation or re-synchronisation thereof G06F11/1658 and subgroups
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes

Abstract

A replicated decentralized storage system comprises a plurality of servers that locally store disk images for locally running virtual machines as well as disk images, for failover purposes, for remotely running virtual machines. To ensure that disk images stored for failover purposes are properly replicated upon an update of the disk image on the server running the virtual machine, a hash of a unique value known only to the server running the virtual machine is used to verify the origin of update operations that have been transmitted by the server to the other servers storing replications of the disk image for failover purposes. If verified, the update operations are added to such failover disk images. To enable the replicated decentralized system to recover from a failure of the primary server, the master secret is subdivided into parts and distributed to other servers in the cluster. Upon a failure of the primary server, a secondary server receives a threshold number of the parts and is able to recreate the master secret and failover virtual machines that were running in the failed primary server.

Claims

1. A method for recovering from a failure of a primary server storing a file that is replicated in each of a plurality of secondary servers in a server cluster, the method comprising:

transmitting a request from a particular server in the server cluster to one or more servers in the server cluster for a portion of a master secret value, wherein, at the time of the failure, the complete master secret value is known to the primary server but not to any one of the other servers in the server cluster;

receiving a threshold number of different portions of the master secret value at the particular server;

reconstructing the master secret value based on the received threshold number of different portions at the particular server;

generating an authentication value derived from the master secret value at the particular server, the authentication value being used by at least some of the secondary servers to authenticate an operation as originating from the primary server;

distributing the authentication value from the particular server to each of the plurality of secondary servers; and

acting as a new primary server by the particular server after the master secret value is reconstructed at the particular server.

2. The method of claim 1, wherein the file is a log file comprising a temporally ordered list of update operations.

3. The method of claim 2, wherein each of the update operations comprises a public unique id comprising a hash of a private unique id generated from the master secret value, a previous private unique id from a previous update operation in the log file, and data.

4. The method of claim 2, wherein the authentication value derived from the master secret value comprises a hash of a bitwise intersection of the master secret value, a parent id from a last update operation in a local replication of the log file, and data from the last update operation in the local replication of the log file.

5. The method of claim 4, wherein the parent id comprises a private unique id of a stored update operation preceding the last update operation in the local replication of the log file.

6. The method of claim 2, wherein the log file corresponds to a disk image of a virtual machine running on the primary server prior to the failure of the primary server.

7. The method of claim 6, further comprising instantiating a new virtual machine and associating the new virtual machine with a local replication of the log file.

8. The method of claim 2, further comprising generating a new master secret value.

9. The method of claim 8, further comprising:

receiving data corresponding to an update operation;

generating a public unique id comprising a hash of a private unique id generated from the new master secret value;

obtaining a previous private unique id corresponding to a last update operation stored in a local replication of the log file;

constructing a data structure for the update operation comprising the public unique id, the previous private unique id and the data; and

transmitting the data structure to the plurality of secondary servers.

10. A computer-readable storage medium including instructions that, when executed by a processing unit of a secondary server storing a replication of a file stored on a primary server, causes the processing unit to recover from a failure of the primary server by performing the steps of:

transmitting a request from a particular server in the server cluster to one or more servers in a server cluster for a portion of a master secret value, wherein, at the time of the failure, the complete master secret value is known to the primary server but not to any one of the other servers in the server cluster;

receiving a threshold number of different portions of the master secret value at the particular server;

reconstructing the master secret value based on the received threshold number of different portions at the particular server;

generating an authentication value derived from the master secret value at the particular server, the authentication value being used by at least some of the secondary servers to authenticate an operation as originating from the primary server;

distributing the authentication value from the particular server to each of the plurality of secondary servers; and

acting as a new primary server by the particular server after the master secret value is reconstructed at the particular server.

11. The computer readable storage medium of claim 10, wherein the file is a log file comprising a temporally ordered list of update operations.

12. The computer readable storage medium of claim 11, wherein each of the update operations comprises an public unique id comprising a hash of a private unique id generated from the master secret value, a previous private unique id from a previous update operation in the log file, and data.

13. The computer readable storage medium of claim 11, wherein the authentication value derived from the master secret value comprises a hash of a bitwise intersection of the master secret value, a parent id from a last update operation in the replication of the log file, and data from the last update operation in the replication of the log file.

14. The computer readable storage medium of claim 13, wherein the parent id comprises a private unique id of a stored update operation preceding the last update operation in the replication of the log file.

15. The computer readable storage medium of claim 11, wherein the log file corresponds to a disk image of a virtual machine running on the primary server prior to the failure of the primary server.

16. The computer readable storage medium of claim 15, wherein the processing unit further performs instantiating a new virtual machine and associating the new virtual machine with a local replication of the log file.

17. The computer readable storage medium of claim 11, further comprising generating a new master secret value.

18. The computer readable storage medium of claim 17, wherein the processing unit further performs:

receiving data corresponding to an update operation;

generating a public unique id comprising a hash of a private unique generated from the new master secret value;

obtaining a previous private unique id corresponding to a last update operation stored in a local replication of the log file;

constructing a data structure for the update operation comprising the id value, the previous private unique id and the data; and

transmitting the data structure to the plurality of secondary servers.

19. A method for enabling a plurality of secondary servers in a server cluster to recover from a failure of a primary server, wherein each of the plurality of secondary servers stores a replication of a log file stored on the primary server, the method comprising:

generating a master secret value to create unique identifiers for update operations to the log file and each replication of the log file stored by each of the plurality of secondary servers, wherein each update operation comprises a public unique id comprising a hash of a private unique id generated from the master secret value;

dividing the master secret value into a plurality of parts, wherein a threshold number of any of the plurality of parts can recreate the master secret value;

transmitting each of the plurality of parts for a different server in the server cluster.

20. The method of claim 19, wherein the log file corresponds to a disk image of a virtual machine running on the primary server.