System and method for measuring consistency within a distributed storage system

• US 8,468,134 B1
• Filed: 09/21/2010
• Issued: 06/18/2013
• Est. Priority Date: 09/21/2010
• Status: Expired due to Fees

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: McHugh, Jason G., Theriault, Eric Yves, Markle, Seth W.
• Primary Examiner(s): To, Baoquoc N
• Application Number:
  US12/886,801
• Time in Patent Office: 1,001 Days
• Field of Search: 707/638, 707/688, 707/704
• US Class Current: 707/638
• CPC Class Codes: G06F 16/24556 Aggregation; Duplicate elimination

Abstract

Embodiments may include a consistency measurement component that utilizes memory-efficient sets (e.g., Bloom filters) assigned to different time periods for tracking when different write operations are performed on replicated data objects within a distributed data store. The consistency measurement component may evaluate whether read operations directed to the distributed data store are inconsistent. To do so, the consistency measurement component may determine, for a given read operation, the age of the value read from a given replicated data object (e.g., by evaluating a “last-modified” timestamp). The consistency measurement component may identify a memory-efficient set that includes the key of that replicated data object in order to determine when the replicated data object was last written to. If the age of the value read is older than the time at which the replicated data object was last written to, the consistency measurement component may determine that the read operation was inconsistent.

Claims

1. 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.

2. The computer-implemented method of claim 1, wherein each memory-efficient set is configured to provide an indication of which keys have been inserted into that set without storing the values of those keys.

3. The computer-implemented method of claim 1, wherein one or more of the memory-efficient sets are Bloom filters.

4. The computer-implemented method of claim 1, wherein one or more of the memory-efficient sets have a fixed data size within memory of a computer.

5. The computer-implemented method of claim 1, wherein determining a particular time period in which a most recent write operation was performed comprises:

identifying multiple memory-efficient sets in which the key of the given replicated data object has been inserted,

from the identified memory-efficient sets, determining that a particular memory-efficient set has been assigned to a time period that is more recent than the time periods of the one or more other identified memory-efficient sets; and

identifying said particular time period as being a time period assigned to said particular memory-efficient set.

6. The computer-implemented method of claim 1, wherein determining said last-modified time for a given replicated data object comprises receiving metadata of the given replicated data object from the distributed storage system, said metadata indicating the last-modified time.

7. The computer-implemented method of claim 1, wherein the method comprises receiving logs or streamed data from nodes of the distributed storage system, wherein said logs or said streamed data specify records for read operations and write operations performed on a respective node of the distributed storage system.

8. The computer-implemented method of claim 7, wherein at least some of said multiple write operations and said multiple read operations are sampled from said logs or said streamed data.

9. The computer-implemented method of claim 8, wherein said consistency metric is generated based on the sampled write operations and read operations, wherein said consistency metric is expressed as a confidence interval.

10. The computer-implemented method of claim 1, wherein the method comprises, during operation, discarding at least one memory-efficient set assigned to an older time period and generating a new memory-efficient set assigned to a more recent time period.

11. The computer-implemented method of claim 1, wherein the method comprises, during operation, clearing a memory-efficient set of its keys and reassigning that memory-efficient set from one time period to a more recent time period.

12. A non-transitory, computer-readable storage medium, storing program instructions computer-executable on a computer to implement a consistency measurement component configured to:

generate multiple memory-efficient sets populated with keys identifying replicated data objects of a distributed storage system, each key inserted into a memory-efficient set assigned to a time period in which a replicated data object identified by that key was written to;

for a read operation that retrieved a value from a given replicated data object in the distributed storage system, determine a last-modified time specifying when the retrieved value was last modified;

identify a particular memory-efficient set in which a key identifying the given replicated data object has been inserted; and

in response to determining the last-modified time is older than the time period to which the identified memory-efficient set is assigned, generate an indication that specifies the value retrieved during the read operation is inconsistent with a most recent value written to the given replicated data object.

13. The non-transitory, computer-readable storage medium of claim 12, wherein the consistency measurement component is configured to repeat the generation of said indication for multiple other read operations performed in the distributed storage system, and generate a consistency metric based on a quantity of instances in which retrieved values are determined to be inconsistent.

