读书笔记 | 数据密集型应用系统设计

super1

程序员必读书籍！！！豆瓣评分9.7  好评如潮

读书笔记Xmind分享  读书笔记 | 数据密集型应用系统设计 | 思维导图  口令: vP5C

品质读物"Go"《数据密集型应用系统设计》

关键词汇 : 数据模型 / 数据存储 / 事务 / 分布式

欢迎关注 : 大摩羯先生

第一部分 数据系统基础

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

背景

应用都属于数据密集型，而非计算密集型

核心在于数据量、数据的复杂度及数据的快速多变性

应用构建模块

数据库


持久化数据

MySQL等关系型数据库Hive/Clickhouse等大数据存储

高速缓存


缓存热点数据/操作复杂数据以供加快访问

应用内存一级缓存Redis、Memcache等二级缓存

索引


通过冗余存储、异构数据结构来加快检索

ES倒排索引MySQL索引

流式处理


持续发送消息至另一个进程，处理采用异步方式

基于RMQ可靠消息传递基于Kafka流式数据传递

批处理


定期处理大量的累积数据
认识数据系统


数据库、队列、高速缓存等都可以认为是“数据系统”

设计数据系统或数据服务时，三个棘手问题

可靠性

出现异常时，系统可以继续正常运转

可扩展性

随着数据规模、流量、复杂性增长，能够以合理的方式来匹配

可维护性

现有功能维护&新功能迭代、新老人员交替

第2章 数据模型与查询语言

背景


应用构建是一层一层叠加“数据模型”来构建的
关系模型&文档模型

SQL

数据被组织成关系，即表

每个关系都是元组的无序集合，即行

RDBMS

事务处理

批处理

NoSQL

比关系数据库有更好的拓展性，支持超大数据集或超高写入吞吐量

大多数免费、开源

关系模型不能很好支持一些特定查询

突破关系模式限制性，期望更动态和表达力的数据模型




对象-关系不匹配

开发语言，普遍面向对象编程

关系型数据库需要ORM映射转化

关系模型的灵活性较差，非关系型可以更丰富的表达逻辑关系，如JSON、XML

多对一与多对多关系

维护关系ID而非纯文本字符串

避免批量复制、更新带来的消耗

容易维护

避免带来数据不一致问题

符合数据库规范思想，消除重复




文档模型并不适合表达多对一的关系

一些数据系统不支持联结join这种操作，需要从数据层转移到应用层


优缺点对比


关系数据库


依赖所使用的数据结构，强在联结操作、多对一、多对多关系的简洁表达

高度关联数据


文档数据库


模式灵活性，局部性带来较好性能

无模式

数据结构是隐式的，读取时才解释

一般为xml、json、二进制变体等结构化数据

类似文档结构，即一系列关系数据，适合使用文档数据库，一次完成加载

局限性在于嵌套层次的访问路径，不能直接引用文档中的嵌套项

对于联结支持不足

适合一对多，无关系，不适合多对多关系的数据模型

数据查询语言

声明式

声明式语言只需要指定所需数据模式、结果满足条件、数据转换（排序、分组、聚合），而不需要关心具体实现过程和细节

比命令式API更加简洁和容易使用，隐蔽了内部实现细节

例如数据库系统的查询优化器会决定采取哪些索引和联结，以及用何种顺序来执行查询的各个语句

命令式

命令式语言告诉计算机以特定顺序执行某些操作，可以完全推理整个过程，逐行遍历代码、评估相关条件、更新对应的变量等

MapReduce

既不是声明式查询语言，也不是一个完全命令式的查询API

它介于两者之间，查询逻辑用代码实现，基于许多函数式编程语言中的map

MapReduce是一个相当底层的编程模型，用于计算集群上分布执行

图状数据模型

例子

社交网络

顶点是人，边表示与其他人的关系

WEB图

顶点是网页，边表示与其他页面的HTML链接

公路/铁路网

顶点是交叉路口，边表示他们之间的公路或铁路线

小结

数据模型演进过程

层次模型

像一颗大树，不利于表示多对多关系

关系模型

文档数据库

图数据库

第3章 数据存储与检索

数据库核心：数据结构

索引


优点：加快检索

缺点：增加写入成本，影响性能


种类


聚集索引

索引中直接保存行数据

非聚集索引

