TAR-CAU: An XOR-Based Data Update Scheme

纠删码也称为纠错码，它将原始数据编码为数据量更大的编码数据，并能利用编码后的部分数据恢复出原始数据。纠删码一般需要指定 $ n $ 和 $ {k} $ 两个参数，用 $ {k} $ 份数据进行编码，产生 $ n $ 份数据。RS编码是最经典的一种纠删码^[1]，图1为一个典型的RS(5, 3)的云存储系统( $ n=5,k=3 $ )，其中有3个数据节点和2个校验节点，每个节点中的数据都按照大小固定的块存储(块大小一般为1～64 MB)，编码后的数据块与校验块组成一个条带(stripe)，大多数数据更新算法都是按照条带顺序一条一条进行更新。图1展示了一个条带信息，其中， $ {d}_{i,j} $ 表示数据块， $ {p}_{i,j} $ 表示校验块，同一条带中属于同一节点的数据块或校验块称为条块(strip)^[11]。

纠删码的数据更新主要有基于RS的更新和基于XOR的更新。

1)基于RS的更新。基于RS的更新主要利用范德蒙德矩阵或柯基矩阵生成校验数据^[3]，图2为图1的编码过程，其中， $ {d}_{i}=\left({d}_{i,0},{d}_{i,1},{d}_{i,2}\right)， {p}_{j}= ({p}_{j,0},{p}_{j,1},{p}_{j,2}) $ 。

编码时，利用生成矩阵(generator matrix)左乘各个数据节点的数据向量 $ ({d}_{0},{d}_{1},{d}_{0}) $ ，生成码字 $ ({d}_{0},{d}_{1},{d}_{0},{p}_{0},{p}_{1}) $ ，其中， $ {p}_{0} $ 和 $ {p}_{1} $ 为校验块，表示为：

当数据 $ i $ 更新时，用 $ {d}_{i}' $ 替换 $ {d}_{i} $ ，或在数据节点 $ i $ 中计算delta值( $ {d}_{i}' \oplus {d}_{i} $ )，然后将delta值传输给 $ {p}_{i} $ 所在的校验节点，最后计算出最新的校验数据。本文参考的CAU算法就是基于RS的数据更新。

2)基于XOR的更新。从式(1)可以看出，基于RS的更新会产生大量的乘法运算( $ {\alpha }_{j,i}{d}_{i} $ )，消耗CPU资源。因此，可以利用有限域(galois field)将所有的乘法和加法运算转化为XOR运算^[12-13]。

如图3所示，利用 $ {\rm{GF}}({2}^{3}) $ 的矩阵表示法可以将柯基矩阵转换为位矩阵(binary distribution matrix, BDM)， $ {\rm{GF}}({2}^{3}) $ 表示所有数据均用3位2进制数表示，数据范围为0～7。

图中，深色表示1，白色表示0，这样，所有的校验数据都可仅用XOR公式表示：

基于XOR的数据更新方法仅依赖简单的XOR运算，CPU可以直接执行XOR操作，相比于乘法运算，XOR运算效率更高，因此，数据更新效率也更高。同时，根据文献[3]研究表明，基于异或的编码方式更适合采用现代CPU的SIMD技术执行并行加速计算。如采用AVX2指令，可同时进行256位异或运算。本文在一台配有4核2.2 GHz Intel CPU、16 GB DDR3内存、1 TB SSD存储的Mac操作系统环境中进行测试，发现采用AVX2指令、基于XOR进行数据更新，更新1 MB的数据仅需20 ms，而采用基于RS的数据更新，需要300 ms。因此，与CAU不同，本文选择基于XOR进行数据更新。

