Distributed storage method, apparatus, and system for reducing a data loss that may result from a single-point failure

• US 8,862,847 B2
• Filed: 12/18/2013
• Issued: 10/14/2014
• Est. Priority Date: 02/08/2013
• Status: Active Grant

• Current Assignee: Huawei Technologies Co., Ltd. (Huawei Investment & Holding Co., Ltd.)
• Original Assignee: Huawei Technologies Co., Ltd. (Huawei Investment & Holding Co., Ltd.)
• Inventors: Feng, Bin, Huang, Cheng, Gong, Xuewen
• Primary Examiner(s): ELMORE, STEPHEN C
• Application Number:
  US14/132,863
• Publication Number:
  US 20140229696A1
• Time in Patent Office: 300 Days
• Field of Search: 711/162, 711/112, 711/114, 714/6.2, 714/6.22, 714/6.24, 714/6.3, 714/6.32
• US Class Current: 711/162
• CPC Class Codes: G06F 3/06 Digital input from, or digital output to, record carriers , e.g. RAID, emulated record carriers or networked record carriers
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0647 Migration mechanisms
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: H04L 67/1097 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]

Abstract

A distributed data storage method, apparatus, and system for reducing a data loss that may result from a single-point failure. The method includes: splitting a data file to generate K data slices, splitting each data slice of the K data slices to generate M data blocks for each data slice, and performing check coding on the M data blocks by using a redundancy algorithm to generate N check blocks; determining, by using a random algorithm, a first physical storage node corresponding to one block of the M data blocks and the N check blocks, and determining at least M+1 different physical storage nodes based on the determined first physical storage node and according to a first rule-based sorting manner; and storing at least M+1 blocks of the M data blocks and the N check blocks onto the at least M+1 different storage nodes, where K, M, and N are integers.

Claims

1. A distributed storage method, comprising:

splitting, by a processor, a data file to generate K data slices;

splitting, by the processor, each data slice of the K data slices to generate M data blocks for each data slice;

performing, by the processor, check coding on the M data blocks by using a redundancy algorithm to generate N check blocks;

determining, by the processor, by using a random algorithm, a first physical storage node corresponding to one data block or one check block of the M data blocks or the N check blocks;

determining, by the processor, at least M+1 different physical storage nodes based on the first physical storage node and according to a first sorting manner that conforms to a preset rule; and

separately storing, by the processor, at least M+1 blocks of the M data blocks and the N check blocks onto the at least M+1 different physical storage nodes, wherein K, M, and N are positive integers.

2. The distributed storage method according to claim 1, wherein determining, by the processor, the first physical storage node corresponding to one data block or one check block of the M data blocks or the N check blocks comprises:

performing, by the processor, a hash calculation on an identifier of one data block or check block of the M data blocks or the N check blocks to generate a key value; and

determining, by the processor, according to the key value, a physical storage node corresponding to one data block or check block of the M data blocks or the N check blocks, and using the physical storage node as the first physical storage node.

3. The distributed storage method according to claim 1, wherein determining, by the processor, the first physical storage node corresponding to one data block or one check block of the M data blocks or the N check blocks comprises:

performing, by the processor, a hash calculation on an identifier of the data slice that is split into the M data blocks, so as to generate a key value; and

determining, by the processor, according to the key value, a physical storage node corresponding to one data block or check block of the M data blocks or the N check blocks, and using the physical storage node as the first physical storage node.

4. The distributed storage method according to claim 1, wherein determining, by the processor, the at least M+1 different physical storage nodes based on the first physical storage node and according to the first sorting manner that conforms to the preset rule comprises determining, by the processor, M+N different physical storage nodes based on the first physical storage node and according to the first sorting manner, and wherein storing, by the processor, the at least M+1 blocks of the M data blocks and the N check blocks onto the at least M+1 different physical storage nodes comprises storing, by the processor, the M data blocks and the N check blocks onto the M+N different physical storage nodes.

5. The distributed storage method according to claim 1, wherein determining, by the processor, at least M+1 different physical storage nodes based on the first physical storage node and according to the first sorting manner that conforms to the preset rule comprises either:

mapping, by the processor, the first physical storage node to one block of the at least M+1 blocks; and

any one of following steps;

determining, by the processor, based on a position of the first physical storage node and according to the first sorting manner, physical storage nodes corresponding to other at least M blocks of the at least M+1 blocks, wherein the M+1 different physical storage nodes comprises the first physical storage node; and

