DDIA 第一章节

可靠性：硬件故障、软件故障、人为错误）中仍可正常工作并能达到性能水准（可以说是把鲁棒性和性能结合在一起？）
可扩展性合理的方法应对系统数据、流量、复杂性的增长（熵增的过程）
可维护性不同生命周期不同工种可以高效协作保持现有功能并能增加新的场景

可靠性（Reliability）

故障（fault）和失效(failure) 的区别

故障通常定义为系统的一部分状态偏离其标准，而失效则是系统作为一个整体停止向用户提供服务。故障的概率不可能降到零，因此最好设计容错机制以防因故障而导致失效

硬件故障（底层）

硬盘的平均无故障时间（MTTF mean time to failure）约为10到50年。因此从数学期望上讲，在拥有10000个磁盘的存储集群上，平均每天会有1个磁盘出故障。解决硬件故障的方法通常都是增加单个硬件的冗余度

软件故障（服务、功能设计）

接受特定的错误输入，响应变慢等等软件bug存在时间较长，不容易被发现，通过测试、监控自检可以减少软件故障

人为故障（使用和维护）

设计并构建了软件系统的工程师是人类，维持系统运行的运维也是人类。即使他们怀有最大的善意，人类也是不可靠的。从最开始的设计到最后的培训可以减少此类故障的发生

可扩展性（Scalability）

是用来描述系统应对负载增长能力的术语。

讨论可扩展性意味着考虑诸如“如果系统以特定方式增长，有什么选项可以应对增长？”和“如何增加计算资源来处理额外的负载？”等问题。

而“负载参数”是用来描述当前系统负载的，比如每秒请求数数据库读写比率，缓存命中率等等

e.g. : Twitter发推

场景描述

用户打开自己的主页timeline，显示他关注的人的全部推文（系统总请求300k/s）

如果只是发推（峰值12k次/s）写入，扩展性是没问题的，但主要挑战来自每个用户关注了很多人，也被很多人关注

解决方法

发推时，将新推文插入全局推文数据库集合，用户查看timeline时，查他关注的所有人，查找他们的推文并按照时间顺序合并推送

SELECT tweets.*, users.*
FROM tweets
JOIN users ON tweets.sender_id = users.id
JOIN follows ON follows.followee_id = users.id
WHERE follows.follower_id = current_userCopy

为每一个用户的时间线维持一个缓存（消息队列？）每当一个用户发布推文，查找所有关注他的人，并将推文插入到每个主页时间线缓存里。这样会让读取timeline的开销变小

结果 & 后续优化

发推频率是比查询timeline少了两个数量级的，所以在写入的时候多做一些工作，在读取时做一些少的工作会好一些，因此方法2更优。

不过如果一个用户有3000万人关注，就要写入3000万次，所以还要加入用户粉丝数的分布（或发推频率）进行更复杂的加权来进行优化负载。推特最终选择了两种方法的结合，大多数用户的推文会被写入缓存，读取timeline时查网红的推文库进行时间线合并

性能指标（e.g.：响应时间）

算术平均值
百分位点（中位数）
- 中位数（p50）一半用户时间比这个长一半比这个短
- 高百分位点（p99、p95）关注异常值，也叫尾部延迟

并行n个请求里是存在木桶短板效应的，也是高百分位点指标关注的点

应对负载

如何保持负载增加时，保持良好的性能？

纵向 / 垂直扩展：转向更强大的机器（开源）
横向 / 水平扩展：分散到小机器上（节流）

跨多台机器的无状态服务很简单，但是带状态的数据系统从单节点变为分布式会多出很多复杂度

没有万金油的可扩展架构，应用的问题可能是响应时间、读取量、写入量、存储的数据量、访问模式等等问题，每秒处理10w个大小为1kb的请求和每秒处理3个2gb的请求完全不一样

可维护性（Maintainability）

软件工程告诉我们，维护成本是软件成本占大头的，而高可维护性只能在设计之初考虑好。

可操作性

方便运维团队平稳运行，合理的自动化机制

运行状况监控
追踪问题可溯源可复现
扩展、配置、补丁、迁移自动化工具
规范化的工作流程
容灾压测兜底

简单性

尽可能减少复杂度和理解成本（总体上看还是要靠共识或者约定）

复杂度：模块之间的耦合、依赖关系、不合规的命名、解决问题的Hack扽等

可演化性

方便更改（留出足够的抽象和可扩展能力做适配）

比如测试驱动开发重构敏捷等概念

人生苦短啊

DDIA 第二章节数据模型与查询语言

数据模型也是一种技术选型，对上层软件功能有着重要的影响。

关系模型与文档模型

SQL：数据被处理成关系（SQL中的表），每一个关系是元组（SQL中的行）的无序集合。关系数据库大量用于商务数据处理，典型的数据处理和批处理。

NoSQL的驱动力有：

更好的可扩展性非常大大的数据集很高的吞吐量
灵活的动态的数据模型和特殊的查询
开源 & 免费浪潮

由于大多数程序是面向对象的，所以数据存储在关系表中会和SQL数据模型之间有一层转换层，模型的不连贯是SQL广受批评的原因

e.g. : Linkin简历

first_name和last_name这种信息每个用户只出现一次，适合放在User表的列里，但是对于工作，大多数人的职业生涯不止一份，所以一到一对多的关系，常见的做法通常是再分出一个表来存储。

但是如果用json来做，将职业信息放进数组里就会灵活很多，有着更强的局部性（不用反复查库）从数据结构的角度来看，json是比较适合这种一对多的树结构

而对于多对一的场景，如国家/地区，一般采取的是用一个ID而不是纯字符串来表示，也是数据库“规范化”的思想。

如果重复存储了可以存储在一个地方的值，那么就不是规范化的

如果数据库不支持连接，那么在这种场景下会多查一次来模拟出连接（不过类似于国家/地区这种不变数据，要么在缓存里要么在内存中，开销一般不大）

如果有一个新的功能，“学校”或者“公司”不只是一个字符串，而是一个实体，那么它也有自己的“简历”，那么一对多的关系就会变成多对多的关系。而在多对多的关系上，文档数据库就会疲软（上世纪70年代的层次模型数据库也遇到了相同的难题，而解决这个问题的两个答案分别是关系模型和网络模型）

网络模型

实现并商用的CODASYL模型：

层次模型的树结构里每条记录只有一个父节点，网络模型中可以有多个父节点，这样多对一和多对多的关系建模比较灵活。网络模型中记录之间的链接不是外键，而是类似于指针，访问记录的唯一方法是沿着根记录的链路路径（也叫访问路径）类似遍历链表。

在多对多的关系中，不同路径可以达到相同的路径，查询是通过遍历记录列和跟随访问路径表在数据库中移动游标执行的，如果记录有多个父节点，则应用程序要跟进所有的关系，非常不灵活

关系模型

相比之下，关系型数据库的所有数据都清晰可见，关系表和行的集合，不会有嵌套结构，不会有复杂的访问路径。查询优化器自动决定查询的那个部分以哪个顺序执行以及使用哪些索引，这些选择实际上是”访问路径“，但因为是自动生成的，不需要使用者考虑这些。

关系型数据库的查询优化器是很复杂的，但是只需要构建一次查询优化器，随后使用该数据库的所有程序都可以从中受益。为特定查询添加索引的成本也比重构查询优化器低一些

文档模型

文档模型中，一对多和多对多关系里，相关项目都被一个唯一标识符引用，在关系型数据库里叫外键，在文档模型中交文档引用。

关系和文档相比

~~那我感觉还是我们文档牛皮~~文档数据库因为局部性和灵活性，对某些应用程序更接近于程序使用的数据结构，关系型数据库为连接提供了良好的支持，处理多对一和多对多的关系占据优势

数据查询语言

SQL采取了声明式写法，比命令式隐藏了更多底层细节，适合并行执行，提供有限的功能性，为数据库提供了更多自动优化的空间。

Cypher是属性图的声明式查询语言，为Neo4j图形数据库发明，和CODASYL类似的，查询语句可能存在多个查询路径，但是不需要指定细节，查询优化程序会自动选择预测效率最高的策略

三元组存储和SPARQL

三元组存储模式大体和属性图模式相同，三元组存储中，所有信息以三部分形式存储（主语宾语谓语）三元组的主语相当于一个顶点，宾语是下面两者之一：

另一个顶点，谓语是图中的一条边，主语是其尾部顶点，宾语是其头部顶点
原始类型的值（如字符串或数字），谓语和宾语相当于主语上的key和value

语义网络

网站将信息发布为文字和图片给人类阅读，那么将信息反过来当作所有机器可读的数据，资源描述框架（RDF）目的是将不同网红赞以一致的格式发布数据的机制，将不同网站的数据自动合并成一个数据网络（最终失败惹）

图形和网络相比

CODASYL网络模型和目前的图模型很相似，但也有很大程度的不同

CODASYL里，数据库存在模式，指定那种记录类型可以嵌套在其他记录类型中，图形数据库不存在类似限制
CODASYL里，只能通过访问路径来达到特定记录，图形数据库可以用唯一ID来直接引用任何顶点，也可以用索引查找
CODASYL里，记录的后续是一个有序集合，所以要手动维护排序，图形数据库里顶点和边不是有序的，只有在查询时排序
CODASYL里，所有查询是命令式的，图形数据库可以用用Cypher/SPARQL查询，也支持命令式代码

Datalog

Datalog很古老，主要在上世纪80年代研究，但它为以后的查询语言提供了基础

Datalog的数据模型也类似三元组形式，将三元组写成**谓语(主语，宾语)**的形式

Datalog通过反复执行一小步和递归调用自己的方式来做查询，是用于简单一次性，不适合复杂数据的情况

DDIA 第三章节存储和检索

数据库在最基础的层次上要做两件事情：存取

数据模型和查询语言规定了程序员录入和查询数据库的格式，那么站在数据库的角度，我们要思考如何存储和重新查找

从程序员的角度看，大多数时候我们不用关心数据库内部存储和检索的机理，但是当我们需要做存储选型，为了协调工作负载，也需要大致了解存储引擎在底层做什么。

主要分两类：日志结构的存储引擎和面向页面的存储引擎

驱动数据库的数据结构

两个bash函数就可以写出一个简单的数据库

#!/bin/bash
db_set() {
echo"$1,$2" >> database
}

db_get() {
grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}Copy

按照key value的形式存取每次调用db_set都会在文件末尾追加一条，在更新键时旧版本值不会被覆盖，在查找最新值的时候都是键最后出现的位置（tail -n 1的含义）

db_set在一些简单场景会有比较好的性能，文件尾部追加写入是很高效，和这种做法类似的是，数据库内部使用日志（Log）来作为仅追加数据文件

但是相对应的，一旦数据比较多db_get的性能就会很糟糕，每次查找它都要从头查到尾寻找键，如果数据量翻一番，查找时间也要翻一倍

为了提升查找效率，我们有了新的数据结构：索引，索引保存一些额外的元数据作为路标，帮助查找想要的数据。索引是附加的数据结构，不会影响数据本身，只影响查询的性能。维护额外的结构会产生开销，写入时索引会拖慢速度。

存储系统的重要权衡：索引，每建立一个索引就会拖慢写入速度，需要程序员或DBA对应用的查询模式选择合适的索引

哈希索引

key value的索引是常见的索引形式，hash map实现散列表映射。将键映射到内存数据文件中的字节偏移量，指明了对应值的位置。写入文件同时要更新散列映射。查找时通过查找映射中的偏移量再读内存里该位置的值

Riak默认的存储引擎Bitcask就是这样做的，将所有键保存在可用内存中，值保存在磁盘或者cache中这样非常适合每个键的值经常更新的场景。

如何避免追加写入一个文件最后用完磁盘空间？一个方法是将日志分为特定大小的段，当日志增长到特定尺寸就关闭当前段文件，开始写入一个新的段文件，然后对这些段进行压缩，只保留每个键的最近更新。多个段合并后，旧的段文件可以删除。

每个段有自己的内存散列表，找一个键的值可以先查最近的段，再找第二近的段，以此类推

主要问题

文件格式

CSV不一定最适合，二进制更快一些，需要重新编码

删除记录

删除一个键和相关值必须要附加一个特殊的删除记录，在合并时删除键之前的所有值

崩溃恢复

数据库重启则内存散列映射将会丢失，可以通过保存快照来进行加速恢复

并发控制

写操作是以严格顺序附加到日志的，实现方案基本为只有一个写入器线程，读取器线程可以有很多个，存在脏读

采取追加日志而不是更新文件用新值覆盖旧值是有原因的

追加和分段合并是顺序写入操作，比随机写入快
段文件是附加或不可变的可以方便并发和崩溃恢复
合并旧段可以避免数据文件分散问题

哈希表存储的局限性：

散列表必须放进内存
范围查询效率低

SSTables 和 LSM树

SSTables

如果对键值对进行按键的序列写入，叫做SSTable（Sorted String Table）且规定每个键在每个合并的段文件里只出现一次

和散列索引日志段相比，似乎破坏了顺序写入的能力，但是合并段可以保证合并段的不重复和保证最新，且不需要保留索引，按照排序特性来查找。节省磁盘空间和IO带宽

在磁盘上维护有序结构是有可能的（B树）但在内存里比较简单，红黑树和AVL树都可以按任何顺序插入键并按顺序读取。

新的引擎这样工作：

写入时添加到内存里的平衡树结构，如红黑树（内存表）
内存表大于某个阈值。将其作为SSTable写进磁盘，写入磁盘时，写入可以开一个新的内存表
遇到读取请求，首先在内存表里查找key，然后在最近的磁盘段里，再在更旧的磁盘段里找
后台运行和压缩覆盖/删除旧值

问题：

数据库崩溃则最近一次写入（内存）未保存在磁盘而丢失，所以可以在磁盘冗余一份日志，便于恢复

用SSTables 制作 LSM树

LevelDB RocksDB使用的关键值存储数据库的算法在日志结构合并树（或LSM树）的基础上的日志结构文件系统，基于这种合并和压缩排序文件原理的存储引擎叫做LSM存储引擎

性能上的优化主要SSTables在压缩合并上的顺序和时间，方案有大小分层压实等等，LSM树的理念：保存一系列在后台合并的SSTables是简单有效的，按顺序存储可以保证高效执行范围查询，磁盘写入是连续的，所以也支持很高的吞吐量

