0 概述

这本书很神奇，简要而深入地描述了各种数据工具的原理和优缺点，非常好。

1 可靠、可扩展与可维护的应用系统

1.1 可靠性

可靠性就是允许系统部分故障的情况下，不至于全部失效。

• 硬件故障，使用软件级容错，多机失效时仍然能正常工作
• 软件故障，做好监控，并且故障隔离，不让部分系统故障级联到整个系统的故障上
• 人为错误，测试，监控与开发流程管理

1.2 可扩展性

描述系统性能：

• 吞吐量，OLAP系统着重关注，系统可以处理数据量大小
• 响应时间，OLTP系统着重关注，客户端测量的请求时间，常用P99指标来展示。值得注意的是，组合多个P99指标的方法，是将多个直方图合并后计算P99，而不是将多个P99指标计算平均值。

可扩展性描述负载增加时，系统应如何应对：

• 垂直扩展，加机器配置
• 水平扩展，加机器数量分担工作量

1.3 可维护性

可维护性描述运维人员方便维护，以及开发人员容易加功能和代码

• 简单性，简化复杂度，抽象出干净易懂的接口，同时屏蔽底层的实现。例如，SQL的查询接口。
• 可演化性，易于改变，轻松修改数据系统，不断适应变化的需求。

2 数据模型与查询语言

2.1 范式化

{
    "name":"fish",
    "company":[
        {
            "companyId":"10001",
            "jobYear":"2020",
        },
        {
            "companyId":"10002",
            "jobYear":"2019",
        }
    ],
}

范式化就是以不冗余的方式存放数据，不同数据之间用id来关联，而不是直接存储原始数据。

{
    "name":"fish",
    "company":[
        {
            "companyName":"A公司",
            "jobYear":"2020",
        },
        {
            "companyName":"B公司",
            "jobYear":"2019",
        }
    ],
}

非范式化就是以冗余的方式存放数据，例如一个人的工作信息就直接存公司的名称，而不是公司的id。

两种存储设计有什么优缺点：

• 范式化，更新公司名称时只需要改一个地方，但读取数据时需要联合多个数据源来展示数据。
• 非范式化，读取数据时只需要读一个地方，更新数据要冗余更新多个位置。

可以使用CQRS的想法，用范式化的数据处理命令模型，用非范式化的数据处理查询模型。

2.2 模式化

模式化就是指数据库中强制要求的数据格式要求，什么属性，什么类型。无模式化就是数据库没有对数据格式的要求，插入的数据没有字段数量，类型的要求。

两者的优缺点：

• 模式化，写时模式，模式严格，避免引用脏数据，但是需求变更时，不仅需要更新应用系统，还要更新数据库。
• 无模式化，读时模式，模型没要求，很灵活，需求变动时只需要更新应用系统，不需要更新数据。但是，应用系统要处理多版本的数据内容。

2.3 文档模型与关系模型

{
    "userId":"20001",
    "name":"fish",
    "tags":[10001,10002],
}

文档模型数据库，例如MongoDB，可以处理范式化或者非范式化的数据，并且是无模式化。擅长处理一对多的关系，直接存入数据库，不需要像关系数据库一样需要转换为多个表来存储。优点是非范式化数据读取数据时不需要join，速度快，模型灵活，快速匹配需求变动。缺点是范式化数据读取时不支持join，只能支持应用层的join操作，MongoDB提供了手动和DBRef引用来简化操作。另外不支持事务操作。但是，对多对象集合的组合筛选依然是很难实现。因此，文档模型数据库总是依赖于消息来生成非范式化视图来优化查询操作。

关系型数据库，例如Mysql，只能处理范式化的数据，只能是范式化的。擅长处理一对多，多对一，多对多的关系，需要转换为多个表的来存储。优点是支持任意的join操作和事务，模式严格，缺点是读取数据时更为耗时，因为要组合多表来合成视图，模式严格对快速需求的变动不太方便。

现在关系型数据库也在融合文档型的优点，加入json字段来满足文档型的需求。例如，对于聚合中，子结构是值对象建模的是可以放入json字段来实现，以优化查询，和减少表数量的。

2.3 查询语言

select * from animals where family = 'Sharks';

sql是一种声明式的数据查询语言，只表达了你需要什么数据，而数据库负责最优的执行方式和路径。

db.observactions.mapReduct(
    function map(){
        var year = this.observactionTimestamp.getFullYear();
        var month = this.observactionTimestamp.getMonth() + 1;
        emit(year + '-' + month ,this.numAnimals);
    },
    function reduce(key,values){
        return Array.sum(values);
    },
    {
        query:{family:"SHarks"},
        out:"monthlySharkReport"
    }
);

MapReduce就是一种半命令式语言，描述了查询的执行逻辑。同时具体的分布式执行的细节被数据库所隐藏了。

2.4 图模型

图模型就是一种，无范式化的关系模型。它的所有信息主要三个：

• 节点，节点名称和类型，例如Lucy:Person，和England:country
• 节点属性，节点的属性，例如Lucy:“sex”->female
• 边，节点的关系，例如Lucy (born in) London

无范式化在于，任何的节点可以动态增删属性，任何节点之间可以以任意方式连接在一起。

所以，图模型非常适合用在需要递归查询，多边连接查询的场景，例如知识图谱，金钱流转路径查洗钱等场景。

2.4.1 Cypher查询语言