determining, by the processor, based on the position of the first physical storage node and according to the first sorting manner, physical storage nodes corresponding to the at least M+1 blocks, wherein the M+1 different physical storage nodes do not comprise the first physical storage node.

6. The distributed storage method according to claim 1, wherein the different physical storage nodes are hard disks, and the number of the hard disks is greater than or equal to M+1;

or wherein the different physical storage nodes are servers, and the number of the servers is greater than or equal to M+1;

or wherein the different physical storage nodes are racks, and the number of the racks is greater than or equal to M+1.

7. The distributed storage method according to claim 1, further comprising restoring, by the processor, data on the faulty physical storage node of the at least M+1 different physical storage nodes onto a hot standby storage node in a distributed storage system on which the physical storage node is located when one of the at least M+1 different physical storage nodes that store at least M+1 blocks of the M data blocks and the N check blocks is faulty.

8. The distributed storage method according to claim 1, further comprising:

sequentially migrating, by the processor, a Lth block of the M data blocks and the N check blocks that are sorted according to the first sorting manner and blocks prior to the Lth block to adjacent physical storage nodes along a first direction when a physical storage node of an Lth block of the M data blocks and the N check blocks that are sorted according to the first sorting manner and stored on the at least M+1 different physical storage nodes is faulty and when L is not greater than (M+N)/2, wherein the first direction is opposite to a direction of a sequence in the first sorting manner, and sequentially migrating, by the processor, the Lth block of the M data blocks and the N check blocks that are sorted according to the first sorting manner and blocks after the Lth block to adjacent physical storage nodes along a second direction when L is greater than (M+N)/2, wherein the second direction is the same as the direction of the sequence in the first sorting manner;

or

sequentially migrating, by the processor, the Lth block of the M data blocks and the N check blocks that are sorted according to the first sorting manner and blocks prior to the Lth block to adjacent physical storage nodes along a first direction when a physical storage node of an Lth block of the M data blocks and the N check blocks that are sorted according to the first sorting manner and stored on the at least M+1 different physical storage nodes is faulty;

or

sequentially migrating, by the processor, the Lth block of the M data blocks and the N check blocks that are sorted according to the first sorting manner and blocks after the Lth block to adjacent physical storage nodes along a second direction when a physical storage node of an Lth block of the M data blocks and the N check blocks that are sorted according to the first sorting manner and stored on the at least M+1 different physical storage nodes is faulty.

9. The distributed storage method according to claim 1, further comprising:

migrating, by the processor, a Pth block of the M data blocks and the N check blocks that are sorted according to the first sorting manner to the new physical storage node when that a new physical storage node is added after a physical storage node of a Pth block of the M data blocks and the N check blocks that are sorted according to the first sorting manner and stored on the at least M+1 different physical storage nodes and when P is not greater than (M+N)/2, sequentially migrating, by the processor, blocks prior to the Pth block of the M data blocks and the N check blocks that are sorted according to the first sorting manner to adjacent physical storage nodes along a first direction, wherein the first direction is the same as a direction of a sequence in the first sorting manner, migrating, by the processor, a (P+1)th block of the M data blocks and the N check blocks that are sorted according to the first sorting manner to the new physical storage node when P is greater than (M+N)/2, and sequentially migrating, by the processor, blocks after the (P+1)th block of the M data blocks and the N check blocks that are sorted according to the first sorting manner to adjacent physical storage nodes along a second direction, wherein the second direction is opposite to the direction of the sequence in the first sorting manner, wherein P is an integer;

or

migrating, by the processor, the Pth block of the M data blocks and the N check blocks that are sorted according to the first sorting manner to the new physical storage node when a new physical storage node is added after a physical storage node of a Pth block of the M data blocks and the N check blocks that are sorted according to the first sorting manner and stored on the at least M+1 different physical storage nodes, and sequentially migrating, by the processor, blocks prior to the Pth block of the M data blocks and the N check blocks that are sorted according to the first sorting manner to adjacent physical storage nodes along a first direction;

or

migrating, by the processor, the (P+1)th block of the M data blocks and the N check blocks that are sorted according to the first sorting manner to the new physical storage node when a new physical storage node is added after a physical storage node on which a Pth block of the M data blocks and the N check blocks that are sorted according to the first sorting manner and stored on the at least M+1 different physical storage nodes is located, and sequentially migrating, by the processor, blocks after the (P+1)th block of the M data blocks and the N check blocks that are sorted according to the first sorting manner to adjacent physical storage nodes along a second direction.