B树

使用最广泛的索引结构是B树，几乎存在于所有关系型数据库和一些NoSQL中

B树同样保持按键值排序，允许搞笑键值查找和范围查询，但是很多地方也和SSTables有不同

B树将数据库分解为固定大小的块和页面（更接近底层硬件）每个页面使用地址标识写入是符合直觉的，但是更新要分空间能否容纳新键，不能还要更新父页面来解释新分区（为了B树平衡）

B树底层是用新数据覆盖旧数据，而不是附加到文件，因此在硬件上SSD反复擦除写入，磁盘也要等待磁头移动。为了保证写入时放崩溃。还要冗余一个预写日志，方便崩溃后恢复

B树和LSM树相比

经验表明，LSM树的写入速度更快，B树读取速度更快

其他索引结构

关键值索引里，每个key都是主键，二级索引的出现可以帮助执行级联操作

将值存储在索引中

行被存储的地方是堆文件（没有特定顺序）新值不大于旧值就可以直接覆盖，大于则需要重新开一个空间并更新指向新堆位置的记录

聚集索引（clustered index）在索引中存储所有行数据

非聚集索引（nonclustered index）仅在索引中存储对数据的引用

二者之间的折衷叫做包含列的索引（index with included columns）或覆盖索引（covering index）其存储表的一部分在索引里，这允许单独使用索引来做查询

和任何类型的冗余一样，聚集索引和覆盖索引可以加快读取速度，但需要额外的存储空间和存储开销和事务保证

多列索引

key - value是一对一关系，如果同时查询一个表里的多个列是不够的

常见的多列索引叫做连接索引（concatenated index）将一列的值追加到另一列后面（将多个字段合并为一个键）

多维索引是查询多列的更一般方法，比如查询地图上特定范围的商店，需要经度纬度的信息进行二维查询，B树或LSM树索引对这种查询的支持并不好

内存存储

RAM的成本降低让一些小数据集保存在内存中是可行的，可以分布在多个机器上，导致内存数据库的发展

内存数据库重启时从磁盘重新加载，但读写仍在内存中进行，磁盘作为耐久性附加日志，使用日志结构，也让内存数据库具有持久性方法

内存数据库的性能优势不在于需要从磁盘读写，而是省去了内存数据结构编码为磁盘数据结构的开销。

“反缓存”方法将内存不足的情况下将最少使用的内存转移到磁盘，并在再次访问中重新加载到内存和OS虚存概念类似，不过有更小的粒度，不是整个内存页，如果硬件NVM（非易失性存储器）技术更广泛使用，没准儿会有新的存储引擎设计捏

事务处理 OR 在线分析

早期事务处理主要在商业交易，一组逻辑单元的读写，事务处理意味着低延迟读取写入，不是批量处理

现在的数据库基本访问模式依旧类似处理业务事务，但通常查找少量记录，并伴随较多更新，这样的应用是交互式的，这种模式叫做在线事务处理（OLTP）

但是当数据库用于数据分析，又有新的访问模式，不需要原始数据，而是将处理后的信息返回，这样的模式叫做在线分析处理（OLAP）

属性	事务处理 OLTP	分析系统 OLAP
主要读取模式	查询少量记录，按键读取	在大批量记录上聚合
主要写入模式	随机访问，写入要求低延时	批量导入（ETL），事件流
主要用户	终端用户，通过Web应用	内部数据分析师，决策支持
处理的数据	数据的最新状态（当前时间点）	随时间推移的历史事件
数据集尺寸	GB ~ TB	TB ~ PB

随着两种模式的日趋分歧，OLTP系统不再作为分析，转去在单独的数据库分析，这类数据库叫做数据仓库

数据仓库

OLTP系统对业务运作比较重要，要求低延迟高可用，执行分析操作会开销巨大，扫描大部分数据集会损害同时执行的事务性能

数据仓库作为独立的数据库，可以分析而不影响OLTP操作，数据仓库一般是所有只读数据副本，转换成适合分析的模式，清理并加载到数据库里。抽取-转换-加载

虽然看起来OLTP和数据仓库都是关系型的（大部分）SQL也基本是支持分析查询的，但是查询模式的不同还是带来了分化

星型模式和雪花型模式

表关系可视化时，事实表（几百列）在中间，被纬度表（可以很宽）包围

如果将尺寸分解，每一行都可以作为外键引用会更加规范化。

列存储

事实表中包含数PB的数据，高效存储和检索就会有问题。数据仓库里并不需要SELECT *，而是读取三四个列，因此列存储会比较有效率

为了降低磁盘IO 列压缩也是一个像样的技术

当需要大规模顺序扫描时，索引显得不是那么重要，紧凑的编码数据却更重要了

OLTP存储引擎学派

日志结构学派

只允许附加到文件和删除过时的文件，不更新已写入的文件。Bitcask SSTables LSM树 HBase都属于这个类别

就地更新学派

将磁盘视为一组可以反复读写的固定大小页面，B树贯彻了这种哲学，也用在大多数关系数据库和NoSQL中

DDIA 第四章节编码与演化

应用程序将会随着时间的变化而变化，而功能的修改也意味着存储的数据可能有更改

数据格式或模式发生变化时，代码或许也要更改。而新旧版本的代码，新旧数据格式可能要在同一个系统中共处，如果想要让系统顺利运行，就要保持双向兼容性：

向后兼容（Backward Compatibility）新代码可以读取旧数据
向前兼容（Forward Compatibility）旧代码可以读取新数据

编码数据的格式

程序中一般有两种数据格式：

内存中，数据保存在对象结构体列表数组哈希表树等结构中，支持CPU高效访问，对操作进行了优化
如果要将数据写入文件或通过网络发送要进行编码（如JSON）

进行这两种之间的翻译，将内存中表示专为字节序列的转换叫做编码（encoding）序列化（serialization）或编组（marshalling）反过来叫做解码解析反序列化反编组

现有的许多编程语言都自建内存对象编码为字节序列的支持，比如Java的java.io.Serializable等等，但是也有一定问题：

编码与语言绑定，其他语言难以读取
解码过程通常需要实例化任意类的能力，会有安全问题
前后向兼容能力较差，效率较低

JSON XML和二进制变体

JSON XML是可以被许多编程语言编写和读取的标准化编码，XML通常被诟病为冗长复杂，JSON由于Web浏览器内置支持而受到欢迎，CSV也与语言无关，但功能较弱

JSON XML CSV都是文本格式，具有人类可读性，但是除了语法问题还有很多小问题：

数字编码有歧义，XML和CSV不区分数字和字符串，JSON区分但不区分整数和浮点数
处理大量数据时，使用浮点数语言进行分析时，基于IEEE 754双精度浮点数会有数字不准确的问题
JSON XML对Unicode支持较好，但不支持二进制数据

作为数据交换格式，JSON XML和CSV比较受欢迎，但是不同组织达成一致的难度很大

二进制编码

简单的小规模数据JSON XML存储成本和交换成本不大，解析压力较小，但是一旦达到TB级别，与二进制相比还是差很多，这导致大量二进制编码版本JSON和XML的出现 JSON有（BSON UBJSON MessagePack Smile等等）他们各自在自己的领域被采用，但没有被广泛使用

Thrift 与 Protocol Buffers

Thrift和Protocol Buffers基于相同原理的二进制编码库且开源，Thrift以接口定义语言（IDL）来描述模式，以模式定义生成各种编程语言实现模式的类

struct person {
1: required string userName,
2: optional i64 favoriteNumber,
3: optional list<string> interest
}Copy

每个字段被标记为必须和可选，但是对如何编码没有影响，如果没有设置该字段会检查出错

字段标签和模式演变

模式是不可避免的随着改变，那么Thrift和Protocol Buffers如何处理模式更改，保证向后兼容呢？

从示例来看，每个字段是由标签号码123标识，并用数据类型约束，没有设置字段值就会从编码记录里省略。添加新的字段值需要标一个新的号码，旧代码读取新数据中包含新的字段，不识别直接省略，保证向前兼容

向后兼容里，只要每个字段的号码标签不变，那么新代码可以读取旧数据，仍然有相同含义。只是不能将新字段设置为必须，或者必须有默认值

删除一个字段只能删除可选，而且不能再用相同号码

数据类型和模式演变

如何改变字段的数据类型？i32 => i64可以保证向后兼容，但是向前兼容里可能有问题

Protocol buf有一个细节是没有列表或数组数据类型，而是有个字段可以从单值变为多值。

Thrift有专用的列表数据类型进行参数化

Avro

Avro是另一种二进制编码格式，适用于Hadoop

record Person {
string userName;
union { null, long } favoriteNumber = null;
array<string> interests;
}Copy

Acro区分作者模式和读者模式，模式解析通过字段名匹配字段，如果出现了作者模式里但读者模式里没有则忽略，反之则转而用读者模式里的声明默认值填充。

为了保持兼容性只能添加或删除有默认值的字段，没有optional和required标记

Avro的优点在于动态生成，模式发生变化时也可以生成新的Avro，由于字段是通过名字来标识的，所以新的模式还可以兼容旧的读者模式。Thrift和Protocol Buf需要手动分配字段标记。

代码生成的动态类型语言

Thrift和Protobuf依赖于代码生成，定义模式之后可以选择编程语言实现此模式的代码，在一些静态类型语言里很有用，Java C++ C#等，可以进行类型检查和自动完成。动态类型编程语言里没有编译时类型检查。所以代码生成往往没啥意义。

模式的优点

Protobuf Thrift Acro都适用模式（Schema）来描述二进制格式。由于Protobuf Thrift Acro实现简单，已经广泛支持到很多编程语言。基于二进制的编码有很多优秀的特性

更加紧凑
作为文档单独维护
保证兼容性
静态类型编程语言可以进行类型检查

Schema可以提供较好的灵活性和规范性

数据流的类型

数据在流程中流动的常见方式：

数据库
服务调用（REST / RPC）
异步消息传递

数据库中的数据流

数据库中，对写入数据编码，对读入数据解码，数据库的内容可以理解为向未来的自己发送消息

一般来说几个不同进程访问数据库是存在的，有些进程是新代码，有些是旧代码，所以数据库要保持向前兼容。

在一个大数据集上执行数据库重写是一个昂贵的事情，大多数关系库支持简单的模式更改，比如添加一个默认值为空的新列。

服务中的数据流：REST / RPC

Client Server体系下，如果要用JSON来作为数据传输格式，C、S两端要对API细节达成一致。Server端也可以去访问另一个服务的数据，这种方式叫做微服务架构。微服务架构的设计目标是让服务独立部署和演化使应用程序容易更改和维护

REST是一种基于HTTP的设计哲学，强调简单的数据格式，用URL标识资源，用HTTP来做缓存控制身份验证和内容写上，符合REST设计原则的API叫做RESTful

SOAP是用于制作网络API请求的基于XML的协议，客户端可以使用本地类和方法调用远程服务，在静态类型语言里很有用，但是Web服务描述语言（WSDL）的设计是人类不可读的，所以要依赖IDE和代码生成工具。

RPC

RPC模型试图向远程网络服务发出请求，调用不同编程语言里约定好的函数/方法。RPC看起来比较方便，但是网络请求和本地函数调用有本质不同：

本地调用可预测，成功失败可控制，网络请求是不可预知的：
请求和响应丢失
远程计算机不可用没有结果
响应较慢而超时

都是可能的，但本机只能进行预测或重试请求，完全不知道发生了什么

如果重试失败的请求伴随着不幂等（如POST请求）可能执行多次，所以要在协议里引入除重机制
网络请求可能要比本地函数调用慢很多，延迟也不可预测
RPC框架要规定好编码和数据类型

RPC的当前方向

Thrift和Avro带有RPC支持，gRPC是用Protobuf的RPC实现，Finagle使用Thrift，Rest.li使用JSON over HTTP

新一代RPC框架会对远程请求进行更多处理，比如Finagle和Rest.li使用futures(promise)来封装可能失败的异步操作，也可以简化多个并行请求返回的结果，gRPC支持流，一个调用可以是一系列的请求和响应

二进制编码的自定义RPC协议可以实现比JSON over REST更好的性能，但是RESTful API便于调试，有大量工具和完整的生态系统，REST很适合公共API的主要风格，RPC的重点在于同一组织的服务之间的请求，在同一数据中心内

数据编码和RPC演化

在可演化性上，RPC方案的兼容性从编码方式中继承

Thrift gRPC 和Avro RPC可以根据编码格式的兼容性规则进行演变
SOAP中请求和响应用XML模式指定
RESTful API使用JSON用于响应，添加新字段可以作为兼容性改变

API版本化如何工作，目前还没有一致意见，对RESTful API，常用的方法是在URL或HTTP Accept头里使用版本号

消息传递中的数据流

RPC和数据库之间的异步消息传递系统和RPC类似，消息以低延迟传送到另一个进程，与数据库类似，不通过网络连接发送消息，而是消息代理（消息队列或面向消息的中间件）来临时存储消息

与直接RPC相比，使用消息代理有很多优点：

消费者不可用或过载，可以充当缓冲区，提高系统可用性
它可以自动将消息发送到已崩溃的进程，防止消息丢失
避免生产者知道消费者的IP地址和端口号（在虚拟机或云存储比较有用）
可以一条消息发送给多个消费者
消费者和生产者逻辑分离

和RPC相比，消息传递通信通常是单向的，发送者一般不期望收到消息回复，通常也在一个通道上完成

消息队列

RabbitMQ ActiveMQ HornetQ NATS和Kafka这样的开源实现比较流行

消息代理的使用方式如下：

一个进程将消息发送到指定的队列或主题，代理确保消息传递给一个或多个消费者或者订阅者的队列或主题，在一个主题上有多个生产者和消费者

消息代理通常不会执行任何数据模型，消息只是包含一些元数据的字节序列

DDIA 第五章节复制

分布式数据

将数据库分布在多台机器上，需要考虑

可扩展性
容错性/可用性
延迟

如果只需要扩展至更高载荷，可以考虑垂直扩展，采用更强的机器。这样的方法问题在于成本增长的速度是快于线性增长的，双倍处理器，双倍内存，双倍磁盘空间的成本远远超过原来的两倍。

