随机测试能有效的发现网络隔离下的 Bugs 吗？

在使用 Jepsen 和我自己折腾的 chaos 的时候，我都有一个困惑，就是这些测试能测出来问题吗？

譬如对于 Jepsen 来说，它会启动一批节点，运行要测试的集群，然后会执行一些网络隔离操作，将整个集群分成多个块，并且在各个块上面都会执行操作，然后恢复集群，然后进行一些收尾的操作。最后我们会根据操作的历史来验证系统是否满足线性一致性。因为判断线性一致性是一个 NP hard 的问题，所以我们实际的操作数量不可能特别多。对于 Jepsen 来说，超过 1 千条历史，验证的时候就很容易发生 OOM。Chaos 虽然是用 Go 写的，快不少，但数量也不可能太多。

所以这就有了我上面的困惑，到底这些测试能不能发现问题？刚好，前一段时间看了一篇 Paper，Why Is Random Testing Effective for Partition Tolerance Bugs?，里面作者也提到了同样的问题，跟我只会怀疑困惑不同，他们直接用数学证明了问题。

首先，我们需要明确，为什么这里重点关注的是网络隔离。对于从事分布式研发的同学来说，CAP 理论一定会非常的熟悉，该理论通俗的解释就是只要是分布式系统，一定会存在网络隔离的情况，那么我们的系统就是要考虑到底是满足完全的可用性，还是保证一致性，也就是在 P 一定存在的情况下，选择 C 还是选择 A 的问题。对于很多数据库系统来说，譬如 etcd，TiDB，一定是一个 CP + HA 系统，也就是说，在 P 出现了，我们要保证 C，如果出现了数据不一致的情况，那么就意味着我们的实现是有 bug 的。

说完了网络隔离，我们下一个要考虑的就是 coverage 的问题，这里我们并不是说的通常测试的 coverage（也就是有多少行被测试覆盖了），但原理差不多，我们这里需要知道的是在网络隔离的 coverage 情况，论文的作者将其分成了三种：

• k-splitting：假设我们有 n 个进程，那么我们就会将其分成 k 个不同的区间。我们可以遍历所有 k 的情况得到 splitting coverage。对于通常的网络隔离来说，其实就是 2-splitting。
• (k, l)-separation：在分布式系统中，通常一个进程都会有 Role 的区分，譬如 Raft 里面的 Leader 和 Follower。对于 separation coverage 来说，我们就是将 k roles 和 l roles 进行隔离。对于 Raft，也就是 (1, 2) separation。如果我们不能知道各个进行的 role，就需要遍历所有的情况了。
• minority isolation：这个大家应该都比较了解，譬如现在 Leader 被隔离在 minority 的区间里面，该 Leader 是否能下线，而 majority 的那边能否选出来一个新的 Leader 进行服务。

Jepsen 支持了上面几种 coverage，通常它仅仅使用一些常用的 coverage 方式，就测试出了很多的 bug，譬如 k-splitting 的 2-splitting 和 3-splitting。那么能找到 bug 的概率大概是多少呢？具体详细的证明我是没看的（如果看懂的同学欢迎过来面基），但根据 paper 作者的说法，只要设计合理，即使这些很小的随机测试，至少能有 80% 的概率能发现 bug，这已经非常高了。

当然，随机的测试只是能有效的找到 bug，并不能保证 100% 找到。所以我们还有其他的做法来更多的发现问题，譬如 A randomized scheduler with probabilistic guarantees of finding bugs。更进一步，为了保证从设计上面就是正确的，我们也可以直接使用 TLA+。

分布式系统的测试是一件非常困难的事情，做这块这么久了，我很大一个感触就是写出一个分布式系统真的不难，难的是你怎么确定它是对的。从事分布式系统的测试，对于个人技术能力的提升是非常大的，我甚至觉得比纯写分布式系统得到的提升都要大。这块我们做了不少工作，但远远不够，如果对这块感兴趣，欢迎联系我：tl@pingcap.com。