Method for adding redundancy data to a distributed data storage system and corresponding device
View Patent ↗The invention proposes a method and device for adding redundancy data in a distributed data storage system. Among others, the invention allows to keep impact on network resources low through the use of coordinated regenerating codes according to the invention.
1. A method of adding redundant data to a distributed data storage system, wherein said distributed data storage system stores a file of quantity M bits split in k blocks of a first predetermined quantity α bits, comprising devices connected to a network, the method comprising the following successive steps:
adding a first predetermined number t of new devices for adding of redundant data, said first predetermined number being equal to at least two, each of said first predetermined number of new devices contacts a set of any existing devices of a second predetermined number d and obtains, from each of said existing devices of said set, a second predetermined quantity β bits of first redundant data in form of at least one code word being the result of a computation applied to said first predetermined quantity α bits of redundant data stored by each of said existing devices;
obtaining, by each of said new devices, from each other new devices, a third predetermined quantity β′ bits of second redundant data in form of at least one code word being the result of a computation applied to all said first redundant data retrieved in the first step in form of at least one code word and stores third redundant data of said first predetermined quantity α bits in form of at least one code word being the result of a computation applied to all said first redundant data retrieved in the first step in form of at least one code word and all said second redundancy data in form of at least one code word;
said second predetermined quantity β bits being different from said third predetermined quantity β′ bits, M and k being whole numbers greater than or equal to two, d being superior to k, α being superior or equal to M divided by k, and β and β′ being inferior to α.
2. A method according to claim 1 , wherein said method minimizes a network data transmission bandwidth γ needed for repair such that γ=d β+(t−1)β′.
3. A method according to claim 1 , wherein said computations are linear functions.
4. A storage device for a distributed data storage system where data storage devices are connected in a network, said distributed data storage system storing a file of quantity M bits split in k blocks of a first predetermined quantity α bits, said storage device being characterized in that it comprises the following means:
means to contact a set of any existing devices of a second predetermined number d and to obtain, from each of said existing devices of said set, a second predetermined quantity β bits of first redundant data in form of at least one code word being the result of a computation applied to said first predetermined quantity α bits of redundant data stored by each of said existing devices;
means to obtain, from each other new devices, a third predetermined quantity β′ bits of second redundant data in form of at least one code word being the result of a computation applied to all said first redundant data retrieved in the first step in form of at least one code word and stores third redundant data of said first predetermined quantity α bits in form of at least one code word being the result of a computation applied to all said first redundant data retrieved in the first step in form of at least one code word and all said second redundancy data in form of at least one code word,
said second predetermined quantity β bits being different from said third predetermined quantity β′ bits, M and k being whole numbers greater than or equal to two, d being superior to k, α being equal or superior to M divided by k, and β and β′ being inferior to α.