相比之下，水平扩展会更加普及，每台机器/虚拟机是一个节点，每个节点使用各自处理器内存磁盘，节点之间通过软件层面协调

复制与分区

分布在多个节点上有两种常见方式：

复制

在几个不同节点上保存数据的相同副本，复制提供了冗余

分区

将一个大型数据库拆分成比较小的子集，将不同分区指派给不同切片（Node）

复制

多台机器上保存相同数据副本会有很多原因：

数据与用户在物理上接近（减少延迟） CDN思路
保证可用性，冗余后即使一个打挂了另一个还能继续服务
支持更多请求，提高读取吞吐量

CDN比较简单，因为其中的数据不会随时间频繁改变，复制也就比较简单，复制的困难在于复制的变更，当前流行的解法有三种：

单领导者(Single leader)
多领导者(Multi leader)
无领导者(leaderless)

领导者与追随者

第一个问题：如何保证数据已经全部落库？

最常见的解决方案被称为基于领导者的复制（leader-based replication）（也称主动/被动（active/passive）或主/从（master/slave）复制）它的机制如下：

一个节点被指定为领导者（leader），也称为主库（master|primary）。当客户端要向数据库写入时，它必须将请求发送给领导者，领导者会将新数据写入其本地存储。
其他副本被称为追随者（followers），亦称为只读副本（read replicas），从库（slaves），备库（ sencondaries），热备（hot-standby）。每当领导者将新数据写入本地存储时，它也会将数据变更发送给所有的追随者，称之为复制日志（replication log）记录或变更流（change stream）。每个跟随者从领导者拉取日志，并相应更新其本地数据库副本，方法是按照领导者处理的相同顺序应用所有写入。
当客户想要从数据库中读取数据时，它可以向领导者或追随者查询。但只有领导者才能接受写操作（从客户端的角度来看从库都是只读的）

这种复制模式是大多数关系型数据库的内置功能。在消息队列这种分布式消息代理中也会使用它

同步复制和异步复制

单线程同步复制里，可以保证从库有与主库一致的最新数据副本。如果主库突然失效，数据仍然能在从库上上找到，缺点是从库如果崩溃或网络故障，主库就无法进行写入操作，要等待同步副本后才能可用

这样很不合理，所以有种配置对一个追随者开启同步复制，对其他节点开启异步复制，如果同步从库缓慢，则从异步从库里抽出一个同步，这样的方法叫做半同步：保证至少两个节点上具有最新的数据副本

通常基于领导者的复制都配制成完全异步。缺点在于主库失效，未复制给从库的所有写入都会丢失，那么C端即使请求成功，写入不能保证持久（弱持久性）。优点在于即使从库落后，主库依然可以处理写入，不会被阻塞

设置新从库

简单从一个节点复制到新节点是不够的，数据总在不断变化，而锁定数据库来保证一致也违背了可用性，所以通常做法为：

获取主库的一致性快照
按快照复制到新的从库节点
从库连接到主库，拉取快照后的一系列数据变更（需要快照与主库复制日志的位置精确关系）
从库处理完积压的数据变更，正式成为从库

处理节点宕机

如何基于主库复制实现高可用性？

从库失效：追赶恢复

如果从库因为网络断开与主库的联系，可以快速恢复，通过日志定位到发生故障前到最后事务，并处理积压的数据变更

主库失效：故障切换

主库失效，需要一个从库提升为新主库，需要重新配置来让C端将写操作发送到新主库。

确认主库失效，所以大多数系统只是简单使用超时（Timeout）：节点频繁地相互来回传递消息，并且如果一个节点在一段时间内（例如30秒）没有响应，就认为它挂了
选择一个新的主库可以通过选举完成，或者可以由之前选定的控制器节点来指定新的主库。主库的最佳人选通常是拥有旧主库最新数据副本的从库（最小化数据损失）
重新配置系统以启用新的主库。客户端现在需要将它们的写请求发送给新主库。如果老领导恢复可用，可能仍然认为自己是主库，需要确保它成为一个从库

故障切换会出现很多大麻烦：

异步复制的一个场景：新主库没有收到旧主库宕机前最后的写入操作。老主库重新加入集群，如何写入这段时间的冲突写入？最常见的解决方案是简单丢弃，这很可能打破客户对于数据持久性的期望。
如果数据库需要和其他外部存储相协调，那么丢弃写入内容是极其危险的操作。

eg: 在GitHub 的一场事故中，一个过时的MySQL从库被提升为主库。数据库使用自增ID作为主键，因为新主库的计数器落后于老主库的计数器，所以新主库重新分配了一些已经被老主库分配掉的ID作为主键。这些主键也在Redis中使用，主键重用使得MySQL和Redis中数据产生不一致，最后导致一些私有数据泄漏到错误的用户手中。

两个节点都以为自己是主库的情况。这种情况称为**脑裂(split brain)**，非常危险：如果两个主库都可以接受写操作，却没有冲突解决机制，那么数据就可能丢失或损坏。一些系统采取了安全防范措施：当检测到两个主库节点同时存在时会关闭其中一个节点。但设计粗糙的机制可能最后会导致两个节点都被关闭。
主库被宣告死亡之前的正确超时应该怎么配置？在主库失效的情况下，超时时间越长，意味着恢复时间也越长。但是如果超时设置太短，又可能会出现不必要的故障切换。

复制日志

基于语句的复制

主库记录下每一个请求语句，将每一次INSERT,UPDATE,DELETE都转发到每一个从库。让从库解析并执行该语句，仿佛是从客户端收到的一样

虽然听上去很合理，但有很多问题会搞砸这种复制方式：

任何调用非确定性函数（nondeterministic）的语句，可能会在每个副本上生成不同的值。例如，使用NOW()获取当前日期时间，或使用RAND()获取一个随机数。
如果语句使用了自增列（auto increment），或者依赖于数据库中的现有数据（例如，UPDATE ... WHERE <某些条件>），则必须在每个副本上按照完全相同的顺序执行它们，否则可能会产生不同的效果。当有多个并发执行的事务时，这可能成为一个限制。
有副作用的语句（例如，触发器，存储过程，用户定义的函数）可能会在每个副本上产生不同的副作用，除非副作用是绝对确定的。

传输预写式日志（WAL）

通常写操作是追加到日志里，日志通常是包含了所有数据库写入的仅追加字节序列，可以使用完全相同的日志在另一个节点上构建副本，除了将日志写进磁盘，主库还可以通过网络将其发送给从库。从库使用这个日志时，会建立一个和主库一样数据结构的副本

缺点是日志记录的数据非常底层：WAL包含哪些磁盘块中的哪些字节发生了更改。这使复制与存储引擎紧密耦合。如果数据库将其存储格式从一个版本更改为另一个版本，通常不可能在主库和从库上运行不同版本的数据库软件。

逻辑日志复制（基于行）

如果复制和存储引擎使用不同的日志格式，可以使复制日志从存储引擎内部分离出来。这种复制日志被称为逻辑日志。逻辑日志与存储引擎内部分离，可以更容易地保持向后兼容，从而使领导者和跟随者能够运行不同版本的数据库软件甚至不同的存储引擎。

关系数据库的逻辑日志通常是以行的粒度描述对数据库表的写入的记录序列：

对于插入的行，日志包含所有列的新值。

对于删除的行，日志包含足够的信息来唯一标识已删除的行。通常是主键，但是如果表上没有主键，则需要记录所有列的旧值。

对于更新的行，日志包含足够的信息来唯一标识更新的行，以及所有列的新值（或至少所有已更改的列的新值）。

基于触发器的复制

如果您只想复制数据的一个子集，或者想从一种数据库复制到另一种数据库，或者如果您需要冲突解决逻辑，可能要把复制从底层提高到应用程序层

触发器允许在写入事务时自动执行的自定义应用程序代码。触发器有机会将更改记录到一个单独的表中，使用外部程序读取这个表，再加上任何业务逻辑处理，会后将数据变更复制到另一个系统去

复制延迟问题

在读多写少的场景，理想情况是创建很多从库，将读请求分散到所有从库上去，减少主库的负载。如果异步写库，那么有些访问了旧数据，有些拿到了新数据，这种不一致是一个暂时的状态，但是最终从库必然保持和主库一致（叫做最终一致性）

写入滞后引起的不一致叫做复制延迟问题，针对不同场景问题有不同解法

读己之写

第一个问题是用户写入后从旧副本里读取了数据，我们需要读写一致性（read-after-write consistency），也称为读己之写一致性（read-your-writes consistency）

如何在基于领导者的复制系统中实现读后一致性？有各种可能的技术，这里说一些：

读用户可能已经修改过的内容时，都从主库读；

e.g. 社交网络上的用户个人资料信息通常只能由用户本人编辑，因此一个简单的规则是：从主库读取用户自己的信息，在从库读取其他用户的信息。

可以跟踪上次更新的时间，在上次更新后的一分钟内，从主库读。还可以监控从库的复制延迟，防止任向任何滞后超过一分钟到底从库发出查询。
客户端可以记住最近一次写入的时间戳，系统需要确保从库为该用户提供任何查询时，该时间戳前的变更都已经传播到了本从库中。如果当前从库不够新，则可以从另一个从库读，或者等待从库追赶上来。
如果您的副本分布在多地会增加复杂性。任何需要由领导者提供服务的请求都必须路由到包含主库的数据中心。（网关层来做？）

单调读

用户可能会遇到时光倒流（moving backward in time）：如果用户从不同从库进行多次读取，首先查询了一个新副本，然后查询了一个旧副本，那么之前看到的新数据就消失了，为了避免这种异常，要单调读取。

单调读（Monotonic reads）是这种异常不会发生的保证。这是一个比强一致性（strong consistency）更弱，但比最终一致性（eventually consistency）更强的保证。单调读取意味着如果顺序进行多次读取，不会读到旧数据，只会读到新数据。

简单实现方式是保证在同一个副本读取

一致前缀读

刚才是因为延迟发生了时间倒流的情况，还有一种情况是因果倒转本是A -> B顺序的数据成了 B -> A

这是分布式数据库的一个特殊问题。不同分区的出现，导致全局写入顺序是不存在的，总有一些部分是旧状态，有些是新状态。

一致前缀读（consistent prefix reads）这个保证说：如果一系列写入按某个顺序发生，那么任何人读取这些写入时，也会看见它们以同样的顺序出现。

简单解决方法是确保因果无关写入相同分区，还有专门的因果依赖关系算法来解决这个问题

多主复制

基于领导者的复制有一个主要的缺点：只有一个主库，而所有的写入都必须通过它。如果出于任何原因无法连接到主库，就无法向数据库写入。

如果允许多个节点接受写入，处理写入的每个节点都必须将该数据更改转发给所有其他节点，叫做多领导者配置（也称多主、多活复制），每个领导者同时扮演其他领导者的追随者

适用场景

适用于多个数据中心的情况。它能提供更好的性能，更低的延迟，更良好的容灾机制和可用性。但缺点也很明显，就是两个数据中心写入相同数据的冲突解决问题。多主复制常常还有自增主键、触发器、完整性约束等麻烦，比较危险
应用程序在断网之后仍然需要继续工作

e.g. 考虑手机上的日历应用。无论设备目前是否有互联网连接，你需要能随时查看你的会议（发出读取请求），输入新的会议（发出写入请求）。如果在离线状态下进行任何更改，则设备下次上线时，需要与服务器和其他设备同步。

在这种情况下每个设备都是一个“数据中心”，是一个本地数据库，而它们之间的网络连接是极度不可靠的。

协同编辑，我们通常不会将协作式编辑视为数据库复制问题，但与前面提到的离线编辑用例有许多相似之处。

处理写入冲突

多领导者复制的最大问题是可能发生写冲突，这意味着需要解决冲突。

避免冲突

应用程序可以确保特定记录的所有写入都通过同一个领导者，那么冲突就不会发生。保证用户交互的始终是同一个数据中心，并使用该数据中心的领导者进行读写。可以cover大部分场景，但是如果需要写另外的主库，还是会出现冲突问题。

收敛至一致的状态

数据库必须以一种收敛（convergent）的方式解决冲突，所有副本必须在所有变更复制完成时收敛至一个相同的最终值。

实现冲突合并解决有多种途径：

给每个写入一个唯一的ID（例如，一个时间戳，一个长的随机数，一个UUID或者一个键和值的哈希），挑选最高ID的写入作为胜利者，并丢弃其他写入。如果使用时间戳，这种技术被称为最后写入胜利（LWW, last write wins）。虽然这种方法很流行，但是很容易造成数据丢失
为每个副本分配一个唯一的ID，ID编号更高的写入具有更高的优先级。这种方法也会数据丢失
以某种方式将这些值合并在一起 - 例如，按字母顺序排序，然后连接它们
在保留所有信息的显式数据结构中记录冲突，并编写解决冲突的应用程序代码

自定义冲突解决逻辑

大多数多主复制工具允许使用应用程序代码编写冲突解决逻辑。在写入或读取时执行：

写时执行，只要数据库系统检测到复制更改日志中存在冲突，就会调用冲突处理程序

e.g. Bucardo允许您为此编写一段Perl代码。这个处理程序通常不能提示用户——它在后台进程中运行，并且必须快速执行。

读时执行，当检测到冲突时，所有冲突写入被存储。下一次读取数据时，会将这些多个版本的数据返回给应用程序。应用程序可能会提示用户或自动解决冲突，并将结果写回数据库

冲突解决通常适用于单个行或文档层面，而不是整个事务。因此，如果有一个事务会原子性地进行几次不同的写入，则对于冲突解决而言，每个写入仍需分开单独考虑。

多主复制拓扑

复制拓扑描述写入从一个节点传播到另一个节点的通信路径。

最普遍的拓扑是全部到全部，其中每个领导者将其写入每个其他领导。但是，也会使用更多受限制的拓扑。

默认情况下，MySQL仅支持环形拓扑，其中每个节点接收来自一个节点的写入，并将这些写入（加上自己的任何写入）转发给另一个节点。另一种流行的拓扑结构具有星形的形状。指定的根节点将写入转发给所有其他节点。星型拓扑可以推广到树。

