一、分布式系统
1.1 总论
分布式系统指的是利用多个单体计算机系统构建的多体计算机系统。
与并行计算不同，分布式系统更侧重于用多个计算实体完成非常多个细碎的任务。而并行计算侧重于利用多个计算实体来更快更高效地完成一个计算任务。
分布式系统包括了执行流的分布式和数据的分布式。在北航 OO 课电梯问题中，涉及了多线程，属于是执行流的分布式，这就导致我以为分布式只是执行流的分布式，涉及的问题只是互斥和同步，这是非常片面的。数据的分布式指的是，存在多个数据副本，cache 就是一种数据分布式的实体。
1.2 背景
分布式系统虽然出现在各个系统层次，比如说多核的 CPU，多级存储系统，多线程的程序，分布式式的 Web APP。但是大部分的分布式理论都源于 Web APP，这是因为 Web 时代发展的红利导致的。
传统的 Web APP 架构被称为 LAMP，即 Linux + Apache + MySQL + PHP。
LAMP 的拓展性并不符合要求，其核心原因在于 Web APP 的用户拓展性非常好，一个用户生产 1M 的数据（非常小），那么一百万个用户就会生产出 1T 的数据，这就不再是一个磁盘可以简单存放的了，我们就需要一个存储的集群了。及时人们可以制造出一个非常大的磁盘，但是它的速度一定是会受到影响的。
计算也是同理，可能一个用户请求的计算量并不大，但是一百万个用户的计算量就非常大了。而受到摩尔定律和登纳德缩放定律失效的影响，人们是无法制造出一个超级强悍的单体芯片的，这就导致必须使用多个芯片。
这个时候将系统从单机拓展成分布式系统，就非常自然了。
1.3 组成
下面会介绍一个分布式的 Web APP （电商平台）由哪几个部分组成，其架构如图所示：
存在如下分布式：
- 外存的分布式：将数据存放在多个外存服务器上，也就是分布式的文件系统和分布式的数据库。
- 内存的分布式：分布式外存无法高效的缓存数据，且 APP 所在的单机的内存不够大，所以将内存也进拓展，也就是 Memcached
- app 的分布式：app 不需要部署在同一个单机上，可以部署在不同单机上，每个单机负责不同的功能。
- Load Balance：仅存在一个 app 依然非常局限，可以在多个单机上启动多个相同的 app，再由 Load Balancer 来决定请求发往哪个更为空闲的单机。这种技术除了依赖负载平衡技术外，还依赖 HTTP 协议的无状态性，使得负载均衡可以做得很轻松，如果是有状态的，那么负载均衡调度的就不再只是请求，就还包括之前的状态信息。
- CDN：将一些多媒体资源，放置在距离用户更近的地方。
- Compute 的分布式：将大量的计算任务放在单独的集群上（这张图上好像没有）。
1.4 CAP 理论
1.4.1 介绍
CAP 指的是分布式的三种重要属性，之所以将它们三个单独拎出来，是因为这三个属性构成了一个不可能三角（我也不知道有没有严格数学证明）。
我个人认为理解 CAP 理论的难点在于理解清楚这三个属性的定义，他们的定义如下：
- Consistency（一致性）：多个数据备份中的数据是一模一样的，用户可能会对某个备份中的数据进行修改，然后另一个数据备份中的数据也会跟随变化，保持一致。当系统没有一致性的时候，可能存在不同的数据备份，也就是正确性出现了问题。
- Available（可用性）：这是非常难理解的一个属性，他指的是用户对于数据的操作（读取或者写入一个数据等）是成功的概率非常高。而当失去可用性的时候，用户的操作经常会收到“操作失败，请重新尝试”的回应。
- Partition Tolerance（分区容忍性）：这个也非常难理解，它指的是在多个数据备份失去连接的时候（也就是所谓的“分区”），系统依然保持一致性和可用性的能力。C 和 A 对于一个单机系统而言，是非常自然的属性（要不然就是写出来 bug）了，但是如果是分布式系统，一旦数据备份之间失去同步能力，那么是很难保证 C 和 A 的。
那么为什么这是一个不可能三角呢？我们考虑如下图这样的情况，目前有两个分布式服务器 $S_1$、$S_2$，这两个服务器里都存储着数据 $V$ 的数据备份，客户 $C$ 可以读写 $V$ ，在开始阶段，$S_1$、$S_2$ 中 $V$ 的值都是 $v_0$ 。
然后出现了网络故障，导致 $S_1$、$S_2$ 之间的同步机制失效，出现了分区情况。然后 $C$ 向 $S_1$ 写入 $V$ 的值为 $v_1$ ，因为缺乏同步机制，所以 $S_2$ 中 $V$ 的值依然是 $v_0$ 。
此时如果 $C$ 从 $S_2$ 处读取 $V$ 的值，那么有两种可能，第一种是为了可用性，我们告诉 $C$ ，$V$ 的值是 $v_0$ ，这样就牺牲了一致性原则。第二种是我们为了一致性，告诉 $C$ 目前网络出现问题，读取并不成功，那么这样就牺牲了可用性原则。
从这个例子就可以看出，CAP 不可兼得。而根据业务场景的不同，我们选择牺牲的属性也不同：
- CA 牺牲 P：牺牲 P 就意味着系统不再是一个真正的分布式系统了，因为分布式系统出现“分区“是非常核心的场景，或者说，在分布式系统中不考虑”同步机制“，就过于理想和不可靠了。所以牺牲 P 的系统往往是一个单机系统（或者是某种无法享受分布式优势的分布式系统）。对于一个单机系统而言，保证 C 和 A 是非常基本的事情。
- CP 牺牲 A：牺牲 A 意味着操作有可能失败，但是只要操作成功了，那么它的一致性（也就是正确性）就得到了保证。对于银行 APP 或者支付宝这种对于正确性比较看重的软件，一般会采用这种策略。毕竟谁也不希望自己的账户里的钱突然没了。
- AP 牺牲 C：牺牲 C 意味着虽然每次操作都会得到响应，但是操作的结果不一定保证一致性。对于微信对这种实时性要求比较高的聊天软件，一般会采用这种策略。这也是我们在使用微信的时候，常常会出现”引用的内容不存在“的原因。
1.4.2 ACID vs BASE
在传统的数据库理论研究中，有 ACID 理论：
- 原子性 (Atomicity)：原子性保证了事务中的所有操作要么全部成功，要么全部失败，不能只完成部分操作。如同“原子”一样，事务是不可分割的。
- 一致性 (Consistency)：一致性保证了事务在执行前后，数据库的数据必须是合法的。当事务完成后，所有数据约束条件都必须得到满足。
- 隔离性 (Isolation)：隔离性确保了并发执行的事务之间不会互相干扰。每个事务的执行都像是独占资源，其他事务不能看到其未提交的结果。
- 持久性 (Durability)：持久性确保了已提交的事务所做的更改是永久性的，即使系统崩溃或出现故障，这些更改也不会丢失。
可以看出大部分的属性都是在保证 C 和 A，而对于 P 是没有描述的。
而随着 Web 时代的来临，传统的 ACID 就跟不上时代了，所以人们又提出了 BASE 理论：
- 基本可用性 (Basically Available)：系统在大多数时间内是可用的，即使在部分节点出现故障时也能处理请求。这意味着要牺牲部分一致性来保证系统的可用性。
- 柔性状态 (Soft state)：在 BASE 理论中，数据的状态不是瞬时的一致性，而是在某个时间点上可能处于“柔性”的状态，允许数据在一定时间内有暂时的不一致性。
- 最终一致性 (Eventual consistency)：在较长的时间内，系统会最终达到一致状态。这意味着虽然可能存在短期的不一致性，但经过一段时间后，所有副本最终会一致。
从这里可以看出，BASE 的思路是弱化 C 和 A ，来保证 P。理论的变化折射出不同的时代需求。
1.5 指标
虽然 CAP 理论提出了一些关于分布式理论的指标，但是我觉得它更像是为了理论服务的，而不是为了实际的生产。
在实际中，我们更看重这些指标：
我们为了这些指标发明了很多技术：
和 CAP 理论一样，这些指标之间也存在一定的权衡，不同的技术满足不同的场景：
我们下面会详细介绍一些特性的实现。
二、一致性
2.1 总论
在分布式系统中，会存在多个数据备份和多个执行流。这种情况下，很容易出现各个实体间操作和数据不一致的情况。也就是说，不一致是自然的，我们希望通过我们的努力，让这个复杂的模型简单下来。
我们简化模型的方式是这样的：
- 所有数据只有一份拷贝
- 整体并发的操作序列会被等价成一个串行序列
也就是如下图所示：
那这是怎么办到的呢？从图上可以看出，确实很多操作就是同时进行的，而不是串行执行的呀？我们改变操作的顺序，本质是在改变操作的起始时间，如果两个操作重叠在一起了，那么我们就让一个操作晚一些启动，也就是阻塞一个操作，来将两个操作错开。
也就是说，为了编程的易用性，我们牺牲的是系统的性能，更具体一些，牺牲的是操作的时延（可能还有些别的）。
一致性模型的光谱（Spectrum）如下：
我们还可以从另一个角度去分析为什么性能和易用性可以形成 tradeoff，当我们有一个并发的操作序列的时候，我们可以将他们排列成多种串行的全排列。一致性模型的本质，就是规定一些全排列是符合要求的，而另一些全排列是不符合要求的。越严格的一致性模型，允许的全排列的数目就越少，那么行为就更好被预测，那么易用性就高；而越宽松的模型，允许的全排列的数目就越多，那么底层实现就可以越灵活，性能就可以越好。
此外还需要强调，这里的一致性，并不完全等价于正确性，并不是说，我们只要遵循了某个一致性的模型，那么程序就不会出我们意想不到的 bug 了（不同的一致性模型可能有不同强度的编程约束，在这个约束下可能有一些奇怪的行为，但是都是符合一致性模型的内在逻辑的）。这是因为这里说的一致性里的操作，每个操作只涉及一个数据 object，而涉及多个 object 的操作（比如说银行账户的转账，涉及一个账户金额的减少和另一个账户金额的增加），就不再是一致性的范畴了，而是下文讨论的隔离性的范畴了。这种涉及多个 object 的操作被称作一个事务（Transaction，TX）。
2.2 一致性模型
2.2.1 Strict
strict 模型指的是按照每个 operation 的起始时间来对这些 operation 进行排列。那么这种模型基本上就等同于只允许一个全排列（因为每个 operation 的开始时间一般都是不同的），是最严格的模型。
这种模型基本上只是只能存在于理论中，因为在分布式系统中很难建立起一个全局的统一时钟。
2.2.2 Linearizability
Linearizability 指的是如果 op1 的终止时间在 op2 的起始时间之前，那么在串行排列中，也一定是 op1 在 op2 之前。如下图所示，这种排列就是不被允许的：
Linearizability 看似也是需要全局时钟的，而实际上并不是，Linearizability 的本质是确定各个操作的相对顺序而不是绝对顺序，所以实现难度会低一些。
2.2.3 Sequential
Sequential 指的是在每个计算实体上维护操作的相对顺序，而 Linearizability 是全局的相对顺序。
也就是说，下面的这个图（就是上面的那个图），虽然不符合 Linearizability ，但是符合 Sequential 。这是因为原本在 Linearizability 中存在的依赖，因为分别属于 P0 和 P1，所以在 Sequential 中并不存在：
2.2.4 Eventual
Eventual 是一种弱一致性模型，它只能保证最终每个数据副本的状态是一致的，而中途的状态就不一定了。
这种模型似乎就是微信这种实时聊天软件所采用的模型，所以微信的实时性更好，但是经常出现错误。
2.3 实现
Linearizability 有一个特性，就是如果每个 object 的 Linearizability 得到了维持，那么整个系统的 Linearizability 就得到了维持。这个特性我其实不是太理解，因为我感觉不同的 object 之间也会存在一些依赖关系。所以就算了，只是记录在这里。
下面我们开始介绍 Linearizability 的实现，其中最简单的一个模型就是 Primary-Backup Model，也就是将某个数据备份设置为 Primary，而其他的数据备份是 Backup。所有的写入操作都需要先对所有的 Backup 写入后，再对 Primary 进行写入。所有的读取操作，也只是对于 Primary 的读取，并不会读 Backup，也就是如下：
这种方式有两个很有趣的点，一个是要先写 backup，然后写 Primary，这是因为如果先写 Primary，那么就又可能在写操作还没有 Done 的时候，另一个读操作就可以读出来新值了，这就违反了 Linearizability 的定义。换句话说，将 Primary 的写入视为整个写入操作的结束，是一种实现 Linearizability 的一种手段。
另一个就是即使本地有数据，也依然要到 Primary 中去读取，这是因为 Read 操作必须完全在 Write 操作之前或者之后，下图就表示了一种不遵循这种方式造成的问题，Read_1 读出了新值，而 Read_2 明明在 Read_1 之后，读出的却是旧值。
当然这种非常愚蠢的读操作也是有办法缓解的，我们还是能读取本地值的，即使本地值是 backup，也就是我们设计每个 object 有两种模式，一种模式下只可以读取本地值，而另一个模式不允许，必须读取 Primary 的值，当 Primary 要写 object 的时候，就会把模式调整为不允许，而写入完成后，就调整成允许。这种设计非常类似于 Cache Coherency 的设计。
此外 Backup 的 op 的顺序也可能因为网络等问题，导致和 Primary 上的 op 的顺序存在差异，如下所示：
明明在 P0 上是 op1，op2，到了 P1 上就变成了 op2，op1 。我们可以给操作一个 seq number，来解决这个问题：
在 Primary-Backup 模型中，Primary 因为承担了过多的通信开销，导致其成为性能瓶颈。我们可以采用分区的方法，也就是不同的 object 的 Primary 并不是同一个，来避免瓶颈问题，下图中 x 的 Primary 是 P0，而 y 的 Primary 是 P1：
在了解完 Linearizability 的实现后，如果我们每次都只读取 local 的数据，写入的时候也只写入 local 数据，对于其他的备份，采用后台写入的方式，那么我们就得到了 Eventual 模型。