CAU算法的核心思想可以用图4表示，如前所述，CAU按照节点所在的机架进行分组，其中， $ {R}_{i} $ 和 $ {R}_{j} $ 分别表示数据节点机架和校验节点机架，CAU并不是实时处理每一个更新请求，而是设置了一个批处理阈值(如100)，当请求数量超过该阈值时，分条带批量处理更新请求。当同一条带中， $ {R}_{i} $ 的数据更新量小于 $ {R}_{j} $ 的校验数据更新量时，采用data update方法，即分别将数据节点的delta值发送给某一校验转发节点，再由校验转发节点通过式(1)计算校验更新并传输给相关的校验节点，如图4a所示；相反，当 $ {R}_{i} $ 的数据更新量大于 $ {R}_{j} $ 的校验数据更新量时，采用parity update方法，即汇总所有的delta值到数据转发节点，再由数据转发节点利用式(1)计算校验更新并传输给相关的校验节点，如图4b所示。

相比于传统的星型数据更新方式(各个数据节点各自将数据传输给相关的校验节点)，CAU利用汇聚节点的转发，确实可以减少网络开销，尤其是跨机架的网络开销。然而，数据更新性能可以进一步优化。

1) 采用打包更新。因为大部分的数据更新量小(不超过4 KB)，而一般设置的块大小为1～64 MB。因此，在同一个机架中，如果同一节点有多个数据块进行了更新，可以采用tar打包模型进行校验数据更新。

2) 基于XOR进行更新。如前文所述，基于RS计算更新会产生大量的乘法运算，对于CPU资源开销较大，鉴于此，本文采用基于XOR的更新方法，在计算校验更新时，采用式(2)～式(7)，将有限域乘法与加法运算都转化为XOR运算。

如图5所示，在同一数据节点中，可能有多个数据块被修改(比如 $ {\rm{Node}}\;0 $ 的0号、6号数据块)，考虑到修改的数据量较小，本文采用tar打包的方式，如图6所示，将同一个节点的数据进行打包，增加一个头数据(用H表示)，头数据中记录该块所在的条带编号、块内起始位置、修改数据大小等信息。

如此，同一个块的大小可以容纳至少200个小更新(假设块大小为1 MB)，从而可在处理一个条带时，同时处理多个更新数据，然后按照CAU的传输模型进行数据更新。

同时本文发现在进行批处理更新时，同一个数据块(如 $ {\rm{Node}}\;0 $ 的0号数据块)可能会被多次修改，但是每一次修改的位置和大小不一定相同。这就需要在进行tar压缩时，对同一个数据块的多次访问进行记录和合并。如图7所示，假设数据块大小为1 MB，在进行批处理更新时，发现0号块有多次修改记录，于是，本文将多次修改的数据进行合并(XOR)，同时找出其中的最小和最大范围(rangeL和rangeR)，并将这2个值转化为块内起始位置和修改数据大小，记录到H。

从图7可以看出，TAR-CAU算法的优化空间是 $ {\rm{blockSize}}-({\rm{rangeR}}-{\rm{rangeL}}) $ ，优化代价是进行了打包与解包处理，增加了CPU开销。因此，TAR-CAU算法性能对于数据访问有一定的依赖性，优化效果与具体的数据访问记录有关。

本文通过微软剑桥研究院提供的真实数据集进行仿真实验，数据集记录了来自微软13个服务器，179块磁盘中36个分区一周内的访问日志，每条记录包含访问时间、请求地址、访问数据大小等信息，本文随机选择了3个数据集进行仿真测试，仿真实验平台采用Go语言环境搭建，通过改变块大小、节点数量等参数，以平均更新时间、吞吐量为指标点，与CAU算法、基本更新算法(简称Base)进行了比较。仿真环境如表1所示。

1) 平均更新时间

如图8所示，本文比较了3个数据集的平均单块更新时间，发现TAR-CAU算法更新效率最高，平均更新时间为0.0094 s，时间效率比BASE提高54%，比CAU提高30%。

2) 吞吐量

如图9a中，尽管本文提出的算法TAR-CAU需要在进行网络传输之前进行打包处理，增加了CPU开销，但是由于降低了网络传输的频率，因此，更新效率大大提高，在3种数据集中表现最佳，吞吐量比BASE提高了119%，比CAU提高了43%。