存储行数据的引用，需要再到实际存储行数据的索引上检索，回表查询


覆盖索引

检索数据就在索引上存储

多列索引

哈希索引


优点：访问快

缺点：内存占用、哈希冲突的解决、随机IO访问、区间查询效率不高不能高效范围查询


全文搜索、模糊索引

倒排表


Lucene是Elasticsearch和Solr的索引引擎

Key记录词条，Value记录包含该词条的文档ID

布隆过滤器

避免频繁无效操作

SSTables（Sorted String Table） 排序字符串表

要求每个键在每个段文件中只能出现一次

合并后的键是有序的

LSM Tree（Log Structured Merge Tree）

一种分层、有序、面向磁盘的数据结构 其核心思想是充分利用磁盘的顺序写性能要远高于随机写性能这一特性，将批量的随机写转换为一次性的顺序写

参考 https://segmentfault.com/a/1190000040752799

CURD


新增

追加一条新记录

更新

追加一条新记录

删除

追加一条删除记录




B-Tree


将数据库分解成固定大小的块或页，一般为4KB

页是内部读写的最小单元

这种数据结构的设计更接近底层硬件，因为硬盘也是以固定大小的块排列

数据更新策略

预写日志（WAL）+ 覆盖页

重做日志

仅支持追加修改的文件，每个B-Tree修改必须先更新WAL然后再修改树本身的页， 当数据库崩溃后需要恢复时，该日志用于将B+Tree恢复到最近一致的状态

写时复制

修改的页被写入不同的位置，树中页的新版本创建后指向新的位置

这是类似一种快照隔离、可重复读的设计思想

B+Tree

增加页的额外指针来指向同层级左、右兄弟页，不用跳回父一级页


追加日志文件的实现


重要问题

文件格式。更快更简单的方法是使用二进制格式

删除记录。进行删除的特殊标记

崩溃恢复。 先写日志，通过日志来恢复和回放

部分写入问题。 追加日志进行校验和保证完整性

并发控制。 严格的先后顺序追加，一个写线程，多个读线程




追加式设计优点


1.磁盘写入友好。 追加和分段合并主要是顺序写，比随机写入快，特别是在旋转式磁性硬盘上

2.并发、崩溃恢复友好。 不必担心错写问题

3.避免碎片化。 根据规则进行旧分段合并，避免磁盘碎片化，提高利用率




事务处理与分析处理


事务属性

ACID 原子性、一致性、隔离性、持久性


OLTP&OLAP


数据仓库

不影响OLTP业务

一般数仓是OLTP系统的只读副本

数据转换，提取-转换-加载

列式存储

按列进行数据聚合存储

列存储压缩

同一列数据类型一致，便于进行压缩

列存储排序

缩小数据范围

利于进行列压缩

随机性大，不容易真正进行压缩

列存储写入

写入相对困难

LSM-Tree解决方案

位图索引 & 游程编码

Clickhouse，Cassandra，Hbase

聚合


COUNT、SUM、AVG、MIN、MAX

物化视图，其实就是预先查询好，根据业务数据的更新来连锁更新，将计算前置
小结

OLTP面向用户，业务查询、事务请求多，数据量小，对性能要求高

OLAP面向数据决策用户，请求量低，但数据查询量大

OLTP主要存储引擎




① 日志结构流派

只允许追加式更新文件和删除过时的文件，但不会修改已写入的文件

BitCask、SSTables、LSM-Tree、LevelDB、Cassandra、HBase、Lucene

② 原地更新流派

将磁盘视为可覆盖的一组固定大小的页，贴近硬件磁盘结构的设计

B-Tree、InnoDB

第4章 数据编码与演化

数据编码格式

编码数据格式

JSON、XML、protobuf、Thrift、Avro

数据存储、通信场景

Rest、RPC、消息传递

编码&解码、序列化&反序列化

语言的特定格式问题

不同语言之间格式的差异和通信

为了在相同对象类型中恢复数据，解码过程需要能够实例化任意的类，这个过程存在一些安全问题，容易遭到恶意攻击

缺乏数据变更带来的向前、向后兼容问题

效率问题，比如Java内置序列化性能较差、编码臃肿

第三方序列化的问题

数字编码的模糊之处

XML、CSV无法区分数字和由数字组成的字符串

