从多线程到分布式（一）：问题的概述

一.多线程的产生
摩尔定律免费午餐的结束……

二.多线程难点的本质
多线程难点本质上是因为并发导致的顺序的不确定性。操作系统和语言设计者，为了性能考虑，对前后顺序都是没有假设的，这就导致了你写代码的顺序，和实际的执行顺序可能有很大的不同。这就类似于你在现实中安排规划一件事情的时候，是以一个人去做这件事情的视角去安排考虑的。但是实际上执行的时候，是多人联合完成的。大家都清楚，如果多个人做一件事，且这件事有严格的先后依赖顺序的时候，如果没有在做事的人之间的充分沟通，那么这件事的结果可能就变得一团糟糕。

三.基于单机的先后顺序规定
1.语言级别的规范：
Happens-before 规则
Java 提出了 Happens-before 规则来规范线程的执行顺序：
程序次序规则：在单线程中，代码的执行是有序的，虽然可能会存在运行指令的重排序，但最终执行的结果和顺序执行的结果是一致的；
锁定规则：一个锁处于被一个线程锁定占用状态，那么只有当这个线程释放锁之后，其它线程才能再次获取锁操作；
volatile 变量规则：如果一个线程正在写 volatile 变量，其它线程读取该变量会发生在写入之后；
线程启动规则：Thread 对象的 start() 方法先行发生于此线程的其它每一个动作；
线程终结规则：线程中的所有操作都先行发生于对此线程的终止检测；
对象终结规则：一个对象的初始化完成先行发生于它的 finalize() 方法的开始；
传递性：如果操作 A happens-before 操作 B，操作 B happens-before 操作 C，那么操作 A happens-before 操作 C；
线程中断规则：对线程 interrupt() 方法的调用先行发生于被中断线程的代码检测到中断事件的发生。
简单来说，就是前一个操作的结果可以被后续的操作获取这种简单的逻辑，在多线程环境中，都是需要特殊考虑。

2.操作系统级别的规范：
从语言层级考虑，我们的数据都是从“内存”中获取的，其实从操作系统层级考虑，内存又进一步的细分为cpu缓存和主存，这其实还是为了性能考虑。多个线程间可以共享的是主存部分，而cpu缓存间的数据则是互相独立，不可知的。如何设计合理的时机规则让数据从cpu缓存同步到主存，这就是问题的关键。
多个线程可能在多个独立的CPU内核中同时修改数据A，导致系统不知应该以哪次修改后的数据为准；或者线程ThreadA在对数据A进行修改后，没有及时将其写回内存，线程ThreadB和线程ThreadC没有及时获取最新的数据A，导致最新修改的数据A对线程ThreadB和线程ThreadC不可见。为了解决这些问题，CPU工程师设计了一套数据状态的记录和更新协议——MESI协议（CPU缓存一致性协议）。这里暂时关于MESI协议不展开，你可以先认为是规定了4种状态来表现哪些数据大家可见，哪些数据只有自己可见，需要通知大家可见。

存储缓存技术和失效队列技术是进一步提高CPU执行性能的关键技术，但是在引入这两种技术后，各高速缓存行之间只能保证数据的弱一致性（最终一致性），而放弃保证数据的强一致性——因为时间单位是纳秒级别的，所以各CPU内核从高速缓存行中读取的数据可能是不一致的，但这些高速缓存行中的数据最终会变得一致。
由于指令集、多级高速缓存、总线、内存等各种客观因素的限制，操作系统不可能清楚哪些数据是高并发场景中的关键共享数据，因此操作系统无法自动地在“保证数据的最终一致性”还是“保证数据的强一致性”之间做出选择。但是程序员应该知道哪些是关键的共享数据，所以一种简单且直接的处理方式是，计算机硬件将以上问题交给程序员解决。

要解决多线程场景中的有序性问题，需要在关键控制位置禁止指令重排，也就是说，让编译器和操作系统按照程序员指定的顺序执行这些代码。这样做也会存在问题：指令重排通常对性能是有益的，而程序员编写代码的方法千差万别，如果全面禁止指令重排，则可能造成较大的性能差异。一个好的解决方法是，引入内存屏障的概念，让不同类型的内存屏障具有不同的禁止指令重排效果，然后让程序员根据自己的需求使用这些特定的禁止指令重排效果。对于其他非特定场景的重排任务，会继续按照操作系统的优化逻辑进行运行。例如，LoadLoad Barrier只禁止了数据读操作的相关指令重排，并没有对数据写操作的指令重排加以限制。

