US2009044075A1PendingUtilityA1
Failure tolerant data storage
Est. expiryDec 8, 2025(expired)· nominal 20-yr term from priority
Inventors:Christopher Jensen Read
H03M 13/3761G06F 11/1076G06F 2211/1023
42
PatentIndex Score
0
Cited by
0
References
0
Claims
Abstract
An arrangement for storing data has a plurality of N storage devices S 1 . . . 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. A storage device S MAX has a largest capacity of the plurality of storage devices S 1 . . . S N . A fountain encoder encodes the data into F fountain codewords, wherein F = ∑ K = 1 N F K with K being a counting integer; and the fountain encoder distributes the fountain codewords among the N storage devices S 1 . . . S N in approximate proportion to the storage capacity C K of each of the N storage devices S 1 . . . 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 1 . . . S N excluding S P . This abstract is not to be considered limiting, since other embodiments may deviate from the features described in this abstract.
Claims
exact text as granted — not AI-modified1 . A method for storing data across a plurality of N storage devices S 1 . . . S N , with respective capacities C 1 . . . 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 1 . . . S N in approximate proportion to the storage capacity C K of each of the N storage devices S 1 . . . 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 1 . . . S N excluding S P .
2 . The method according to claim 1 , 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.
3 . The method according to claim 1 , wherein the erasure codewords comprise fountain codewords.
4 . The method according to claim 1 , wherein the storage devices S 1 . . . 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.
5 . The method according to claim 1 , 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 1 . . . S N+1 .
6 . The method according to claim 5 , wherein the reallocating comprises moving codewords from certain of the storage devices S 1 . . . S N to storage device S N+1 .
7 . The method according to claim 5 , wherein the reallocation is carried out subject to the constraint that
(
∑
K
=
1
N
+
1
F
K
)
-
F
MAX
≥
R
,
where F MAX is the number of codewords to be stored on the largest of storage devices S 1 . . . S N+1 .
8 . The method according to claim 1 , further comprising:
determining that storage device S P , being any one of storage devices S 1 . . . S N is no longer available for storage of the codewords; reallocating the codewords across the plurality of storage devices S 1 . . . S N excluding S P .
9 . The method according to claim 8 , wherein the reallocating comprises:
calculating a new allocation; generating new codewords; and distributing the new codewords among the storage devices S 1 . . . S N excluding S P .
10 . The method according to claim 5 , wherein the reallocation is carried out subject to the constraint that
(
∑
K
=
1
N
F
K
)
-
F
P
-
F
MAX
≥
R
,
where F P is the number of codewords that were allocated to storage device S P and F MAX is the number of codewords to be stored on the largest of storage devices S 1 . . . S N .
11 . The method according to claim 5 , further comprising:
determining that storage device S P , being any one of storage devices S 1 . . . 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 1 . . . 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 . An arrangement for storing data, comprising in combination:
a plurality of N storage devices S 1 . . . 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 1 . . . S N ; a fountain encoder that encodes the data into F fountain codewords, wherein
F
=
∑
K
=
1
N
F
K
with K being a counting integer; and
wherein the fountain encoder distributes the fountain codewords among the N storage devices S 1 . . . S N in approximate proportion to the storage capacity C K of each of the N storage devices S 1 . . . 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 1 . . . S N excluding S P .
14 . The apparatus according to claim 13 , wherein the storage devices S 1 . . . 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.
15 . The apparatus according to claim 13 , 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 1 . . . S N+1 in response to determining that the storage devices S N+1 is available for storage of the codewords.
16 . The apparatus according to claim 13 , wherein the reallocating comprises moving codewords from certain of the storage devices S 1 . . . S N to storage device S N+1 .
17 . The method according to claim 13 , wherein the reallocation is carried out subject to the constraint that
(
∑
K
=
1
N
+
1
F
K
)
-
F
MAX
≥
R
,
where F MAX is the number of codewords to be stored on the largest of storage devices S 1 . . . S N+1 .
18 . The apparatus according to claim 13 , further comprising:
means for determining that storage device S P , being any one of storage devices S 1 . . . 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 1 . . . S N excluding S P upon determining that storage device S P is no longer available for storage of the codewords.
19 . The apparatus according to claim 18 , wherein the reallocating comprises calculating a new allocation;
generating new codewords; and distributing the new codewords among the storage devices S 1 . . . S N excluding S P .
20 . The apparatus according to claim 18 , wherein the reallocation is carried out
(
∑
K
=
1
N
F
K
)
-
F
P
-
F
MAX
≥
R
,
subject to the constraint that where F P is the number of codewords that were allocated to storage device S P and F MAX is the number of codewords to be stored on the largest of storage devices S 1 . . . S N excluding S P .
21 . The apparatus according to claim 13 , further comprising:
means for determining that storage device S P , being any one of storage devices S 1 . . . 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 1 . . . S N excluding S P ; and if not, establishing that an error condition exists.Cited by (0)
No later patents cite this yet.
References (0)
No backward citations on record.