前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >有趣的纠删码(erasure code)

有趣的纠删码(erasure code)

原创
作者头像
王磊-字节跳动
发布2021-05-30 20:07:18
10.4K0
发布2021-05-30 20:07:18
举报
文章被收录于专栏:01ZOO01ZOO

冗余备份技术

在了解纠删码之前先来了解另外两种常用的冗余备份技术: 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个文件,数据始终能够恢复. 完整的程序在这里

代码语言:txt
复制
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)
			}
		}
	}
}

演示

代码语言:txt
复制
# 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

参考

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 冗余备份技术
    • RAID
      • 多副本
      • 纠删码技术
      • 纠删码的实际应用和改进
      • 实战
        • 演示
        • 参考
        相关产品与服务
        对象存储
        对象存储(Cloud Object Storage,COS)是由腾讯云推出的无目录层次结构、无数据格式限制,可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限,无需分区管理,适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
        领券
        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档