《数据密集型应用系统设计》，英文名《Designing Data-Intensive Applications》

手机横屏观看效果更佳

第零部分 走进数据系统

第1章 整体设计目标和策略

数据密集系统相对与计算密集系统的主要特征：系统的瓶颈不在于CPU的处理能力，而是数据量、数据的复杂度及数据的快速多变性

1.1 认识数据系统

我们一般模块化地使用各个工具，比如数据库、缓存、索引、消息队列。通过集成一个个较小的通用模块，我们可以构建一个专门的数据系统（例子），并且通过用户界面或程序接口来隐藏内部的实现细节。这样的集成数据系统应该提供的技术保证：可靠、可扩展、可维护。

1.2 可靠

• 即使出现故障（硬件、软件、人为失误），系统也能保持正常运转

1.3 可扩展

• 即使面对突发的海量读写负载，系统也能保持性能稳定
  • 负载主要通过读写量来描述，比如推特平均每秒20万笔1KB写入
  • 负载影响性能指标，后者最好用百分位数表示，如99分位
    • 这方便我们了解异常值有多糟糕，理解整体用户的服务体验
    • 常见的服务标准是，“99%请求的相应时间小于1秒”

1.4 可维护

• 即使变得复杂或古老，系统也容易开发、运营与修复
  • 复杂度包括：状态空间的膨胀、依赖关系、不一致的命名、特殊例外与后门
    • 降低复杂度：用设计抽象隐藏大量的实现细节，对外提供简洁易懂的接口
  • 提高运营效率：监控系统状况、自动化、使用通用工具、维护运营手册

第一部分 数据系统的基石

单台机器的数据系统设计——数据的建模与查询、存储机制、编码与传输

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

大多数应用程序就是多层数据模型的叠加，每层都通过一个简洁的数据模型来隐藏下层的复杂性。分层的抽象机制使得软件团队内外的不同人群可以高效协作。

2.1 数据模型

• 纯文本模型：最原始的结构，数据之间没有任何关系
• 层次模型：最早期的结构，已濒危，结构为树（嵌套在记录中的记录）（例子）
  • 局限：只能表示一对多的关系；查询节点时必须获取其父节点
• 网状模型：已濒危，是层次模型的推广，结构为由指针连接的有向图（例子）
  • 局限：结构复杂，必须仔细维护每项记录的访问路径
• 关系模型：最主流的数据模型，由SQL实现，结构为数学上的关系
  • 列=属性/字段；行=多个字段的无序集合；二维表=关系=多行记录
  • 优点：支持多对多关系；无需手动维护访问路径；查询自动选择可用的索引
• 键值对模型：以Redis为代表，结构为哈希表，优点：查询速度快
• 文档模型：以MongoDB为代表，是键值对模型的子集，值为JSON或XML
  • 相比关系模型，无需提前定义字段的格式，依赖应用程序解释其结构和内容
  • 数据紧密存储，频繁查询整个文档时有性能优势（类似的优化：列式存储）
  • 局限：不适合多对一的关系（比如许多人住在同一城市，而城市名不一致）
  • 关系与文档模型的融合：前者支持JSON/XML字段，后者开始支持外键引用

2.2 数据查询语言

• 声明式语言：语言无需给出中间过程，只需给定输出的格式和结果应满足的条件
  • 由查询优化器来决定查询的语句和执行的顺序
  • 隐藏了数据库引擎的实现细节，可在不改变查询语句的情况下提高性能
  • 比如：SQL、CSS、GraphQL、EntQL
• 命令式语言：语言把执行操作的特定顺序告诉计算机
  • 代码可以逐行遍历，可以推算出中间变量和逻辑判断
  • 限制了多核及多节点上并行执行的能力（比如：大多数编程语言的for循环）
• 函数式语言/λ函数：语言给出函数的逻辑，但函数不与任何上下文进行交互
  • 比如：MapReduce中的映射器和汇总器回调函数

2.3 图状模型

• 图中所有记录都可相互关联，是对关系模型、列式存储与二级索引的一层抽象

• 图由顶点和边构成，边可以连接不同类型的顶点（比如：用户-购买-商品）

  • 顶点关系表：ID、出边的集合、入边的集合、属性的哈希表

  • 边关系表：ID、起点顶点、终点顶点、边的类型标签、属性的哈希表

  • 上述两个关系表相互引用，有冗余？空间换时间，遍历时可避免昂贵的JOIN
  • 如何避免查询时扫描全表？为顶点的属性和边的标签构建二级索引

• 图遍历语言：以SPARQL为代表，可以用正则表达式递归地在图中搜索目标

  • 若大明湖 位于 济南且济南 位于 山东 ，则哪里 位于* 山东能搜到大明湖

第3章 存储与检索

数据库只需做两件事情：添加数据时，保存数据；查询时，返回数据。

3.1 业务系统：日志与索引

• 日志：追加式更新的数据文件，用来存储数据
• 最简单的数据库是纯文本日志存储，每次写入时在文件末尾追加新的键值对
  • 读出时：遍历全文，返回键最新（最后）对应的值，复杂度为O(n)
