关于分布式存储:纠删码技术在vivo存储系统的演进上篇
作者：vivo 互联网服务器团队- Gong Bing本文将学术界和工业界的纠删码技术的外围研究成果进行了相应的梳理，而后针对公司线上存储系统的纠删码进行剖析，联合互联网企业通用的IDC资源、服务器资源、网络资源、业务个性进行剖析对原有纠删码技术进行优化和微翻新，提出了交融EC整体计划以及可落地的RS+LRC+两头后果优化+并行修复跨AZ带宽设计方案，为后续的工程实际提供重要原理和架构撑持。 引言本文借友商轮值CEO 于2020年8月28日在长沙“数学促成企业翻新倒退论坛”上分享的《后香农时代，数学决定将来倒退的边界》【85】进行开篇，发言提出了后香农时代，ICT信息产业面向数学的十大挑战性问题，其中就有一项“高效的纠删码问题”，尽管这个问题的提出背景是出于通信编码畛域，但对于纠删码在存储畛域的应用同样面临着具大的时机与挑战。 图1：纠删码问题挑战 针对纠删码的钻研分为两派： 一派则是纯理论界针对纠删码编码技术在编解码复杂度、修复带宽及磁盘IO、存储开销等维度进行钻研提出新的实践齐备性证实过的纠删码，这类钻研可能思考更多的是实践齐备性的证实；不会思考工程界的实现复杂度等状况；一派是不扭转编码实践，利用纠删码联合生产环境进行适当革新（多AZ、异构服务器、大条带、跨rack等）再联合试验数据在修复开销、存储开销、可靠性等指标来证实价值。这两派的钻研相辅相成独特推动纠删码技术在分布式存储畛域的倒退。本次分享的主题“纠删码技术在vivo存储系统的演进”，分为高低两篇： 上篇偏重介绍和剖析纠删码技术的演进历程、外围纠删码技术的原理和以及工业界存储产品当中的纠删码技术的摸索与实际，最初介绍vivo存储系统在纠删码技术上的一些摸索；下篇重点开展介绍存储团队在纠删码畛域的研究成果及纠删码研究成果在vivo存储系统中的实际，与工业界存储产品中的纠删码相干指标进行全方位比照，以及将来的一些布局。 图2：本文的组织构造 注：本文当中有大量的专业术语，不可能所有术语都去作个解释，因而针对不懂的有些术语能够自行去搜寻相干含意一、相干背景1.1 钻研意义分布式存储系统为了降低成本往往采纳大量便宜通用的服务器提供服务，然而这些服务器的磁盘的可靠性是个很大的问题，其平均寿命在2-7年，还受外部环境因素的影响，受限于其机械结构，磁盘会产生磁盘故障、扇区故障和不可检测磁盘故障等。因而，分布式存储系统为了进步原始数据的可靠性，正本和纠删码是两种最常见的数据冗余办法。正本将原始数据复制到n份，并存储到不同的存储节点上，可能容忍任意n-1个节点生效，其毛病是存储开销大。纠删码则以计算资源换存储资源，采纳了一种更高效的形式减少数据冗余，因而，纠删码成为了以后云存储的支流数据冗余形式，并且继续成为学术界和工业界在存储畛域的一种钻研热点。 图3：应用纠删码技术公司列表 1.2 钻研现状纠删码也被称为纠错码，它将原始数据编码为数据量更大的编码数据，并可能利用编码后的局部编码数据复原出原始数据。当有节点产生故障时，要复原这个节点的数据须要读取多个节点的数据，这个过程会耗费大量的网络带宽和磁盘IO，另外解码复杂度对业务可用性和数据可靠性也有影响，解码复杂度越高，则长期修复时延就高，从而减少业务读取时延；因而，影响纠删码好坏的指标很多，次要有如下一些指标：以下指标都是以可靠性对立基准的前提下进行参考： 【编码复杂度】编码复杂度决定了数据写入的时延【解码复杂度】解码复杂度决定了读取的时延以及节点故障时数据长期修复及永恒修复的时延【修复网络带宽】节点故障时数据修复所需耗费的整体网络带宽，这个指标十分要害【修复磁盘IO】磁盘IO耗费和网络带宽个别成正比，思考大部分存储服务器是高密服务器，个别网络会是瓶颈【修复节点数】修复节点数缩小，往往也就升高了修复须要的网络带宽【更新复杂度】更新复杂度是指一份数据有大量更新操作，比方更新一两个字节很频繁所波及的相干操作复杂度【存储开销】这个指标是指的编码效率，编码效率越高，存储开销越低【参数限度】比方纠删码的码长受不受限制等等以利用最为宽泛的【n,k】RS码【2】为例，RS的码长为n，码的维度为k，当呈现有节点故障时，须要k个节点进行复原，同时能够容忍n-k个节点的故障，这种编码也被称为最大间隔可分纠删码MDS【3】，对应上述指标也就意味着雷同的容错能力下RS码的存储开销小，另外RS码的码长不受限制，这也是RS码如此受欢迎的起因；而在通信畛域大杀四方的LDPC【4】纠错码在存储畛域利用较少，起因就是因为LDPC不满足MDS个性，容错能力不限，意味着雷同的容错能力LDPC须要更大的存储开销, LDPC更多是利用在磁盘外部的冗余；而得益于晚期在RAID5和RAID6中的宽泛应用，具备MDS个性的阵列纠删码也被尝试着利用在分布式存储系统当中，MDS阵列码绝对于RS码全是异或操作，编解码绝对RS码复杂度低，然而同时相干参数有所受限，这也克制了它在分布式存储的广泛应用；常见的阵列码有EVENODD码【5】、RDP码【6】、STAR码【7】反对3容错、Liberation码绝对EVENODD更新复杂度靠近实践下界【8】，ZigZag码【9】磁盘IO开销达实践下界，Blaum-Roth码【10】基于多项式环上结构的MDS阵列码，绝对于RS是编解码复杂度要低些。 另外针对RS码昂扬的网络修复带宽，涌现出一类再生码【11】来升高修复中所要耗费的带宽。再生码是一类通过容许节点发送编码过的数据来使得修复中可最小化修复带宽的纠删码，其可在不减少存储开销的状况下显著升高修复带宽。Dimakis等人将再生码分为两大类：MSR码【23-47】和MBR码【12,13】。MBR码是最小化修复带宽次要分为Polygonal MBR Code【14】和Product-Matrix MBR Code【15】；MSR码是在最小化存储开销下升高修复带宽，又分为准确修复码和性能修复码，准确修复码是指通过修复可修复出原始失落数据，性能修复码则不保障，数据读取每次都须要进行解码操作。比方Hu等人提出了一种功能性MSR码F-MSR【16】，精确性MSR钻研次要基于Product-Matrix MSR【26】，还有比方Butterfly码【48】、Coupled Layer Code码【38-40】等以后曾经在工业界有所利用的再生码。最近又有一些工作【18,19,20】是针对跨机架带宽和机架内带宽进行辨别，为最小化跨机架带宽为指标缩小修复带宽。升高修复带宽还有一些其它的钻研工作，比方2013年Rashmi等人提出Piggybacking框架【22】，框架以MDS码为根本码通过将子条带数据嵌入其它条带来显著升高修复带宽，Piggybacking框架的编码设计也有很多研究成果。【79-81】 针对修复节点数升高这个指标，Huang等人提出了一种部分修复码LRC【17,21】通过对传统编码数据块进行分组，并针对每组生成校验块，从而使得单块修复只须要组内节点参加修复进步修复性能。但因为引入额定存储开销，LRC没达到存储最优。但因为LRC的繁难性，工业界有很多的实际反馈，因而LRC逐步成为近年来纠删码畛域的钻研热点【66-78】。LRC的一个分支MRC码的钻研PMDS也吸引了不少关注【49-60】，除了单节点修复相干的LRC码的结构，针对修复多个节点的LRC码【62-65)】是一个钻研方向，另外，联合LRC和RC的Local Regeration Code【61】也是个钻研思路。 图4：纠删码钻研方向概览 二、原理解析2.1 基础知识介绍概念1：纠删码原理 纠删码通用由两个参数n和k来进行配置，称为(n,k)编码。在分布式系统当中，通常将数据以固定大小的块进行组织，编码时，存储系统将k个数据块进行编码生成额定的n-k = m个大小雷同的校验块，这样n个数据块和校验块中有任意的磁盘节点故障，都能够通过其它的磁盘节点进行解码复原失落的数据。以下为纠删码的一个示意图： 图5：纠删码原理示意图 概念2：Singleton顿界 假如C是一个参数为[n,k]的线性码，则C的极小间隔d≤n-k+1。以上表明一个线性码的极小间隔不会“太大”，无论怎样致力，都不可能结构出一个参数为[n,k]的线性码，使得它的极小间隔大于n-k+1，这个n-k+1就称为Singleton界。 概念3：MDS个性 一个参数为[n,k]的线性码C，若满足dmin(C)=n-k+1，则称该码为极大间隔可分码，简称为MDS（Maximum Distance Separable）码。 概念4：系统性 系统性就是零碎中存储了k个数据块可用来直接存取，如果故障的节点没包含数据块，则不影响数据的读取，系统性可升高读取时延。非系统性则在每次读取时都须要进行解码操作，读取时延绝对偏大。 2.2 经典纠删码介绍2.2.1 Reed-Solomon CodeRS码最早是ECC畛域的一种纠错算法，RS编码算法是一种典型的零碎编码，也是一种典型的MDS性质的编码。 RS码根本思维其实就是拉格朗日插值多项式，我感觉用拉格朗日插值多项式来推导RS码绝对于其它文献的解说会更清晰，上面咱们简略回顾一下拉格朗日插值多项式：对于任何k阶的多项式函数f(x)=a0+a1x+a2x^2+...+akx^k，咱们很容易通过任意的n+1个点(x0, f(x0)，(x1,f(x1))，... (xk,f(xk))对这个多项式进行复原。 解码过程如下： 那么RS码是如何应用拉格朗日插值的呢？对于一个(n,k)的RS码，假如a0,a1,...ak-1在Fq域内的k个发送信号，咱们在Fq中采样n个插值点x0,x1,...xn-1，则能够失去拉格朗日插值多项式为： 不难发现，前k个插值的多项式值有如下： 如果用矩阵来示意则为： 令上式的范德蒙德矩阵的逆*a向量 = b向量，则校验矩阵有如下： 【A|B】【A^-1】 a向量= 【E|BA^-1】* a向量 = 【a0,a1,...ak, c1,...cn-k】 ...