Hadoop笔记汇总系列第十篇-Erasure code

这是我参与更文挑战的第16天，活动详情查看: 更文挑战

背景

Erasure Code是分布式存储系统中常用的一种编码技术,HDFS就是基于Erasure Code来实现底层存储.

Erasure code

Erasure code原理

Erasure code是一种技术，它可以将n份原始数据，增加m份数据，并能通过n+m份中的任意n份数据，还原为原始数据。定义中包含了encode和decode两个过程，将原始的n份数据变为n+m份是encode，之后这n+m份数据可存放在不同的device上，如果有任意小于m份的数据失效，仍然能通过剩下的数据还原出来

Erasure code主要运用于存储和数字编码领域,但是需要通过冗余来进行高可用的场景也都能适用

多副本策略和Erasure Code

多副本策略在满足存储可靠、优化数据读性能同时也不可避免地造成存储资源利用率低的缺陷。erasure code编码存储策略在满足和多副本同样可靠性前提下，可以达到更高的存储资源利用率。

云存储

erasure code是云存储的核心技术，最初诸如hadoop, GFS，CEPH等都采用的是n-way replication来做冗余，但是这样会带来极大的成本开销，因此几乎各大公司都在用erasure code替代n-way replication

Reed-Solomon Codes编码

erasure code是所有基于之前定义的统称，但具体下来有很多种，其中RS code是最基本的一种。RS codes是基于有限域的一种编码算法，有限域又称为Galois Field，是以法国著名数学家Galois命名的

1. Google GFS II中采用了最基本的RS（6,3）编码

将一个待编码数据单元(Data Unit)分为6个data block, 再添加3个parity block，最多可容包括parity blocks在内的任意3个数据块错误。存储的space overhead 为（6+3)/6 = 1.5x.数据恢复的网络I/O开销为：恢复任何一个数据块需要6次I/O，通过网络传输6个数据block

2. Microsoft：erasure code in WAS(Windows Azure Storage)

为减少数据恢复时的网络I/O，微软采用了如上LRC编码策略，其核心思想为：将校验块（parity block）分为全局校验块(global parity)、局部校验块(local reconstruction parity).微软LRC（12,2,2）编码将一个待编码数据块分为12个data blocks，并进一步将这12个data blocks平均分为2个groups,每个group包括6个data blocks.为每个data group分别计算出一个local parity，以及所有12个data blocks计算出2个global parities.当发生任何一个数据块错误时，恢复代价由传统RS（12,4）编码的12（通过网络传输的数据块数量）变为6，恢复过程的网络I/O开销减半。Microsoft 以上LRC编码的space overhead为（12+2+2）/12 = 1.33x

3. Facebook：从RS(10,4)到LRC（10,6,5）

RS(10,4)编码是Facebook HDFS RAID的早期编码方式，如上图所示。将每个待编码Data Unit均分为10个data block, 后面添加4个校验的parities.以上编码方式的space overhead为（10+4）/10 = 1.4x,发生任何一个数据块错误的恢复代价为10,即发生任意一个块错误需要10次I/O操作，从网络传输的数据量为10个数据块

Erasure Code的问题

erasure code编码技术无疑对存储空间利用率带来很大提升，但由于引入额外的编码、解码运算，对分布式计算本身会造成一定程度的性能损失。由于当前的编码技术还未从根本上解决降低性能损失，目前erasure code还仅适用于对冷数据的离线处理阶段

实时编码和异步编码

目前已经应用Erasure code的分布式文件系统里，HDFS、Windows Azure等系统采用异步编码的方式，写流程和数据编码流程完全解耦；而GPFS、pangu（阿里云的分布式文件系统）等系统则是采用实时编码的方式，在数据写入时进行编码

TFS无法使用实时编码

• HDFS等系统主要针对大文件存储，一个文件包含多个数据块，写文件时通常是大块数据的连续写入，可以选择在写文件时对数据进行编码；
• 而TFS主要针对小文件存储，多个小文件存储到一个数据块里，写文件时通常是是小块数据的随机写入，导致TFS很难对写入的文件进行实时编码

TFS的异步编码方案