• 索引：用来快速检索键的数据结构，使查询的复杂度小于O(n)
  • 副作用：每次写入记录都要更新对应字段的索引，减慢写入速度
• 哈希索引：以Bitcask为代表，哈希表的值是日志存储的数据值在硬盘中的位置
  • 日志耗尽硬盘空间？将数据依次存成数据段，每个段包含索引和值
    • 当段数超过某上限时，将多个段合并压缩（丢弃过期的键值），写入新段
  • 如何删除键？写入的数据值为某个特殊的标记，压缩时再删除键
  • 优点：读数据时只需一次硬盘读；硬盘顺序写超快，不碎片化；多线程读安全
  • 局限：所有哈希表必须全部放入内存；区间查询效率低：O(n)
• SSTable/LSM树：以脸书的RocksDB和谷歌的LevelDB为代表
  • 相比哈希索引，SSTable索引中的键必须有序（由平衡树实现，如红黑树）
  • 内存中的索引只保存少数键，每个键指向（多个段压缩成的）硬盘数据块
    • 存储：键值对直接写入内存树；若内存树过大，将子树追加式地存入硬盘
      • 后台对SSTable进行分层，并周期性地压缩与合并
    • 读取：先试图在内存树中查找某键，找不到则去硬盘逐层寻找
  • 优势：键的数据量和段文件都可大于可用内存、高速写入、区间查询
• B-tree索引：最广泛使用，是关系数据库的标准索引实现
  • 整个表的索引是一棵有序平衡树，使用4KB的页作为读写的最小单元
    • 每个页包含多个指针，分别引用下一级的页，每级都快速缩小键的范围
    • 写入新键时，满的页将分裂为两个半满的页，并更新父页
  • 写入时，原地修改硬盘上的旧页，不同于日志结构索引中仅追加更新
    • 为防止多线程写，编辑树的时候要加互斥锁
    • 为了在崩溃后修复数据，数据先写入预写日志，再编辑树
  • 优势：高速读取、读写性能稳定、键级别的事务隔离
  • 劣势：树的平衡需要更多次硬盘写、硬盘碎片化
• 其它索引概念
  • 聚集索引/一级索引：在索引中直接保存行数据
  • 非聚集索引/二级索引：在索引中只保存数据值的引用，高效执行JOIN和搜索
  • 覆盖索引：上两者的折中，索引中保存数据的几个字段
  • 全文索引（比如Elasticsearch）：键是单词，值是包含该词的文档ID列表
  • 其它：多列索引、模糊索引（单词匹配）、内存数据库（无需序列化）

3.2 分析系统

• 小公司的数据少，SQL/电子表格就能同时支持业务系统和分析系统的查询
• 大公司的分析系统运行在单独的数据仓库上面
  • 因为分析查询要扫描大量数据集，代价高，损害业务系统的并发性能
  • 周期或连续地从业务系统中提取数据
    • 业务数据可源于多条业务线，比如电商的销售、仓储、快递、门店
    • 提取-转换-清理-加载到数据仓库的过程被称为ETL
• Hadoop生态：分布式计算MapReduce与Spark，数据仓库Hive，数据流Pig
• 数据模型为星型：事实表位于中间，指向众多维度表
  • 相比（第2章介绍的）业务系统中复杂的数据模型，分析系统的模型非常一致
  • 事实表：每行表示特定时间发生的事件，比如：某项物品的购买
    • 每列包含属性（如：时间、产品售价）和外链（如：产品ID、客户ID）
  • 维度表：描述事件中的某一个对象的具体信息，比如：产品、店铺、客户
• 列式存储：以Cassandra和HBase为代表
  • 主要解决万亿行的事实表的存储，因为维度表通常只有百万行
  • 业务系统一般把一行的所有值彼此相邻，但分析查询一般只访问少数列
  • 列式存储：数据表的每列存成一个文件，各文件的第i项对应数据表的第i行
    • 每列具有相同的数据类型和相似的值，非常适合数据压缩和矩阵计算
• 使用数据立方体进行汇总：在原始数据上，把高频的查询结果预先计算并保存
  • 数据立方体：以原始数据的列作为维度，在多个维度上压缩数据
    • 比如，原始销售数据有四个维度：日期、地点、产品、网店
    • 每个网店每天的总销售量：汇总地点和产品，生成网店和日期的二维表

第4章 编码与演化

• 编码：庞大的软件需要拆分成模块，模块间的沟通需要彼此兼容的编码协议
• 演化：各个模块的快速迭代，数据格式不断更新，会造成多版本共存
  • 典型原因：版本的滚动升级、终端用户的习惯/局限

4.1 编码结构

• 基本数据结构
  • 由指针维护的内存结构：对象、数组、树、哈希表
  • 硬盘或网络中的连续字节文件：JSON、XML、CSV
• 结构与文件相互转换：编码（序列化）、解码（反序列化、解析）
  • 编程语言自带的编码一般与语言绑定，牺牲了兼容性、安全性、性能
