Back to results
US RE49,134 E1Granted
Erasure coding and redundant replication
AssigneeAmazon Technologies, Inc.
InventorsGang He, James Christopher Sorenson, III
Life of this patent
Estimating the term…
Abstract
Disclosed are various embodiments for employing an erasure coding storage scheme and a redundant replication storage scheme in a data storage system. Data objects that are greater than a size threshold and accessed less frequently than an access threshold are stored in an erasure coding scheme, while data objects that are sized less than a size threshold or accessed more often than an access threshold are stored in a redundant replication storage scheme.
Claims104
A non-transitory computer-readable medium embodying a program executable in a at least one computing device, wherein the programcomprising, when executed, causes the at least one computing device to at least:
- code that generates generate an object size distribution of a plurality of data objects stored in a data storage system, the data storage system comprising at least one data store;
- periodically determine a size threshold to maintain a balance between data objects stored in a first data replication scheme and a second data replication scheme in the data storage system based at least in part on a number of data objects distributed above or below the size threshold in the object size distribution;
- code that generates generate an access pattern distribution of the plurality of data objects;
- periodically determine an access frequency threshold to maintain the balance between the data objects stored in the first data replication scheme and the second data replication scheme in the data storage system based at least in part on a number of data objects distributed above or below the access frequency threshold in the access pattern distribution;
- code that identifies from the object size distribution identify a first at least one object stored in the data storage system that is greater than a the size threshold, the first at least one object stored in a the first data replication scheme, the first data replication scheme comprising a redundant replication scheme wherein a copy of the first at least one object is stored in a plurality of data stores in the data storage system;
- code that identifies from the access pattern distribution identify whether the first at least one object is accessed less often than an the access frequency thresholdfrequency;
- code that stores store the first at least one object in a the second data replication scheme in the data storage system when the first at least one object exceeds the size threshold and the first at least one object is accessed less often than the access frequency threshold frequency over a period of time, the second data replication scheme comprising an erasure coding scheme, wherein the at first least one data object is divided into a plurality of shards, each of the plurality of shards having a size less than an object size of the first at least one object and stored in a respective plurality of data stores in the data storage system;
- code that identifies from the object size distribution identify a second at least one object stored in the data storage system that is less than the size threshold, the second at least one object stored in the second data replication scheme;
- code that identifies from the access pattern distribution identify whether the second at least one object is accessed more often than the access frequency thresholdfrequency;
- and
- code that stores store the second at least one object in the first data replication scheme in the data storage system when the first second at least one object is either less than the size threshold or the second at least one object is accessed more often than the access frequency threshold frequency over a period of time.
8 more elements
A system, comprising:
- at least one computing device;
- and
- at least one storage device that is accessible to the at least one computing device, the at least one storage device storing a data storage application executable in the at least one computing device, wherein the data storage applicationcomprising, when executed, causes the at least one computing device to at least:
- logic that generates generate an object size distribution of a plurality of data objects stored in a data storage system, the data storage system comprising at least one data store;
- periodically determine a size threshold to maintain a balance between data objects stored in a first data replication scheme and a second data replication scheme in the data storage system based at least in part on a number of data objects distributed above or below the size threshold in the object size distribution;
- logic that generates generate an access pattern distribution of the plurality of data objects;
- periodically determine an access frequency threshold to maintain the balance between the data objects stored in the first data replication scheme and the second data replication scheme in the data storage system based at least in part on a number of data objects distributed above or below the access frequency threshold in the access pattern distribution;
- logic that identifies from the object size distribution identify at least one data object stored in the data storage system that is greater than a the size threshold, the at least one data object stored in a the first data replication scheme, the first data replication scheme comprising a redundant replication scheme wherein a copy of the at least one data object is stored in a plurality of data stores in the data storage system;
- logic that identifies from the access pattern distribution identify whether the at least one data object is accessed less often than an the access frequency thresholdfrequency;
- and
- logic that stores store the at least one data object in a the second replication scheme in the data storage system when the at least one data object exceeds the size threshold and the at least one data object is accessed less often than the access frequency threshold frequency over a period of time, the second replication scheme comprising an erasure coding scheme, wherein the at least one data object is divided into a plurality of shards, each of the plurality of shards having a size less than an object size of the at least one data object and stored in a respective plurality of data stores in the data storage system.
8 more elements
A method, comprisingthe steps of:
- receiving, in at least one computing device, a request to retrieve a data object from a data storage system comprising at least one data store;
- logging, in the at least one computing device, the request in an access log accessible to the at least one computing device;
- periodically determining, in the at least one computing device, a size threshold to maintain a balance between data objects stored in a first replication scheme and a second replication scheme in the data storage system based at least in part on a number of data objects distributed above or below the size threshold in an object size distribution for the data storage system;
- determining, in the at least one computing device, whether that a size of the data object exceeds a the size threshold;
- determining, in the at least one computing device, whether that the data object is stored in a the first replication scheme in the data storage system, the first replication scheme comprising a redundant replication scheme wherein a copy of the data object is stored in a plurality of data stores in the data storage system;
- and
- encoding, in the at least one computing device, the data object in a the second replication scheme when in response to determining that the size exceeds the size threshold, the second replication scheme comprising an erasure coding scheme, wherein the data object is divided into a plurality of shards, each of the plurality of shards having a size less than an object size of the data object and stored in a respective plurality of data stores in the data storage system;
- and
- storing, in the data storage system, the data object in the second replication scheme.
6 more elements
A system, comprising:
- at least one computing device;
- and
- at least one storage device that is accessible to the at least one computing device, the at least one storage device storing a data storage application executable in the at least one computing device, the data storage application configured to cause the at least one computing device to at least:
- receive a request to store a data object in a data storage system, the data storage system comprising a plurality of data stores;
- generate an object size distribution for the data storage system;
- periodically determine a size threshold to maintain a balance between data objects stored in a redundant replication scheme and an erasure coding scheme in the data storage system based at least in part on a number of data objects distributed above or below the size threshold in the object size distribution;
- determine whether an object size of the data object meets the size threshold;
- store the data object in the data storage system using the redundant replication scheme when the object size fails to meet the size threshold, wherein the redundant replication scheme comprises a first scheme in which a copy of the data object is stored in a first at least two of the plurality of data stores;
- and
- store the data object using the erasure coding scheme in the data storage system when the object size meets the size threshold, the erasure coding scheme comprising a second scheme in which the data object is divided into a plurality of shards, individual ones of the plurality of shards having a size less than the object size and stored in a second at least two of the plurality of data stores.
7 more elements
A method, comprising:
- obtaining, by at least one computing device, a request to store a data object in a data storage system comprising a plurality of data stores;
- generating, by the at least one computing device, an object size distribution for the data storage system;
- periodically determining, by the at least one computing device, a size threshold to maintain a balance between data objects stored in a redundant replication scheme and an erasure coding scheme in the data storage system based at least in part on a number of data objects distributed above or below the size threshold in the object size distribution;
- determining, by the at least one computing device, that an object size of the data object fails to meet the size threshold;
- storing, by the at least one computing device, the data object in the data storage system using the redundant replication scheme instead of the erasure coding scheme responsive to determining that the object size fails to meet the size threshold, wherein the redundant replication scheme comprises a scheme in which a copy of the data object is stored in a first at least two of the plurality of data stores;
- and
- storing, by the at least one computing device, another data object in the data storage system using the erasure coding scheme, wherein the other data object is divided into a plurality of shards, each of the plurality of shards having a size less than an object size of the other data object and stored in a respective plurality of data stores in the data storage system.
4 more elements
A system, comprising:
- at least one computing device;
- and
- at least one storage device that is accessible to the at least one computing device, the at least one storage device storing a data storage application executable in the at least one computing device, the data storage application configured to cause the at least one computing device to at least:
- generate an access pattern distribution of a plurality of data objects stored in a data storage system, the data storage system comprising at least one data store;
- periodically determine an access frequency threshold to maintain a balance between data objects stored in a redundant replication scheme and an erasure coding scheme in the data storage system based at least in part on a number of data objects distributed above or below the access frequency threshold in the access pattern distribution;
- identify a data object stored in the data storage system having an access frequency that fails to meet the access frequency threshold, the data object stored in the data storage system using the redundant replication scheme wherein a copy of the data object is stored in a plurality of data stores in the data storage system;
- and
- store the data object in the data storage system in the erasure coding scheme, wherein the data object is divided into a plurality of shards, each of the plurality of shards having a size of less than an object size of the data object, each of the plurality of shards being stored in a respective plurality of data stores in the data storage system.
5 more elements
A method comprising:
- obtaining, in at least one computing device, a request to retrieve a data object from a data storage system comprising at least one data store;
- logging, in the at least one computing device, the request in an access log accessible to the at least one computing device;
- determining, in the at least one computing device, that an access frequency of the data object fails to meet an access frequency threshold;
- determining, in the at least one computing device, that the data object is stored in a first replication scheme in the data storage system, the first replication scheme comprising a redundant replication scheme wherein a copy of the data object is stored in a plurality of data stores in the data storage system;
- generating, by the at least one computing device, an object size distribution for the data storage system;
- periodically determining, by the at least one computing device, a size threshold to maintain a balance between data objects stored in the first replication scheme and a second replication scheme in the data storage system based at least in part on a number of data objects distributed above or below the size threshold in the object size distribution;
- and
- encoding, in the at least one computing device, the data object in the second replication scheme responsive to determining that the access frequency fails to meet the access frequency threshold and that a size of the data object meets the size threshold, the second replication scheme comprising an erasure coding scheme, wherein the data object is divided into a plurality of shards, each of the plurality of shards having a size less than an object size of the data object and stored in a respective plurality of data stores in the data storage system.
5 more elements
A system, comprising:
- at least one computing device;
- and
- at least one storage device that is accessible to the at least one computing device, the at least one storage device storing a data storage application executable in the at least one computing device, the data storage application configured to cause the at least one computing device to at least:
- generate an object size distribution of a plurality of data objects stored in a data storage system, the data storage system comprising at least one data store;
- generate an access pattern distribution of the plurality of data objects;
- periodically determine a size threshold to maintain a balance between data objects stored in a first replication scheme and a second replication scheme in the data storage system based at least in part on a number of data objects distributed above or below the size threshold in the object size distribution;
- identify at least one data object stored in the data storage system that fails to meet the size threshold, the at least one data object stored in the first replication scheme, the first replication scheme comprising an erasure coding scheme in which the at least one data object is divided into a plurality of shards, each of the plurality of shards having a size less than an object size of the at least one data object and stored in a respective plurality of data stores in the data storage system;
- identify that the at least one data object is accessed more often than an access frequency threshold;
- and
- store the at least one data object in the second replication scheme in the data storage system responsive to determining that the at least one data object fails to meet the size threshold and the at least one data object is accessed more often than the access frequency threshold over a period of time, the second replication scheme comprising a redundant replication scheme in which a copy of the at least one data object is stored in another respective plurality of data stores in the data storage system.
7 more elements
A method comprising:
- receiving, in at least one computing device, a request to retrieve a data object from a data storage system comprising at least one data store;
- logging, in the at least one computing device, the request in an access log accessible to the at least one computing device;
- generating, in the at least one computing device, an object size distribution for the data storage system;
- periodically determining, in the at least one computing device, a size threshold to maintain a balance between data objects stored in a first replication scheme and a second replication scheme in the data storage system based at least in part on a number of data objects distributed above or below the size threshold in the object size distribution;
- determining, in the at least one computing device, that the object size of the data object fails to meet the size threshold;
- determining, in the at least one computing device, that the data object is stored in the first replication scheme in the data storage system, the first replication scheme comprising an erasure coding scheme, wherein the data object is divided into a plurality of shards, each of the plurality of shards having a size less than the object size of the data object and stored in a respective plurality of data stores in the data storage system;
- and
- encoding, in the at least one computing device, the data object in the second replication scheme responsive to determining that the size fails to meet the size threshold and the data object is stored according to the first replication scheme, the second replication scheme comprising a redundant replication scheme wherein a copy of the data object is stored in another respective plurality of data stores in the data storage system.
5 more elements
A non-transitory computer-readable medium embodying a program executable by at least one computing device, the program, when executed, configured to cause at least one computing device to at least:
- receive a request to store a data object in a data storage system, the data storage system comprising a plurality of data stores;
- determine whether a size of the data object meets a size threshold that is periodically determined to maintain a balance between data objects stored in a redundant replication scheme and an erasure coding scheme in the data storage system and depends upon a number of data objects distributed above or below the size threshold in an object size distribution of a plurality of data objects stored in the data storage system;
- store the data object in the data storage system using the redundant replication scheme in response to the size of the data object not meeting the size threshold, wherein the redundant replication scheme comprises a first scheme in which a copy of the data object is stored in a first at least two of the plurality of data stores;
- and
- store the data object using the erasure coding scheme in the data storage system in response to the size of the data object meeting the size threshold, the erasure coding scheme comprising a second scheme in which the data object is divided into a plurality of shards, individual ones of the plurality of shards having a size less than an object size and stored in a second at least two of the plurality of data stores.
2 more elements
A system, comprising:
- at least one computing device;
- and
- at least one storage device that is accessible to the at least one computing device, the at least one storage device storing a data storage application executable in the at least one computing device, the data storage application configured to cause the at least one computing device to at least:
- receive a request to store a data object in a data storage system, the data storage system comprising a plurality of data stores;
- determine whether a size of the data object meets a size threshold that is periodically determined to maintain a balance between data objects stored in a redundant replication scheme and an erasure coding scheme in the data storage system and depends upon a number of data objects distributed above or below the size threshold in an object size distribution of a plurality of data objects stored in the data storage system;
- store the data object in the data storage system using the redundant replication scheme in response to the size of the data object not meeting the size threshold, wherein the redundant replication scheme comprises a first scheme in which a copy of the data object is stored in a first at least two of the plurality of data stores;
- and
- store the data object using the erasure coding scheme in the data storage system in response to the size of the data object meeting the size threshold, the erasure coding scheme comprising a second scheme in which the data object is divided into a plurality of shards, individual ones of the plurality of shards having a size less than an object size and stored in a second at least two of the plurality of data stores.
5 more elements
A method, comprising:
- obtaining, by at least one computing device, a request to store a data object in a data storage system comprising a plurality of data stores;
- determining, by the at least one computing device, that a size of the data object meets a size threshold that is periodically determined to maintain a balance between data objects stored in a redundant replication scheme and an erasure coding scheme in the data storage system and depends upon a number of data objects distributed above or below the size threshold in an object size distribution of a plurality of data objects stored in the data storage system;
- storing, by the at least one computing device, the data object using the erasure coding scheme in the data storage system instead of the redundant replication scheme in response to the size of the data object meeting the size threshold, the erasure coding scheme comprising a scheme in which the data object is divided into a plurality of shards, individual ones of the plurality of shards having a size less than an object size and stored in at least two of the plurality of data stores;
- and
- storing, by the at least one computing device, another data object in the data storage system using the redundant replication scheme, wherein a copy of the other data object is stored in another at least two of the plurality of data stores in the data storage system.
2 more elements
A system, comprising:
- at least one computing device;
- and
- at least one storage device that is accessible to the at least one computing device, the at least one storage device storing a data storage application executable in the at least one computing device, the data storage application configured to cause the at least one computing device to at least:
- perform an analysis of a data storage system to generate an object size distribution for the data storage system, the data storage system comprising at least one data store;
- periodically determine a size threshold to maintain a balance between data objects stored in a first data replication scheme and a second data replication scheme in the data storage system based at least in part on a number of data objects distributed above or below the size threshold in the object size distribution;
- identify whether a data object is stored in the data storage system in at least one of the first data replication scheme or the second data replication scheme, the first data replication scheme comprising a redundant replication scheme wherein a copy of the data object is stored in a plurality of data stores in the data storage system and the second data replication scheme comprising an erasure coding scheme, wherein the data object is divided into a plurality of shards, each of the plurality of shards having a size less than an object size of the data object and stored in a respective plurality of data stores in the data storage system;
- determine whether an object size of the data object meets the size threshold;
- and
- store the data object in one of the first data replication scheme or the second data replication scheme in the data storage system based at least in part upon whether the data object meets the size threshold.
6 more elements
A method, comprising:
- performing, by at least one computing device, an analysis of a data storage system to generate an object size distribution for the data storage system, the data storage system comprising at least one data store;
- periodically determining, by the at least one computing device, a size threshold to maintain a balance between data objects stored in a first data replication scheme and a second data replication scheme in the data storage system based at least in part on a number of data objects distributed above or below the size threshold in the object size distribution;
- identifying, by the at least one computing device, whether a data object is stored in the data storage system in at least one of the first data replication scheme or the second data replication scheme, the first data replication scheme comprising a redundant replication scheme wherein a copy of the data object is stored in a plurality of data stores in the data storage system and the second data replication scheme comprising an erasure coding scheme, wherein the data object is divided into a plurality of shards, each of the plurality of shards having a size less than an object size of the data object and stored in a respective plurality of data stores in the data storage system;
- determining, by the at least one computing device, whether an object size of the data object meets the size threshold;
- and
- storing, by the at least one computing device, the data object in one of the first data replication scheme or the second data replication scheme in the data storage system based at least in part upon whether the data object meets the size threshold.
3 more elements
A system, comprising:
- at least one computing device;
- and
- at least one storage device that is accessible to the at least one computing device, the at least one storage device storing a data storage application executable in the at least one computing device, the data storage application configured to cause the at least one computing device to at least:
- generate an object size distribution of a plurality of data objects stored in a data storage system, the data storage system comprising at least one data store;
- periodically determine a size threshold to maintain a balance between data objects stored in a redundant replication scheme and an erasure coding scheme in the data storage system based at least in part upon a number of data objects distributed above or below the size threshold in the object size distribution;
- identify a data object stored in the data storage system having an object size that meets the size threshold, the data object stored in the data storage system using the redundant replication scheme, wherein a copy of the data object is stored in a plurality of data stores in the data storage system;
- and
- store the data object in the data storage system in the erasure coding scheme, wherein the data object is divided into a plurality of shards, each of the plurality of shards having a size of less than an object size of the data object, each of the plurality of shards being stored in a respective plurality of data stores in the data storage system.
5 more elements
Dependencies are inferred from the claim text.