光与影的个人博客

NEUCoder

0%

链式复制论文总结

发表于 更新于 分类于 ，

链式复制及其改进

写在前面：CRAQ还涉及到了服务器放置策略等内容，我目前阶段学习并不关心，所以没有深入了解

论文：Object Storage on CRAQ High-throughput chain replication for read-mostly workloads

本文主要提出了一种区别于主从备份容错方式的链式复制容错方式，通过将备份服务器组织链结构，实现数据的冗余备份。本文中的CRAQ(Chain Replication with Apportioned Queries) 是在链式复制（Chain Replication）的基础上改进而来的，两者针对对象存储系统设计实现（object-based storage system），对象存储系统主要包括一下两个操作原语：

  1. write(objID, V)：更新某个obj关联的值
  2. read(objID): 获取某个obj的值

对象存储只需要考虑修改读取特定对象的请求顺序，而并不需要考虑整个数据库，降低了保证一致性的成本

链式复制（CR:Chain Replication）

链式复制的原理容易理解，通过将多个存储数据副本的服务器组织成链式形式，在响应读取、更新请求时在链上进行传播处理，拓扑结构如下图所示

  1. 所有的写请求wirte 由Head节点服务器处理，计算得到状态后，在链上传播直到tail节点提交后，向client返回ack完成写请求
  2. 所有读请求read 由Tail节点服务器处理，直接查询本地值返回client

其中链式复制保证强一致性（strong consistency）

  • 所有写请求只有在TAIL提交后才对client可见
  • 所有的读请求均在TAIL节点处理，返回TAIL数据

链式复制的特殊请求处理机制保证了所有请求按照其发出的顺序处理，所以实现了强一致性。

请求重发

While it would be possible to ensure that each request reaching the storage service is guaranteed to be performed, the end-to-end argument suggests there is little point in doing so.

论文中有意思的一点是认为由服务器保证接收到的请求一定被处理是”得不偿失“的

  • 由客户端在请求超时一段时间后，向服务器重新发送请求
  • 链式复制容错实现机制中，可能会丢弃一部分服务器接收到但未处理的请求

由客户端重发请求引出另外一个问题：如果请求超时是由于客户端未收到服务器处理成功响应，重新发送请求会导致重复执行操作，需要保证操作的幂等性（idempotent）

  1. 读操作：读操作不改变系统状态，是幂等的
  2. 写操作：论文中没有写怎么解决，只是说可以通过客户端查询判断是否更新已经在server执行，从而避免重发请求

应对失效

要理解CR如何应对实现，首先要理解链上的server的下两个状态

  1. $Hist_{objID}$：当前副本已提交的状态更新列表（实际上的待处理写请求，所有server均维护自己的该状态），其中尾节点的$Hist^{tail}_{objID}$定义为全局已提交的写请求
  2. $Pending_{objID}$：待处理的读取请求列表，只有tail节点存储当前状态

不同节点之间的hist状态满足以下Update Propagation Invariant性质：即后继节点的待提交状态更新是前驱节点的前缀子集（从读请求从头节点向后传播容易理解）

针对不同节点的失效，CR分情况处理（CR假设了一个永不失效的master节点负责维护节点信息，处理失效情况。实际上master
是由paxos算法实现多主从容错）

  1. 头节点失效: 后续节点取代它成为头节点
  2. 尾节点失效：前驱节点成为新的尾节点
  3. 中间节点失效：类似于从链表中删除节点操作，更新服务器拓扑结构

其中情况2会导致尾节点的待处理请求丢失，然而这在系统中是允许的（把重传的职责交给client）。由于上述Update Propagation Invariant性质的保证，不会丢失写请求。

情况3会导致忘记更新传播的情况

  • T-节点将更新传播给了T节点，T节点还未来得及传播给T+,T节点失效，导致T-认为已将更新向后传播，T+实际上未收到更新的情况
  • 由master节点在维护链拓扑时，比较T-和T+的$Hist_{objID}$列表，找出两者缺失部分，提醒T-节点重传