• 最流行的编码：JSON（非常流行，在Web浏览器中内置）、XML（语法冗长）
  • 类型模糊：字符串与数字、整数与浮点数、大数字
  • 不原生支持二进制字节序列和数据格式更新
    • 二进制编码：方便压缩空间、提升解析性能，但牺牲可读性
• 格式驱动的二进制编码协议：需要格式来编码任意的数据
  • 静态类型：以脸书的Thrift和谷歌的Protocol Buffers为代表
    • struct Cat {1: required i64 id, 2: optional string name}
    • 协议原生的工具能生成多种编程语言的类，调库就能自动地编码或解码
    • 编码没有字段名（id, name），只有字段标签（1, 2）和数据类型
    • 兼容新数据：旧代码能够读取新代码写入的数据
      • 新字段添加到格式后，旧代码自动忽略新的字段
      • 新格式只能删除旧格式里可选（或有默认值的）的字段
    • 兼容旧数据：新代码能够读取旧代码写入的数据
      • 添加的每个新字段都必须是可选的（或有默认值）
  • 动态类型：以Avro为代表，基于JSON，适合动态类型编程语言
    • 无需为语言生成代码；编码内容中没有数据类型、字段标签和名称
    • 格式演化：读模块和写模块在握手时交换彼此的格式
      • 各个格式只能增加或删除具有默认值的字段
      • 收到数据后，读模块只提取数据里自己格式中存在的字段

4.2 数据传递

• 数据传递：数据从一个进程流向（不共享内存的）另一个进程
• 基于数据库的传递：使用数据库查询语言直接读写，编码与解码进程彼此独立
  • 不同的进程会有数据库格式版本差异，小心旧代码丢掉新字段
  • 数据比代码更长久：5年前的数据仍然使用原始编码
    • 添加新列时，除非已完成数据迁移，否则建议将旧数据的新列填入空值
• 基于服务的传递：服务器通过网络公开API/服务，客户端向API发送请求
  • 和数据库最大的区别：服务限制了数据的范围和粒度，封装了数据获取方式
  • 客户端（浏览器、手机app）使用HTTP的GET和POST读写HTML资源
  • 组织之间-在线服务：后端系统数据交换，以OAuth和脸书的GraphAPI为代表
    • REST：使用URL来标识网络上的资源
      • 支持所有主流编程语言、平台、浏览器，伴随庞大的工具生态系统
  • 组织内部-微服务/中台：A服务的客户端可以是B服务的服务器
    • 比如：A是数据库，B是业务逻辑层
    • 每个服务由一个团队进行维护，更容易进行部署、演化和维护
    • RPC：进程发出的“网络服务请求”看上去与“本地函数调用”相同
      • 局限：难以处理请求超时、无法传递指针变量、不同语言间数据转换
      • 新一代RPC框架封装了可能失败的异步操作，比如Futures/Promises
• 基于消息队列的传递
  • 消息队列兼具RPC和数据库的性质
    • 类似RPC：客户端的请求（消息）以低延迟传递到另一个进程
    • 类似数据库：不直接向解码进程发送消息，而是让消息队列暂存后发送
  • 单向数据流：指定某队列/主题，多个生产者向其发布消息，多个消费者订阅
    • 为实现RPC的请求响应，消费者可向另一主题发布消息，原生产者订阅
  • 优点：缓冲区避免接收方过载、崩溃自动重试、逻辑上分离发送方与接收方

第二部分 分布式数据

使用多台机器来维护一个数据库的系统设计

• 为什么要把数据放在多台机器节点上？
  • 扩展性：数据量或读写的负载严重超过了单台机器的处理上限
    • 共享内存/硬盘架构（垂直扩展）中，两倍硬件指标未必能处理两倍负载
    • 无共享架构（水平扩展）中，单台运行数据库软件的机器称为节点
      • 由网线进行连接通讯，由软件进行管理
      • 性价比高，可以租用云计算虚拟机进行部署
  • 容错/可用：当部分组件出现故障，冗余组件可以迅速接管，让系统平稳工作
  • 降低延迟：在地理上更靠近客户的应用服务，可以更快地完成数据请求

第5章 复制

• 在多节点上保存相同数据的副本：容忍节点故障、扩展并行吞吐量、低访问延迟
  • 如何应对持续更改的数据？如何确保副本间的数据一致？

5.1 主从复制

• 副本：数据库的一个完整数据集，保存在一个（或分区支持的多个）节点上
• 主从复制：指定某一个副本为主节点，其余副本为（客户端只读的）从节点
  • 主节点把所有新数据写入本地存储，把每一笔数据更新写入复制日志
  • 所有从节点获得复制日志，在本地按顺序执行更新
• 主节点何时向客户端报告写入完成？
  • （全）同步复制：主节点需等待所有从节点完成复制
  • 半同步复制：主节点只等待一个从节点完成复制，其它节点异步更新
  • （全）异步复制：主节点不等待任何从节点，保持连续的响应和高吞吐性能
• 如何添加从节点，使其追赶上主节点的最新状态？
  • 周期性地为主节点创建一致性快照，将此快照复制到新节点
  • 寻找快照所对应的复制日志位置，执行此位置后的所有更新
