US 11,531,593 B2Granted

Data encoding, decoding and recovering method for a distributed storage system

AssigneeHere Data Technology

InventorsBin Hao, Jian Zhu, Jingyao Zhang

Life of this patent

Estimating the term…

Loading patent…

Abstract

Disclosed is a data encoding, decoding and recovering method of a distributed storage system for data protection of the distributed storage system. The methods include using local recoverable coding, and calling Reed-Solomon coding on data blocks obtained from divisions of file segments based on coding parameters to generate global coding blocks, locally coding to data blocks and global coding blocks respectively to generate local coding blocks. The methods can also include computing decoded block indices and recovered block indices according to current node state, reading block data of assistant node, and implementing decoding of file segments and recovery of failed blocks. The coding method of the present disclosure can reduce the amount of data that needs to be transmitted when recovering a failed node by increasing local coding blocks and speed up the node recovery speed.

Claims12

Dependent claims

A method of reading data stored in a distributed storage system having a plurality of storage nodes each configured to store data, wherein the data has been written to the distributed storage system by adopting a method of writing data to the distributed storage system, the method of writing data comprising:

an initializing step configured for setting coding parameters, including:
collecting number k of original data blocks, number m of global coding blocks, repair degree r, spacial setting w of algebraic operation field GF, i.e. operation field GF2w, and
an encoding step configured for:
dividing every file segment into k data blocks, calling RS(k, m+1) coding to k original data blocks, generating m global coding blocks;
for k data blocks, performing XOR operations on r data blocks which are taken out in sequence from k data blocks to totally generate ┌k/r┐ local coding blocks;
and for m global coding blocks, performing XOR operations on r coding blocks which are taken out in sequence from m global coding blocks to totally generate ┌m/r┐ local coding blocks, the method of reading the data comprises:
collecting states of storage nodes, reading states of n storage nodes stored in every data block and coding block which have been encoded, and acquiring an online-block index list and a failed-block index list;
acquiring a decodable state based on the states of storage nodes;
determining position of data to be read during decoding according to different decodable states to define a decoding index list;
reading data blocks or coding blocks needed by decoding according to the decoding index list;
and
decoding file segments based on the decodable state, indices of decoded blocks, and their corresponding block data which have already been read.

9 more elements

A method of data recovery for a distributed storage system for data recovery of storage node failures in the distributed storage system, the distributed storage system having a plurality of storage nodes each configured to store data, wherein the data has been written to the distributed storage system by adopting a method of writing data to the distributed storage system, the method of writing data comprising:

an initializing step configured for setting coding parameters, including:
collecting number k of original data blocks, number m of global coding blocks, repair degree r, spacial setting w of algebraic operation field GF, i.e. operation field GF2w, and
an encoding step configured for:
dividing every file segment into k data blocks, calling RS(k, m+1) coding to k original data blocks, generating m global coding blocks;
for k data blocks, performing XOR operations on r data blocks which are taken out in sequence from k data blocks to totally generate ┌k/r┐ local coding blocks;
and for m global coding blocks, performing XOR operations on r coding blocks which are taken out in sequence from m global coding blocks to totally generate ┌m/r┐ local coding blocks, the method of data recovery comprises:
collecting states of storage nodes, reading states of n storage nodes stored in every data block and coding block which have been encoded, and acquiring an online-block index list and a failed-block index list;
acquiring a recoverable state based on the states of storage nodes;
obtaining a repairing block index list that should be read and is used for recovering failed blocks according to the recoverable state;
reading data blocks or coding blocks of storage nodes corresponding to indices of repaired blocks according to the repairing block index list;
and
recovering failed blocks based on the recoverable state, indices of repairing blocks, and their data of corresponding blocks.

9 more elements

Dependencies are inferred from the claim text.

Facts

Application: 16/973,027Filed 3 Sep 2018
Published: US 2021/0271557 A12 Sep 2021
Granted: 20 Dec 2022
Term ends: Not estimatedThe source records don’t support an estimate.

Classification6 codes

G06F 11/1448
Point-in-time backing up or restoration of persistent data: management of the data involved in backup or backup restore
G06F 11/1464
Management of the backup or restore process: for networked environments
G06F 11/1469
Management of the backup or restore process: backup restoration techniques
G06F 11/2028
Failover techniques: eliminating a faulty processor or activating a spare