问题

  1. 尾节点处理所有读请求，负载过大
  2. 写请求按照链式传播，导致写请求的延迟过高（理论上链越长，更新延迟越大，相当于增加了server反而降低了性能）

CRAQ（Chain Replication with Apportioned

Queries）

CRAQ针对CR只能在尾节点处理读请求的问题进行了改进，实现了任意节点的读取，缓解了负载问题

  1. 每个副本server为对象维护一个原子递增的版本号，同时存储多个版本的对象值，每个版本的对象值带上一个是否提交的标志（clean or dirty）

  2. 当副本server收到修改对象请求（还是从头向后传播），增加版本号大小并将更新值添加到版本值列表中

    • 若当前节点非TAIL，将当前值标记为dirty,向后继节点传播

    • 当前节点为TAIL，标记当前节点为clean（完成更新提交），反向沿链传播ack，接收到ack的节点，更新值状态为clean，并删除存储的历史版本值

  3. 当副本server首先读取对象请求，根据最新版本对象值是否为clean执行不同操作

    • clean：直接响应client请求
    • dirty：询问tail节点，获得最新version的clean值，响应client请求（反向ack还未传播完全）

应对失效

与CR一致，区别在于管理和容错的master节点不再自己实现（paxios），而是借由第三方分布式协调服务服务实现，如zookeeper等（懒狗，不重复造轮子是吧）

相对于CR的改进

首先多版本的对象值能够根据应用需求，实现不同的一致性保证（不要更好的一致性，当然是为了更好的性能）

  1. 强一致性：论文中描述的即保证强一致性的操作，即只读clean数据
  2. 最终一致性：允许节点返回未提交的新数据，但是单个节点不能读到历史数据（在CRAQ中，即允许读取dirty数据）
  3. 带有最大不一致要求的最终一致性：允许节点返回未提交的新数据，但是需要满足一定约束，（例如单个客户端不能读到历史数据，即每次读取version必须单调递增）

最后也是最重要的性能提升

  1. Read-Mostly Workloads（读操作为主的负载）：读操作可以在所有节点执行，吞吐量随着server增加而增加
  2. Write-Heavy Workloads（写操作为主的负载）：写操作过多，会导致大部分非tail节点的数据均为dirty，转而大部分查询请求询问尾节点，然而此情况仍然优于所有读请求由尾部处理的情况

补充

CR和CRAQ中为什么要使用master节点管理和监控链上节点状态？

如果不使用外部节点，我们的只能通过前驱或者后继节点相互感知，当节点失效时，由其后继或者前驱替代的方式实现容错，然而这样会出现脑裂问题

  • 当tail与前驱节点出现网络分区（CAP中的P）问题时，显而易见此时前驱节点会认为TAIL失效，自己成为tail,此时出现了两个TAIL即脑裂问题
  • 头节点失效类似，也会出现脑裂问题

所以必须采用外部的权威节点(共识算法：raft、paxos 或分布式协调服务：zookeeper)，来监控整体状态，决定谁是tail或者head

总结

正如MIT6.824中所说的当我们使用多个服务器提供服务时，我们首先应该考虑使用N个服务器是否能够带来N倍的性能/吞吐量提升，或者线性提升，然而实际情况中受限于算法实现、一致性的保证、服务器拓扑，性能提升往往是低于预期的。

CRAQ通过简单的链式结构+符合直觉的错误恢复机制，实现了容错备份，但是性能部分有所取舍

  1. 写入沿链传播，随着链长度的增加，写入延迟增加（增加服务器反而性能下降）
  2. 读取通过一系列优化，近似实现了任意节点的随机读取（增加服务器，近似线性提升处理性能）

然而链式更新传播，相较于raft、zookeeper等的由master节点广播传播的方式，降低了master节点通信负载

  • master节点广播形式需要传n-1个节点，链式传播每个节点只需要负责传播自己的后继节点

zookeeper、CRAQ以及GFS的例子，告诉我们一个道理：三个和尚没水喝，如果没必要别搞分布式，费力不讨好