Step 1

题目摘要引言

Title

The FuzzyLog: A Partially Ordered Shared Log

设计 partial order 的 shared log 抽象

Abstract

开篇点明 FuzzyLog 是针对 partial order 设计的 shared log 抽象。使用 partial order，就是可以支持并发 append（非线序）。利用基础的共享日志（baseline）可以便捷得获得 strong consistency、durability 和 failure atomicity。应用 partial order 信贷来：linear scaling（吞吐量和容量），weaker consistency guarantees 以及 tolerance to network partitions（可以容忍网络分区）。

编写 Dapple 实现 FuzzyLog 抽象，以及一些利用 Dapple 实现得数据结构和应用（特别提到一个 ZooKeeper 的实现。

简易性（应用实现仅百余行），linear scalability 的日志，灵活的一致性保证（比如 CC+）和 network partition tolerance。

Introduction

背景多次提及，分布式系统中的 control plane services（举例 filesystem namenodes， SDN controllers），由于持久性、高可用性以及可扩展性需求从单机维护逐步转移为分布式维护。传统的 Paxos 和 2PC 复杂，不够高效。

最近研究的 shared log abstraction，汇集程全局共享日志来服务诸多应用。构建在 shared log 抽象上的服务简单，利用高层次的 API（最终对应日志的 append 和 read），使用 shared log 提供的 strong consistency，durability，failure atomicity 和 transaction isolation。

（话锋一转）然而简单的 shared log 需求强制全局全序，作者认为它是昂贵、难以实现而且最重要的非必要的。先前的工作表明中间尺度（小集群、数十台）使用旁路的序列器模式是可行的，然而，更大规模情况下，强制 total order，吞吐量和网络带宽/延时是昂贵的，作者对于一些操作，并不需要被 order，所以提出了本文关键问题：

Can we provide the simplicity of a shared log without imposing a total order?

给出 FuzzyLog 抽象的要求：durable、iterable 并且 extendable。用 partial order 代替传统 shared log 的 total order。内部使用染色机制，一个颜色表示一个独立的、全序的链。相同颜色的链通过交叉连接起来表示因果关系的更新。完整的 DAG——由多种颜色（每个 shard 占据一个）以及每种颜色的多条链（每个 region 表示一条）——在每个 region 中都完全备份，并 lazy synchronize。

一个 shard 使用一种颜色，并运行在单一区域的 FuzzyLog 等价于一个传统的 shared log。

Dapple 以及提及的使用 FuzzyLog 的重新实现：

• CRDTMap（284 LOC）：提供了 causal+ consistency，在 FuzzyLog 上构建 CRDT
• CAPMap（424 LOC）：提供强一致性，但缺少网络分区
• ZooKeeper clone（1881 LOC）： 基于 FuzzyLog。
• 提供 Red-Blue consistency 的 Map，以及支持事务的 CRDT

基本理论概况

结论部分

主要贡献：

• 提出了通用形式的偏序 shared log 抽象（退化版本为全序 shared log）
• 表明该抽象的易用性，基于其 API 简化构建某些实现
• 表明该抽象的实际可行性，构建 Dapple

回答基本问题

1. 类别

   原型系统描述

2. 内容

   shared log 系列：Corfu，Tango，vCorfu，Scalog，Boki

3. 正确性

   存疑

4. 创新点

   提出的第一个偏序的 shared log 抽象，并基于此 API 构建了众多实现。

5. 清晰度

   存疑

阅读选择

Step 2

细读笔记

Motivation

分析传统 shared log 机制的 pros and cons

• Simplicity
  • 提供简易的 share log API 免于复杂的协议来实现关键共嗯那个
  • shared log 是一致性的关键，共写，读回
  • 同时提供了 log 的历史审查功能
• Drawbacks
  • Expensive：始终围绕释放潜能，提供更大的吞吐量
    • 传统的 leader 选举/no shard，限制为单一设备 I/O bandwidth
    • Corfu：由 sequencer 指定 order，再放置数据，限制为 sequencer 更新计数并分发的速度（约 600K ops/sec）
    • Tango, vCorfu： 分别使用了 streams 和 materialized streams，支持 selective playback
  • Impossible：
    • 在存在网络分区的时候期望的 total order 无法实现，见参考文献 Towards robust distributed systems PODC 2000

作者认为主要有下面几个维度限制了旁路构建 sequencer 模式的进一步扩展：