如图9b中，本文比较了常见的RS( $ n $ , $ {k} $ )配置：RS(4, 2)、RS(9, 6)、RS(16, 12)，机架容量(rack size)分别设置为2、3、4。仿真结果表明，TAR-CAU的吞吐量比CAU提高了44%。

如图9c中，通过改变块大小(block size)的实验对比发现，TAR-CAU的吞吐量提高了60%。

本文采用Go语言在Ubuntu 18.04平台实现了基于TAR-CAU算法的原型系统，并在本地局域网搭建集群进行测试，以了解在较为真实的环境中TAR-CAU算法的性能。局域网内部署了3台服务器(2台华为H12M-03，1台华为H22M-03)，利用pve虚拟管理平台^[14]搭建了虚拟机集群环境，共有13台虚拟机，网络拓扑结构如图10所示，主要由3个部分组成：中央控制器(central controller)、算法调度器(scheduler)以及节点代理(agent)。其中，中央控制器位于元数据服务器(metadata server, ms)中，负责整个流程控制，包括发送命令给节点代理、收集代理返回的响应ACK、统计时间和跨域流量等；而算法调度器是整个系统的大脑，负责根据指定的算法指挥中央控制器进行调度，算法调度器也位于元数据服务器中；节点代理负责接受中央控制器的命令，执行相关任务，并返回给上级ACK。

每台虚拟机的配置如表2所示。

为了模拟真实的网络环境，本文采用Linux tc工具^[15]进行网络带宽限制，设置机架内部带宽1 Gbps，机架外部200 Mbps，该设置可以根据具体的应用场景自行配置。与仿真实验一致，本文采用hm_0、hm_1、rsrch_1这3个数据集进行测试。

1) 平均更新时间

如图11所示，设置块大小为4 MB，实验结果与仿真结果大体相同，TAR-CAU算法表现最佳，平均单块更新时间为0.4544 s，相比Base节省约78%的时间开销，相比CAU节省近70%的时间开销。

2)吞吐量

如图12a所示，设置块大小为4 MB，通过3种数据集对比，在吞吐量方面，本文提出的TAR-CAU算法大大优于Base和CAU，平均吞吐量比Base高出9倍，比CAU也高出206%，这样的表现也是出乎意料。当然，值得注意的是，如前所述，TAR-CAU的算法性能依赖于用户访问数据的位置，如果rangeL和rangeR过于靠近边界(0和blockSize)，TAR-CAU的算法表现甚至会略弱于CAU。

图12b展示了不同块大小对各个算法的影响，当块大小较小时(如1 M)，CAU算法略优于TAR-CAU，原因可能是rangeL和rangeR过于靠近边界，导致打包产生的收益不如打包带来的额外开销。而随着块大小的逐渐增大，TAR-CAU算法的优势愈发明显，尤其是在块大小达到16 M以上时，频繁IO的开销逐渐成为了性能的主导因素，所以，仅传输delta值的TAR-CAU算法表现更佳。

由于引入了打包和解包过程，因此，TAR-CAU算法相比于CAU算法会产生额外的CPU开销，如图13所示，设置数据块大小分别为1、4、16、64 MB，同时随机产生100个数据块更新，每个数据更新的大小都不超过数据块大小的 $ 1/100 $ ，本文在一台虚拟机中测试打包与解包性能发现，打包与解包时间均不超过300 ms。因此，对于整体的数据更新性能影响可以忽略不计。

为解决云存储中数据更新的网络瓶颈，本文针对数据更新的网络传输进行了优化，基于CAU算法，提出了TAR-CAU，并针对数据更新量普遍较小的现象进行优化，将同一节点的多条带更新数据打包到同一条带进行处理。仿真实验和本地集群实验均表明，相比于CAU算法，当数据更新量较小时，本文的TAR-CAU算法能够至少提高44%的数据更新吞吐量。