JSON区分字符串和数字，但不区分整数、浮点数，并且不指定精度

JSON、XML对Unicode字符串支持友好

不支持二进制字符串，通过Base64将二进制数据编码为文本来解决这个限制

二进制编码

结构紧凑，效率高，节省空间

可读性差

JSON的二进制编码


MessagePack，二进制编码

Thrift、protobuf

字段标签和模式演化

字段位置、标签记录

数据类型和模式演化

精度丢失风险

Avro

读模式

写模式


延伸阅读《深入理解序列化和反序列化》https://book.douban.com/subject/35303133/

数据流模式

通过数据库

通过服务调用


远程调用的问题

网络请求是不可预测的，远程服务响应慢、网络问题丢失等

超时情况的处理

重试带来的幂等处理

较大对象的传输问题

不同进程语言服务的数据转换问题




RPC的数据编码和演化

Thrift、gRPC和Avro RPC可以根据各自编码格式的兼容性规则进行演化

在SOAP中，请求和响应是用XML模式指定的

Restful API通常使用JSON用于响应


通过消息队列


消息队列比RPC的优点


系统间的缓冲区，如果接收方系统过载或不可用，可以暂时存储，提高系统整体可用性

自动将消息重新发送到之前崩溃的系统，防止消息丢失

发送方不需要知道接收方IP、端口信息等

支持一条消息同时发给多个接收方

发送方、接收方分离，解耦


消息队列比RPC的差异

通信是异步的

不关心响应结果

不强制特定数据格式

消息队列产品 RabbitMQ、ActiveMQ、Kafka

小结

编程语言自身支持的序列化仅限自身语言中使用，无法跨语言使用，且缺乏向前、向后兼容

JSON、XML、CSV等文本格式非常普遍，主要特定数据类型的兼容支持问题

二进制编码格式支持使用清晰定义来进行向前、向后兼容性的变更且可以进行紧凑、高效的编码，但是对阅读不友好

第二部分 分布式数据系统

分布式部署

目的

扩展性

突破单机能力

容错与高可用性

避免单机带来的故障、破坏问题

延迟考虑

就近部署，提高响应效率

第5章 数据复制

数据复制的方式

主从复制


主从复制原理

指定某一个副本为主副本（主节点），当写数据时，写请求由主节点来处理并把新数据写入主节点

其他副本则全部称为从副本（从节点），主副本写入本地存储后将数据更改通过复制的日志或更改流发送给所有从副本，然后从节点严格保持和主节点一样的写入顺序写入到从节点本地

客户端读取数据时可以从主节点、从节点上进行，但是只有主节点接受写请求




数据复制的问题


同步or异步


同步复制

同步复制的优点是，确保副本之间数据一致性

同步复制的缺点是，延时高，如果出现节点故障，写入将阻塞且始终无法成功

半同步

至少有两个节点拥有最新的数据副本（即主节点和一个同步从节点）

全异步复制

主节点一直可以响应写请求，吞吐性好，但是从节点可能远远落后主节点，也可能会有数据不一致、持久性问题

不靠谱较为折中的设计，但是应用也比较广泛


处理失败副本


从节点失效

重启后追赶主节点最新数据

主节点失效


确认主节点失效

一般基于超时机制，节点之间频繁地相互发送心跳存活消息， 如果发现某一个节点在一段时间内没有响应则认为该节点失效

选举新的主节点

通过共识机制来投票选举

候选节点最好与原主节点的数据差异最小，这样可以最小化数据丢失风险

重新配置系统使新主节点生效

请求路由控制

多副本的一致性


增加新的从节点


在某个时间点对主节点的数据副本产生一个一致性快照，这样不会长时间锁定整个数据库

将此快照拷贝到新的从节点

从节点从拷贝来的数据中追赶主节点的最新数据同步

实现


MySQL、SQL Server、Oracle

MongoDB

Kafka、RabbitMQ

复制日志的实现

基于语句的复制

记录每个写请求并将语句作为日志发送给从节点


问题

非确定性函数，如时间函数、随机数函数不同副本可能产生不同结果

副作用的语句，触发器、存储过程、用户自定义函数等，也可能产生不同结果

自增列，所有副本必须按照完全相同顺序执行，否则会产生不同结果

如果存在多个并发执行的事务时，会有很大限制


