零基础入门分布式系统 8. 案例研究 Case studies （完）

8. 案例研究 Case studies

8.1 Collaboration and conflict resolution

协作软件是一个广泛的软件类别，它可以促进几个人一起完成某些任务。这包括Google Doc/Office 365（多用户文本文档、电子表格、演示文稿等）、Overleaf（协作式LaTex文档）、多用户图形软件（如Figma）、项目计划工具（如Trello）、笔记应用程序（如OneNote、Evernote、Notion），以及同事或家庭成员之间的共享日历。

现代协作软件允许几个人同时更新一个文件，而不必通过电子邮件来回发送文件。这使得协作成为复制的另一个例子：用户打开文档的每个设备都是一个副本，对一个副本的任何更新都需要通过网络发送到其他设备上的副本。

原则上，协作软件可以使用线性一致化的复制方案。然而，这样的软件使用起来会很慢，因为每一个读或写的操作都必须联系quorum副本；此外，它不能在离线设备上工作。相反，为了更好的性能和对网络中断更好的稳健性，大多数协作软件使用乐观复制，提供强最终一致性。

在本节中，我们将研究一些用于这种协作的算法。作为例子，考虑一下第7.3节中的日历同步问题。两个节点最初以相同的日历条目开始。在节点A上，标题从"Lecture"改为"Lecture1"，同时在节点B上，时间从12:00改为10:00。这两个更新发生时，两个节点暂时无法通信，但最终连接还是会恢复，两个节点同步了它们的更改。上图所示的结果中，最后的日历条目既反映了标题的变化，也反映了时间的变化。

这个场景是conflict resolution冲突解决的一个例子，当对同一个对象的几个并发写需要整合到一个最终状态时，就会发生conflict resolution冲突解决。Conflict-free replicated data types 无冲突复制数据类型（CRDTs for short 简称CRDT），是一系列执行这种冲突解决的算法[Shapiro et al., 2011]。CRDT是一个复制对象，应用程序通过抽象数据类型的接口来访问对象。

上图显示了一个CRDT的例子，它提供了一个从键到值的映射。应用程序可以调用两种类型的操作：读取给定键的值，以及设置给定键的值（如果该键尚未存在，则添加该键）。

每个节点的本地状态由包含（timestamp时间戳, key键, value值）三元组的values集合组成。读取给定键的值是一个纯粹的本地操作，只检查当前节点上的values，不执行网络通信。该算法保留了一个不变的原则，即对于任何给定的键，values最多包含一个元素。因此，当读取一个键的值时，如果它存在，该值一定是唯一的。

为了更新某个键的值，我们为该操作创建一个全局唯一时间戳（Lamport时间戳是一个不错的选择）然后广播一个包含时间戳、键和值的消息。当该消息被递交时，我们检查本地的values副本是否已经包含了相同键的更高时间戳条目；如果是，我们忽略该消息，因为具有更高时间戳的值优先。否则，我们将删除之前的值（如果有的话），并将新的（timestamp时间戳, key键, value值）三元组添加到values中。这意味着我们可以使用last-writer-wins (LWW) 的方法来解决对同一个键的并发更新。

上述算法使用可靠的广播执行复制的方案，不需要全序递交。它是一种基于操作operation-based的CRDT，因为每个广播消息都包含一个更新操作的描述。它允许在没有网络连接的情况下完成操作，因为可靠广播的发送者可以立即将消息传递给自己，并在之后的某个时间将其发送给其他节点。此外，尽管消息可能在不同的副本上以不同的顺序传递，该算法也能确保最终的一致性，因为更新副本状态的函数满足交换律。

上图显示了同样处理map数据类型的另一种CRDT算法。values的定义和读取键值的函数与之前相同。然而，更新的处理方式是不同的：不再广播每个操作，而是直接更新values，然后广播整个values。当向另一个副本传递该信息时，我们使用合并函数\sqcup 将两个副本的状态合并起来。这个合并函数比较具有相同键的条目的时间戳，并保留那些具有较大时间戳的条目。这种广播整个副本状态并将其与另一个副本的状态合并的方法被称为基于状态state-based的CRDT。

state-based方法的缺点是，广播信息可能比operation-based方法要大。但优点是它可以容忍丢失或重复的消息：只要两个副本最终成功地交换了它们的最新状态，它们就会收敛到相同的状态，即使一些早期的消息已经丢失。重复的信息也是中性的，因为合并操作是幂等的。这就是为什么基于状态的CRDT可以使用不可靠的best-effort广播，而基于操作的CRDT需要可靠的广播（有些甚至需要因果广播）。

此外，基于状态的CRDT并不限于使用广播的复制系统。其他复制方法，如quorum写算法和反熵协议，也可以使用CRDT来解决冲突。