• 如何在保持系统可用的情况下，处理个别节点（短暂）失效？
  • 从节点失效：找到复制日志中的最近一笔更新，追赶式恢复
  • 主节点失效：用超时确认失效后，通过共识选出新的主节点，更新写请求路由
    • 超时时间：过长导致系统恢复慢；过短导致不必要的切换，系统状况恶化
    • 新旧主节点的不一致可导致严重的问题，自动切换有时不如运维手动配置
• 哪种复制日志可以让各副本完全一致？
  • 原始的SQL写语句？依赖当前状态则不适用，如时间戳、线程执行顺序
  • SSTable日志或B-tree预写日志？与存储引擎的耦合过于紧密，软件更新困难
  • 基于行值的逻辑日志？与存储引擎解耦，方便兼容旧编码、数据仓库

5.2 复制滞后问题

• 最终一致性：异步复制时，从节点相对主节点的更新滞后时间没有理论上限
• 神秘消失？新数据提交到主节点，读取数据来自从节点，新数据暂时不可见
  • 写后读一致性：用户总能看到自己提交的最新数据
  • 实现：根据用户身份、从节点滞后程度、写入顺序序列号，找主节点读取
  • 难以处理同一用户多设备访问数据的情况
• 穿越回过去？先读取不滞后的节点，后读取滞后的从节点，新数据出现又消失
  • 单调读一致性：用户读取新值之后不会再读取旧值
  • 实现：每个用户ID总是从固定的节点读取数据
• 预知未来？用户C发现用户B的回答先于用户A的问题，因为用户A的复制有滞后
  • 前缀读一致性：读取因果的次序与写入因果的次序相同

5.3 多主复制

• 相比主从复制，多主复制有多个主节点，每个都可独立接受写请求
  • 适用于多数据中心、协作编辑文档、离线编辑
• 主节点之间互相采用异步复制，需要解决并发写冲突
  • 定义：两个不知道另一方存在的操作为并发操作，与时间无关
  • 主从复制中的不一致只是短暂的，而写冲突可以导致最终结果不一致
  • 解决方法：最后写入获胜、拼接所有写入值、应用层提示用户处理
• 预设主节点复制顺序可能出现故障瓶颈，而广播可能导致因果关系乱序写入

5.4 无主复制

• 相比主从复制，无主复制没有主节点，所有节点都可接受写请求
• 每次并行写入半数以上的节点，则并行读取半数以上的节点一定包含新数据
  • 比较多个节点来修复滞后的节点：读时修复，或后台进程主动检查
• 解决5.3中的并发写冲突之后，无主复制一般只能保证5.2中的最终一致性
• 如何知道各节点的数据有多滞后？
  • 主从复制可以测量主从节点在复制日志上的差距，因为写入的次序相同
  • 无主复制没有统一的写入次序，难以测量，而且读时修复的数据可以极度滞后
• 多主和无主复制的可用性比主从复制高，代价是系统的复杂性和弱一致性保证

第6章 分区

单个节点无法容纳整个数据集，则把数据集拆分成多个子集/分区，帮助系统扩展

6.1 分区与复制

• 复制和分区经常组合使用（比如：主从复制分区的例子）
  • 每条数据只属于某个特定的分区，而同样的内容复制保存在不同的节点上
  • 某节点可以包含多个不同分区的副本
• 第5章涉及的复制原理均适用于分区数据的复制

6.2 分区平衡

• 分区的目标：把数据的存储和查询压力均匀分布在所有节点上
  • 分区失衡：某些节点的压力显著高于其它节点，导致某些节点超负荷
  • 排序键分区？利于区间查询，难以寻找合适的键和分区边界
  • 哈希键分区？无法彻底避免单节点的负荷失衡（比如：突发时事的关键字）
    • 可手工在某热键的结尾加随机数，来强行分散热键的压力
• 增减节点时，如何动态地调整存储和查询的压力？
  • 分区数远大于节点数，每次增减节点，其它节点都只增减少量分区
  • 动态创建分区：单分区的数据量超过上限则分裂，小于下限则合并

6.3 分区与二级索引

• 在二级索引中，某字段值对应的多个键应该放入哪些分区？
  • 多个键的多个分区：查询需遍历所有分区，以获取该字段值对应的所有键
  • 单一分区：每个值的所有键集中在一处，而某字段的不同值放在多个分区
    • 即全局索引：读延迟小，写延迟大，因为需要异步地执行分布性事务

6.4 请求路由

• 来自客户端的查询应该发送给哪个节点？
  • 典型的“服务发现”问题：需要一个模块来作出查询-节点的路由决策
  • 模块的位置有3种解决方案：节点、客户端、中间路由层
  • 全局路由状态的同步，需要独立的协调服务ZooKeeper或节点间同步协议

第7章 事务

数据层、应用层、客户端之间会出现各种错误，事务是简化这些问题的首选机制

7.1 事务基本概念