在圆形和星形拓扑中，为了防止无限复制循环，每个节点被赋予一个唯一的标识符

循环和星型拓扑的问题是，如果只有一个节点发生故障，则可能会中断其他节点之间的复制消息流，导致它们无法通信，直到节点修复。

全能拓扑也可能有问题。特别是，一些网络链接可能比其他网络链接更快（例如，由于网络拥塞），结果是一些复制消息可能“超过”其他复制消息。这样又成了一个因果关系问题，要正确排序这些事件，要用到一种称为版本向量（version vectors）的技术

无主复制

一些数据存储系统放弃主库概念，允许任何副本直接接受客户端写入。在无领导者的实现中，客户端直接将写入发送到几个副本里，或者一个协调者（coordinator）节点代表客户端进行写入（但不执行特定写入顺序）

123节点里3出现了故障，只有12成功写入，那么读取到3会发现旧值当成了正确响应，为了解决这个问题，读请求也会并行发送到123三个节点，响应中包含数据的最新值和旧值，通过版本号确定哪一个是正确的

读修复和反熵

在节点重新联机之后，如何赶上它错过的写入？

在Dynamo风格的数据存储中经常使用两种机制：

读修复（Read repair）

当客户端并行读取多个节点时，它可以检测到任何陈旧的响应。像上文说的一样，这种方法适用于频繁阅读的值。

反熵过程（Anti-entropy process）

一些数据存储具有后台进程不断查找副本之间的数据差异，并将任何缺少的数据从一个副本复制到另一个副本。与基于领导者的复制中的复制日志不同，此反熵过程不会以任何特定的顺序复制写入，并且在复制数据之前可能会有显著的延迟。

读写的法定人数

每个成功的写操作意味着在三个副本中至少有两个出现，这意味着至多有一个副本可能是陈旧的。更一般地说，如果有n个副本，每个写入必须由w节点确认才能被认为是成功的，并且我们必须至少为每个读取查询r个节点。（在我们的例子中，$$n = 3，w = 2，r = 2$$）。只要$$w + r> n$$，我们期望在读取时获得最新的值，因为r个读取中至少有一个节点是最新的。遵循这些r值，w值的读写称为法定人数（quorum）的读和写。r和w是有效读写所需的最低票数。

仲裁条件$$w + r> n$$允许系统容忍不可用的节点，如下所示：

如果$$w <n$$，如果节点不可用，我们仍然可以处理写入。
如果$$r <n$$，如果节点不可用，我们仍然可以处理读取。
对于$$n = 3，w = 2，r = 2$$，我们可以容忍一个不可用的节点。
对于$$n = 5，w = 3，r = 3$$，我们可以容忍两个不可用的节点。

通常，读取和写入操作始终并行发送到所有n个副本。参数w和r决定我们等待多少个节点，即在我们认为读或写成功之前，有多少个节点需要报告成功。

如果少于所需的w或r节点可用，则写入或读取将返回错误。

监控陈旧度

从运维的角度来看，监控数据库是否返回最新的结果是很重要的。即使应用可以容忍陈旧的读取，也需要了解复制的健康状况。如果显著落后，有提示和复现途径

在无领导者复制的系统中，没有固定的写入顺序，这使得监控变得更加困难。而且，如果数据库只使用读修复（没有反熵过程），那么对于一个值可能会有多大的限制是没有限制的 - 如果一个值很少被读取，那么由一个陈旧副本返回的值可能是旧值。

松散法定人数与带提示的接力

合理配置的法定人数可以使数据库无需故障切换即可容忍个别节点的故障。也可以容忍个别节点变慢，因为请求不必等待所有n个节点响应——当w或r节点响应时它们可以返回。

对于需要高可用、低延时、且能够容忍偶尔读到陈旧值的应用场景来说，这些特性使无主复制的数据库很有吸引力。

在一个大型的群集中（节点数量明显多于n个），网络中断期间客户端可能连接到某些数据库节点，而不是为了为特定值组成法定人数的节点们。在这种情况下，需要权衡一下：

将错误返回给我们无法达到w或r节点的法定数量的所有请求是否更好？
或者我们是否应该接受写入，然后将它们写入一些可达的节点，但不在n值通常存在的n个节点之间？

后者被认为是一个松散的法定人数（sloppy quorum）：写和读仍然需要w和r成功的响应，但是那些可能包括不在指定的n个“主”节点中的值。比方说，如果你把自己锁在房子外面，你可能会敲开邻居的门，问你是否可以暂时停留在沙发上。

一旦网络中断得到解决，代表另一个节点临时接受的一个节点的任何写入都被发送到适当的“本地”节点。这就是所谓的带提示的接力（hinted handoff）。（一旦你再次找到你的房子的钥匙，你的邻居礼貌地要求你离开沙发回家。）

检测并发写入

Dynamo风格的数据库允许多个客户端同时写入相同的Key，这意味着即使使用严格的法定人数也会发生冲突。这种情况与多领导者复制相似，但在Dynamo样式的数据库中，在读修复或带提示的接力期间也可能会产生冲突。

问题在于，由于可变的网络延迟和部分故障，事件可能在不同的节点以不同的顺序到达。两个客户机A和B同时写入三节点数据存储区中的键X：

节点 1 接收来自 A 的写入，但由于暂时中断，从不接收来自 B 的写入。
节点 2 首先接收来自 A 的写入，然后接收来自 B 的写入。
节点 3 首先接收来自 B 的写入，然后从 A 写入。

如果每个节点只要接收到来自客户端的写入请求就简单地覆盖了某个键的值，那么节点就会永久地不一致，不符合最终一致性

最后写入胜利（丢弃并发写入）

实现最终融合的一种方法是声明每个副本只需要存储最“最近”的值，并允许“更旧”的值被覆盖和抛弃。然后，只要我们有一种明确的方式来确定哪个写是“最近的”，并且每个写入最终都被复制到每个副本，那么复制最终会收敛到相同的值。

因为网络延迟和并发的不确定性，没有自然的写入排序，我们也可以强制任意排序。例如，可以为每个写入附加一个时间戳，挑选最“最近”的最大时间戳，并丢弃具有较早时间戳的任何写入。这种冲突解决算法被称为最后写入胜利（LWW, last write wins），是Cassandra唯一支持的冲突解决方法，也是Riak中的一个可选特征。

LWW实现了最终收敛的目标，但以持久性为代价：如果同一个Key有多个并发写入，即使它们都被报告为客户端成功（因为它们被写入 w 个副本），但只有一个写入将存活，而其他写入将被静默丢弃。此外，LWW甚至可能会删除不是并发的写入。

与LWW一起使用数据库的唯一安全方法是确保一个键只写入一次，然后视为不可变，从而避免对同一个密钥进行并发更新。例如，Cassandra推荐使用的方法是使用UUID作为键，从而为每个写操作提供一个唯一的键。

“此前发生”的关系和并发

如何判断两个操作是否是并发的？

如果操作B了解操作A，或者依赖于A，或者以某种方式构建于操作A之上，则操作A在另一个操作B之前发生。事实上，我们可以简单地说，如果两个操作都不在另一个之前发生，那么两个操作是并发的（即，两个操作都不知道另一个）

只要有两个操作A和B，就有三种可能性：A在B之前发生，或者B在A之前发生，或者A和B并发。

由于分布式系统里的时钟问题，并发不等同于同时

合并同时写入的值

合并兄弟值，本质上是与多领导者复制中的冲突解决相同的问题。一个简单的方法是根据版本号或时间戳（最后写入胜利）选择一个值，但这意味着丢失数据。所以，需要在程序代码里做一些处理。

版本向量

使用单个版本号来捕获操作之间的依赖关系，但是当多个副本并发接受写入时，这是不够的。相反，除了对每个键使用版本号之外，还需要在每个副本中使用版本号。每个副本在处理写入时增加自己的版本号，并且跟踪从其他副本中看到的版本号。这个信息指出了要覆盖哪些值，以及保留哪些值作为兄弟。

所有副本的版本号集合称为版本向量（version vector）。这个想法的一些变体正在使用，但最有趣的可能是在Riak 2.0 中使用的分散版本矢量（dotted version vector）

当读取值时，版本向量会从数据库副本发送到客户端，并且随后写入值时需要将其发送回数据库。（Riak将版本向量编码为一个字符串，它称为因果上下文（causal context））。版本向量允许数据库区分覆盖写入和并发写入。

另外，就像在单个副本的例子中，应用程序可能需要合并兄弟。版本向量结构确保从一个副本读取并随后写回到另一个副本是安全的。这样做可能会创建兄弟，但只要兄弟姐妹合并正确，就不会丢失数据。

DDIA 第六章分区

在不同节点上部署相同副本叫做复制，对于比较大的数据集，要进行分片/分区。分区通常与复制结合使用，使得每个分区的副本存储在多个节点上。

分区目标是将数据和查询负载均匀分布在各个节点上。如果每个节点公平分享数据和负载，那么理论上10个节点应该能够处理10倍的数据量和10倍的单个节点的读写吞吐量。

如果分区是不公平的，一些分区比其他分区有更多的数据或查询，我们称之为偏斜（skew），因为偏斜导致的高负载分区叫做热点（hot spot）

键值数据的分区

避免热点最简单的方法是将记录随机分配给节点以达到平均。但是它有一个缺点：读取一个特定的值时，不知道它在哪个节点上，所以需要并行查询所有节点

按照键的范围来做分区

一种分区方法是按照连续键的范围（比如A-Z）不一定均匀分布，会导致热点

按照键的散列分区

为了避免偏斜和热点，多数分布式数据库采用散列函数确定键的分区（前提是有个好的散列函数）

使用散列分区的缺点在弱范围查询能力

负载倾斜和消除热点

哈希分区可以帮助减少热点，蛋依然会有极端情况下，大量读写操作请求到同一分区的情况

e.g. 在社交媒体网站上，一个拥有数百万追随者的名人用户在做某事时可能会导致大量写入同一个键（键可能是名人的用户ID，或者人们正在评论的动作的ID）

大多数数据系统无法自动补偿这种高度偏斜的负载，所以要在软件层面减少。一个简单的方法是在主键的开始或结尾添加一个随机数。只要一个两位数的十进制随机数就可以将主键分散为100种不同的主键,从而存储在不同的分区中。

分片与次级索引

如果只通过主键访问记录，可以通过该键确定分区，如果涉及次级索引会更加复杂。有两种用次级索引进行数据库分区的方法：基于文档的分区和基于关键词的分区

按文档的二级索引

按文档ID来做分区，其中的字段来作为二级索引，当有新的数据，数据库分区会自动添加到索引条目的ID文档里。

这种方法里每个分区完全独立，维护自己的二级索引（本地索引）要查询特定字段的数据，要将查询发送到所有分区，合并返回的结果，这个方法叫分散/聚集（scatter/gather），可能会使二级索引上的读取查询相当昂贵。而且也可能放大尾部延迟

根据关键词(Term)的二级索引

构建一个覆盖所有分区的全局索引，可以通过关键词本身或者它的散列进行索引分区。根据它本身分区对于范围扫描非常有用。

理想情况下，索引总是最新的，但是实践里全局二级索引的更新通常是异步的

分区再平衡

将数据和请求（统称负载）从一个节点移动到另一个节点的过程叫做再平衡（reblancing）平衡后通常能保证：

平衡后负载平衡的共享
再平衡期间可以接受读写
移动必要数据减少网络和IO负载

平衡策略

反面教材： hash mod N

如果单纯进行哈希散列分布，那么最初10个节点，键存储在6上，11个节点就要移动到3，到了12个节点就要移动到0，重新平衡的成本较高

固定数量分区

一个相当简单的解决方案：创建比节点更多的分区，并为每个节点分配多个分区。如果一个节点被添加到集群中，新节点可以从当前每个节点中窃取一些分区，直到分区再次公平分配。

这样甚至可以解决硬件不匹配问题，但是太大的固定数量分区也有管理开销，太小的分区跟不上数据集增长会继续有扩展性问题

动态分区

按键的范围进行分区的数据库（如HBase和RethinkDB）会动态创建分区。当分区增长到超过配置的大小时（在HBase上，默认值是10GB），会被分成两个分区，每个分区约占一半的数据。与之相反，如果大量数据被删除并且分区缩小到某个阈值以下，则可以将其与相邻分区合并。此过程与B树顶层发生的过程类似。

数据集开始时很小，所有写入操作都必须由单个节点处理，而其他节点则处于空闲状态。为了解决这个问题，HBase和MongoDB允许在一个空的数据库上配置一组初始分区（这被称为预分割（pre-splitting））

按节点比例分区

通过动态分区，分区的数量与数据集的大小成正比，固定数量的分区，每个分区的大小和数据集的大小成正比，这两种情况下分区的数量和节点的数量无关

Cassandra和Ketama使用的第三种方法是使分区数与节点数成正比。也就是每个节点具有固定数量的分区，在这种情况下，每个分区的大小与数据集大小成比例地增长，而节点数量保持不变，但是当增加节点数时，分区将再次变小。

当一个新节点加入集群时，它随机选择固定数量的现有分区进行拆分，然后占有这些拆分分区中每个分区的一半，同时将每个分区的另一半留在原地。

请求路由

现在我们已经将数据集分割到多个机器上运行的多个节点上。但是仍然存在一个问题：当Client想要发出请求时，如何知道要连接哪个节点？需要连接哪个IP地址和端口号？

这个问题可以概括为**服务发现(service discovery)**，它不仅限于数据库。任何可通过网络访问的软件都有这个问题，特别是如果它的目标是高可用性（在多台机器上运行冗余配置）

概括来说，这个问题有几种不同的方案:

允许Client联系任何节点（例如，通过循环策略的负载均衡（Round-Robin Load Balancer））。如果该节点恰巧拥有请求的分区，则它可以直接处理该请求;否则，它将请求转发到适当的节点，接收回复并传递给客户端。
首先将所有来自客户端的请求发送到路由层，它决定了应该处理请求的节点，并相应地转发。此路由层本身不处理任何请求；它仅负责分区的负载均衡。
要求客户端知道分区和节点的分配。在这种情况下，客户端可以直接连接到适当的节点，而不需要任何中介。

以上所有情况中的关键问题是：如何了解分区-节点之间的分配关系变化？

