好久没更新了，这篇文章，我是来扯淡的。回忆一下过去。

零

想起当年刚开始实习的时候，我的第一个任务就是——写一个抽奖程序。虽然业务需求很简单，但是老大给我提了一些问题，让我深深地学习、思考了一番：

• 怎么保证安全？千万不要一个奖品被两个人抽到了。
• 怎么保证性能不要太差？
• 很多人同时抽，怎么减少冲突？等等。

经过这个简单程序的锤炼，当时的我对数据库^[1]、事务^[2]、隔离级别^[3]开始有了比较深的了解，而不再仅仅停留在课本上。从那个时候开始，我就觉得，数据库真是个神奇的东西，特别是 SQL 和事务。

一

刚毕业的那一两年，那个时候负责某个业务。某天，某个业务挂了，原因是 DB 挂了，然后备机也有问题，切换不了主备。结果可想而知，造成了严重的影响……

然后，整个部门开始“大跃进式”地 review 各个业务的数据存储的容灾情况。当时手上刚好有个小业务用了 MySQL 作为存储。问了一下运维的同学，发现这个 DB 用的竟然只是异步复制，主备切换无法保证数据一致性，极端情况下，备机的数据可能落后较多。

当时简单调研了一下 MySQL 的半同步复制，所以就有了这篇文章：MySQL半同步复制^[4]。半同步复制不是一个完美的方案，所以后来 MySQL 又推出了新的复制方式 MGR(MySQL Group Replication)^[5] —— 用 Paxos^[6] 来做复制容灾。我赶紧把 Paxos 的论文（Paxos Made Simple）^[7]下载下来拜读，结果看了几遍都没太看懂——压根想不到它和数据库的复制容灾有半毛钱关系。

后来才了解到有一个比 Paxos 更好懂的分布式共识算法 —— Raft^[8]。真牛逼啊，我赶紧把论文下载下来拜读，还好这次基本能看懂——虽然实际细节其实还有很多坑，但是基本原理清清楚楚的。可惜，由于这与当时手上的工作没半毛钱关系，所以蜻蜓点水式学习后便弃坑了，先乖乖地用 MySQL 的半同步复制吧。

二

故事当然不会就这样结束。后来有一个业务，遇到了“分布式事务”的问题——数据不是保存在同一个数据库的，但是业务上需要保证两份数据的“一致性”。更确切地讲，保证最终一致^[9]即可。

当时的解决方案很简单：业务上将逻辑设计成可重入（幂等）的，然后“重试”到成功。重试操作的高可用由一个高可用的分布式队列来解决。

虽然当时将接口设计成幂等的，但是刚开始调用“分布式事务”解决方案时思考过一个问题：分布式队列能不能保证一个请求刚好只成功执行一次？经典的 exactly once 问题。当时主要看了几篇 Kafka 相关的文章，比如 Exactly-once Support in Apache Kafka^[10]、Exactly-once, once more^[11]。

先说结论：Exactly once 是不可能的。

虽然有一些文章、系统喜欢卖弄，声称自己能支持 exactly once —— 实际上肯定是要业务配合。因为这里出队是否成功其实是由业务来决定的。业务说成功就成功，业务说失败就失败。但是业务还有可能超时。超时了，如果分布式队列认为成功，实际上业务上是失败了，则变成 at mostly once。超时了，如果分布式队列认为失败，实际上业务上是成功了，则变成 at least once。这种时候，如果操作是幂等的，那一切就会简单很多。在分布式环境中，充满着各种不确定，各种重试，不幂等的核心业务操作其实很危险。超时，是分布式系统中的魔鬼。所以，还是老老实实在业务上保证操作的幂等吧。

三

数据量大了之后，开始思考扩展性的问题。自己用 MySQL 做分片，扩容起来就是很蛋疼。水平扩展是分布式系统的标配——所有不支持水平扩展的分布式系统都不配姓“分布式”。

GFS^[12] 的 master + chunk server 架构是一个经典的分布式系统架构。master 保存元数据。Chunk server 保存实际数据。Chunk server 在 master 的管控下，支持水平扩展。这种架构存在的一个问题就是，master 可能成为系统的瓶颈。所以设计的时候，一般需要尽可能减少元数据的大小、数量。

P2P^[13] 是另一种经典的分布式架构，代表作是 Dynamo^[14]。

研究 MySQL 扩展方式的时候，当时的 NewSQL 开始崭露头角。我最开始了解到的是 TiDB^[15] 和 Cockroachdb^[16]。两个都是借鉴了 Google Spanner^[17] 的论文，当然也各有特色。

顺着 spanner 这条路，刷了一波它的“周边论文”。比如它的 SQL 层 F1^[18]。比如 Google 内部的其它一些存储系统 ——  bigtable^[19]、megastore^[20]。

Spanner 的分布式事务实现依赖 TrueTime，第一次看论文的时候，真的不太看不太懂。TiDB 的分布式事务实现模型来自 percolator^[21]，基于中心化的授时节点和两阶段提交，论文中的例子也很详细、很好理解。Omid，另一种分布式事务实现模型，也非常好理解，这个系列有四篇论文之多，但是都很容易看懂：

• Omid: Lock-free Transactional Support for Distributed Data Stores^[22]
• Omid, Reloaded: Scalable and Highly-Available Transaction Processing^[23]
• A Critique of Snapshot Isolation^[24]
• Taking Omid to the Clouds: Fast, Scalable Transactions for Real-Time Cloud Analytics^[25]

四

单机存储引擎。虽然严格来讲不属于分布式系统。但是，实际上也是不可缺少的一环，毕竟，分布式系统也是由一个个单机组成的。单机存储引擎的数据结构挺多的，常见的有 Hash Table^[26]、LSM-Tree^[27]、B-Tree^[28]/B+Tree^[29] 等。

之前刷过一波 LSM-Tree 相关论文，还做了个 ppt —— A Study of LSM-Tree^[30] 总结了一下。

其它数据结构，现在还不是特别了解，也想找时间了解一下它们的的细节。

五

大概就扯到这吧。

当然，本文只是记录了几个关键节点，很多琐碎的细节也没法都回忆起来。

全程自己自由摸索，中间肯定走过很多弯路的……

参考资料