大多数的应用程序是通过一层一层叠加数据模型来构建的。

计算资源的过剩和短缺问题是会一直存在的，“节省资源的技术，只会带来资源使用率的增加”（Jevons paradox）。

书中讨论的一些问题都是在遵循P（现实问题）的前提下，找到代价最小（通常也是最低要求的）C，并以此达到最好的A（成果），书里的例子是多核CPU。 虽然多核CPU 算是分布式系统，但是不会受到网络延迟的影响，所以CAP 理论中的Partition tolerance 会被永远满足。可为了追求更快的计算速度，多核CPU 还是会放弃一致性来追求更强的可用性，哪怕可能会算错，可能会重复计算，还是要尽一切可能压榨计算资源。

范式是为了规范化数据使用流程而存在的东西，可随着硬件的不断提高，应用场景的不断扩充。我们发现破坏规则给我们带来的收益更大。不然NoSQL 也不会出现，存一个大json ，DB 都不用了，迭代效率一下提升很多。

那范式还需要遵循吗？其实范式只是一个让我们知道什么场景下该做什么事，不做的后果是什么的，一个度量标准。而不是必须死死遵循的准则。

单机单线程总能避免各种并发问题，但是这种计算方式过于缓慢，所以我们会发展出多线程，多进程，多机，分布式。与之带来的就是并发问题，符合这样一种条件的问题可以被归类为并发问题👇

先讨论在单机多线程多进程就会出现的并发问题。

讨论问题的模型：

在没有读-提交时，脏读会在如下场景发生：

举例：

例子1：Alice 在银行有两个账户，账户1 有100元，账户2 有0元，接着账户1 给账户2 转账100元，对应事务扣除账户1 的100元，给账户2 添加100元。若在事务扣除账户1 的100元且还没有给账户2 添加100 元时，Alice 读取了自己的存款余额，结果是0元。这个例子一个不好的点是不可重复读取也能导致相同的情况，我们在不可重复读取section 接着讨论。

例子2：在例子1 的条件上加上一个限制条件，账户2 是II 类账户，一次转账不能超过50 元，如果账户2 的转账超过了限额，则事务回滚。在事务扣除账户1 的100 元后，其他查询读取了账户1 的数据，发现账户1 的余额是0元，之后转账失败，事务回滚。因为事务的原子性，我们可以说事实上账户1 的余额从来就没有变成0 元，但是某个时刻其他事务却看到了余额为0 元的账户1。

在没有读-提交时，脏写会在如下场景发生：

举例：

某交易网站的一次交易会添加物品的收货人，和付款方。Alice 和Bob 同时购买一个商品，Alice 的事务在添加收货人是Alice 后，Bob 的事务把收货人改成了Bob 并声明Bob 是付款方，之后Alice 的事务更新了付款方为Alice，结果收货人成了Bob，Alice 却成了付款方。

大多数业务场景都不希望发生不可重复度，如下场景尤其不能容许不可重复读取：

不可重复读取又被称为读倾斜的原因：理想情况下，一个事务读取全部数据的发生时间应该是一瞬间，但发生不可重复读取时，事务读取全部数据的时间分布在时间轴的各处而不是一瞬间，所以我们说这个时候“读倾斜”了。

举例：

接着脏读的例子1，Alice 在开启转账事务2 前还运行了读取账户余额的事务1。考虑如下读取情况，事务1 先读取了账户2 的0 元，此操作符合读-提交；接着事务2 完成，账户1 变为0 元， 账户2 变为100 元；最后事务1 读取了账户1 的0 元，总金额为0 元，此操作也符合读-提交。

举例：

是更新丢失的升级版，不同之处是对应用层代码有更多的逻辑依赖，有着如下模式：

一般来说，如果2 个事务更新不同的对象导致出错（一般是应用层的语义出错），就是写倾斜，同一个对象就可能是脏写或更新丢失了。

为什么叫“写倾斜”：我们可以参考读倾斜的含义去归纳，理想情况下，一个事务读取进行写事务的操作应该是一瞬间，但发生写倾斜时，往往是事务先读取一个过期的数据，然后数据被修改，事务在没有觉察的情况下写入了非法的数据。也就是说单个事务的多次读取和写入分布在时间轴的各处，所以我们说这个时候“写倾斜”了。