许多分布式数据系统都依赖于一个独立的协调服务进行集群管理或配置管理，如ZooKeeper来跟踪集群元数据，Cassandra和Riak采取不同的方法：他们在节点之间使用流言协议（gossip protocol）来传播群集状态的变化。

DDIA 第七章节事务

在数据系统功能中，出错是很常见的，包括硬件软件网络的故障和并发导致的竞争等情况

为了实现可靠性，必须要考虑所有可能出错的情况，并通过大量测试保证方案可用

事务（transaction）一直是简化这些问题的首选机制。事务是应用程序将多个读写操作组合成一个逻辑单元的一种方式。整个事务要么成功（提交（commit））要么失败（中止（abort），回滚（rollback））

但是事务本身并不是自然的，而是为了简化应用编程模型创建的，所以也并不适用于全部清空。

ACID

事务所提供的安全保证，通常由众所周知的首字母缩略词ACID来描述，ACID代表原子性（Atomicity），一致性（Consistency），隔离性（Isolation）和持久性（Durability）。

实际上不同数据库的ACID实现并不一样，比如围绕着隔离性的含义有许多含糊不清，在细节上有更多未统一。（不符合ACID标准的系统有时被称为BASE，它代表基本可用性（Basically Available），软状态（Soft State）和最终一致性（Eventual consistency））

原子性（Atomicity）

一般来说，原子是指不能分解成更小的东西。

ACID的原子性描述了，如果进行多次写入，但在过程中出现故障的情况。则该事务将被中止，并且数据库必须丢弃或撤消该事务中迄今为止所做的任何写入。

ACID原子性的定义特征是：能够在错误时中止事务，丢弃该事务进行的所有写入变更的能力。或许可中止性（abortability）是更好的术语

一致性（Consistency）

一致性是个很宽泛的概念，在ACID上下文中，一致性是指数据库在应用程序的特定概念中处于“良好状态”。

ACID一致性的概念是，对数据的一组特定陈述必须始终成立。即不变量（invariants）一致性的这种概念取决于应用程序对不变量的观念，应用程序负责正确定义它的事务，并保持一致性。

隔离性（Isolation）

ACID意义上的隔离性意味着，同时执行的事务是相互隔离的，传统的数据库教科书将隔离性形式化为可序列化（Serializability），这意味着每个事务可以假装它是唯一在整个数据库上运行的事务。以此确保事务提交时看上去是按照顺序运行（尽管实际上可能是并发的）。

实践中因为性能问题，可序列化隔离较少，在Oracle中有一个名为“可序列化”的隔离级别，但实际上它实现了一种叫做快照隔离，这是一种比可序列化更弱的保证

持久性（Durability）

持久性是一个承诺，即一旦事务成功完成，即使发生硬件故障或数据库崩溃，写入的任何数据也不会丢失。为了提供持久性保证，数据库必须等到这些写入或复制完成后，才能报告事务成功提交。

单对象和多对象操作

单对象写入

当单个对象发生改变时，原子性和隔离也是适用的。向数据库写入一个 20 KB的 JSON文档：

如果在发送10 KB之后网络连接中断，数据库是否存储了不可解析的10KB JSON？
如果在数据库正在覆盖磁盘上的前一个值的过程中断电，是否最终将新旧值拼接在一起？
如果另一个客户端在写入过程中读取该文档，是否会看到部分更新的值？

这些问题非常让人头大，所以存储引擎一个几乎普遍的目标是：对单节点上的单个对象（例如键值对）上提供原子性和隔离性。原子性可以通过使用日志来实现崩溃恢复，并且可以使用每个对象上的锁来实现隔离

一些更复杂的原子操作，比如自增，需要CAS（Compare and set 比较和设置），当值没有被其他人修改过才允许执行写操作。

这些单对象操作很有用，因为它们可以防止在多个客户端尝试同时写入同一个对象时丢失更新。但它们不是通常意义上的事务。CAS以及其他单一对象操作被称为“轻量级事务”，甚至出于营销目的被称为“ACID”，但是这个术语是误导性的。事务通常被理解为，将多个对象上的多个操作合并为一个执行单元的机制

多对象事务的需求

许多分布式数据存储已经放弃了多对象事务，因为多对象事务很难跨分区实现，而且不符合需要高可用性或高性能的场景

有很多场景需要协调写入多个不同对象：

关系型数据库中的外键
文档型数据库更新多个文档
具有二级索引的数据库里更新索引

这些应用仍然可以在没有事务的情况下实现。然而，没有原子性，错误处理就要复杂得多，缺乏隔离性，就会导致并发问题。

错误处理和终止

ACID数据库基于这样的哲学：如果数据库有违反其原子性，隔离性或持久性的危险，则宁愿完全放弃事务（宁为玉碎，不为瓦全）

但是一些数据库保持乐观的态度，采取“尽力而为”的想法（比如无主复制的数据存储）处理错误的一个常见的方法就是重试

尽管重试一个中止的事务是一个简单而有效的错误处理机制，但它并不完美：

如果事务实际上成功了，但是客户端认为提交失败了，那么重试事务会导致事务被执行两次（类似浏览器刷新和POST请求）解决这个还要一个额外的应用级除重机制。
如果因为负载过大造成错误，重试事务将使问题变得更糟。为了避免这种死循环，可以限制重试次数，使用指数退避算法。
仅在临时性错误后才值得重试。在发生永久性错误后重试是毫无意义的。
如果客户端进程在重试中失效，任何试图写入数据库的数据都将丢失。

弱隔离级别

两个事务不触及相同数据就可以安全并行，如果涉及修改相同数据，就会有并发竞争问题。

并发BUG难以通过测试找到，也比较难推理复现，出于这个原因，数据库提供事务隔离（transaction isolation）来隐藏应用程序开发者的并发问题。

可序列化（serializable）的隔离等级意味着数据库保证事务的效果与连续运行（即一次一个，没有任何并发）是一样的。但是因为性能损失，许多数据库不支持，所以通常用更弱的隔离级别来防止一部分并发问题。

读已提交

最基本的事务隔离级别是读已提交（Read Committed），它提供了两个保证：

从数据库读时，只能看到已提交的数据（没有脏读（dirty reads））。
写入数据库时，只会覆盖已经写入的数据（没有脏写（dirty writes））。

没有脏读

读取到了事务未提交的数据叫做脏读，原因有：

前后数据可能不一致，用户会困惑，应用程序也可能做出错误操作
如果事务需要回滚，就读取了本不存在的数据

没有脏写

当两个事务同时更新相同对象，而先写入的值尚未进行事务提交，后面的写入覆盖一个尚未提交的值叫做脏写。防止脏写通常是延迟第二次写入，直到第一次写入事务提交或中止为止。

通过防止脏写会避免一些并发问题

实现读已提交

读已提交是一个比较流行的隔离级别，也是大多数数据库的默认设置。最常见的情况是，数据库通过使用行锁（row-level lock）来防止脏写

防止脏读的方法一种是使用相同的锁，但是要求读锁的办法在实践中效果并不好。会损失只读事务的响应时间，并且不利于可操作性，所以大多数数据库都会记住旧的已提交值，和由当前持有写入锁的事务设置的新值。事务正在进行时，任何其他读取对象的事务都会拿到旧值。只有当新值提交后，事务才会切换到读取新值

快照隔离和可重复读

如果在事务执行中读取数据，会是旧数据，其实只要等待一段时间再读就会是新数据。有些情况不能容忍这种暂时性的不一致：

备份

备份可能需要数个小时，但数据库依然接受写入，所以备份可能会是一部分旧的一部分新的

分析查询和完整性检查

要扫描大部分的数据库（分析查询）或是执行定期完整性检查，如果这些查询在不同时间点观察数据库的不同部分，则可能会返回毫无意义的结果。

快照隔离（snapshot isolation）是这个问题最常见的解决方案。想法是，每个事务都从数据库的一致快照（consistent snapshot）中读取，也就是说，事务可以看到事务开始时在数据库中提交的所有数据。即使这些数据随后被另一个事务更改，每个事务也只能看到该特定时间点的旧数据。

快照隔离对长时间运行的只读查询（如备份和分析）非常有用

实现快照隔离

与读取提交的隔离类似，快照隔离的实现通常使用写锁来防止脏写，读取不需要任何锁定。

快照隔离的一个关键原则是：读不阻塞写，写不阻塞读。这允许数据库在处理一致性快照上的长时间查询时，可以正常地同时处理写入操作。且两者间没有任何锁定争用。为了实现快照隔离，需要保留一个对象的多个版本，这项技术叫做多版本并发控制（MVCC, multi-version concurrentcy control）。

防止丢失更新

读已提交和快照隔离级别，主要保证了只读事务在并发写入时可以看到什么。两个事务并发写还有其他冲突的发生，比如丢失更新（lost update）问题

如果有两个事务都在做读取-修改-写入，那么前一个的修改可能会更新，这在诸如计数器协同编辑的场景会比较突出

原子写

许多数据库提供了原子更新操作，从而消除了在应用程序代码中执行读取-修改-写入序列的需要。原子操作通常通过在读取对象时，获取其上的排它锁来实现。以便更新完成之前没有其他事务可以读取它。这种技术有时被称为游标稳定性（cursor stability），另一个选择是简单地强制所有的原子操作在单一线程上执行。

显式锁定

防止丢失更新的另一个选择是让应用程序显式地锁定将要更新的对象，然后应用程序可以执行读取-修改-写入序列，如果有其他事务要读取同一个对象则强制等待，直到第一个读取-修改-写入序列完成。

自动检测丢失的更新

原子操作和锁是通过强制读取-修改-写入序列按顺序发生，来防止丢失更新。另一种方法是允许它们并行执行，如果事务管理器检测到丢失更新，则中止事务并强制它们重试其读取-修改-写入序列。

数据库可以结合快照隔离高效地执行此检查。它不需要在程序里引入锁代码就可以达成，更不容易出错

比较并设置（CAS）

只有当前值从上次读取时一直未改变，才允许更新发生。

冲突解决和复制

锁和CAS操作假定有一个最新的数据副本。但是多主或无主复制的数据库通常允许多个写入并发执行，保证不了有一份统一的最新副本，所以基于锁或CAS操作的技术不适用于这种情况。

这种复制数据库中的一种常见方法是允许并发写入创建多个冲突版本的值（也称为兄弟），并使用应用代码或特殊数据结构在事实发生之后解决和合并这些版本。

写入偏差和幻读

写偏差。它既不是脏写，也不是丢失更新，因为是两个事务同时更新两个不同的对象，但是数据库使用快照隔离，两个事务都进行到下一阶段，却有逻辑上的不正常（比如A B同时定会议室）

写偏差是一个比较难的问题，单对象的原子操作不起作用，一些自动检测丢失和快照检测实现也没用

为了确保不会遇到冲突，可能又要可序列化的隔离级别。

导致写入偏差的幻读

所有写偏差都遵循类似模式：

SELECT查找合适的行，检查是否符合要求
按照查询结果来决定代码是否继续
写入，提交事务

但是写偏差的问题在于，一个事务中的写入是会改变另一个事务的搜索查询的结果的，这种情况称为幻读，快照隔离避免了只读查询中幻读，但是读写事务里就会出现写偏差

物化冲突

如果采用锁机制来避免幻读：

在会议室预订的场景中，可以想象创建一个关于时间槽和房间的表。锁定表中与所需房间和时间段对应的行，这个表不是用来存储预定相关信息，而是事实上的一组锁，用来防止同一会议室同一时间范围的预定

物化冲突应被视为最后的手段。在大多数情况下。可序列化（Serializable）的隔离级别是更可取的。

可序列化

读已提交和快照隔离级别会阻止某些竞争条件，但不会阻止另一些。如果遇到写偏差和幻读就会很棘手（从20世纪70年代起就是这样）如果要解决这个问题，大多数回答是使用可序列化（serializable）的隔离级别

可序列化（Serializability）隔离通常被认为是最强的隔离级别。它保证即使事务可以并行执行，最终的结果也是一样的，就好像它们是挨个连续执行一样。因此数据库保证防止所有可能的竞争条件。

目前大多数提供可序列化的数据库都使用了三种技术：

字面意义上地串行顺序执行事务
两相锁定（2PL, two-phase locking）（当前唯一实践）
乐观并发控制技术，例如可序列化的快照隔离（serializable snapshot isolation）

真串行执行

最简单方法就是完全不要并发：在单个线程上按顺序一次只执行一个事务。这似乎是一个明显的主意，但数据库设计人员只是在2007年左右才决定，因为在那个时候，RAM的成本降低了，许多场景现在都可以将完整的活跃数据集保存在内存中。而且大多数OLTP事务通常很短，而且只进行少量的读写操作，但是长时间运行的分析查询是只读的，可以串行执行在快照隔离上

在存储过程中封装事务

几乎所有的OLTP应用程序都避免在事务中等待交互式的用户输入，以此来保持事务的简短。交互式的事务方式中，应用程序和数据库之间的网络通信耗费了大量的时间，吞吐量会非常差。出于这个原因，具有单线程串行事务处理的系统不允许交互式的多语句事务。应用程序必须提前将整个事务代码作为存储过程提交给数据库。

存储过程的优点和缺点

每个数据库厂商都有自己的存储过程语言，陈旧且简陋，没有完善的生态
在数据库中运行的管理困难，调试困难，版本控制和部署起来也更为尴尬，更难测试
数据库通常比应用服务器对性能敏感的多，数据库中一个写得不好的存储过程会造成更大麻烦

存储过程与内存存储使得在单个线程上执行所有事务变得可行。由于不需要等待I/O，且避免了并发控制机制的开销，它们可以在单个线程上实现相当好的吞吐量。

分区

顺序执行使并发控制很简单，但是对于写入吞吐量较高的应用，单线程事务处理器可能成为一个严重的瓶颈。

为了扩展到多个CPU核心和多个节点，可以对数据进行分区，，对于需要访问多个分区的事务，数据库必须在所有分区间协调事务。存储过程需要跨越所有分区锁定执行，以确保整个系统的可串行性。

两阶段锁定（2PL）

大约30年来，在数据库中只有一种广泛使用的序列化算法：两阶段锁定（2PL，two-phase locking）

