Failure tolerant data storage

• US 20070136525A1
• Filed: 12/08/2005
• Published: 06/14/2007
• Est. Priority Date: 12/08/2005
• Status: Active Grant

• Current Assignee: Sony Corporation (Sony Group Corp.), Sony Electronics Inc. (Sony Group Corp.)
• Original Assignee: Sony Corporation (Sony Group Corp.), Sony Electronics Inc. (Sony Group Corp.)
• Inventors: Read, Christopher
• Granted Patent: US 7,596,673 B2
• Time in Patent Office: Days
• US Class Current: 711/114
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 2211/1023 Different size disks, i.e. non uniform size of disks in RAID systems with parity
• 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

Abstract

A method for storing data across a plurality of N storage devices S₁ . . . S_N, wherein at least one of the storage devices has a storage capacity that not equal to a storage capacity of others of the storage devices involves identifying a storage device S_MAX having a largest capacity of the plurality of storage devices S₁ . . . S_N; encoding the data with a erasure encoder to produce F erasure codewords, where F= $\sum _{K=1}^N{F}_K$
with K being a counting integer; and distributing the erasure codewords among the N storage devices S₁ . . . S_N in approximate proportion to the storage capacity C_K of each of the N storage devices S₁ . . . S_N subject to the constraint that enough erasure codewords are stored in each of the N storage devices to assure that if any one of the storage devices become unavailable, all of the data stored in the systems can be restored using the fountain codewords stored in the remaining storage devices S₁ . . . S_N. In accordance with certain embodiments consistent with the present invention, the erasure codewords are fountain codewords. This abstract is not to be considered limiting, since other embodiments may deviate from the features described in this abstract.

Claims

1. A method of allocating storage for storing data across a plurality of N storage devices S₁ . . . S_N, wherein at least one of the storage devices has a storage capacity that is not equal to a storage capacity of others of the storage devices, the method comprising:

a) determining a maximum capacity C_MAX of a storage device S_MAX having a largest capacity of the plurality of storage devices S₁ . . . S_N;

b) determining a total storage capacity C of all of the plurality of storage devices

$S_1<br><br>\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>S_N<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{as}<br><br>\text{\hspace{1em}<br><br>}<br><br>C=\underset{K=1}{\overset{N}{\sum <br><br>}}<br><br>C_K,$

 

where K is a counting integer;

c) defining a maximum total number of fountain codewords

$F=\underset{K=1}{\overset{N}{\sum <br><br>}}<br><br>F_K$

 

that could be stored in the plurality of storage devices S₁ . . . S_N;

d) defining F_MAX as a maximum number of fountain codewords that would be lost if the data in S_MAX is lost;

e) estimating a target ratio of capacity to fountain codewords V as V≈

C/F≈

(C−

C_MAX)/(F−

F_MAX)≈

(C−

C_MAX)/R, where R is a number of fountain codewords required to recover C_MAX if the data in S_MAX is lost;

f) using the estimate of the value of V to estimate the values of F₁ . . . F_N as F_K=Int(C_K/V);

g) adjusting the estimated values of F₁ . . . F_N by addition of a rounding factor F_K=Int(C_K/V+L) to assure that

$\left(\underset{K=1}{\overset{N}{\sum <br><br>}}<br><br>F_K\right)-F_{\mathrm{MAX}}\ge <br><br>R;<br><br>$

 

and

h) allocating fountain codewords, and storing data to the storage devices S₁ . . . S_N in proportion to the estimated values of F₁ . . . F_N.

2. The method according to claim 1, wherein the storage devices S₁ . . . S_N comprise at least one of a disc storage device, a Random Access Memory (RAM) device, a network memory device, an optical storage device, a magnetic storage element, a magneto-optical storage element, or a flash memory.

3. The method according to claim 1, further comprising:

determining that a storage device S_N+1 is available for storage of the codewords;

reallocating the codewords across the plurality of storage devices S₁ . . . S_N+1.

