Distributed System Paper

论文阅读-Managing Update Conflicts in Bayou, a Weakly Connected Replicated Storage System

Posted by keys961 on April 30, 2019

1. Introduction

Bayou是一个支持复制、弱一致的存储系统，针对网络不理想的情形设计。

Bayou实际上是一个多主复制的数据库，客户端可向任何副本写入，无需协调。

它会产生冲突，因此Bayou提供自动冲突检测和冲突解决（单个操作粒度下），保证数据一致性和安全性，且保证数据依旧可用。

例如网络非常不好的时候，可把写操作写入当前客户端，此时客户端可视作一个主节点。

2. Bayou的应用

Bayou适用于非实时的协作应用程序（如共享日历、共享邮件、会议室安排、书目数据库、程序开发、支持离线的共享文件编辑），也适用于不同时间由不同主机的个人使用的应用程序。

3. Bayou基本系统模型

Bayou中：

  • 每份数据会在许多服务端节点上复制
  • 客户端通过RPC和服务端节点交互（支持读、写，写包含插入、修改、删除）
    • 客户端的写入被服务端接受后，不需要等待服务端将变更传播，直接可以返回
    • 客户端对选择服务端的节点没有限制
  • 客户端和服务端可处于同一台机器上

而多主架构，势必引入冲突，因此：

  • 写入需要额外信息，如检测和解决冲突的必要信息，且每次写入需要全局唯一的WriteID
  • 使用反熵传播本节点的一系列写入，并检测和解决冲突，使数据达成一致
  • 只要网络不永久分区，写入最终会被传播到所有服务端节点，达到最终一致

arch

4. 冲突检测和解决

4.1. 适应应用程序的语义

Bayou提供两种机制，以满足任何应用程序的冲突检测和解决：

  • 依赖检查
  • 合并过程

上述机制应用于每次写入操作，且内部逻辑都可以自定义，以满足不同应用的需求。

下述是每次写入时的逻辑：

# 参数依次为: 更新数据，依赖检查逻辑，合并过程逻辑
Bayou_Write(update, dependency_check, mergeproc) {
    # 依赖检查
    if (DB_Eval(dependency_check.query) <> dependency_check.expected_result) {
        # 冲突，则合并
        resolved_update = Interpret(mergeproc);
    } else {
        resolved_update = update;
    }
    DB_Apply(resolved_update);
}

4.2. 依赖检查

依赖检查包含2个参数：应用提供的查询、期望结果。

当查询的结果和期望结果不同时，冲突产生，然后执行合并。

Bayou的依赖检查可以检测写-写冲突（传统实现为向量时钟或时间戳）：

  • 检查需要更新的数据项
  • 保证从写提交后开始，对应数据项没有改变

Bayou的依赖检查也可以检测读-写冲突（传统向量时钟做不到）：

  • 指定更新依赖的数据项预期值
  • 模拟分布式数据库的乐观并发控制解决冲突

由于Bayou依赖检查的灵活性，它可以实现很多其它的功能，如保证数据完整性依赖等等。

4.3. 合并过程

合并过程在检测到冲突后调用，以解决冲突。它可嵌入一些数据，并可在当前副本执行任何的读取。

合并过程可被自定义，并被封装，上层不需感知它（除非自动合并不能完成）。

当自动合并无法完成时：

  • 合并过程依旧会完成，但会产生一个revised update，并记录合并时无法解决的冲突（如通过日志形式）
  • 之后，用户可根据记录的冲突，手动合并数据

合并过程中，Bayou不会锁定副本，副本依旧可用。

5. 副本一致性

Bayou保证副本的最终一致，只要所有的写能通过反熵进行写入传播，而下面2个特性是实现最终一致的基础：

  • 在所有的服务节点上，写操作顺序明确定义且相同
  • 冲突检测和合并过程是确定的，保证冲突检测和解决的行为在所有节点上都一样

写入分为两类:

  • tentative write（暂定）：根据时间戳<ts, server_id>（单调递增）排序
    • 对于时间戳，服务端对每个新写入维护一个单调递增的逻辑时间戳，以在全局下依旧保持因果顺序（见Lamport时间戳）
    • 逻辑时间戳往往和同步时钟接近，但反熵时可能需要将时间戳增加（调快）
    • 服务节点需要有undo & reapply写入操作的能力（因为写入可能从客户端也可能从其它服务节点来），保证顺序一致
  • committed write（已提交）：最终的结果，根据提交时间排序，且排在任何tentative write之前
    • 每个服务节点维护一个写入日志，根据时间戳排序，committed在前，tentative在后，节点根据该顺序执行写入
    • 实际上时间戳为<commit_ts, ts, server_id>，未提交的请求commit_ts可设为无穷大，commit_ts单调递增

