The FuzzyLog -- A Partially Ordered Shared Log

The FuzzyLog: A Partially Ordered Shared Log

0x00 引言

这篇Paper是关于Shared Log优化的一个文章，前面的Corfu就是一个典型的Shared Log的系统。FuzzyLog的基本思路是放宽Shared Log中的Log之间的顺序关系，使用偏序而不是全序。再次的基础之上，FuzzyLog认为大部分的操作都只会设计到一个数据分区，FuzzyLog就使用每一个数据分区维护自己分区的方法，这样可以增加操作的并行性；另外，在跨地理区域部署是，通过降低一致性来避免在关键路径上面的同步跨区域协调，因此FuzzyLog也可以实现并发访问不同的区域，即使是对同一个逻辑的数据分区。偏序而非全序的设计使得FuzzyLog可以提供更加好的拓展性(在不牺牲原子性的同时实现容量和吞吐的线性拓展)，可以通过更弱的一致性以及容忍网络分区，

... retain the simplicity (100s of lines of code) and strong semantics (durability and failure atomicity) of a shared log design while exploiting the partial order of the FuzzyLog for linear scalability, flexible consistency guarantees (e.g., causal+ consistency), and network partition tolerance. On a 6-node Dapple deployment, our FuzzyLog-based ZooKeeper supports 3M/sec single-key writes, and 150K/sec atomic cross-shard renames.

0x01 FuzzyLog抽象

与前面的Corfu的论文有所不同，在这篇Paper中突出说明的是FuzzyLog的抽象和应用。FuzzyLog被抽象为一个DAG图，每一个操作(Log项)每称为一个节点(不是服务器节点，而是这个Log)，这些Log根据关系组织为DAG图。在这个DAG中，一个节点会被标记1种or多种的颜色。标记的颜色将应用的状态划分为逻辑上的分区。每一个颜色的节点的结合是全序的，节点之间的边表示来节点之间的因果关系，一个颜色的节点就表现为一条链，每一个区域会有一条。每一个区域会包含一个颜色标记的节点，可能包含以及过时的节点。FuzzyLog的API是很简洁的，只包含很少的几个操作，

// constructs a new handle for playing a color
FL_ptr new instance(colorID color, snapID snap=NULL); 
// appends a node to a set of colors
int append(FL_ptr handle, char *buf , size_t bufsize , colorset *nodecolors);
// synchronizes with the log
snapId sync(FL_ptr handle, void (*callback)(char *buf, size_t bufsize));
//trims the color
int trim(FL_ptr handle, snapID snap) ;

其中的sync操作被客户端用来与FuzzyLog同步器状态。一个sync调用形成一个在本地区域存在节点的一个快照，本“播放“自上次sync操作新添加的节点。sync操作会有一个回调函数，会返回一个不透明的snapID，

 A sync takes a snapshot of the set of nodes currently present at the local region’s copy of a color, and plays all new nodes since the last sync invocation. Once all new nodes have been provided to the application via a passed-in callback, the sync returns with an opaque ID describing the snapshot.

FuzzyLog使用trim操作来表明一个snapID对应的快照的节点不会再使用，一个节点有多个颜色标记的情况，trim操作只会设计到操作的颜色标记而不会影响到其它颜色标记。在创建一个日志实例的时候，也可以提供一个snapID，“播放”节点的时候会跳过这些节点，这个的主要用途就是在新的客户端加入的时候不需要从头“播放”节点。在append和trim操作中，因为FuzzyLog中可能有多个颜色的表示，这个两个API也是支持同时操作多个颜色标记的，append对多个颜色标记的操作是原子的。

fuzzylog-sync

在FuzzyLog中，跨区域的在一个颜色上面的标记会是因果一致性的(causally consistent)，也就是说两个客户端在不同区域对同一个颜色标记的操作只有在一个看到了另外客户端的操作的时候才会是排序的(有顺序关系)，在这种情况下，两个节点之间会存在一条DAG图中的边。在一个区域内操作都是序列化的(serializable)。

0x02 FuzzyLog应用

使用FuzzyLog实现的几个应用，

