Data storage method, device and distributed network storage system

Patent metadata

Field	Value
Publication number	US-9961142-B2
Application number	US-201213818360-A
Country	US
Kind code	B2
Filing date	Feb 15, 2012
Priority date	Jan 13, 2012
Publication date	May 1, 2018
Grant date	May 1, 2018

Abstract

A method, device and system disclosed used in storage technique, comprising: splitting a file of size M into k blocks, that is to say, each block is of size M/k; issuing the above k blocks across k different storage nodes in the distributed network storage system in a distributed manner; using the k blocks, constructing n−k independent blocks via linear coding method, and satisfying the property that any k of the n encoded blocks can be used to reconstruct the original data in the file, which means the linear coding method is a kind of Maximum-Distance Separable (MDS) code; distribute the n−k encoded blocks to the rest n−k different storage codes in the distributed network storage systems.

First claim

What is claimed is:

1. A method of storing data, comprising:
splitting a file of size M into k blocks, wherein M is a measure of an amount of data in the file and k is a positive integer and is the smallest number of nodes required to reconstruct the file and such that each block is of size M/k;
distributing the k blocks across k first storage nodes in a distributed network storage system via a first block allocation device;
constructing n-k independent blocks via a linear coding method employing a Maximum-Distance Separable (MDS) code, where n is a total number of nodes in the distributed network storage system and n>k and satisfying that any k of the n encoded blocks can reconstruct the original data in the file;
distributing the n-k encoded blocks to n-k different second storage nodes in the distributed network storage systems via a second block allocation device;
determining that nodes have failed and that no more than n-k first and second nodes have failed; and
recovering data stored in failed first and second nodes by a node recovery device through linear encoding via at least k intact nodes, wherein data in the failed first nodes is exactly regenerated with interference alignment and wherein data in the failed second nodes is regenerated maintaining a MDS code property.

2. A data storage device comprising:
a data block device which splits a file of size M into k blocks, wherein M is a measure of an amount of data in the file and k is a positive integer and is the smallest number of nodes required to reconstruct the file, where each block is of size M/k;
a first block allocation device which distributes the k blocks into k first nodes in a distributed network storage system;
a first encoding device which constructs n-k independent blocks via linear coding employing a Maximum-Distance Separable (MDS) code from the k blocks and satisfying a property that arbitrary k of the n encoded blocks can reconstruct the file;
a second block allocation device which distributes n-k encoding blocks into n-k second storage nodes wherein, n, k are both positive integers, and satisfy n>k, and n is the number of total nodes in distributed network storage system, while k is the least number of nodes needed to reconstruct the file; and
a node recovery device which determines that nodes have failed and that no more than n-k first and second nodes have failed and recovers data stored in failed first and second nodes through linear encoding via at least k intact nodes, wherein data in the failed first nodes is exactly regenerated with interference alignment and wherein data in the failed second nodes is regenerated maintaining a MDS code property.

Assignees

• Li Hui
• Huang Xianxia
• Hou Hanxu
• Zhou Tai
• Zhu Bing
• Chen Changmin
• Zhou Jingbang
• Univ Peking Shenzhen Graduate School
• Shenzhen Iptv Co Ltd

Inventors

• Li Hui
• Huang Xianxia
• Hou Hanxu
• Zhou Tai
• Zhu Bing
• Chen Changmin
• Zhou Jingbang

Classifications

• H03M13/033

  Theoretical methods to calculate these checking codes · CPC title

• H04L67/1097 Primary

  for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS] · CPC title

• G06F11/1092

  Rebuilding, e.g. when physically replacing a failing disk · CPC title

• H04L67/1095

  Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes · CPC title

• H03M13/1515

  Reed-Solomon codes · CPC title