Erasure coding and replication in storage clusters
원문보기
IPC분류정보
국가/구분
United States(US) Patent
등록
국제특허분류(IPC7판)
G11C-029/00
H03M-013/05
H03M-013/25
G06F-011/10
G06F-011/14
출원번호
US-0517527
(2012-06-13)
등록번호
US-8799746
(2014-08-05)
발명자
/ 주소
Baker, Don
Carpentier, Paul R. M.
Klager, Andrew
Pierce, Aaron
Ring, Jonathan
Turpin, Russell
Yoakley, David
출원인 / 주소
Caringo, Inc.
대리인 / 주소
Beyer Law Group LLP
인용정보
피인용 횟수 :
44인용 특허 :
16
초록▼
A cluster receives a request to store an object using replication or erasure coding. The cluster writes the object using erasure coding. A manifest is written that includes an indication of erasure coding and a unique identifier for each segment. The cluster returns a unique identifier of the manife
A cluster receives a request to store an object using replication or erasure coding. The cluster writes the object using erasure coding. A manifest is written that includes an indication of erasure coding and a unique identifier for each segment. The cluster returns a unique identifier of the manifest. The cluster receives a request from a client that includes a unique identifier. The cluster determines whether the object has been stored using replication or erasure coding. If using erasure coding, the method reads a manifest. The method identifies segments within the cluster using unique segment identifiers of the manifest. Using these unique segment identifiers, the method reconstructs the object. A persistent storage area of another disk is scanned to find a unique identifier of a failed disk. If using erasure coding, a missing segment previously stored on the disk is identified. The method locates other segments. Missing segments are regenerated.
대표청구항▼
1. A method of storing a digital object in a storage cluster, said method comprising: receiving from a client application a request at a computer node of said storage cluster to store said digital object;determining whether to store said digital object in said storage cluster using replication or er
1. A method of storing a digital object in a storage cluster, said method comprising: receiving from a client application a request at a computer node of said storage cluster to store said digital object;determining whether to store said digital object in said storage cluster using replication or erasure coding;when it is determined to store said digital object using erasure coding, writing said digital object to a plurality of computer nodes of said storage cluster using erasure coding, said digital object being stored as a plurality of segments;creating a manifest computer file that includes an indication of said erasure coding and a unique identifier within said storage cluster for each of said segments;storing said manifest computer file on a computer node of said storage cluster; andreturning a manifest unique identifier identifying said manifest computer file to said client application. 2. A method as recited in claim 1 further comprising: determining whether to store said digital object using replication or erasure coding by reference to an inherent property of said digital object, an instruction from said client application, or metadata of said digital object. 3. A method as recited in claim 1 further comprising: replicating said manifest computer file within said storage cluster and not storing said manifest computer file using erasure coding. 4. A method as recited in claim 1 further comprising: not replicating said digital object within said storage cluster. 5. A method as recited in claim 1 further comprising: for each segment stored on a disk of said storage cluster, storing on said disk in association with said segment a unique identifier of a next disk that stores another segment of said digital object. 6. A method as recited in claim 5 further comprising: storing said unique identifier of said next disk in association with said segment by storing said unique identifier in a journal entry for said segment on said disk. 7. A method of reading a digital object from a storage cluster having a plurality of computer nodes, said method comprising: receiving, at one of said computer nodes within said storage cluster, a request from a client application that includes a unique identifier for said digital object;determining whether said digital object is stored within said storage cluster using replication or erasure coding;when it is determined that said digital object is stored using erasure coding, reading a manifest stored on a computer nodes of said storage cluster, said manifest being identified by said unique identifier;identifying a plurality of segments within said storage cluster using unique segment identifiers found within said manifest;reconstructing said digital object using said segments and an erasure coding algorithm; andreturning said digital object to said client application. 8. A method as recited in claim 7 further comprising: determining that said digital object is stored using erasure coding by reference to said manifest. 9. A method as recited in claim 7 further comprising: determining that one of said segments is not present within said storage cluster; andregenerating said segment not present using other of said segments and an erasure coding algorithm. 10. A method as recited in claim 7 further comprising: identifying a first disk where one of said segments is stored; andreading a disk identifier for a second disk where another of said segments is stored, said disk identifier being stored in association with said one of said segments on said first disk. 11. A method as recited in claim 7 further comprising: identifying a second erasure set within said manifest, said second erasure set including a plurality of second unique segment identifiers; andreconstructing said digital object using said segments, a plurality of second segments identified by said second unique segment identifiers, and said erasure coding algorithm. 12. A method as recited in claim 7 wherein said manifest is replicated within said storage cluster and wherein said manifest is not stored within said storage cluster using erasure coding. 13. A method as recited in claim 7 wherein said digital object is not replicated within said storage cluster. 14. A method of recovering from a failed disk, said method comprising: detecting within a storage cluster having a plurality of computer nodes that a first disk of one of said plurality of computer nodes has failed;scanning a persistent storage area of a second disk of said storage cluster to find a unique identifier of said failed disk, said unique identifier in association with a digital stream of said storage cluster;determining whether said digital stream is stored within said storage cluster using replication or erasure coding;when it is determined that said digital stream is stored using erasure coding, identifying a missing segment previously stored on said failed disk;locating a plurality of other segments within said storage cluster, said plurality of other segments including said digital stream;regenerating said missing segment previously stored on said failed disk using said plurality of other segments and an erasure coding algorithm; andstoring said regenerated segment on a computer node of said storage cluster. 15. A method as recited in claim 14 further comprising: scanning a metadata section of said digital stream to find unique identifiers for said plurality of other segments. 16. A method as recited in claim 14 further comprising: scanning said persistent storage area of said second disk includes scanning a journal entry for said digital stream. 17. A method as recited in claim 16 further comprising: determining whether said digital stream is stored using erasure coding by reference to said journal entry. 18. A method as recited in claim 14 further comprising: identifying said missing segment previously stored on said failed disk before receiving a request from outside the storage cluster for a digital object that is stored within said storage cluster using erasure coding that includes said missing segment. 19. A method as recited in claim 14 wherein said missing segment is not replicated within said storage cluster. 20. A method of relocating a segment within a storage cluster, said method further comprising: identifying a segment on a first disk of a computer node within a storage cluster, said segment being one of a plurality of segments representing a digital object stored within said storage cluster;relocating said segment from said first disk to a second disk of said storage cluster, said second disk being identified by a second unique disk identifier;retrieving from metadata of said segment a unique identifier for a sibling segment of said plurality of segments, said sibling segment including in its metadata a first unique disk identifier for said first disk;locating said sibling segment within said storage cluster using said unique identifier; andreplacing said first unique disk identifier for said first disk within said metadata of said sibling segment with a second unique disk identifier for said second disk, whereby said metadata of said sibling segment indicates said second disk to where said segment has been relocated. 21. A method of converting a digital object within a storage cluster, said method comprising: storing said digital object within said storage cluster on a single disk of a computer node as a continuous stream of bits, said digital object having a unique identifier within said storage cluster;after said storing, identifying metadata of said storage cluster indicating a requirement to convert said digital object to an erasure coding storage format;reading said digital object from said single disk using said computer node of said storage cluster;writing said digital object to a plurality of disks of said storage cluster using said erasure coding storage format; andretaining said unique identifier for said digital object written in said erasure coding storage format, whereby a client application may retrieve said digital object written in said erasure coding storage format using said unique identifier. 22. A method of converting a digital object within a storage cluster, said method comprising: storing said digital object within said storage cluster in a first erasure coding storage format, said digital object having a unique identifier within said storage cluster;after said storing, identifying metadata of said storage cluster indicating a requirement to convert said digital object to a second erasure coding storage format;reading said digital object from said storage cluster using a computer node of said storage cluster;writing said digital object to said storage cluster using said second erasure coding storage format; andretaining said unique identifier for said digital object written in said second erasure coding storage format, whereby a client application may retrieve said digital object written in said second erasure coding storage format using said unique identifier. 23. A method of converting a digital object within a storage cluster, said method comprising: storing said digital object within said storage cluster in an erasure coding storage format, said digital object having a unique identifier within said storage cluster;after said storing, identifying metadata of said storage cluster indicating a requirement to convert said digital object to a storage format using replication;reading said digital object from said storage cluster using a computer node of said storage cluster;writing said digital object to a single disk of a computer node of said storage cluster as a continuous stream of bits; andretaining said unique identifier for said digital object written as said continuous stream of bits, whereby a client application may retrieve said digital object written as said continuous stream of bits using said unique identifier. 24. A method of copying a digital object from a source storage cluster to a target storage cluster, said method comprising: receiving an instruction at a target node of said target storage cluster to copy said digital object from said source storage cluster to said target storage cluster, said instruction including an address of a source node of said source storage cluster;determining a target conversion format into which said digital object will be stored in said target storage cluster;reading said digital object from said source storage cluster, said digital object being stored in a source conversion format and having a unique identifier within said source storage cluster; andstoring said digital object in said target storage cluster using said target conversion format, said digital object being stored using said unique identifier. 25. A method as recited in claim 24 wherein said target conversion format is different from said source conversion format. 26. A method as recited in claim 24 wherein said source conversion format is replication or erasure coding. 27. A method as recited in claim 24 further comprising: determining said target conversion format by reference to the metadata of said digital object or by reference to a setting of said target storage cluster. 28. A method as recited in claim 24 wherein said target storage cluster implements a storage format different from said source storage cluster.
연구과제 타임라인
LOADING...
LOADING...
LOADING...
LOADING...
LOADING...
이 특허에 인용된 특허 (16)
Carpentier,Paul R. M.; Forret,Peter; Willems,Maarten J. P. A., Additional hash functions in content-based addressing.
Farber David A. ; Lachman Ronald D., Data processing system using substantially unique identifiers to identify data items, whereby identical data items hav.
Sim-Tang, Siew Yong; Ustimenko, Semen Alexandrovich, Method for lock-free clustered erasure coding and recovery of data across a plurality of data stores in a network.
Davis, John; Miller, Ethan; Gold, Brian; Colgrove, John; Vajgel, Peter; Hayes, John; Ho, Alex, Data placement based on data properties in a tiered storage device system.
Davis, John D.; Hayes, John; Kannan, Hari; Miladinovic, Nenad; Tan, Zhangxi, Data rebuild on feedback from a queue in a non-volatile solid-state storage.
Davis, John D.; Hayes, John; Tan, Zhangxi; Kannan, Hari; Miladinovic, Nenad, Data rebuild on feedback from a queue in a non-volatile solid-state storage.
Hayes, John; Gupta, Shantanu; Davis, John; Gold, Brian; Tan, Zhangxi, Nonrepeating identifiers in an address space of a non-volatile solid-state storage.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.