Providing the latest version of a data item from an N-replica set
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 a version number, a membership group identifier, and 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.
1. A method of managing replicas of a data item, the method comprising the computer-implemented steps of:
responding to a request to update the data item by
initiating an update operation to replicas of the data item;
determining whether at least a first predetermined percentage of 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
in response to determining that (a) at least the first predetermined percentage of the members of the most-recently-established membership group were updated in the update operation, and (b) all members of the most-recently-established membership group were not updated in the update operation, establishing the replicas of the data item that were updated in the update operation as a new membership group that replaces the most-recently-established membership group; and
responding to a request to read the data item by
initiating a read operation on replicas of the data item;
determining a second predetermined percentage based on determining a difference between one hundred percent and the first predetermined percentage of the most-recently-established membership group;
determining whether more than the second predetermined percentage of the members of the most-recently-established membership group were read in the read operation;
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; and
wherein the method is performed by one or more computing devices.
2. The method of claim 1 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.
3. The method of claim 1 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.
4. The method of claim 3 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.
5. The method of claim 3 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.
6. The method of claim 1 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.
7. The method of claim 1 further comprising:
when a previously-offline replica of a data item comes online, populating a latest copy of the data item to the replica;
adding the replica as a member of the 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.
8. The method of claim 7 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.
9. A computer-readable storage medium storing 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 .
10. A computer-readable storage medium storing 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 .
11. A computer-readable storage medium storing 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 .
12. A computer-readable storage medium storing 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 .
13. A computer-readable storage medium storing 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 .
14. A computer-readable storage medium storing 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 .
15. A computer-readable storage medium storing 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 .
16. A computer-readable storage medium storing 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 .
17. The method of claim 1 further comprising initiating roll back of the update operation if the first predetermined percentage of the members of the most-recently-established membership group were not successfully updated in the update operation.
18. A computer-readable storage medium storing 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 17 .