基于预写日志（WAL）复制


适用

日志结构存储引擎、采用覆盖写磁盘+预写日志的存储引擎都适合此类复制方式

缺点

复制方案和存储引擎紧密耦合，如果数据存储结构、存储引擎变化则会有很大影响和改变

实现

PostgreSQL、Oracle、MySQL


基于行的逻辑日志复制


复制和存储引擎采用不同的日志格式，复制和存储引擎逻辑剥离

关系数据库的逻辑日志一般指的是一系列记录来描述数据表行级别的写请求

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

对于行删除，日志里有足够的信息来唯一标识已删除的行，通常是靠主键

对于行更新，日志包含足够的信息来唯一标识更新的行，以及所有的新值

如果一条事务涉及多行的修改，会产生多条日志记录

实现


MySQL使用基于二进制日志binlog进行复制

基于触发器的复制

可以考虑基于应用层代码逻辑实现和控制

多主节点复制

特点

多主节点接收写操作，复制流程类似

每个主节点同时也扮演其他主节点的从节点角色

通常多主节点之间数据同步是异步复制

适用场景

一个数据中心使用多主节点基本没有太大意义，其复杂性已经超过所能带来的好处

适合多数据中心

适合应用与网络断开后继续工作的场景，如IM多端数据同步、文档协作编辑

多主主从复制 vs 单主主从复制

性能

容忍数据中心失效

容忍网络问题

问题

处理多主的写冲突，实现收敛冲突解决的方式

给每个写入分配唯一的ID，例如一个时间戳，一个足够长的随机数，一个UUID或者一个基于键-值的哈希，挑选最高ID的写入作为胜利者，并将其他写入丢弃

为每个副本分配一个唯一的ID，并制定规则，例如序号高德副本写入始终优先于序号低的副本

以某种方式将这些值合并在一起，如5-7，A-C


保留所有冲突信息，交给用户事后解决

写入时检查

读取时检查

多主节点模型的拓扑结构


多节点容错性更好

多节点数据通信传播复杂性增加

多节点数据复制覆盖问题

时间戳无法保证副本时钟

版本向量控制
无主节点复制


放弃选择主节点，允许任何副本直接处理客户端请求完成写处理

问题

多副本写入性能

大部分ack

失效节点恢复上线后进行数据追赶修复

最后写入者获胜 last write win - LWW

实现

Cassandra

复制滞后问题

满足最终一致性

写主，读从分摊压力

追求一致性

写后读

读写均在主节点

单调读

用户数据读取固定在一个副本执行

基于用户ID、IP的哈希方法

比强一致性弱，但比最终一致性强的保证

顺序一致读

顺序写入，不能产生乱序情况，包含数据上下文顺序，还有数据自身更新顺序

解决方案是，具有因果顺序关系的写入都交给一个分区副本来完成，但是效率和稳定性有损失

第6章 数据分区

数据分区与数据复制


每个分区在多个节点都存有副本
键-值数据的分区


分区的目的是将海量数据平均分摊到不同分区节点

分摊不均匀的情况叫做数据倾斜，导致部分分区效率性能严重下降

热点数据也会导致系统资源使用不均匀，过于集中于部分分区出现问题

基于关键字区间分区

指定一段段连续区间范围（最小值、最大值、时间戳）

这些区间不一定非要均匀分布，因为数据本身就可能不均匀

基于关键字哈希值分区


一个好的哈希函数可以处理数据倾斜并使其均匀分布，哈希能够解决数据分布均匀的问题，但是也破坏了连续性数据的区间特性
一致性哈希

哈希分区的热点，数据倾斜问题

需要在切分键上增加随机数或取模后缀进行再次rehash来打散

需要额外维护元数据来映射打散数据，还需要负责聚合这些数据

基于混合键分区


键的一部分标识分区，另一部分用来记录排序后的顺序
分区与二级索引


基于文档分区的二级索引（本地索引）

写数据时，按切分键（如用户ID）来路由到不同分区，并在各自分区内构建二级索引（如性别-用户ID关系）

读数据时，如果使用到二级索引进行检索，会同时查询所有分区中的二级索引拿到符合条件的数据然后做聚合返回

实现


MongoDB、Cassandra、Elasticsearch

基于词条的二级索引分区（全局索引）