10. The distributed storage method according to claim 1, further comprising:

determining, by the processor, by using the random algorithm, the first physical storage node corresponding to one data block or check block of the M data blocks or the N check blocks when the data file needs to be read;

determining, by the processor, at least M different physical storage nodes based on the determined first physical storage node and according to the first sorting manner;

reading, by the processor, at least M blocks from the at least M different physical storage nodes, wherein the read M blocks comprise the M data blocks or comprise some data blocks of the M data blocks and some check blocks of the N check blocks;

performing, by the processor, decoding and a reverse check on the at least M blocks to generate M decoded data blocks; and

combining, by the processor, the M decoded data blocks to generate the data file.

11. The distributed storage method according to claim 1, wherein the data file is acquired from the outside of the distributed storage system, or wherein the data file is acquired from some physical storage nodes of the distributed storage system.

12. The distributed storage method according to claim 1, wherein the redundancy algorithm is an erasure coding algorithm, and wherein the random algorithm is a distributed hash table algorithm.

13. The distributed storage method according to claim 1, wherein the different physical storage nodes are different physical storage nodes on the distributed storage system, wherein each physical storage node of the different physical storage nodes comprises multiple virtual storage nodes, and wherein virtual storage nodes with consecutive serial numbers are deployed on the different physical storage nodes according to a second sorting manner that conforms to a preset rule, wherein determining, by the processor, by using a random algorithm, the first physical storage node corresponding to one data block or one check block of the M data blocks or the N check blocks, and determining, by the processor, at least M+1 different physical storage nodes based on the first physical storage node and according to the first sorting manner that conforms to a preset rule comprises:

determining, by the processor, by using the random algorithm, a serial number of a first virtual storage node corresponding to one block of the M data blocks and the N check blocks; and

determining, by the processor, the serial numbers of at least M+1 virtual storage nodes based on the serial number of the first virtual storage node and according to the first sorting manner, and wherein separately storing at least M+1 blocks of the M data blocks and the N check blocks onto the at least M+1 different physical storage nodes comprises storing the at least M+1 blocks of the M data blocks and the N check blocks onto virtual storage nodes corresponding to the serial numbers of the at least M+1 virtual storage nodes.

14. The distributed storage method according to claim 13, wherein the first sorting manner or the second sorting manner refers to a method of sequence sorting at a fixed interval.

15. A distributed storage system, comprising:

a client;

multiple physical storage nodes; and

a distributed storage apparatus, wherein the distributed storage apparatus stores or reads a data file of a user onto or from the multiple physical storage nodes according to a storage or read request sent by the user through the client, and wherein the distributed storage apparatus comprises;

a generating module configured to;

split a data file to generate K data slices;

split each data slice of the K data slices to generate M data blocks for each data slice; and

perform check coding on the M data blocks by using a redundancy algorithm to generate N check blocks;

a determining module configured to;

determine, by using a random algorithm, a first physical storage node corresponding to one data block or one check block of the M data blocks or the N check blocks; and

determine at least M+1 different physical storage nodes based on the first physical storage node and according to a first sorting manner that conforms to a preset rule; and

a storing module configured to store at least M+1 blocks of the M data blocks and the N check blocks onto the at least M+1 different physical storage nodes, wherein K, M, and N are positive integers.

16. The distributed storage system according to claim 15, wherein the determining module is configured to:

perform a hash calculation on an identifier of one data block or check block of the M data blocks or the N check blocks to generate a key value;

determine, according to the key value, a physical storage node corresponding to one data block or check block of the M data blocks or the N check blocks; and

use the physical storage node as the first physical storage node.

17. A distributed storage apparatus, a processor and a memory coupled to the processor, wherein the processor is configured to:

split a data file to generate K data slices;

split each data slice of the K data slices to generate M data blocks for each data slice;

perform check coding on the M data blocks by using a redundancy algorithm to generate N check blocks;

determine by using a random algorithm, a first physical storage node corresponding to one data block or one check block of the M data blocks or the N check blocks;

determine at least M+1 different physical storage nodes based on the first physical storage node and according to a first sorting manner that conforms to a preset rule; and

separately store at least M+1 blocks of the M data blocks and the N check blocks onto the at least M+1 different physical storage nodes, wherein K, M, and N are positive integers.

18. The distributed storage apparatus according to claim 17, wherein determining the first physical storage node corresponding to one data block or one check block of the M data blocks or the N check blocks comprises:

