冗余备份技术

在了解纠删码之前先来了解另外两种常用的冗余备份技术: raid 和 多副本

RAID

RAID 是 "Redundant Array of Independent Disk" 的缩写，中文意思是独立冗余磁盘阵列 是一种古老的磁盘冗余备份技术，也许你从未了解其中的原理，但肯定也听说过它的大名。简单地解释，就是将N台硬盘通过RAID Controller（分Hardware，Software）结合成虚拟单台大容量的硬盘使用，其特色是N台硬盘同时读取速度加快及提供容错性.

RAID 根据实现技术的不同有 RAID0~9, RAID10 等等。目前用得比较多的是 RAID 0, RAID 1, RAID 5, RAID 10.

这种技术在保护单节点的磁盘数据时还是非常有效可靠的，同时还有专用的计算机芯片支持硬件的方式实现 RAID 算法，提高效率和降低资源占用。单使用支持冗余的 RAID 算法时，单磁盘的损害由 RAID 算法可以恢复，但是 8T+ 磁盘的恢复时间可能高达数天。同时 RAID 算法在云时代的灵活性差了一点。

多副本

多副本技术就比较简单直接了，既然要冗余保护关键数据，就干脆多存几份好了，单个数据的算坏不要紧，还有备份可以使用。

这种技术在现代的软件系统中随处可见，比如 mysql 的同步/异步备份，分布式数据库中的三副本存储+一致性协议。

这种方法的优缺点也比较明显，优点是写入效率高，无需多余的计算，直接存多份即可，数据恢复也很快，从副本复制即可。缺点就是存储效率低，以前需要的磁盘容量直接 X2 或者 X3 了，成本很高。

纠删码技术

ErasureCode（纠删码）以更低成本的方式提供近似三副本的可靠性，吸引众多分布式存储／云存储的厂商和用户。可以说纠删码是云存储，尤其是现在广泛使用的对象存储的核心。纠删码（Erasure Coding，EC）是一种编码容错技术，最早是在通信行业解决部分数据在传输中的损耗问题。其基本原理就是把传输的信号分段，加入一定的校验再让各段间发生相互关联，即使在传输过程中丢失部分信号，接收端仍然能通过算法将完整的信息计算出来。在数据存储中，纠删码将数据分割成片段，把冗余数据块扩展和编码，并将其存储在不同的位置，例如磁盘、存储节点或者其他地理位置。

现在思考一个问题：现在有 2 份数据（有可能其实是一份数据被分割成了两部分），允许你做 2 的冗余（就是实际存储的使用是要存储数据的 (2+2)/2 = 2 倍），要求达到这样的效果：任意两份数据丢失，数据都能恢复。

如何来解决这个问题呢。一个简单的想法是，给两个数据都做一下备份。

将数据存储为 X1, X2, X3, X4 分别等于 A1, A2, A1, A2；这样假设数据 X1 X2 丢失了，数据就可以从 X3,X4 中恢复出来。但是这样存储存在问题：如果丢失的数据刚好是 X1, X3 呢，那么原先的数据 A1 就彻底丢失找不回来了。但是你可以使用下面的一种存储方式 X1, X2 还是不变，X3=A1+A2, X4=A1+2*A2 这样任意两份数据丢失，都可以恢复出 A1 和 A2 了。

纠删码的核心原理就是这样了，当然实际上并不会这么简单，这种算法只是一种简化。实际在计算的时候常用一种叫做 RS 码的方法，根据设置好的 m, n 值，生成一个 RS 矩阵，存储时通过 RS 矩阵计算出校验块，单任意 m 块数据损坏时，通过还存在的数据块，和 RS 的矩阵的部分的逆矩阵做运算，既可以恢复出所有的数据。具体的计算原理请参考这篇文章

总数据块 = 原始数据块 + 校验块 即 n = k + m，纠删码技术允许在数据存储中任意 m 个块损坏的场景中恢复出数据。

纠删码的实际应用和改进

根据上面的介绍，我们知道纠删码的核心参数就是 n和m 的比值，我们把这个值称为冗余度，冗余度越高，允许损坏的数据块就越多，也就越安全，同时数据存储的成本也越高。同时 k 值也很重要，这个值决定了数据分块的粒度，k值越小，数据分散度越小，故障影响面越大，重建代价也就越大；k值越大，多路数据拷贝增加的网络和磁盘负载越大，重建代价也越大。

• EMC对象存储系统ECS 12 + 4 和 10+2 冗余度分别为 1.33 、 1.2
• 阿里云盘古集群chunk存储 8+3 冗余度=1.375
• Google RS(6,3) in GFS II (Colossus)