构建全局索引，但是这个全局索引不仅仅存储在某个单点上，而是根据索引检索值路由到不同分区上

优点：客户端只需要对包含词条索引的分区发出一次请求，不需要遍历所有分区即可拿到索引命中的数据，效率更高

不足：写入速度较慢且非常复杂，主要是因为单个文档更新时，可能需要涉及多个二级索引的更新，而这些二级索引可能在不同分区节点上，造成写放大问题；且这个更新过程一般都是异步的，不会立刻反应在检索上


分区再平衡

动态再平衡策略

为什么不用取模

节点树变化，数据到分区节点的路由关系变化，需要重新迁移进行再平衡，成本巨大

固定数量的分区

创建远超实际节点数的分区数，然后为每个节点分配多个分区，比如10节点集群，每个节点分配100个逻辑分区

实现


Elasticsearch

动态分区


每个分区只属于一个节点，每个节点可以管理多个分区

如果一个节点中数据量过大，会被限制分区大小，避免倾斜


按节点比例分区


自动与手动再平衡操作

维护成本，可操作维护性


请求路由

服务发现问题

处理策略

允许客户端链接任意节点，如果节点恰好拥有所请求的分区，则直接处理该请求，否则会将请求转发到下一个合适的节点来处理

所有的客户端请求都发送到一个路由层，由路由层负责请求转发到对应的分区节点上。路由层不处理业务，只负责请求分发

客户端感知分区和节点分配关系。客户端可以直接链接到目标分区节点，不需要任何中介




并行查询执行

第7章 事务

深入理解事务


事务有其优势，也有自身局限性
ACID的含义


原子性（Atomicity）、一致性（Consistency）、隔离性（Isolation）、持久性（Durability）
BASE的含义


基本可用性（Basically Available）、软状态（Soft state）、最终一致性（Eventual consistency）
单对象、多对象事务操作


修改多个对象的整体一致性、隔离性等
单对象写入


修改单个对象的原子性、隔离性等
多对象事务的必要性

关系数据模型中，外键关系要求数据更新必须联动

文档数据模型中，由于缺少join功能支持，需要同时维护反范式多对象来更新

对于带有二级索引的数据库，需要维护事实表和二级索引的更新

处理错误和中止

支持安全的重试机制才是中止流程的重点

考虑返回客户端失败，但是重试执行成功导致的响应结果与实际数据状态不一致情况

重试需要设置次数上限，例如指数回退，避免给系统负载带来超负荷压力

由临时性故障引起的重试才有意义，永久性故障、错误导致的重试毫无意义

重试考虑幂等问题，避免重复

充分考虑重试的持久驱动，驱动进程也出现异常则再无可重试驱动力

弱隔离级别

并发问题 / 竞争条件

多个不同事务同时读取或操作同一数据

弱隔离的目的

提高性能，也要避免并发竞态带来的问题

读-提交

最基本的事务隔离级别，提高两个保证

读数据库时，只能看到已成功提交的数据，防止“脏读”

写数据库时，只会覆盖已成功提交的数据，防止”脏写”




实现读-提交


防止脏写：对访问数据对象上锁（如行级锁）保证同一时间一个事务进行事务操作

防止脏读：多版本快照提供非锁定读的支持，可以读已提交事务的最新数据，也可以读最旧的数据

快照级别隔离与可重复读


实现 PostgreSQL、MySQL的InnoDB存储引擎、SQL Server、Oracle

实现快照级别隔离


写锁防止脏写

读不需要加锁，是非阻塞的读

多版本并发控制 MVCC（Multi-Version Concurrency Control）

记录多个事务在不同时间点的数据对象提交版本

唯一、单调递增的事务ID（txid）


一致性快照的可见性规则

每笔事务开始时，其他进行中的事务对自身不可见

所有中止事务做的修改对自身不可见

较晚事务ID（晚于当前事务）所做的修改对自身不可见

其他所有的写入都对应用查询可见




索引与快照级别隔离


追加式的B-Tree，每个写入事务都会创建一个新的B-Tree root，代表该时刻数据库的一致性快照

查询根据特定快照B-Tree来实现隔离

需要后台进程来执行压缩和垃圾回收


防止更新丢失


写事务并发带来的问题

解决方案


原子写操作

单线程，顺序写入

显式加锁

FOR UPDATE