performing a hash calculation on an identifier of one data block or check block of the M data blocks or the N check blocks to generate a key value; and

determining according to the key value, a physical storage node corresponding to one data block or check block of the M data blocks or the N check blocks, and using the physical storage node as the first physical storage node.

19. The distributed storage apparatus according to claim 17, wherein determining the first physical storage node corresponding to one data block or one check block of the M data blocks or the N check blocks comprises:

performing a hash calculation on an identifier of the data slice that is split into the M data blocks, so as to generate a key value; and

determining according to the key value, a physical storage node corresponding to one data block or check block of the M data blocks or the N check blocks, and using the physical storage node as the first physical storage node.

20. The distributed storage apparatus according to claim 17, wherein determining the at least M+1 different physical storage nodes based on the first physical storage node and according to the first sorting manner that conforms to the preset rule comprises determining M+N different physical storage nodes based on the first physical storage node and according to the first sorting manner, and wherein store the at least M+1 blocks of the M data blocks and the N check blocks onto the at least M+1 different physical storage nodes comprises store the M data blocks and the N check blocks onto the M+N different physical storage nodes.

21. The distributed storage apparatus according to claim 17, wherein determining at least M+1 different physical storage nodes based on the first physical storage node and according to the first sorting manner that conforms to the preset rule comprises either:

mapping the first physical storage node to one block of the at least M+1 blocks; and

any one of following steps;

determining based on a position of the first physical storage node and according to the first sorting manner, physical storage nodes corresponding to other at least M blocks of the at least M+1 blocks, wherein the M+1 different physical storage nodes comprises the first physical storage node; and

determining based on the position of the first physical storage node and according to the first sorting manner, physical storage nodes corresponding to the at least M+1 blocks, wherein the M+1 different physical storage nodes do not comprise the first physical storage node.

22. The distributed storage apparatus according to claim 17, wherein the different physical storage nodes are hard disks, and the number of the hard disks is greater than or equal to M+1;

or wherein the different physical storage nodes are servers, and the number of the servers is greater than or equal to M+1;

or wherein the different physical storage nodes are racks, and the number of the racks is greater than or equal to M+1.

23. The distributed storage apparatus according to claim 17, wherein the processor is further configured to:

restore data on the faulty physical storage node of the at least M+1 different physical storage nodes onto a hot standby storage node in a distributed storage system on which the physical storage node is located when one of the at least M+1 different physical storage nodes that store at least M+1 blocks of the M data blocks and the N check blocks is faulty.

24. The distributed storage apparatus according to claim 17, wherein the processor is configured to:

sequentially migrate a Lth block of the M data blocks and the N check blocks that are sorted according to the first sorting manner and blocks prior to the Lth block to adjacent physical storage nodes along a first direction when a physical storage node of an Lth block of the M data blocks and the N check blocks that are sorted according to the first sorting manner and stored on the at least M+1 different physical storage nodes is faulty and when L is not greater than (M+N)/2, wherein the first direction is opposite to a direction of a sequence in the first sorting manner, and sequentially migrate the Lth block of the M data blocks and the N check blocks that are sorted according to the first sorting manner and blocks after the Lth block to adjacent physical storage nodes along a second direction when L is greater than (M+N)/2, wherein the second direction is the same as the direction of the sequence in the first sorting manner;

or

sequentially migrate the Lth block of the M data blocks and the N check blocks that are sorted according to the first sorting manner and blocks prior to the Lth block to adjacent physical storage nodes along a first direction when a physical storage node of an Lth block of the M data blocks and the N check blocks that are sorted according to the first sorting manner and stored on the at least M+1 different physical storage nodes is faulty;

or

sequentially migrate the Lth block of the M data blocks and the N check blocks that are sorted according to the first sorting manner and blocks after the Lth block to adjacent physical storage nodes along a second direction when a physical storage node of an Lth block of the M data blocks and the N check blocks that are sorted according to the first sorting manner and stored on the at least M+1 different physical storage nodes is faulty.

25. The distributed storage apparatus according to claim 17, wherein the processor is further configured to:

