ERASURE CODING AND REPLICATION IN STORAGE CLUSTERS

• US 20130339818A1
• Filed: 06/13/2012
• Published: 12/19/2013
• Est. Priority Date: 06/13/2012
• Status: Active Grant

• Current Assignee: DataCore Software Corporation (Flagship Ventures 2004 Fund LLC)
• Original Assignee: Caringo Incorporated
• Inventors: TURPIN, Russell, BAKER, Don, CARPENTIER, Paul R.M., KLAGER, Andrew, PIERCE, Aaron, RING, Jonathan, YOAKLEY, David
• Granted Patent: US 8,799,746 B2
• Time in Patent Office: Days
• US Class Current: 714/763
• CPC Class Codes: G06F 11/10 Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/14 Error detection or correction of the data by redundancy in operation G06F11/16 takes precedence
• CPC Class Codes: G06F 3/0605 by facilitating the interaction with a user or administrator
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0632 by initialisation or re-initialisation of storage systems
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/0667 at data level, e.g. file, record or object virtualisation
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 3/0683 Plurality of storage devices
• CPC Class Codes: H03M 13/05 using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits H03M13/2906 takes precedence
• CPC Class Codes: H03M 13/25 Error detection or forward error correction by signal space coding, i.e. adding redundancy in the signal constellation, e.g. Trellis Coded Modulation [TCM] modulation codes H03M13/31
• CPC Class Codes: H03M 13/251 with block coding
• CPC Class Codes: H03M 13/2707 Simple row-column interleaver, i.e. pure block interleaving
• CPC Class Codes: H03M 13/353 Adaptation to the channel
• CPC Class Codes: H03M 13/356 Unequal error protection [UEP]
• CPC Class Codes: H03M 13/373 with erasure correction and erasure determination, e.g. for packet loss recovery or setting of erasures for the decoding of Reed-Solomon codes
• CPC Class Codes: H03M 13/3761 using code combining, i.e. using combining of codeword portions which may have been transmitted separately, e.g. Digital Fountain codes, Raptor codes or Luby Transform [LT] codes
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04L 67/1097 : for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

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.

Claims

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; and

returning a unique identifier of said manifest computer file to said client application.

2. The 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. The 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. The method as recited in claim 1 further comprising:

not replicating said digital object within said storage cluster.

5. The 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. The 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 one of said computer nodes, 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; and

returning said digital object to said client application.

8. The method as recited in claim 7 further comprising:

determining that said digital object is stored using erasure coding by reference to said manifest.

9. The method as recited in claim 7 further comprising:

determining that one of said segments is not present within said storage cluster; and

regenerating said segment not present using other of said segments and an erasure coding algorithm.

10. The method as recited in claim 7 further comprising:

identifying a first disk where one of said segments is stored; and

reading 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. The 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; and

reconstructing said digital object using said segments, a plurality of second segments identified by said second unique segment identifiers, and said erasure coding algorithm.

12. The 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. The 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 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 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; and

storing said regenerated segment on a computer node of said storage cluster.

15. The 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. The 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. The 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. The 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. The 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 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 unique disk identifier for said first disk;

locating said sibling segment within said storage cluster using said unique identifier; and

replacing said unique disk identifier for said first disk within said metadata of said sibling segment with a unique disk identifier for said second disk, whereby said metadata of said sibling segment indicates the 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 storage, 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 a 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; and

retaining 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 storage, 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; and

retaining 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 storage, 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; and

retaining 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 cluster to copy said digital object from said source cluster to said target cluster, said instruction including an address of a source node of said source cluster;

determining a target conversion format into which said digital object will be stored in said target cluster;

reading said digital object from said source cluster, said digital object being stored in a source conversion format and having a unique identifier within said source cluster; and

storing said digital object in said target cluster using said target conversion format, said digital object being stored using said unique identifier.

25. The method as recited in claim 24 wherein said target conversion format is different from said source conversion format.

26. The method as recited in claim 24 wherein said source conversion format is replication or erasure coding.

27. The 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 cluster.

28. The method as recited in claim 24 wherein said target cluster implements a storage format different from said source cluster.