METHOD OF DATA STORING AND MAINTENANCE IN A DISTRIBUTED DATA STORAGE SYSTEM AND CORRESPONDING DEVICE

• US 20150089283A1
• Filed: 04/24/2013
• Published: 03/26/2015
• Est. Priority Date: 05/03/2012
• Status: Abandoned Application

• Current Assignee: Thomson Licensing SAS (Vantiva SA)
• Original Assignee: Thomson Licensing (Vantiva SA)
• Inventors: Kermarrec, Anne-Marie, Straub, Gilles, Van Kempen, Alexandre, Le Merrer, Erwan
• Application Number:
  US14/398,502
• Publication Number:
  US 20150089283A1
• Time in Patent Office: Days
• US Class Current: 714/6.32
• CPC Class Codes: G06F 11/1088 Reconstruction on already foreseen single or plurality of spare disks
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 16/182 Distributed file systems
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0665 at area level, e.g. provisioning of virtual or logical volumes
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

The present invention generally relates to distributed data storage systems. In particular, the present invention is related to a method of data storing in a distributed data storage system that comprises a clustering of data blocks and the use of random linear combinations of data blocks that makes the distributed data store system efficient in terms of storage space needed and inter-device communication costs, both for the storage method, as for the associated repair method.

Claims

1. A method of storing data files in a distributed data storage system comprising storage devices interconnected in a network, wherein said method comprises the following steps, executed for each data file of said data files, to store in said distributed data storage system:

splitting said data file in k data blocks, and creation of at least n encoded data blocks from said k data blocks through random linear combination of said k data blocks;

storing said at least n encoded data blocks by spreading said at least n encoded data blocks of said data file over at least n storage devices that are part of a same storage device cluster, each cluster comprising a distinct set of storage devices, said at least n encoded data blocks of said data file being distributed over said at least n storage devices of a storage device cluster so that each storage device cluster stores encoded data blocks from at least two different data files, and that each of said storage devices of a storage device cluster stores encoded data blocks from at least two different data files.

2. A method of repairing a failed storage device in a distributed data storage system where data is stored according to claim 1 and a data file stored is split in k data blocks, wherein said method comprises:

adding a replacement storage device to a storage device cluster to which said failed storage device belongs;

receiving, by said replacement storage device, from any of k+1 remaining storage devices in said storage device cluster, k+1 new random linear combinations, generated from two encoded data blocks from two different files X and Y stored by each of said k+1 remaining storage devices;

combining said new random linear combinations received between them to obtain two linear combinations, in which two blocks are obtained, one only related to X and another only related to Y, using an algebraic operation;

storing said two linear combinations, obtained in the combining step, in the said replacement storage device.

3. The method according to claim 2, wherein said method of repairing comprises reintegrating, into said storage device cluster, of a failed storage device that that returns to said distributed data system.

5. A device for management of repairing a failed storage device in a distributed data storage system where data is stored according to claim 1 and a data file stored is split in k data blocks, wherein said device comprises:

a replacer for adding a replacement storage device to a storage device cluster to which said failed storage device belongs;

a distributor for distributing to said replacement storage device, from any of k+1 remaining storage devices in said storage device cluster, k+1 new random linear combinations, generated from two encoded data blocks from two different data files X and Y stored by each of said k+1 remaining storage devices;

a combiner for combining said new random linear combinations received between them to obtain two linear combinations, in which two blocks are obtained, one only related to X and another only related to Y, using an algebraic operation; and

a data writer for storing said two linear combinations, obtained by the combiner, in said replacement storage device.

4. A device for management of storing of data files in a distributed data storage system comprising storage devices interconnected in a network, wherein the device comprises:

a data splitter for splitting the data file in k data blocks, and for creation of at least n encoded data blocks from these said k data blocks through random linear combination of said k data blocks;

a storage distributor for storing said at least n encoded data blocks by spreading said at least n encoded data blocks of said data file over at least n storage devices that are part of a same storage device cluster, each cluster comprising a distinct set of storage devices, said at least n encoded data blocks of said data file being distributed over the at least n storage devices of a storage device cluster so that each storage device cluster stores encoded data blocks from at least two different data files, and that each of said storage devices of a storage device cluster stores encoded data blocks from at least two different data files.