migrate a Pth block of the M data blocks and the N check blocks that are sorted according to the first sorting manner to the new physical storage node when that a new physical storage node is added after a physical storage node of a Pth block of the M data blocks and the N check blocks that are sorted according to the first sorting manner and stored on the at least M+1 different physical storage nodes and when P is not greater than (M+N)/2, sequentially migrate blocks prior to the Pth block of the M data blocks and the N check blocks that are sorted according to the first sorting manner to adjacent physical storage nodes along a first direction, wherein the first direction is the same as a direction of a sequence in the first sorting manner, migrate a (P+1)th block of the M data blocks and the N check blocks that are sorted according to the first sorting manner to the new physical storage node when P is greater than (M+N)/2, and sequentially migrate blocks after the (P+1)th block of the M data blocks and the N check blocks that are sorted according to the first sorting manner to adjacent physical storage nodes along a second direction, wherein the second direction is opposite to the direction of the sequence in the first sorting manner, wherein P is an integer;

or

migrate the Pth block of the M data blocks and the N check blocks that are sorted according to the first sorting manner to the new physical storage node when a new physical storage node is added after a physical storage node of a Pth block of the M data blocks and the N check blocks that are sorted according to the first sorting manner and stored on the at least M+1 different physical storage nodes, and sequentially migrate blocks prior to the Pth block of the M data blocks and the N check blocks that are sorted according to the first sorting manner to adjacent physical storage nodes along a first direction;

or

migrate the (P+1)th block of the M data blocks and the N check blocks that are sorted according to the first sorting manner to the new physical storage node when a new physical storage node is added after a physical storage node on which a Pth block of the M data blocks and the N check blocks that are sorted according to the first sorting manner and stored on the at least M+1 different physical storage nodes is located, and sequentially migrate blocks after the (P+1)th block of the M data blocks and the N check blocks that are sorted according to the first sorting manner to adjacent physical storage nodes along a second direction.

26. The distributed storage apparatus according to claim 17, wherein the processor is further configured to:

determine by using the random algorithm, the first physical storage node corresponding to one data block or check block of the M data blocks or the N check blocks when the data file needs to be read;

determine at least M different physical storage nodes based on the determined first physical storage node and according to the first sorting manner;

read at least M blocks from the at least M different physical storage nodes, wherein the read M blocks comprise the M data blocks or comprise some data blocks of the M data blocks and some check blocks of the N check blocks;

perform decoding and a reverse check on the at least M blocks to generate M decoded data blocks; and

combine the M decoded data blocks to generate the data file.

27. The distributed storage apparatus according to claim 17, wherein the data file is acquired from the outside of the distributed storage system, or wherein the data file is acquired from some physical storage nodes of the distributed storage system.

28. The distributed storage apparatus according to claim 17, wherein the redundancy algorithm is an erasure coding algorithm, and wherein the random algorithm is a distributed hash table algorithm.

29. The distributed storage apparatus according to claim 17, wherein the different physical storage nodes are different physical storage nodes on the distributed storage system, wherein each physical storage node of the different physical storage nodes comprises multiple virtual storage nodes, and wherein virtual storage nodes with consecutive serial numbers are deployed on the different physical storage nodes according to a second sorting manner that conforms to a preset rule, wherein determine by using a random algorithm, the first physical storage node corresponding to one data block or one check block of the M data blocks or the N check blocks, and determining at least M+1 different physical storage nodes based on the first physical storage node and according to the first sorting manner that conforms to a preset rule comprises:

determining by using the random algorithm, a serial number of a first virtual storage node corresponding to one block of the M data blocks and the N check blocks; and

determining the serial numbers of at least M+1 virtual storage nodes based on the serial number of the first virtual storage node and according to the first sorting manner, and wherein separately storing at least M+1 blocks of the M data blocks and the N check blocks onto the at least M+1 different physical storage nodes comprises storing the at least M+1 blocks of the M data blocks and the N check blocks onto virtual storage nodes corresponding to the serial numbers of the at least M+1 virtual storage nodes.

30. The distributed storage apparatus according to claim 29, wherein the first sorting manner or the second sorting manner refers to a method of sequence sorting at a fixed interval.

31. A non-transitory computer-readable medium having computer executable instructions for performing an information publishing method comprising:

Splitting a data file to generate K data slices;

Splitting each data slice of the K data slices to generate M data blocks for each data slice;

performing check coding on the M data blocks by using a redundancy algorithm to generate N check blocks;

determining, by using a random algorithm, a first physical storage node corresponding to one data block or one check block of the M data blocks or the N check blocks;

determining at least M+1 different physical storage nodes based on the first physical storage node and according to a first sorting manner that conforms to a preset rule; and

separately storing at least M+1 blocks of the M data blocks and the N check blocks onto the at least M+1 different physical storage nodes, wherein K, M, and N are positive integers.