论文研读（2019.1~2019.2）

最近比较关注纠删码存储系统中数据更新的文章，做个小总结，以便理清思路。

Shen，et al.《Cross-Rack-Aware Updates in Erasure-Coded Data Centers》

摘要：该文章关注于数据更新中引起的的跨机架传输数据问题，提出了CAU算法。该算法包含三部分：（一）选择性的数据更新方案，根据更新模式和数据块的布局来选择更新方案以减少跨机架流量（二）数据块布局重组，将同步更新的数据块尽可能地放在同一机架（三）临时复制，为了保证在数据更新时的可靠性，为每个更新后的数据块准备临时副本。

主要内容：数据更新中的小写更新主要分为RMW（读改写）和RCW（重构写）。作者提出的更新方案数据RMW类型，同时RWM可分为基于数据增量和基于校验数据增量两种。

（1）选择性的数据更新方法。为了避免频繁的校验更新，CAU算法采用一种迭代的追加-提交程序来进行数据更新，即分为两个阶段，追加数据阶段和提交增量数据阶段。如图2。图3是更新的两种方案。

其中，在图3上，数据-增量提交和校验 - 增量提交之间的关键区别在于在哪计算奇偶校验块的变化。在数据-增量提交中，我们在Rj里面计算奇偶校验块的变化，其中存储奇偶校验块;相反，在校验-增量提交中，我们首先在Ri中计算奇偶校验块的变化，然后将结果发送到Rj。这两种方法都会产生不同数量的跨机架更新流量。 CAU执行以下决定：如果i'≤j'，则CAU执行数据-增量提交;否则，它执行校验 - 增量提交。因此，跨机架更新流量的量是min {i'，j'}。i'表示以数据-增量提交形式下更新时引起的跨机架流量，j'表示以校验-增量提交形式下更新时引起的跨机架流量。

但作者也提出，该方法不一定达到理论上的最小跨机架更新流量，因为在数据增量提交中，作者将所有数据块视为不同，但如果它们相同，我们可以仅从Ri向Rj发送一个数据增量块。此外，在奇偶校验增量提交中，我们独立更新每个奇偶校验块。但是，如果底层擦除代码允许从另一个奇偶校验块（例如，RDP [10]）计算一个奇偶校验块，我们可以从Ri到Rj仅发送一个奇偶校验块（而不是j'奇偶校验 - delta块），并且计算Rj中的所有奇偶校验块。如何找到理论上最小的跨机架更新流量将作为未来的工作。

（2）数据块重组。该问题可由下图说明：

从图中可以看出，如果我们将需要更新的数据块尽可能地放在同一个机架上，则可以减少跨机架的流量。但是，在进行数据块重新布局时，即将另一个需要更新的数据块迁移到最多需更新数据块的机架时，也会引起跨机架的流量，因此需要通过算法计算数据布局变更前后的跨机架流量消耗，找出消耗最小的数据布局方案。这既是作者提出的第二个算法-数据布局算法。

（3）临时副本。为了防止在追加数据阶段中更新后数据块的丢失，CAU算法将实施临时副本策略，对更新后的数据块尽快临时存储（在另外一个机架上存储更新后数据块的副本），直到实行提交阶段后将它们删除，这样副本就不会引起额外的存储开销，同时保证更新时的可靠性。

最后是CAU算法的系统架构：

元数据服务器(Metadata Server)管理正在存储的每个块的元数据信息，包括块(chunk)ID，块所属的条带(stripe)ID，存储块的数据节点ID，以及校验节点ID。它还记录更新数据块的块ID以及在附加阶段期间具有数据块更新的条带ID。

追加阶段：客户端首先将更新的请求与更新的数据块的块ID一起发送到元数据服务器（步骤1）。元数据服务器返回访问权证（步骤2），其指出存储数据块的数据节点ID，存储数据块的副本以用于临时复制的校验节点ID，以及校验节点ID，其中校验节点ID块将存储在提交阶段。客户端将访问权限附加到新数据块并将数据块发送到相应的数据节点（步骤3）。数据节点将更新的数据块附加到其附加日志（步骤4），并且还将更新的数据块的副本转发到另一个机架中的校验节点（步骤5）。校验节点存储副本（步骤6）并将ACK返回到数据节点（步骤7）。最后，数据节点向客户端发送ACK以完成更新请求（步骤8）。

提交阶段：元数据服务器触发提交阶段以更新校验块。它首先识别从其记录的信息更新数据块的所有条带。对于每个条带，它向所涉及的数据节点发送提交请求，并指定是否应使用数据-增量提交或校验-增量提交，并且数据节点相应地发送数据-增量或校验-增量块。每个校验节点在完成校验更新时向元数据服务器返回ACK。当元数据服务器从所有n-k个奇偶校验节点接收到ACK时，它确保正确提交条带。

总结：CAU算法是一个解决了分层特性问题的跨机架感知更新机制方案，通过选择性的更新方案和数据块布局重组减少了跨机架流量，同时采用临时副本机制来保证数据更新时的可靠性。