举例：用户有一个支出项目表，同时还有余额的限制，两个事务各自同时插入没有超额的支出项目，但是因为两个事务没有注意到对方，多出的两个支出项目让账户余额成了负数（应用层逻辑）。

在这里我们讨论一个可行性不大的解决方案：

例如对上面那个余额为0 的例子，我们创建一个账户余额表，其内容为账户的总余额，然后加一个新收支字段，即一个时刻的余额只能被一次收支改变，这样两次事务就不用去计算账户的总余额，而是给当前余额加一个收支，问题变成了更新丢失或脏写问题。

实体化冲突主要的问题是过于占用数据库内容，比如我们要设计一个会议室预订系统，那么是否需要实体化未来6个月内所有房间和时间的组合呢？

除非万不得已，一般不会使用这个方法。

幻读是一个高概括性的概念，个人认为目前讨论并发问题都可以被归类为幻读？

更新丢失的情景相较于其他并发问题更简单，解决方法也好理解，因此我们先讨论怎么防止更新丢失。

如果DB 支持原子写操作，就尽量使用原子写操作。

DB 底层可以用独占锁或者让所有原子操作在单线程上执行来实现原子写操作。

应用程序显式锁定相关对象，DDIA 中用 FOR UPDATE 关键词来表示应用层请求为 SELECT 的结果加锁。

看似这个方案也能解决写倾斜问题，但需要考虑写倾斜也包括“检查不满足给定搜索条件的行（预期结果为空）”的情况，这个时候没有对象可以加锁，我们在其他section 讨论写倾斜的解决方案。

上面讨论了两种依赖锁的解决方案，接下来我们讨论一下无锁的解决方案。

先让更新并发执行，如果事务管理器检测到了更新丢失风险，就终止当前事务，并回退到某个安全的“读-修改-写回”方式。

数据库可以借助快照级别隔离来执行检查，我的一个猜测是一个对象在一个时刻只能有一个没提交的版本？应该还有更细粒度的检测方法。

只有在上次读取的数据没有发生变化时才允许更新，如果已经发生了变化，回退到其他“读-修改-写回”方式，或者重试。

实现方法：CAS compare and swap，现代的CPU 都支持这个指令。或者显式地在执行时加上 WHERE content = 'old content' 一类的条件，危险的是如果 WHERE 是在快照上执行的，那么 content 对应的值很有可能不是最新的。

详情会在分布式并发问题section 讨论，大体是这样的思路，应用层有逻辑，或者数据结构有逻辑来应对冲突的写入；或者尽可能把操作设计成与操作顺序无关的，这一类操作自然就不会有更新冲突。

解决了：

实现方法：

加上了读锁当然可以实现读-提交，但有以下缺点：

对每个待更新的对象，维护旧值和当前持锁事务将要设置的新值两个版本。在事务提交之前，所有其他读操作都读取旧值；仅当写事务提交之后，才会切换到新值。

下一个section 会提到

可以避免：

数据库保存对象多个不同的提交版本，并给每一行加上 created_by 和 deleted_by 字段，代表数据行在不同事务操作下产生的版本。同时有定时的垃圾回收任务清除不再需要的版本。

一个事务不能见到：

反之一个事务可以见到：

MVCC 的索引大致有两种实现思路

通常被认为是最强的隔离级别。

但在现实中实现可串行化非常困难，讨论下面3 种实现方法。

随着硬件的不断发展，数据库研究人员重新意识到单线程执行事务是可行而且高效的。

以下条件可以帮助我们利用内存和单个CPU 来实现串行化隔离：

具体操作时，我们可以用存储过程封装事务，因为一般的OLTP 执行步骤短，只要我们可以把用户IO 排除在一次事务中，那么单线程操作事务就会很高效。业务服务器把所有逻辑打包成数据发送给数据库服务器，然后数据库服务器就可以立即在内存中执行相关操作。过往的存储过程因为各个数据库有各自的实现语言，被饱受诟病，目前的解决方案是用通用编程语言来实现存储过程（举例：Redis 使用Lua 实现）。

近30 年来唯一被广泛使用的串行化算法。

在MVCC 基础上提出的乐观控制算法，08 年被提出，没有太多实践。DDIA 的作者基于如下理由认为此算法是未来数据库的标配：

基于MVCC 的快照隔离，我们用如下原则进行乐观控制：

一旦有，冲突发现，回滚。