• 事务：将应用程序的多个读写操作捆绑在一起，成为一个逻辑操作单元
• 什么是ACID？Atomic, Consistency, Isolation, Durability
  • 原子性：作为一个执行的整体，整个事务要么圆满完成，要么中止且复原
    • 如果失败，应用程序可以安全地重试，无需担心任何部分失败的情况
  • 一致性？要求应用层维护数据状态恒等，不是事务的属性
  • 隔离性：同时运行的事务不互相干扰，逻辑上是串行执行，没有资源竞争
  • 持久性：数据已写入硬盘，或已经复制到多个节点
• 总是重试中止的事务？执行成功信息丢失、系统超负荷、写入不合规、副作用

7.2 弱隔离级别：读

• 如何防止事务间的资源竞争，即某事务错误地读到其它事务稍后修改的数据？
  • 并发性的错误难以测试发现和重现，涉及多用户时更难以排查
  • 串行化的隔离会严重影响性能，所以普遍采用较弱的隔离级别
• 写隔离：防止（事务写入多个字段期间的）脏读和脏写
  • 脏读：一个事务读到另一个事务的数据的中间状态
  • 脏写：两个事务的写入交叉覆盖（比如：数据永久出现“山东省无锡市”）
    • 在同一行，事务1写入“山东省”“济南市”，事务2写入“江苏省”“无锡市”
  • 实现：事务写入前获取数据的行级锁，事务完成或中止后释放
    • 事务完成前，数据库维护待更新字段的旧值，方便其它事务读取
• 快照隔离：防止（读期间出现事务写的）不可重复读
  • 不可重复读不违反写隔离（比如：数据暂时出现“山东省无锡市”）
    • 事务1先读取省份，事务2写入“江苏省无锡市”，事务1再读取城市名
    • 长时间运行的只读（备份和分析）查询中，业务数据出现永久不一致
  • MVCC技术：每个事务都始终从特定时间点的一致性快照中读取数据
    • 每个（增删改查）事务对应单增的ID，每个键保留多个版本的行
    • 每个版本对应“键-写事务ID”，读事务只读取“写事务ID小于本ID”的版本

7.3 弱隔离级别：写

• 如何避免并发写冲突造成的更新丢失？
  • 单主节点串行执行“读-修改-写”：数据层的原子写/比较、应用层的显式加锁
  • 单主节点自动检测更新丢失：先允许并行，检测到风险则强制串行
  • 多主节点：加锁或原子比较不适用，参考5.3的并发写冲突解决
• 如何避免幻读造成的更新异常？
  • 幻读：一个事务中的写入改变了另一个事务的查询结果
  • 快照隔离解决了只读查询时的幻读，没解决依赖于读的写事务
  • 比如：吃火锅，两人都发现没锅，于是都买了；发现对方买了，于是都没带
  • 解决：串行化隔离+谓词锁、实体化冲突（比如：创建一行“房间ID-锅数量”）

7.4 串行化隔离

• 工业界的弱隔离级别通常没有统一定义、难以理解、难以测试
  • 因为经过数十年的讨论，学术界才找到描述事务隔离性的理论（详情）
• 串行化：事务并行执行的结果与依次/串行执行的结果相同
• 实际串行执行：单线程依次执行事务，避免锁开销
  • 影响性能？扩容降价的内存可储存整个数据库、业务系统事务读写较少
  • 限制：吞吐量上限是单个CPU核的吞吐、事务执行不支持网络/硬盘读写
• 两阶段加锁：相比写隔离，写锁不仅排斥写，还排斥读
  • 一阶段-上锁：事务对于自己需要读写的数据，集齐所有相关的读锁和写锁
  • 二阶段-解锁：事务完成/复原后，释放所有的读写锁
  • 谓词锁：锁住满足匹配条件的所有行，无论某行存在与否
    • 索引区间锁：在索引的值上加锁；锁住更多行，但加锁更快
  • 优化：越热点的记录越晚锁提高吞吐，数据库检测死锁后中止某事务
• 可串行快照隔离：在事务执行时，如果违反任何读写隔离，则中止
  • 防止写事务期间有读：读事务查看快照版本中其它事务未执行的写
  • 防止写事务之前有读：读事务在数据留下读信息，留给写事务发现并报告

第8章 分布式系统的麻烦

所有可能出错的事情，都一定会出错！

8.1 局部失效

• 局部失效：系统的一部分正常运行，另一部分出现难以预知的故障
  • 作为对比，单机系统中的任何核心硬件的错误都会导致系统完全崩溃
    • 超算的故障处理：定期储存系统快照，节点故障后用快照重启集群
• 局部失效是不确定的（比如：发送的消息是否送达），大大提高了系统的复杂性
  • 大多数分布式系统需全天候在线，重启集群修复故障不可取
  • 云计算使用的硬件海量、通用、廉价，使故障率更高，局部失效近乎常态化
• 基于不可靠的组件构造可靠的系统：依靠软件系统，为失效提供有限的容错机制
  • 比如：通信系统中的纠错码、互联网协议IP层之上的TCP层

8.2 不可靠的网络

• 在无共享（内存/硬盘）的系统中，网络是跨节点通讯的唯一途径
  • 网络通讯更容易支持跨区域的多数据中心，使系统整体更可靠
