System and method for optimizing efficiency of replicated network services

• US 20070276873A1
• Filed: 02/13/2002
• Published: 11/29/2007
• Est. Priority Date: 02/13/2001
• Status: Abandoned Application

• Current Assignee: Duke University
• Original Assignee: Duke University
• Inventors: Vahdat, Amin, Yu, Haifeng
• Application Number:
  US10/547,927
• Publication Number:
  US 20070276873A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 16/275 Synchronous replication

Abstract

A system and method for controlling a selectable level of consistency in a replicated data system (FIG. 3) uses consistency metrics to determine when to perform updates between data replicas. Each replica tracks one or more consistency metrics, and compares the consistency metrics to predetermined boundary values. If a metric value exceeds a boundary value, updates are performed. The metrics can include numerical error, order error and staleness.

Claims

1. In a data system having a plurality of data store replicas, a method of updating at least one of the plurality of data store replicas, comprising:

receiving new data into a first replica;

reading status data associated with at least one consistency metric relative to a second replica;

comparing the status data to a predetermined consistency metric bound; and

determining whether to update replica data based on a result of the comparison step.

2. The method of claim 1, further comprising updating replica data if the result of the determining step indicates that an update is required.

3. The method of claim 2, wherein the updating step comprises conducting anti-entropy sessions between the replicas.

4. The method of claim 2, wherein the updating step comprises the first replica sending writes to the second replica.

5. The method of claim 2, wherein the updating step comprises the first replica pulling writes from the second replica.

6. The method of claim 1, wherein the receiving step comprises:

receiving a write from one of a client and an application;

assigning an acceptance stamp to the write; and

storing the write in a data store of the first replica.

7. The method of claim 6, further comprising assigning a tentative status to the write.

8. The method of claim 6, wherein the storing step comprises making an entry in a write log of the first replica.

9. The method of claim 6, wherein the acceptance stamp includes a time and a replica identifier.

10. The method of claim 9, wherein the time is a logical time.

11. The method of claim 1, wherein the reading step is performed by the first replica.

12. The method of claim 1, wherein the reading step comprises reading information from the second replica.

13. The method of claim 1, wherein the at least one consistency metric is at least one of numerical error, order error and staleness.

14. The method of claim 1, wherein the reading step comprises reading a numerical error of the second replica relative to the first replica, the numerical error indicating the number of writes present in the first replica that have not been seen by the second replica.

15. The method of claim 14, wherein the numerical error of the second replica relative to the first replica also comprises a total weight of the writes present in the first replica that have not been seen by the second replica.

16. The method of claim 1, wherein the reading step comprises reading an order error of the first replica, the order error comprising the number of writes in the first replica that have not been seen by other replicas.

17. The method of claim 16, wherein the order error also includes a total weight of the writes in the first replica that have not been seen by other replicas.

18. The method of claim 1, wherein the reading step comprises reading a staleness metric, wherein the staleness metric indicates a delay period between the present time and the time that the second replica received the most recent write present in a write log of the first replica.

19. In a data system having a plurality of data store replicas, a method of updating at least one of the plurality of data store replicas, comprising using at least one metric of data consistency to provide a selectable level of data consistency on a per data store replica basis.

20. A system for providing network-based services comprising:

an interface to a communications link;

a data source coupled to the communications link; and

a first and second replica coupled to the communication link, wherein the first and second replicas each include a read/write controller and a data store, and wherein the read/write controller is configured to receive new data from the data source into the data store, read status data associated with at least one consistency metric relative to another replica, compare the status data to a predetermined consistency metric bound, and determine whether to update another replica based on a result of the comparison step.

21. A computer readable medium having stored thereon a sequence of instructions which, when executed by a processor, cause the processor to perform a sequence of steps, comprising:

receiving new data into a first replica;

reading status data associated with at least one consistency metric relative to a second replica;

comparing the status data to a predetermined consistency metric bound; and

determining whether to update replica data based on a result of the comparison step.