测试分布式系统的线性一致性
一. 介绍
正确实现一个分布式系统是非常有挑战的一件事情，因为需要很好的处理并发和失败这些问题。网络包可能被延迟，重复，乱序或者丢弃，机器可能在任何时候宕机。即使一些设计被论文证明是正确的，也仍然很难再实现中避免 bug。
通常对于一个 key-value store，我们对于它在顺序操作下面的行为都能有一个直观的认识：Get 操作如果在 Put 的后面，那么一定能得到 Put 的结果。譬如，如果 Put("x", "y") ，那么后面的 Get("x") 就能得到 "y"，如果得到了 "z"，那么这就是不对的。
对于一个基于顺序规范的并发操作来说，我们会用一个一致性模型，也就是线性一致性来说明它的正确性。在一个线性一致性的系统里面，任何操作都可能在调用或者返回之间原子和瞬间执行。除了线性一致性，还有一些其他一致性的模型，但多数分布式系统都提供了线性一致性的操作：线性一致性是一个强的一致性模型，并且基于线性一致性系统，很容易去构建其他的系统。
测试：有了一个正确性的定义，我们就可以考虑如何去测试分布式系统了。通常的做法就是对于正确的操作，不停的进行随机的错误注入，类似机器宕机，网络隔离等。我们甚至能模拟整个网络，这样我们就能做长时间的网络延迟等。因为测试时随机的，我们需要跑很多次从而确定一个系统的实现是正确的。
线性一致性：一个更好的办法就是并发的客户端完全跑随机的操作。譬如，循环的去调用 kvstore.put(rand(), rand()) 和 kvstore.get(rand())，有可能会只用很少的 key 去增大冲突的概率。但在这种情况下，我们如何定义什么是正确的操作呢？在上面的简单的测试里面，因为每个 client 都操作的是一个独立的 key，所以我们可以非常明确的知道输出结果。
但是 clients 并发的操作同一堆 keys，事情就变得复杂了。我们并不能预知每个操作的返回值因为这并没样一个唯一的答案。但我们可以用另一个办法：我们可以记录整个操作的历史，然后去验证这个操作历史是线性一致的。
线性一致性验证：一个线性一致性验证器会使用一个顺序规范和一个并发操作的历史，然后执行一个判定程序去检查这个历史在规范下面是否线性一致。
二. 相关测试的系统
2.1 TLA+的形式规范测试
理论上，所有的生产系统都会有一个形式规范，而且一些系统也已经有了，譬如 Raft 就有一个用 TLA+ 写的形式规范。但不幸的是，大部分的系统是没有的。
2.2 使用Porcupine进行线性一致性测试
详见：http://www.jianshu.com/p/9aedd234ef62
2.3 使用Chaos测试分布式系统线性一致性
详见：
http://www.jianshu.com/p/2e65e6f37c76
三. 参考资料：
1. 测试分布式系统的线性一致性：http://www.jianshu.com/p/bddfce1494d6
2. 使用 Porcupine 进行线性一致性测试：http://www.jianshu.com/p/9aedd234ef62
3. 使用 Chaos 测试分布式系统线性一致性：http://www.jianshu.com/p/2e65e6f37c76
