1.4.1 并发执行

并发执行是保证分布式算法正确性的一大挑战。

假设有一个进程p，它有m步，分别为s₁， s₂，…， s_m。如果只分析这一个进程的执行轨迹，显然只有一种执行轨迹，即s₁， s₂，…， s_m。如果要求s_i先于s_j执行，只需要在代码中确保第i步在前、第j步在后即可。

但对于多进程并发执行的分布式系统，情况则复杂得多。假设有一个全局时钟负责记录每个进程的每一步发生的时间点，然后根据每一步发生的先后顺序写成一个序列，就得到了一个执行轨迹。假如有n个进程p₁， p₂，…， p_n，每个进程的步数为m，进程i的第j步表示为p（i， j）。如果n=m=2，那么该分布式系统可能的执行轨迹有6种：

<p(1,1), p(1,2), p(2,1), p(2,2)>

<p(1,1), p(2,1), p(1,2), p(2,2)>

<p(1,1), p(2,1), p(2,2), p(1,2)>

<p(2,1), p(2,2), p(1,1), p(1,2)>

<p(2,1), p(1,1), p(2,2), p(1,2)>

<p(2,1), p(1,1), p(1,2), p(2,2)>

通过多重集合的全排列公式可知，执行轨迹共有种可能。我们把所有可能的执行轨迹的集合称为执行轨迹空间，它与进程数和步数的乘积的阶乘成正比。一看就知道，这不是什么好事。

仅仅令n、m为2、3、4，就可以发现执行轨迹空间爆炸的速度是惊人的。如果进程数n=2，且每个进程的步数m=2，那么执行轨迹有6种；如果进程数n=3，且每个进程的步数m=3，那么执行轨迹有1680种；如果进程数n=4，且每个进程的步数m=4，那么执行轨迹则高达 63063000 种！面对爆炸式增长的执行轨迹空间，如何确保每一个可能的执行轨迹是正确的，对于开发者而言是一个巨大的挑战。

此外，基于消息传递的分布式系统没有共享内存，从而也没有所谓的信号量或锁，因此编程难度更大。另外，需要说明的是，尽管一些分布式框架（如ZooKeeper等）提供了信号量、锁等更高层语意的封装，但本书研究的是实现分布式框架的内在原理，而非使用这些分布式框架提供的外在接口。