另一个并发更新和需要解决冲突的例子，我们将考虑协作软件，如Google Docs。当你在Google Doc中打字时，这些按键会立即应用到浏览器中的文档的本地副本，而不需要等待它们同步到服务器或任何其他用户。这意味着，当两个用户同时打字时，他们的文档可能会暂时出现分歧；随着网络通信的进行，系统需要确保所有用户都收敛到文档的同一视图。

我们可以把一个可协作编辑的文本文档看作是一个字符列表，每个用户都可以在列表中的任意索引处插入或删除字符。字体、格式、嵌入式图像、表格等各种元素就会进一步增加复杂性，所以我们现在只专注于纯文本。当几个用户可以同时更新一个文本文档时，就会出现一个特别的问题，如下图。

在这个例子中，两个用户A和B从同一个文档开始，"BC"。用户A在文件的开头添加了字符"A"，这样就变成了"ABC"。同时，用户B在文件的末尾添加了字符"D"，使之成为"BCD"。由于A和B合并了他们的编辑，我们期望最终的文件应该是"ABCD"。

上图中，用户的副本通过互相发送他们所做的操作来进行交流。用户A向B发送（insert，0，"A"），而B应用这个操作，得到了所需的结果 "ABCD"。然而，当B向A发送（insert，2，"D"），A在索引2处插入字符"D"，结果是 "ABDC"，而不是预期的 "ABCD"。

问题是，在B执行insert(2, "D")操作时，索引2指的是字符"C"之后的位置。然而，A在索引0处同时插入的效果是将所有后续字符的索引增加1，所以"C"后面的位置现在是索引3，而不是索引2。

解决这个问题的一种方法是Operational transformation操作转换。有一系列不同的算法使用这种方法，它们在解决冲突的细节上有所不同，下图说明了它们共同原理。

一个节点会跟踪它所执行操作的历史。当一个节点收到另一个节点的操作与它自己的多个并发操作时，它将transform转换与它相对的操作。

函数T(op_1, op_2)接受两个操作：op_1是一个传入操作，op_2是一个并发的本地操作。T返回一个转换后的操作op_1{'}，使得将op_1{'}应用于本地状态具有op_1想要的效果。例如，如果op_1=(insert, 2, D)和 op_2=(insert, 0, A)。那么转换后的操作是T(op_1, op_2)=(insert, 3, D).因为原来在索引2的插入op_1现在需要在索引3执行，因为在索引0的存在并发插入。另一方面，T(op_2, op_1)=op_2返回未修改的op_2，因为索引0处的插入操作不受随后在文件的之后位置并发插入的影响。

当考虑到删除、格式化等因素时，转换功能变得更加复杂，我们将跳过这些细节。然而，这种方法在实践中被广泛使用：例如，Google Docs中的冲突解决算法使用了基于Xerox PARC研究系统Jupiter的操作转换方法[Nichols et al. , 1995]。这种方法的一个局限性是，它要求用户之间的通信使用全序广播，需要使用一个指定的领导节点来排列更新，或者使用共识算法。

操作转换的一个替代方案是使用CRDT进行文本编辑，它避免了对全序广播的需要。使用索引来识别文本中的位置，需要进行操作转换。而文本编辑CRDT通过给每个字符附加一个unique identifier唯一标识符来工作。即使周围的字符被插入或删除，这些标识符依然保持不变。

上图显示了一种unique identifier唯一标识符的结构。在这里，每个字符都被分配了一个有理数i \in \mathbb{Q}，0<i<1\vdash来代表文档的开始和\dashv 代表结束；这些符号是算法内部状态的一部分，对用户来说不可见。

当我们想在位置 i 和 j 的相邻字符之间插入一个新的字符时，我们可以给这个新的字符分配一个位置号，(i+j) / 2，这个位置号总是在i和j之间。只要我们使用arbitrary-precision任意精度（浮点数的精度有限），这个新的位置总是存在的。但也有可能两个不同的节点同时生成具有相同位置号的字符，因此我们可以使用当前节点ID来区分相同位置字符的先后关系。使用这种方法，解决冲突变得很容易：一个特定位置的插入可以简单地广播给其他副本，然后将该字符添加到他们的字符集中，并按位置号排序，获得当前的文档。

