专注网站建设怎么样,如何建设一个专业的网站,江苏网站建设价格低,有哪些室内设计网站Erasure-Code(纠删码) 最佳实践
1. 纠删码原理
这个星球产生的数据越来越庞大#xff0c;差不多2010年开始各大互联网公司大都上线了系统以应对数据膨胀带来的成本增长。Erasure-Code#xff08;纠删码#xff09;技术应用其中。典型如Google 新一代分布式存储系统colossu…Erasure-Code(纠删码) 最佳实践
1. 纠删码原理
这个星球产生的数据越来越庞大差不多2010年开始各大互联网公司大都上线了系统以应对数据膨胀带来的成本增长。Erasure-Code纠删码技术应用其中。典型如Google 新一代分布式存储系统colossus系统的Reed-solomon算法、Window Azure Storage 的LRC算法等等。
EC(Erasure-Code)算法的最底层的基本的数学原理行列矩阵中一种特殊矩阵的性质即任意MxNM行N列{MN}的行列式其任意MxM的子矩阵都是可逆以实现数据恢复运算。
如下图所示以一个典型的例子进行说明。
D1D5通过矩阵A(8*5)相乘得到D1D5的原始数据和C1C3的校验数据块Figure-1。假设此时原始数据块D1、D4和校验数据块C1发生损坏。那要如何才能读取D1、D4等数据块、还原C1校验数据块这个时候就依赖矩阵运算的特性。首先可知从A获取子矩阵B‘ 5*5与原始数据相乘可以得到D2、D3、D5、C2、C3即现有还未损坏的数据Figure-1那反过来说当前的问题就是如何通过已有的B‘和D2、D3、D5、C2、C3还原得到D1、D4数据块和C1校验块。此时利用矩阵运算假设B可逆在等式2边分别乘上B’的可逆矩阵B-1这样就可以通过B-1 和已有的D2、D3、D5、C2、C3 进行矩阵运算还原得到D1和D4数据块。C1可以通过B11B15与已经恢复的数据(D1D5)相乘获得。该过程可行的核心保障就是需要确保矩阵A的任意5*5的子矩阵的可逆矩阵都是存在的这样才能确保丢失8块数据中的任意3块数据都可以进行数据还原。核心的重点就是需要找到这样的矩阵A其中黄色部分就是范德蒙矩阵这里对此不多做展开自行google或者参看任何矩阵论的教材都有清晰的说明。 更多由浅入深如何工程化的原理的解释可以参考Erase Code 原理。
2. EC与数据放置
首先看如何对数据进行数据放置。比如HDFS、colossus、Ceph 将数据条带化的放置在不同的chunk(Stripe placement)。而Window Azure Storage 则使用连续数据块放置方式(Contiguous placement)。各自有各自的特点。 如上图所示假设abcdfghigklmnopqrstuvwxyz为原始的一段数据内容在EC场景下可以有2种截然不同的数据划分方式。
Stripe Placement条带的数据放置方式即将数据顺序进行拆散逻辑放置在不同的数据块中打破了数据原先的物理相邻顺序。Contiguous PlaceMent连续的数据放置方式即保留数据原来的顺序除了数据分块的边界(如上图D1、D2)的边界核心上来说数据逻辑上还是保持了相邻的顺序。
这2种方式各有各的特点如上图所示在工程上D1D5数据块 、C1C3校验块一般都按照故障域原则放置在不同可用区的不同的磁盘上。
Stripe Placement 的特点
一份数据的读取可以同时利用多个磁盘的吞吐能力但是对于IOPS来说是放大换句话说对大块数据读取比较友好缺点就是失去了数据的locality这在Hadoop大数据体系中将计算放置在数据附近来说是很关键的一点及时EC即不用等凑足整一份大的数据才进行EC写入基本在凑足EC的条带大小即可进行写入也就是说在线数据写入可以直接以EC的体系。
Contiguous Placement的特点则相对来说相反
数据都是临近放置所以一般情况下的数据的读取就跟副本形式一样在一个数据节点是就可以获得对于小IO来说比较友好对于大IO没有明显的缺陷。不能进行及时EC。需要进行凑足一定的数据才能够形成D1到D5的数据块进行EC所以一般来说比较适合做后台的EC。比如Window Azure Storage 是先写三副本的Extent在Extent seal关闭掉之后后台异步得将数据为EC。
3. EC 条带大小与小IO
在大规模的存储系统中小文件往往会结合索引机制将小文件合并成一整个大文件。详见对象存储架构设计A Bite of S3 Storage Arch。
对于小文件一般是指小于128KB的文件在Contiguous PlaceMent 条件下小文件在常规情况下的读取方式与传统的多副本类似。但是在高负载情况下和节点故障情况下需要backup request 机制保障latency在如上53的模式下一个IO需要其他5个节点的IO进行恢复。
为了避免在5倍的IO造成对用户latency的显著放大负载情况下慢节点拖慢整个数据读取的速度。一般来说可以通过Backup Request的方式减少对用户即时访问的影响。window-azure 给出了RS(123 )、 LRC1222等 纠删码算法情况下EC重建4KB数据的响应时间情况。从图(a)可以看出在低压力情况下通过RS方式重建读取12块数据相比直接读取的时间差不多是2.5倍(23ms VS 51ms vs)在通过Backup Requst的方式发送15个请求选最快的12个的策略恢复数据情况下可以获得与单副本差不多的响应时间(29ms)。但是在高压力情况下读取12块数据的响应时间相比于直接读取的响应时间是(305ms VS 91ms )同样可以通过backup Request122的方式来使得响应时间降低到差不多与直接读取差不多的响应时间97ms。也就是说在整体IOPS能力并非瓶颈情况下可以通过BackUp Request的机制显著降低采用EC技术方案在坏盘等故障情况下对用户IO延迟的直接影响。 而对于Stripe PlaceMent 情况下。如果Stripe Unit 过小比如4KB那么可能会导致128KB的小文件读取需要跨很多节点才能够读取完整的数据相对来说比较费IOPS。这个时候可以适当调整条带大小使得在正常情况下小IO的绝大多数情况下的读取可以在单个节点读取跨越边界情况下读取2个节点。
但是这会导致小文件需要很大的IO填充才能够进行一次写入满条带写空间利用率会有比较大的降低。上层合直接写入的文件不适合太小A Bite of S3 Storage Arch中说明的小文件一般来说先可以不通过3副本WAL的方式保障持久性的情况下通过Merge成更大的MobFile EC的方式来避免文件太小。如下图所示EC 42组合可以使得EC Stripe Unit大小比如为1.5MB。每个分片数据256KB的方式来使得小IO在正常情况下可以在一个节点上读取。 4. EC 与大IO
在大块数据读写情况下Contiguous PlaceMent 方案在一般场景下跟传统的多副本策略几乎是一样的。因为数据一般来说都是临近放置直接按照分块的放置进行直接数据读取即可。但是在异常情况下按照Window Azure Storage 场景的测试由于磁盘和网络带宽容易相对容易达到瓶颈所以采用BackUp Request的并没有啥改善。
如下图所示RS(read k) 、RS(readk 1、RS(readk 2)、RS(readk 3) 均没有太大的改善。其发表paper的时候大概是2010年当初其网络(NIC) 大概是1Gbps。而现在其实网络越来越多的是10Gbps、50Gbps、100Gbps。所以今日不同往时最核心的原因还是看当前系统带宽层面的带宽是否已经饱和。 一般情况下可以认为上层业务的大块连续IO读取都是满条带的读取在Stripe Placement 情况下满条带的读取在正常情况下和异常情况下从底层读取的数据量可以认为是一致的如下图左侧图所示而且当前一般来说EC 解码有硬件加速即计算层面不太容易成为瓶颈所以Stripe Placement 在正常度和异常情况下的开销基本可以认为差不多。在极端情况下数据跨越stripe unit边界的情况下会带来2倍的IO放大。但是在Contiguous PlaceMent 策略下则需要更大的范围内的放大如下EC 42 的策略下可能会导致4倍的放大在比如123等情况下会有更大的放大。 5. 总结
上述分析了EC 结合不同的放置策略Stripe PlaceMent、Congiguous PlaceMent情况下各自的优势和缺点在这些固有的约束条件下需要通过合理的架构选择来充分利用EC的优点屏蔽EC缺点以最大化EC的价值。
在当前机房网络能力越来越强的情况下如Flat DataCenter Storage说明数据的locality总体来说在大多数大数据场景下越来越不重要了存储计算分离是大趋势。比如S3对象存储、EBS等可以考虑使用 RS Stripe PlaceMent 结合合理的 Stripe Unit的方案作为底层的纠删码方案在架构选择层面可以参考之前的2篇博文
对象存储架构设计、随机IO存储系统EBS架构设计。
题图19世纪伟大数学家 伽罗华. 其数学理论让EC在计算机上的实现成为可能 Notes
作者网易存储团队工程师 TOM。限于作者水平难免有理解和描述上有疏漏或者错误的地方欢迎共同交流部分参考已经在正文和参考文献中列表注明但仍有可能有疏漏的地方有任何侵权或者不明确的地方欢迎指出必定及时更正或者删除文章供于学习交流转载注明出处
参考文献
HDFS-Erasure-Coding-DesignErasure Coding in Windows Azure StorageErasure Code 原理和工程化介绍)Flat DataCenter StorageA Bite Of S3 Storage ArchA Bite of Random IO Storage Design-EBS
