System and method for targeted consistency improvement in a distributed storage system

• US 8,396,840 B1
• Filed: 09/22/2010
• Issued: 03/12/2013
• Est. Priority Date: 09/22/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., Uhlar, Michael A., Henry, Alyssa H.
• Primary Examiner(s): Breene, John E
• Assistant Examiner(s): ASPINWALL, EVAN S
• Application Number:
  US12/888,356
• Time in Patent Office: 902 Days
• Field of Search: 707/687, 707/688, 707/690, 707/691, 707/689
• US Class Current: 707/690
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 11/2097 maintaining the standby controller/processing unit updated initialisation or re-synchronisation thereof G06F11/1658 and subgroups
• CPC Class Codes: G06F 2201/82 Solving problems relating to consistency ensuring consistency in mirrored systems G06F11/2064
• CPC Class Codes: G06F 3/0617 in relation to availability
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

Embodiments may include a consistency measurement component that utilizes memory-efficient sets (e.g., Bloom filters) to generate consistency metrics for read operations performed on different replicated data objects of distributed storage system. Based on the consistency metrics, the consistency measurement component may identify a subset of replicated data objects associated with low levels of consistency. The consistency measurement component may target this subset for consistency improvement by generating instructions to improve the consistency of the subset. In other cases, the consistency measurement component may notify a consistency improvement component about the targeted subset. In response, the consistency improvement component may generate instructions to improve the consistency of the targeted subset.

Claims

1. A computer-implemented method for targeted consistency improvement within a distributed storage system, the method comprising:

utilizing multiple memory-efficient sets to generate consistency metrics for different replicated data objects stored within the distributed storage system, wherein the consistency metrics are based on a measure of inconsistent read operations performed on the replicated data objects;

wherein an inconsistent read operation includes retrieving from a replicated data object, a value that is older than the most recent write operation performed on that replicated data object;

identifying a subset of the replicated data objects having consistency metrics that indicate a lower level of consistency than the consistency metrics of other replicated data objects; and

for each given replicated data object of said subset;

identifying multiple individual data objects that represent the given replicated data object within the distributed data store;

identifying the individual data object storing a most recent value relative to values of the other individual data objects; and

writing the most recent value to each of the other individual data objects.

2. The computer-implemented method of claim 1, wherein the method comprises populating the memory-efficient sets with keys identifying replicated data objects of the 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.

3. The computer-implemented method of claim 2, wherein utilizing multiple memory-efficient sets to generate a given consistency metric for a given replicated data object comprises:

for each given read operation of multiple read operations performed on the given replicated data object;

comparing a last-modified time at which a value retrieved during that read operation was last modified to a time period assigned to a memory-efficient set that includes the key of the given replicated data object;

if the last modified time is older than the most recent time that a write operation was performed, determining that the value retrieved is inconsistent with a most recent value written to the given replicated data object; and

generating the consistency metric for the given replicated data object based on a quantity of instances in which retrieved values are determined to be inconsistent.

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

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

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

7. The computer-implemented method of claim 1, wherein the identified subset of the replicated data object comprises replicated data objects associated with a common customer entity, data center, node, hardware device, or batch of hardware devices.

8. The computer-implemented method of claim 1, wherein the method comprises determining that one or more of the consistency metrics indicate a level of consistency that is less than a desired level of consistency, and generating an alert in response to that determination.

9. The computer-implemented method of claim 1, wherein the method comprises generating at least some of the consistency metrics subsequent to a configuration change within the distributed storage system, and generating a report specifying one or more of the generated consistency metrics.

10. A computer-readable storage medium, storing program instructions computer-executable on a computer system to:

utilize multiple memory-efficient sets to generate consistency metrics for different replicated data objects stored within a distributed storage system, wherein the consistency metrics are based on a measure of inconsistent read operations performed on the replicated data objects;

wherein an inconsistent read operation includes retrieving from a replicated data object, a value that is older than the most recent write operation performed on that replicated data object;

identify a subset of the replicated data objects having consistency metrics that indicate a lower level of consistency than the consistency metrics of other replicated data objects; and

for each given replicated data object of said subset, perform one or more operations to improve the data consistency of that replicated data object.

11. The computer-readable storage medium of claim 10, wherein the program instructions are configured to populate the memory-efficient sets with keys identifying replicated data objects of the 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.

12. The computer-readable storage medium of claim 11, wherein to utilize multiple memory-efficient sets to generate a given consistency metric for a given replicated data object the program instructions are configured to:

for each given read operation of multiple read operations performed on the given replicated data object;

compare a last-modified time at which a value retrieved during that read operation was last modified to a time period assigned to a memory-efficient set that includes the key of the given replicated data object;

if the last modified time is older than the most recent time that a write operation was performed, determine that the value retrieved is inconsistent with a most recent value written to the given replicated data object; and

generate the consistency metric for the given replicated data object based on a quantity of instances in which retrieved values are determined to be inconsistent.

13. The computer-readable storage medium of claim 10, 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.

14. The computer-readable storage medium of claim 10, wherein one or more of the memory-efficient sets are Bloom filters.

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

16. The computer-readable storage medium of claim 10, wherein the identified subset of the replicated data object comprises replicated data objects associated with a common customer entity, data center, node, hardware device, or batch of hardware devices.

17. The computer-readable storage medium of claim 10, wherein the program instructions are configured to determine that one or more of the consistency metrics indicate a level of consistency that is less than a desired level of consistency, and generate an alert in response to that determination.

18. The computer-readable storage medium of claim 10, wherein the program instructions are configured to generate at least some of the consistency metrics subsequent to a configuration change within the distributed storage system, and generate a report specifying one or more of the generated consistency metrics.

19. A system, comprising:

a memory; and

one or more processors coupled to the memory, wherein the memory comprises program instructions executable by the one or more processors to;

utilize multiple memory-efficient sets to generate consistency metrics for different replicated data objects stored within a distributed storage system, wherein the consistency metrics are based on a measure of inconsistent read operations performed on the replicated data objects;

wherein an inconsistent read operation includes retrieving from a replicated data object, a value that is older than the most recent write operation performed on that replicated data object;

identify a subset of the replicated data objects having consistency metrics that indicate a lower level of consistency than the consistency metrics of other replicated data objects; and

provide an indication of the replicated data objects within said subset to a consistency improvement component configured to improve consistency of replicated data objects.

20. The system of claim 19, wherein the program instructions are configured to populate the memory-efficient sets with keys identifying replicated data objects of the 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.

21. The system of claim 20, wherein to utilize multiple memory-efficient sets to generate a given consistency metric for a given replicated data object the program instructions are configured to:

for each given read operation of multiple read operations performed on the given replicated data object;

compare a last-modified time at which a value retrieved during that read operation was last modified to a time period assigned to a memory-efficient set that includes the key of the given replicated data object;

if the last modified time is older than the most recent time that a write operation was performed, determine that the value retrieved is inconsistent with a most recent value written to the given replicated data object; and

generate the consistency metric for the given replicated data object based on a quantity of instances in which retrieved values are determined to be inconsistent.

22. The system of claim 19, 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.

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

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

25. The system of claim 19, wherein the identified subset of the replicated data object comprises replicated data objects associated with a common customer entity, data center, node, hardware device, or batch of hardware devices.

26. The system of claim 19, wherein the program instructions are configured to determine that one or more of the consistency metrics indicate a level of consistency that is less than a desired level of consistency, and generate an alert in response to that determination.

27. The system of claim 19, wherein the program instructions are configured to generate at least some of the consistency metrics subsequent to a configuration change within the distributed storage system, and generate a report specifying one or more of the generated consistency metrics.