METHOD AND SYSTEM FOR RESOLVING DATA INCONSISTENCY

• US 20130097130A1
• Filed: 10/17/2011
• Published: 04/18/2013
• Est. Priority Date: 10/17/2011
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Mortazavi, Masood, Levy, Jacob Y., Nip, Patrick, Bingol, Tugrul
• Granted Patent: US 8,849,776 B2
• Time in Patent Office: Days
• US Class Current: 707/694
• CPC Class Codes: G06F 16/273 Asynchronous replication or reconciliation

Abstract

Method, system, and programs for resolving data inconsistency in a distributed system having a plurality of replica instances. In response to a read request of at least one data element, a key-specific probability value for the at least one data element of the read request is retrieved. Based on the retrieved key-specific probability value and a system load of the distributed system, a self-healing probability of the at least one data element of the read request is computed. A self-healing transaction that includes the at least one data element of the read request is then generated based on the self-healing probability of the at least one data element. The generated self-healing transaction is further applied to at least some of the plurality of replica instances in the distributed system to resolve data inconsistency.

Claims

1. A method, implemented on at least one machine each having at least one processor, storage, and a communication platform connected to a network for resolving data inconsistency in a distributed system having a plurality of replica instances, comprising:

in response to a read request of at least one data element, retrieving, by a probability assigning module, a key-specific probability value for the at least one data element of the read request;

computing, by the probability assigning module, a self-healing probability of the at least one data element of the read request based on a system load of the distributed system and the retrieved key-specific probability value;

generating, by a transaction generating module, a self-healing transaction that includes the at least one data element of the read request based on the self-healing probability of the at least one data element; and

applying, by a transaction dispatcher via a data replication bus, the generated self-healing transaction to at least some of the plurality of replica instances in the distributed system to resolve data inconsistency.

2. The method of claim 1, wherein

the system load of the distributed system includes a write throughput of the distributed system;

and

the self-healing probability of a data element increases as the write throughput of the distributed system decreases.

3. The method of claim 1, wherein

the key-specific probability value for a data element is provided based on a transaction history of the corresponding data element;

the self-healing probability of a data element decreases when a self-healing transaction that includes the corresponding data element has been applied; and

the self-healing probability of a data element increases when the corresponding data element has been updated.

4. The method of claim 1 further comprising determining, by a policy checking module, whether the self-healing transaction is to be applied based on one or more self-healing policies.

5. The method of claim 4, wherein the step of determining whether the self-healing transaction is to be applied comprises:

determining whether a write transaction has been requested, wherein the write transaction includes the same at least one data element in the self-healing transaction; and

discarding the self-healing transaction if the write transaction has been requested.

6. The method of claim 1, wherein

the at least one data element in the self-healing transaction includes a key, a value, and a time stamp indicating when the value of the at least one data element was most recently updated;

and

the step of applying the generated self-healing transaction comprises;

comparing the time stamp of the at least one data element in the self-healing transaction with a time stamp of a corresponding data element in each replica instance,

if the time stamp of the at least one data element in the self-healing transaction is more recent than a time stamp of a corresponding data element in a replica instance, replacing a value of the corresponding data element in the replica instance with the value of the at least one data element in the self-healing transaction, and

if the time stamp of the at least one data element in the self-healing transaction is not more recent than the time stamp of a corresponding data element in a replica instance, discarding the self-healing transaction in the corresponding replica instance.

7. The method of claim 1, wherein

a self-healing transaction is an writing operation on at least one data element of at least some of the plurality of replica instances in response to a read request by a user or an application;

and

the self-healing transaction includes directive information that controls an application thereof to each of the some replica instances in the distributed system.

8. A system for resolving data inconsistency in a distributed system having a plurality of replica instances, comprising:

a probability assigning module configured to

in response to a read request of at least one data element, retrieve a key-specific probability value for the at least one data element of the read request, and

compute a self-healing probability of the at least one data element of the read request based on a system load of the distributed system and the retrieved key-specific probability value;

a transaction generating module operatively coupled to the probability assigning module, configured to generate a self-healing transaction that includes the at least one data element of the read request based on the self-healing probability of the at least one data element; and

a transaction dispatcher operatively coupled to the transaction generating module, configured to apply, via a data replication bus, the generated self-healing transaction to at least some of the plurality of replica instances in the distributed system to resolve data inconsistency.

9. The system of claim 8, wherein