LogMap，这个是一个简单的Key/Value Map的实现。Log会实现为一个区域内的一种颜色标记的Log。每一个使用LogMap的服务器会有一个Map的拷贝，保存在内存中，支持 put/get/delete等操作。通过连续的sync操作使得本地的副本保持一个最新的view。get操作就是等待sync操作完成，然后在本地的Map副本上面操作即可，对于put/ delete操作来说，就是添加一个节点到一个Log中，然后等待sync操作返回。
ShardedMap & AtomicMap，与LogMap相比，ShardedMap使用了多个颜色标记，每个服务器也只保存了Map 的一部分。在LogMap的基础上只要修改颜色参数即可。FuzzyLog支持原子性的跨分区访问，如果一个muilt-put的操作是直接地添加而不用返回一个值，AtomicMap就是在添加的时候使用一组的颜色标记而不是一个。FuzzyLog支持的多颜色标记添加满足Serializable，所以AtomicMap也满足Serializable，但是不满足Linearizable or Strictly Serializable。
TXMap，FuzzyLog使用和Tango[2]系统的协议来实现读写事务。服务器使用推测性的方式执行读写事务，它会追踪读的数据项集合和缓冲写的数据项的集合。为了提交一个读写事务，TXMap通过在多个颜色标记的Log中添加一个Speculative Intention节点，当一个服务器在遇到了这个节点之后，它会通过检查这个事务涉及到的数据项在自己分区的部分来决定这个提交是yes还是no。

CRDTMap，CRDTMap使用一种更弱一致性Map的实现，它使用一种颜色标记，会在多个区域内复制。CRDTMap的实现就是简单地使用一种颜色标记来更新一个Map。在一个区域内的更新会异步地更新到另外的区域中，这里的因果一致性就是依赖于FuzzyLog本身的特性实现的。

To achieve convergence when servers see causally independent updates in different orders, we employ a design for CRDTMap based on the Observed-Remove set CRDT, which exploits commutativity to execute concurrent updates in conflicting orders without requiring rollback logic. The CRDT design achieves this by predicating deletions performed by a server on put operations that the server has already seen; accordingly, each delete node in the DAG lists the put operations that it subsumes.

CAPMap，CRDTMap可以实现在网络分区的时候的可用性，但是会牺牲一致性。CAPMap可以实现在没有网络分区的时候提供强一致性，在有网络分区的时候提供因果一致性。CAPMap使用一个put操作然后使用sync操作直到其返回的方式，不同的地方在于CAPMap通过使用一个代理的方式来实现服务器之间的通信操作。在没有网络分区的时候，服务器的put操作是通过代理在一个主区域实现append操作，然后使用sync在自己的区域看到这个新节点，一个put操作才算完成。在网络分区发生的时候，服务器切换到早本地的一个区域进行append操作。对于这些操作，CAPMap会使用一个Flags值标记出来。在网络分区幸福之后，CAPMap会进行类似合并的操作，
```
  When the network partition heals, servers at the secondary stop appending locally and resume routing appends through the proxy at the primary. Every routed append includes the snapshot ID of the last sync call at the secondary client; the proxy blocks the append until it sees a subsuming snapshot ID on a sync, ensuring that all the nodes seen by the secondary client have also been seen by the proxy and are available at the primary region.
```
TXCRDTMap，结合TXMap和CRDTMap的设计；RedBlueMap支持RedBlue Consistency……

fuzzylog-apps

0x03 设计与实现

Dapple是Paper中FuzzyLog的一个实现。Dapple要求满足scalability、space efficiency和performance三点的要求。在Dapple中，存储服务器被抽象为chainserver，每一个会有多个日志式结构的保存在内存中的Log的地址空间。Dapple会将FuzzyLog的状态分区保存在这些chainservers上面，每一个颜色标记的保存在一个Dapple的分区内，每一个分区会使用Chain Replication的方式来复制，同时Dapple的设计中假设使用的内存为battery-backed DRAM。

单个颜色标记的操作。Dapple将一个颜色的Chain保存在单个的Log中。在多个分区的部署中，一个客户端会写入其中的一个分区(本地分区)，然后异步地复制到其它分区，这部分的Log被称为Shadow Logs。Log使用三个基本的API来实现FuzzyLog的API，

... Clients implement the sync on a color via a log-snapshot on the logs for that color, followed by a sequence of log-reads. The return value of log-snapshot acts as a vector timestamp for the color, summarizing the set of nodes present for that color in the local region; this is exactly the snapshot ID returned by the sync call. The client library fetches new nodes that have appeared since its last sync via log-read calls. When the application calls append on a color, the client library calls log-append on the local log for that color. It includes the vector timestamp of nodes seen thus far in the new entry;

多个颜色标记的操作，Dapple多个颜色标记上面的操作基于Skeen’s algorithm。针对原始的Skeen’s algorithm不能容忍参与者失败的问题，Dapple中认为服务器会存在多个副本，可以认为不会故障。对于客户端的故障，Paper中认为这个不是很常见的，这样Dapple的实现要求一个在没有客户端的故障的时候可以快速工作在发生这个故障的时候可以接受比较慢但是安全的方法。Dapple使用了三种基本的方法：Leases, Fencing,和 Write-ahead Logging。TODO[2].

0x04 评估

这里具体的信息可以参看[1],

fuzzylog-perf

参考

The FuzzyLog: A Partially Ordered Shared Log, OSDI’18.
Tango: Distributed Data Structures over a Shared Log, SOSP’13.