假设我们要提供 (k, m) = (12, 4) 的冗余，冗余度为 (12+4)/12=1.33. 直接使用上面介绍的方法存在一个问题，单一个数据损坏时，就需要从 12 个数据块中传输数据进行计算，所需的网络 IO 很大。Azure 的改进是，12 块分成两个分组，每组 6块，先计算出一个 local 校验块，再在整体上算出 2个 global 校验块，这样冗余度还是 1.33, 但是单一个数据块损坏时（这是数据中心最常见的情况），IO 就从 12 缩小到了 6，降低了数据恢复的成本。

实战

在开源的对象存储项目 min.io 中使用的纠删码库是 klauspost/reedsolomon, 我们这里就用 klauspost/reedsolomon 做一个小型的工具，演示纠删码冗余备份效果。这里我们写了一个小程序，设置了 k/s 分别为 5,3 冗余度为 1.6，即任意删除 3个文件，数据始终能够恢复. 完整的程序在这里

var (
	decode = flag.Bool("decode", false, "decode or not")
	fileName = flag.String("file", "", "file to encode/decode")
	encodePath = flag.String("encode_path", "", "folder to save encode files")
)

// usage
// ./main --file=./file//testfile.txt -encode_path=./encode
// ./main --file=./file//testfile_recover.txt -encode_path=./encode --decode


func main() {
	flag.Parse()

	if fileName == nil || encodePath == nil{
		panic("need filename and encode path")
	}

	encoder, err := reedsolomon.New(5, 3)
	if err != nil{
		panic(err)
	}

	if *decode{
		shards := make([][]byte, 8)
		for i:= 0; i< 8; i ++{
			encodeFile := path.Join(*encodePath, fmt.Sprintf("encode_%d", i))
			data, err := ioutil.ReadFile(encodeFile)
			if err == nil {
				shards[i] = data
			} else if os.IsNotExist(err){
				continue
			}else {
				panic(err)
			}

		}
		err = encoder.Reconstruct(shards)
		if err != nil{
			panic(err)
		}
		fmt.Printf("reconstruct data done\n")
		f, err := os.OpenFile(*fileName, os.O_WRONLY|os.O_CREATE|os.O_TRUNC, 0644)
		if err != nil{
			panic(err)
		}
		dataSize := 0
		for i := 0; i < 5; i++{
			dataSize += len(shards[i])
		}
		err = encoder.Join(f, shards, dataSize)
		if err != nil{
			panic(err)
		}
		fmt.Printf("recover file success")
	}else{
		data, err := ioutil.ReadFile(*fileName)
		if err != nil{
			panic(err)
		}
		shards, err := encoder.Split(data)
		if err != nil{
			panic(err)
		}
		fmt.Printf("split data into 5+3=%d shards success.\n", len(shards))
		err = encoder.Encode(shards)
		if err != nil{
			panic(err)
		}
		fmt.Printf("encode data success.")
		err = os.MkdirAll(*encodePath, 0777)
		if err != nil{
			panic(err)
		}

		for i, s := range shards{
			err := ioutil.WriteFile(path.Join(*encodePath, fmt.Sprintf("encode_%d", i)), s, 0644)
			if err != nil{
				panic(err)
			}
		}
	}
}

演示

# 1. 首先我们试试存储的效果
? cat ./file//testfile.txt                                                                                                           
this
is
just
a
test
file
content
is
meaningless% 

? ./main --file=./file//testfile.txt -encode_path=./encode                 
split data into 5+3=8 shards success.
encode data success.%  

# 这里我们把文件 testfile.txt 分成了 5份，加上3份校验数据进行存储，encode 文件夹为存储的数据内容，我们假设在现实的场景中 7 份数据存储在不同的节点上
? ls ./encode           
encode_0  encode_1  encode_2  encode_3  encode_4  encode_5  encode_6  encode_7

# 2. 现在我们(因为节点的磁盘损坏)损失了其中的 任意三份数据
? rm ./encode/encode_3 ./encode/encode_5 ./encode/encode_7   

# 3. 尝试恢复数据, 可以看出，数据恢复很成功, encode file 都恢复了，而且 recover 出来的原始数据也没问题
? ./main --file=./file//testfile_recover.txt -encode_path=./encode --decode
reconstruct data done
recover file success%    

? ls ./encode
encode_0  encode_1  encode_2  encode_3  encode_4  encode_5  encode_6  encode_7

? cat ./file/testfile_recover.txt 
this
is
just
a
test
file
content
is
meaningless%


# 4. 删除更多的数据, 再次尝试恢复, 可以发现恢复失败: too few shards given
? rm ./encode/encode_1 ./encode/encode_3 ./encode/encode_5 ./encode/encode_7   
? ./main --file=./file//testfile_recover.txt -encode_path=./encode --decode    
panic: too few shards given

参考

• Shenoy_The_Pros_and_Cons_of_Erasure
• 纠删码 Erasure Code
• Dummies Guide to Erasure Coding