两阶段锁定类似锁，但要求更强：只要没有写入，就允许多个事务同时读取同一个对象。但对象只要有写入（修改或删除），就需要独占访问（exclusive access）权限：

如果事务A读取了一个对象，并且事务B想要写入该对象，那么B必须等到A提交或中止才能继续。（这确保B不能在A底下意外地改变对象。）
如果事务A写入了一个对象，并且事务B想要读取该对象，则B必须等到A提交或中止才能继续。

在2PL中，写入不仅会阻塞其他写入，也会阻塞读，反之亦然。相对的，快照隔离里读不阻塞写，写也不阻塞读。因为2PL提供了可序列化的性质，它可以防止早先讨论的所有竞争条件，包括丢失更新和写入偏差。

实现两阶段锁

读与写的阻塞是通过为数据库中每个对象添加锁来实现的。锁可以处于共享模式（shared mode）或独占模式（exclusive mode）锁使用如下：

若事务要读取对象，则须先以共享模式获取锁。允许多个事务同时持有共享锁。但如果另一个事务已经在对象上持有排它锁，则这些事务必须等待。
若事务要写入一个对象，它必须首先以独占模式获取该锁。没有其他事务可以同时持有锁，所以如果对象上存在任何锁，该事务必须等待。
如果事务先读取再写入对象，则它可能会将其共享锁升级为独占锁。升级锁的工作与直接获得排他锁相同。
事务获得锁之后，必须继续持有锁直到事务结束（提交或中止）。这就是“两阶段”这个名字的来源：第一阶段（当事务正在执行时）获取锁，第二阶段（在事务结束时）释放所有的锁。

由于锁的使用过多，因此可能会发生死锁情况

两阶段锁的性能

两阶段锁定的巨大缺点，是其性能问题。两阶段锁定下的事务吞吐量与查询响应时间要比弱隔离级别下要差得多。一部分是由于获取和释放所有这些锁的开销，但更重要的是由于并发性的降低

运行2PL的数据库可能具有相当不稳定的延迟，如果在工作负载中存在争用，那么可能高百分位点处的响应会非常的慢，只需要一个缓慢的事务就能把系统的其他部分拖慢甚至迫使系统停机

如果出现频繁死锁导致终止，也意味着极大的浪费

谓词锁

幻读是一个事务改变另一个事务的搜索查询的结果。具有可序列化隔离级别的数据库必须防止幻读。用锁来解决幻读的问题，从概念上讲，我们需要一个谓词锁（predicate lock）类似于共享/排它锁，但不属于特定的对象，它属于所有符合某些搜索条件的对象，如：

SELECT * FROM bookings
WHERE room_id = 123 AND
end_time > '2018-01-01 12:00' AND
start_time < '2018-01-01 13:00';Copy

如果事务A想要读取匹配某些条件的对象，就像在这个SELECT查询中那样，它必须获取查询条件上的共享谓词锁（shared-mode predicate lock）。如果另一个事务B持有任何满足这一查询条件对象的排它锁，那么A必须等到B释放它的锁之后才允许进行查询。
如果事务A想要插入，更新或删除任何对象，则必须首先检查旧值或新值是否与任何现有的谓词锁匹配。如果事务B持有匹配的谓词锁，那么A必须等到B已经提交或中止后才能继续。

如果两阶段锁定包含谓词锁，则数据库将阻止所有形式的写入偏差和其他竞争条件，因此其隔离实现了可串行化。

索引范围锁

不幸的是谓词锁性能不佳：如果活跃事务持有很多锁，检查匹配的锁会非常耗时。因此，大多数使用2PL的数据库实际上实现了索引范围锁（也称为间隙锁（next-key locking）），一个简化的近似版谓词锁

在房间预订数据库中，如果在room_id列上有一个索引，或者在start_time和end_time上有索引：

room_id上有索引：数据库可以简单地将共享锁附加到这个索引项上，指示事务已搜索123号房间用于预订。
使用基于时间的索引来查找现有预订，可以将共享锁附加到该索引中的一系列值，指示事务已经将12:00~13:00时间段标记为用于预定。

如果另一个事务想要插入，更新或删除同一个房间和/或重叠时间段的预订，则它将不得不更新索引的相同部分。在这样做的过程中，它会遇到共享锁，它将被迫等到锁被释放。

索引范围锁并不像谓词锁那样精确，但是由于它们的开销较低，所以是一个很好的折衷。

序列化快照隔离（SSI）

一方面，我们实现了性能不好（2PL）或者扩展性不好（串行执行）的可序列化隔离级别。另一方面，我们有性能良好的弱隔离级别，但容易出现各种竞争条件，序列化的隔离级别和高性能是不可兼得的吗？

一个称为可序列化快照隔离（SSI, serializable snapshot isolation）的算法是非常有前途的。它提供了完整的可序列化隔离级别，但与快照隔离相比只有只有很小的性能损失。

悲观与乐观的并发控制

两阶段锁是一种所谓的悲观并发控制机制（pessimistic）：如果有事情可能出错，最好等到情况安全后再做任何事情。这就像互斥，用于保护多线程编程中的数据结构。串行执行可以称为悲观到了极致：在事务持续期间，每个事务对整个数据库具有排它锁，作为对悲观的补偿，我们让每笔事务执行得非常快，所以只需要短时间持有“锁”。

相比之下，序列化快照隔离是一种乐观（optimistic）的并发控制技术。乐观意味着，如果存在潜在的危险也不阻止事务，而是继续执行事务，希望一切都会好起来。当一个事务想要提交时，数据库检查是否有什么不好的事情发生（即隔离是否被违反）；如果是的话，事务将被中止，并且必须重试。只有可序列化的事务才被允许提交。

乐观并发控制是一个古老的想法，如果存在很多事务试图访问相同的对象，则表现不佳，会导致很大一部分事务被终止，但是如果系统还有足够容量，乐观的并发控制技术往往比悲观的要好。

SSI基于快照隔离，事务中的所有读取都是来自数据库的一致性快照，SSI添加了一种算法来检测写入之间的序列化冲突，并确定要中止哪些事务。

基于过时前提的决策

写偏差的出现：事务基于一个前提（premise）采取行动，之后当事务要提交时，原始数据可能已经改变——前提可能不再成立。

当应用程序进行查询时，数据库需要假设任何对该结果集的变更都可能会使该事务中的写入变得无效。也就是事务中的查询与写入可能存在因果依赖。为了提供可序列化的隔离级别，如果事务在过时的前提下执行操作，数据库必须能检测到这种情况，并中止事务。

数据库如何知道查询结果是否可能已经改变？有两种情况需要考虑：

检测对旧MVCC对象版本的读取（读之前存在未提交的写入）
检测影响先前读取的写入（读之后发生写入）

检测旧MVCC读取

快照隔离通常是通过多版本并发控制实现的，一个事务从MVCC数据库中的一致快照读时，它将忽略取快照时尚未提交的任何其他事务所做的写入。为了防止读取一致性快照时被忽略的写入已经生效，数据库需要跟踪一个事务由于MVCC可见性规则而忽略另一个事务的写入。当事务想要提交时，数据库检查是否有任何被忽略的写入现在已经被提交。如果是这样，事务必须中止。

检测影响之前的读取的写入

第二种情况要考虑的是另一个事务在读取数据之后修改数据，索引范围锁允许数据库锁定与某个搜索查询匹配的所有行的访问权，这个信息只需要保留一段时间：在一个事务完成（提交或中止）之后，所有的并发事务完成之后，数据库就可以忘记它读取的数据了。

当事务写入数据库时，它必须在索引中查找最近曾读取受影响数据的其他事务。这个过程类似于在受影响的键范围上获取写锁，但锁并不会阻塞事务到其他事务完成，而是像一个引线一样只是简单通知其他事务：你们读过的数据可能不是最新的。

可序列化的快照隔离的性能

果数据库详细地跟踪每个事务的活动（细粒度），那么可以准确地确定哪些事务需要中止，但是粒度较细，记录开销会比较大，较粗粒度的跟踪有更好的速度，但可能让更多必要的事务终止。

与两阶段锁定相比，可序列化快照隔离的最大优点是一个事务不需要阻塞等待另一个事务所持有的锁。就像在快照隔离下一样，写不会阻塞读，反之亦然。这种设计原则使得查询延迟更可预测，变量更少。特别是，只读查询可以运行在一致的快照上，而不需要任何锁定，这对于读取繁重的工作负载非常有吸引力。

与串行执行相比，可序列化快照隔离并不局限于单个CPU核的吞吐量，事务也可以在保证可序列化隔离等级的同时读写多个分区中的数据。

中止率显著影响SSI的整体表现。例如，长时间读取和写入数据的事务很可能会发生冲突并中止，因此SSI要求同时读写的事务尽量短（只读长事务可能没问题）。对于慢事务，SSI可能比两阶段锁定或串行执行更不敏感。

DDIA 第八章节分布式系统的麻烦

使用分布式系统与在一台计算机上编写软件有着根本的区别，之前的章节里讨论的各种各样的问题和解决方法依旧不能cover分布式系统的情况。

在单机情况下，硬件软件出现问题，那么结果要么是继续保持功能完好，要么完全失效。但是运行在多台计算机上的分布式软件，系统模型不再是单机理想化模型，部分失效（partial failure）和部分失效的不确定性（nonderterministic）会让分布式系统难以工作

云计算与超级计算机

如何构建大型计算系统：

规模的一端是高性能计算（HPC）领域。具有数千个CPU的超级计算机通常用于计算密集型科学计算任务，如天气预报或分子动力学。
另一个极端是云计算（cloud computing），通常与多租户数据中心，连接IP网络的商品计算机（通常是以太网），弹性/按需资源分配以及计量计费等相关联。
传统企业数据中心位于这两个极端之间。

超级计算机更像是一个单节点计算机，通过让部分失败升级成完全失败来进行处理。但是实现互联网服务的系统上，通常有更高的可用性和低延迟要求。

如果要使分布式系统工作，就必须接受部分故障的可能性，在软件中建立容错机制。我们需要从不可靠的组件构建一个可靠的系统。在分布式系统中，怀疑，悲观和偏执狂是值得的。

不可靠的网络

我关注的分布式系统是无共享的系统，即通过网络连接的一堆机器。网络是这些机器可以通信的唯一途径

以太网中的大多数内部网络都是异步分组网络（asynchronous packet networks），很多事情可能会出错，包括丢包、阻塞、节点宕机、响应丢失等等。处理这些问题的通常方法是超时，在一段时间之后放弃等待，并且认为响应不会到达。

检测故障

许多系统需要自动检测故障节点。如：

负载平衡器需要停止向已宕机的节点转发请求（移出轮询列表（out of rotation））。
在单主复制功能的分布式数据库中，如果主库失效，则需要将从库之一升级为新主库

但是如何判断一个节点是否能够工作也是比较难确定的，所以关于远程节点关闭的快速反馈很有用，但是我们更需要应用程序本身的积极响应。如果出了问题，要假设没有收到任何回应，重试几次，等待超时过期没有响应才能宣布节点已死亡

超时和无穷的延迟

如果超时是检测故障的唯一可靠方法，那么超时应该等待多久？没有答案。

长时间超时意味着长时间等待，直到一个节点被宣告死亡（在这段时间内，用户必须等待，或者看到错误信息）。如果过早宣布节点死亡，将任务交由下一个节点接管，那么很可能执行两次。而如果系统处于高负荷状态，节点没有死亡而是因为过载导致响应缓慢，转移到其他节点的过程会造成级联失效（cascading failure）

很难规定一个最大延迟，因为异步网络具有无限的延迟，或者只是一个瞬间高峰就可以打挂系统

网络拥塞与排队

在公共云和多租户数据中心中，资源被许多客户共享：网络链接和交换机，甚至每个机器的网卡和CPU（在虚拟机上运行时）。由于无法控制或了解其他客户对共享资源的使用情况，如果附近的某个人正在使用大量资源，则网络延迟可能会发生剧烈抖动。更好的做法是系统不是使用配置的常量超时时间，而是连续测量响应时间及其变化（抖动），并根据观察到的响应时间分布自动调整超时时间。

同步网络 vs 异步网络

电话网络中的电路与TCP连接有很大不同：电路是固定数量的预留带宽，在电路建立时没有其他人可以使用。数据中心网络和互联网的以太网和IP用的是是分组交换协议，没有电路的概念，因为要针对突发流量（bursty traffic）进行优化。

已经有一些尝试去建立支持电路交换和分组交换的混合网络，比如ATM InfiniBand有一些相似之处：它在链路层实现了端到端的流量控制，从而减少了在网络中排队，但是可能因链路拥塞而受到延迟。通过仔细使用服务质量（quality of service,）（QoS，数据包的优先级和调度）和准入控制（admission control）（限速发送器），可以仿真分组网络上的电路交换，或提供统计上的有限延迟。

但是，目前在多租户数据中心和公共云或通过互联网进行通信时，此类服务质量尚未启用。必须假设网络拥塞，排队和无限的延迟总是会发生。

不可靠的时钟

在分布式系统中，因为通信不是即时的，确定时间是一个麻烦的问题。每台机器都有自己的时钟，这些设备不是完全准确的，所以每台机器都有自己的时间概念，可能比其他机器稍快或更慢。可以在一定程度上同步时钟：最常用的机制是网络时间协议（NTP），它允许根据一组服务器报告的时间来调整计算机时钟，服务器则从更精确的时间源（如GPS接收机）获取时间。

单调钟和时钟

时钟根据某个日历（也称为挂钟时间（wall-clock time））返回当前日期和时间。时钟通常与NTP同步

单调钟适用于测量持续时间（时间间隔），例如超时或服务的响应时间

单调钟不需要同步，但是时钟需要根据NTP服务器或其他外部时间源来设置才能有用。

依赖同步时钟

时钟的问题在于，虽然它们看起来简单易用，但却具有缺陷：一天可能不会有精确的86,400秒，时钟可能会前后跳跃，一个节点上的时间可能与另一个节点上的时间完全不同。

有一部分问题是，不正确的时钟很容易被视而不见而导致系统无法工作，如果使用需要同步时钟的软件，必须仔细监控所有机器之间的时钟偏移才可以保证系统可用

有序事件的时间戳