the system load of the distributed system includes a write throughput of the distributed system;

and

the self-healing probability of a data element increases as the write throughput of the distributed system decreases.

10. The system of claim 8, wherein

the key-specific probability value for a data element is provided based on a transaction history of the corresponding data element;

the self-healing probability of a data element decreases when a self-healing transaction that includes the corresponding data element has been applied; and

the self-healing probability of a data element increases when the corresponding data element has been updated.

11. The system of claim 8 further comprising a policy checking module operatively coupled to the transaction generating module and the transaction dispatcher, configured to determine whether the self-healing transaction is to be applied based on one or more self-healing policies.

12. The system of claim 11, wherein the policy checking module, in determining whether a self-healing transaction is to be generated, is further configured to:

determine whether a write transaction has been requested, wherein the write transaction includes the same at least one data element in the self-healing transaction; and

discard the self-healing transaction if the write transaction has been requested.

13. The system of claim 8, wherein

the at least one data element in the self-healing transaction includes a key, a value, and a time stamp indicating when the value of the at least one data element was most recently updated;

and

the transaction dispatcher, in applying the generated self-healing transaction, is further configured to;

compare the time stamp of the at least one data element in the self-healing transaction with a time stamp of a corresponding data element in each replica instance,

if the time stamp of the at least one data element in the self-healing transaction is more recent than a time stamp of a corresponding data element in a replica instance, replace a value of the corresponding data element in the replica instance with the value of the at least one data element in the self-healing transaction, and

if the time stamp of the at least one data element in the self-healing transaction is not more recent than the time stamp of a corresponding data element in a replica instance, discard the self-healing transaction in the corresponding replica instance.

14. The system of claim 8, wherein

a self-healing transaction is an writing operation on at least one data element of at least some of the plurality of replica instances in response to a read request by a user or an application;

and

the self-healing transaction includes directive information that controls an application thereof to each of the some replica instances in the distributed system.

15. A machine-readable tangible and non-transitory medium having information for resolving data inconsistency in a distributed system having a plurality of replica instances recorded thereon, wherein the information, when read by the machine, causes the machine to perform the following:

in response to a read request of at least one data element, retrieving a key-specific probability value for the at least one data element of the read request;

computing a self-healing probability of the at least one data element of the read request based on a system load of the distributed system and the retrieved key-specific probability value;

generating a self-healing transaction that includes the at least one data element of the read request based on the self-healing probability of the at least one data element; and

applying the generated self-healing transaction to at least some of the plurality of replica instances in the distributed system to resolve data inconsistency.

16. The medium of claim 15, wherein

the system load of the distributed system includes a write throughput of the distributed system;

and

the self-healing probability of a data element increases as the write throughput of the distributed system decreases.

17. The medium of claim 15, wherein

the key-specific probability value for a data element is provided based on a transaction history of the corresponding data element;

the self-healing probability of a data element decreases when a self-healing transaction that includes the corresponding data element has been applied; and

the self-healing probability of a data element increases when the corresponding data element has been updated.

18. The medium of claim 15 further comprising determining whether the self-healing transaction is to be applied based on one or more self-healing policies.

19. The medium of claim 15, wherein the step of determining whether the self-healing transaction is to be applied comprises:

determining whether a write transaction has been requested, wherein the write transaction includes the same at least one data element in the self-healing transaction; and

discarding the self-healing transaction if the write transaction has been requested.

20. The medium of claim 15, wherein

the at least one data element in the self-healing transaction includes a key, a value, and a time stamp indicating when the value of the at least one data element was most recently updated;

and

the step of applying the generated self-healing transaction comprises;

comparing the time stamp of the at least one data element in the self-healing transaction with a time stamp of a corresponding data element in each replica instance,

if the time stamp of the at least one data element in the self-healing transaction is more recent than a time stamp of a corresponding data element in a replica instance, replacing a value of the corresponding data element in the replica instance with the value of the at least one data element in the self-healing transaction, and

if the time stamp of the at least one data element in the self-healing transaction is not more recent than the time stamp of a corresponding data element in a replica instance, discarding the self-healing transaction in the corresponding replica instance.

21. The medium of claim 15, wherein

a self-healing transaction is an writing operation on at least one data element of at least some of the plurality of replica instances in response to a read request by a user or an application;

and

the self-healing transaction includes directive information that controls an application thereof to each of the some replica instances in the distributed system.