14. The non-transitory, computer-readable storage medium of claim 13, wherein said consistency metric is generated based on write operations and read operations sampled from a larger population of write operations and read operations, wherein said consistency metric is expressed as a confidence interval.

15. The non-transitory, computer-readable storage medium of claim 12, wherein each memory-efficient set is configured to provide an indication of which keys have been inserted into that set without storing the values of those keys.

16. The non-transitory, computer-readable storage medium of claim 12, wherein one or more of the memory-efficient sets are Bloom filters.

17. The non-transitory, computer-readable storage medium of claim 12, wherein one or more of the memory-efficient sets have a fixed data size within memory of the computer.

18. The non-transitory, computer-readable storage medium of claim 12, wherein to identify the particular memory-efficient set, the consistency measurement component is configured to:

identify multiple memory-efficient sets in which the key of the given replicated data object has been inserted, and

from the identified memory-efficient sets, select said particular memory-efficient set in response to determining that said particular memory-efficient set has been assigned to a time period that is more recent than the time periods of the one or more other identified memory-efficient sets.

19. The non-transitory, computer-readable storage medium of claim 12, wherein to determine said last-modified time the consistency measurement component is configured to receive metadata of the given replicated data object from the distributed storage system, said metadata indicating the last-modified time.

20. The non-transitory, computer-readable storage medium of claim 12, wherein the consistency measurement component is configured to, during operation, discard at least one memory-efficient set assigned to an older time period and generate a new memory-efficient set assigned to a more recent time period.

21. The non-transitory, computer-readable storage medium of claim 12, wherein the consistency measurement component is configured to, during operation, clear a memory-efficient set of its keys and reassign that memory-efficient set from one time period to a more recent time period.

22. A system, comprising:

a memory comprising multiple memory-efficient sets assigned to different time periods; and

one or more processors coupled to the memory, wherein the memory comprises program instructions executable by the one or more processors to implement a consistency measurement component configured to;

populate the memory-efficient sets with keys identifying replicated data objects of a distributed storage system, each key inserted into a memory-efficient set assigned to a time period in which a replicated data object identified by that key was written to;

for a read operation that retrieved a value from a given replicated data object in the distributed storage system, determine a last-modified time specifying when the retrieved value was last modified;

identify a particular memory-efficient set in which a key identifying the given replicated data object has been inserted; and

in response to determining the last-modified time is older than the time period to which the identified memory-efficient set is assigned, generate an indication that specifies the value retrieved during the read operation is inconsistent with a most recent value written to the given replicated data object.

23. The system of claim 22, wherein the consistency measurement component is configured to repeat the generation of said indication for multiple other read operations performed in the distributed storage system, and generate a consistency metric based on a quantity of instances in which retrieved values are determined to be inconsistent.

24. The system of claim 23, wherein said consistency metric is generated based on write operations and read operations sampled from a larger population of write operations and read operations, wherein said consistency metric is expressed as a confidence interval.

25. The system of claim 22, wherein each memory-efficient set is configured to provide an indication of which keys have been inserted into that set without storing the values of those keys.

26. The system of claim 22, wherein one or more of the memory-efficient sets are Bloom filters.

27. The system of claim 22, wherein one or more of the memory-efficient sets have a fixed data size within memory of the computer.

28. The system of claim 22, wherein to identify the particular memory-efficient set, the consistency measurement component is configured to:

identify multiple memory-efficient sets in which the key of the given replicated data object has been inserted, and

from the identified memory-efficient sets, select said particular memory-efficient set in response to determining that said particular memory-efficient set has been assigned to a time period that is more recent than the time periods of the one or more other identified memory-efficient sets.

29. The system of claim 22, wherein to determine said last-modified time the consistency measurement component is configured to receive metadata of the given replicated data object from the distributed storage system, said metadata indicating the last-modified time.

30. The system of claim 22, wherein the consistency measurement component is configured to, during operation, discard at least one memory-efficient set assigned to an older time period and generate a new memory-efficient set assigned to a more recent time period.

31. The system of claim 22, wherein the consistency measurement component is configured to, during operation, clear a memory-efficient set of its keys and reassign that memory-efficient set from one time period to a more recent time period.