Providing the latest version of a data item from an N-replica set

• US 20060253504A1
• Filed: 05/04/2005
• Published: 11/09/2006
• Est. Priority Date: 05/04/2005
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Srivastava, Alok K., Lee, Ken, Joshi, Sameer
• Granted Patent: US 7,631,016 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/273 Asynchronous replication or reconciliation
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

Less-restrictive techniques are provided for ensuring that replicated-data systems will never provide out-of-date version of data items. A replicated-data system maintains (1) a version number, (3) a membership group identifier, and (6) a membership count, with each replica of a data item. These values are maintained in such a way as to allow the replicated-data system to reliably satisfy some read requests even though half, or less than half, of the replicas of the data item are available.

Claims

1. A method of managing replicas of a data item, the method comprising:

responding to a request to update the data item by

attempting to perform an update operation to replicas of the data item;

determining whether a first predetermined percentage of the members of a most-recently-established membership group were updated in the update operation, wherein the most-recently-established membership group includes those replicas that were updated in a most recent prior update to the data item; and

if the first predetermined percentage of the members of the most-recently-established membership group were updated in the update operation,

then

if all members of the most-recently-established membership group were not updated in the update operation, then establishing the replicas of the data item that were updated in the update operation as a new most-recently-established membership group.

2. The method of claim 1 wherein the first predetermined percentage is fifty percent.

3. The method of claim 1 further comprising:

responding to a request to read the data item by

attempting to perform a read operation on replicas of the data item;

determining whether more than a second predetermined percentage of the members of the most-recently-established membership group were read in the read operation; and

if more than the second predetermined percentage of the members of the most-recently-established membership group (a) were read in the read operation and (b) contained a most recent version associated with the data item, then determining a current version of the data item based on the members of the most-recently-established membership group that were read in the read operation.

4. The method of claim 3 wherein:

if (a) all members of the most-recently-established membership group were read in the read operation, and (b) less than the second predetermined percentage of members of the most-recently-established membership group contain a most recent version associated with the data item, then performing the steps of;

populating the next highest version data to the replicas of the most-recently-established membership group that do not currently have the next highest version data, and

returning the next highest version of the data item as the latest version of the data item.

5. The method of claim 3 wherein the second predetermined percentage is one hundred percent minus the first predetermined percentage.

6. The method of claim 3 further comprising:

storing, in association with each replica of the data item, a membership group identifier and a membership count;

wherein the membership group identifier of a replica indicates the membership group to which the replica belongs; and

wherein the membership group count of a replica indicates how many replicas belong to the membership group to which the replica belongs.

7. The method of claim 6 wherein the step of determining whether more than the second predetermined percentage of the members of the most-recently-established membership group were read in the read operation is performed by:

reading the membership group identifiers and membership counts associated with all replicas that were read; and

determining, based on the membership group identifiers and membership counts, whether more than the second predetermined percentage of the members of the most-recently-established membership group were read.

8. The method of claim 6 wherein the step of determining whether the first predetermined percentage of the members of the most-recently-established membership group were updated in the update operation is performed by:

reading the membership group identifiers and membership counts associated with all replicas that were updated; and

determining, based on the membership group identifiers and membership counts, whether the first predetermined percentage of the members of the most-recently-established membership group were updated in the update operation.

9. The method of claim 1 further comprising attempting to roll back the update operation if the first predetermined percentage of the members of the most-recently-established membership group were not updated in the update operation.

10. The method of claim 3 further comprising causing the request to read the data item to fail if more than the second predetermined percentage of the members of the most-recently-established membership group were not read in the read operation.

13. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 1.

14. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 2.

15. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 3.

16. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 4.

17. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 5.

18. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 6.

19. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 7.

20. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 8.

21. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 9.

22. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 10.

11. A method for handling a previously-offline replica of a data item, the method comprising:

when the previously-offline replica comes online, populating a latest copy of the data item to the replica before the replica is established as a member of a most-recently-established membership group; and

in response to the addition of the previously-offline replica to the most-recently-established membership group, updating a membership count of all available members of the most-recently-established membership group.

12. The method of claim 11 wherein the change in membership of the most-recently-established membership group triggers generation of a new membership group identifier, which is stored in association with all replicas that were updated with the new membership count.

23. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 11.

24. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 12.