“Hi，这是小5自学算力大集群相关知识的第14篇笔记。这次期我们将讨论我们能否构建一个系统，使得写操作也能够从客户端的视角出发，纯粹地以本地方式进行。”
摘要
那些拥有多个数据中心的大型网站们，它们希望在每个数据中心都复制所有数据，这既是为了将副本靠近用户，也可能是为了容错。
考虑到客户端通常是网络浏览器的场景，随之而来的便是要求快速读取。典型的安排是，读取操作至少在本地进行，而写入操作可能稍微复杂一些。符合这种模式的系统之一就是之前介绍过的 Spanner ，而 Spanner 及其写操作涉及跨所有数据中心的 Paxos 算法运行。
Facebook 的 Memcached 是该通用模式下的另一种设计。其存在一个主站点，该站点拥有一组主 MySQL 数据库。所以，如果客户端想要进行写 操作它必须将所有写操作发送到主站点，随后主站点向其他数据中心发送新的信息或无效化通知。因此，写入操作实际上有些昂贵，与 Spanner 系统并无太大不同。另一方面，其所有的读取操作都是本地的。所以， Facebook 的 Memsached 方案在进行写入操作时需要涉及跨数据中心通信，而读取操作则是本地的。
那么，我们能否构建一个系统，使得写操作能够从客户端的视角出发，纯粹地以本地方式进行。这样，客户端若要进行写操作，可以将写请求发送至其 所在数据中心内的本地副本，同时仅向本地副本发起读请求，无需等待其他数据中心，也无需与其他数据中心通信或等待它们执行写操作？
另外，如果写操作能在本地完成。那么我们就不必担心其他数据中心是否正常运行，或者我们能否快速与其通信，因为客户端无需等待这些数据中心的响应。
- 尝试构建系统1
遵循本地写入策略的最简单设计，假设一个包含三个数据中心的系统。假设数据在每个分片中都是以两种方式进行切分的从 A 到 M 的鍵以及以 M 到 Z 的鍵，在每个数据中心中均按照相同的方式进行分片。
客户端将在本地进行读取。如果客户端需要写入一个以 M 开头的键，那么客户端将向负责以 M 开头的键的分片服务器发送写入请求。该本地分片服务器将立即向客户端回复，表示已正确处理该写入操作。除此之外，每个服务器还会维护一个待处理权限队列。这些权限是近期由客户端发送给它的，而它需要将这些权限转发给其他数据中心。它将异步地在后台将这些权限流传输到其他数据中心中相应的服务器上。在客户端应用之后，我们这里的分片服务器将向其他每个数据中心发送一份客户端权限的副本。每个分片服务器随后将对其本地数据表应用相应的权限。
这种设计实际上更有利于读取操作的高效执行。读取操作对本地数据中心之外没有任何影响。而每当进行写入操作时，客户端无需等待该操作完成，但分片服务器随后必须将这些写入操作推送至其他数据中心。对于新数据的读取，其他数据中心随即迅速进行。因此，读取操作的工作量小于写入操作。
亚马逊的 Dynamo 系统或开源的 Cassandra 系统都遵循了相同的基本模式。
这类方案的常用名称是“最终一致性”。原因在于，至少在最初阶段，如果你进行了一次写操作，其他读取者和其他数据中心并不能确保能够看到你的这次写入，且也无法保证顺序。
例如，如果作为客户端，首先写入以 M开 头的键，随后写入以 A 开头的键，那么， M 对应的分片服务器会发送我的写入请求， A 对应的服务器也会发送我的写入请求。但请注意，这些请求可能在广域网中沿着不同的速度或路径传输。或许先写了 A ，也可能先写了 M ，然后才是 A 。而在另一个数据中心，这些更新可能以相反的顺序到达。因此，不同的客户端将以不同的顺序观察到更新。
“最终一致性”的根本意义在于：如果一切稳定下来，人们停止写入操作，所有这些写入消息最终都到达了目的地并得到处理，那么一个最终一致性的系统应该会在所有副本中存储相同的值。
由于这是一个宽松的规范，因此在实现上拥有很大的自由度，并且有很多机会获得良好的性能，因为该系统基本上不要求你立即执行任何操作。
一个例子：
假设我们正在构建一个网站，用于存储照片，每位用户都有一组以键值对形式存储的照片，其中某种唯一的 ID 作为键。每位用户都维护着一个列表，其中包含了他们允许他人查看的公开照片。
客户端 C1 上，先是插入照片，然后向我的照片列表中添加对该照片的引用。但在前述的最终一致性方案中，这第二次写入操作有可能在第一次写入之前到达其他数据中心。所以，如果这个其他客户端在不同的数据中心进行读取，它可能会看到包含我的新照片的更新列表。但当另一个数据中心的客户端尝试获取列表中的照片时，该照片可能尚未存在，因为首次写入可能还未通过广泛分布的网络传输至客户端 C2 的数据集。在最终一致性系统中，这种情况将成为一种常规现象。
那如何确定哪次写入是最新的？
对于某些数据，如果数据可能被多个参与方写入，那么我们可能需要判定哪个数据项更为新近。假设我们有一个键，我们称之为 K ，并且有两个针对它的写操作：两个客户端同时对 K 发起写操作。一个客户端将值设为1，而另一个客户端将值设为2。我们需要搭建一个系统，使得所有三个数据中心就键K的最终值达成一致。这就需要引入版本号。
最直接的版本号分配方式是使用墙钟时间。其理念是，当客户端生成一个 PUT 请求时，无论是它自身还是与之通信的本地分片服务器，都会查看当前时间——比如说现在是12:50——并将这个时间作为该键版本的版本号。这样一来，我们不仅会在数据库中存储时间戳，还会在数据中心之间发送的写入消息上标注这个时间。然后通过对比时间戳确定最新的数据。
但这里存在两个小问题：
一个问题是，如果两个数据中心同时进行写操作，它们实际上可能会分配相同的时戳。通常的做法是，时间戳实际上是时间或任何其他信息在高位的对（只要它是唯一的标识）。
另一个问题是，只有当所有数据中心的时间完全同步时，该系统才能正常工作。如果时钟偏差达到数秒，甚至可能达到数分钟，那么我们实际上就面临一个严重的问题了。比如说，某个服务器的时钟快了一分钟，那么在那一整分钟内，其他任何写入都无法生效，因为没有其他写入的时间戳会超过它。
为了解决这一问题。一种方法是采用称为 Lamport 时钟的这一概念。 Lamport 时钟是一种分配时间戳的方法，这些时间戳与实际时间有关，但能够应对某些服务器时钟运行过快的问题。每个服务器都维护一个名为 tmax 的值。该值表示它从其他任何地方迄今为止所见到的最高版本号。如果有人生成的时戳超前于实际时间，所有看到这些时戳的其他服务器，它们的 tmax 值将会反映出这一点，即相对于实际时间有所超前。当服务器需要办新的写入分配时间戳或版本号时。它会采用的方法是取 tmax （当前最大时间戳）加一，以及实际的系统时间（即墙钟时间）中的最大值。即（Tmax+1，real time）。这意味着我们需要为新版本分配编号，而这些版本号正是我们最终一致性系统中伴随值所需的。因此，每个新版本号都将高于所见过的最高版本号，也就是说，它高于对我们要更新的数据进行的最近一次写入的版本号，并且至少与墙钟同步。
是关于并发读取同一键的处理问题
并发读取可能都携带了应该保留的重要信息。例如，如果我们有两个数据中心，分别有客户端1和客户端2它们都向同一键发出了写入请求。这两个 put 操作都被发送到数据中心3。数据中心3应如何处理这些信息？
数据中心3将查看分配的版本号，丢弃时间戳较低的数据，并接受时间戳较高的数据。这被称为“最后写入者胜出”策略。
这一特性具有确定性的优点，因为每个人都参照相同的时戳，所以最终得到的答案也将一致。但我们真正希望的是，数据中心3能够将这个增量与那个增量合并的结果。比如，假设我们在这里维护的值是一个包含众多商品的购物车。而我们的用户，或许因为在他们的网络浏览器中同时打开了两个窗口，从而从两个不同的网络服务器向其购物车中添加了两件不同的商品。我们希望这两个针对同一购物车的冲突权限能够通过取集合并集的方式正确解决。
这是弱一致性系统的一个缺陷，即容易陷入一种可能对同一数据拥有冲突权限的情况，而希望对此有精细的、应用特定的解决方案，但这通常相当困难。
- 构建系统2
我们能否构建一个系统，它仍然允许本地读取和本地写入，但可能略微减少异常行为？
在此方案中，将提出一个新操作符， sync 操作符。功能是，当客户端调用它时，你需要提供一个键和一个版本号， sync 将等待，直至所有数据中心中键 k 的副本至少更新到指定的版本号。这是一种强制排序的方式。但请记住，这个同步调用可能会相当慢，因为其实现方式是向外发送请求，与所有其他数据中心通信，并询问它们：“您保存的键 K 的版本是否至少达到了这个版本号？”。随后需等待数据中心响应，若其中任一数据中心表示拒绝，则必须等待直至该数据中心同意。
再次针对我们的图片列表，假设客户端 C1 正在更新图片，它会调用 put 方法来插入图片，并获取到一个版本号。现在，程序员必须意识到，这里存在一个风险：我即将更新图片列表，但如果其他数据中心尚未看到我的图片，该如何是好？这时，程序员会执行同步操作，同步图片，等待所有数据中心都拥有由 put 方法返回的那个版本号。仅在同步返回之后，客户端 C1 才会调用 put 方法并更新照片列表。之后执行 sync 。
现在，如果客户端 C2 加入并希望读取照片列表，然后他们阅读了照片。客户端 C2 将执行一个获取照片列表的操作。它将在照片列表上执行一个 get 操作，如果发现所需的照片在列表中，它将在其本地数据中心再次执行 get 操作以获取照片。如果在不同数据中心的客户端 C2 看到了列表中的这张照片，那就意味着客户端 C1 已经调用了 put 操作到这个列表中，并执行了 sync 。这意味着，无论谁将照片添加到了列表中，他们的同步过程已经完成，这意味着同步完成的事实表明照片已无处不在，因此我们可以信赖这个获取照片的操作实际上会返回该照片。
这一切的核心，在于确保顺序的严格执行，即在前一个操作彻底完成之后，后一个操作才能开始。因此同步机制会明确地强制为写入者规定顺序。
但如果一个数据中心宕机，那么同步将会阻塞，直到另一个数据中心恢复运行。可以在这个方案的基础上利用法定人数来规避这个问题。
- COPS
可否在系统中，不会强制客户端在同步时等待，而是以某种方式将顺序编码为一条信息，告知读取者或其他数据中心？
一种非可扩展的实现方式，简单来说，就是在每个数据中心，采用日志记录的方法，而非让各个分片服务器独立地与其在其他数据中心的对应服务器进行通信。相反，在每个数据中心，我们将设置一个专门的日志服务器，负责通信和向其他数据中心发送写入操作。这意味着，如果客户端对其本地分片执行写入操作（即 put 操作），该分片并非单独将数据发送至其他数据中心，而是会与本地日志服务器通信，并将此次写入追加到该数据中心正在累积的单一日志中。
然后，如果客户端，比如，对一个不同的键进行写操作，假设我们在这里写入了键 A 和键 B ，而不是像之前那样，这个分片服务器独立地将写入操作发送到键 B，它会指示本地日志服务器将该写入操作追加到日志中。随后，日志服务器按照日志顺序将日志发送至其他数据中心，确保所有数据中心都能首先正确地接收到 A 的日志。他们将首先将数据处理到 A 节点，然后，再执行 B 的操作。实际上，这种方式恢复了部分性能，因为客户端可以恢复到仅执行操作的状态，即从 A 开始，然后是 B ，客户端 put 操作可以在数据存入本地日志服务器的日志后立即返回。我们通过日志条目的序列号来大致保持顺序，而不是让客户端等待。现在强制执行有序写入，并确保这些写入操作按顺序在其他数据中心显示，以便读取客户端能够按序查看它们。
这种解决方案的缺点在于，日志服务器成为了所有写操作必须经过的瓶颈。随着系统规模的扩大，单个日志服务器所面对的分片数量会越来越多，此时，单个日志服务器可能就无法快速地处理所有的写入操作。因此，COPS并未采用这种方式将顺序约束传达给其他数据中心。我们希望以某种方式将订单信息传达给其他数据中心，而不必通过单一日志服务器汇集所有费率信息。
非 GT 版本（即无 GET 事务）的 COPS 系统的功能与介绍
COPS 的基本策略是，当 COPS 客户端进行本地读写操作时，它们会积累关于操作顺序的信息，比日志方案的粒度要稍微细一些。每当客户端执行一个 put 操作时，该信息都会被发送到远程数据中心。这里我们需要引入客户端上下文(client context)的概念。
当客户端进行 get 和 put 操作时，可能一个客户端先获取 X ，接着获取 Y ，然后对 Z 进行 put 操作，并赋予其某个值。客户端所使用的库，实现了 put 和 get 操作，并在执行这些操作的同时，积累相关的上下文信息。
如果客户端执行了一次 get 操作，并得到了 X 版本号为2的某个值， Y 返回的是版本4的当前值。在上下文中累积的信息是：该客户端已读取 X ，并获取了版本2；在获取 Y 之后， COPS 客户端库将会向上下文中添加信息，这样一来，我们不仅读取了 X 并获取了版本2，而且现在我们还读取了 Y 并获取了版本4。当客户端执行 put 操作时，发送给本地分片服务器的信息不仅仅是 put 、键和对应的值，还包括这些依赖关系。因此，我们将通知 Z 的本地分片服务器，该客户端在执行 put 操作之前，已读取过 X 并获取版本2，以及 Y 并获取版本4。这里发生的是，客户端正在表达这种排序信息，即在向 Z 执行 put 操作之前，客户端已经看到了 X 版本2和 Y 版本4。因此，任何读取这个版本 Z 的其他客户端，也最好能看到至少这些版本的 X 和 Y 。
同样地，如果客户端随后执行了另一个对象的 put 操作。比如 Q ，那么发送到本地分片服务器的不仅仅是 Q 本身，还包括该客户端先前执行过的 get 和 put 操作的事实。假设这次 put 操作生成了第三个版本，即本地启动服务器告知：“你好，将版本3赋予你的新 Z 值。” 当我们进行对 Q 的写入操作时，将会伴随有依赖信息，表明此次对 Q 的写入是在创建 Z 版本3的对 Z 的写入之后进行的。至少在概念上，其余上下文也应一并传递。尽管 COPS （并发操作协议）可以对此信息进行优化省略。
COPS 将这种关系称为依赖性，即当前的 put 操作必须在之前的这些值之后执行。
那么这种传递给本地分片服务器的依赖信息，实际上会导致 COPS 执行什么操作呢？
每个 COPS 分片服务器在接收到本地客户端的写入请求时，首先会分配一个新的版本号。随后，它存储这个新值，即针对 Z 存储这个新值以及它所分配的版本号。之后，它将这一团乱麻发送至其他每个数据中心。因此，至少在非 GT 型 COPS 中，本地分片服务器仅记录键值及其最新版本号。它并不会记住依赖关系，仅将这些数据通过网络转发至其他数据中心。
依赖信息实质意义在于，操作层面上，新版本的 Z 无法向客户端公开，直到其依赖项（即这些版本的 X 和 Y ），已经在数据中心向客户端公开。对于 Z 的分片服务器必须持有这个写入权限直到它确认依赖项在本地数据中心已经可见。 Z 需要向 X 的分片服务器和 Y 的分片服务器发送消息。询问当前 X 和 Y 的版本号是多少。它必须等待结果，如果这两个分片服务器它们给出的 X 版本号是2或更高，或者对于 Y 来说是4或更高，那么 Z 就可以继续将其应用到本地数据表中。然而，或许其他分片服务器尚未接收到对应 X 版本2或 Y 版本4的更新。在这种情况下， Z 的分片服务器必须保留此更新，直到指定的 X 和 Y 版本已到达并在这些分片服务器上安装完毕。因此可能存在一些延迟。
此外，系统可能会遇到级联依赖等待的情况。比如可能是 Z 已经到达了分片服务器，但它本身可能依赖于键 A 。因此，分片服务器无法安装它。而 A 的分片服务器也可能已经收到更新但由于依赖关系仍需要等到其上一步的完成。即虽然更新已到达，但其仍在等待其他依赖项而不能进行安装与揭示。
- 关于因果一致性
客户端的操作引发了依赖关系，而依赖关系可以通过两种方式产生。
1. 如果某个客户端执行了一次 put 操作，随后进行一次 ge t操作，或者先执行 get 再执行 put ，又或者连续进行两次 put 操作，我们称后一次 put 操作依赖于前一次的 put 或 get 操作。
2. 如果一个客户端从存储系统中读取了某个值，那么我们可以说第2个客户端发出的 get 操作依赖于先前客户端实际插入该值的相应 put 操作。
此外，依赖关系具有传递性。
在因果一致性系统中，根据刚才概述的依赖关系定义，如果 B 依赖于 A ，并且客户端读取了 B ，那么该客户端随后也必须看到 A ，即该依赖关系。因此，如果客户端观察到两个有序操作中的某一个，即依赖关系排序的操作，那么在此之后，客户端也必定能够看到该操作所依赖的所有内容。
因果一致性的一个优点是，当系统中的两个值，即两个更新之间不存在因果关系时，因果一致性系统，如 COPS 存储系统，对于维护非因果相关更新之间的顺序没有义务。因此，因果一致性在允许并行操作和良好性能方面具有正面的意义。
因果一致性似乎既能提供是够的致性，又比线性一致性提供了更多实现高性能的机会。但它无法提供严格的因果关系，仅能提供某种程度的因果关系，这在一定程度上限制了它的吸引力。
以上内容来自对 MIT 《分布式系统 6.824》的学习笔记，在此特别声明。