Method of storing a data set in a distributed storage system, distributed storage system and computer program product for use with said method
The present invention is directed to a method of storing a data set in a storage system. Said storage system comprises a plurality of storage entities. The method comprises the following steps. A step of forming at least one data set block from said data set using a fragmentation entity. A step of encoding said at least one data set block by means of an encoding entity, wherein said encoding entity provides a plurality of encoded blocks based on said at least one data set block at an output of said encoding entity. And a step of distributing said encoded blocks amongst at least two of said storage entities using a distribution entity for storage thereof by said storage entities. Said encoding entity uses a rateless erasure encoding algorithm based on rateless codes for encoding said at least one data set block. The invention is further directed to a storage system and a computer program product.
1. A method of storing a data set in a storage system, wherein the storage system comprises a plurality of storage groups representing different storage media, wherein the method comprises:
forming at least one data set block from the data set using a fragmentation entity;
encoding the at least one data set block by means of an encoding entity, wherein the encoding entity provides a plurality of encoded blocks based on the at least one data set block at an output of the encoding entity, and wherein the encoding entity uses a rateless erasure encoding algorithm based on rateless codes for encoding the at least one data set block; and
distributing the encoded blocks amongst at least two of the storage groups using a distribution entity for storage thereof by the storage groups,
wherein the encoded blocks are distributed amongst a number of g storage groups, and wherein n crit is the number of encoding blocks required for decoding the data set with a sufficiently large probability of success, wherein each of the g storage groups receives at least n g encoded blocks, with
n
g
=
n
crit
(
g
-
s
)
and
n
g
,
n
crit
,
g
,
s
∈
ℕ
⩓
g
>
0
wherein s is the maximum number of storage groups that are allowed or expected to concurrently fail, g>s, and s≧2.
2. The method of claim 1 , wherein the rateless erasure encoding algorithm uses online codes for encoding the at least one data set block.
3. The method of claim 1 , wherein each of the encoded blocks is assembled by the encoding entity by selecting a number of data set blocks of the at least one data set block, and calculating the encoded block as the exclusive or of the selected data set blocks.
4. The method of claim 3 , wherein the number of data set blocks used for assembling each of the encoded blocks is varied for each encoded block by the encoding entity.
5. A method of storing a data set in a storage system, wherein the storage system comprises a plurality of storage groups representing different storage media, wherein the method comprises:
forming at least one data set block from the data set using a fragmentation entity;
encoding the at least one data set block by means of an encoding entity, wherein the encoding entity provides a plurality of encoded blocks based on the at least one data set block at an output of the encoding entity, and wherein the encoding entity uses a rateless erasure encoding algorithm based on rateless codes for encoding the at least one data set block; and
distributing the encoded blocks amongst at least two of the storage groups using a distribution entity for storage thereof by the storage groups,
wherein the encoded blocks are distributed amongst a number of g storage groups, and wherein n crit is the number of encoding blocks required for decoding the data set with a sufficiently large probability of success, wherein each of the g storage groups receives at least n g encoded blocks, with
n
g
=
n
crit
(
g
-
s
)
and
n
g
,
n
crit
,
g
,
s
∈
ℕ
⩓
g
>
0
wherein s is the maximum number of storage groups that are allowed or expected to concurrently fail, g>s, and s≧2,
wherein each of the g storage groups receives at least n g encoded blocks, with
n
g
=
n
crit
(
g
-
s
)
and
n
g
,
n
crit
,
g
,
s
∈
ℕ
⩓
g
>
0
and r is the minimum fraction of non-defective encoded blocks in each storage group.
6. The method of claim 1 , wherein the distribution entity uses a distribution policy for providing the encoded blocks to the at least two storage groups.
7. The method of claim 1 , wherein the method further comprises:
after storage of the encoded blocks on the at least two of the storage groups, retrieving one or more encoded blocks from at least one of the storage groups; and
redistributing the retrieved encoded blocks amongst at least two further storage groups of the storage groups.
8. The method of claim 1 , wherein the at least two storage groups for receiving the encoded blocks are selected by a director entity, the director entity communicating the selected storage groups to the distribution entity.
9. A storage system for storing a data set, the storage system comprising:
a plurality of storage groups representing different storage media,
a fragmentation entity for forming at least one data set block from the data set,
an encoding entity for encoding the at least one data set block, wherein the encoding entity is arranged for assembling a plurality of encoded blocks based on the at least one data set block at an output of the encoding entity, wherein the encoding entity is arranged for using a rateless erasure encoding algorithm based on rateless codes for encoding the at least one data set block, and
a distribution entity for distributing the encoded blocks amongst at least two of the storage groups for storage thereof by the storage groups, wherein the encoded blocks are distributed amongst a number of g storage groups, and wherein n crit is the number of encoding blocks required for decoding the data set with a sufficiently large probability of success, wherein each of the g storage groups receives at least n g encoded blocks, with
n
g
=
n
crit
(
g
-
s
)
and
n
g
,
n
crit
,
g
,
s
∈
ℕ
⩓
g
>
0
wherein s is the maximum number of storage groups that are allowed or expected to concurrently fail, g>s, and s≧2.
10. The storage system of claim 9 , wherein the encoding entity is arranged for using a rateless erasure encoding algorithm based on online codes for encoding the at least one data set block.
11. The storage system of claim 9 , wherein the distribution entity is arranged for applying a distribution policy for distributing the encoded blocks.
12. The storage system of claim 9 , further comprising a director entity for selecting the at least two storage groups of the storage system for receiving the encoded blocks.
13. A non-transitory computer readable medium comprising a computer program product comprising computer readable instructions for causing a computer to perform a method of claim 1 , when the computer program product is executed on the computer.
14. A method of storing a data set in a storage system, wherein the storage system comprises a plurality of storage groups representing different storage media, wherein the method comprises:
forming at least one data set block from the data set using a fragmentation entity;
encoding the at least one data set block by means of an encoding entity, wherein the encoding entity provides a plurality of encoded blocks based on the at least one data set block at an output of the encoding entity and uses a rateless erasure encoding algorithm based on rateless codes for encoding the at least one data set block;
distributing the encoded blocks amongst at least two of the plurality of storage groups using a distribution entity for storage thereof by the storage groups, wherein the encoded blocks are distributed amongst a number of g storage groups, and wherein n crit is the number of encoding blocks required for decoding the data set with a sufficiently large probability of success, wherein each of the g storage groups receives at least n g encoded blocks, with
n
g
=
n
crit
(
g
-
s
)
and
n
g
,
n
crit
,
g
,
s
∈
ℕ
⩓
g
>
0
wherein s is the maximum number of storage groups that are allowed or expected to concurrently fail, g>s, and s≧2;
after storage of the encoded blocks on the at least two storage groups, retrieving one or more encoded blocks from at least one of the at least two storage groups; and
redistributing the retrieved encoded blocks amongst at least two further storage groups of the plurality of storage groups.
15. A method of storing a data set in a storage system, wherein the storage system comprises a plurality of storage groups representing different storage media, wherein the method comprises:
forming at least one data set block from the data set using a fragmentation entity;
encoding the at least one data set block by means of an encoding entity, wherein the encoding entity provides a plurality of encoded blocks based on the at least one data set block at an output of the encoding entity and uses a rateless erasure encoding algorithm based on rateless codes for encoding the at least one data set block;
distributing the encoded blocks amongst at least two of the plurality of storage groups using a distribution entity for storage thereof by the storage groups, wherein the encoded blocks are distributed amongst a number of g storage groups, and wherein n crit is the number of encoding blocks required for decoding the data set with a sufficiently large probability of success, wherein each of the g storage groups receives at least n g encoded blocks, with
n
g
=
n
crit
(
g
-
s
)
and
n
g
,
n
crit
,
g
,
s
∈
ℕ
⩓
g
>
0
wherein s is the maximum number of storage groups that are allowed or expected to concurrently fail, g>s, and s≧2;
wherein each of the g storage groups receives at least n g encoded blocks, with
n
g
=
n
crit
(
g
-
s
)
and
n
g
,
n
crit
,
g
,
s
∈
ℕ
⩓
g
>
0
and r is the minimum fraction of non-defective encoded blocks in each storage group;
after storage of the encoded blocks on the at least two storage groups, retrieving one or more encoded blocks from at least one of the at least two storage groups; and
redistributing the retrieved encoded blocks amongst at least two further storage groups of the plurality of storage groups.
16. The method of claim 1 , wherein at least two of the storage groups are directly connected to a single local system.
17. The method of claim 1 , wherein at least two of the storage groups reside at different geographical locations from each other and are interconnected through a telecommunications network.
18. The method of claim 1 , wherein the storage groups representing different storage media are directly connected to a local system or are interconnected through a telecommunications network.
19. The storage system of claim 9 , wherein at least two of the storage groups are directly connected to a single local system.
20. The storage system of claim 9 , wherein at least two of the storage groups reside at different geographical locations from each other and are interconnected through a telecommunications network.
21. The storage system of claim 9 , wherein the storage groups representing different storage media are directly connected to a local system or are interconnected through a telecommunications network.