Network storage system fault-tolerant encoding technology progress (1)

Summary: professional large disk storage systems are developed to contain multiple disks, large array system.

As the system disk number continues to increase, by the disk failure due to the possibility of data loss. For the storage system in some disk failure data loss problem, industry recognized a better solution is to use a redundant fault tolerant encoding technology for disk fault tolerance. In engineering practice, is currently widely used in coding mostly confined to double fault tolerant array codes. As the system scale further intensify, 3-tolerant even more fault-tolerant encoding method has attracted attention from researchers. The next five to 10 years, for 3-tolerant or more fault-tolerant encoding methods will become the new hot spot.

1 storage fault-tolerant encoding indexes

In the last 20 years computer, along with the technologies, the development of mass storage system is also very fast.

Currently, the ordinary PC storage capacity has reached the terabit level, compared with 20 years ago 20 MB storage capacity increase 10 000 times.

In addition to traditional disk drives, type of solid state storage (SSD) for storage also has to the market.

Although a single storage capacity rapidly, but still miss the people on the storage capacity requirements increase speed.

With the large computer system from "calculated" toward "information processing", as well as the amount of explosive growth, mass storage system of increasing demand.

Mass storage system is essentially a single will be a lot of storage devices (following the disk as an example), via the system's interface, consolidation is connected to a virtual capacity huge single storage, disk array.

As the number of disks in the array increases the reliability of the system is down.

Industry generally use average data lost time (MTTDL) to measure the reliability of the array.

Set a single disk failure time MTTFdisk average, then for contains n disks non-redundant array, its estimated MTTDL can simple: MTTDL = MTTFdisk/n.

Thus, when n is large, the reliability of the entire system will be reduced proportionally. This is a massive system speaking is unacceptable. Use redundant data encoding to improve system reliability is recognized as a solution to this problem in a good way. By skilfully m block standard size of the data on the disk, add some redundancy check information, encoded deposited n block on the disk, make the system meet: for any k block disk failure, to pass through other n-k block does not fail data to decode in the tray, then called the entire recovery system is k-tolerant, or that k is the number of fault-tolerant system.

Analysis shows [1], a system for k-tolerant, you can approximate estimated as:

Thus, in large scale systems, fault-tolerant can say is another description of the system reliability.

Market in General disk MTTFdisk 105, system time to repair MTTR generally 10 or so. According to (1)-you can see that when the system disk is 103-104, fault tolerant or 2 3 fault-tolerant encoding is basically can meet the requirement of fault-tolerant storage system.

System to increase fault tolerance and redundancy is added, the system of additional cost will be higher.

Thus the number with the same fault-tolerant, people often pursue smaller redundant, i.e. (n-m)/n value, where n is the number, the system disk to store the user data m the number of disks. According to the coding theory of Singleton territories, k-tolerant system minimum redundancy to: k/n. Reach this minimum value of the encoding method called MDS codes. At present most storage encoding research focuses on the structure of the MDS under different parameters.

In addition to the index, any computer system speed and efficiency are important indicators need to be considered.

Here we do not discuss how to effectively handle multiple parallel data read from the disk (that's another one larger project), which focuses on the study due to redundant coding additional computational overhead. For even a same encoding methods, decoding algorithm may calculate differences in efficiency. As in a computer system, the final coding operations are reflected to some binary arithmetic, so researchers generally use encoding needs of the total number of binary XOR to measure because of the additional redundancy of the system to calculate the coding overhead. For a random access storage system, random small block information write performance is particularly important. Encoding operation in a single unit in which average XOR times can be used to measure the metrics that we refer to it as code complexity of updates.

Integrated storage system discussed above, fault-tolerant encoding problems boil down to search on the following indicators for optimized coding method

System meets the needs of fault-tolerant performance, fault-tolerant digital systems for k.

The system has a smaller (or optimal) redundancy.

The system has a smaller (or optimal) encoding/update complexity.

2 linear encoding

For single-fault-tolerant system, simple parity can make the above three indicator reaching optimal.

Classic systems are used by this method. However for k is greater than 1, the problem was not so simple. From communication coding theory of rich fruit, two more representative encoding method was chosen and used for fault-tolerant storage, they are binary linear codes and RS code.

Multidimensional array code 2.1

As shown in Figure 1 is a two-dimensional array of coding and validation matrix.

Two-dimensional array codes is a natural extension of parity, the figure 1 easy to see that it is a double fault. Two-dimensional array codes maintained a single fault-tolerant when parity codes of optimal coding complexity, but two-dimensional array code redundancy is no longer the best.

Two-dimensional array code is also very easy to promote k-dimension array.

And easy to get encoded k-tolerant characteristics. But as k increases, redundancy will become more and more large [2-3].

2.2 Full code

As shown in Figure 2 is FULL-2 yards.

FULL-2 code can be seen as a two-dimensional array code promotion.

FULL code remains the best encoding complexity and redundancy than array code much better.

Unfortunately, when the k is greater than 3, FULL-k code is no longer fault tolerant k [4].

[1] [2] [3] [4]