Patent ID: 8468134

Claim:
A computer-implemented method for evaluating the consistency of read operations performed in a distributed storage system, wherein the method comprises: for each of multiple write operations performed within the distributed storage system: inserting a key identifying a replicated data object modified by the write operation into a particular memory-efficient set of multiple memory-efficient sets assigned to different time periods, wherein said particular memory-efficient set is assigned to a time period inclusive of a time at which the write operation was performed; for each given read operation of multiple read operations performed in the distributed storage system: determining a last-modified time specifying when a value retrieved from a given replicated data object during the given read operation was last modified; determine a particular time period in which a most recent write operation was performed on the given replicated data object, the particular time period being a time period assigned to a memory-efficient set in which the key identifying the given replicated data object has been inserted; and if the last-modified time is older than the particular time period, determining that the value retrieved is inconsistent with a most recent value written to the particular replicated data object wherein if the last-modified time is not older than the particular time period, the value retrieved is not determined to be inconsistent; and generating a consistency metric based on a quantity of instances in which retrieved values are determined to be inconsistent.