如果两个客户端写入分布式数据库，谁先到达？哪一个更近？在多领导复制的数据库里，这个问题尤其明显，这种冲突解决策略被称为最后写入为准（LWW），但是LWW是有问题的，它防止不了写丢失，也无法区分高频写入和并发写入，也可能违背写入先后

如果采取本地时钟来确定“最近”的值可能是不准确的

时钟读数存在置信区间

您可能能够以微秒或甚至纳秒的分辨率读取机器的时钟，这样细致的测量结果不意味着这个值对于这样的精度实际上是准确的。

使用公共互联网上的NTP服务器，最好的准确度可能达到几十毫秒，而且当网络拥塞时，误差可能会超过100毫秒，但是大多数系统不公开这种不确定性。

因此，将时钟读数更像是一段时间范围：例如，一个系统可能以95％的置信度认为当前时间处于本分钟内的第10.3秒和10.5秒之间，

全局快照的同步时钟

在“快照隔离和可重复读取”中，我们讨论了快照隔离，这是数据库中非常有用的功能，需要支持小型快速读写事务和大型长时间运行的只读事务，用于备份或分析）。它允许只读事务看到特定时间点的处于一致状态的数据库，且不会锁定和干扰读写事务。

暂停进程

如果采用单领导复制分布式数据库，只有领导被允许接受写入。一个节点如何知道它仍然是领导者（它并没有被别人宣告为死亡），并且它可以安全地接受写入？

一种选择是领导者从其他节点获得一个租约（lease），类似一个带超时的锁，任一时刻只有一个节点可以持有租约，在此期间自己是领导者，直到租约到期。因此处理循环要check租约。

但是处理中如果依赖于同步时钟，到期时间和本地时间不同步则会有问题出现

如果当前节点被抢占（preempt）正在运行的线程，并在稍后的时间恢复运行，租约如果已经过期，那么就处理了一个危险事务，而线程甚至不会注意到这一点。因为这个问题其实是：如何在单个机器上使多线程代码线程安全。

当在一台机器上编写多线程代码时，我们有相当好的工具来实现线程安全：互斥量，信号量，原子计数器，无锁数据结构，阻塞队列等等。但是这些工具并不能直接转化为分布式系统操作，因为分布式系统没有共享内存，只有通过不可靠网络发送的消息。

分布式系统中的节点，随时可能宣布死亡，可能在程序运行当中，但是其他节点还在继续运转。

响应时间保证

在一些实时系统中，软件必须有一个特定的截止时间（deadline），如果截止时间不满足，可能会导致整个系统的故障。

而提供实时保证的系统要做很多额外的工作，对于大多数服务器端数据处理系统来说，实时保证是不经济或不合适的。比如垃圾收集本是一个“暂停”时进行的，会阻塞很多事情，但是变成“滚动升级”就会好很多

知识、真相与谎言

网络中的一个节点无法确切地知道任何事情——它只能根据它通过网络接收到（或没有接收到）的消息进行猜测。

真理由多数所定义

一个经历了一个长时间停止世界垃圾收集暂停（stop-the-world GC Pause）的节点。节点的所有线程被GC抢占并暂停一分钟，在此期间没有请求被处理和响应，其他节点宣布它已经死亡，而死亡节点在一分钟后活了过来，从它自己的角度来看，几乎没有经过任何时间。

节点不一定能相信自己对于情况的判断。分布式系统不能完全依赖单个节点，因为它随时可能失效。许多分布式算法都依赖于法定人数，即在节点之间进行投票：决策需要来自多个节点的最小投票数，以减少对于某个特定节点的依赖。

最常见的法定人数是超过一半的绝对多数。多数法定人数允许系统继续工作，如果单个节点发生故障（三个节点可以容忍单节点故障；五个节点可以容忍双节点故障）。系统仍然是安全的

领导者与锁定

通常情况下，一些东西在一个系统中只能有一个。例如：

数据库分区的领导者只能有一个节点，以避免脑裂（split brain）
特定资源的锁或对象只允许一个事务/客户端持有，以防同时写入和损坏。
一个特定的用户名只能被一个用户所注册，因为用户名必须唯一标识一个用户。

一个节点可能以前是领导者，但是如果其他节点在此期间宣布它死亡或者被降级，另一个领导者当选，而自己还在执行领导者的全能，如果其他节点相信，系统就会奇怪起来

防护令牌

当使用锁或租约来保护对某些资源的访问时，需要确保一个被误认为自己是“天选者”（分区的负责人，锁的持有者，成功获取用户名的用户的请求处理程序，且没有经过多数法定同意）的节点不能中断系统的其它部分。实现这一目标的一个相当简单的技术就是防护（fencing）

假设每次锁定服务器授予锁或租约时，它还会返回一个防护令牌（fencing token），这个数字在每次授予锁定时都会增加，然后，我们可以要求客户端每次向存储服务发送写入请求时，都必须包含当前的屏蔽令牌。

这种机制要求资源本身在检查令牌方面发挥积极作用，通过拒绝使用旧的令牌，而不是已经被处理的令牌来进行写操作（也就是服务端检查）

拜占庭故障

如果存在节点可能“撒谎”（发送任意错误或损坏的响应）的风险，则分布式系统的问题变得更困难了。拜占庭故障（Byzantine fault），在不信任的环境中达成共识的问题被称为拜占庭将军问题

当一个系统在部分节点发生故障、不遵守协议、甚至恶意攻击、扰乱网络时仍然能继续正确工作，称之为拜占庭容错（Byzantine fault-tolerant）的，。大多数拜占庭式容错算法要求超过三分之二的节点能够正常工作（即，如果有四个节点，最多只能有一个故障）

系统模型与现实

已经有很多算法被设计以解决分布式系统问题，三种系统模型是常用的：

同步模型（synchronous model）假设网络延迟，进程暂停和和时钟误差都是有界限的。这只意味着你知道网络延迟，暂停和时钟漂移将永远不会超过某个固定的上限。同步模型并不是大多数实际系统的现实模型
部分同步模型（partial synchronous）一个系统在大多数情况下像一个同步系统一样运行，但有时候会超出网络延迟，进程暂停和时钟漂移的界限。这是很多系统的现实模型：大多数情况下，网络和进程表现良好，否则我们永远无法完成任何事情，但在任何时刻都有可能偶然被破坏。
异步模型在这个模型中，一个算法不允许对时机做任何假设——事实上它甚至没有时钟（所以它不能使用超时）。一些算法被设计为可用于异步模型，但非常受限。

进一步来说，除了时间问题，我们还要考虑节点失效。三种最常见的节点系统模型是：

崩溃-停止故障

算法可能会假设一个节点只能以一种方式失效，即通过崩溃。这意味着节点可能在任意时刻突然停止响应，此后该节点永远消失——它永远不会回来。

崩溃-恢复故障

节点可能会在任何时候崩溃，但也许会在未知的时间之后再次开始响应。在崩溃-恢复（crash-recovery）模型中，假设节点具有稳定的存储（即，非易失性磁盘存储）且会在崩溃中保留，而内存中的状态会丢失。

拜占庭（任意）故障

节点可以做（绝对意义上的）任何事情，包括试图戏弄和欺骗其他节点

算法的正确性

如果我们正在为一个锁生成屏蔽令牌，我们可能要求算法具有以下属性：

唯一性

没有两个屏蔽令牌请求返回相同的值。

单调序列

如果请求$$x$$返回了令牌$$t_x$$，并且请求$$y$$返回了令牌$$t_y$$，并且$$x$$在$$y$$开始之前已经完成，那么$$t_x <t_y$$。

可用性

请求防护令牌并且不会崩溃的节点，最终会收到响应。

安全性和活性

安全性（safety）和活性（liveness）。在刚刚给出的例子中，唯一性（uniqueness）和单调序列（monotonic sequence）是安全属性，但可用性是活性（liveness）属性。

这两种性质有什么区别？一个是，活性属性通常在定义中通常包括“最终”一词（类似最终一致性）

安全性通常被非正式地定义为，没有坏事发生，而活性通常就类似：最终好事发生

如果安全属性被违反，我们可以指向一个特定的时间点（例如，如果违反了唯一性属性，我们可以确定重复的防护令牌返回的特定操作）。违反安全属性后，违规行为不能撤销——损失已经发生。
活性属性反过来：在某个时间点（例如，一个节点可能发送了一个请求，但还没有收到响应），它可能不成立，但总是希望在未来（即通过接受答复）。

对于分布式算法，在系统模型的所有可能情况下，要求始终保持安全属性是常见的。也就是说，即使所有节点崩溃，或者整个网络出现故障，算法仍然必须确保它不会返回错误的结果（即保证安全性得到满足）

但是，对于活性属性，只有在大多数节点没有崩溃的情况下，只有当网络最终从中断中恢复时，我们才可以说请求需要接收响应。部分同步模型的定义要求系统最终返回到同步状态，然后进行修复。

将系统模型映射到现实世界

在故障恢复模型中的算法通常假设稳定存储器中的数据经历了崩溃。但是，如果磁盘上的数据被破坏，或者由于硬件错误或错误配置导致数据被清除，会发生什么情况？如果服务器存在固件错误并且在重新启动时无法识别其硬盘驱动器，即使驱动器已正确连接到服务器，也会发生什么情况？

算法的理论描述可以简单宣称一些事在假设上是不会发生的——在非拜占庭式系统中。但实际上我们还是需要对可能发生和不可能发生的故障做出假设，真实世界的实现，仍然会包括处理“假设上不可能”情况的代码，即使代码可能就是printf("you sucks")和exit(666)，实际上也就是留给运维来擦屁股。（这可以说是计算机科学和软件工程间的一个差异）。

这并不是说理论上抽象的系统模型是毫无价值的，证明算法正确并不意味着它在真实系统上的实现必然总是正确。但这迈出了很好的第一步，因为理论分析可以发现算法中的问题，这种问题可能会在现实系统中长期潜伏，直到你的假设（例如，时间）因为不寻常的情况被打破。理论分析与经验测试同样重要。

DDIA 第九章节一致性与共识

分布式系统中的许多事情可能会出错。我们需要找到容错的方法让系统里某些内部组件出现故障但服务也能正常运行。

构建容错系统里，我们大量的使用了抽象，让应用依赖这些抽象的实现。比如使用事务，应用可以假装没有崩溃（原子性），没有其他人同时访问数据库（隔离），存储设备是完全可靠的（持久性）

分布式系统最重要的抽象之一就是共识（consensus）：就是让所有的节点对某件事达成一致。

一致性保证

大多数复制的数据库至少提供了最终一致性，一个非常弱的保证，它的更好的名字是收敛（convergence），因为我们预计所有的复本最终会收敛到相同的值。但是最终一致性是一种很弱的一致性保证

线性一致性

最终一致的数据库，如果在同一时刻问两个不同副本相同的问题，可能会得到两个不同的答案。

如果数据库可以提供只有一个副本的假象，那么事情就简单太多了。那么每个客户端都会有相同的数据视图，且不必担心复制滞后了。

这就是线性一致性（linearizability）（也称为原子一致性（atomic consistency），强一致性（strong consistency），立即一致性（immediate consistency）或外部一致性（external consistency ）【8】）

它基本的想法是让一个系统看起来好像只有一个数据副本，而且所有的操作都是原子性的。

在一个线性一致的系统中，只要一个Client成功完成写操作，所有其他Client从数据库中读取数据必须能够看到刚刚写入的值。线性一致性是一个新鲜度保证（recency guarantee）

什么使得系统线性一致？

线性一致性背后的基本思想很简单：使系统看起来好像只有一个数据副本。通过记录所有请求和响应的时序，并检查它们是否可以排列成有效的顺序，测试一个系统的行为是否线性一致性是可能的（尽管在计算上是昂贵的）

依赖线性一致性

线性一致性在什么情况下有用？对于少数领域，线性一致性是系统正确工作的一个重要条件。

锁定和领导选举

一个使用单主复制的系统，为了确保领导真的只有一个，一种选择领导者的方法是使用锁：每个节点在启动时尝试获取锁，成功者成为领导者。不管这个锁是如何实现的，它必须是线性一致的：所有节点必须就哪个节点拥有锁达成一致

约束和唯一性保证

唯一性约束在数据库中很常见：例如，用户名或电子邮件地址必须唯一标识一个用户，而在文件存储服务中，不能有两个具有相同路径和文件名的文件。

实现线性一致的系统

由于线性一致性本质上意味着“表现得好像只有一个数据副本，而且所有的操作都是原子的”，所以最简单的答案就是，真的只用一个数据副本。如果副本的节点失效，数据就会丢失或需要重新启动。使系统容错最常用的方法是使用复制。

单主复制（可能线性一致）
多主复制（线性一致）
无主复制（可能线性一致）
共识算法（线性一致）

CAP定理

任何线性一致的数据库只要在任何不可靠的网络上，无论单复制还是多复制，即使在同一个数据中心内也是如此。问题面临的权衡如下：

如果应用需要线性一致性，且某些副本因为网络问题与其他副本断开连接，那么这些副本掉线时不能处理请求。请求必须等到网络问题解决，或直接返回错误。（无论哪种方式，服务都不可用（unavailable））。
如果应用不需要线性一致性，那么某个副本即使与其他副本断开连接，也可以独立处理请求（例如多主复制）。在这种情况下，应用可以在网络问题前保持可用，但其行为不是线性一致的。

因此不需要线性一致性的应用对网络问题有更强的容错能力。这种见解通常被称为CAP定理

CAP最初是作为一个经验法则提出的，没有准确的定义， CAP定理的正式定义仅限于很狭隘的范围，它只考虑了线性一致性模型和一种故障（网络分区，或活跃但彼此断开的节点）。它没有讨论任何关于网络延迟，死亡节点或其他权衡的事，对于设计系统而言并没有实际价值

线性一致性和网络延迟

虽然线性一致是一个很有用的保证，但实际上，线性一致的系统非常少。现代多核CPU上的内存甚至都不是线性一致的：如果一个CPU核上运行的线程写入某个内存地址，而另一个CPU核上运行的线程不久之后读取相同的地址，并没有保证一定能一定读到第一个线程写入的值（除非使用了内存屏障（memory barrier）或围栏（fence））。