合并过程确定性的保证：

  • 合并过程只能依赖于当前节点的数据，以及合并过程自身产生的数据
  • 设置访问边界，超过边界外的数据（如服务器环境信息）不能保证确定性，若访问则返回失败

6. 写稳定性与提交

写稳定：该写请求最后一次执行已完成（Note：反熵会造成undo和redo），即该写入之前的写入，在日志上的位置已经固定

提交过程：当写入被显式提交，写入才算稳定（因此已提交和稳定等价）。已提交的写会排在日志开头，和反熵协议一起，服务节点可以知道哪些写入已被提交，以提供稳定性。

Primary commit：Bayou使用“主节点提交”机制来提交数据

  • 指定一个主节点，接管提交过程，主节点的选取可根据数据副本按需指定
  • 节点（包含主节点）通过反熵，从其它节点获取更新（主要是tentative write），并进行排序
  • 主节点会分配递增的commit_ts，提交写入，然后通过反熵传播给其它节点
  • 同步不需要投票选举，适合弱连接的网络环境

Bayou会尝试，但不能保证已提交写的顺序和所有暂定写的时间戳顺序一样，当主节点先看到新的更新时，会造成顺序不同：

  • A更新<-,10,A>$W_1$，B更新<-,20,B>$W_2$，主节点为C，正常下应该：$W_1, W_2$
  • A由于一直断线，C先看到B，$W_2=$<5,20,B>，并将其提交
  • A终于上限，C看到A，$W_1=$<6,10,A>，并将其提交
  • 此时顺序变为$W_2, W_1$

反熵：后台进程不断查找不同副本之间的差异，将缺少的数据从一个副本复制到另一个副本，但有明显的同步滞后

  • 对于已提交的记录：根据日志上的时间戳，直接同步缺失区间即可
    • 日志上的时间戳为<commit_ts, ts, server_id>
  • 对于暂定的记录：根据向量时间戳，发送缺失的区间
    • 这里向量时间戳类似于<x:ts_x, y:ts_y>，x,y为对应的数据项

write_anti_entropy

7. 存储系统实现的问题

存储系统实现分为3个部分：

  • Write log：当前节点收到的所有写请求，根据<commit_ts, ts, server_id>排序
    • 当数据稳定后，相关的日志项可以丢弃（Bayou会保留一部分，有助于增量反熵）
  • Tuple store：存储数据，数据由日志顺序生成，是一个内存式关系式表，支持部分SQL查询，它维护2个视图
    • Committed view：只包含已提交写
    • Full view：还包含暂定写
    • 实现时，为了节省空间，只需每个条目额外附带2个bit，表明它出现在哪个视图上，假如格式为[c/f]：
      • 01：只存在Full view中
      • 10：存在于Commit view，也存在于Full view中
      • 11：存在于稳定存储中（被checkpoint了）
    • 已提交日志项产生的Tuple store会被checkpoint到稳定存储中，以加速恢复
  • Undo log：记录并用于回滚tentative write，以便于重新执行它们

每个节点维护一系列时间戳向量，格式均为<a:ts_a, b:ts_b, ...,>，保证相同的写请求不会被重新接受，并决定反熵需要传输的数据范围（后2个）：

  • O Vector：记录最新的日志项已丢弃（omitted）的写入时间戳
  • C Vector：记录最新的已提交（committed）的写入时间戳
  • F Vector：记录最新已执行的暂定写入时间戳（即full）

整体架构图如下：

storage_arch

节点加入和离开（假定节点为Z）：

  • 加入：
    • Z与某个节点X通信，获取server_id = <ts_z, X>
    • X生成一项Z:<-,ts_z,X>，通过反熵传播到集群，表明集群知道Z加入了

  • 离开：直接关闭即可，集群是不会收到影响的

  • 例外——分辨2种情况（版本向量不会包含Z）：Z加入后马上离开，Z根本没加入

    1
2
3
4
5
6
7
8
9
10

    假定Z的ID = <20,X>
  A --> B
    A拥有Z的日志项<-,25,<20,X>>
    B的向量不含Z项--如何区分：B从没发现Z，B发现了Z已经离开
  One case:
    B的向量: [X:10, ...]
    10 < 20 表明B从没感知Z的存在
  The other case:
    B的向量: [X:30, ...]
    20 < 30 表明B感知到Z的存在，且知道Z已经退出

8. 访问控制

以一个data collection为粒度，并通过非对称加密，实现访问控制和相互认证。

Bayou使用3种认证来授予、委托和收回data collection的访问权：

  • AC[PU,P,D]：授予用户权限P（如read, write, server）于data collectionD，PU为用户的公钥
  • D[PU,C,PY]：将公钥为PY的用户下的证书C委托给另一个公钥为PU的用户
  • R[C,PY]：收回公钥为PY的用户下的证书C
CATALOG
    FEATURED TAGS
    Algorithm Java Network Distributed System Stream Processing Operating System Paper Linux Redis etcd Kubernetes C++