异步编码方案，由nameserver（NS)在后台控制编码，以数据块为单位，每次选择K个数据块，编码出M个校验块，这K+M个块在TFS里称为一个编组，编组的元信息持久化存储在tair（阿里的开源KV存储系统）里，编组里不超过M个块的丢失（或失效），都能通过编组内任意K个正常的块计算恢复回来。
TFS采用4+2,即4个block+2个校验块

异步编码，对用户透明

1. 目前已经应用Erasure code的分布式文件系统里，HDFS、Windows Azure等系统采用异步编码的方式，写流程和数据编码流程完全解耦；而GPFS、pangu（阿里云的分布式文件系统）等系统则是采用实时编码的方式，在数据写入时进行编码。
2. TFS与GFS、HDFS等系统类似，以数据块（block，通常为64MB）为单位管理存储的数据。不同的是，HDFS等系统主要针对大文件存储，一个文件包含多个数据块，写文件时通常是大块数据的连续写入，可以选择在写文件时对数据进行编码；而TFS主要针对小文件存储，多个小文件存储到一个数据块里，写文件时通常是是小块数据的随机写入，导致TFS很难对写入的文件进行实时编码。
3. 基于TFS的写入特性，我们选择类似HDFS-RAID的异步编码方案，由nameserver（NS)在后台控制编码，以数据块为单位，每次选择K个数据块，编码出M个校验块，这K+M个块在TFS里称为一个编组，编组的元信息持久化存储在tair（阿里的开源KV存储系统）里，编组里不超过M个块的丢失（或失效），都能通过编组内任意K个正常的块计算恢复回来。

块失效时的恢复策略

当某个块失效时，退化读该块内的文件时，TFS只会恢复被访问文件的数据，尽快返回给客户端，而不会在此时恢复整个块的数据，因为数据块的恢复时间远超出客户端能接受的response time。
失效数据块的恢复由NS在后台控制完成，跟文件读写流程也是完全解耦的。以D1失效为例，当NS检测到D1失效后，如果等待一定时间（规避短时间内可恢复故障的影响）D1仍然处于失效状态，NS会发起一个恢复D1的任务，具体流程如下：

1. 从D1所属编组里选择一个Master DS(某个块所在的dataserver)，将编组信息发送该DS，让其负责恢复D1的数据。
2. Master DS从编组里任意选择K个正常的块，比如D2、D3、D4、P1，用于恢复D1的数据。
3. Master DS从D2、D3、D4、P1读取数据，计算恢复出D1的数据。
4. Master DS从P1或P2读取D1的索引，恢复D1的索引。
5. Master DS向NS汇报恢复D1完成

索引文件的策略

TFS在对数据块进行Erasure code编码时，最大的难题是对数据块索引文件的处理；TFS的每个数据块都对应一个索引文件，用于快速定位文件在数据块内的位置
若对索引文件也编码,那么读一个很小的文件，也要读取K份索引的完整数据，开销非常大
为了减小退化读时的开销，我们的做法是不对索引文件进行编码，而是以副本的机制存储索引文件，将每个数据块的索引，都存储一份副本到每个校验块的索引文件里。

文件更新的策略

1. 在应用Erasure code后，对于没有编组的数据块，更新的流程保持不变；但对于已经编组的数据块，如果修改了数据块的数据，必须重新计算校验块响应部分的数据，并在校验块上进行更新，如下图所示，这整个过程必须做成一个事务，要么不做、要么都做，否则如果出现部分成功的情况，会影响到其他块的恢复
2. 引入事务机制对于TFS来说成本过高，为了解决上述问题，我们对已编组数据块上的文件更新做特殊处理，使用跟索引文件一样的处理方式，对更新的文件以多副本的形式进行存储，方案如下图所示。D1、D2、D3、D4、P1、P2构成一个编组，假设要更新D1上的某个文件，首先将文件数据追加到D1数据块的末尾（图中update的黄色部分），并更新D1的索引，同时在每个校验块的末尾追加更新的文件数据，并更新D1在各个校验块里的索引信息。由于被更新过的文件特殊性，实际上在恢复失效块时，对于块内被更新过的文件，是直接从校验块上读取恢复的
3. 这样设计导致已编组的数据块上更新的并文件不能享受Erasure code带来的成本降低，但基于更新文件总量不大这一前提（实际上，我们一直在推动应用尽量不使用更新接口），加上已经编组的数据块通常是很冷的数据，发生更新的可能性更小，所以总体影响不大