原子比较更新和设置 CAS（compare and set）

Update Table set content=2 where id = 1 and content=1

多副本的冲突解决和复制

多主节点或者无主节点中多副本，天然支持多个并发写，通常以异步方式来同步更新，因此也会出现多个最新的数据副本情况 该场景下加锁、原子比较不适用

解决方案是保留多个冲突版本，由应用层逻辑解决，或者依靠特定的数据结构来解决，合并多版本

最后写入获胜（LWW）

容易丢失更新，但是是多数多副本数据库的默认配置

写倾斜与幻读


定义写倾斜

原因

多个事务读取同一个数据对象，然后更新其中一部分或各自更新不同对象，造成写倾斜

涉及多个对象，单对象的原子操作不起作用

对参与原子操作的对象进行加锁

总结

由于有了不同隔离级别下支持的多版本非锁定读，拿到非锁定读数据只是整个事务操作的一步，且这个数据在事务外还会进行变化，那就导致整体事务操作的原子性不可控，背离初衷产生一些问题

幻读

实体化冲突

将竞态条件建立在可操作对象上进行加锁

串行化


最强的隔离级别

通过避免并发的方式解决并发问题

采用存储过程封装事务


优点

缺点

语义丑陋、过时，缺乏函数库支持

管理、调试、测试困难，不易监控和应用层集成

糟糕的存储过程会给数据库性能带来极大影响

两阶段加锁（2PL，tow-phase locking），比较标准的串行化方式


读锁定

写锁定

谓词锁

百度什么是“谓词”？
数理逻辑中表示一个个体的性质和两个或两个以上个体间关系的词 谓词锁不属于某个特定对象，而是面向某些特殊的搜索条件命中的对象，这里的代表可以是范围查询返回的行数据索引区间锁（next-key locking）

谓词锁性能不佳，事务中存在许多锁，检测匹配锁就变得非常耗时

索引区间锁是对谓词锁的简化和优化，它是对保护对象进行扩大化，优化可以理解为是把一条条具体明细锁变成了范围区间锁，效率是大大提升的

目的是有效防止写倾斜、幻读问题

当没有合适的索引（即没有合适的加锁对象）进行区间锁施加，会退化成锁表操作

可串行化的快照隔离（Serializable Snapshot Isolation，SSI ）


乐观并发控制
第8章 分布式系统挑战

故障与部分失效

不可靠的网络


网络问题

请求可能在节点转发中丢失

请求可能在某个队列中等待，无法马上发送

远程接受节点可能已经宕机失效

远程接收节点可能暂时无法响应（GC、负载过高等）

远程接收节点已经完成处理请求，但回复消息在回传过程中丢失

远程接收节点已经完成处理请求，但是回复消息超时返回，发送方无法处理

不可靠的时钟


时钟和计时的重要性

测量持续时间

记录业务时间节点

特定时间触发业务

单调时钟与墙上时钟

墙上时钟，根据某个日历返回当前的日期与时间

服务器与NTP服务同步

单调时钟，保证总是向前计数，不会出现回拨现象

单调时钟适合测量持续时间段

知识，真相与谎言


拜占庭将军问题
第9章 一致性与共识


一致性保证

强一致性

弱一致性

最终一致性
可线性化（原子一致性、强一致性）


多副本下数据读取结果在任何时刻都保持一致

对客户端来说就像只有一个数据副本一样

可线性化 vs 可串行化

可线性化

读写单个对象的最新值保证


可串行化


一般指事务隔离级别

线性化的依赖条件

加锁与主节点选举

主节点选举过程进行加锁保证线性化

如使用Zookeeper

约束与唯一性保证

数据库唯一索引

跨通道的时间依赖

如消息队列中消息的顺序性

实现线性化系统

主从复制（部分支持线性化）

主节点复制到从节点满足线性化

共识算法（可线性化）

通过共识协议防止多副本数据不一致，包含Zookeeper，etcd等

共识算法就是基于强一致性来实现，一定是可线性化的

多主复制（不可线性化）

由于在多个节点执行并发写入，数据异步复制到其他节点，因此写入有可能出现冲突

无主复制（可能不可线性化）

需要读取多个节点数据，但是无法确定节点数据间的差异

CAP理论


一致性(C)、可用性(A)、分区容错性(P)，系统只能同时满足两个特性

