System for de-duplicating network coded distributed storage and related techniques
Methods for encoding a file and de-duplicating a coded packet of the file are presented. The encoding method includes: identifying a file to be stored; encoding the file to generate a plurality of coded packets; generating a hash code associated with the file; distributing the plurality of coded packets to a plurality of storage nodes; and storing the hash code associated with the file in a hash server. The de-duplicating method includes: receiving a coded packet at a storage node; retrieving a hash code, from the hash server, corresponding to the coded packet; determining whether the coded packet has been stored in the storage node based upon the hash code; in response to determination that the coded packet has being stored, discarding the coded packet; and in response to determination that the coded packet has not being stored, storing the coded packet in the storage node.
1. A method for encoding a file, the method comprising:
identifying a file to be stored;
encoding the file to generate a plurality of coded packets;
generating a hash code associated with the file, wherein the generation of the hash code includes generating a set of first vectors based on the contents of the file and generating a second vector orthogonal to a set of first vectors;
distributing the plurality of coded packets to a plurality of storage nodes; and
storing the hash code associated with the file in a hash server.
2. The method of claim 1 , further comprising:
generating and storing a public key associated with a source node in the hash server, wherein the generation of the hash code includes computing a third vector based on the second vector and a private key.
3. The method of claim 1 , wherein generating a hash code associated with the file comprises generating a hash code for a plurality of files.
4. The method of claim 1 , wherein encoding the file further comprises:
encoding the file using random linear network coding (RLNC) to generate a plurality of RLNC coded packets.
5. The method of claim 1 , wherein distributing the plurality of coded packets to a plurality of storage nodes further comprises at least one of:
distributing the plurality of coded packets in a sequential order to a plurality of storage nodes; and
distributing the plurality of coded packets in a random order to a plurality of storage nodes.
6. The method of claim 1 , wherein distributing the plurality of coded packets to a plurality of storage nodes further comprises:
distributing the plurality of coded packets to a plurality of storage nodes based upon a data transfer rate between at least one source node and at least some of the plurality of storage nodes.
7. The method of claim 1 , wherein the file comprises m linearly independent packets v={v 1 . . . v m }, wherein v is a vector in a finite 1-dimensional vector over a space with p elements p l , wherein the generation of the hash code includes generating a set of first vectors y={y 1 , . . . y m }, where
y
i
=
(
0
…
1
…
0
v
i
︷
)
and generating a second vector u=(u 1 , u 2 , . . . u m+l ), wherein u∈ p m+l is orthogonal to all vectors y={y 1 , . . . y m }.
8. The method of claim 7 , wherein the generation of the hash code includes
selecting a set of elements {α 1 , α 2 , α m+l } in p * as private keys; and
computing a third vector x=(u 1 /α 1 . . . u m+l /α m+l ).
9. An apparatus for encoding a file, the apparatus comprising:
a coded packet generator configured to:
encode the source file to generate a plurality of coded packets; and
distribute the plurality of coded packets to a plurality of storage nodes; and
a hash generator configured to:
generate a hash code associated with the source file, wherein the generation of the hash code includes generating a set of first vectors based on the contents of the file and generating a second vector orthogonal to a set of first vectors; and
store the hash code associated with the source file in a hash server.
10. The apparatus of claim 9 , further comprising:
a public key generator configured to:
generate and store a public key associated with the source node in the hash server.
11. The apparatus of claim 9 , further comprising means for identifying a source file to be stored.
12. The apparatus of claim 9 , wherein the file comprises m linearly independent packets v={v 1 . . . v m }, wherein v is a vector in a finite 1-dimensional vector over a space with p elements p l , wherein the generation of the hash code includes generating a set of first vectors y={y 1 , . . . y m }, where
y
i
=
(
0
…
1
…
0
v
i
︷
)
and generating a second vector u=(u 1 , u 2 , . . . u m+l ), wherein u∈ p m+l is orthogonal to all vectors y={y 1 , . . . y m }.
13. The apparatus method of claim 12 , wherein the generation of the hash code includes
selecting a set of elements {α 1 , α 2 , α m+l } in p * as private keys; and
computing a third vector x=(u 1 /α 1 . . . u m+l /α m+l ).
14. A method for de-duplicating a coded packet in a distributed storage system, the method comprising:
retrieving a hash code associated with a source file from a hash server, the hash code being computed by generating a set of first vectors based on the contents of the source file and generating a second vector orthogonal to a set of first vectors;
determining whether the coded packet can be deduplicated based upon finding a match using the coded packet and the hash code; and
in response to determination that the coded packet can be deduplicated, discarding the coded packet.
15. The method of claim 14 , further comprising:
retrieving a public key, from the hash server, corresponding to a source node that sent the coded packet; and
using the public key when determining whether the coded packet can be deduplicated.
16. The method of claim 14 , further comprising:
in response to determination that the coded packet cannot be deduplicated, retrieving an additional hash code to determine whether the coded packet can be deduplicated.
17. The method of claim 16 , further comprising:
retrieving an additional public key corresponding an additional source node to determine whether the coded packet can be deduplicated.
18. The method of claim 14 , wherein the coded packet is a network coded packet.
19. The method of claim 14 , wherein the coded packet is a random linear network coded (RLNC) packet.
20. A storage node for de-duplicating a coded packet in a distributed storage system, the storage node comprising:
a de-duplication processor configured to:
retrieve a hash code associated with a source file from a hash server, the hash code being computed by generating a set of first vectors based on the contents of the source file and generating a second vector orthogonal to a set of first vectors;
determine whether the coded packet can be deduplicated based upon finding a match using the coded packet and the hash code; and
in response to determination that the coded packet has being stored, discard the coded packet; and
a storage space; and
a storage processor configured to:
store and retrieve data from/to the storage space.