可串行化的快照隔离(Serializable Snapshot Isolation) 依赖于SSI 锁，类似于索引区间锁，但SSI 锁只记录，不阻塞。在事务提交后通知其他相关事务，并被丢弃。

实现的tradeoff 是锁的粒度，大了可能会误判冲突，扩大一个事务的影响范围，小了可能会导致元数据开销过大。

为什么要分布式

属性

接下来的讨论我们会假设通过事务我们已经解决了一些问题。

不需要考虑。

共识是对分布式系统中最重要的一个抽象：所有的节点就某一项提议达成一致。基于此可以克服许多分布式系统挑战。下面的这些方案可以实现共识，最后可发现共识类似图灵完备，只要实现了一个共识方案，那么就能基于这个共识方案推演出其他所有共识方案。

注意：

quorum 可以实现可线性化，前提是没有不确定的网络延迟。

可线性化的限制太多，能否降低要求完成共识呢？我们想到了因果一致性，只要保证有因果关系的事件有序发生，其他事件并行发生，难度应该小于可线性化（可线性化等同于没有并行）。

那么如何给操作做因果排序呢？有一个方案叫Lamport 时间戳，给每个操作和客户端都加上一个序列号，序列号有一个自增的数字和节点ID 组成，两个序列号之前由自增数字决定大小，如果数字一样，就由节点ID 大小决定。每个请求都要带上时间戳，节点和客户端一旦遇到最大的序列号，就自增数字形成一个更大的序列号，放在下次的请求中，这样就能对每次操作排序。

只要没有不确定网络延迟，就能保证顺序。如果有网络延迟，考虑实现CAS，Lamport 时间戳此时需要先需要每个节点都确认没有并发的CAS 请求（有的话根据序列号决定先后），因此网络延迟会直接让系统停顿。（具体Lamport 时间戳的运行环境需要更多假设，我们不去讨论）

Lamport 时间戳和其他因果一致性模型失败的原因是它是一个同步模型（得到所有节点信息再决策），我们考虑用异步模型，就能实现CAS。

不考虑实现环境，只要有这两个条件，CAS 就会被实现：

以此CAS 只要在一个节点实现，其他节点就必须遵从这个CAS 操作，因为操作可靠发送且严格有序。

所以实现全序广播就能实现共识吗？我们可以用全序广播能否实现可线性化来验证，结果发现异步模型无法处理读取的问题，即系统内部的网络延迟（不是外部，前面说了我们不必考虑外部网络延迟）会使外界在读到新值后又读到旧值。

因此：

之所以有上面的两段论述，是想引出下面的观点：

所以我们如何实现全序关系广播呢？（答：使用可线性化……）

最后，讨论如何通过实现全序关系广播来实现共识。

我们先讨论一个可行的近似方案，之后把这个方案扩展成全序关系广播。

引入一个新组件：协调者，协调者和各节点之间这样实现两阶段提交：

显然这样是可以实现共识的，问题依然是网络延迟。所以我们增强协调者的容错性，看看能否实现共识：

书中介绍了几种容错式共识算法：VSR，Paxos，Raft 和Zab。我比较熟悉Raft (MIT 6.824)，所以用Raft 来介绍如何扩展2PC 以增强容错性。

协调者其实也可以是主节点，每当出现问题，若我们可以从所有可用的节点中选出新的主节点作为协调者，那么共识就依然有效。选出新的节点其实也是一个共识，这个共识只要被超过半数的节点承认，那么就是共识。

即每当有节点发现主节点失效，其就可以声明自己成为新的主节点，只要它得到了半数以上的节点认可，那么其就是主节点。之后这个主节点作为协调者，来给各个从节点的操作做排序即可，只要有半数以上的节点同意某操作，即立刻执行。

一旦系统中超过半数的节点挂掉，则系统进入宕机状态。我们可以发现半数以上的节点的好处在于，永远有一个节点参与了所有投票，确保脑裂不会发生，共识可以在系统中被延续。

至此我们知道了如何实现共识，并在讨论中我们发现，不是所有操作都需要共识的参与，只要一些关键的操作符合共识，我们就能构建出稳定的分布式系统。因此我们可以用封装好的ZooKeeper (Zab)，etcd (Raft) 针对少量、可完全载入内存的数据建立共识，以次达成高可靠的共识算法。