QUARANTINE AND REPAIR OF REPLICAS IN A QUORUM-BASED DATA STORAGE SYSTEM

• US 20150278324A1
• Filed: 11/17/2014
• Published: 10/01/2015
• Est. Priority Date: 03/31/2014
• Status: Active Grant

• Current Assignee: Akamai Technologies, Inc.
• Original Assignee: Akamai Technologies, Inc.
• Inventors: Wong, Kai C, Lisiecki, Philip A, Chiu, Sung
• Granted Patent: US 10,120,924 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/08 Error detection or correction by redundancy in data representation, e.g. by using checking codes
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor

Abstract

A data storage system with quorum-based commits sometimes experiences replica failure, due to unavailability of a replica-hosting node, for example. In embodiments described herein, such failed replicas can be quarantined rather than deleted, and subsequently such quarantines can be recovered. The teachings hereof provide data storage with improved fault-tolerance, resiliency, and data availability.

Claims

1. A method for improving data persistence and availability in a distributed data store where data is stored in a plurality of shards and a given shard is replicated across a plurality of nodes in the distributed system, where a quorum of replicas is needed for access to the given shard, the method operable within the data distributed data store, the method comprising:

detecting that a replica associated with the given shard are unavailable;

determining whether the available replicas for the given shard represent a quorum;

upon a determination that the available replicas do not represent a quorum, marking the unavailable replica as quarantined;

upon a determination that the available replicas do represent a quorum, marking the unavailable replica to be deleted.

2. The method of claim 1, further comprising:

selecting a node to host a new replica for the given shard;

copying data from an available replica for the given shard to the new replica.

3. The method of claim 2, wherein the step of copying occurs before the step of determining whether the available replicas in the given shard represent a quorum, wherein the number of available replicas in the given shard does not include the number of new replicas.

4. The method of claim 2, wherein the step of copying occurs after the step of determining whether the available replicas in the given shard represent a quorum, wherein the number of available replicas in the given shard does not include the number of new replicas.

5. The method of claim 1, further comprising:

marking the quarantined replica with a quarantine generation identifier.

6. A data storage system with improved operation, comprising:

a plurality of distributed nodes, each node comprising a microprocessor and memory storing instructions to be executed on the microprocessor for operating of that node, the plurality of nodes including a plurality of storage nodes each storing at least one replica of a shard;

one or more processes executing on one or more of the plurality of nodes to detect and handle faults in replicas, the one or more processes executing the following steps;

detecting that a replica associated with the shard are unavailable;

determining whether the available replicas for the shard represent a quorum;

upon a determination that the available replicas do not represent a quorum, marking the unavailable replica as quarantined;

upon a determination that the available replicas do represent a quorum, marking the unavailable replica to be deleted.

7. The system of claim 6, the one or more processes further executing the following steps:

selecting a node to host a new replica for the given shard;

copying data from an available replica for the given shard to the new replica.

8. The system of claim 7, wherein the step of copying occurs before the step of determining whether the available replicas in the given shard represent a quorum, wherein the number of available replicas in the given shard does not include the number of new replicas.

9. The system of claim 7, wherein the step of copying occurs after the step of determining whether the available replicas in the given shard represent a quorum, wherein the number of available replicas in the given shard does not include the number of new replicas.

10. The system of claim 7, the one or more processes further executing the following step:

marking the quarantined replicas with a quarantine generation identifier.

11-21. -21. (canceled)

22. A data storage system with improved operation, comprising:

a plurality of distributed nodes, each node comprising means for operating that node, the plurality of nodes including a plurality of storage nodes each storing at least one replica of a shard;

means for detecting that a replica associated with the shard are unavailable;

means for determining whether the available replicas for the shard represent a quorum;

means for, upon a determination that the available replicas do not represent a quorum, marking the unavailable replica as quarantined;

means for, upon a determination that the available replicas do represent a quorum, marking the unavailable replica to be deleted.

23. The system of claim 22, further comprising:

means for selecting a node to host a new replica for the given shard;

means for copying data from an available replica for the given shard to the new replica.

24. The system of claim 23, wherein the step of copying occurs before the step of determining whether the available replicas in the given shard represent a quorum, wherein the number of available replicas in the given shard does not include the number of new replicas.

25. The system of claim 23, wherein the step of copying occurs after the step of determining whether the available replicas in the given shard represent a quorum, wherein the number of available replicas in the given shard does not include the number of new replicas.

26. The system of claim 23, further comprising:

means for marking the quarantined replicas with a quarantine generation identifier.

27-31. -31. (canceled)