US 10,120,924 B2Granted

Quarantine and repair of replicas in a quorum-based data storage system

AssigneeAkamai Technologies, Inc.

InventorsKai C Wong, Philip A Lisiecki, Sung Chiu

Life of this patent

Estimating the term…

Loading patent…

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.

Claims15

Dependent claims

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.

6 more elements

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.

7 more elements

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.

6 more elements

Dependencies are inferred from the claim text.

Facts

Application: 14/543,507Filed 17 Nov 2014 · us provisional application
Priority: 31 Mar 2014
Published: US 2015/0278324 A11 Oct 2015
Granted: 6 Nov 2018
Term ends: Not estimatedThe source records don’t support an estimate.

Classification4 codes

G06F 11/1448
Point-in-time backing up or restoration of persistent data: management of the data involved in backup or backup restore
G06F 11/08
Responding to the occurrence of a fault, e.g. fault tolerance: error detection or correction by redundancy in data representation, e.g. by using…
G06F 16/27
Of structured data, e.g. relational data: replication, distribution or synchronisation of data between databases or within a distributed database…
G06F
Computing and data processing

Family

Application61/972,955Us provisional application · filed 31 Mar 2014
US 2015/0278324 A1Pre-grant publication · published 1 Oct 2015
US 10,120,924 B2This patent

From the US filing history. Foreign family members aren’t listed.

Timeline

Citations

Open elsewhere

Building an agent or pulling many patents? Use the API or MCP server instead of scraping pages. Get an API key