4. The method according to claim 3, wherein the reallocating comprises moving codewords from certain of the storage devices S₁ . . . S_N to storage device S_N+1.

5. The method according to claim 3, wherein the reallocation is carried out subject to the constraint that

6. The method according to claim 3, wherein the reallocation comprises:

i) determining a new maximum capacity C_MAX of a storage device S_MAX having a largest capacity of the plurality of storage devices S₁ . . . S_N+1;

j) determining a total storage capacity C of all of the plurality of storage devices

$S_1<br><br>\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>S_{N+1}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{as}<br><br>\text{\hspace{1em}<br><br>}<br><br>C=\underset{K=1}{\overset{N+1}{\sum <br><br>}}<br><br>C_K;<br><br>$

k) defining a maximum total number of fountain codewords

$F=\underset{K=1}{\overset{N+1}{\sum <br><br>}}<br><br>F_K$

 

that could be stored in the plurality of storage devices S₁ . . . S_N+1;

l) defining F_MAX as a maximum number of fountain codewords that would be lost if the data in S_MAX is lost;

m) estimating a revised target ratio of capacity to fountain codewords V as V≈

C/F≈

(C−

C_MAX)/(F−

F_MAX)=(C−

C_MAX)/R, where R is a number of fountain codewords required to recover C_MAX if the data in S_MAX is lost;

n) using the estimate of the value of V to estimate the values of F₁ . . . F_N+1 as F_K=Int(C_K/V);

o) adjusting the estimated values of F₁ . . . F_N+1 by addition of a rounding factor to assure that

$\left(\underset{K=1}{\overset{N+1}{\sum <br><br>}}<br><br>F_K\right)-F_{\mathrm{MAX}}\ge <br><br>R;<br><br>$

and

p) allocating fountain codewords storing data to the storage devices S₁ . . . S_N+1 in proportion to the adjusted values of F₁ . . . F_N+1.

7. The method according to claim 1, further comprising:

determining that storage device S_P, being any one of storage devices S₁ . . . S_N is no longer available for storage of the codewords;

reallocating the codewords across the plurality of storage devices S₁ . . . S_N excluding S_P.

8. The method according to claim 7, wherein the reallocating comprises calculating a new allocation:

generating new codewords; and

distributing the new codewords among the storage devices S₁ . . . S_N excluding S_P.

9. The method according to claim 7, wherein the reallocation is carried out subject to the constraint that

10. The method according to claim 7, wherein the reallocation comprises:

i) determining a new maximum capacity C_MAX of a storage device S_MAX having a largest capacity of the plurality of storage devices S₁ . . . S_N excluding S_P;

j) determining a total storage capacity C of all of the plurality of storage devices S₁ . . . S_N excluding S_P as

$C=\left(\underset{K=1}{\overset{N}{\sum <br><br>}}<br><br>C_K\right)-C_P;<br><br>$

k) defining a maximum total number of fountain codewords

$F=\left(\underset{K=1}{\overset{N}{\sum <br><br>}}<br><br>F_K\right)-F_P$

 

that could be stored in the plurality of storage devices S₁ . . . S_N excluding S_P;

l) defining F_MAX as a maximum number of fountain codewords that would be lost if the data in S_MAX is lost;

m) estimating a revised target ratio of capacity to fountain codewords V as V≈

C/F≈

(C−

C_MAX/(F−

F_MAX)≈

(C−

C_MAX)/R, where R is a number of fountain codewords required to recover C_MAX if the data in S_MAX is lost;

n) using the estimate of the value of V to estimate the values of F₁ . . . F_N+1 as F_K=Int(C_K/V) for S₁ . . . S_N excluding S_P;

o) adjusting the estimated values of F₁ . . . F_N+1 by addition of a rounding factor to assure that

$\left(\underset{K=1}{\overset{N+1}{\sum <br><br>}}<br><br>F_K\right)-F_{\mathrm{MAX}}\ge <br><br>R$