• network diameter：序列器位于网络中的固定点，最远端的客户端的通信代价必然高昂。
• network bindwith：序列器不是 IO-bound 或易于并行的（意思后半句话解释了），不能跟上 I/O bandwidth 的数量级增速。
• payload granularity：log payload 的粒度维度，shared log 应用的 payload 不会很大（大的目标通常限制为 64-bit 指针指向 external blob store）。作者提到如果 payload 增加，对 sequencer 的效率要去会更严格（要求达到接近 1 billion ops/s）
• system size: 系统大小维度，如果扩增到支持四十台服务器，我们需要接近 2 billion ops/s 的序列器。

已发表的构建在功能齐全的系统中的序列器及其能力：

• CORFU: 200K ops/s
• NOPaxos: 250K ops/s
• Tango: 600K ops/s
• Stand-alone sequencers（比如无需 per-stream state 的计数器）
  • RDMA-based counters 122M op/s 见Design Guidelines for High Performance RDMA Systems

总结动机，shared log 是一种简化的提供强语义支持的模式，但强制 total order 代价过于昂贵且有时不可满足（网络分区情况）。如何打破僵局？partially ordered shared log abstraction

The FuzzyLog Abstraction

partially ordered shared log abstraction （实现形式为 FuzzyLog Abstraction）提供 partial ordering API（实现形式为 FuzzyLog API）

FuzzyLog 是一种 DAG，提供了 partial order 操作的两个重要模式支持。

1. 划分了多个 logical data shards：可以由多个 clients 并发地更新。Chuannan：个人理解，传统的 total order 虽然没有提 logical data shard，也支持多个 clients 并发更新，只是需要 ordering layer 或者 sequencer 来序列化。
2. 在跨地理区域部署时，应用较弱的一致性来避免跨区域的在请求的 critical path 上的开销

为了清晰，术语作如下解释：

1. node表示 FuzzyLog DAG 上的一个节点。
   1. 每个 node 可以被标记上一种或多种颜色
   2. 颜色将应用的状态划分为多个 logical shards
   3. 某种颜色的 node 表示对该对应颜色 logical shard 的更新

每种颜色是一个全序排列的链的集合，每个区域（region）一个链，跨链的箭头表示 causality 因果关系。每个区域分配一个颜色。每个区域都有每种颜色全部但暂时陈旧的拷贝副本（虚线表示远程 node），DAG 的一条割表示当前区域看到的视图。对于自己区域的链保持最新。Clients 仅与自己区域的 DAG 本地拷贝沟通，他们可以在 local chain 上 append 记录来改写拷贝。

FuzzyLog API

• new_instance call: client 创建一个 FuzzyLog shard（逻辑 shard），需要指定颜色，另外也可以提供描述像的 snapshot ID 快速构建 fuzzy log（避免从头构建日志）
• sync：用于同步状态，sync 操作会先取下当前快照，执行自上次 sync 调用后所有 new nodes（日志操作），一旦所有 new nodes 都通过 passed-in callback 的形式传递给 sync 发出端，sync最后返回一个不透明？的 ID 来描述当前的快照。这些 nodes 会以 DAG 的逆拓扑排序序被本地看到。无跨链箭头的不同链上的 nodes（操作）可以以链间任意序被看见（序无关）。
  • 返回的 Snapshot 的 ID 可用来与其他 clients 维护的 instance 来比对 snapshot 是否匹配。
• append：用于本地更新操作，加入新的 node 作为本地链的链尾，边指向原链尾，另外还有指向最近看见的远程链链为的交叉边（是每一个好像是的，因为是因果关系，描述的是“看见”）。
• trim：garbage collection 相关，提供一个描述 snapshot 的 snapshot ID 来表明该像不再需要。

sync和trim操作仅对单一颜色使用，append可以对多颜色集进行操作，这表明将实际操作的 node 加入多个颜色的本地链尾。

语义：单颜色跨区域的操作是因果一致的。即二者序确定仅当其中一个操作在另一个操作被提出时已被“看到”，在这种情况下，DAG 的图示上会有一个边表示。DAG 的内部结构保证收敛性，即便并发更新以不同顺序执行：由于本地 client 只更新本地链，对于 general 的 DAG 的不相交集，所以并发更新不会产生冲突。在单一 region 内的操作是 serializable 的。最后一句话不太明白，it does not necessarily respect real-time ordering when append operations span multiple colors。似乎是append操作 span 多个颜色的时候不需要遵守现实时钟。