P 是客观存在的，无法避免的，在P不能满足时，只能选择可用性(A)或者一致性(C)

关于CAP理论对于分布式系统设计有重要指导作用，它已被更精确的研究成果所取代

顺序保证


事实证明，排序、可线性化与共识之间存在着联系

顺序与因果关系

因果关系对所发生的事件施加了某种排序

发送消息先于收到消息

问题出现在答案之前

如果系统服从因果关系所规定的的顺序，则称之为因果一致性

快照隔离提供了因果一致性，因为事务在数据读取时可以按照事件发生的顺序进行选择

因果顺序并非全序

全序和偏序的差异体现在不同数据一致性模型

可线性化

在一个可线性化的系统中，存在全序操作关系，能指出哪个操作在先，哪个在后

因果关系

两个非并发的操作一定存在因果关系（前后次序），否则不可排序

实现可线性化是要保持因果关系

单调递增序列号排序

非因果序列发生器

奇偶递增，A：1，3，5  B：2，4，6

时间戳递增，最后写获胜

按区间分配递增序列，A：1-1000 B：1001-2000

Lamport时间戳

全序关系广播

利用明确的顺序关系

分布式事务与共识


需要集群节点达成一致的场景

主节点选举

原子事务提交


两阶段提交 2PC（two-phase commit）

启动一个分布式事务时，向协调者请求全局唯一的事务ID

协调者向每个参与者发送执行事务的一阶段准备请求


参与者返回是否要提交的反馈、投票，协调者记录投票结果

投票不可反悔、不可更改

协调者按照结果通知所有参与者二阶段完成或者取消请求




三阶段提交 3PC

分布式事务概念

数据库内部的分布式事务

MySQL Cluster的NDB存储引擎

• 
  异构分布式事务
  
  存在两种及以上不同的参与者实现技术
  
  数据库 、缓存、消息队列等
  
  Exactly-once消息处理
  
  XA交易
     并不是网络协议，而是与事务协调者进行通信的API   停顿时仍持有锁   当有节点不能正常工作时，仍持有锁阻止其他事务进行并发操作
  从故障中恢复
     通过恢复日志、人为处理等方式
  分布式事务的限制
     协调者不支持数据复制，意味着单点运行，本身就不是高可用   协调者需要依赖日志进行中断事务的恢复和保证   2PC并不是完备的事务提交保证机制，需要考虑它的异常场景带来的问题
  
• 
  支持容错的共识
  
  共识算法的性质
     协商一致性       所有节点都接受相同的协议   诚实性       所有节点不能反悔，对一项提议不能有两次决定   合法性       如果决定了某个值，则一定是由某个节点提议的   可终止性   节点如果不崩溃最终一定可以达成协议
  共识算法
  

VSR、Paxos、Raft、Zab


全序关系广播

消息按照相同的顺序发送到所有节点，有且只有一次

相当于持续的多轮共识

由于协商一致性，所有节点决定以相同的顺序发送相同的消息

由于诚实性，消息不会改变

由于合法性，消息不会被破坏和造假

由于可终止性，消息不会丢失

主从复制与共识

主节点写入，同步给从节点，是满足共识的，这里主节点相当于独裁者角色

但是分布式场景下，选主过程中要避免出现多主

世纪编号（epoch number）

保证每个是世代里，主节点是唯一确定的

更高编号将获胜

共识的局限性

投票过程是一个同步复制过程，节点数据复制大部分是异步的，故障切换时有数据丢失风险

共识体系需要严格的节点数才能运行，因此会引入投票限制的节点部署代价

共识体系中节点不能动态添加、删除，否则会影响选举结果甚至出现问题

共识体系依赖超时机制来检测节点失效，超时时间的配置和网络情况对故障切换和感知有很大影响

• 
  成员与协调服务
  
  Zookeeper、ETCD、Consul
  
  保存少量、可完全载入内存（最终要写入磁盘以支持持久性）的数据设计
  
  采用容错的全序广播算法在所有节点上复制这些数据从而实现高可靠
  
  适用场景
     节点任务分配   作业调度   负载平衡   服务发现   成员服务
  

第三部分 派生数据

第10章 批处理系统

第11章 流处理系统

第12章 数据系统的未来

本文由博客一文多发平台 OpenWrite 发布！