MATCH
    (pserson) -[:BORN_IN] -> () -[:WITH*o..]-> (us:Location {name:'United States'})
    (pserson) -[:LIVES_IN] ->() -[:WITH*o..]-> (eu:Location {name:'Europe})
RETURN person.name

查询在美国出生，但在欧洲居住的人，隐含了递归查询，*o语法

2.4.2 SPARQL查询语言

select ?personName where {
    ?person :name ?personName,
    ?person :bornIn / :within* / :name "Unied States",
    ?person :livesIn / :within* / :name "Europe".
}

同样地实现一样的查询，更加简洁

3 数据存储与检索

3.1 LSM结构

写入：

• 数据单线程写入内存的平衡树（MemTable），并且写磁盘的WAL文件，这保证了崩溃时内存不丢失。
• 当内存平衡树满了以后，将整个平衡树写入到磁盘的排序字符串表（SSTable），就是以key排序后的键值对文件。之后新来的数据都写入全新的内存平衡树上。
• 删除与修改数据是通过添加数据来实现的，从来不更改磁盘上的SSTable文件，所以称磁盘上的文件是Immutable的。如果数据key在内存平衡树已经有的，则在内存上进行删除或者修改操作。
• 后台周期性地，多线程地合并和压缩SStable。为什么能压缩，因为同一个key在两个SSTable文件出现时，以新的SSTable的数据为准，覆盖旧的SSTable文件即可。合并的速度很快，因为SSTable本来就是有序的，合并只需要做线性复杂度就能合并新的SSTable。
• 合并有两种策略，按照相似大小的SSTable合并（Hbase），或者按照相同等级的SSTable合并（leveldb）。

SSTable，有序键值对文件。并附带一个稀疏索引，Index数组。为什么是稀疏，因为Index数组不需要存所有key的数据，存一部分的key数据就可以了，根据key的有序性我们能知道到它在Data数组的偏移量区间。

查询：

• 读布隆过滤器，检查这个key是否存在，不存在的话直接返回
• 读内存的平衡树，如果这个key存在的话，直接返回数据
• 从新到旧依次读磁盘的SSTable，对于每个SSTable，先通过Index定位到大概的偏移量，然后在这个偏移量里面顺序扫描每个key。如果这个key存在的话，直接返回数据。最终，在扫描了所有的SSTable都不存在的话，就返回空。

场景：

• 写入吞吐量特别大。写入直接操作内存加WAL顺序写日志，定期写磁盘是通过批量的顺序写操作执行的，所以总体写入吞吐量和速度特别大，基本跑满了磁盘极限。
• 读取吞吐量低，延迟波动大。因为读取数据是通过读取多个SSTable和MemTable来进行的，涉及了多个文件的随机读操作，导致吞吐量不高。同时，当读取的数据在最旧的SSTable里面，延迟就会大。当读取的数据在MemTable里面，延迟就会很小。所以读取的延迟波动大，不均衡。
• 范围读性能不佳，一个key范围的读操作需要读取所有的SSTable的数据，然后组合结果来得到的，所以考虑不佳。而单个key的读操作，则只需要从MemTable，从新到旧的SSTable依次读取，有的话可以提前返回，性能更好。
• 内存占用空间小，支持数据量大。因为SSTable是有序的，所以Index数组是稀疏索引，不需要索引所有的key数据。因此整个LSM数仅需要索引一部分的key数据，就能查询任意key的数据。
• 多副本，无事务。一个key对应的数据可能在多个SSTable，因为一个key有多个数据版本。而且，LSM树从不覆盖数据，只添加数据，所以无法做事务的锁操作。同时，这个只添加不修改的特性非常适合做多副本的复制操作，来提高读的吞吐量。

3.2 B树

B树在关系式数据库用得特别多，具体的实现就不说了。

特点：

• 树型结构，每个key只有一个对应的数据位置，轻松实现事务操作。
• 覆盖写，而不是追加写。对一个key的增加或修改操作需要覆盖写多个数据页面，这产生了随机写操作。另外，由于避免多页面写的中途产生断电产生的不一致问题，需要用WAL日志来保证多数据页面的原子写操作，这又额外产生了顺序写操作。

部分的B树针对性地作出优化：

• 写时覆盖，增删改key数据时，只添加数据页面和数据根，实现更复杂。但的确避免了WAL的原子写问题，而且能更好地实现隔离性的读一致性。
• B+树，非叶子节点只存key，叶子节点存完整的key和value。因此每个数据块可以索引更多的key，查询速度更快，对于大value而言性能可以提高。

场景：

• 读写平衡，写的吞吐量比LSM树少一个数量级，但是读吞吐量要比LSM树多一个数量级。
• 读延迟确定，波动小。查询的速度仅却决定于的树的高度，延迟确定，波动范围小。
• 范围读性能好，范围靠近的数据都靠在一起，范围读性能要比LSM树更好。
• 支持数据量小，当数据量增大时，树的高度越来越高，插入修改删除要修改的数据块越来越多，导致性能会不断下降。B树在单机情况一般只支持5000万行的数据量。
• 支持事务，单key的数据都在一个位置，能实现事务的锁操作。

3.3 多维树

多维树的一个实现就是R树，类似于pg中的gist索引，看这里

场景：

• 多key的范围查询的任意组合，例如查找某个时间段，某个地理位置范围的用户。

3.4 倒排索引

倒排索引的实现是搜索引擎，类似于pg中的gin索引。它建立每个key对应的posting list，然后以高效的算法将posting list进行and与or的操作

elasticsearch的核心是，posting list以顺序的document id存放，同时用跳表来做索引，这保证了扫描的过程是顺序读，而且索引能避免全扫描。由于建立的索引的顺序结构，难以支持即时的更新。所以，es采取和lsm树类似的方法，数据增删改都在内存上做，并且做WAL日志。每1秒批量将内存上的文档生成一个索引，写入到磁盘上。唯一付出的代价是，1秒以内增删改的数据无法查询到，所以，es称为近实时的查询。

场景：

• 多key的精确查询的任意组合，例如查找未付款的，并且属于20001用户的订单列表

3.5 内存数据结构

内存的数据库（redis）摆脱了磁盘需要块读写，随机读写慢的问题，允许使用更加丰富多样的数据结构，以及无编解码开销，性能非常强悍。但是内存在突然断电会丢失数据，而且容量小，成本高。

场景：

• 数据量小但读或者写次数很多的结构，例如用户权限列表，商品名称列表，秒杀场景的商品库存量。

3.6 OLTP与OLAP

OLTAP与OLAP是不同的业务场景，它们对性能的侧重点也不同。

OLAP数据，通常由在线OLTP数据库通过

3.7 列式存储

存储：

• 每列的值组成一个文件，每个文件相同的index组成一个行。由于一个文件里面都是相同的数据类型，所以压缩比很高。
• 存放的格式有两种，一个列存放各个行的具体值。或者一个列值一个文件，每个值是0或者1，代表该行是否包含这个列值。
• 排序时，隐式要求所有列都是按照这个顺序来排序，因为不同列之间只能通过相同index这个规格来组成一行。排序的意义在于优化查询中的order操作，以及limit提前返回操作。

列式存储的格式都是顺序的，难以支持中间删除与插入，修改。因此有两种写入列值存储的方式：

• 批量写入，每个批量一个大的列存储，读的时候需要组合多个列存储来得到结果。写入吞吐量大，但是有较大的延迟读问题。
• 类似LSM的实现，在内存维护列存储，后台负责周期写入磁盘。写入吞吐量小，但是延迟读也比较小。

场景：

• 任意的全表多行少列的分析操作
• 即时分析操作，无需预定义哪些查询行为

3.8 物化视图

使用类似cube分组的方式对表里面各个列的任意组合的预先计算保存下来，能有效避免查询时需要扫表的问题。例如，我要知道男性人群在18岁以下的数量，可以将男性的10岁以下数量，叠加男性的10岁至15岁数量，叠加男性的16岁数量，叠加男性的17岁数量，叠加男性的18岁数量。可见这样就能避免扫表，查询的速度和并发量要大很多，付出的代价是，无法支持灵活查询，维度多的时候预先计算量和存储量都很大。

场景：

• 预定义的聚合查询分析操作
• 聚合操作能被分步组合起来

4 数据编码与演化

4.1 兼容性

数据编码的兼容性

• 向后兼容，较新的代码可以读取由旧代码编写的数据
• 向前兼容，较旧的代码可以读取由新代码编写的数据

我们的目标是数据编码同时灵活地支持向后兼容，并尽可能支持向前兼容。

4.2 文本格式

josn和xml都是常见的文本格式，它们的特点是：

• 可读性好
• 占用空间大，数据类型模糊
• 无二进制字符串的友好支持

兼容性：

• 向后兼容，新加的字段不要沿用所有之前曾用过的key，而且新key必须提供默认值。以新代码保证读取旧数据时不会失败。
• 向前兼容，旧的字段不要删除，并填充恰当的值。以保证旧代码读取新数据时不会失败。

4.3 MessagePack

MessagePack对json的优化在于，明确的数据类型和数据长度边界，保留json以string作为key的方式，特点是：

• 占用空间与json类型，一样大，冗长
• 数据类型准确
• 支持二进制字符串

兼容性：与json相同

4.4 Thrift

ThriftCompactProtocol的优化在于，使用整数tag而不是字符串作为key，数据长度使用边长编码，例如即使是int类型，小整数的话也仅需要1位就可以了。特点是：

• 使用整数tag，而不是字符串tag，大幅度减少占用空间
• 变长编码大幅压缩整型空间

兼容性：

• 向后兼容，新加的字段不要沿用所有之前曾用过的整数tag，而且新tag必须设置为option，或者有默认值。以新代码保证读取旧数据时不会失败。
• 向前兼容，旧的tag字段不要删除，并填充恰当的值。以保证旧代码读取新数据时不会失败。

4.5 Protobuffer

Protobuffer相对ThriftCompactProtocol的优化在于，没有专门的list类型，相同tag类型的读取时自动填充到一个list类型，进一步缩小了占用空间，特点是：

• 采用和Thrift的整数tag和变长编码
• 没有专门的list类型标志

兼容性：与Thrift相同

4.6 Avro

Avro是专门为模式演化而设计的编码语言。在OLAP环境中，多个版本的OLTP的同一个表不断通过ETL写入到数据仓库中，这些表可能增加字段，可能删除字段。这种情况下，使用PB或者Thrift得需要非常小心tag标记可能被重用，导致兼容失败。如果使用json或者MessagePack，由于每个key都是字符串类型，长度十分冗长。所以，我们期望一个用字符串作为key，同时空间很小的编码方式。

Avro的思路是让模式与数据分离，每个数据文件都有一个模式头部来指示，数据文件的内容格式与数据类型。

同时，区分写模式与读模式。每个文件都有自己专属的模式描述，同时代码可以指定读模式来兼容不同的写模式，例如是对不存在的key如何填补默认值，对已有的key名称如何重命名。

特点：

• 模式与数据分离，减少了数据文件空间，并提高了模式演化的兼容性

4.7 场景

数据编码

• 数据库与代码库的升级。代码与数据库是分离升级的，在先升级数据库的情况下，后升级代码的情况下，会产生旧代码需要读新数据类型的情况下。因此，如果要保证不停机升级，需要在升级数据库schema时，保证不删除字段，只添加新字段，并且新字段均需要默认值。
• 数据库归档存储，数据库需要归档时，需要记录多个版本的schema，这种情况下比较适合使用Avro编码。
• 服务和消息的数据流，严格按照各自编码方式的前后兼容性要求就可以了。

5 数据复制

5.1 意义

数据复制的意义在于：

• 更低的延迟，多数据副本，让客户端可以选择最靠近的节点访问，延迟更低
• 提高可用性，多副本让其中一个节点宕机后，依旧可以对外访问
• 提高读吞吐量，读操作可以分散到多个节点来执行，提高读吞吐量

5.2 主从复制

主从复制，就是一主多从的复制方式，只有主节点能写，其他从节点不断获取主节点数据，并对外提供读查询。

5.2.1 同步方式

主从复制的同步方式：

• 同步，主从节点之间没有延迟，主节点宕机后从节点补上，不会有数据丢失。但是，受网络影响，写执行延迟提高，并且从节点挂后，主节点不能对外工作。
• 异步，主从节点有少量延迟，主节点宕机后从节点补上，有少量数据丢失。但是，不受网络影响，写执行延迟不变，并且从节点挂后，主节点依然能对外工作。

一主多从的同步方式：

• 全同步，所有从节点与主节点使用同步复制，一挂全挂，但没有数据延迟。
• 全异步，所有从节点与主节点使用异步复制，有数据延迟，从节点切换为主节点时有少量数据丢失。但是主节点不受从节点宕机影响。这是使用最为广泛的一种方式，但要做好监控，避免主从节点之间落后太多。
• 半同步，选择一个从节点为同步复制，其他从节点为异步复制。既允许挂一部分从节点，也保证了从节点提升后没有数据丢失，是一种折中的好办法。

5.2.2 复制方式

主从复制之间都是采用状态机复制的方式，就是主节点总是将修改记录逐条发给从节点，从节点在本地重放记录来实现与主节点的数据同步。复制方式：

• 语句方式，使用很少，而且受now()，rand()这些函数影响
• WAL复制，底层存储引擎的块字节修改记录，效率高，但是不允许跨版本的主从复制，无法实现不停机的数据库升级。使用广泛，但是升级数据库时需要停机。
• 行日志复制，效率中等，但是可靠且能实现跨版本的主从复制。最为推荐的主从复制选项。

5.2.3 切换问题

当主从复制时，从机发现主机宕机后，将自己切换到主机后，可能会产生以下问题：

• 脑裂，当主机并不是真正宕机，而是网络断开造成的。当网络恢复正常后，原来的主机就会仍然觉得自己是主机，就会出现多个主机的脑裂问题。解决方法是，建立一个路由中间件，决定谁是主机，路由写请求到主机上。或者用zookeeper算法，所有节点共同选择一个主节点，一旦选择后，不允许非主节点的同步过来的数据。
• 丢失数据，主从延迟异步复制有延迟，提升从机会丢失少量数据。对于关键应用必须使用半同步方式。
• 自增冲突，主从延迟异步复制有延迟，从机提升后的自增主键依然是旧的，就会产生与原来的主机相同的主键，造成依赖主键同步的缓存和搜索引擎有冲突问题。改为半同步方式，或者不依赖数据库的主键生成方式。

5.2.4 复制滞后问题

主从复制使用全异步，或者半同步是最为正常的做法，全同步是没有意义的（写延迟太大，可用性比单机更差）。一旦使用异步复制，总会遇到主从数据滞后产生的问题：

• 读自己写，写用主节点，读用从节点，然后出现刚写的数据读的时候无法读取出来。解决方法是，①对于自己可能修改的数据走主节点，例如，自己详情页面走主节点，其他人详情走次节点。②客户端或者后端单点来跟踪最终修改了的数据，最近修改的数据走主节点，否则走从节点。
• 单调读，用户的一个列表两次查询操作，可能会路由到两个不同的从节点上，导致数据不统一或者重复。解决方法，以访问用户为key，对于同一个用户，总是路由到相同的从节点上查询。
• 前缀读，有因果关系的数据，位于两个分区时，因果关系由于两个从节点的延迟造成先读取果数据，再读取到因数据。解决方法，有因果关系的数据交给同一个分区。

以上的复制滞后都是些细节上的小问题，只会影响用户的体验，不影响写入逻辑的正确性。相对来说，更加要注意的是，对于写入操作的读操作，都必须要从主节点读取，否则无法加锁，或者读取到滞后太多的数据，影响写入逻辑的正确性。

5.3 多主复制

5.3.1 意义

多主复制的架构为，多个主从节点同时对外工作，多主节点之间采用异步复制。这样做的架构更常用于多数据中心，它的意义是：

• 扩大写吞吐量，和减少写延迟。用户可以使用选择靠近客户端的数据中心进行访问。
• 单个数据中心失效时，只会影响部分用户，其他数据中心依然能对外访问
• 数据中心之间访问不稳定，只能使用延迟更大的异步复制。

5.3.2 冲突

多主复制相对于单主复制，增加了一个新的问题，多主之间同步的数据可能是冲突的。例如A数据中心新增一个fish用户，B数据中心也要新增一个fish用户，两者异步合并数据时，发现同名用户冲突，无法合并数据。这个问题在单主复制时不存在的，因为写入数据都是只能经过唯一的主节点来执行，主节点会无歧义地允许其中一个新增用户，而拒绝另外一个新增用户的请求。

我们的目标是，让各主副本的数据收敛到一致的状态。解决冲突的方法：

• 避免冲突，这是最广泛的方法，每个数据中心都是分区处理一部分数据，他们没有数据交集的地方。例如，A数据中心只去处理F开头的新增用户请求，而B数据中心只去处理G开头的新增用户请求。
• 最后写入值胜（LWW），就是后请求者胜的方法。具体有客户端时间，服务器端时间，事务号。但是这种方法既不可靠，也会造成数据丢失。
• 矢量数据结构，版本矢量的方法，后面会有介绍
• 应用层处理冲突，包括读时处理冲突，和写时处理冲突。写时处理冲突，就是当数据中心发现数据冲突时，上报应用层来协调解决。

5.3.3 LWW

LWW的冲突解决方法为，最后写入者胜。如何判断最后写入者

• 各主服务器的时间戳，由于网络延迟的原因，服务器收到两个请求的先后顺序不同，这种方法不可行，会被收敛到不一致的数据上。
• 客户端的时间戳，不同客户端的时钟不同，会有同步误差，这会导致后写入者的客户端反而会丢数据。但是这种方法确实能让服务器收敛到一致的数据上。

但是，这种方法有根本上的缺陷，因为LWW依赖于服务器的实现，如果数据不仅要在主服务器存储，还要在派生数据库存储（缓存），就会产生更新丢失。例如，以上例子中，主服务器使用LWW规则会判断value2为最终获胜者，但在缓存中却判断value1为最终获胜者。

5.3.4 版本矢量

版本矢量来自于简单的想法，写入时需要指定你在读取什么版本的数据的结果，就是指定数据之间的因果关系。如果两个数据之间没有明确的因果关系，那么两个数据都要保留下来。如果两个数据之间有因果关系，可以安全地丢掉因数据。

插入时，指定数据和原有的版本号a：

• 获取所有小于等于版本号a的数据，并剔除它。
• 所有版本号a的数据，保留它
• 插入该行的新数据，版本号为当前最大版本号+1

应用层，获取数据：

• 取出当前行的所有版本数据a
• 在应用层合并这些版本数据，得到结果k1
• 在应用层执行修改操作，得到结果k2
• 插入数据到数据库，并指定版本号为a，数据为k2

5.4 无主复制

无主复制的特点是，多节点之间没有主从之分。写入数据的时候同时对所有节点进行写入操作。总共有n个节点，可以设定当w个节点返回成功时就向应用层返回成功，读数据时，也是同时读取r个节点的数据，成功后就返回。

5.4.1 读修复

很显然，一切正常的情况下，所有节点的数据都是一致的。当其中一个节点宕机以后重新上线后，由于缺少主从节点的同步复制方式，这个曾经宕机的节点无法自动知道如何到什么节点拉取什么新数据，所以，无主复制需要一种方法，来互相同步那些过期的数据。这个方法称为读修复。

• 读修复，多节点读取时，根据版本号来知道那些节点的数据是落后的，然后将新版本的数据同步写入到这些落后节点上。
• 反熵，后台进程寻找差异，并互相复制这些数据。不以特定的顺序复制，而且有较大的同步滞后。

5.4.2 新旧值概率

无主节点的主要问题是，即使w+r>n的配置下，我们依然可能读到旧值

• 并发冲突，新写入的数据可能被错误的LWW覆盖了
• 写入新值得节点返回成功后宕机了，重新上线后，恢复用了旧数据
• 写入的过程中，新值与旧值会互相摇摆。例如，n为3，w和r都设置2。在写入的过程中，可能先读到一新一旧节点，然后读到两旧节点。

因为要对无主节点的外部一致性问题，看成一个概率，而不是绝对值。w+r越大，读到新值得概率越大。从某种意义上，无主复制应该尽可能使用只增不减的数据模型。

5.5 总结

多种复制方式的特点：

• 主从复制，滞后的问题
• 多主复制，冲突+滞后的问题
• 无主复制，冲突+滞后+概率旧值的问题。

6 数据分区

6.1 意义

数据分区的意义：

• 提高写入的吞吐量，和降低写入延迟
• 提高可用性，一整个数据分区挂了，只会影响部分数据

6.2 分区方式

分区方式：

• 范围分区，可以支持区间查询，但是容易产生热点集中在某一段分区，所以设计key的时候要适当在前缀加入随机数，来避免数据倾斜。
• 哈希分区，不支持区间查询，但是分布均匀，不容易产生热点
• 组合分区，首列使用哈希分区，第二列以后使用范围分区

6.3 二级索引

二级索引，就是以不同的列值来索引同一个文档。

• 文档分区，每个分区对应一个独立的索引，写入速度快，单机事务。但是读取速度慢，延迟大，需要读取所有分区的二级索引来执行查询。
• 词条分区，所有分区对应一个独立的索引，写入速度慢，分布式事务。但是读取速度快，延迟小，读取时仅需要读取二级索引key所在的一个分区。

6.4 分区再平衡过程

分区再平衡的过程，需要考虑：

• 重分区的过程，依然可以对外使用
• 重分区的过程，不影响外部一致性

LSM结构重分区的过程

• 新数据双写到新分区和旧分区，这时候查询和写入都是在旧分区上执行
• 旧分区的旧数据异步复制一部分到新分区上
• 完成异步复制后，将新数据的查询和写入切换到新分区上即可

BTree结构重分区的过程

• 新数据查询和写入都到旧分区上
• 旧分区生成两个从库，两个从库只承担原来旧分区的一半数据，同时从库不断追赶旧分区的数据，从旧分区中拉取数据。
• 追赶完成后，两个从库上线，旧分区整个下线，切换新数据的查询和写入到在新的两个从库上

6.5 分区与节点分配策略

分区与节点的分配策略：

• 固定数量分区，分区数量从一开始就固定的，哪个key与哪个分区是固定对应的，常用于哈希分区。改变的仅仅是分区与节点之间的对应关系。例如，增加节点时，就将一部分的分区分配给新的节点。删除节点时，就将旧节点的分区平均分配给原有的节点上。
• 动态数量分区，分区的容量是固定的，是数量是动态的，常用于范围分区。当该分区的容量超过阈值时，将分区分裂为两个分区，然后找一下相对富余的节点来存放这个新分区。

6.6 路由

如何根据key路由到对应的节点上：

• 服务器路由，客户端可以向任意一个节点路由，然后节点根据路由信息转发到实际的处理节点上。各个节点之间使用特殊的协议来互相同步路由信息。使用这种方式的数据库有Cassandra和Riak
• 路由层路由，专属的服务器来执行路由操作，这个服务既充当了路由工作，也充当了负载均衡的工作。使用这种方式的数据库有Couchbase
• 客户端路由，客户端存放多个节点的信息，直接在本地查询后就可以路由到最终节点。这个需要客户端与一个中心路由信息系统保持连接，当路由变化时，中心路由系统通知客户端发生变化。这个中心路由系统常用ZooKeeper来实现。使用这种方式数据库有Hbase，SolrClound和Kafka。

7 事务

7.1 ACID

数据库的ACID一直是个比较容易混淆的问题，我想在这本书里面得到了最确切的解析。

• A原子性，无关并发性，强调的是多对象的原子性，在一个事务中的多个对象要么一起提交，要么一起回滚，任何状态下都不会出现中间结果的情况，但外部可能看到这个多对象逐个提交的过程。
• C一致性，保证数据库的约束在任何情况都会得到保证，例如是唯一约束，非空约束，外键约束。这个一致性与CAP中的一致性是不同的，CAP的一致性是指线性一致性，强调的是写后读，单调读，前缀读这些的一致性。
• I隔离性，强调的是并发情况的安全性和读写隔离情况，有多种的隔离级别可以选择
• D持久性，事务提交后就保证不会丢失数据，即使在崩溃的情况，这是通过WAL日志来实现的

对于NOSQL来说，与SQL数据库最大的区别在于，缺少原子性A和隔离性I的支持。

7.2 原子性

7.2.1 意义

原子性有很重要的意义，大部分的NOSQL数据库都提供了单对象的原子性，例如，一个key/value数据库，更新的时候要么提交一个新的value，要么保持原来的旧value，在任何情况下（包括中途宕机），都不会出现数据库的value出现半新半旧的情况。

但是，多对象的原子性是如此的重要，意义在于：

• 外键，唯一索引。写入原始文档后，还要写入唯一索引，来检查注册用户的名字是否重复。如果唯一索引插入失败时，就应该回滚原来的原始文档写入操作。如果没有多对象的原子性，就可能出现，唯一索引插入失败，但原始文档没有被正确回滚的情况。
• 更新非规范化文档，文档数据库不提供join操作，因此为了查询方便，总是在更新一个原始文档的同时，额外更新多个非规范化的文档。如果没有没有多对象的原子性，就可能出现非规范文档与原始文档不一致的情况。
• 二级索引。原始文档与二级索引的数据应该要一一对应。如果没有没有多对象的原子性，就可能出现二级索引与原始文档不一致的情况。

7.2.2 实现

在SQL数据库中，实现原子性需要满足以下几步：

• 开启事务
• 对原始记录加锁，阻止其他人对该记录修改或者删除操作。然后将原始记录的数据写入undo日志，将新数据写入redo日志，两个日志都落地。最后对原始行执行新数据的覆盖操作。
• 事务提交时，写入binlog，提交该日志。释放所持有的所有记录锁。
• 事务回滚时，写入binlog，回滚该日志。将undo日志记录的旧数据覆盖到原始位置上，然后释放所持有的所有记录锁。
• 宕机重启后，查询binlog，如果发现该事务已经确认提交，则根据redo日志重做。如果该事务已经回滚或中途状态，则用undo日志进行回滚。

可以看出，实现原子性的关键在于：

• 对每条修改记录都上锁
• 对每条记录的原始数据都写入undo日志，落地。

7.2.3 加锁

为什么要这样做：

不上锁的话，可能会出现A事务在已经执行第一行对象时，B事务进而也修改了第一行对象，然后A事务出现失败，想用undo日志回滚数据就会出错。因为第一行目前的状态既包含了A事务的修改，也包含了B事务的修改，直接回滚到A事务之前的数据状态，就会丢失B事务所产生的修改，这被称为第一类更新丢失

func changeNameAndAddress(newName,newAddress){
    var oldName = ctx.Db.Query("select name from t_user where userId = 10001")
    var oldAddress = ctx.Db2.Query("select address from t_address where userId = 10001")

    err := ctx.Db.Update("update t_user set name = ? where userId = 10001",newName)
    err2 := ctx.Db2.Update("update t_address set address = ? where userId = 10001",newAddress)

    if err != nil || err2 != nil{
        //任意一个出错时，回滚数据
        ctx.Db.Update("update t_user set name = ? where userId = 10001",oldName)
        ctx.Db2.Update("update t_address set address = ? where userId = 10001",oldAddress)
    }else{
        //没有出错时，提交执行返回
    }
}

func go1(){
    //假设两个请求并发
    go changeNameAndAddress("fish","addr1")
    go changeNameAndAddress("cat","addr2")
}

当没有多行事务保证时，我们会用上述的代码来实现多行事务。即使不考虑App服务器可能在中途宕机产生无法自动回滚的问题，也会产生第一类更新丢失的问题。因为在并发的情况下，没有对修改记录进行加锁，回滚的时候，可能会丢失B事务对name设置为cat的更新。

为什么修改记录时自动加锁能解决这个问题，因为加锁能保证对当前行的更新只有一个事务来产生的，当事务回滚时，只需要用一个undo记录就能回滚了。不加锁时对当前行的更新可能是多个事务来产生的，当事务回滚时，无法用一个undo记录来回滚。

7.2.4 undo日志

undo日志的想法比较直观了，中途宕机可能会找不到旧数据来回滚数据，例如，上面App的例子中，oldName和oldAddress都在内存上，宕机重启后无法找到旧数据来回滚到对应的记录。那么解决方法就是，将oldName与oldAddress先写入undo日志，然后才能进行修改记录，宕机重启后就能再文件中找到这个oldName与oldAddress来回滚对应的数据行。

7.3 隔离性

在并发产生时，产生的问题远远比我们想象的多

7.3.1 脏读

现象：

脏读就是看到其他事务进行中的修改数据，其他事务未提交的数据，这样会对用户的体验产生困惑。

解决：

• 行级锁，当读取数据时，需要获取行的读锁。写入数据时，需要获取行的写锁。而多个读锁可以并行，读锁与写锁之间冲突，这样就能避免脏读，因为持有读锁的数据，不能被其他事务修改。但是，这种实现对行产生很多锁，大大提高了延迟，很可能产生死锁。
• 快照隔离，因为每一行同时只有一个事务在修改它，因此，每行在数据库中被维护两个版本，一个进行中的版本，一个已经提交的版本。查询的时候只读那些已经提交事务的行版本即可，这样就能避免脏读。这样既允许了对同一个行的写操作与读操作同时进行，大大提高并发性，而又不会提高延迟，也不会产生死锁。

7.3.2 脏写

现象：

脏写就是可以并发地对同一个行进行写操作，即使不考虑回滚产生的第一类更新丢失的问题，也会产生多行版本数据冲突的问题。例如，获取了车辆的是Bob，但是发票却发送给了Alice。

值得注意的是，这个问题在双写数据库与缓存的时候也会出现，因为数据库与缓存不在同一个事务中。最终造成，数据库显示的是value2数据，但是缓存显示的是value1数据，两者数据并不一致。要避免这个问题，要么让定时器定时扫描数据库定期写入缓存，要么让外部程序监控binlog时序异步写入缓存，这样至少能保证最终情况下，数据库与缓存总是保持一致的。

解决：

• 禁止并发写入同一行，A事务对该行的写入时，对该行获取写锁。B事务要对该行写入时，必须等待A事务的结束才能执行。

7.3.3 读倾斜（不可重复读）

现象：

读倾斜，就是对两个写入操作不在一个事务操作时，两次读数据库会产生不同的结果。例如，在照片的例子中，Alice前后检查它的两个账户，似乎总额少了100元。而另外一方面，转账者是在两个事务中，更新Alice的两个账户，其中一个加100，另外一个减100，按道理并不会出现这种情况。

读倾斜的本质在于，两次或多次读查询事务让数据变了，所以用户会产生困惑。在某些场景下时这个问题是不可接受的，例如在数据库的备份与分析场景中，多次查询会产生不断变化的数据库视图，得到的结果是不稳定和不可靠的。当然，我们也不能要求备份和分析场景中，要求数据库停下来不接受写请求，这是不现实的。

解决：

|-----------|-------------|----------|
|---以前的---|---进行的-----|---未来的--|
------------[tx_min~tx_max]----------

使用基于事务号的MVCC可见性分析，每个读事务都会分配一个事务号id为tx。每个读事务在开始执行时都会获取三部分信息。

• 以前的，tx_min，这个事务号以下的事务都是可见的，因为这个事务号以下的事务都全部已经完成了。
• 进行的，tx_min~tx_max，这个事务号之间的写事务是不确定的，有些事务已经完成了，有些事务是进行中的。对于这个段的事务号，数据库会给与一个列表，明确标注每个事务号对应的事务状态，已提交的，已回滚的，还是进行中的。
• 未来的，tx_max，这个事务号以上的事务都是不可见的，因为这个事务号以上的事务都还没有开始。

然后，在对每一行的读操作时，根据该行的版本号来判断可见性。

• 如果该行的版本号少于tx_min，那么肯定可见
• 如果该行的版本号大于tx_max，那么肯定不可见
• 如果该行的版本号位于tx_min~tx_max之间，那么查表来确定可见性。

最后，我们得到一个事务下多次查询依然能保持一致性的视图。因为多次查询的可见性都是基于同一批的tx_min，tx_max，和tx_min~tx_max的事务状态列表。即使在第二次查询时，数据被修改了，但基于可见性分析，该读事务也会对新数据不可见。

这也被称为快照读隔离，这个方法就像查询的时候对数据库的某一个时刻立即冻结产生一个快照，然后所有查询都在这个快照上执行一样，在这个事务上的多次查询结果都是一致的。

7.3.4 第二类更新丢失（同行更新）

现象：

第二类丢失更新，是指并发时读到了同一行数据，然后执行更新时也是更新到同一行。例如，用户1和用户2都是执行原子的递增操作。结果发现，两次进行递增以后，数字也是仅从42更新到43，只递增了1次。这相当于用户2的更新操作丢失了，就像从来没有递增过一样。所以这称为，第二类丢失更新。

第二类丢失更新是十分常见，和必须留意的并发问题。因为我们常见有扣除积分，扣除库存，扣除账户余额，扣除优惠券等的常见操作，在并发场景下就会出现，并发扣除两次，但实际只扣除一次的问题，这会造成严重的业务亏损。你试想象，并发1元抢购iPhone手机多次，但库存仅减去1次的情况，这会造成超卖的严重问题。

解决：

7.3.4.1 原子递增操作

原子操作，在一条基础语句里面执行sql递增操作，“update counter set count = count- 1 where counter = 10001”。但是，这样做还需要进行一次select操作取回更新后的数据。这个不失为一个好方法，在没有提供多对象原子事务的NOSQL数据库，这是唯一的防止第二类丢失更新问题的方法。例如MongoDB和Redis数据库中，都有提供类似的原子操作。

7.3.4.2 显式加锁

显式加锁 ，使用类似的语句，“select count from t_counter where counter = 10001 for update”，来对该行进行显式加锁。这是悲观锁的方法，有效可行。

7.3.4.3 自动检测

自动检测，PG中提供了默认使用乐观锁来解决这个问题。启动事务时，获取最新的写事务ID为txid。然后写入数据的时候检查该行的最新版本号是否少于txid，然后不是的话，证明该行被其他更加新的事务修改了，最后报错并放弃其中一个事务。

这种方式，决定了最先写入者胜。并且不需要加锁，大大降低了并发隔离的消耗。唯一的缺点是，并发出现时，另外一条事务会被整条回滚，用户需要手动重试。

7.3.4.4 原子比较操作

原子比较操作就是使用原子的compareAndSwap操作。用sql表达就是上面的操作，更新的时候不仅要检查数据，还要检查原数据的版本号。对于不支持乐观锁的NOSQL数据库，它们也会提供ompareAndSwap操作来解决这类问题。同样地，这种方法能大大降低了并发隔离的消耗，但仍然需要用户手动重试。

7.3.5 写倾斜（不同行更新）

问题：

写倾斜就是进行同一个读操作，然后更新或者插入到不同的行中。例如，在图片中，至少有2个医生值班的时候才可以请假。但是，在并发的条件下，可能会产生没有医生值班的结果。他们检查的都是同一个查询条件，select count(*) from doctors where on_call = true，发现都是为2，满足了可以请假的条件，然后更新到不同的行中，结果导致所有医生都请假了。

类似的问题还有：

• 检查用户名重复，两个并发都检查了用户名不存在，然后同时插入，接着就发生了用户名重复
• 多人预定一个会议室，两个并发都检查了会议室没有人占用，然后同时插入，接着就发生了会议室预约冲突的问题

解决：

7.3.5.1 索引约束

• 使用唯一约束来保证用户名不会重复
• 使用gist索引来保证会议室的预约时段不会重复

使用索引的特性来简单有效地解决这个问题，但是可以解决的问题不多，例如医生值班的问题就解决不了。

7.3.5.2 多行加锁

select * from doctors where on_call = true and shift_id = 123 for update;

对于查询以后执行的都是update或者delete操作时，可以对多行进行加锁操作。这保证加锁以后，其他写事务读到on_call为true的字段时就需要等待，值得本事务完成。

7.3.5.3 间隙锁

select * from t_user where name = "fish";

insert into t_user(name) values("fish");

但是，对于查询以后的操作是insert操作的时候，就不能够进行简单地用加锁操作。因为select时候的加锁仅能够对现有的已经存在的行进行加锁，不能对未来的未出现的行就进行加锁。当select的行为空的时候，加锁就没有对任意行执行锁操作。自然地，另外一个并发事务遇到一样的select请求时也不会等待。

select * from t_user where name = "fish" for update;

在mysql的RR隔离模式下，对于非唯一索引，提供了一种额外的锁类型，称为间隙锁。这种锁会在非唯一索引，在RR隔离模式下自动使用的。使用了间隙锁以后，当插入数据的时候，先在间隙的位置视图获取插入意向锁，只有在获取成功以后才能执行插入操作。而，插入意向锁，与间隙锁是冲突的。这个机制实现了对未来不存在的数据来加锁，能有效地解决这个问题。但是，这种间隙锁的缺点在于，它锁的间隙特别大，我们要锁47的数据时，就要在现有记录的41和49之间使用间隙锁，那么任何的42，43，直到48之间的数据插入操作都不被允许。

7.3.5.4 实体化加锁

select * from t_lock where lock_type = "add_user_name" for update

select * from t_user where name = "fish";

insert into t_user(name) values("fish");

对于没有间隙锁的数据库，例如PostgresSQL和Oracle，如何解决对未来数据需要加锁的这个问题。它的方法是转化为现有的行加锁问题。当检查到用户名在数据库不存在时，就对t_lock表的一个固定行进行加锁，然后再执行一次select操作，最后进行插入操作。这样的确可以避免这个问题，但是加锁的粒度太大，相当于所有的用户插入操作都要排队等待t_lock的这个固定行的锁，插入的并发度大幅下降。

一个优化方法是，t_lock表使用多个固定行，然后加锁的时候对用户名哈希，来加锁不同的固定行，这样加锁的粒度分散，并发度得到提高。

同理，对于会议室的预约问题，可以对会议室的按月份的行进行加锁。对于医生预约的问题，可以对医生的科室进行加锁。这种加锁的方式称为实体化加锁，加锁的目的仅仅是为了防止写倾斜的问题，没有实际的存储意义。

7.4 隔离级别

在事务中，我们有多个隔离性的问题。不同的数据库各自都有提供的不同的隔离模式，这是为什么呢。因为要完全解决并发隔离问题，要么是完全推给数据库来处理，但这样性能很差，并发度很低。要么是开发者结合场景，部分使用数据库自动处理，部分使用手动加锁来处理。这样的话性能比较好，并发度较高，但对开发者的要求也更高了。因此，不同的隔离模式，我们需要仔细注意它们的区别。

7.4.1 读未提交

任何的关系式数据中都没有提供读未提交的隔离模式，这会让数据库产生脏读的问题。

但是，对于分布式事务中间件中，GTS采用的就是读未提交的模式，这可能会产生比较多的隔离问题，和较差的用户体验，开发者在使用时需要仔细留意。

7.4.2 读已提交

读已提交是PostgresSQL的默认隔离模式，无论是MySql，还是PGSql，开启读已提交的隔离模式，都能避免脏读和脏写的并发问题。

在单机数据库中，原子提交可以用WAL日志+锁来实现。但是，在分布式数据库中，原子提交就是一个更为复杂的问题了，它常用2PC来实现。2PC在第9章有更详细的介绍。

7.4.3 可重复读

可重复读是MySQL的默认隔离模式，无论是MySql，还是PGSql，开启可重复读的隔离模式，都能避免读倾斜的问题，他们的解决方法都是一样，使用MVCC的多版本来实现。而MSSQL的可重复读的隔离模式，比较特别，它是通过2PL来实现的，这种方法严格来说是实现了可串行化的隔离模式。

MVCC功能在实现时，需要对不同的行赋予一个事务号，读事务执行时需要比较每个行的事务号，用来确定这一行是进行中的未提交的数据，还是过去已经提交的数据。因此，它需要事务号允许进行全序比较。在单机数据库的实现中，事务号是通过递增原子变量来实现，而在分布式数据库中，可以用分布式事务号节点来分发(OceanBase)，也可以使用原子钟来做这个事务号（TrueTime，Spanner实现）。

在可重复读的隔离模式，除了打开了MVCC的功能外，还会出现：

• PostgresSQL还会开启自动乐观锁检测，来避免第二类更新丢失的问题。这种方法不需要任何的开发者干预，自动检查到同行更新的第二类更新丢失问题。但是，这种方法无法解决写倾斜的问题。
• MySQL还会开启间隙锁的功能，间隙锁能有效地同时解决第二类更新丢失问题，与写倾斜的问题，但是这种方法需要开发者手动上锁，需要仔细安排锁的顺序，否则可能产生死锁。

7.4.4 可串行化

可串行化是最为自动化的隔离模式，它的目标是，不需要任何的开发者干预，就能完全避免所有的并发问题。这是如何实现的呢，不同的数据库有不同的实现。

7.4.4.1 单线程

最为简单的方法是，每个事务都真正地串行化地执行，就能完全解决并发隔离的问题。但是，单线程的缺点也很明显，即使在多核机器下，所有写请求都单线程在执行，相当于写请求都只有一个核在执行，其他核在等待。因此，单线程实现的可串行化隔离下，吞吐量必然受限于单核处理能力，即使升级再多的核心也无法提高写的吞吐量。

具体实现：

• Redis的Lua事务，Redis中处理数据的部分，只有一个线程在执行。开发者可以直接发送一段Lua代码来操作多个key的数据，从而解决了多行事务的并发隔离问题。
• 应用级别的全局锁，在应用级别对所有写请求都需要争夺全局同一个锁，从而避免并发隔离问题。这种方法十分简单粗暴，完全没有悲观锁的死锁问题和乐观锁的不断重试的问题，但是只能用在并发量不大的场景。
• 存储过程，将业务逻辑用存储过程的方式写在数据库，从而避免了应用层与数据库之间的多次网络往返的延迟问题，这种方法大大提高了单线程的每秒处理事务的能力。但是这种方法比较难以调试和扩展，对于事务要求性很高，并发度要求也很高的场景，不妨为一个好方法。
• 应用级别的分区单线程，对每个请求进行分区，每个分区下使用单线程来执行，这样就避免了并发冲突的问题，这个方法非常值得一试。但是，对于请求无法被预先分区的情况，就无能为力了。

存储过程的意义

7.4.4.2 两阶段加锁2PL

2PL和2PC是两件事情，它的方法很简单。

• 如果事务中执行的是读操作，那么就尝试对这个读的SQL操作加上for share锁，从而保证读取的数据不会被其他事务修改。
• 如果事务中执行的是写操作，那么就尝试对这个写的SQL操作加上for update锁，从而保证对这些数据是只能被当前事务所修改的，其他事务不能修改，也不能读取。

在Mysql中，读已提交，和可重复读的隔离模式，如果没有显式使用加锁操作，原子递增操作肯定会失败，时序如上。

但是，在Mysql的可串行化隔离模式，实现的是2PL实现，它能在没有显式加锁的操作下，实现了原子递增操作。

2PL实现的显然缺陷是，自动的加锁不是提前加到最强的锁级别，容易出现死锁操作。相应的，在手动加锁的场景，我们加锁一般是使用for update锁（因为后面的操作要更新这一行，所以需要提前申请for update锁），而不是for share锁，同样的时序并不会出现死锁问题。

到这个位置，你可能会问，为什么2PL要区别for share锁和for update锁，全部用for update锁不好吗。因为：

• 不是所有事务都是有写操作的，分析和备份场景只是一个纯读操作，但是为了避免读倾斜的问题，才用的是可串行化隔离模式。如果纯读事务，使用for update锁，会造成大量行无法进行读取操作（多个for share锁可以兼容，但是多个for update是不兼容的），这显然是不合理的。
• 有时候写事务只是为了保证存在性而已，不是为了更新这一行。例如，添加子类目的时候，我们读取父类目是否存在，只有父类目存在才能添加。如果对父类目进行for update锁，那么其他事务无法对父类目进行读取操作，这显然是不合理的。

总结一下，2PL的特点：

• 无需开发者干预，自动解决所有并发隔离问题
• 相比单线程实现，能充分调用多核的吞吐量，支持更大的并发量和吞吐量
• 所有读写操作都需要自动加锁，锁开销要比单线程多得多
• 并发竞争较多时，容易造成死锁
• 严格的2PL实现，需要谓词锁的实现，也就是间隙锁的支持，否则依然会产生写倾斜的问题。

7.4.4.3 可串行化的快照隔离SSI

所有的并发隔离其实可以归纳为一个话，根据读操作执行的写操作时，读操作是否被其他事务修改了，造成了过期。2PL使用加锁来保证读操作无法被其他事务修改，而SSI的想法是通过建立因果关系，读写依赖来检查读操作是否过期了。它相当于乐观锁的更广义的版本。

SSI事务会检查两部分操作：

当前事务A在读取行时，该行是否在被其他进行中的事务B在修改。当事务B在提交时，就通知包含写操作的事务A失败了。

当前事务A在读取行时，该行并没有被其他进行中的事务B在修改。但是，事务B而后修改了这一行，那么当事务B提交时，也去通知这个包含写操作的事务A失败了。

总而言之，SSI在内存中维护一个视图

• 读取的行是否正在修改
• 读取的行是否在未来修改

当写事务提交时，通知依赖它写过的行Line，其他事务读过的这一行Line的，全部失败。

就目前而言，只有PostgresSQL实现了以SSI为基础的可串行化隔离，但是PostgresSQL的SSI实现，没有检查未来新增行所造成的读操作过期的问题，也就是无法解决部分的写倾斜问题（因插入数据而让读操作过期的写倾斜）。但总体而言，SSI的未来依然很乐观，因为它：

• 无需开发者干预，自动解决所有并发隔离问题
• 相比单线程实现和2PL，能充分调用多核的吞吐量，支持更大的并发量和吞吐量
• 无需锁开销，串行化代价比2PL要少得多，几乎与单线程持平
• 更容易在分布式事务中实现可串行化隔离
• 唯一缺点是难以实现，插入数据造成的写倾斜问题，PostgreSQL暂时也没有实现

8 分布式系统的挑战

分布式系统的意义在于，容错，即使部分节点挂了，依然能无损地对外服务。这是单机所无法实现的。

8.1 网络

网络有延迟是常见的，原因可能是：

• 网络排队引起的延迟
• CPU核处理网络包的延迟
• 虚拟机在切换时产生的网络延迟

所以，不要在应用层对网络延迟有任何假设，和界定。

更好的做法是，持续对现有的网络进行测量，以确定什么样的延迟量是对方失效的标记。

当网络延迟发生的时候，我们无法确定是以下的哪种情况发生了：

• 请求丢失了
• 对方节点失效了
• 响应丢失了

8.2 时钟

8.2.1 现象

墙上时钟是不可靠的，因为：

• 漂移。电子钟总是有累积误差，每天同步一次，偏差大概为17秒，但没有上限保证。
• 回跳。当电子时钟跑得过快，然后与服务器同步以后，就会出现时钟回跳的情况。所以，不要期望墙上时钟是严格递增的。
• 精度有限，可能相等。电子时钟有可能会出现两个观测值是相同的情况。

单调时钟是墙上时钟的一种改进，特点是：

• 总是严格递增的，没有回跳和偏移的情况，也没有相等的情况。
• 但是难以在不同节点中比较，例如不同机器的单调时钟相互比较是没有意义的。

8.2.2 场景

LWW的冲突处理办法，如果使用墙上时钟来处理，就会导致：

• 时钟回跳导致丢失数据
• 时钟相等导致无法仲裁选择哪个作为唯一数据

分布式数据库，在实现MVCC时，如果使用墙上时钟来作为事务号，就会导致：

• 时钟回跳，导致读到了进行中的数据，脏读发生了
• 时钟相等，无法确定是否读这个行，因为无法判断这个行是过去的，还是进行中的。

8.3 进程暂停

进程在代码中的任意一个位置都可能产生长时间（超过10秒）的暂停，这是在现实环境中曾经出现过的，这是因为：

• GC产生时，执行了Full GC导致长时间暂停
• 虚拟机的切换和迁移
• 磁盘IO读到了坏页
• 内存换页到磁盘
• 操作系统切换进程上下文。

进程暂停的问题告诉我们，不要在检查了时间或者获取锁以后，就假设它是正常的。

HBase就曾经出现了这个问题。对锁服务的申请成功后，有30秒的占用时间，开发者假设了代码不会超过30秒。但是，GC产生了长时间的进程暂停，使得假设失败了。这个进程在30秒以后仍然在修改文件存储，导致文件被损坏了。

8.4 原则

分布式系统有三大不可控的因素，那么我们唯一可采取的原则是什么。

8.4.1 真相是由大多数来决定的

我们使用网络延迟来确定节点是否挂了，但是网络延迟是不确定的，有些节点觉得A断了，但是有些节点却觉得A没有断。在这种情况下，主从节点的主从切换会产生脑裂行为。问题的关键在于，不是节点A是否真的挂了，而是所有节点是否对节点A是否挂了的这个现象是否达成了一致。例如，即使节点A没挂，但是大家投票一致，觉得它挂了，那么大家就会选择某个节B点作为主节点，并且一致拒绝来自节点A的主从复制的写请求，这样没有产生脑裂问题，也不会丢失数据。

如果有一种算法能让大家对一件事情达成协议的一致，那么节点A是否真的挂了并不重要。而且重要的是，这种算法能在允许部分节点失效的情况下依然能正常工作。

同理，分布式的MVCC实现中，墙上时钟是不可靠的，因为它不是严格递增的。很自然地，我们可以指定一台机器来实现全局的事务号统一分配，但是很明显，这有单点故障的问题。我们需要的是，一个能在分布式环境下，部分节点失效时，依然能分配严格原子递增的全局事务号的算法。这个事务号既不会回跳，也不会出现相等，也没有空隙的问题。

于是，所有的分布式问题问题最终都指向到了同一个问题，实现一个分布式的共识算法，同时允许任意部分的节点失效时，依然能正常工作。

8.4.2 用fencing令牌来保证锁

fencing令牌是解决进程暂停的常见方法，每个获得锁的客户端，都顺带获取一个递增的令牌，然后来请求存储。存储在下一次遇到更大的递增令牌时，就自然拒绝前面更小令牌的请求。

很显然，fencing令牌简单，但依然需要一个共识算法来保证严格原子递增的令牌。

9 一致性和共识

9.1 线性化与一致性的术语

一致性这个词简直太滥用了，我们经常会混淆中CAP中的一致性，而ACID的一致性，和事务隔离级别的可串行化的含义。

• ACID的一致性C，说的是数据库的约束（唯一约束，非空约束）在任何条件（宕机重启，高并发）都会被保证。
• 可串行化，说的是可以并发读写多个对象，但就如串行化执行它们一样，保证不产生并发隔离问题。
• CAP的一致性，其实说的是线性一致性，说的是在分布式中读写单个对象，就如同在单节点一样，保证了写后读，读后写，单调读，单调写的一致性。

我们研究共识算法，关键在于研究如何在分布式中实现可线性化的这个问题。在分布式的主从节点分布中，我们看到不同的用户，由于复制延迟的关系，他们无法实现单调读的一致性。对于单个对象，在分布式环境中可能出现：

• 写了新值后读到旧值，违反写后读。
• 读到新值后再读到旧值，违反单调读。
• 连续写值，类似原子递增操作，但结果不一致的，违反单调写。
• 写入值进行原子比较执行后执行，类似cas操作，但结果不一致的，违反读后写。

我们不加证明地指出，分布式中的一致性级别依次为：

• 最高，可线性化（线性一致性），全序关系广播，共识问题，这三个问题互相等价。四个保证都能实现。
• 中等，顺序一致性。不保证写后读，但是其他三个都能保证。
• 最低，弱一致性。四个都没有保证。

9.2 可线性化（线性一致性）

9.2.1 定义

在分布式数据中，对一个分布式系统的单对象操作就像单机一样，同时满足四个保证。这意味着：

• 写前，读的为旧值
• 写后，读的为新值
• 与写时间重叠的区间，任何的读操作可以返回旧值或者新值。但是当某个时刻的读操作为新值后，之后的所有读操作都必须为新值。

可线性化上有三个操作：

• read，对单对象的读操作
• write，对单对象的写操作
• cas，对单对象的compareAndSwap实现

9.2.2 场景

有了可线性化的操作，我们可以实现以下场景：

• 原子递增，可以用cas操作实现
• 分布式锁，可以用cas操作实现
• 唯一约束，可以用cas操作实现

9.2.3 实现

要实现可线性化，我们直观地有几种做法：

• 单节点，显然这样有单点故障，没有分区可用性
• 主从复制，有强一致性，当从节点宕机时，仍然可以对外服务，并满足可线性化要求。但是当主节点挂机后，可能产生脑裂问题，这个时候无法保证可线性化要求。因此，需要额外的机制来避免脑裂问题，才能实现主从复制的可线性化。
• 多主复制，多主节点之间使用异步复制，数据有延迟，不可能实现可线性化。
• 无主复制，无主复制使用墙上时钟会有丢失数据的问题，不可能实现可线性化。即使无主复制使用严格的quorum设置，仍然无法满足严格的可线性化。

讨论的结果得到，我们另外需要一个全新的算法来实现线性化问题，这个问题就是我们说到的共识算法。Paxos，Raft这类算法。

9.3 全序关系广播

9.3.1 定义

全序关系广播就是向任意一个节点发送消息时，该节点也会向其他节点广播这个消息。但是，所有节点都对所有节点收到的消息顺序（全序关系）达成了一致，并且保证了消息不丢失。它必须满足：

• 可靠发送，如果消息发送到了某一节点，那么它一定发送到所有节点。
• 严格有序，消息总是以相同的顺序发送给每个节点。

而且，即使某些节点出现了故障，全序关系广播的要求也必须保证以上两点。

9.3.2 与可线性化的关系

与线性化不同的是，全序关系广播是基于异步的模型，保证消息以固定的顺序可靠地发送，但是不保证消息何时发送成功。而可线性化描述的是一个基于同步的模型，两个是不同的问题。但是，令人惊讶的是，两个问题是互相等价的，即如果实现了其中一个，就能实现另外一个。

如果已经有全序关系广播，我们可以这样实现线性化模型：

• write，向节点发送写消息，并且等待回复，成功以后才返回。
• read，向节点发送读消息，并且等待当前节点确定消息后，才执行执行的读操作返回。
• cas，向节点发送占用消息，并附带cas的旧数据，并且等待回复，成功占用后才执行真正执行cas操作，写入write消息，等待回复后返回。

如果已经有线性化模型，我们可以这样实现全序关系广播：

• 每个消息发送前，使用原子递增计数器读取线性化计数，然后作为消息号对所有节点发送消息。
• 接收者必须按照无空隙的消息号逐个处理消息。例如，如果完成了消息4的发送，而后接收到了消息6，则在回复消息6之前必须等待消息5的到来。

9.3.3 场景

全序关系广播，可以看成是异步的可靠的日志传递。那么，我们可以将主从复制的binlog直接写入到全序关系广播实现中，那么我们可以得到可靠的保证不丢失一行的主从复制模型。它与同步模型不同的是，它仅需要任意的大多数的节点的同步回复，就可以返回成功。

9.3.4 实现

这与可线性化模型一样，最终都指向到了，共识算法。

9.4 共识问题

9.4.1 问题

共识算法就是各个节点对某一个决定进行投票，以确定该决定是否成功。共识问题的困难在于，各个节点可以任意时候出现分布式系统的三个问题。

9.4.2 实现

我们不加证明地，大概地指出共识算法的过程为：

• 首先投票一个主节点。各节点可以自由睡眠一段时间后各自醒来。最先醒来的将发出将自己选为主节点的请求，并群发给其他节点。其他节点，如果在没有收到其他主节点的请求时，就返回成功，确定该请求的节点为主节点。当主节点收集到了足够的票数以后，就将群发通知自己确实成为了主节点。
• 然后发出决议。任意节点收到要发送消息的请求后，将该消息转发给主节点处理，主节点统一对消息排序，然后对所有节点发出对该消息请求投票的通知。
• 投票决定决议，主节点只有在该消息收集到了足够的票数时，才确定该消息是被处理成功的。

以上流程为一轮共识决策的过程。多个消息的发送就会实现为多轮的共识决策。

9.4.3 与全序关系广播的关系

显然，全序关系广播就是持续的多轮共识

9.5 顺序一致性

顺序一致性是一个比可线性化更弱的保证。不保证写后读，但是其他三个都能保证。如果用全序关系广播来实现顺序一致性，是这样的：

• write，向节点发送写消息，并且等待回复，成功以后才返回。
• read，直接在本地节点读消息。
• cas，向节点发送占用消息，并附带cas的旧数据，并且等待回复，成功占用后才执行真正执行cas操作，写入write消息，等待回复后返回。

可以看出，仅仅是read的实现与普通实现不同，直接在本地节点读消息，而不经过所有节点的消息广播。这样的结果是，读取的速度更快，但是最新的写入消息的请求可能还没到达当前的节点，所以，读出来的数据是旧的。

但依然保证了，单调读，然后本地节点的写入顺序与所有节点的写入顺序是相同的。不会出现，先读新数据，再读旧数据的问题。

9.6 ZooKeeper

ZooKeeper是封装了Paxos算法的一个库，它提供了很多分布式有用的工作。

• 线性化读写，对一个单对象的读写就像在单节点一样简单透明
• 分布式锁，每个请求在zk的同一个目录下注册文件，然后检查自己的文件名是否最小的，来确定是否获得了锁。当前一个请求释放锁以后，下一个请求就会收到通知，它是当前最新的最小文件。这对分布式文件的锁机制提供工具。
• 故障检测与通知，zk对多个机器进行监控，当某台机器宕机以后，就设置它为宕机状态，并通知所有其他机器这台节点宕机了，并释放宕机机器所持有的资源。这对主从自动切换非常重要。

关于Zookeeper的使用场景，可以看这里

9.7 2PC事务

9.7.1 过程

1.begin;
2.update ....;
3.update ....;
4.commit;

2PC事务是分布式事务透明提交的方法，它的工作流程为：

• 第1步的时候，是应用服务与协调者申请全局事务ID
• 第2，3步的时候，是应用服务直接跟各数据节点，执行sql操作，每个sql操作都附带这个全局事务ID。
• 第4步，提交的时候，应用服务器告诉协调者，然后进入了阶段1。
• 阶段1，协调者询问各个数据节点，各个节点进行Prepare操作，将数据写入WAL日志，保证宕机重启后该事务依然能够正常提交，不丢失。但是，这个阶段，所有节点都不释放锁。Prepare操作完成后，告诉协调者，操作成功。
• 协调者收到所有的节点的成功操作后，判断为可以commit，然后写入本地磁盘。然后进入阶段2。
• 阶段2，协调者告诉所有节点2，可以正式提交了，然后每个节点设置事务状态为已提交，并释放锁。

9.7.2 FAQ

2PC的过程还是比较简单的，但是，重点在于，为什么要这样设计。

9.7.2.1 为什么分2步

1.begin;
2.update ....;
3.update ....;
4.commit 节点1;
5.commit 节点2;

2PC的特点是，原来单机事务提交，接收到commit指令时，写入WAL日志，和释放锁是同一个步骤完成的，为什么2PC要分为2个阶段。因为，如果我们沿用单机事务的方法，提交的时候逐个提交每个节点，就会出现部分极限情况失败的问题。例如，第4步向节点1请求commit，节点1返回成功了。然后在第5步我们请求向节点2执行commit，但是刚好这个时候节点2已经挂了，无法完成commit请求。这样就会出现不一致的问题，因为节点1的数据已经提交了，无法回滚。节点2重启后必然回滚到事务回滚的状态。最终导致，节点1的数据是提交的，但是节点2的数据是回滚的，违反了事务是原子性的要求。

1.begin;
2.update ....;
3.update ....;
4.prepare 节点1;
5.prepare 节点2;
6.commit 节点1;
7.commit 节点2;

因此，2PC分两步提交，先对每个节点进行prepare请求，保证他们的数据已经落地，即使任意一个节点宕机重启后也不会自动回滚数据，也不会提交数据，而是只会去等待协调者的最终仲裁结果。然后，我们模拟一下刚才的情况，第4步成功了，但是第5步节点2宕机了。那么协调者就会仲裁该事务无法提交，然后执行回滚节点1的数据，并且不断重试节点2，告诉它重启后应该要回滚数据。

9.7.2.2 为什么协调者仲裁后要先落地

1.begin;
2.update ....;
3.update ....;
4.prepare 节点1;
5.prepare 节点2;
6.commit 节点1;
7.commit 节点2;

即使这样设计后，还会出现以下问题。第4步和第5步都成功了，第6步也成功了，然后注意，协调者自己宕机了。协调者重启以后，它不清楚自己进行到了那一步，它也不知道应该要对节点1和节点2是应该执行commit还是rollback命令。因为它忘掉了，两个节点的prepare的结果。

1.begin;
2.update ....;
3.update ....;
4.prepare 节点1;
5.prepare 节点2;
6.仲裁为成功，协调者自己写入本地数据库，设置该事务为提交状态
7.commit 节点1;
8.commit 节点2;

因此，协调者仲裁后要先落地才能执行阶段2操作。如果在执行第7步的时候宕机了，协调者重启后，可以查询本地数据库，然后逐个提交或回滚每个节点就可以了。

9.7.2.3 为什么prepare阶段必须保证commit阶段的成功

1.begin;
2.update ....;
3.update ....;
4.prepare 节点1;
5.prepare 节点2;
6.仲裁为成功，协调者自己写入本地数据库，设置该事务为提交状态
7.commit 节点1;
8.commit 节点2;//反悔了，不能commit，但是节点1已经commit了，无法回滚。

节点在prepare阶段返回ok的时候，它就隐含了保证，它如果收到commit请求的时候，必须是无条件成功的。例如在上面的例子中，如果所有节点在prepare阶段都返回ok，仲裁者也仲裁为整个事务为提交，而节点2在commit的时候却进行反悔，就会导致无法回滚节点1的问题。

如果没有“prepare阶段必须保证commit阶段的成功”，2PC其实就是和1PC没有区别。2PC的关键优化在于，先让各人宣誓，再决定要不要执行。

9.7.2.4 为什么prepare阶段不释放锁，且还需要写入WAL日志

1.begin;
2.update ....;
3.update ....;
4.prepare 节点1;//释放锁
5.仲裁者询问节点2的prepare结果，由于节点2刚好宕机，处于等待状态。
6.节点1的锁已经释放了，该行数据被其他事务修改。
7.仲裁者询问节点2的prepare结果超时，判断事务失败，企图回滚节点1的数据。
8.由于节点1的时候在第6步被其他事务修改了，若此时直接回滚，将产生第一类更新丢失，看7.2.3节。

prepare阶段是不允许释放锁，这是显然的。如果prepare阶段释放锁，一旦第4步成功并释放锁，但是第5步失败的时候，就无法回滚第4步的数据。这样的话就会导致，数据不一致的情况。

再贴一次第一类更新丢失的例子，由于rollback所产生的丢失。

所以，为了避免脏写的问题，整个prepare阶段都需要上锁，直到该节点收到第二阶段的明确仲裁结果以后，才能释放锁。另外，考虑到节点可能因为宕机重启以后会释放锁，所以节点在prepare阶段也会同步写入WAL日志，节点在重启以后，会立即读取WAL日志，然后恢复到prepare阶段。

至于那些，在未进入prepare节点的节点，则不需要写入WAL日志，在宕机重启以后直接对外服务就可以了。

9.7.3 总结

2PC事务的隐含要求：

• Prepare阶段返回Ok的时候，如果接收到Commit指令，db必须要保证成功。
• Prepare阶段开始上锁，直到收到仲裁者的Commit或者Rollback指令，才能释放锁，中途即使遇到宕机重启等现象都不能释放锁。
• 仲裁者在Prepare阶段返回Ok的时候，必须要写入WAL日志，以便宕机重启以后，能够恢复到Prepare阶段。

2PC事务的特点在于：

• 透明，应用层无需改动就能支持分布式事务
• 延迟大，commit操作从一阶段变为两阶段，延迟肯定变大了。
• 只支持读已提交隔离，显然，多节点之间缺少全局事务号，无法实现可重复读，甚至串行化隔离。
• 锁的时间长，节点在Prepare阶段需要上锁，直到其他节点明确返回Prepare结果或者超时以后，才能释放锁，锁的时间比1PC要更长。

2PC事务的另外一个显然缺点在于，协调者是单点的，一旦宕机，所有数据节点都无法独自释放锁资源，以及独自提交或者回滚事务，它必须等到协调者重启为止。但是，如果协调者永久丢失数据了，那就这个分布式事务就称为悬疑未解之谜了，这些数据永久地被锁了。因此，2PC的一个改进时，将仲裁结果写入Zookeeper算法，而将协调者设计为一个无状态的服务，这样就能避免单点故障问题了。

10 批处理系统

10.1 Unix工具

Unix工具成功的原因：

• 不可变文件，无副作用，任意重启而不损坏原文件。
• 中途结束，可以随便取出输入文件重来一遍，不需要重启整个流水线。
• 逻辑与布线分离，每个程序只负责处理，而不清楚自己的输入和输出来自哪里。管道则负责布线的问题。

10.2 MapReduce的过程

MapReduce的过程

• 本地调用map任务切分数据，数据按照reduce任务的分区数量写入到不同的文件上。有多少个reduce分区就有多少个文件。
• 每个分区文件执行sort操作
• 每个reduce分区从多个map任务中下载对应的分区块排序文件
• reduce合并多个排序分区块，生成单个排序文件
• 对单个文件执行reduce任务

从MapReduce的过程中可以看出，它总是隐含了sort操作

10.3 MapReduce的join实现

使用MapReduce，我们如何实现两个表join：

• 排序合并join，利用MapReduce的排序特性，在reduce端将同一个key的数据靠近地放在一起。
• 广播join，将join的其中一个表数据整个复制到另外一个表的map节点，另外一个表直接只执行map操作就可以了。这种方法的前提是，其中一个表的数据量比较小。
• 分区哈希join，两个表都是相同分区数量，和相同分区方式时，join的时候，就仅需要对各自对应分区进行广播join操作就可以了，大大减少广播join需要的小数据量要求。前提是，两个表都是相同分区。
• 分区哈希合并join，两个表都是相同分区，且都已经按照key排序时，join的话，可以直接在map端依次读取两个表数据，进行归并算法join就可以了。前提是，两个表都是相同分区，且都已经排序好了。

10.4 MapReduce的group实现

使用MapReduce，我们如何实现一个表的group：

• 排序group，reduce端排序后，在reduce任务里执行group操作即可。

10.5 数据倾斜

数据倾斜的特点是，部分热点数据占用的key范围很小，但数量却很多。如果是使用排序合并的join算法，就容易导致部分节点很忙，其他节点很闲的问题。解决方法是：

• 热键数据随机分发reducer，热键数据随机复制到其中的一个reducer，而热键对应的另外一个表数据，则全量发送到所有的reducer上。然后在reducer进行join操作时，热键数据直接查本地的另外一个表数据，非热键数据找附近的另外一个表数据。从而让各个reducer的工作量都均衡。这种方法前提是，另外一个表的数据量中等。
• 热键数据广播join，将另外一个表的热键对应数据直接复制到map端，然后在map端进行区分，热键数据在本地使用广播join，非热键数据分发到reducer进行join。这种方法前提是，另外一个表的数据量较小。

数据倾斜遇到的是group任务，而不是join任务时，处理要简单一点。

• 首先，第一轮MapReduce，所有数据随机分发到Reducer上，在Reducer进行一次预聚合。
• 然后，第二轮MapReduce，对预聚合数据按照key分发到对应的Reducer上，对结果做最后的汇总聚合。

10.6 与分布式数据仓库的区别

MapReduce与分布式数据仓库的区别：

• 支持任意类型的数据，面向文件数据，而不是面向表数据。更适合处理日志分析，图分析的任务。
• 无固定模式，常用于收集在线OLTP的各个历史版本的所有数据，然后进行ETL操作，转换为统一的表格式，写入到数据仓库，最后在数据仓库做查询。
• 容错性高，作业数据量大，倾向于放磁盘，而不是放内存。

10.7 超越MapReduce

10.7.1 性能优化

MapReduce的性能优化方向：

• 整个工作流当成一个作业，而不是多个作业。中间状态不落地，任务之间数据仅使用网络来传递。
• 中间状态不落地，如何容错。Spark方法是，追踪数据祖先，对结果丢失数据的部分，找出它的祖先数据来重试。Flink方法是，运算符状态的检查点，失败时，从上一个检查点恢复状态，然后重做。
• 不再限定Map与Reduce的两个操作符，而是任意的操作符

10.7.2 图优化

图计算的特点是，同一个数据集不断用同一个算法迭代计算。

Pergel优化计算方向：

• 顶点计算后结果不落地，而是直接发送到它的下一个计算节点。
• 所有顶点完成这一轮以后，才能执行下一轮计算
• 定期快照所有顶点状态来容错
• 网络可能是瓶颈，单机可能更快。

11 流处理系统

11.1 消息系统

消息系统主要划分为三种：

11.1.1 直接传递

生产者与消费者之间直接的消息传递，不经过消息代理，特点是：

• 延迟很低，响应速度快
• 丢失数据，使用推方式时，消费者暂时掉线时，生产者就无法推送数据给它。使用拉方式时，生产者暂时掉线时，消费者就无法拉取数据。

11.1.2 消息代理

生产者发送消息给消费代理，然后消费代理发送消息给消费者，消息通过消息代理来中转，特点是：

• 支持多个消费者组（扇出发布订阅），以及单消费组下的多消费者（负载均衡）。实现的时候需要为每个消费者组维护一组状态，以记录哪些消息已经处理了，哪些消息仍然还没处理。
• 可能导致无序，当使用单消费者组下多消费者时，消费者消费消息可能是乱序的。因为消息消费失败时，会被之后重发消费一次，但这之前会被其他消费者消费了一部分以后的消息。
• 暂时的存储转发，总是假设消息存放在代理的时间很短。当消息堆积很多时，性能会急剧下降。

11.1.3 日志式消息存储

日志式消息存储是对传统消息系统的改进，特点是：

• 发送时分区，消息划分为多个分区来存储，在发送消息时就根据消息上的key作为路由，存放到不同的分区上。而传统消息代理，并没有在发送时分区，而是接收时根据负载分区。
• 固定有序，一个消费者组下，一个分区就只能由一个消费者单线程读取，不允许多个消费者消费同一个分区的消息。这保证了，消费者消费数据时是严格按照发送顺序消费的。即使某个消息消费失败了，消费者也要不断重试该消息，才能消费下一个消息。
• 吞吐量大，一个消费者的消息消费状态，仅需要一个偏移量就能描述，不需要传统的消息代理需要维护一组状态来描述，大大降低了消息状态维护的代价。
• 永久存储，日志式直接顺序写磁盘，当消息堆积很大时，性能依然保持高效。

11.1.4 对比

日志式消息存储对比传递的消息代理，它们的场景是：

• 日志式，吞吐量大，可靠性高，严格有序，时延中等（ms级别），无法真平衡（发送时分区，而不是消费时分区），不支持多样的消费功能
• 传统式，吞吐量小，可靠性中等，可能乱序，时延低（ns级别），绝对真平衡（消费时分区，保证不会出现消息消费倾斜问题），支持多样的消费功能（延迟消息，消息消费时选择）

11.2 数据库与流

数据库是OLTP的主数据，但是为了更好地提高查询速度，我们需要将它派生到其他的系统中，搜索引擎，和缓存。为了同时更新在线系统，和派生系统，我们常用双写的办法来实现。但是，这样会产生以下问题：

• 不一致，数据以不同的速度到达派生系统，导致派生系统和在线系统的数据永久性的不一致。
• 没有容错，如果派生系统暂时宕机了，那么请求在修改在线系统数据成功以后，不可能永久等待派生系统恢复后才能返回，这会导致无法更新派生系统的问题。

很显然，我们要求的是将派生系统与在线系统数据都看成一个原子操作，两个更新要么全部成功，要么全部失败。很自然地，我们希望使用2PC分布式事务来实现，但是这样的实现资源消耗太大，而且派生系统也没有锁支持，难以实现2PC分布式事务。

解决方法是，让请求只修改在线系统，然后在后台异步读取binlog来将数据库的修改记录信息写入到消息系统中（这称为CDC，变更数据捕获），最后派生系统通过不变的消息系统来逐个更新自己的数据。这种方法的优势在于：

• 原子性，简化多对象更新回滚问题，如果派生系统宕机了，数据将会一直保持在消息系统。派生系统恢复了，依然能读取消息系统数据来逐步更新自己的数据，最终达到与在线系统的一致性。也就是说，只要在线系统更新成功，这种方法保证派生系统也能更新数据，即使派生系统暂时宕机。
• 隔离性，消息系统保证了消息顺序与在线系统是完全一致的，不会出现消息乱序问题。再加上读取消息系统并写入到派生系统的操作是单线程的，因此无需考虑并发问题。这大大简化了派生系统在并发更新时需要锁机制的要求。

但是，这种方法的缺点也很明显：

• 异步更新，派生系统与在线系统的数据总是会有延迟的，不是像2PC事务一样的强一致性。你甚至可以将派生系统看成是从机，在线系统看成是主机，那么主从复制的延迟问题在这种方法里面都会一样出现。
• 派生系统与在线系统之间无法实现线性化，由于异步更新造成的延迟问题，应用中是不可能期望以派生系统数据视图为依据来更新在线系统的，这样会导致过期数据读取的问题。

总的来说，瑕不掩瑜，这种方法很可能是未来数据密集型应用的唯一正确方向，因为它提供了将命令模式需要的数据存储，与查询模式需要的数据存储划分开来，两者为各自的业务做最好的优化，大大提高了系统的吞吐量和可承载的数据量。而传统的开发模式中，SQL数据库同时承担了查询和命令的两种任务，最终导致SQL数据库难以支持复杂的规模也很大的查询而失败。这就是CQRS的一种想法。

11.3 流处理任务

对于一个事件流，我们对它进行流处理，常用于：

• 匹配，事件的模式匹配，CEP实现，常用于监控系统
• 分析，计算事件的累计效果和统计，Flink和Spark的实现，常用了实时聚合分析，漏斗价值分析
• 物化视图，计算两个表的实时join视图，Flink和Spark的实现，常用于支持大规模数据的实时联合查询。

11.4 流处理时间问题

在流处理中的我们需要注意：

• 事件发生的时间，和事件处理的时间，是不同的。事件里面需要添加一个发生的时间戳，而不是使用处理时的时间戳。
• 客户端时间戳可能是不正确的（没有与NTP服务器对齐），我们需要对客户端产生的事件进行校正。校正方法为，服务器校正的事件时间-客户端事件发生时间=服务器收到事件时间-客户端发送事件的时间。因为我们总是假设，客户端发送的时刻与服务器收到的时刻是相同的，不同的时间是仅因为时钟偏移产生的。

流处理窗口的类型：

• 轮转窗口，5分钟窗口，就是以每5分钟作为窗口
• 跳跃窗口，5分钟窗口，就是以当前为1分钟的窗口为边界，取前后的2分钟窗口为
• 滑动窗口，5分钟窗口，就是以当前时刻的前后2.5分钟时刻作为窗口
• 会话窗口，以时间上紧密相连的事件组合在一起，如果一段时间内用户没有操作，就会结束当前会话

11.5 流处理的join实现

流处理的join实现方式：

• 流和流的窗口join，一个窗口内的两个表join
• 流和表join，表用CDC更新到一个分布式存储上，每个流事件进来后查询分布式存储，join在一起后得到结果。
• 表和表join，物化视图维护，任意一个流的事件都可能导致最终表的行添加或者删除，这是最复杂的方法，也是目前维护大规模物化视图的方法。

注意，窗口是流处理中一个重要的工具，它可以看成，将指定窗口内的数据放在一起，然后对其进行join以后，得到的结果就是最终结果。窗口提供了将流看成是特定时间段内的小表的工具。

12 数据系统的未来

将在线系统看成是流处理，然后使用流处理的Exactly-Once语义，在流处理的最终结果才进行副作用（发送邮件和通知，对外部系统触发命令）的方法。这种方法避免了当前在线系统过度依赖于OLTP的ACID事务的要求，同时大大提高了吞吐量，不过不足在于，全系统是异步的，用户的命令并不能马上就能进行同步更新。想法很好，但实际用户体验可能较差，值得思考。

13 应用的分布式事务

参考资料：

• Seata官网
• 分布式事务解决方案之TCC
• tidb多进程下的分布式事务
• Seata的TCC
• @GlobalLock注解使用场景及源码分析
• Seata AT模式的全局锁GlobalLock

我们将要集中解决应用级的分布式事务问题，在微服务或者SOA场景中，每个微服务都有自己的业务数据库，这些业务数据库可能是同构的数据库，也可能是异构的数据库。如何保证一个跨越多个微服务的请求满足事务性的要求？

• TC (Transaction Coordinator) - 事务协调者，维护全局和分支事务的状态，驱动全局事务提交或回滚。也就是Seata服务器
• TM (Transaction Manager) - 事务管理器，定义全局事务的范围：开始全局事务、提交或回滚全局事务。微服务中首次创建全局事务的应用。
• RM (Resource Manager) - 资源管理器，管理分支事务处理的资源，与TC交谈以注册分支事务和报告分支事务的状态，并驱动分支事务提交或回滚。各个微服务下自己的数据库。

13.1 XA

XA事务是从2PC事务衍生出来的应用层分布式事务协议，它只需要要求数据库实现XA事务就可以了。常见的数据库都支持XA协议，例如是postgresql, mysql ,oracble, sql server, ocean base。注意，tidb并不支持标准的XA事务。

XA事务就是对2PC的统一封装以后，没什么难度的。在全局事务开始前，TM对TC获取全局事务号。在全局事务提交的时候，TM对TC发出提交请求，然后TC对各个的RM执行prepare的询问，然后仲裁并落地结果以后，对各个RM进行commit/cancel操作。在全局事务的过程中，全局事务号在多个微服务进行透传，并在执行Sql的时候，将每个微服务自身数据库RM都注册到TC中。因此在最终提交的时候，TC能透明地清楚有多少个RM需要prepare，而由于跨数据库的统一XA接口，TC能简单地跨越多个数据库进行统一的prepare/commit/rollback操作。

XA事务的特点和2PC事务是完全一致的，应用层透明，但是并发量低（加锁时间长）

13.2 TCC

XA事务的问题在于：

• 加锁的时间太长，延迟太大
• 并不是所有数据库都支持，如果遇到非ACID数据库就无法使用XA事务，例如是redis, kafka等等

TCC事务是将XA事务上移到应用层来实现，是一个侵入性较大的实现。

分支事务提交的情况

分支事务失败的情况

13.2.1 异常情况与难点

TCC实现的难点在于：

• 需要开发者考虑好，try, confirm 与cancel三个阶段的具体动作。try的动作是冻结，confirm的动作是确认执行，cancel的动作是取消冻结。
• try，confirm与cancel，由于网络原因，可能产生丢包，重传，乱排序的情况，开发者需要自行处理这些异常情况

异常情况，空回滚

• 问题：在没有调用TCC资源Try方法的情况下，调用来二阶段的Cancel方法，Cancel方法需要识别出这是一个空回滚，然后直接返回成功。
• 原因：出现原因是当一个分支事务所在服务宕机或网络异常，分支事务调用记录为失败，这个时候其实是没有执行Try阶段，当故障恢复后，分布式事务进行回滚则会调用二阶段的Cancel方法，从而形成空回滚。
• 解决：解决思路是关键就是要识别出这个空回滚。思路很简单就是需要知道一阶段是否执行，如果执行来，那就是正常回滚；如果没执行，那就是空回滚。前面已经说过TM在发起全局事务时生成全局事务记录，全局事务ID贯穿整个分布式事务调用链条。再额外增加一张分支事务记录表，其中有全局事务ID和分支事务ID，第一阶段Try方法里会插入一条记录，表示一阶段执行来。Cancel接口里读取该记录，如果该记录存在，则正常回滚；如果该记录不存在，则是空回滚。

异常情况，幂等

• 问题：通过前面介绍已经了解到，为了保证TCC二阶段提交重试机制不会引发数据不一致，要求TCC的二阶段Try、Confirm和Cancel接口保证幂等，这样不会重复使用或者释放资源。如果幂等控制没有做好，很有可能导致数据不一致等严重问题。
• 解决：解决思路在上述 “分支事务记录”中增加执行状态，每次执行前都查询该状态。

异常情况，悬挂

• 情况：悬挂就是对于一个分布式事务，其二阶段Cancel接口比Try接口先执行。
• 原因：原因是在RPC调用分支事务try时，先注册分支事务，再执行RPC调用，如果此时RPC调用的网络发生拥堵，通常RPC调用是有超时时间的，RPC超时以后，TM就会通知RM回滚该分布式事务，可能回滚完成后，RPC请求才到达参与者真正执行，而一个Try方法预留的业务资源，只有该分布式事务才能使用，该分布式事务第一阶段预留的业务资源就再也没有人能够处理了，对于这种情况，我们就称为悬挂，即业务资源预留后无法继续处理。
• 解决：解决思路是如果二阶段执行完成，那一阶段就不能再继续执行。在执行一阶段事务时判断在该全局事务下，“分支事务记录”表中是否已经有二阶段事务记录，如果有则不执行Try。

13.2.2 场景例子

场景：A转账30元给B，A和B账户在不同的服务。

账号A:

try: 检查余额是否够30元，扣减30元 
confirm: 空
cancel: 增加30元

账号B：

try: 增加30元
confirm: 空
cancel: 减少30元

问题在于：

• 账号A的实现不对，try阶段的包丢失，只有cancel包到达的情况下，账号A会凭空多了30元。（空回滚的情况）
• 账号B的实现不对，账号B首先增加了30元，但是账号A后进行try的时候发现失败，账号B的cancel可能无法完成。因为账号B多出来的30元可能早就被用户提取出来消费了，这个时候就无法执行账号B的cancel。（在没有明确仲裁结果下就进行confirm操作）

账号A:

try: try悬挂，幂等检查，检查余额是否够30元，扣减30元 
confirm: 无
cancel: 空回滚检查，幂等检查，增加30元

账号B：

try: 无
confirm: 幂等检查，增加30元
cancel: 无

以上才是正确做法。在有Seata等TCC框架的支持下，开发者不再需要做幂等，空回滚和try悬挂问题的检查了，框架已经做好这些步骤。

13.2.3 小结

显然，XA事务重得多，每个事务的最终提交都需要等待其他事务的prepare完成。但是，TCC事务加锁的粒度要少得多，可支持的并发量也要更大，延迟中等。

缺点是

• TCC业务侵入性非常大，对开发者的要求也高。
• TCC的数据隔离性是读未提交，因为有可能异步的cancel操作。而XA能实现“读已提交”的隔离性。
• TCC的实现依然需要2PC的隐含规则，Try阶段成功的节点，当收到commit指令的时候，必须执行成功。Try阶段节点冻结的数据，必须要在commit/cancel以后才能释放掉。

13.3 Saga

TCC模式需要由业务方提供，Try/Confirm/Cancel的三个业务方法。Saga模式只需要由业务方提供，Normal（一阶段正向服务）/Compensate（二阶段补偿服务）的方法，它的想法相当直观，就是以顺序链的方式依次执行每个本地事务，如果其中一个失败的话，就反向补偿前面已经成功的业务。

但是，Saga和TCC模式的一个显著区别是，TCC先对所有节点进行Try测试以后，才进行Confirm或者Cancel操作。但是，Saga是逐个节点进行Normal，失败的话再进行反向Compensate操作。这就造成了,Saga可能会出现Compensate失败的问题。例如：

场景：A转账30元给B

• 1. 给账号B增加30元，成功
• 2. 给账号A减少30元，失败。这个时候，刚好有其他事务将账号B完全消费了，这时候账号B余额为0。
• 3. 回滚第一步，给账号B减少30元，失败，因为账号B余额为0，无法扣除30元。

因此，Saga的特点是：

• 实现简单，容易理解，可支持的并发量大，延迟低，吞吐量大
• 业务侵入性大
• 只能实现“读未提交”的隔离性
• 需要手动对长事务排序，Compensate可能失败的节点优先排在流程前面，Compensate不可能失败的节点放在流程后面。（先扣款，后转款）

总体而言，Saga仅用于遗留系统，不建议使用。

13.4 AT

13.4.1 问题与改进

在9.7.2.4中，我们讨论过，XA事务（2PC）都需要遵循：

• Prepare阶段开始上锁，直到收到仲裁者的Commit或者Rollback指令，才能释放锁，中途即使遇到宕机重启等现象都不能释放锁。

这显然是造成XA事务性能较差的地方，因为Prepare阶段无法释放锁，导致加锁的时间过长了，影响性能。而如果Prepare阶段就释放锁的话，就会导致当遇上Rollback的时候，无法正确rollback，造成第一类更新丢失（脏写）的问题。

在2PC的设计中，Prepare之前和之后都是共用一把锁的。我们为什么不换一下思路Prepare阶段之前使用的是数据库的本地锁，Prepare阶段之后使用的是中心的全局锁，并释放数据库的本地锁。因为Prepare阶段所持有的锁其实只是为了避免rollback情况下的脏写问题，而rollback情况在绝大部分的分布式事务下都是很少发生的。当我们使用两把锁，而不是一把锁的时候，我们就能提前释放数据库的本地锁，从而提高事务的吞吐量。但是，使用两把锁的缺点也随之而来，也就是：

• 一旦遇上rollback的情况，我们就会更可能遇上死锁现象，而且rollback所需要的延迟也会更大，
• 数据库默认情况就会降级为“读未提交”的隔离级别，而不是“读已提交”的隔离级别。

这个就是Seata的AT模式的设计思路了。

13.4.2 正常情况

可以完成，正常情况下，AT事务的能prepare阶段提前释放本地所，让其他事务更快读取和写入到这行中。

13.4.3 回滚情况

可以看到，交互执行的tx1/tx2，在遇到回滚场景的情况，只持有一把锁的XA事务没有产生死锁情况，最终tx1回滚，tx2提交。但是AT事务的情况是，出现了死锁情况，死锁的结果是经历一个较长的超时以后，tx2回滚，tx1也回滚，整个事务的延迟也比较长。

13.4.4 工作机制

在理解了AT模式的两把锁的用法以后，我们就能解释AT的工作机制了

执行事务阶段：

• 获取update前的主键ID，在prepare阶段，通过解析update语句，然后构造select语句，来获取update行所对应的主键。
• 通过主键ID获取更新前的镜像，构造SQL语句，通过主键来获取对应的行内容。插入回滚内容，将更新前的镜像，写入同一个数据库的UNDO_LOG表中
• 执行update语句
• 通过主键ID获取更新后的镜像，构造SQL语句，写入到UNDO_LOG表中。

提交的prepare阶段：

• 向TC获取全局锁，全局锁是行锁类型，是记录中TC的一个数据行，以数据库名，表名和主键ID来描述这个锁的。
• 执行本地事务的提交操作，这同时会释放本地锁，并将commit结果上传给TC。

提交的rollback阶段：

• 收到TC的分支回滚请求，包括有XID和BranchID
• 启动本地事务
• 找到对应的UNDO_LOG表，找到该事务的更新前，和更新后，的镜像。
• 校验更新后镜像与当前行是否一致，不一致的证明该行在“全局锁”以外被修改了，无法有效回滚，这就是“第一类更新丢失”的问题。
• 将更新前的镜像生成update语句，将当前行内容update为更新前的镜像。
• 提交本地事务，并释放全局锁

提交的commit阶段：

• 收到TC的分支提交请求，包括有XID和BranchID
• 异步批量删除UNDO_LOG表的内容

可以看到：

• 全局锁是建立在数据库以外的TC机制，与数据库自身的锁机制毫无关系，全局锁是以行主键作为加锁key
• AT模式无法阻止，其他事务以本地事务，非分布式事务的方式来修改prepare阶段以后但没提交的行（因为这类事务无需获取全局锁），这可能会产生第一类更新丢失（脏写）的问题

13.4.5 本地事务的@GlobalLock

默认的本地事务无需获取全局锁就能执行，这就会造成无意中修改了正在等待commit/rollback的全局事务的行。一旦这样做的话，rollback的全局事务就无法正常回滚。

@GlobalLock(lockRetryInternal = 100, lockRetryTimes = 100)
@GetMapping("/GlobalLock")
@Transactional
public Object GlobalLock() {
    AccountTbl accountTbl = accountTblMapper.selectById(11111111);
    AccountTbl accountTbl1 = accountTbl.setMoney(accountTbl.getMoney() - 1);
    accountTblMapper.updateById(accountTbl1);
    return "成功执行！！！";
}

解决方法比较简单，就是直接在本地事务中，加入@GlobalLock的注解，指定该本地事务也需要获取全局锁。和AT的其他方法也是一样，这样可能会导致死锁的现象，所以最好显式指定重试间隔（lockRetryInternal），和重试时间（lockRetryTimes）

13.4.6 显式的读提交隔离

Seata（AT 模式）的默认全局隔离级别是 读未提交（Read Uncommitted） 。

如果应用在特定场景下，必需要求全局的 读已提交 ，目前 Seata 的方式是通过 SELECT FOR UPDATE 语句的代理。

SELECT FOR UPDATE 语句的执行会申请 全局锁 ，如果 全局锁 被其他事务持有，则释放本地锁（回滚 SELECT FOR UPDATE 语句的本地执行）并重试。这个过程中，查询是被 block 住的，直到 全局锁 拿到，即读取的相关数据是 已提交 的，才返回。

出于总体性能上的考虑，Seata 目前的方案并没有对所有 SELECT 语句都进行代理，仅针对 FOR UPDATE 的 SELECT 语句。

13.4.7 AT小结

AT模式的优点：

• 透明实现，无需应用层干预
• 锁粒度更小，比XA吞吐量更大

AT模式的缺点：

• 一旦遇上rollback的情况，我们就会更可能遇上死锁现象，而且rollback所需要的延迟也会更大
• 当本地事务和全局事务有重叠的行，需要小心加上@GlobalLock注解，没有注解的话会造成脏写现象，有注解的话容易造成死锁现象。
• 数据库默认情况就会降级为“读未提交”的隔离级别，而不是“读已提交”的隔离级别。“读已提交”的隔离级别性能损耗大。
• 对SQL语法和数据库有较多限制

AT模式更适合长事务，少并发冲突，对隔离级别缺少要求的场景。

13.5 小结

分布式事务很好地体现了“软件工程没有银弹”的这句话，每一个方案都是不同方面（透明易用，性能，死锁，隔离性）折衷的结果，并不存在一个完美的方案。

最后，对比一下不同场景下的分布式事务的性能损耗：

用户服务扣除余额=》订单服务添加一个订单=》库存服务扣除库存。并发总数设置为1W次，并发请求数每次增加10。

在并发请求数超过20 时，会爆发异常，100 并发数下，异常率为18%。尽可能避免分布式事务，XA和AT依然有较大的异常和性能损耗

20 总结

DDIA是神书，它的主要贡献在于，提供了如何将不同的数据存储系统有效地组合起来的方法，同时也描述了不同存储系统在设计上的取舍，和不同的应用场景的区别，十分值得细细一读。

参考资料：

• 从原理到应用，Elasticsearch详解
• 把MySQL中的各种锁及其原理都画出来
• zookeeper系列

• 本文作者： fishedee
• 版权声明： 本博客所有文章均采用 CC BY-NC-SA 3.0 CN 许可协议，转载必须注明出处！

相关文章

• 2020-11-03-《精通PostgreSQL 11》的读书笔记
• 2020-09-01-《PostgresSQL修炼之道》读书笔记
• 2018-06-04-schema数据库管理工具
• 2015-03-15-数据库分类
• 2016-03-18-分布式存储概览