R for each of S₁ . . . S_N excluding S_P; and

p) allocating fountain codewords storing data to the storage devices S₁ . . . S_N excluding S_P in proportion to the estimated values of F₁ . . . F_N.

11. The method according to claim 1, further comprising:

determining that storage device S_P, being any one of storage devices S₁ . . . S_N is no longer available for storage of the codewords;

determining if it is possible to reallocate codewords representing all stored data on the remaining storage devices S₁ . . . S_N excluding S_P; and

if not, establishing that an error condition exists.

12. A computer readable storage medium storing instructions which, when executed on a programmed processor, carry out a process according to claim 1.

13. A method for storing data across a plurality of N storage devices S₁ . . . S_N, with respective capacities C₁ . . . C_N, wherein at least one of the storage devices has a storage capacity that not equal to a storage capacity of others of the storage devices, the method comprising:

encoding the data with an erasure encoder to produce erasure codewords; and

distributing the erasure codewords among the N storage devices S₁ . . . S_N in approximate proportion to the storage capacity C_K of each of the N storage devices S₁ . . . S_N subject to the constraint that enough erasure codewords are stored in each of the N storage devices, to assure that if any one of the storage devices, S_P, becomes unavailable, all of the data in the system can be restored using the erasure codewords stored in the remaining storage devices S₁ . . . S_N excluding S_P.

14. The method according to claim 13, wherein the proportion of the number codewords F_P to the capacity C_P of each of the storage devices is a multiple of (C−

C_MAX)/R.

15. The method according to claim 13, wherein the erasure codewords comprise fountain codewords.

16. The method according to claim 13, wherein the storage devices S₁ . . . S_N comprise at least one of a disc storage device, a Random Access Memory (RAM) device, a network memory device, an optical storage device, a magnetic storage element, a magneto-optical storage element, or a flash memory.

17. The method according to claim 13, further comprising:

determining that a storage devices S_N+1 is available for storage of the codewords;

reallocating the codewords across the plurality of storage devices S₁ . . . S_N+1.

18. The method according to claim 17, wherein the reallocating comprises moving codewords from certain of the storage devices S₁ . . . S_N to storage device S_N+1.

19. The method according to claim 17, wherein the reallocation is carried out subject to the constraint that

20. The method according to claim 13, further comprising:

determining that storage device S_P, being any one of storage devices S₁ . . . S_N is no longer available for storage of the codewords;

reallocating the codewords across the plurality of storage devices S₁ . . . S_N excluding S_P.

21. The method according to claim 20, wherein the reallocating comprises:

calculating a new allocation;

generating new codewords; and

distributing the new codewords among the storage devices S₁ . . . S_N excluding S_P.

22. The method according to claim 17, wherein the reallocation is carried out subject to the constraint that

23. The method according to claim 17, further comprising:

determining that storage device S_P, being any one of storage devices S₁ . . . S_N is no longer available for storage of the codewords;

determining if it is possible to reallocate codewords representing all stored data on the remaining storage devices S₁ . . . S_N excluding S_P; and

if not, establishing that an error condition exists.

24. A computer readable storage medium storing instructions which, when executed on a programmed processor, carry out a process according to claim 13.

25. An arrangement for storing data, comprising in combination:

a plurality of N storage devices S₁ . . . S_N, wherein at least one of the storage devices has a storage capacity that not equal to a storage capacity of others of the storage devices;

wherein a storage device S_MAX has a largest capacity of the plurality of storage devices S₁ . . . S_N;

a fountain encoder that encodes the data into F fountain codewords, wherein

$F=\underset{K=1}{\overset{N}{\sum <br><br>}}<br><br>F_K$

 

with K being a counting integer; and

wherein the fountain encoder distributes the fountain codewords among the N storage devices S₁ . . . S_N in approximate proportion to the storage capacity C_K of each of the N storage devices S₁ . . . S_N subject to the constraint that enough fountain codewords are stored in each of the N storage devices, to assure that all of the data in all of the N storage devices can be recovered if any one of the N storage devices S_P is lost using the fountain codewords stored in the remaining storage devices S₁ . . . S_N excluding S_P.