• 互联网（及大部分数据中心内网）的通讯不提供任何结果和时间的保证
  • 多种未知的失败：请求丢失、远程节点下线、响应丢失
  • 多种延迟：（路由器/远程节点/本节点）队列过长、远程节点进程暂停
  • 超时机制：（在TCP/应用层）重试，若等待期间没有响应，则判定节点失效
    • 过早超时可能导致节点频繁下线，造成其它节点的高负荷，并不断扩散

8.3 不可靠的时钟

• 物理时间：用于测量当前的世界时间点，依赖在线同步
  • 同步时，可能导致时间前后跳跃，不适合测量时间间隔
• 单增时间：用于测量时间段，电脑启动后单调递增，不依赖同步
  • 节点间比较毫无意义，适合测量超时
• 节点时间不准：石英钟的精度、同步服务不稳定、闰秒、虚拟机切换
  • 解决石英漂移，可借助北斗接收器或原子钟
• 需要精确时间时，集群需监控所有节点的时钟偏差，并踢除偏差超标的节点
  • 超标的危害：最后写入获胜中，慢时钟节点上的新写被看作旧写而丢弃
• 进程长期暂停：垃圾回收、虚拟机/进程切换、磁盘读写/缺页中断
  • 实时操作系统？可保证响应时间，但吞吐量太低且工具苛刻，不适合服务器

8.4 从不可靠到可靠

• 监测和处理分布式系统中的部分失效，会受制于网络和时钟的可靠性
  • 比如：无法区分超时对应的网络和节点故障
• 哪些基本假设可以让系统更可靠？
  • 单一节点不可靠：多数投票算法+单增令牌，强行让过期的锁/主节点失效
  • 消除撒谎的节点：验证来自客户端的请求，防止注入的代码改变网站的功能
• 系统理论模型：对预期的系统错误进行形式化描述
  • 计时（同步、半同步、异步），节点失效（崩溃中止、崩溃恢复、任意失效）
  • 算法正确（比如，单调令牌算法需保证令牌唯一、单增、请求最终有响应）
  • 理论不足以满足实践（比如：降级至1kB/s吞吐的节点，比崩溃更难处理）

第9章 一致性与共识

通过一套抽象机制和相应的容错技术保证，让应用程序安全地信赖底层

9.1 抽象与容错

• 在分布式系统中，第8章中所有的故障都可能发生
  • 丢包、乱序、重复、延迟、时钟偏差、节点暂停/崩溃
• 分布式系统的抽象使应用逻辑更简单，忽略系统内部的各种问题
  • 一致性：针对延迟和故障等问题，协调副本之间的状态
  • 共识：所有的节点就某项提议达成一致
• 第7章的事务也是给应用程序提供各种容错的抽象
  • 没有崩溃（原子性）、没有并发访问（隔离性）、存储完全可靠（持久性）
  • 事务隔离更关注并发执行事务的边界情况，而一致性更关注副本的状态差异

9.2 一致性

• 更强的一致性意味着性能代价更高、可用性更低
• 线性一致性：系统看起来只有一个数据版本（强一致性）
  • 一旦最新值被读取，则任意客户端都必能看到新值，即使新值的写还未返回
  • 串行化隔离强调数据库的最终版本，线性一致性强调最新值保证
    • 实际串行和两阶段加锁都提供线性一致性，但串行快照隔离不提供
  • 应用：持有锁的节点唯一、用户名唯一、库存值/余额非负约束
  • 实现：共识算法、不使用快照隔离的主从复制
  • 性能代价：网络中断/分区的情况下，线性一致和可用只能2选1（CAP理论）
    • 线性一致性的数据库很少见，就连多核CPU都存在缓存和内存的不一致
• 顺序一致性：所有节点看到的读写顺序都相同（强一致性）
  • 系统使用逻辑时钟（序列号）构建系统上的全序和每个节点上操作的偏序
    • 对比：线性一致性试图使用物理时钟构建全局全序
    • 狭义相对论告诉我们，时空中不存在绝对的全序事件顺序
  • 逻辑时钟（如兰伯特算法）可构建系统全序，但不足以实现全局用户名唯一
    • 后者需借助全序广播/全局日志，而这等价于共识问题
• 因果一致性：所有节点看到的具有因果关系的读写顺序都相同（弱一致性）
  • 更少约束的偏序：相比顺序一致性，只约束具有因果关系的读写
• 客户端一致性：只为单一客户端提供一致性保证（弱一致性）（参考）

9.3 共识

• 共识的理论模型：提议被所有节点接受、不可反悔、源于某节点、可最终通过
• 原子执行：保证多节点的事务全部完成或全部中止，不存在“部分完成”
  • 复习单节点原子写：若预写日志已写入硬盘，则支持崩溃后重试；否则复原
  • 两阶段执行：协调器收集齐所有节点的票后，才允许多节点执行事务
    • 与两阶段加锁是完全独立的概念
    • 一阶段-投票：各节点将事务写入复制日志，向协调器承诺“准备”并阻塞
    • 二阶段-执行：协调器汇总结果并写入复制日志，广播“执行”或“放弃”
    • 节点或协调器半途崩溃？有复制日志则不断重试直至恢复；否则放弃
  • 局限：使用异构系统时，某些节点不支持原子执行协议，如邮件服务器
  • 系统死锁：当多节点持有行级锁或读写锁，协调器的崩溃可阻塞大量事务