用一个图总结一下：

image.png

根据内存模型来看无锁：
一写一读的无锁队列
内存屏障一写一读的无锁队列即Linux内核的kfifo队列，一写一读两个线程，不需要锁，只需要内存屏障。

一写多读的无锁队列
volatile关键字在Martin Fowler关于LMAX架构的介绍中，谈到了Disruptor。Disruptor是一个开源的并发框架，能够在无锁的情况下实现Queue并发操作。Disruptor的RingBuffer之所以可以做到完全无锁，也是因为“单线程写”，这是“前提的前提”。离开了这个前提条件，没有任何技术可以做到完全无锁。借用Disruptor官方提到的一篇博客文章Sharing Data Among Threads Without Contention，也就是single-writer principle。在这个原则下，利用volatile 关键字可以实现一写多读的线程安全。具体来说，就是RingBuffer有一个头指针，对应一个生产者线程；多个尾指针对应多个消费者线程。每个消费者线程只会操作自己的尾指针。所有这些指针的类型都是volatile变量，通过头指针和尾指针的比较，判断队列是否为空。

多写多读的无锁队列：CAS
同内存屏障一样，CAS（Compare And Set）也是CPU提供的一种原子指令。在第2章中会对CAS进行详细的解释。基于CAS和链表，可以实现一个多写多读的队列。具体来说，就是链表有一个头指针head和尾指针tail。入队列，通过对tail进行CAS操作完成；出队列，对head进行CAS操作完成。在第3章讲Lock的实现的时候，将反复用到这种队列，会详细展开介绍。

无锁栈
无锁栈比无锁队列的实现更简单，只需要对head 指针进行CAS 操纵，就能实现多线程的入栈和出栈。

无锁链表
相比无锁队列与无锁栈，无锁链表要复杂得多，因为无锁链表要在中间插入和删除元素。

四、基于不可靠网络的分布式问题
基于单机的多线程协调，还是可以归为在一定的限制下，可以有比较稳定的先后顺序的。但是分布式通常意味着不在同一台物理机上，是基于不可靠的网络进行沟通协调处理，这进一步加剧了问题，我们往往无法识别出到底是网络故障导致的问题，还是本身机器导致的问题。对于先后顺序问题，往往也很难有全场景高效的全体协商一致的方式。

1.关于CAP和BASE
分布式系统中，节点之间的数据同步是基于网络的。由于网络本身固有的不可靠属性，极端情况下会出现网络不可用的情况，进而将网络两端的节点孤立开来，这就是所谓的“网络分区”现象。“网络分区”理论上是无法避免的，虽然实际发生的概率较低、时长较短。没有发生“网络分区”时，也就是在大部分正常的时间里，系统事实上可以做到同时保证「一致性」和「可用性」。

C（一致性）
一致性这个指标，描述的是分布式系统非常重要的一个特性，强调的是数据正确。也就是说，对客户端而言，每次读都能读取到最新写入的数据。不过集群毕竟不是单机，当发生分区故障的时候，有时不能仅仅因为节点间出现了通讯问题，无法响应最新写入的数据，之后在客户端查询数据时，就一直返回给客户端出错信息。这句话怎么理解呢？我来举个例子。业务集群中的一些关键系统，比如名字路由系统（基于 Raft 算法的强一致性系统），如果仅仅因为发生了分区故障，无法响应最新数据（比如不满足“大多数”，没有了领导者），为了不破坏一致性，那么客户端查询相关路由信息时，系统就一直返回给客户端出错信息，此时相关的业务都将因为获取不到指定路由信息而不可用、瘫痪，这可以说是灾难性的故障了。 这个就是选择了CP。
每个参与者投票表决事务是放弃还是提交。一旦参与者投票要求提交事务，那么就不允许放弃事务。也就是说，在一个参与者投票要求提交事务之前，它必须保证能够执行提交协议中自己那一部分，即使参与者出现故障或者中途被替换掉。 这个特性，是我们需要在代码实现时保障的。否则就是需要拜占庭容错。因为承诺了却做不到，相当于散布了虚假信息。
需要关注的是，选择CP的时候，集群的可用性是每个节点可用性的乘积，比如，假设 3 个节点的集群，每个节点的可用性为 99.9％，那么整个集群的可用性为 99.7％，也就是说，每个月约宕机 129.6 分钟，这是非常严重的问题。