Discussion：对 FuzzyLog API 设计一些 trade-off 的考量，先前的设计有考虑过向程序员暴露所有链（exposed chains），并允许在其任何子集上 append/sync，并选择某一一致性保证。这个版本的 API 使可扩展的实现变得更加困难。比如对任意子集的拓扑排序可能要求我们去遍历每条边。另外，一致性选择则要求 programmers 去推理各种组合的性能和可用性（举了 strong consistent multi-appends 为例）。（后面解释了如何促成了现在的版本）We were able to drastically simplify the API once we realized the equivalence between colors and shards.

FuzzyLog Applications

本节讨论应用如何使用 FuzzyLog API（with a case study）。

从最基本的 LogMap 来说明，提供put/get/delete的 KV 操作，对于 FuzzyLog 来说，一个 LogMap server 相当于一个 client。

• get的实现，先调用 FuzzyLog 的sync，保证本地视图最新，要求任何更新（对 FuzzyLog 的 append）必须被本地看到。
• put/delete的实现，会在 FuzzyLog 上append一个新的 node，然后等待sync将该更新作用在本地视图。

当然这最基本的 LogMap，仅用 193 行就完成了，实现了可持续性，高可用性，强一致性。并发控制和故障原子性。它等同于基于传统 shared log 的先前实现。当然这种强制的 total order 限制了一些能力。本节后续部分介绍基于 LogMap 构建的其他应用，如何进一步释放 FuzzyLog 的真正潜力。

Scaling with atomicity within a region

潜力一：scalability：scale linearly。

ShardedMap（开始介绍颜色了！）每个 server 储存一个 shard，这个 shard 对应一种 FuzzyLog 的颜色。对特定 shard 的更新就意味着对某一颜色的 FuzzyLog 更新。

隔离的重要性！通过 color，避免了增加 server 时不必要的通信，完全的隔离就意味着，scale linearly。

AtomicMap 支持 atomicity：对多个 shard 的原子更新。

• multi-put的实现，将更新作用于一个颜色集合，即在各颜色的 FuzzyLog 都append一个 node（标记 put 操作）。这里不理解点的是这句。因为multi-color appends 是 serializable，所以 AtomicMap 也是 serializable 的，不是 linearizable 或者 strictly serializable。这三者的区别：

Much work on databases and distributed systems uses serializability as the basic correctness condition for concurrent computations. In this model, a transaction is a thread of control that applies a finite sequence of primitive operations to a set of objects shared with other transactions. A history is serializable if it is equivalent to one in which transactions appear to execute sequentially, i.e., without interleaving. A (partial) precedence order can be defined on non-overlapping pairs of transactions in the obvious way. A history is strictly serializable if the transactions’ order in the sequential history is compatible with their precedence order...

...Linearizability can be viewed as a special case of strict serializability where transactions are restricted to consist of a single operation applied to a single object. Nevertheless, this single-operation restriction has far-reaching practical and formal consequences, giving linearizable computations a different flavor from their serializable counterparts. An immediate practical consequence is that concurrency control mechanisms appropriate for serializability are typically inappropriate for linearizability because they introduce unnecessary overhead and place unnecessary restrictions on concurrency.

TXMap，进一步支持带有更强隔离等级的 read/write transactions，使用 Tango 中相同的协议。

• commit的实现，TXMap 的 server 回在 read-write 操作对应的颜色集中append a speculative intention node，这一段先 pass。有意思的是在 FuzzyLog 本身仅 serializable 情况下提供了 strict serializability。

Weaker consistency across regions

一些应用可以容忍更弱的一致性保证，一个常见例子是因果一致性。

CRDTMap：提供空间维度，更弱的一致性支持，引入多个 region，单颜色（不涉及隔离维度）。

• put的实现，仅对本地的 chain，即 FuzzyLog 记录append一条记录，与其他区域的 chain 是异步更新的。

为了确保当 server 看到因果独立（而非依赖）的更新以不同序出现时，状态是收敛的，使用了 Observed-Remove set CRDT。（查询一下这个结构）

Tole rating network partitions

问题记录

未读（且值得读）文献记录

Step 3

主要是实现细节

思路复现

Dapple Design/Implementation

设计的一些要点

• scalability： reads 和 appends 必须是可线性拓展的（随着 colors 增加） 对应我思考中的隔离维度的实现
• space efficiency： FuzzyLog partial order（带有这些 node 和 edge 标记）必须被紧凑的存储。
• performance： append 和 sync 操作必须以 low latency 和 I/O overhead