26. The apparatus according to claim 25, wherein the storage devices S₁ . . . S_N comprise at least one of a disc storage device, a Random Access Memory (RAM) device, a network memory device, an optical storage device, a magnetic storage element, a magneto-optical storage element, or a flash memory.

27. The apparatus according to claim 25, further comprising:

means for determining that a new storage device S_N+1 is available for storage of the codewords; and

wherein the fountain coder reallocates the codewords across the plurality of storage devices S₁ . . . S_N+1 in response to determining that the storage devices S_N+1 is available for storage of the codewords.

28. The apparatus according to claim 25, wherein the reallocating comprises moving codewords from certain of the storage devices S₁ . . . S_N to storage device S_N+1.

29. The method according to claim 25, wherein the reallocation is carried out subject to the constraint that

30. The apparatus according to claim 25, further comprising:

means for determining that storage device S_P, being any one of storage devices S₁ . . . S_N is no longer available for storage of the codewords;

wherein the fountain encoder reallocates the codewords across the plurality of storage devices S₁ . . . S_N excluding S_P upon determining that storage device S_P is no longer available for storage of the codewords.

31. The apparatus according to claim 30, wherein the reallocating comprises calculating a new allocation;

generating new codewords; and

distributing the new codewords among the storage devices S₁ . . . S_N excluding S_P.

32. The apparatus according to claim 30, wherein the reallocation is carried out subject to the constraint that

33. The apparatus according to claim 25, further comprising:

means for determining that storage device S_P, being any one of storage devices S₁ . . . S_N is no longer available for storage of the codewords;

means for determining if it is possible to reallocate codewords representing all stored data on the remaining storage devices S₁ . . . S_N excluding S_P; and

if not, establishing that an error condition exists.

34. A method for storing data across a plurality of N storage devices S₁ . . . S_N, wherein at least certain of the storage devices have a storage capacity C_MIN=C_J≦

C_K . . . ≦

C_MAX, and C_MIN<

C_MAX with the method comprising;

establishing a first capacity band equal in capacity to C_MIN in each of the storage devices;

encoding a collection of source data with an erasure encoder to produce F_J erasure codewords;

allocating the F_J erasure codewords uniformly among the N storage devices S₁ . . . S_N;

establishing a second capacity band equal in capacity to C_K−

C_J in each of the storage devices having capacity≧

C_J;

encoding a collection of source data with an erasure encoder to produce F_K erasure codewords;

allocating the F_K erasure codewords uniformly among the storage devices S₁ . . . S_N having capacity≧

C_J.

35. The method according to claim 34, wherein the erasure codewords are encoded using an encoder selected from the group consisting of a RAID parity encoding, fountain encoding, and simple data duplication.

36. The method according to claim 34, wherein the storage devices S₁ . . . S_N comprise at least one of a disc storage device, a Random Access Memory (RAM) device, a network memory device, an optical storage device, a magnetic storage element, a magneto-optical storage element, or a flash memory.

37. The method according to claim 34, further comprising:

determining that a storage device S_N+1 is available for storage of the codewords;

reallocating the codewords across the plurality of storage devices S₁ . . . S_n+1.

38. The method according to claim 34, further comprising:

determining that storage device S_P, being any one of storage devices S₁ . . . S_N is no longer available for storage of the codewords;

reallocating the codewords across the plurality of storage devices S₁ . . . S_N excluding S_P.

39. The method according to claim 34, further comprising:

determining that storage device S_P, being any one of storage devices S₁ . . . S_N is no longer available for storage of the codewords;

determining if it is possible to reallocate codewords representing all stored data on the remaining storage devices S₁ . . . S_N excluding S_P; and

if not, establishing that an error condition exists.

40. A computer readable storage medium storing instructions which, when executed on a programmed processor, carry out a process according to claim 34.