最近完成了 fly.io 推出的和分布式系统有关的一些挑战，感觉挺有意思的。这篇文章分享一下最后一道题的思路。

题目

最后一道题的原文在这里。它要求我们实现一个支持 transaction, totally-available, read committed 的分布式 K/V 数据库。

第一个版本的思路

我的思路其实有点偷懒。因为这个挑战的框架提供了一些支持 linearizability 的中心化 KV 数据库（但是不支持 transaction），所以我就基于这个数据库实现了一个 WAL。每一次提交事务就只需要把事务里的所有写操作 append 到这个数据库里就行。对于读操作，我们可以通过 apply WAL 里面所有（可见的）写操作，来获取实际的数据。为了避免每次都 apply 全部的 WAL，每个 node 还会维护一个 snapshot。

这个版本已经可以在 QPS 比较低的情况下通过 part a 了。但是一旦 QPS 变高，最终的 WAL 会变得非常长，导致测试框架出问题。第二个版本解决了这个问题。

第二个版本的思路

既然问题是 WAL 太长，那我们定期把不需要的 WAL 清理掉不久好了。显然，如果一个 WAL entry 包含在所有 node 的 snapshot 中，我们就不再需要这个 entry 了。

为了判断 WAL entry 是否在所有 node 的 snapshot 中，在这个中心化数据库中我们为每一个 node 维护一个 watermark，watermark 之前的 entry 都已经包含在了这个 node 的 snapshot 中。通过计算这些 watermark 里面的最小值，我们可以知道哪些 WAL entry 可以被删除了。

分析

Transaction

为了保证事务的原子性，每个 WAL 的 entry 包含了一个事物所有的写操作。这样，当我们在内存里 apply 一个 WAL entry 的时候，就可以保证这个 entry 里面的所有写操作都会被 apply。这样，我们就可以保证事务的原子性。

Totally Availablility

这个系列的第二个挑战解释了什么是 totally available： 即使出现了网络问题（network partition），服务还是能正常工作。按照我的理解，这里说的网络问题是指 node 之间无法通讯，但是 node 还是可以访问框架提供的 KV 数据库。显然，因为上面描述的思路不需要 node 之间进行通讯，所以它是 totally available 的。

Read Committed

因为只要插入 WAL 我们就认为一个 transaction 已经 commit 了，所以我们只能读到 committed 的修改。