上图显示了text CRDT算法。一个副本的状态由集合chars表示，它包含**(position 位置, nodeId 节点ID, character字符)**三元组。函数ElementAt遍历chars的元素。它首先找到position最小的元素，如果多个元素有相同position，则选择有最低nodeId的元素。如果index=0，我们返回这个最小的元素，否则我们删除最小的元素，递减index，然后重复。(这是一个相当慢的算法）。

一个副本的chars被初始化为\vdash和\dashv 元素。为了得到某个特定index的字符，我们使用刚才定义的ElementAt，在索引上加1，以便跳过chars中的第一个元素(0,null,\vdash)。

要在一个特定的位置插入一个字符，我们要得到紧邻的前一个和后一个位置p_1和p_2，然后计算新的位置(p_1+p_2)/2。然后通过因果广播来传递这一操作。在传递insert信息时，我们只需将该三元组添加到chars中。

为了删除某个特定位置的字符，我们使用ElementAt，像以前一样加1跳过\vdash，以找到该字符的位置和nodeId。然后，我们通过因果广播delete该字符的唯一标识。当delete消息被递交时，副本将从chars中删除与消息中的位置和节点Id相匹配的元素（如果它存在的话）。

在这个算法中使用因果广播（而不仅仅是可靠的广播）的原因是为了确保如果一个字符被删除，所有的副本在处理删除之前都会处理该字符的插入。这个限制是必要的，因为插入和删除同一个字符的操作是不相通的。然而，不同字符的插入和删除是相通的，这使得该算法能够确保收敛性和最终强一致性。

8.2 Google's Spanner

尽管名字里有"强"字，但强最终一致性是一个相当弱的一致性属性：例如，当读取一个值时，不能保证该操作会返回最新的值，因为更新从一个副本传播到另一个副本可能需要一些时间。与此相反，我们现在来看看一个不同的系统，它的一致性保证要强得多。与以往一样，这些保证是有代价的，但是对于某些应用来说，这是一个正确的选择。

谷歌开发的Spanner数据库[Corbett et al., 2012]是一个提供最强一致性保证的系统：事务具有可序列化隔离和原子承诺，线性一致化读写。Spanner实现了这些特性的同时保持了很好的可扩展性，支持大数据量、大交易吞吐量，并允许数据在全球范围内分布。Spanner的副本被设计成位于数据中心。

Spanner使用的许多技术都是非常传统的，我们在本课程的前面已经看到了这些技术：它使用Paxos共识算法进行状态机复制，使用两阶段锁来确保事务之间的可序列化隔离，使用两阶段提交来确保原子承诺。为了使这些算法在实践中运行良好，需要进行大量的工程设计，但在架构层面上，这些成熟的选择并不令人惊讶。

然而，Spanner因其设计的一个非常不寻常的方面而闻名，即它对原子钟的使用。这就是我们在本节中要重点讨论的方面。使用时钟的原因是为了实现无锁只读事务lock-free read-only transactions。

一些只读事务需要读取数据库中的大量对象；例如，备份或审计过程基本上需要读取整个数据库。用两阶段锁来执行这样的事务将是非常具有破坏性的，因为备份可能需要很长的时间，而且对整个数据库的读锁会阻止任何客户在备份期间向数据库写入数据。出于这个原因，大型只读事务可以在后台执行，而不需要任何锁，因此不会干扰并发的读写事务，这一点非常重要。

Spanner通过允许事务从数据库的consistent snapshot一致性快照中读取，来避免对只读事务的加锁。也就是说，事务观察的是整个数据库在一个时间点上的情况，即使此时数据库的某些部分正在被其他事务更新。在快照的语境中，"一致"一词意味着它与因果关系一致：如果事务T_2之前，并且如果快照包含T_2的结果，那么它也必须包含T_1的结果。

Spanner对快照的实现使用了multi-version concurrency control 多版本并发控制(MVCC)，这是一种optimistic concurrency control乐观并发控制的特殊形式。MVCC的基础是为每个事务分配一个提交时间戳；每个数据对象都被标上写入该事务的时间戳。当一个对象被更新时，我们并不只是覆盖它，而是在最新的版本之外再存储几个旧的版本（每个都有一个时间戳）。只读事务的快照也是由一个时间戳定义的：即该事务读取快照时间戳之前的每个对象的最新版本，并忽略任何时间戳大于快照的对象版本。许多其他数据库也使用MVCC，但Spanner的特别之处在于它给事务分配时间戳的方式。

为了确保快照与因果关系一致，MVCC算法要求，如果事务T_1发生在事务T_2之前，那么T_1的提交时间戳必须小于T_2的时间戳。然而之前讲过，来自物理时钟的时间戳不一定满足这个属性。因此，我们的自然反应应该是使用逻辑时间戳，例如Lamport时间戳。

不幸的是，逻辑时间戳也有问题。考虑一下上图的例子，用户观察了事务T_1的结果，然后采取了一些行动，并在事务T_2中执行。这意味着在事务之间有一个real-time dependency实时依赖关系：T_1必须在T_2开始之前完成，因此我们希望T_2的时间戳比T_1大。然而，Lamport的时间戳不一定能确保这种排序属性：回顾一下，它们的工作方式是为网络上传播的每条消息附加一个时间戳，并在每次收到这样的消息时取最大值。然而，在上图的例子中，可能没有任何消息从执行T_1的副本A发到执行T_2的副本B。相反，通信是通过用户进行的，我们不能期望人类在他们执行的每个动作中都包含一个正确的时间戳。如果没有一个可靠的机制来传播每个通信步骤的时间戳，逻辑时间戳就不能提供我们需要的排序保证。

生成逻辑时间戳的另一个选择是有一个指定的服务器来为事务签署时间戳。然而，这种方法在一个全球分布的数据库中被打破了，因为该服务器将成为单点故障和性能瓶颈。此外，如果在与时间戳服务器不同的大陆上执行的交易需要等待响应，由于光速延迟造成的不可避免的往返时间会使交易执行缓慢。需要一个不太集中化的方法来处理时间戳。

这就是Spanner的TrueTime机制的作用。TrueTime是一个物理时钟系统，它并不返回单一的时间戳，而是返回一个uncertainty interval不确定的间隔。并不返回单一的时间戳，而是返回一个不确定的时间间隔。尽管我们无法确保实际系统中的时钟完全同步，但我们可以跟踪在系统中的不同点上可能被引入的误差。对于原子钟来说，误差范围是由制造商报告的。对于GPS接收机来说，误差取决于目前在范围内的卫星信号的质量。在网络上同步时钟所带来的误差取决于round-trip time往返时间。石英钟的误差取决于它的漂移率和它上次与更精确的时钟同步的时间。

当要求TrueTime提供当前的时间戳时，它会返回一个区间[t_{earliest}, t_{latest}]。系统不知道真正的当前物理时间戳t_{real}，但它可以通过考虑上述所有的误差来源，确保t_{earliest} \le t_{real} \le t_{latest}的概率非常高。

当事务T_i想在Spanner中提交时，它从TrueTime获得一个时间戳区间[t_{earliest}, t_{latest}]，并指定t_{i,latest}为T_i的提交时间戳。然而，在事务实际提交并释放锁之前，它首先暂停并等待一个与时钟uncertainty interval不确定周期相等的时间\delta_i = t_{i,lastest}-t_{i,earliest}。只有在这个等待时间过后，该事务才被提交，其写入的内容才对其他事务是可见的。

尽管我们没有完全同步的时钟，导致一个节点不能知道事件的确切物理时间，但这种算法确保事务的时间戳在事务提交的那一刻小于真正的物理时间。因此，如果T_2的实际时间比T_1晚开始，最早可能分配给T_2的时间戳必须大于T_1的时间戳。换句话说，等待的过程确保T_1和T_2的时间戳间隔不会重叠，即使两个事务在不同的节点上执行，并且之间没有通信。

由于每个事务都必须等待不确定性间隔的过去，真正问题是如何使不确定性间隔尽可能的小，以便事务保持快速进行。谷歌的方案是在每个数据中心安装原子钟和GPS接收器，并每隔30秒将每个节点的石英钟与本地数据中心的时间服务器同步。在本地数据中心，往返时间通常低于1毫秒，因此由网络延迟引入的时钟误差相当小。如果网络延迟增加，例如由于拥堵，TrueTime的不确定性区间会相应增加，同时误差增大。

在每30秒的定期时钟同步之间，节点的时钟仅由其本地石英振荡器决定。这里引入的误差取决于石英的漂移率。为了安全起见，谷歌假设最大漂移率为200ppm，这比正常工作条件下观察到的漂移要高得多。此外，谷歌监控每个节点的漂移，并提醒管理员注意任何异常值。

200ppm的漂移率是一个安全的假设吗？根据Spanner的论文：“我们的机器统计显示，CPU损坏的可能性是时钟损坏的6倍。也就是说，相对于更严重的硬件问题，时钟问题是非常低频的。因此，我们相信TrueTime的实现与Spanner所依赖的任何其他软件一样值得信赖。”[Corbettet al., 2012]。

如果我们假设石英漂移为200ppm，并且自上次时钟同步以来已经过了30秒，这意味着由于石英漂移造成的时钟不确定性为6毫秒（不包括网络延迟、GPS接收器和原子钟的不确定性）。不确定区间随着上次时钟同步后的时间逐渐变大，最多达到约7毫秒，并在每次时钟同步时重置为约1毫秒（往返时间+时钟服务器不确定度）。

因此，在正常工作条件下，平均不确定性间隔约为4毫秒。4毫秒是一个事务在提交前必须等待的平均时间，这比等待洲际网络往返（100毫秒+）要快得多。

总结一下：通过对不确定性的仔细核算，TrueTime提供了当前物理时间的上限和下限；通过高精度时钟，它保持了较小的不确定性间隔；通过等待不确定性间隔，Spanner确保时间戳与因果关系一致；通过将这些时间戳用于MVCC，Spanner提供可序列化的事务，而不需要为只读事务提供任何锁。这种方法保持了交易的快速性，而不需要对客户端提出任何传播逻辑时间戳的要求。

最后是猫猫的乱入(ฅωฅ*)