US 10,372,574 B1 · Skew detector for data storage system

Abstract

A computing resource service provider may store user data in a distributed data storage system. The distributed data storage system may contain one or more storage partitions configured to store based at least in part on prefixes of keys contained in a key-value store, where the size of the keys may vary. The one or more storage partitions may track requests to access data where the requests include a key such that the data may be located by the service provider based at least in part on the key. When a request is received a skew value associated with the key included in the request may be determined. The skew value may be determined based at least in part on the ratio of rate estimators, where the rate estimators represent a weighted average of the movement of the keys in a key space. If the skew value exceeds a threshold the service provider may take mitigating action.

Claims20

Dependent claims

A non-transitory computer-readable storage medium having collectively stored thereon executable instructions that, as a result of being executed by one or more processors of a computer system, cause the computer system to at least:

obtain data based at least in part on a plurality of requests including one or more keys capable of locating data in one or more partitions of the computer system connected to a network;
calculate a redistribution skew value based at least in part on a distance function and the one or more keys;
and
provide the redistribution skew value, thereby causing an update to a configuration of the one or more partitions.

1 more element

A system, comprising:

one or more processors;
and
memory with instructions that, as a result of being executed by the one or more processors, cause the system to:
for a plurality of requests that identify data objects stored in a plurality of storage partitions connected to a network, the plurality of requests including at least one key of a set of keys:
calculate a redistribution skew value based at least in part on a first measure determined based at least in part on a first subset of keys of the set of keys and a second subset of keys of the set of keys and a second measure determined based at least in part on a third subset of keys of the set of keys and a fourth subset of keys of the set of keys;
and
provide the redistribution skew value, thereby causing an update to a configuration of the plurality of storage partitions based at least in part on the skew value.

4 more elements

Dependencies are inferred from the claim text.

Skew detector for data storage system

Life of this patent

Skew detector for data storage system

Life of this patent

Abstract

Claims20