• 全序广播等价于多轮共识：每一轮的共识对应一条广播消息
  • 主从复制中主节点写入、从节点执行的复制日志，就是基本的全序广播
• 容错的共识算法：相比两阶段执行，投票只需过半，增加了主节点的选举和识别
  • 流行的协议：ZooKeeper的Zab（ZooKeeper Atomic Broadcast）
  • 恢复模式：选举主节点，每轮对应单增的选举码，各节点保存最新的选举码
  • 广播模式：主节点广播事务，过半从节点支持后，主节点广播并执行
    • “真假美猴王”：过期主节点的选举码更小，系统忽略其广播并转为从节点
• 与共识问题等价：线性一致性、原子执行、全序广播、唯一性约束
  • 均可由主从复制实现，但要处理主节点故障：等待、手动配置、共识算法

第三部分 数据系统集成

同步/整合异构的数据系统：数据库、索引、缓存、分析系统

• 根据数据产生方式划分，数据类型有两种：
  • 记录数据：真实的业务数据（比如：用户账号、发帖记录、购买记录）
    • 不同数据系统间遇到差异时，以记录数据为准
  • 衍生数据：对记录数据进行转换的结果，以优化查询和指导业务
    • 若衍生数据丢失，可从原始数据源进行重建（比如：缓存不命中）
• 如何区分？不取决于存储机制和查询语言，更多依赖于用户的定义和使用方式

第10章 批处理

10.1 什么是批处理？

• 根据交互类型划分，数据系统有三种：
  • 在线系统：用户触发请求，并等待服务器响应（即本书的第一、二部分）
  • 批处理/离线系统：周期性地处理有界的大量数据（像公交车运输乘客）
    • 读取一组文件作为输入，生成一组文件作为输出
  • 流处理系统：介于前两者之间，近实时地处理数据
    • 相比批处理的有界分批输入，流处理的输入无限、延迟更小
• 批处理历久弥新：银行间每日清算、水电每月账单、IBM的人口普查制表机
  • 主要应用：分析系统、搜索引擎的索引、机器学习的分类器和推荐系统

10.2 Unix单机批处理

• Unix脚本可以对大量日志字符串进行数据分析（比如：将网址按浏览量排序）
  • 使用Unix管道依次连接：字符串切割、排序、计数、按列排序、取前5
• 数据大于内存时的硬盘排序：n个子文件排序后，依次内存排序各文件的前1/n
• Unix管道的哲学：化整为零、使用文件作为标准输入输出接口、模块化测试

10.3 MapReduce与分布式文件系统

• MapReduce计算框架由谷歌提出，由Hadoop和MongoDB仿制
• 使用分布式文件系统（在Hadoop的实现为HDFS）的只读文件作为输入
  • HDFS使用无共享架构，无需特殊的硬件，存储的容量大而单位成本低
• MapReduce（映射-汇总）分为四步，其中映射器和汇总器的回调函数需自定义：
  • 1/ 加载：各节点加载本地文件；2/ 映射：映射器从本地输入文件中提取键值对
  • 3/ 排序：对所有键值对按键排序；4/ 汇总：汇总器将相同键的所有值汇总
  • 汇总：对一系列值进行求平均值、最值、和、中位数、计数
• 并行计算基于分区：在子文件所在节点运行映射器，让计算靠近数据
• 数据管道：前后依赖的MapReduce任务通过临时文件传递数据
• 容错：无状态的回调函数使任务失败时可以安全地重试，并丢弃失败任务的输出

• 什么是Hadoop？像分布式的Unix：HDFS是文件系统，MapReduce是进程

  • Hadoop的数据类型广泛、不限于SQL，由数据消费者而非生产者解释数据
  • Hive是在HDFS和MapReduce之上建立的SQL引擎

10.4 改进MapReduce

• MapReduce易于理解但难以直接使用，比如SQL的JOIN需要进行复杂的实现
  • 所以Hadoop在这之上封装抽象了各种高级工具，比如：Hive、Pig
    • 有些高级接口允许交互式使用，方便数据探索与测试
    • 声明式查询：自动选择JOIN的算法与次序，使中间状态最少
• 数据流对MapReduce的改进：不需要将所有中间状态写入分布式文件系统
  • 串联多任务时，映射器通常是冗余的：只是读取前一个汇总器的文件
  • 可在内存/本地硬盘串联汇总器构成数据流引擎，比如：Spark
    • 这里的汇总器被称为函数运算符，构成有向无环图

第11章 流处理

如何持续地处理事件？

11.1 发送事件流

• 事件：包含时间戳的一个请求，可表示为事实表的一行记录
  • 来源：用户活动、传感器、金融市场数据、服务器日志
  • 编码：字符串、JSON、二进制格式