这种行为的原因是每个CPU核都有自己的内存缓存和存储缓冲区。默认情况下，内存访问首先走缓存，副本是异步更新的，所以就失去了线性一致性。

对多核内存一致性模型而言，CAP定理是没有意义的，因为在一台计算机中通信是可靠的，所以牺牲线性一致性的原因是性能，而不是容错。

能找到一个更高效的线性一致存储实现吗？看起来答案是否定的：如果你想要线性一致性，读写请求的响应时间至少与网络延迟的不确定性成正比。在像大多数计算机网络一样具有高度可变延迟的网络中，线性读写的响应时间不可避免地会很高。

更快地线性一致算法不存在，但更弱的一致性模型可以快得多，所以对延迟敏感的系统而言，这类权衡非常重要。

顺序保证

顺序与因果

顺序反复出现有几个原因，其中一个原因是，它有助于保持因果关系（causality）

因果关系对事件施加了一种顺序：因在果之前；如果一个系统服从因果关系所规定的顺序，我们说它是因果一致（causally）的。

因果顺序不是全序的

全序（total order）允许任意两个元素进行比较，所以如果有两个元素，你总是可以说出哪个更大，哪个更小。例如，自然数集是全序的：5和13里，13大于5。

然而数学集合并不完全是全序的，{a, b}比{b, c}更大吗？二者都不是对方的子集。我们说它们是无法比较（incomparable）的，因此数学集合是偏序（partially order）的

全序和偏序之间的差异反映在不同的数据库一致性模型中：

线性一致性

在线性一致的系统中，操作是全序的，对任何两个操作，我们总是能断定哪个先发生

因果性

如果两个操作都没有在彼此之前发生，那么这两个操作是并发的，是无法比较的

根据这个定义，在线性一致的数据存储中是不存在并发操作的：必须有且仅有一条时间线，所有的操作都在这条时间线上，构成一个全序关系。

线性一致性强于因果一致性

那么因果顺序和线性一致性之间的关系是什么？答案是线性一致性隐含着（implies）因果关系：任何线性一致的系统都能正确保持因果性

线性一致性并不是保持因果性的唯一途径，还有其他方法可以保证一个系统是因果一致的，但无需承担线性一致带来的性能折损（尤其是CAP定理不适用的情况）实际上在所有的不会被网络延迟拖慢的一致性模型中，因果一致性是可行的最强的一致性模型。而且在网络故障时仍能保持可用

在许多情况下，看上去需要线性一致性的系统，实际上需要的只是因果一致性

捕获因果关系

为了维持因果性，你需要知道哪个操作发生在哪个其他操作之前（happened before），这是一个偏序。用于确定“哪些操作发生在其他操作之前”的技术，在之前的无领导者数据存储中的因果性里有说为了防止丢失更新，我们需要检测到对同一个键的并发写入。

因果一致性则更进一步：它需要跟踪整个数据库中的因果依赖，可以推广版本向量以解决此类问题

序列号顺序

虽然因果是一个重要的理论概念，但实际上跟踪所有的因果关系是不切实际的。

在许多应用中，客户端在写入内容之前会先读取大量数据，所以弄清因果依赖是有很高成本的。我们可以使用序列号（sequence nunber）或时间戳（timestamp）来排序事件。时间戳不一定来自时钟，可以来自一个逻辑钟

这样的序列号或时间戳是紧凑的（只有几个字节大小），它提供了一个全序关系：每操作都有一个唯一的序列号，而且总是可以比较两个序列号，确定哪一个更大（即哪些操作后发生）。

非因果序列号生成器

如果是多主数据库或无主数据库，操作生成序列号要用其他方法：

每个节点生成自己独立的一组序列号
物理时钟时间戳（要求精准分辨率）
预先分配好序列号区块，节点AB分用

兰伯特时间戳

尽管刚才描述的三个序列号生成器与因果不一致，，但实际上有一个简单的方法来产生与因果关系一致的序列号。它被称为兰伯特时间戳：

每个节点都有一个唯一标识符，和一个保存自己执行操作数量的计数器。兰伯特时间戳就是两者的简单组合：（计数器，节点ID）$$(counter, node ID)$$。两个节点有时可能具有相同的计数器值，但通过在时间戳中包含节点ID，每个时间戳都是唯一的。

它提供了一个全序：如果你有两个时间戳，则计数器值大者是更大的时间戳。如果计数器值相同，则节点ID越大的，时间戳越大。

使兰伯特时间戳因果一致的关键思想如下所示：每个节点和每个客户端跟踪迄今为止所见到的最大计数器值，并在每个请求中包含这个最大计数器值。当一个节点收到最大计数器值大于自身计数器值的请求或响应时，它立即将自己的计数器设置为这个最大值。

全序广播

如果你的程序只运行在单个CPU核上，那么定义一个操作全序是很容易的：可以简单地就是CPU执行这些操作的顺序。在分布式系统里，如果吞吐量超出单个主库的处理能力，这种情况下如何扩展系统；以及，如果主库失效如何处理故障切换。在分布式系统文献中，这个问题被称为全序广播（total order broadcast）或原子广播（atomic broadcast）

全序广播通常被描述为在节点间交换消息的协议。非正式地讲，它要满足两个安全属性：

可靠交付（reliable delivery）

没有消息丢失：如果消息被传递到一个节点，它将被传递到所有节点。

全序交付（totally ordered delivery）

消息以相同的顺序传递给每个节点。

使用全序广播

像ZooKeeper和etcd这样的共识服务实际上实现了全序广播。全序广播正是数据库复制所需的：如果每个消息都代表一次数据库的写入，且每个副本都按相同的顺序处理相同的写入，那么副本间将相互保持一致（除了临时的复制延迟）。这个原理被称为状态机复制（state machine replication）

分布式事务与共识

共识是分布式计算中最重要也是最基本的问题之一。从表面上看似乎很简单：非正式地讲，目标只是让几个节点达成一致（get serveral nodes to agree on something）。

两阶段提交（2PC, two-phase commit）算法，这是解决原子提交问题最常见的办法，并在各种数据库、消息队列和应用服务器中实现。事实证明2PC是一种共识算法，但不是一个非常好的算法

原子提交与二阶段提交（2PC）

事务原子性的目的是在多次写操作中途出错的情况下，提供一种简单的语义。事务的结果要么是成功提交，在这种情况下，事务的所有写入都是持久化的；要么是中止，在这种情况下，事务的所有写入都被回滚（即撤消或丢弃）。

正常情况下，2PC事务以应用在多个数据库节点上读写数据开始。我们称这些数据库节点为参与者（participants）。当应用准备提交时，协调者开始阶段 1 ：它发送一个准备（prepare）请求到每个节点，询问它们是否能够提交。然后协调者会跟踪参与者的响应：

如果所有参与者都回答“是”，表示它们已经准备好提交，那么协调者在阶段 2 发出提交（commit）请求，然后提交真正发生。
如果任意一个参与者回复了“否”，则协调者在阶段2 中向所有节点发送中止（abort）请求。

系统承诺

为了理解它的工作原理，我们必须更详细地分解这个过程：

当应用想要启动一个分布式事务时，它向协调者请求一个事务ID。此事务ID是全局唯一的。
应用在每个参与者上启动单节点事务，并在单节点事务上捎带上这个全局事务ID。所有的读写都是在这些单节点事务中各自完成的。如果在这个阶段出现任何问题（例如，节点崩溃或请求超时），则协调者或任何参与者都可以中止。
当应用准备提交时，协调者向所有参与者发送一个准备请求，并打上全局事务ID的标记。如果任意一个请求失败或超时，则协调者向所有参与者发送针对该事务ID的中止请求。
参与者收到准备请求时，需要确保在任意情况下都的确可以提交事务。这包括将所有事务数据写入磁盘（出现故障，电源故障，或硬盘空间不足都不能是稍后拒绝提交的理由）以及检查是否存在任何冲突或违反约束。通过向协调者回答“是”，节点承诺，只要请求，这个事务一定可以不出差错地提交。换句话说，参与者放弃了中止事务的权利，但没有实际提交。
当协调者收到所有准备请求的答复时，会就提交或中止事务作出明确的决定（只有在所有参与者投赞成票的情况下才会提交）。协调者必须把这个决定写到磁盘上的事务日志中，如果它随后就崩溃，恢复后也能知道自己所做的决定。这被称为提交点（commit point）。
一旦协调者的决定落盘，提交或放弃请求会发送给所有参与者。如果这个请求失败或超时，协调者必须永远保持重试，直到成功为止。没有回头路：如果已经做出决定，不管需要多少次重试它都必须被执行。如果参与者在此期间崩溃，事务将在其恢复后提交——由于参与者投了赞成，因此恢复后它不能拒绝提交。

因此，该协议包含两个关键的“不归路”点，以此区分“两阶段”：当参与者投票“是”时，它承诺它稍后肯定能够提交（尽管协调者可能仍然选择放弃）。一旦协调者做出决定，这一决定是不可撤销的。这些承诺保证了2PC的原子性。

协调者失效

如果协调者在发送准备请求之前失败，参与者可以安全地中止事务。但是，一旦参与者收到了准备请求并投了“是”，就不能再单方面放弃，它必须等待协调者回答事务是否已经提交或中止。如果此时协调者崩溃或网络出现故障，参与者只能等待。参与者的这种事务状态称为存疑（in doubt）的或不确定（uncertain）的。

可以完成2PC的唯一方法是等待协调者恢复，协调者恢复后，通过读取其事务日志来确定所有存疑事务的状态。任何在协调者日志中没有提交记录的事务都会中止。

实践中的分布式事务

分布式事务的名声毁誉参半，尤其是那些通过两阶段提交实现的。一方面，它被视作提供了一个难以实现的重要的安全性保证；另一方面，它们因为导致运维问题，造成性能下降，做出超过能力范围的承诺而饱受批评。

分布式事务的某些实现会带来严重的性能损失 —— 例如据报告称，MySQL中的分布式事务比单节点事务慢10倍以上。两阶段提交所固有的性能成本，大部分是由于崩溃恢复所需的额外强制刷盘（fsync）以及额外的网络往返。

数据库内部的分布式事务

一些分布式数据库（即在其标准配置中使用复制和分区的数据库）支持数据库节点之间的内部事务。例如，VoltDB和MySQL Cluster的NDB存储引擎就有这样的内部事务支持。在这种情况下，所有参与事务的节点都运行相同的数据库软件。

异构分布式事务

在异构（heterogeneous）事务中，参与者是两种或以上不同技术：例如来自不同供应商的两个数据库，甚至是非数据库系统（如消息代理）。跨系统的分布式事务必须确保原子提交，尽管系统可能完全不同。

恰好一次的消息处理

异构的分布式事务处理能够以强大的方式集成不同的系统。例如：消息队列中的一条消息可以被确认为已处理，当且仅当用于处理消息的数据库事务成功提交。这是通过在同一个事务中原子提交消息确认和数据库写入两个操作来实现的，但这是两种不相关的技术

如果消息传递或数据库事务任意一者失败，两者都会中止，因此消息代理可能会在稍后安全地重传消息。因此，通过原子提交消息处理及其副作用，即使在成功之前需要几次重试，也可以确保消息被有效地（effectively）恰好处理一次。中止会抛弃部分完成事务所导致的任何副作用。

然而，只有当所有受事务影响的系统都使用同样的原子提交协议（atomic commit protocl）时，这样的分布式事务才是可能的。XA事务：X/Open XA（扩展架构（eXtended Architecture）的缩写）是跨异构技术实现两阶段提交的标准

容错共识

共识算法可以用来确定这些互不相容（mutually incompatible）的操作中，哪一个才是赢家。共识问题通常形式化如下：一个或多个节点可以提议（propose）某些值，而共识算法决定（decides）采用其中的某个值。了哪个顾客获得了座位。

在这种形式下，共识算法必须满足以下性质：

一致同意（Uniform agreement）

没有两个节点的决定不同。

完整性（Integrity）

没有节点决定两次。

有效性（Validity）

如果一个节点决定了值v，则v由某个节点所提议。

终止（Termination）由所有未崩溃的节点来最终决定值。

前两个是基本属性，有效性保证了没有平凡解决方案（比如始终提议null），如果不关心容错，那么可以设定一个节点为“独裁者”，让该节点做出所有决定，终止属性包含容错的思维，一个共识算法不能简单地永远闲坐着等死，它必须取得进展。即使部分节点出现故障，其他节点也必须达成一项决定。

事实上可以证明，任何共识算法都需要至少占总体多数（majority）的节点正确工作，以确保终止属性

共识算法和全序广播

最著名的容错共识算法是视图戳复制（VSR, viewstamped replication），Paxos ，Raft 以及 Zab 。

大多数这些算法实际上并不直接使用这里描述的形式化模型（提议与决定单个值，一致同意，完整性，有效性和终止属性）。取而代之的是，它们决定了值的顺序（sequence），这使它们成为全序广播算法，全序广播要求将消息按照相同的顺序，恰好传递一次，准确传送到所有节点。如果仔细思考，这相当于进行了几轮共识：

由于一致同意属性，所有节点决定以相同的顺序传递相同的消息。
由于完整性属性，消息不会重复。
由于有效性属性，消息不会被损坏，也不能凭空编造。
由于终止属性，消息不会丢失。

共识的局限性

共识算法对于分布式系统来说是一个巨大的突破：它为其他充满不确定性的系统带来了基础的安全属性（一致同意，完整性和有效性），然而它们还能保持容错

尽管如此，它们并不是在所有地方都用上了，因为好处总是有代价的。

节点在做出决定之前对提议进行投票的过程是一种同步复制。通常数据库会配置为异步复制模式。在这种配置中发生故障切换时，一些已经提交的数据可能会丢失。但是为了获得更好的性能，许多人选择接受这种风险。

共识系统通常依靠超时来检测失效的节点。在网络延迟高度变化的环境中，特别是在地理上散布的系统中，经常发生一个节点由于暂时的网络问题，错误地认为领导者已经失效。虽然这种错误不会损害安全属性，但频繁的领导者选举会导致糟糕的性能表现，也会在领导者问题上花费更多成本

技术

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

【译】使用RAIL模型衡量性能上一篇

迟来的五月下一篇

DDIA学习笔记