Computation refinement in a data storage system
원문보기
IPC분류정보
국가/구분
United States(US) Patent
등록
국제특허분류(IPC7판)
G06F-011/00
G06F-011/10
G06F-017/30
출원번호
US-0543827
(2014-11-17)
등록번호
US-10198317
(2019-02-05)
발명자
/ 주소
Sorenson, III, James Christopher
Sieklucki, Mark Robert
Patel, Rajesh Shanker
Rahmany, Dave
출원인 / 주소
Amazon Technologies Inc.
대리인 / 주소
Kowert, Robert C.
인용정보
피인용 횟수 :
0인용 특허 :
5
초록▼
A storage manager may be used to perform a refinement operation on a coding matrix as part of a coding operation (e.g., an encoding operation or a decoding operation) in a storage system, such as an object-redundant storage system. The refinement operation may include identifying a plurality of comp
A storage manager may be used to perform a refinement operation on a coding matrix as part of a coding operation (e.g., an encoding operation or a decoding operation) in a storage system, such as an object-redundant storage system. The refinement operation may include identifying a plurality of computations to be performed as part of the coding operation, where the plurality of computations have common terms and operations. The refinement operation may include refining a coding matrix associated with the coding operation based on the identified computations and precomputing the identified computations. The precomputed computations may be used instead of performing the computations when performing the coding operation.
대표청구항▼
1. A system, comprising: a storage system comprising a plurality of storage devices, wherein the storage system is configured to store a plurality of data objects according to an erasure coding technique, wherein each respective data object of the plurality of data objects is stored as a respective
1. A system, comprising: a storage system comprising a plurality of storage devices, wherein the storage system is configured to store a plurality of data objects according to an erasure coding technique, wherein each respective data object of the plurality of data objects is stored as a respective plurality of shards such that the respective data object can be reconstructed from a particular number of shards that is fewer than a total number of shards for that data object, wherein each shard for the respective data object is stored on a different one of the plurality of storage devices than any other shard of the plurality of shards for the respective data object; anda storage manager implemented by one or more hardware processors and configured to receive a plurality of requests from one or more clients for respective data objects of the plurality of data objects, wherein in response to each individual request of the plurality of requests the storage manager is configured to: retrieve, while the storage devices storing the plurality of shards for the requested data object are each operational, a subset of the plurality of shards for the requested data object from the storage system, wherein the subset includes at least the particular number of shards;determine a decoding matrix for the requested data object, wherein the decoding matrix specifies a plurality of computations for reconstructing the data object from the subset of the plurality of shards;perform a refinement operation on the decoding matrix, wherein to perform the refinement operation the storage manager is further configured to identify two or more computations of the plurality of computations having common terms and operations according to the decoding matrix, and to precompute one or more results for the two or more identified computations;perform computations according to the decoding matrix to reconstruct the requested data object from the subset, wherein the storage manager is further configured to use the one or more precomputed results instead of performing the identified computations while reconstructing the requested data object; andreturn the reconstructed data object to the client. 2. The system of claim 1, wherein, to identify the two or more computations having common terms and operations according to the decoding matrix, the storage manager is further configured to: generate a list of indices based on the decoding matrix, wherein each row of the list of indices corresponds to a row of the decoding matrix and comprises one or more index values indicating which data terms from the subset of shards are specified by the row of the decoding matrix for computation to reconstruct the requested data object; andparse the list of indices to identify one or more sets of indices having index values that are repeated in different rows of the list of indices. 3. The system of claim 2, wherein, to perform the refinement operation, the storage manager is further configured to replace a particular set of indices in the list of indices with a new index representative of a particular corresponding computation to be precomputed. 4. The system of claim 1, wherein the storage system and storage manager are part of a network-based storage service, wherein respective data objects of the plurality of data objects are stored on behalf of a plurality of different clients according to a network-based interface of the network-based storage service, and wherein at least some of the storage devices store shards for multiple different clients of the plurality of different clients. 5. The system of claim 1, wherein, to determine the decoding matrix of the subset, the storage manager is further configured to: retrieve a stored erasure coding matrix corresponding to the data object; andgenerate the decoding matrix from the erasure coding matrix according to which shards of the plurality of shards form the subset, wherein each shard of the plurality of shards corresponds to a respective portion of the stored erasure coding matrix, wherein the decoding matrix is generated from respective portions of the stored erasure coding matrix. 6. A method, comprising: performing, by one or more computers: receiving a plurality of requests from one or more clients, wherein each request comprises instructions for a respective data object; andin response to receiving each individual request of the plurality of the requests: retrieving a subset of a plurality of shards for an encoded data object, wherein the data object requested from the respective client is stored as the encoded data object comprising at least the plurality of shards such that the data object can be reconstructed from a particular number of shards that is fewer than a total number of shards of the plurality of shards, wherein each shard of the plurality of shards is stored on a different one of a plurality of operational storage devices than any other shard of the plurality of shards;determining a decoding matrix for the encoded data object, wherein the decoding matrix specifies a plurality of computations for reconstructing the data object from at least the subset of the plurality of shards;performing, on the decoding matrix, a refinement operation comprising identifying two or more computations of the plurality of computations having common terms and operations according to the decoding matrix, and precomputing one or more results for the two or more identified computations;perform computations according to the decoding matrix to reconstruct the data object from at least the subset of the plurality of shards, wherein the one or more precomputed results are used instead of performing the identified computations while generating the decoded data object; andreturning, to the respective client, the data object reconstructed from the at least the subset of the plurality of shards. 7. The method of claim 6, further comprising: retrieving each shard from a respective storage device of the plurality of storage devices, wherein at least some of the plurality of storage devices store different shards for other data objects. 8. The method of claim 6, wherein retrieving a subset of a plurality of shards further comprises waiting until a minimum number of shards needed to reconstruct the data object have been received. 9. The method of claim 6, wherein performing, on the decoding matrix, a refinement operation comprising identifying two or more computations of the plurality of computations further comprises: generating a list of indices based on the decoding matrix, wherein each row of the list of indices corresponds to a row of the decoding matrix and comprises one or more index values indicating which data terms from the at least a subset of the plurality of shards are specified by the row of the decoding matrix for computation to reconstruct the requested data object; anditeratively parsing the list of indices to identify one or more sets of indices having index values that are repeated in different rows of the list of indices. 10. The method of claim 6, wherein determining the decoding matrix further comprises determining the decoding matrix according to which shards of the plurality of shards form the subset. 11. The method of claim 6, wherein determining the decoding matrix further comprises rejecting, based at least on a sufficient number of shards in a subset being available, one or more of the plurality of shards from being included in the at least the subset of the plurality of shards. 12. A non-transitory, computer-readable storage medium storing program instructions that when executed on one or more computers cause the one or more computers to: implement a data decoding system configured to, in response to each individual request of a plurality of requests from one or more client computers for respective data objects: retrieve a subset of a plurality of shards for an encoded data object, wherein the data object requested from the client computer is stored as the encoded data object comprising at least the plurality of shards, wherein each shard of the plurality of shards is stored on a different one of a plurality of operational storage devices than any other shard of the plurality of shards;determine a decoding matrix for the encoded data object, wherein the decoding matrix specifies a plurality of computations for reconstructing a data object from at least the subset of the plurality of shards;perform a refinement operation on the decoding matrix, comprising identifying two or more computations of the plurality of computations having common terms and operations according to the decoding matrix, and precomputing one or more results for the two or more identified computations;perform computations according to the decoding matrix to reconstruct the data object from the at least a subset of the plurality of shards, wherein the data decoding system is configured to use the one or more precomputed results instead of performing the two or more identified computations; andreturn, to the client computer, the data object reconstructed from the at least the subset of the plurality of shards. 13. The non-transitory, computer-readable storage medium of claim 12, wherein, to determine the decoding matrix, the data decoding system is further configured to reject, based at least on a sufficient number of shards in a subset being available, one or more of the plurality of shards from being included in the at least the subset of the plurality of shards. 14. The non-transitory, computer-readable storage medium of claim 12, wherein, to receive the plurality of shards, the data decoding system is further configured to wait until a minimum number of shards needed to reconstruct the data object have been received. 15. The non-transitory, computer-readable storage medium of claim 12, wherein, to identify the two or more computations, the data decoding system is configured to: generate a list of indices based on the decoding matrix, wherein each row of the list of indices corresponds to a row of the decoding matrix and comprises one or more index values indicating which data terms from the at least a subset of the plurality of shards are specified by the row of the decoding matrix for computation to reconstruct the requested data object; anditeratively parse the list of indices to identify one or more sets of indices having index values that are repeated in different rows of the list of indices. 16. The non-transitory, computer-readable storage medium of claim 15, wherein, to iteratively parse the list of indices, the data decoding system is configured, during a particular iteration, to: identify a particular set of indices having index values that are repeated in different rows of the list of indices;replace each occurrence of the repeated index values of the particular set of indices with a respective new index value; andgenerate a new row in the list of indices that indicates that each new index value represents the repeated index values of the particular set of indices. 17. The non-transitory, computer-readable storage medium of claim 16, wherein, to iteratively parse the list of indices, the data decoding system is configured, during a subsequent iteration, to: identify a different set of indices having index values that are repeated in different rows of the list of indices, wherein the index values that are repeated in the different set of indices include the new index value and at least one other index value;replace each occurrence of the repeated index values of the different set of indices with a respective different new index value; andgenerate a different new row in the list of indices that indicates that each different new index value represents the repeated index values of the different set of indices. 18. The non-transitory, computer-readable storage medium of claim 12, wherein, to identify the two or more computations, the data decoding system is configured to continue to attempt to identify, according to a greedy algorithm on the decoding matrix, computations having common terms and operations as specified in the decoding matrix until a specified number of computations have been identified. 19. The non-transitory, computer-readable storage medium of claim 12, wherein, to identify the two or more computations, the data decoding system is configured to continue to attempt to identify, according to a greedy algorithm on the decoding matrix, computations having common terms and operations as specified in the decoding matrix until a predetermined threshold has been reached, and wherein the predetermined threshold includes: until a predetermined amount of time expires, until a specified number of computations has been identified, until all computations having at least a particular complexity are identified, until a minimum number of terms in common for each identified computation is reached, until a number of common terms based on matrix size is reached, or until a predicted number of optimal computations is reached. 20. The non-transitory, computer-readable storage medium of claim 12, wherein the data decoding system is further configured to receive a complexity indicator that specifies a minimum number of terms, and, to perform the refinement operation, the data decoding system is further configured to identify only computations having at least the minimum number of terms in common. 21. The non-transitory, computer-readable storage medium of claim 12, wherein the encoded data object is stored as at least one other shard that is not included in the plurality of shards, and wherein the encoded data object is stored according to an erasure coding technique. 22. The non-transitory, computer-readable storage medium of claim 12, wherein each computation of the two or more identified computations includes one or more exclusive or (XOR) operations, and wherein precomputing the one or more results for the two or more identified computations comprises performing the one or more XOR operations.
연구과제 타임라인
LOADING...
LOADING...
LOADING...
LOADING...
LOADING...
이 특허에 인용된 특허 (5)
Dayal, Shobhit; Lee, Edward K.; Gritter, Mark G., Avoiding long access latencies in redundant storage systems.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.