TFS Erasure code实现方案

作者：[e-mail]
博客：ydzhang.blog.chinaunix.net | blog.yunnotes.net
微博：

TFS发展至今，集群部署总容量已超过50PB，机器数量约2700台。TFS在阿里内部主流部署方式是主集群内数据块2个副本，每个主集群配置两个备集群，分别在同城和异地机房，实际上每份数据6个副本，存储成本非常高，为了降低TFS存储成本，我们将Erasre code引入到TFS系统，本文将详细介绍TFS应用的技术方案。

异步编码，对用户透明

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

TFS与GFS、HDFS等系统类似，以数据块（block，通常为64MB）为单位管理存储的数据。不同的是，HDFS等系统主要针对大文件存储，一个文件包含多个数据块，写文件时通常是大块数据的连续写入，可以选择在写文件时对数据进行编码；而TFS主要针对小文件存储，多个小文件存储到一个数据块里，写文件时通常是是小块数据的随机写入，导致TFS很难对写入的文件进行实时编码。

基于TFS的写入特性，我们选择类似HDFS-RAID的异步编码方案，由nameserver（NS)在后台控制编码，以数据块为单位，每次选择K个数据块，编码出M个校验块，这K+M个块在TFS里称为一个编组，编组的元信息持久化存储在里，编组里不超过M个块的丢失（或失效），都能通过编组内任意K个正常的块计算恢复回来。

如上图所示K=4、M=2，D1-D4原来各有2个副本，总共2个副本，能容忍1个副本失效；在对数据块D1-D4进行编码后，生成P1、P2两个校验块，编码完成后D1-D4多余的副本会被删除掉，[D1、D2、D3、D4、P1、P2]构成一个编组，总共6个副本，能容忍2个副本失效（理论安全性更高）；经过编组后，存储成本下降了25%。

从存储安全性以及空间利用率等因素考虑，编组选择数据块时必须满足如下条件：

1. 机架安全，K+M的块必须分布在不同机架 
2. 数据块必须已经写满，避免空间浪费 
3. 数据块内删除文件数低于一定比例（如5%)，减少存储空间的浪费 
4. 数据块超过一定时间没被访问过（如1个月），尽量只对冷数据进行编码 

TFS采用上述异步编码方案，编组过程由服务器端控制，对用户完全透明；用户仍使用原来的API来读写文件，他们并不知道写入的数据在服务器端会被进行编码，这就使得我们在应用Erasure code时，并不需要应用升级程序来配合。

编码方案可扩展

在编码方案选择上，HDFS、Windows Azure等都选择了Reed Solomon(Azure后来使用来优化数据恢复），TFS也选择了Reed Solomon，并使用了开源的Jerasure库；在容错性上，TFS最初确定编组容忍2个块失效，即编组内校验块的数量为2（M=2)；而在数据块数量上，综合存储成本、编组恢复开销、实时恢复性能等因素，将数据块数量确定为4（K=4)。

在工程实现时，我们将编码方案、数据块及校验块数量等都是可配置的，作为编组元信息的一部分持久化存储，这么做使得后期都编码方案做优化非常方便；在应用Erasure code过程中，我们可以随时修改编码方案、以及容错参数等，一旦配置被修改，新产生的编组就会应用新的编码方案。

编组及恢复流程

TFS在对数据块进行Erasure code编码时，最大的难题是对数据块索引文件的处理；TFS的每个数据块都对应一个索引文件，用于快速定位文件在数据块内的位置，如下图所示，索引文件大小在几十KB左右。

最直观的方法是对数据块的索引也进行Erasure code编码，将索引编码生成的数据作为校验块的索引存储，如下图所示

上述做法，虽然直观简单，但有个致命的问题，就是当编组内某个数据块D1失效时，如果要访问这个数据块里的某个文件（TFS里称为退化读），首先要读取编组内K份索引文件数据，恢复出D1的索引，然后在D1的索引里查找出文件在数据块内的位置及大小信息（offset、size）；再从编组里选择K个块，读取出每个块[offset，offset + size]部分的数据，恢复出待读取文件的数据，返回给客户端。

从上述过程可以看出，即使退化读一个很小的文件，也要读取K份索引的完整数据，开销非常大，使得退化读的response time达到不可接受的地步。为了减小退化读时的开销，我们的做法是不对索引文件进行编码，而是以副本的机制存储索引文件，如下图所示，将每个数据块的索引，都存储一份副本到每个校验块的索引文件里。

索引以副本机制存储后，校验块索引占的存储空间变大K倍，但因为索引文件很小，增加存储开销基本可以忽略；带来的好处是，退化读文件时，选择任意一个校验块，就能从校验块的索引里查找到文件在数据块内的位置信息，接下来就可以选择编组内任意K个块来读取需要的数据，恢复出待读取的文件，返回给客户端。

很显然，通过将索引以副本的形式存储起来后，退化读的开销小了很多，少了K次读取索引文件的网络及IO开销、以及恢复索引的计算开销。下图黄色部分展示了当D1失效时，要读取D1里的某个文件时需要读取的数据。（黄色的D1 index只会查询到，并不会读取整个索引文件）

当某个块失效时，退化读该块内的文件时，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完成。 

NS选择master DS时，会选择编组里某个状态正常的块所在的DS，保证至少一个块的数据读取会在本地完成，节省恢复时的网络开销。

文件更新的弱一致性

在引入Erasure code前，TFS支持文件更新，但不保证更新后的一致性，内部有部分应用能接受不一致的语义，使用了更新接口，但频率不高，占总共写请求的0.5%不到。

在应用Erasure code后，对于没有编组的数据块，更新的流程保持不变；但对于已经编组的数据块，如果修改了数据块的数据，必须重新计算校验块响应部分的数据，并在校验块上进行更新，如下图所示，这整个过程必须做成一个事务，要么不做、要么都做，否则如果出现部分成功的情况，会影响到其他块的恢复。比如某次更新D1上的文件，D1上成功，P1也更新成功，但P2失败，接下来如果D2失效，如果选中P1、P2来回复D2，则恢复出来肯定是错误的。

引入事务机制对于TFS来说成本过高，为了解决上述问题，我们对已编组数据块上的文件更新做特殊处理，使用跟索引文件一样的处理方式，对更新的文件以多副本的形式进行存储，方案如下图所示。D1、D2、D3、D4、P1、P2构成一个编组，假设要更新D1上的某个文件，首先将文件数据追加到D1数据块的末尾（图中update的黄色部分），并更新D1的索引，同时在每个校验块的末尾追加更新的文件数据，并更新D1在各个校验块里的索引信息。由于被更新过的文件特殊性，实际上在恢复失效块时，对于块内被更新过的文件，是直接从校验块上读取恢复的。

这样设计导致已编组的数据块上更新的并文件不能享受Erasure code带来的成本降低，但基于更新文件总量不大这一前提（实际上，我们一直在推动应用尽量不使用更新接口），加上已经编组的数据块通常是很冷的数据，发生更新的可能性更小，所以总体影响不大。

未来工作

目前，TFS线上服务已经开启了Erasure code功能，NS正逐步把满足条件的数据块进行编码，生成校验块，同时删除掉已编组数据块的多余副本，随着编码的不断进行，集群的存储容量正在逐步下降。

接下来，我们会逐步对Erasure code的应用进行各项优化工作，主要包括：

1. 对编码的性能进行优化，如使用更优的编码算法、使用硬件加速编码等。 
2. 优化块失效时的恢复时间，降低恢复时系统总体的网络和磁盘的开销。 
3. 优化对冷数据的统计，尽可能让Erasure code只应用在冷数据上，降低块失效的影响。