Dapple 在名为 chainservers 的物理存储 servers 上实现 FuzzyLog 抽象，每一个储存多个 in-memory log-structured address spaces。Dapple 对 FuzzyLog 的状态作了划分：

• 每个颜色进存储在一个分割（partition）中
• 每个分割（partition）通过 chain replication 进行复制

然后对单颜色和多颜色操作的实现

Single-color operation

Dapple 将每个链储存在一个单独的 log 中。对于一个在\(R\)个区域（region）的部署，那么每个区域都会实际存储\(R\)个日志，对应\(R\)条链，其中对应本地 region 的 log（local log）会由 client 写，剩下的是其余区域链的异步福本。

Server （指的这些存储节点）暴露三个 low-level 的 API 接口：

• log-append：append 一条 log
• log-snapshot：接受 a set of logs 并返回当前尾部位置
• log-read

Client 实现某一颜色上的sync，即log-reads得到日志序列后执行log-snapshot，log-snapshot的返回值可以作为该颜色的一个向量时钟，表示当前 local region 看到的链的情况，这实际上就是sync返回的 snapshot ID。上部 APIappend会使 client 调用log-append写入 local log。新的写入会包含向量时钟记录已经看到了那些，因此每个写入按照 FuzzyLog 的抽象，都包含对已观察到的指向。sync递归 fetch 依赖来保证传送这些 nodes 保持 DAG 序。

每个 chainserver（链服务器）阶段性地与其他远程地区的同伴进行通信，更新它们的 shadow logs 和新的写入。为了获取信心，它们自身相当于远程 chainserver 的 client 并使用sync，这样保证了依赖关系（TODO：为什么？）

Dapple 对每个分割使用 chain replication，每个log-append操作，会传递这条链并在末尾被接受。一旦 client 获得一个 snapshot，随后的log-append可以由任意 replica 来执行。复制协议与系统设计是正交的：我们也可以使用 Multi-Paxos。

Multi-color operations

涉及多颜色的操作，由于 FuzzyLog 的 API 支持添加一个 node 到多颜色。在 Dapple 实际实现中，这要求可以自动地在多个日志中添加：每个颜色一个对应的本地日志链。使用了 Skeen 算法。

Skeen 的原始算法会为跨多 server 的多个 client（而非添加到一个 server）的操作产生一个序列化的值。但原始版本并不处理容错，在我们的设置中，每个‘server’是 chainserver 复制的 partition，可被认为是不会 fail 的。这里提出的 Skeen 针对较低频率的 client 故障，增加了三种容错机制-leases，fencing 和 WAL。

Skeen variant detail

Leases： 所有 client 的操作都依赖一个粗粒度的租期，从每个 server 获得或者从每个分区的复制链头获取。如果租期过期，或者复制链头变更，操作会被拒绝。

Failure-free operations

1. Phase 1，origin client 发送请求，每个 server 会将该 multi-append 操作加入 pending queue并返回return timestamp\(X.Y\)，其中\(X\)表示 logical clock 而\(Y\)是 server-specific 标识。另外，origin client 提供一个 WAL 入口由每个 chainservers 存储。一旦 client 收到所有 chain-servers 的返回 Timestamp，会计算\(Max\)值并发送给 chainservers 并启动 Phase 2。
2. Phase 2：这个\(Max\)标识 multi-append。当一个 chainserver 收到这个消息，会将 multi-append 操作从 pending queue 移入 delivery queue。
   • multi-append 的执行规则，等待 pending queue 中没有 return timestamp更小的操作，并且delivery queue 中没有比其 max timestamp更小的操作。条件满足则移出delivery queue并执行。
   • 观察图中例子

上述的协议通过两阶段完成，不属于关键路径，还有一个过程涉及 client 发送 clean-up 消息来删除 per-append state（the WAL，以及表示上次执行阶段的状态图）。lazily executed。

Recovering a stuck multi-append

典型如 Client 故障重启，三个 phases：隔离原始客户端或者其他恢复客户端的活动，确定系统状态，完成 multi-append。

• Phase 1（fncing phase）：访问原始客户端（存储在 WAL 中）的 lease set，并使其在 servers 无效并重写新的 recovery

有关协议的正确性！

We wrote conventional proofs as well as a machine-checked proof in Coq. We wrote conventional proofs as well as a machine-checked proof in Coq

证明与推理复现

We wrote conventional proofs as well as a machine-checked proof in Coq.

Related Work

相关工作回顾。

实验验证复现