Method and system for byzantine fault tolerant data replication

Patent metadata

Field	Value
Publication number	US-9753792-B2
Application number	US-201414778084-A
Country	US
Kind code	B2
Filing date	Mar 18, 2014
Priority date	Mar 20, 2013
Publication date	Sep 5, 2017
Grant date	Sep 5, 2017

Abstract

A method for byzantine fault tolerant data replication with a plurality of 2f+1 data servers and one or more clients includes storing data in at least f+1 different data servers out of the 2f+1 data servers, and storing metadata of the stored data under a metadata-identifier in a metadata-service (MDS). The stored metadata includes a unique identifier of the stored data, a fingerprint of the stored data, and a list of the at least f+1 different data servers which have stored the data.

First claim

The invention claimed is:

1. A method for byzantine fault tolerant data replication with a plurality of 2f+1 data servers and one or more clients, the method comprising:
storing data in at least f+1 different data servers of the 2f+1 data servers;
storing metadata of the stored data under a metadata-identifier in a metadata-service (MDS), wherein the stored metadata includes a unique identifier of the stored data, a fingerprint of the stored data, and a list of the at least f+1 different data servers which have stored the data; and
reading the stored data by, a first one of the one or more clients by:
(a) querying a first data server of the list of the at least f+1 different data servers with the unique identifier of the data based on the stored metadata provided by the MDSupon being queried with the metadata-identifier,
(b) providing the stored data according to the unique identifier; and
(c) providing the stored data to the first client based on a match of the fingerprints of the stored data and of the stored metadata.

2. The method according to claim 1 , wherein the metadata is only stored upon successful storing of the data on the at least f+1 different data servers.

3. The method according to claim 1 , further comprising:
repeating (a)-(c) based on a mismatch of the fingerprints with one or more other data servers of the list of the at least f+1 different data servers until at least one match is achieved.

4. The method according to claim 3 , wherein the repeating steps (a)-(c) is performed sequentially with only one of the other data servers of the list of the at least f+1, different data servers per repetition.

5. The method according to claim 1 , wherein version information of the stored data is stored in the MDS and provided to the one or more clients upon querying.

6. The method according to claim 1 , wherein the MDS is provided as a cloud service.

7. The method according to claim 1 , wherein at least two of the plurality of 2f+1 data servers provide different file storage services for storing the data.

8. The method according to claim 1 , further comprising storing a plurality of data units simultaneously by storing each data unit on each of the f+1 different data servers.

9. The method according to claim 1 , wherein the MDS uses a quorum-based protocol for fault-tolerance.

10. The method according to claim 1 , wherein the metadata service MDS linearizes operations on the metadata.

11. The method according to claim 1 , wherein the MDS is a fault-tolerant MDS.

12. The method according to claim 1 , wherein at least two of the at least f+1 different data servers provide different file storage services for storing the data.

13. A system for byzantine fault tolerant data replication with a plurality of 2f+1 data servers and one or more clients, the system comprising:
at least f+1 different data servers of the 2f+1 data servers each being operable to store data;
a fault-tolerant metadata-service (MDS) being operable to store metadata of the stored data under a metadata-identifier, wherein the metadata includes a unique identifier of the stored data, a fingerprint of the stored data and a list of data servers which have stored the data, and
a first on of the one or more clients being operable to read the stored data by:
(a) querying a first data server of the list of the at least f+1 different data servers with the unique identifier of the data based on the stored metadata provided by the MDS upon being queried with the metadata-identifier,
(b) providing the stored data according to the unique identifier; and
(c) providing the stored data to the first client based on a match of the fingerprints of the stored data and of the stored metadata.

Assignees

• Nec Europe Ltd

Inventors

• Dobre Dan
• Karame Ghassan
• Vukolic Marko

Classifications

• G06F3/067

  Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS] · CPC title

• G06F2201/83

  the solution involving signatures · CPC title

• G06F11/1443 Primary

  Transmit or communication errors · CPC title

• G06F11/2094

  Redundant storage or storage space (G06F11/2056 takes precedence) · CPC title

• G06F3/0619

  in relation to data integrity, e.g. data losses, bit errors · CPC title