• 流：随着时间的推移而不断出现的数据，比如：网络直播、系统监控/仪表盘
  • 批处理中，文件写入一次后，可被多个作业读取；记录组合成文件名
  • 流处理中，生产者发布一次，可被多个消费者订阅；事件组合成主题或流
• 消息系统：发布新事件后，系统主动向消费者通知新事件
  • 消费者处理过慢？丢弃消息、缓存消息至队列/硬盘、抑制消息发送
  • 不使用代理：金融行业的UDP多播、基于HTTP或RPC的钩子（订阅生产者）
• 消息代理/队列/中间件：异步处理消息流的服务器（以生产者和消费者为客户端）
  • 优点：提高客户端响应速度、服务模块解耦、流量削峰、数据传输缓冲
  • 基于推的RabbitMQ：基于JMS/AMQP协议，不保证顺序（除非单线程消费）
  • 基于拉的Kafka：基于分区日志（监视文件的尾部），保证顺序，可回溯
    • 很像主从复制：消息代理=主节点，消费者=从节点，偏移量=日志序列号
• 向消息代理发送消息：HTTP或MQTT（基于TCP协议，源于沙漠油田连接卫星）

11.2 有时数据库也是流

• 跨服务的并发写冲突，比如数据库、索引与缓存之间不一致？
  • 解决：把数据库抽象为消息代理，各服务按顺序异步处理变更数据
  • 实现：数据库提供变更流/复制日志的接口，或使用“变更数据捕获”工具
  • 各子服务的变更流输出的结果状态不一致？直接广播结果状态，而非变化量
• 经过覆盖删除后，中间状态丢失？只建新行，不删旧行，按需构建历史的流
• 数据模型违反规范化，比如我发的图在所有好友的朋友圈重复？
  • 解释：数据的写和读的形式可以分开，允许为了优化读而用流广播内容

11.3 流处理：分析与容错

• 流分析：测量近期的统计信息，比如：p99响应时间、5分钟内平均查询次数
  • 以只读的方式接收输入流，借助数据流持续进行过滤、计算、汇总
  • 事件时间有多种统计口径：客户端的发生、发送，流处理节点的接收、处理
    • 影响因素：客户设备时钟的精度、网络延迟、流节点进程暂停
• 流容错：相比批处理更有限，因为很难恢复已运行多年的流作业
  • 微批处理：把流切分成1秒长的多个文件，运行容错的批处理
  • 多次失败导致重复发送邮件？使用原子执行以保证副作用的一致性
  • 写入ID幂等，递增不幂等？<计数, 请求ID>，仅ID不匹配时递增并更新ID

第12章 集成数据系统

结合全书介绍的数据工具，我们能做什么，不能做什么？

12.1 集成数据工具

• 对于任何给定的问题，一般都有多种解决方案，比如存储引擎、多副本复制
  • 厂商不愿宣传软件产品不适合解决哪些问题，需要分析字里行间的含义
• 实际的业务往往需要集成多个数据工具，没有绝对通用或无用的工具
  • 比如（提供持久化的）业务数据库和（提供复杂查询的）全文搜索索引
  • 工具之间的数据不一致？使用基于日志的数据流或基于锁的两阶段执行
    • 后者提供线性一致性，但是性能和容错性远不如前者
  • 全序的局限：单主节点的性能、多数据中心、微服务独立存储、离线编辑
• 并行地使用批处理和流处理，则既能实时，又能精确而容错地处理历史数据

12.2 数据的抽象

• 数据库与文件系统都是一种（用来保存、处理和查询数据的）硬件抽象
  • 前者抽象层次更高，由数据模型表示记录，支持多种强大的声明式查询
  • 后者抽象层次更低，仅仅是硬件资源的一层包装，比如HDFS和NoSQL
• 数据的正确性需要审计：内存与硬盘的数据有极小概率出现损坏
  • HDFS等大型存储系统周期性比较各副本并修复，维持“存储正确”的抽象

12.3 数据层与应用层

• 数据库的局限性：即使用了最强的事务，也无法阻止应用层误写或误删数据
  • 比如，某客户端的第一次支付没有得到确认，则第二次（多余地）支付
  • 幂等容错：应用层创建唯一的UUID请求ID来帮数据库消除重复的请求
• 应用层和流处理分区日志的结合，可优化唯一性和原子执行的性能局限
  • 唯一性：将用户名哈希到分区，各流处理分区分配给顺序中的第一个请求
  • 原子执行：将请求ID写入日志，流处理向各节点发请求，节点幂等执行
    • 无需阻塞各节点，但未经协调的异步执行会导致不可重复读

12.4 技术的局限

• 总是使用最“高级”的技术？一个可用的复杂系统总是从可用的简单系统演进而来
  • 反之，如果一个复杂系统开始就用不了，那之后也无法使其可用
• 技术并不总是改善人类社会：数据=监控
  • 算法经常会系统性地洗白各种歧视、剥削和诱惑，把人困在算法里
  • 只有掌握充足的时间或知识的人，才可能不使用某种垄断的技术服务

• Previous
  回调函数与匿名类
• Next
  西周史