# US 10,120,924 B2 · Quarantine and repair of replicas in a quorum-based data storage system

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 10,120,924 B2
- Document ID: US10120924B2
- Status: Granted
- Kind: B2
- Application number: 14/543,507
- Filed: 2014-11-17
- Published: 2015-10-01
- Granted: 2018-11-06
- Earliest claimed: 2014-03-31
- Assignees: Akamai Technologies, Inc.
- Applicants: Akamai Technologies, Inc.
- Inventors: Kai C Wong; Philip A Lisiecki; Sung Chiu
- Web page: https://patentgrep.com/patent/US10120924B2

## CPC

- G06F 11/1448: {Management of the data involved in backup or backup restore}
- G06F 11/08: Error detection or correction by redundancy in data representation, e.g. by using checking codes
- G06F 16/27: Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A data storage system with quorum-based commits sometimes experiences replica failure, due to unavailability of a replica-hosting node, for example. Described herein are methods and systems 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 so as to create a plurality of replicas, and a quorum of replicas is needed for access to the given shard. Among other things, the methods and systems generally involve determining whether to quarantine or delete unavailable replicas in a given shard, and how to handle purge requests related to the shard when there are quarantined replicas.

## Claims

### Claim 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 data store so as to create a plurality of replicas, where a quorum of replicas is needed for access to the given shard, the method performed by the data distributed data store, the method comprising:
detecting that a particular replica of the plurality of replicas associated with the given shard is unavailable;
in response to said detection, determining whether the available replicas of the plurality of replicas for the given shard represent a quorum, based on a configuration that requires a minimum number of available replicas in the given shard for the available replicas to qualify to be a quorum, and in response to said determination, taking one of the following two actions:
(a) upon a determination that the available replicas of the plurality of replicas for the given shard do not represent a quorum, marking the particular replica as quarantined; and
(b) upon a determination that the available replicas of the plurality of replicas for the given shard do represent a quorum, marking the particular replica to be deleted;
upon the distributed data store marking the particular replica as quarantined, the method further comprising, with the distributed data store:
subsequent to marking the particular replica as quarantined, receiving a purge request to purge data in one or more of the available replicas of the given shard;
in response to the purge request, queuing the purge request instead of purging the data in the one or more of the available replicas of the given shard, based at least in part on the particular replica having a quarantined status;
queuing the purge request at least until the distributed data store determines that there are less than a quorum of unavailable replicas left in quarantine in the shard.

### Claim 2 (depends on 1)

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 of the plurality of replicas for the given shard to the new replica.

### Claim 3 (depends on 2)

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

### Claim 4 (depends on 2)

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

### Claim 5 (depends on 1)

The method of claim 1, further comprising:
marking the particular replica with a quarantine generation identifier.

### Claim 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 so as to create a plurality of replicas;
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 particular replica of the plurality of replicas associated with the shard is unavailable;
in response to said detection, determining whether the available replicas of the plurality of replicas for the shard represent a quorum, based on a configuration that requires a minimum number of available replicas in the given shard for the available replicas to qualify to be a quorum, and in response to said determination, taking one of the following two actions:
(a) upon a determination that the available replicas of the plurality of replicas do not represent a quorum, marking the particular replica as quarantined;
(b) upon a determination that the available replicas of the plurality of replicas do represent a quorum, marking the particular replica to be deleted;
upon the one or more processes marking the particular replica as quarantined, the method further comprising, with the distributed data store;
subsequent to marking the particular replica as quarantined, receiving a purge request to purge data in one or more of the available replicas of the given shard;
in response to the purge request, queuing the purge request instead of purging the data in the one or more of the available replicas of the given shard, based at least in part on the particular replica having a quarantined status;
queuing the purge request at least until the one or more processes determine that there are less than a quorum of unavailable replicas left in quarantine in the shard.

### Claim 7 (depends on 6)

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 of the plurality of replicas for the given shard to the new replica.

### Claim 8 (depends on 7)

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

### Claim 9 (depends on 7)

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

### Claim 10 (depends on 6)

The system of claim 6, the one or more processes further executing the following step:
marking the particular replica with a quarantine generation identifier.

### Claim 11

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 so as to create a plurality of replicas;
means for detecting that a particular replica of the plurality of replicas associated with the shard is unavailable;
means for, in response to said detection, determining whether the available replicas of the plurality of replicas for the shard represent a quorum, based on a configuration that requires a minimum number of available replicas in the given shard for the available replicas to qualify to be a quorum, and in response to said determination, taking one of the following two actions:
(a) means for, upon a determination that the available replicas of the plurality of replicas do not represent a quorum, marking the particular replica as quarantined;
(b) means for, upon a determination that the available replicas of the plurality of replicas do represent a quorum, marking the particular replica to be deleted;
means for, upon marking the particular replica as quarantined, the method further comprising, with the distributed data store:
means for, subsequent to marking the particular replica as quarantined, receiving a purge request to purge data in one or more of the available replicas of the given shard;
mean for, in response to the purge request, queuing the purge request instead of purging the data in the one or more of the available replicas of the given shard, based at least in part on the particular replica having a quarantined status;
mean for queuing the purge request at least until a determination that there are less than a quorum of unavailable replicas left in quarantine in the shard.

### Claim 12 (depends on 11)

The system of claim 11, further comprising:
means for selecting a node to host a new replica for the given shard;
means for copying data from an available replica of the plurality of replicas for the given shard to the new replica.

### Claim 13 (depends on 12)

The system of claim 12, wherein the step of copying occurs before the step of determining whether the available replicas of the plurality of replicas for the given shard represent a quorum, wherein the number of available replicas of the plurality of replicas for the given shard does not include the new replica.

### Claim 14 (depends on 12)

The system of claim 12, wherein the step of copying occurs after the step of determining whether the available replicas of the plurality of replicas for the given shard represent a quorum, wherein the number of available replicas of the plurality of replicas for the given shard does not include the new replica.

### Claim 15 (depends on 11)

The system of claim 11, further comprising:
means for marking the particular replica with a quarantine generation identifier.