A（可用性）
可用性说的是任何来自客户端的请求，不管访问哪个非故障节点，都能得到响应数据，但不保证是同一份最新数据。你也可以把可用性看作是分布式系统对访问本系统的客户端的另外一种承诺：我尽力给你返回数据，不会不响应你，但是我不保证每个节点给你的数据都是最新的。这个指标强调的是服务可用，但不保证数据正确。这个就是选择了AP

P（分区容错性）
其实P不算是指标，而是考虑你的系统可不可能发生网络分区问题。分布式系统一定会发生分区问题，所以P是不可以舍弃的。
实际上P不存在的时候，其实A也难以保证。
如果舍弃P，那么就搭不成分布式系统，也就是单机，单机怎么保证高可用性呢？也就一个节点，故障也就故障了。虽然理论上符合访问非故障节点就能得到响应。

既要考虑发生分区时需要保证的是CP还是还是AP，还需要考虑在没有发生分区时，如何保证CA的问题。
我们可以在分区故障解决时，让系统重新恢复CA状态。

以用户系统为例，假如我们选择了CP，则分区发生后，节点1能继续写入数据注册新用户，节点2不能注册新用户，因为返回error，这就是不符合A。此时节点1可以将注册但未同步到节点2的用户记录到日志中。当分区恢复以后，节点1读取日志中的记录，同步给节点2。当同步完成时，节点1和2就同时达到了CA状态。

同样的，如果我们选择了AP，那么节点1和节点2都可以修改用户信息，但是修改的结果不一样。比如，节点1中修改为美食，节点2修改为旅游，节点1和节点2都记录了未同步的修改信息，当分区恢复时，系统需要按某种规则合并数据。也可以将冲突报告出来，由人工解决。（有点类似于Git）

设计分布式系统的两大初衷：横向扩展（scalability）和高可用性（availability）。“横向扩展”是为了解决单点瓶颈问题，进而保证高并发量下的「可用性」；“高可用性”是为了解决单点故障（SPOF）问题，进而保证部分节点故障时的「可用性」。由此可以看出，分布式系统的核心诉求就是「可用性」。这个「可用性」正是 CAP 中的 A：用户访问系统时，可以在合理的时间内得到合理的响应。

为了保证「可用性」，一个分布式系统通常由多个节点组成。这些节点各自维护一份数据，但是不管用户访问到哪个节点，原则上都应该读取到相同的数据。为了达到这个效果，一个节点收到写入请求更新自己的数据后，必须将数据同步到其他节点，以保证各个节点的数据「一致性」。这个「一致性」正是 CAP 中的 C：用户访问系统时，可以读取到最近写入的数据。

需要注意的是：CAP 并没有考虑数据同步的耗时，所以现实中的分布式系统，理论上无法保证任何时刻的绝对「一致性」；不同业务系统对上述耗时的敏感度不同。

Base
Base是对AP系统的更进一步说明。基本可用与最终一致。
最终一致性是说，系统中所有的数据副本在经过一段时间的同步后，最终能够达到一个一致的状态。也就是说，在数据一致性上，存在一个短暂的延迟。几乎所有的互联网系统采用的都是最终一致性，只有在实在无法使用最终一致性，才使用强一致性或事务。

本篇核心：
1.多线程难点本质上是因为并发导致的顺序的不确定性。操作系统和语言设计者，为了性能考虑，对前后顺序都是没有假设的，这就导致了你写代码的顺序，和实际的执行顺序可能有很大的不同。
2.操作系统不可能清楚哪些数据是高并发场景中的关键共享数据，因此操作系统无法自动地在“保证数据的最终一致性”还是“保证数据的强一致性”之间做出选择。但是程序员应该知道哪些是关键的共享数据，所以计算机硬件将以上问题的选择权交给程序员解决。
3要解决多线程场景中的有序性问题，需要在关键控制位置禁止指令重排。但是在分布式环境中中，我们往往无法识别出到底是网络故障导致的问题，还是本身机器导致的问题，机器本身也可能因为网络死灰复燃。因此没有简单并高效的解决多台机器有序性的方法，需要针对性的引入共识算法。
4.CAP讨论的是在发生网络分区错误的时候，对用户表现的是一致性还是可以用性。CAP 并没有考虑数据同步的耗时，所以现实中的分布式系统，理论上无法保证任何时刻的绝对「一致性」；不同业务系统对上述耗时的敏感度不同。BASE理论是对CAP的进一步补充描述。