设计数据密集型应用

设计数据密集型应用 - 中文翻译

第一部分：数据系统的基石

第一章：可靠性，可扩展性，可维护性

如今很多应用程序都是数据密集型而不是计算密集型的

  • 存储数据，以便自己或其他应用程序之后能再次找到 （数据库（database））
  • 记住开销昂贵操作的结果，加快读取速度（缓存（cache））
  • 允许用户按关键字搜索数据，或以各种方式对数据进行过滤（搜索索引（search indexes））
  • 向其他进程发送消息，进行异步处理（流处理（stream processing））
  • 定期处理累积的大批量数据（批处理（batch processing））

​本书着重讨论三个在大多数软件系统中都很重要的问题：

  • 可靠性（Reliability）
    ​ 系统在困境（adversity）（硬件故障、软件故障、人为错误）中仍可正常工作（正确完成功能，并能达到期望的性能水准）。
  • 可扩展性（Scalability）
    ​ 有合理的办法应对系统的增长（数据量、流量、复杂性），负载参数（load parameters）描述系统当前负载
  • 可维护性（Maintainability）
    ​ 许多不同的人（工程师、运维）在不同的生命周期，都能高效地在系统上工作（使系统保持现有行为，并适应新的应用场景）。

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

在历史上，数据最开始被表示为一棵大树（层次数据模型），但是这不利于表示多对多的关系，所以发明了关系模型来解决这个问题。

现在最著名的数据模型可能是SQL，SQL是一种 声明式 查询语言，而许多常用的编程语言是命令式的。

在声明式查询语言（如SQL或关系代数）中，你只需指定所需数据的模式 - 结果必须符合哪些条件，以及如何将数据转换（例如，排序，分组和集合） - 但不是如何实现这一目标。数据库系统的查询优化器决定使用哪些索引和哪些连接方法，以及以何种顺序执行查询的各个部分。

声明式查询语言是迷人的，因为它通常比命令式API更加简洁和容易。但更重要的是，它还隐藏了数据库引擎的实现细节，这使得数据库系统可以在无需对查询做任何更改的情况下进行性能提升。

非关系数据库，NoSQL，被追溯性地重新解释为不仅是SQL（Not Only SQL）

MapReduce既不是一个声明式的查询语言，也不是一个完全命令式的查询API，而是处于两者之间：查询的逻辑用代码片断来表示，这些代码片段会被处理框架重复性调用。它基于map（也称为collect）和reduce（也称为fold或inject）函数，两个函数存在于许多函数式编程语言中。

第三章：存储与检索

我们会研究两大类存储引擎：日志结构（log-structured） 的存储引擎，以及面向页面（page-oriented）的存储引擎（例如B树）。

日志（log） 这个词通常指应用日志：即应用程序输出的描述发生事情的文本。本书在更普遍的意义下使用日志这一词：一个仅追加的记录序列。它可能压根就不是给人类看的，使用二进制格式，并仅能由其他程序读取。

索引是从主数据衍生的附加（additional）结构。许多数据库允许添加与删除索引，这不会影响数据的内容，它只影响查询的性能。维护额外的结构会产生开销，特别是在写入时。写入性能很难超过简单地追加写入文件，因为追加写入是最简单的写入操作。任何类型的索引通常都会减慢写入速度，因为每次写入数据时都需要更新索引。

哈希索引

键值存储（key-value Data） 与在大多数编程语言中可以找到的字典（dictionary）类型非常相似，通常字典都是用散列映射（hash map）（或哈希表（hash table））实现的。

假设我们的数据存储只是一个追加写入的文件，就像前面的例子一样。那么最简单的索引策略就是：保留一个内存中的哈希映射，其中每个键都映射到一个数据文件中的字节偏移量，指明了可以找到对应值的位置。当你将新的键值对追加写入文件中时，还要更新散列映射，以反映刚刚写入的数据的偏移量（这同时适用于插入新键与更新现有键）。当你想查找一个值时，使用哈希映射来查找数据文件中的偏移量，寻找（seek） 该位置并读取该值。

Bitcask存储引擎就是这么做的（Riak默认的存储引擎），Bitcask提供高性能的读取和写入操作，但所有键必须能放入可用内存中，因为哈希映射完全保留在内存中。Bitcask非常适合每个键的值经常更新的情况。

如果仅仅是追加写的日志，占用空间可能很大，所有可以将日志分为特定大小的段，当日志增长到特定尺寸时关闭当前段文件，并开始写入一个新的段文件。然后，我们就可以对这些段进行压缩（compaction）。压缩意味着在日志中丢弃重复的键，只保留每个键的最近更新。

由于压缩经常会使得段变得很小（假设在一个段内键被平均重写了好几次），我们也可以在执行压缩的同时将多个段合并在一起。段被写入后永远不会被修改，所以合并的段被写入一个新的文件。

哈希表索引也有局限性：

  • 散列表必须能放进内存
  • 范围查询效率不高（无法范围查询）

SSTables和LSM树

如果要求键值对的序列按键排序，这种格式称为排序字符串表（Sorted String Table），简称SSTable，我们还要求每个键只在每个合并的段文件中出现一次（压缩过程已经保证）

相比于哈希索引，SSTable的优势：

  • 合并段是简单而高效的，即使文件大于可用内存。这种方法就像归并排序算法中使用的方法一样，如果多个段有相同的键，保留最新值即可。
  • 不再需要保存内存中所有键的索引，假设你正在内存中寻找键B，而你知道键A和键C的便宜，由于排序特性，键B必然在这两者之间，于是可以跳到键A然后向后扫描，如果没找到，则文件中没有该键，虽然仍然需要一些类似定位点的索引来记录键的偏移量，单它可能很稀疏，每几千字节的段文件有一个键就足够了（几千字节可以很快被扫描）
构建和维护SSTables

红黑树或AVL树这些数据结构，可以按任何顺序插入键，并按排序顺序读取它们。

存储引擎工作如下：

  • 写入时，将其添加到内存中的平衡树数据结构（例如，红黑树）。这个内存树有时被称为内存表（memtable）。
  • 当内存表大于某个阈值（通常为几兆字节）时，将其作为SSTable文件写入磁盘。这可以高效地完成，因为树已经维护了按键排序的键值对。新的SSTable文件成为数据库的最新部分。当SSTable被写入磁盘时，写入可以继续到一个新的内存表实例。
  • 为了提供读取请求，首先尝试在内存表中找到关键字，然后在最近的磁盘段中，然后在下一个较旧的段中找到该关键字。
  • 有时会在后台运行合并和压缩过程以组合段文件并丢弃覆盖或删除的值。

唯一会碰到的问题是：如果数据库崩溃，最近的写入（在内存表中，单尚未写进磁盘）将会丢失。为了避免，可以在磁盘上保存一个单独的日志，每个写入都会立即被附加到磁盘上，每当内存表写出到SSTable时，相应的日志都可以被丢弃。

用SSTables制作LSM树

基于这种合并和压缩排序文件原理的存储引擎通常被称为LSM存储引擎，是LevelDB和RocksDB中使用的关键值存储引擎库

Lucene是Elasticsearch和Solr使用的一种全文搜索的索引引擎，它使用类似的方法来存储它的词典。全文索引比键值索引复杂得多，但是基于类似的想法：在搜索查询中给出一个单词，找到提及单词的所有文档（网页，产品描述等）。这是通过键值结构实现的，其中键是单词（关键词（term）），值是包含单词（文章列表）的所有文档的ID的列表。（倒排索引的感觉）

性能优化

布隆过滤器确定键是否存在

还有不同的策略来确定SSTables如何被压缩和合并的顺序和时间。最常见的选择是大小分层压实。 LevelDB和RocksDB使用平坦压缩（LevelDB因此得名），HBase使用大小分层，Cassandra同时支持

B树

像SSTables一样，B树保持按键排序的键值对，这允许高效的键值查找和范围查询。B树有着非常不同的设计理念。

前面看到的日志结构索引将数据库分解为可变大小的段，通常是几兆字节或更大的大小，并且总是按顺序编写段。相比之下，B树将数据库分解成固定大小的块或页面，传统上大小为4KB（有时会更大），并且一次只能读取或写入一个页面。这种设计更接近于底层硬件，因为磁盘也被安排在固定大小的块中。

一个页面会被指定为B树的根；在索引中查找一个键时，就从这里开始。该页面包含几个键和对子页面的引用。每个子页面负责一段连续范围的键，以及之间的键的引用，这些引用又进一步地指明了子子页面的键范围。最后，我们可以看到包含单个键（叶页）的页面。

插入和删除通常需要分割或者合并页面，该算法确保树保持平衡，B树的深度是O(logn)

让B树更加可靠

B树的基本底层写操作是用新数据覆盖磁盘上的页面，而且插入和删除需要覆盖几个页面。

为了让B树更加可靠，B树实现通常会带有一个额外的磁盘数据结构：预写式日志（WAL, write-ahead-log）（也称为重做日志（redo log））。这是一个仅追加的文件，每个B树修改都可以应用到树本身的页面上。当数据库在崩溃后恢复时，这个日志被用来使B树恢复到一致的状态

如果多个线程要同时访问B树，则需要仔细的并发控制 —— 否则线程可能会看到树处于不一致的状态。这通常通过使用锁存器（latches）（轻量级锁）保护树的数据结构来完成。日志结构化的方法在这方面更简单，因为它们在后台进行所有的合并，而不会干扰传入的查询，并且不时地将旧的分段原子交换为新的分段。

B树优化
  • 写时复制，而不覆盖页面并维护WAL进行崩溃恢复
  • 不存储整个键来节省页面空间，键只需要提供足够的信息来充当键范围之间的边界
  • 许多B树实现尝试布局树，使得叶子页面按顺序出现在磁盘上。但是，随着树的增长，维持这个顺序是很困难的。相比之下，由于LSM树在合并过程中一次又一次地重写存储的大部分，所以它们更容易使顺序键在磁盘上彼此靠近。
  • 每个叶子页面可以在左边和右边保存对其兄弟页面的引用，而不用跳回父页面（这好像是B+树的特点？？？）

比较B树和LSM树

读写速度

通常LSM树的写入速度更快，而B树的读取速度更快

LSM树上的读取通常比较慢，因为它们必须在压缩的不同阶段检查几个不同的数据结构和SSTables。

LSM树的优点

B树索引必须至少两次写入每一段数据：一次写入预先写入日志，一次写入树页面本身（也许再次分页）。即使在该页面中只有几个字节发生了变化，也需要一次编写整个页面的开销。有些存储引擎甚至会覆盖同一个页面两次，以免在电源故障的情况下导致页面部分更新

SM树通常能够比B树支持更高的写入吞吐量，部分原因是它们有时具有较低的写放大（尽管这取决于存储引擎配置和工作负载），部分是因为它们顺序地写入紧凑的SSTable文件而不是必须覆盖树中的几个页面

LSM树可以被压缩得更好，因此经常比B树在磁盘上产生更小的文件。 B树存储引擎会由于分割而留下一些未使用的磁盘空间：当页面被拆分或某行不能放入现有页面时，页面中的某些空间仍未被使用。由于LSM树不是面向页面的，并且定期重写SSTables以去除碎片，所以它们具有较低的存储开销，特别是当使用平坦压缩时。

LSM树的缺点

日志结构存储的缺点是压缩过程有时会干扰正在进行的读写操作，因为磁盘资源有限

压缩的另一个问题出现在高写入吞吐量：磁盘的有限写入带宽需要在初始写入（记录和刷新内存表到磁盘）和在后台运行的压缩线程之间共享。写入空数据库时，可以使用全磁盘带宽进行初始写入，但数据库越大，压缩所需的磁盘带宽就越多。

如果写入吞吐量很高，并且压缩没有仔细配置，压缩跟不上写入速率。在这种情况下，磁盘上未合并段的数量不断增加，直到磁盘空间用完，读取速度也会减慢，因为它们需要检查更多段文件。

B树的一个优点是每个键只存在于索引中的一个位置，而日志结构化的存储引擎可能在不同的段中有相同键的多个副本。这个方面使得B树在想要提供强大的事务语义的数据库中很有吸引力：在许多关系数据库中，事务隔离是通过在键范围上使用锁来实现的，在B树索引中，这些锁可以直接连接到树

其他索引结构

到目前为止，我们只讨论了关键值索引，它们就像关系模型中的主键（primary key） 索引。主键唯一标识关系表中的一行，或文档数据库中的一个文档或图形数据库中的一个顶点。数据库中的其他记录可以通过其主键（或ID）引用该行/文档/顶点，并且索引用于解析这样的引用。

聚集/聚簇索引

从索引到堆文件（行被存储的地方）的额外跳跃对读取来说性能损失太大，因此可能希望将索引行直接存储在索引中，这被称为聚集索引。在MySQL的InnoDB存储引擎中，表的主键总是一个聚簇索引，二级索引用主键（而不是堆文件中的位置）

在 聚集索引（clustered index） （在索引中存储所有行数据）和 非聚集索引（nonclustered index） （仅在索引中存储对数据的引用）之间的折衷被称为 包含列的索引（index with included columns）或覆盖索引（covering index），其存储表的一部分在索引内

与任何类型的数据重复一样，聚簇和覆盖索引可以加快读取速度，但是它们需要额外的存储空间，并且会增加写入开销。数据库还需要额外的努力来执行事务保证，因为应用程序不应该因为重复而导致不一致。

多维索引

最常见的多列索引被称为 连接索引（concatenated index） ，它通过将一列的值追加到另一列后面，简单地将多个字段组合成一个键（索引定义中指定了字段的连接顺序）

多维索引（multi-dimensional index） 是一种查询多个列的更一般的方法，这对于地理空间数据尤为重要（经度和维度）

全文搜索和模糊索引

到目前为止所讨论的所有索引都假定您有确切的数据，并允许您查询键的确切值或具有排序顺序的键的值范围。他们不允许你做的是搜索类似的键，如拼写错误的单词。这种模糊的查询需要不同的技术。

全文搜索引擎通常允许搜索一个单词以扩展为包括该单词的同义词，忽略单词的语法变体，并且搜索在相同文档中彼此靠近的单词的出现，并且支持各种其他功能取决于文本的语言分析。为了处理文档或查询中的拼写错误，Lucene能够在一定的编辑距离内搜索文本（编辑距离1意味着添加，删除或替换了一个字母）

Lucene为其词典使用了一个类似于SSTable的结构。这个结构需要一个小的内存索引，告诉查询在排序文件中哪个偏移量需要查找关键字。在LevelDB中，这个内存中的索引是一些键的稀疏集合，但在Lucene中，内存中的索引是键中字符的有限状态自动机，类似于trie 。这个自动机可以转换成Levenshtein自动机，它支持在给定的编辑距离内有效地搜索单词

在内存中存储一切

本章到目前为止讨论的数据结构都是对磁盘限制的回答。

随着RAM变得更便宜，许多数据集不是那么大，也可以将它们全部保存在内存中，可能分布在多台机器上，这导致了内存数据库的发展

某些内存数据库不需要持久性，某些内存中的键值存储（如Memcached）仅用于缓存，在重新启动计算机时丢失的数据是可以接受的。而有些内存数据库的目标是持久性，可以通过特殊的硬件（例如电池供电的RAM），将更改日志写入磁盘，将定时快照写入磁盘或通过复制内存来实现，记忆状态到其他机器。

除了性能，内存数据库的另一个有趣的领域是提供难以用基于磁盘的索引实现的数据模型。例如，Redis为各种数据结构（如优先级队列和集合）提供了类似数据库的接口。因为它将所有数据保存在内存中，所以它的实现相对简单。

所谓的 反缓存（anti-caching） 方法通过在内存不足的情况下将最近最少使用的数据从内存转移到磁盘，并在将来再次访问时将其重新加载到内存中。这与操作系统对虚拟内存和交换文件的操作类似，但数据库可以比操作系统更有效地管理内存，因为它可以按单个记录的粒度工作，而不是整个内存页面。尽管如此，这种方法仍然需要索引能完全放入内存中

列存储

面向列的存储背后的想法很简单：不要将所有来自一行的值存储在一起，而是将来自每一列的所有值存储在一起。如果每个列存储在一个单独的文件中，查询只需要读取和解析查询中使用的那些列，这可以节省大量的工作。

列存储更适合bitmap压缩

第四章：编码与演化

当数据格式（format）或模式（schema）发生变化时，通常需要对应用程序代码进行相应的更改（例如，为记录添加新字段，然后修改程序开始读写该字段）。但在大型应用程序中，代码变更通常不会立即完成：

  • 对于 服务端（server-side） 应用程序，可能需要执行 滚动升级 （rolling upgrade） （也称为 阶段发布（staged rollout） ），一次将新版本部署到少数几个节点，检查新版本是否运行正常，然后逐渐部完所有的节点。这样无需中断服务即可部署新版本，为频繁发布提供了可行性，从而带来更好的可演化性。
  • 对于 客户端（client-side） 应用程序，升不升级就要看用户的心情了。用户可能相当长一段时间里都不会去升级软件。

这意味着，新旧版本的代码，以及新旧数据格式可能会在系统中同时共处。系统想要继续顺利运行，就需要保持双向兼容性：

  • 向后兼容 (backward compatibility)：新代码可以读旧数据。
  • 向前兼容 (forward compatibility)：旧代码可以读新数据。

向后兼容性通常并不难实现：新代码的作者当然知道由旧代码使用的数据格式，因此可以显示地处理它（最简单的办法是，保留旧代码即可读取旧数据）。

向前兼容性可能会更棘手，因为旧版的程序需要忽略新版数据格式中新增的部分

本章中将介绍几种编码数据的格式，包括 JSON，XML，Protocol Buffers，Thrift和Avro。尤其将关注这些格式如何应对模式变化，以及它们如何对新旧代码数据需要共存的系统提供支持。然后将讨论如何使用这些格式进行数据存储和通信：在Web服务中，具象状态传输（REST）和远程过程调用（RPC），以及消息传递系统（如Actor和消息队列）。

编码数据的格式

程序通常（至少）使用两种形式的数据：

  • 在内存中，数据保存在对象，结构体，列表，数组，哈希表，树等中。 这些数据结构针对CPU的高效访问和操作进行了优化（通常使用指针）。
  • 如果要将数据写入文件，或通过网络发送，则必须将其 编码（encode） 为某种自包含的字节序列（例如，JSON文档）。 由于每个进程都有自己独立的地址空间，一个进程中的指针对任何其他进程都没有意义，所以这个字节序列表示会与通常在内存中使用的数据结构完全不同。

所以，需要在两种表示之间进行某种类型的翻译。 从内存中表示到字节序列的转换称为 编码（Encoding） （也称为序列化（serialization）或编组（marshalling）），反过来称为解码（Decoding）（解析（Parsing），反序列化（deserialization），反编组( unmarshalling））

许多编程语言都内建了将内存对象编码为字节序列的支持，但是其他语言很难读取这种数据，除非临时使用，采用语言内置编码通常是一个坏主意

JSON，XML和二进制变体

数字的编码多有歧义之处。XML和CSV不能区分数字和字符串（除非引用外部模式）。 JSON虽然区分字符串和数字，但不区分整数和浮点数，而且不能指定精度。

JSON和XML对Unicode字符串（即人类可读的文本）有很好的支持，但是它们不支持二进制数据（不带字符编码(character encoding)的字节序列）

JSON比XML简洁，但与二进制格式一比，还是太占地方，这一事实导致大量二进制编码版本JSON & XML的出现

Thrift与Protocol Buffers

Apache Thrift 和Protocol Buffers（protobuf）是基于相同原理的二进制编码库。 Protocol Buffers最初是在Google开发的，Thrift最初是在Facebook开发的，并且在2007~2008年都是开源的。 Thrift和Protocol Buffers都需要一个模式来编码任何数据。

Thrift ：

1
2
3
4
5
struct Person {
    1: required string       userName,
    2: optional i64          favoriteNumber,
    3: optional list<string> interests
}

Protocol Buffers：

1
2
3
4
5
message Person {
    required string user_name       = 1;
    optional int64  favorite_number = 2;
    repeated string interests       = 3;
}

我们之前说过，模式不可避免地需要随着时间而改变。我们称之为模式演变。 Thrift和Protocol Buffers如何处理模式更改，同时保持向后兼容性？

只要每个字段都有一个唯一的标签号码，新的代码总是可以读取旧的数据，因为标签号码仍然具有相同的含义。因此，为了保持向后兼容性，在模式的初始部署之后 添加的每个字段必须是可选的或具有默认值

Protobuf的一个奇怪的细节是，它没有列表或数组数据类型，而是有一个字段的重复标记

Apache Avro

Apache Avro 是另一种二进制编码格式，与Protocol Buffers和Thrift有趣的不同。 它是作为Hadoop的一个子项目在2009年开始的，因为Thrift不适合Hadoop的用例

数据流的类型

数据库中的数据流

在数据库中，写入数据库的过程对数据进行编码，从数据库读取的过程对数据进行解码

服务中的数据流：REST与RPC

REST不是一个协议，而是一个基于HTTP原则的设计哲学。它强调简单的数据格式，使用URL来标识资源，并使用HTTP功能进行缓存控制，身份验证和内容类型协商

相比之下，SOAP是用于制作网络API请求的基于XML的协议，虽然它最常用于HTTP，但其目的是独立于HTTP，并避免使用大多数HTTP功能。相反，它带有庞大而复杂的多种相关标准

RPC（ 远程过程调用）模型试图向远程网络服务发出请求，看起来与在同一进程中调用编程语言中的函数或方法相同（这种抽象称为位置透明）。尽管RPC起初看起来很方便，但这种方法根本上是有缺陷的。网络请求与本地函数调用非常不同：

  • 本地函数调用是可预测的，并且成功或失败，这仅取决于受您控制的参数。网络请求是不可预知的：由于网络问题，请求或响应可能会丢失，或者远程计算机可能很慢或不可用，这些问题完全不在您的控制范围之内。网络问题是常见的，所以你必须预测他们，例如通过重试失败的请求。
  • 本地函数调用要么返回结果，要么抛出异常，或者永远不返回（因为进入无限循环或进程崩溃）。网络请求有另一个可能的结果：由于超时，它可能会返回没有结果。在这种情况下，你根本不知道发生了什么：如果你没有得到来自远程服务的响应，你无法知道请求是否通过。
  • 如果您重试失败的网络请求，可能会发生请求实际上正在通过，只有响应丢失。在这种情况下，重试将导致该操作被执行多次，除非您在协议中引入去重（ 幂等（idempotence））机制。本地函数调用没有这个问题。
  • 每次调用本地功能时，通常需要大致相同的时间来执行。网络请求比函数调用要慢得多，而且其延迟也是非常可变的：在不到一毫秒的时间内它可能会完成，但是当网络拥塞或者远程服务超载时，可能需要几秒钟的时间完全一样的东西。
  • 调用本地函数时，可以高效地将引用（指针）传递给本地内存中的对象。当你发出一个网络请求时，所有这些参数都需要被编码成可以通过网络发送的一系列字节。如果参数是像数字或字符串这样的基本类型时没关系，但是对于较大的对象很快就会变成问题。

尽管有这样那样的问题，RPC不会消失。在本章提到的所有编码的基础上构建了各种RPC框架：例如，Thrift和Avro带有RPC支持，gRPC是使用Protocol Buffers的RPC实现，Finagle也使用Thrift，Rest.li使用JSON over HTTP

其中一些框架还提供服务发现，即允许客户端找出在哪个IP地址和端口号上可以找到特定的服务

RESTful API还有其他一些显著的优点：对于实验和调试（只需使用Web浏览器或命令行工具curl，无需任何代码生成或软件安装即可向其请求），它是受支持的所有的主流编程语言和平台，还有大量可用的工具（服务器，缓存，负载平衡器，代理，防火墙，监控，调试工具，测试工具等）的生态系统。由于这些原因，REST似乎是公共API的主要风格。 RPC框架的主要重点在于同一组织拥有的服务之间的请求，通常在同一数据中心内。

消息传递中的数据流（消息队列）

异步消息传递系统：与RPC类似，因为客户端的请求（通常称为消息）以低延迟传送到另一个进程；与数据库类似，不是通过直接的网络连接发送消息，而是通过称为消息代理（也称为消息队列或面向消息的中间件）的中介来临时存储消息

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

  • 如果收件人不可用或过载，可以充当缓冲区，从而提高系统的可靠性。
  • 它可以自动将消息重新发送到已经崩溃的进程，从而防止消息丢失。
  • 避免发件人需要知道收件人的IP地址和端口号（这在虚拟机经常出入的云部署中特别有用）。
  • 它允许将一条消息发送给多个收件人。
  • 将发件人与收件人逻辑分离（发件人只是发布邮件，不关心使用者）。

然而，与RPC相比，差异在于消息传递通信通常是单向的：发送者通常不期望收到其消息的回复。一个进程可能发送一个响应，但这通常是在一个单独的通道上完成的。这种通信模式是异步的：发送者不会等待消息被传递，而只是发送它，然后忘记它。

消息代理的使用方式如下：一个进程将消息发送到指定的队列或主题，代理确保将消息传递给一个或多个消费者或订阅者到那个队列或主题。在同一主题上可以有许多生产者和许多消费者。

消息代理通常不会执行任何特定的数据模型 - 消息只是包含一些元数据的字节序列，因此您可以使用任何编码格式。如果编码是向后兼容的，则您可以灵活地更改发行商和消费者的独立编码，并以任意顺序进行部署。

第二部分：分布式数据

如果多台机器参与数据的存储和检索，会发生什么？

你可能会出于各种各样的原因，希望将数据库分布到多台机器上：

  • 可扩展性：如果你的数据量、读取负载、写入负载超出单台机器的处理能力，可以将负载分散到多台计算机上。
  • 容错/高可用性：如果你的应用需要在单台机器（或多台机器，网络或整个数据中心）出现故障的情况下仍然能继续工作，则可使用多台机器，以提供冗余。一台故障时，另一台可以接管。
  • 延迟：如果在世界各地都有用户，你也许会考虑在全球范围部署多个服务器，从而每个用户可以从地理上最近的数据中心获取服务，避免了等待网络数据包穿越半个世界。

如果你需要的只是扩展至更高的载荷（load），最简单的方法就是购买更强大的机器（有时称为垂直扩展（vertical scaling）或向上扩展（scale up））。

  • 许多处理器，内存和磁盘可以在同一个操作系统下相互连接，快速的相互连接允许任意处理器访问内存或磁盘的任意部分。在这种共享内存架构（shared-memory architecture）中，所有的组件都可以看作一台单独的机器。
  • 另一种方法是共享磁盘架构（shared-disk architecture），它使用多台具有独立处理器和内存的机器，但将数据存储在机器之间共享的磁盘阵列上，这些磁盘通过快速网络连接（网络附属存储（Network Attached Storage, NAS），或存储区网络（Storage Area Network, SAN））。这种架构用于某些数据仓库，但竞争和锁定的开销限制了共享磁盘方法的可扩展性

相比之下，无共享架构（shared-nothing architecture）（有时称为水平扩展（horizontal scale） 或向外扩展（scale out））已经相当普及。在这种架构中，运行数据库软件的每台机器/虚拟机都称为节点（node）。每个节点只使用各自的处理器，内存和磁盘。节点之间的任何协调，都是在软件层面使用传统网络实现的。

复制（Replication）：在几个不同的节点上保存数据的相同副本，可能放在不同的位置。 复制提供了冗余：如果一些节点不可用，剩余的节点仍然可以提供数据服务。 复制也有助于改善性能。

分区 (Partitioning)：将一个大型数据库拆分成较小的子集（称为分区），从而不同的分区可以指派给不同的节点（node）（亦称分片（shard））

第五章：复制

如果复制中的数据不会随时间而改变，那复制就很简单：将数据复制到每个节点一次就万事大吉。复制的困难之处在于处理复制数据的变更（change），这就是本章所要讲的。我们将讨论三种流行的变更复制算法：单领导者（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）。每个跟随者从领导者拉取日志，并相应更新其本地数据库副本，方法是按照领导者处理的相同顺序应用所有写入。
  • 当客户想要从数据库中读取数据时，它可以向领导者或追随者查询。 但只有领导者才能接受写操作（从客户端的角度来看从库都是只读的）。
同步复制与异步复制

​复制系统的一个重要细节是：复制是同步（synchronously）发生还是异步（asynchronously）发生。 （在关系型数据库中这通常是一个配置项，其他系统通常硬编码为其中一个）。

同步复制的优点是，从库保证有与主库一致的最新数据副本。如果主库突然失效，我们可以确信这些数据仍然能在从库上上找到。缺点是，如果同步从库没有响应（比如它已经崩溃，或者出现网络故障，或其它任何原因），主库就无法处理写入操作。主库必须阻止所有写入，并等待同步副本再次可用。

​因此，将所有从库都设置为同步的是不切实际的：任何一个节点的中断都会导致整个系统停滞不前。实际上，如果在数据库上启用同步复制，通常意味着其中一个跟随者是同步的，而其他的则是异步的。如果同步从库变得不可用或缓慢，则使一个异步从库同步。这保证你至少在两个节点上拥有最新的数据副本：主库和同步从库。 这种配置有时也被称为 半同步（semi-synchronous）

设置新从库

简单地将数据文件从一个节点复制到另一个节点通常是不够的：客户端不断向数据库写入数据，数据总是在不断变化，标准的数据副本会在不同的时间点总是不一样。复制的结果可能没有任何意义。

可以通过锁定数据库（使其不可用于写入）来使磁盘上的文件保持一致，但是这会违背高可用的目标。幸运的是，拉起新的从库通常并不需要停机。从概念上讲，过程如下所示：

  • 在某个时刻获取主库的一致性快照（如果可能），而不必锁定整个数据库。大多数数据库都具有这个功能，因为它是备份必需的。对于某些场景，可能需要第三方工具。
  • 将快照复制到新的从库节点。
  • 从库连接到主库，并拉取快照之后发生的所有数据变更。这要求快照与主库复制日志中的位置精确关联。该位置有不同的名称：例如，PostgreSQL将其称为 日志序列号（log sequence number, LSN），MySQL将其称为 二进制日志坐标（binlog coordinates）。
  • 当从库处理完快照之后积压的数据变更，我们说它赶上（caught up）了主库。现在它可以继续处理主库产生的数据变化了。
处理节点宕机

从库失效：追赶恢复

主库失效：故障切换

​主库失效处理起来相当棘手：其中一个从库需要被提升为新的主库，需要重新配置客户端，以将它们的写操作发送给新的主库，其他从库需要开始拉取来自新主库的数据变更。这个过程被称为故障切换（failover）。

故障切换可以手动进行（通知管理员主库挂了，并采取必要的步骤来创建新的主库）或自动进行。自动故障切换过程通常由以下步骤组成：

  • 确认主库失效。有很多事情可能会出错：崩溃，停电，网络问题等等。没有万无一失的方法来检测出现了什么问题，所以大多数系统只是简单使用 超时（Timeout） ：节点频繁地相互来回传递消息，并且如果一个节点在一段时间内（例如30秒）没有响应，就认为它挂了（因为计划内维护而故意关闭主库不算）。
  • 选择一个新的主库。这可以通过选举过程（主库由剩余副本以多数选举产生）来完成，或者可以由之前选定的控制器节点（controller node）来指定新的主库。主库的最佳人选通常是拥有旧主库最新数据副本的从库（最小化数据损失）。让所有的节点同意一个新的领导者，是一个共识问题。
  • 重新配置系统以启用新的主库。客户端现在需要将它们的写请求发送给新主库（将在“请求路由”中讨论这个问题）。如果老领导回来，可能仍然认为自己是主库，没有意识到其他副本已经让它下台了。系统需要确保老领导认可新领导，成为一个从库。

一些麻烦：

  • 如果使用异步复制，则新主库可能没有收到老主库宕机前最后的写入操作。在选出新主库后，如果老主库重新加入集群，新主库在此期间可能会收到冲突的写入，那这些写入该如何处理？最常见的解决方案是简单丢弃老主库未复制的写入，这很可能打破客户对于数据持久性的期望。
  • 发生某些故障时可能会出现两个节点都以为自己是主库的情况。这种情况称为 **脑裂(split brain)**，非常危险：如果两个主库都可以接受写操作，却没有冲突解决机制（参见“多领导者复制”），那么数据就可能丢失或损坏。

复制日志的实现

基于语句的复制

在最简单的情况下，主库记录下它执行的每个写入请求（语句（statement））并将该语句日志发送给其从库。对于关系数据库来说，这意味着每个INSERT，UPDATE或DELETE语句都被转发给每个从库，每个从库解析并执行该SQL语句，就像从客户端收到一样。

缺点：

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

5.1版本前的MySQL中使用基于语句的使用，有时候现在也在用，现在MySQL主要使用基于行的复制

传输预写式日志（WAL）

在第3章中，我们讨论了存储引擎如何在磁盘上表示数据，并且我们发现，通常写操作都是追加到日志中：

  • 对于日志结构存储引擎（请参阅“SSTables和LSM树”），日志是主要的存储位置。日志段在后台压缩，并进行垃圾回收。
  • 对于覆写单个磁盘块的B树，每次修改都会先写入 预写式日志（Write Ahead Log, WAL），以便崩溃后索引可以恢复到一个一致的状态。

在任何一种情况下，日志都是包含所有数据库写入的仅追加字节序列。可以使用完全相同的日志在另一个节点上构建副本：除了将日志写入磁盘之外，主库还可以通过网络将其发送给其从库。
​
当从库应用这个日志时，它会建立和主库一模一样数据结构的副本。

主要缺点是日志记录的数据非常底层：WAL包含哪些磁盘块中的哪些字节发生了更改。这使复制与存储引擎紧密耦合。

逻辑日志复制（基于行）

另一种方法是，复制和存储引擎使用不同的日志格式，这样可以使复制日志从存储引擎内部分离出来。这种复制日志被称为逻辑日志，以将其与存储引擎的（物理）数据表示区分开来。

​由于逻辑日志与存储引擎内部分离，因此可以更容易地保持向后兼容，从而使领导者和跟随者能够运行不同版本的数据库软件甚至不同的存储引擎。

复制延迟问题

最终一致性

应用程序从异步从库读取时，如果从库落后，它可能会看到过时的信息。这会导致数据库中出现明显的不一致：同时对主库和从库执行相同的查询，可能得到不同的结果，因为并非所有的写入都反映在从库中。这种不一致只是一个暂时的状态——如果停止写入数据库并等待一段时间，从库最终会赶上并与主库保持一致。出于这个原因，这种效应被称为 最终一致性（eventually consistency），最终一致性也可以叫做收敛

读己之写

提交新数据时，必须将其发送给领导者，但是当用户查看数据时，可以从追随者读取。但在异步复制的场景下，如果用户在写入后马上就查看数据，则新数据可能尚未到达副本。

在这种情况下，我们需要 读写一致性（read-after-write consistency），也称为 读己之写一致性（read-your-writes consistency）

  • 读用户可能已经修改过的内容时，都从主库读；比如用户读自己的个人资料只能从主库读（因为用户可能修改自己的个人资料），用户读他人的个人资料可以从从库读（因为用户不可能修改他人的个人资料）
  • 在上次更新后的一分钟内，都从主库读
  • 客户端可以记住最近一次写入的时间戳，系统需要确保从库为该用户提供任何查询时，该时间戳前的变更都已经传播到了本从库中。如果当前从库不够新，则可以从另一个从库读，或者等待从库追赶上来。时间戳可以是逻辑时间戳（指示写入顺序的东西，例如日志序列号）或实际系统时钟（在这种情况下，时钟同步变得至关重要）
单调读

​ 从异步从库读取第二个异常例子是，用户可能会遇到 时光倒流（moving backward in time）。如果用户从不同从库进行多次读取，首先查询了一个延迟很小的从库，然后是一个延迟较大的从库，就可能发生这种情况，先看到的记录后面看不到了，仿佛时光倒流一般。

单调读（Monotonic reads）是这种异常不会发生的保证。这是一个比强一致性（strong consistency）更弱，但比最终一致性（eventually consistency）更强的保证。当读取数据时，您可能会看到一个旧值，但是再次查询时不会看到更旧的值

实现单调读的一种方式是确保每个用户总是从同一个副本进行读取（不同的用户可以从不同的副本读取），比如可以基于用户ID的散列值来选择副本。

一致前缀读

假设两个数据有很强的前因后果，而某些分区的复制速度慢于其他分区，那么观察者就有可能看到问题（因）之前就看到答案（果）

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

复制延迟的解决方案

如果应用程序开发人员不必担心微妙的复制问题，并可以信赖他们的数据库“做了正确的事情”，那该多好呀。这就是事务（transaction）存在的原因：数据库通过事务提供强大的保证，所以应用程序可以更加简单。

单节点事务已经存在了很长时间。然而在走向分布式（复制和分区）数据库时，许多系统放弃了事务。

多主复制

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

如果允许多个节点接受写入，处理写入的每个节点都必须将该数据更改转发给所有其他节点，这称为多主复制， 在这种情况下，每个领导者同时扮演其他领导者的追随者。

多领导者复制如何处理写入冲突

如果应用程序可以确保特定记录的所有写入都通过同一个领导者，那么冲突就不会发生。

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

给每个写入一个唯一的ID（例如，一个时间戳，一个长的随机数，一个UUID或者一个键和值的哈希），挑选最高ID的写入作为胜利者，并丢弃其他写入。如果使用时间戳，这种技术被称为最后写入胜利（LWW, last write wins）。虽然这种方法很流行，但是很容易造成数据丢失

多主复制拓扑

复制拓扑描述写入从一个节点传播到另一个节点的通信路径。有环形、星型、全部到全部

最普遍的拓扑是全部到全部，其中每个领导者将其写入每个其他领导。默认情况下，MySQL仅支持环形拓扑（circular topology），其中每个节点接收来自一个节点的写入，并将这些写入（加上自己的任何写入）转发给另一个节点。

为了防止无限复制循环，每个节点被赋予一个唯一的标识符，并且在复制日志中，每个写入都被标记了所有已经通过的节点的标识符。当一个节点收到用自己的标识符标记的数据更改时，该数据更改将被忽略，因为节点知道它已经被处理。

无主复制

我们在本章到目前为止所讨论的复制方法 ——单主复制、多主复制——都是这样的想法：客户端向一个主库发送写请求，而数据库系统负责将写入复制到其他副本。主库决定写入的顺序，而从库按相同顺序应用主库的写入。

一些数据存储系统采用不同的方法，放弃主库的概念，并允许任何副本直接接受来自客户端的写入。最早的一些的复制数据系统是无领导的（leaderless）

当节点故障时写入数据库

当一个客户端从数据库中读取数据时，它不仅仅发送它的请求到一个副本：读请求也被并行地发送到多个节点。

客户可能会从不同的节点获得不同的响应。即来自一个节点的最新值和来自另一个节点的陈旧值（可能节点故障后重新联机了）。版本号用于确定哪个值更新。

读修复和反熵

读修复（Read repair）

当客户端并行读取多个节点时，它可以检测到任何陈旧的响应。例如，用户获得了来自副本3的版本值6和来自副本1和2的版本值7。客户端发现副本3具有陈旧值，于是将新值（版本值7）写回副本3。这种方法适用于频繁读的值。

反熵过程（Anti-entropy process）

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

读写的法定人数

如果有n个副本，每个写入必须由w个节点确认才算成功，每个读取必须查询r个节点，才能被认为是成功的，

只要$w + r> n$，我们期望在读取时获得最新的值，因为r个读取中至少有一个节点是最新的。遵循这些r值，w值的读写称为法定人数（quorum）的读和写。

第六章：分区

对于非常大的数据集,或非常高的吞吐量，仅仅进行复制是不够的：我们需要将数据进行分区（partitions），也称为分片（sharding）

上文中的分区(partition),在MongoDB,Elasticsearch和Solr Cloud中被称为分片(shard),在HBase中称之为区域(Region)，Bigtable中则是 表块（tablet），Cassandra和Riak中是虚节点（vnode), Couchbase中叫做虚桶(vBucket)。但是分区(partition) 是约定俗成的叫法。

分区主要是为了可扩展性。不同的分区可以放在不共享集群中的不同节点上。因此，大数据集可以分布在多个磁盘上，并且查询负载可以分布在多个处理器上。

分区与复制

分区通常与复制结合使用，使得每个分区的副本存储在多个节点上。 这意味着，即使每条记录属于一个分区，它仍然可以存储在多个不同的节点上以获得容错能力。

一个节点可能存储多个分区。每个分区领导者(主)被分配给一个节点，追随者(从)被分配给其他节点。 每个节点可能是某些分区的领导者，同时是其他分区的追随者。

理解：节点是物理的，分区是逻辑的。一个节点可能有多个分区，其中一些是分区的领导者，其中一些是分区的追随者。

键值数据的分区

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

如果分区是不公平的，一些分区比其他分区有更多的数据或查询，我们称之为偏斜（skew）。数据偏斜的存在使分区效率下降很多。在极端的情况下，所有的负载可能压在一个分区上，其余9个节点空闲的，瓶颈落在这一个繁忙的节点上。不均衡导致的高负载的分区被称为热点（hot spot）。

假设您有一个简单的键值数据模型，总是通过其主键访问记录。例如，在一本老式的纸质百科全书中，你可以通过标题来查找一个条目，由于所有条目按字母顺序排序，因此您可以快速找到您要查找的条目。

一种分区的方法是为每个分区指定一块连续的键范围（从最小值到最大值）。如果知道范围之间的边界，则可以轻松确定哪个分区包含某个值。如果您还知道分区所在的节点，那么可以直接向相应的节点发出请求（对于百科全书而言，就像从书架上选取正确的书籍）。然而，Key Range分区的缺点是某些特定的访问模式会导致热点。

根据键的散列分区

由于偏斜和热点的风险，许多分布式数据存储使用散列函数来确定给定键的分区。

一旦你有一个合适的键散列函数，你可以为每个分区分配一个散列范围（而不是键的范围），每个通过哈希散列落在分区范围内的键将被存储在该分区中。

这种技术擅长在分区之间分配键。分区边界可以是均匀间隔的，也可以是伪随机选择的（在这种情况下，该技术有时也被称为一致性哈希（consistent hashing））。

不幸的是，通过使用Key散列进行分区，我们失去了键范围分区的一个很好的属性：高效执行范围查询的能力，因为顺序性丢失了。

分区再平衡

随着时间的推移，数据库会有各种变化。

  • 查询吞吐量增加，所以您想要添加更多的CPU来处理负载。
  • 数据集大小增加，所以您想添加更多的磁盘和RAM来存储它。
  • 机器出现故障，其他机器需要接管故障机器的责任。

所有这些更改都需要数据和请求从一个节点移动到另一个节点。 将负载从集群中的一个节点向另一个节点移动的过程称为再平衡（reblancing）。

反面教材：hash mod N

模$N$方法的问题是，如果节点数量N发生变化，大多数密钥将需要从一个节点移动到另一个节点。例如，假设$hash(key)=123456$。如果最初有10个节点，那么这个键一开始放在节点6上（因为$123456\ mod\ 10 = 6$）。当您增长到11个节点时，密钥需要移动到节点3（$123456\ mod\ 11 = 3$），当您增长到12个节点时，需要移动到节点0（$123456\ mod\ 12 = 0$）。这种频繁的举动使得重新平衡过于昂贵。

固定数量的分区

创建比节点更多的分区，为每个节点分配多个分区。只有分区在节点之间的移动。分区的数量不会改变，键所指定的分区也不会改变。唯一改变的是分区所在的节点。

如果数据集的总大小难以预估（例如，如果它开始很小，但随着时间的推移可能会变得更大），选择正确的分区数是困难的。由于每个分区包含了总数据量固定比率的数据，因此每个分区的大小与集群中的数据总量成比例增长。如果分区非常大，再平衡和从节点故障恢复变得昂贵。但是，如果分区太小，会产生太多的开销。

动态分区

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

每个分区分配给一个节点，每个节点可以处理多个分区，就像固定数量的分区一样。大型分区拆分后，可以将其中的一半转移到另一个节点，以平衡负载。在HBase中，分区文件的传输通过HDFS（底层分布式文件系统）来实现

动态分区的一个优点是分区数量适应总数据量。如果只有少量的数据，少量的分区就足够了，所以开销很小;如果有大量的数据，每个分区的大小被限制在一个可配置的最大值

请求路由

当客户想要发出请求时，如何知道要连接哪个节点？随着分区重新平衡，分区对节点的分配也发生变化。为了回答这个问题，需要有人知晓这些变化：如果我想读或写键“foo”，需要连接哪个IP地址和端口号？

这个问题可以概括为 服务发现(service discovery) ，它不仅限于数据库。任何可通过网络访问的软件都有这个问题。

有几种不同的解决方案：

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

许多分布式数据系统都依赖于一个独立的协调服务，比如ZooKeeper跟踪集群元数据。 每个节点在ZooKeeper中注册自己，ZooKeeper维护分区到节点的可靠映射。 其他参与者（如路由层或分区感知客户端）可以在ZooKeeper中订阅此信息。 只要分区分配发生的改变，或者集群中添加或删除了一个节点，ZooKeeper就会通知路由层使路由信息保持最新状态。

第七章：事务

事务的棘手概念

ACID的含义

ACID代表原子性（Atomicity），一致性（Consistency），隔离性（Isolation）和持久性（Durability）

不符合ACID标准的系统有时被称为BASE，它代表基本可用性（Basically Available），软状态（Soft State）和最终一致性（Eventual consistency）

原子性（Atomicity）

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

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

all-or-nothing

一致性（Consistency）

一致性的概念是，对数据的一组特定陈述必须始终成立。即不变量（invariants）

一致性（在ACID意义上）是应用程序的属性。应用可能依赖数据库的原子性和隔离属性来实现一致性

隔离性（Isolation）

大多数数据库都会同时被多个客户端访问。如果它们各自读写数据库的不同部分，这是没有问题的，但是如果它们访问相同的数据库记录，则可能会遇到并发问题（竞争条件（race conditions））。

隔离性意味着，同时执行的事务是相互隔离的：它们不能相互冒犯。传统的数据库教科书将隔离性形式化为可序列化（Serializability），这意味着每个事务可以假装它是唯一在整个数据库上运行的事务。数据库确保当事务已经提交时，结果与它们按顺序运行（一个接一个）是一样的，尽管实际上它们可能是并发运行的

持久性（Durability）

数据库系统的目的是，提供一个安全的地方存储数据，而不用担心丢失。持久性 是一个承诺，即一旦事务成功完成，即使发生硬件故障或数据库崩溃，写入的任何数据也不会丢失。

弱隔离级别

数据库一直试图通过提供事务隔离（transaction isolation） 来隐藏应用程序开发者的并发问题。从理论上讲，隔离可以通过假装没有并发发生，让你的生活更加轻松：可序列化（serializable） 的隔离等级意味着数据库保证事务的效果与连续运行（即一次一个，没有任何并发）是一样的。

读未提交（Read uncommitted）

它可以防止脏写，但不防止脏读

脏读（dirty reads）：一个事务已经将一些数据写入数据库，但事务还没有提交或中止，而另一个事务可以看到未提交的数据。

为什么要防止脏读，有几个原因：

  • 如果事务需要更新多个对象，脏读取意味着另一个事务可能会只看到一部分更新。看到处于部分更新状态的数据库会让用户感到困惑，并可能导致其他事务做出错误的决定。
  • 如果事务中止，则所有写入操作都需要回滚。如果数据库允许脏读，那就意味着一个事务可能会看到稍后需要回滚的数据，即从未实际提交给数据库的数据。

脏写（dirty writes）：后面的写入会覆盖一个事务尚未提交的写

读已提交（Read Committed）

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

读已提交是一个非常流行的隔离级别。

如何防止脏写：

最常见的情况是，数据库通过使用行锁（row-level lock） 来防止脏写：当事务想要修改特定对象（行或文档）时，它必须首先获得该对象的锁。然后必须持有该锁直到事务被提交或中止。一次只有一个事务可持有任何给定对象的锁；如果另一个事务要写入同一个对象，则必须等到第一个事务提交或中止后，才能获取该锁并继续。这种锁定是读已提交模式（或更强的隔离级别）的数据库自动完成的。

如何防止脏读：

  • 也用行锁，任何想要读取对象的事务来简单地获取该锁，然后在读取之后立即再次释放该锁。这能确保不会读取进行时，对象不会在脏的状态，有未提交的值（因为在那段时间锁会被写入该对象的事务持有）。但是性能差。
  • 对于写入的每个对象，数据库都会记住旧值。 当事务正在进行时，任何其他读取对象的事务都会拿到旧值。 只有当持有行锁的事务的新值提交后，事务才会切换到读取新值。
可重复读（repeatable read）

读已提交的隔离级别并不能解决更高的并发错误，比如在一次事务中，同样的两次查询的结果是不一样的，这种异常叫做不可重复读（nonrepeatable read）

快照隔离（snapshot isolation）

每个事务都从数据库的一致快照（consistent snapshot） 中读取，即事务可以看到事务开始时在数据库中提交的所有数据。即使这些数据随后被另一个事务更改，每个事务也只能看到该特定时间点的旧数据。

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

从性能的角度来看，快照隔离的一个关键原则是：读不阻塞写，写不阻塞读。这允许数据库在处理一致性快照上的长时间查询时，可以正常地同时处理写入操作。且两者间没有任何锁定争用。

由于历史原因，快照隔离≈可重复读，都是一种隔离级别

MVCC实现快照隔离：数据库必须可能保留一个对象的几个不同的提交版本，因为各种正在进行的事务可能需要看到数据库在不同的时间点的状态。因为它并排维护着多个版本的对象，所以这种技术被称为多版本并发控制（MVCC, multi-version concurrentcy control）。

防止丢失更新

并发的写入事务之间还有其他几种有趣的冲突。其中最着名的是丢失更新（lost update） 问题

如果应用从数据库中读取一些值，修改它并写回修改的值（读取-修改-写入序列），则可能会发生丢失更新的问题。如果两个事务同时执行，则其中一个的修改可能会丢失，因为第二个写入的内容并没有包括第一个事务的修改

原子写

许多数据库提供了原子更新操作，例如，下面的指令在大多数关系数据库中是并发安全的：

1
UPDATE counters SET value = value + 1 WHERE key = 'foo';

原子操作通常通过在读取对象时，获取其上的排它锁来实现。以便更新完成之前没有其他事务可以读取它。这种技术有时被称为游标稳定性（cursor stability）

幻读

一个事务中的写入改变另一个事务的搜索查询的结果，被称为幻读，比如用户两次查询的结果不一致，好像产生幻觉一样

可序列化（Serializability）

可序列化（Serializability）隔离通常被认为是最强的隔离级别。它保证即使事务可以并行执行，最终的结果也是一样的，就好像它们没有任何并发性，连续挨个执行一样。因此数据库保证，如果事务在单独运行时正常运行，则它们在并发运行时继续保持正确 —— 换句话说，数据库可以防止所有可能的竞争条件。

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

  • 字面意义上地串行顺序执行事务
  • 两相锁定（2PL, two-phase locking），几十年来唯一可行的选择。
  • 乐观并发控制技术，例如可序列化的快照隔离（serializable snapshot isolation）
真的串行执行

避免并发问题的最简单方法就是完全不要并发：在单个线程上按顺序一次只执行一个事务。这样做就完全绕开了检测/防止事务间冲突的问题

  • 每个事务都必须小而快，只要有一个缓慢的事务，就会拖慢所有事务处理。
  • 仅限于活跃数据集可以放入内存的情况。很少访问的数据可能会被移动到磁盘，但如果需要在单线程执行的事务中访问，系统就会变得非常慢。
  • 写入吞吐量必须低到能在单个CPU核上处理，如若不然，事务需要能划分至单个分区，且不需要跨分区协调。
  • 跨分区事务是可能的，但是它们的使用程度有很大的限制。
两阶段锁定（2PL）

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

2PL用于MySQL（InnoDB）和SQL Server中的可序列化隔离级别

2PL不是2PC！

之前我们看到：锁通常用于防止脏写，如果两个事务同时尝试写入同一个对象，则锁可确保第二个写入必须等到第一个写入完成事务（中止或提交），然后才能继续。

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

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

在2PL中，写入不仅会阻塞其他写入，也会阻塞读，反之亦然。快照隔离使得读不阻塞写，写也不阻塞读，这是2PL和快照隔离之间的关键区别。

另一方面，因为2PL提供了可序列化的性质，它可以防止丢失更新和写入偏差。

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

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

由于使用了这么多的锁，因此很可能会发生：事务A等待事务B释放它的锁，反之亦然。这种情况叫做死锁（Deadlock）。数据库会自动检测事务之间的死锁，并中止其中一个，以便另一个继续执行。被中止的事务需要由应用程序重试。

谓词锁

在会议室预订的例子中，这意味着如果一个事务在某个时间窗口内搜索了一个房间的现有预订，则另一个事务不能同时插入或更新同一时间窗口与同一房间的另一个预订 （可以同时插入其他房间的预订，或在不影响另一个预定的条件下预定同一房间的其他时间段）。

我们需要一个谓词锁（predicate lock）。它类似于前面描述的共享/排它锁，但不属于特定的对象（例如，表中的一行），它属于所有符合某些搜索条件的对象。

谓词锁限制访问，如下所示：

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

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

这种方法能够有效防止幻读和写入偏差。索引范围锁并不像谓词锁那样精确（它们可能会锁定更大范围的对象，而不是维持可串行化所必需的范围），但是由于它们的开销较低，所以是一个很好的折衷。

序列化快照隔离（SSI）

一方面，我们实现了性能不好（2PL）或者扩展性不好（串行执行）的可序列化隔离级别。另一方面，我们有性能良好的弱隔离级别，但容易出现各种竞争条件（丢失更新，写入偏差，幻读等）。序列化的隔离级别和高性能是从根本上相互矛盾的吗？

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

第八章：分布式系统的麻烦

故障与部分失效

在分布式系统中，尽管系统的其他部分工作正常，但系统的某些部分可能会以某种不可预知的方式被破坏。这被称为部分失效（partial failure）。难点在于部分失效是不确定性的（nonderterministic）：如果你试图做任何涉及多个节点和网络的事情，它有时可能会工作，有时会出现不可预知的失败

不可靠的网络

互联网和数据中心（通常是以太网）中的大多数内部网络都是异步分组网络（asynchronous packet networks）。在这种网络中，一个节点可以向另一个节点发送一个消息（一个数据包），但是网络不能保证它什么时候到达，或者是否到达。如果您发送请求并期待响应，则很多事情可能会出错

  • 请求可能已经丢失（可能有人拔掉了网线）。
  • 请求可能正在排队，稍后将交付（也许网络或收件人超载）。
  • 远程节点可能已经失效（可能是崩溃或关机）。
  • 远程节点可能暂时停止了响应（可能会遇到长时间的垃圾回收暂停），但稍后会再次响应。
  • 远程节点可能已经处理了请求，但是网络上的响应已经丢失（可能是网络交换机配置错误）。
  • 远程节点可能已经处理了请求，但是响应已经被延迟，并且稍后将被传递（可能是网络或者你自己的机器过载）。

处理这个问题的通常方法是超时（Timeout）：在一段时间之后放弃等待，并且认为响应不会到达。但是，当发生超时时，你仍然不知道远程节点是否收到了请求（如果请求仍然在某个地方排队，那么即使发件人已经放弃了该请求，仍然可能会将其发送给收件人）。

电话网络中的电路与TCP连接有很大不同：电路是固定数量的预留带宽，在电路建立时没有其他人可以使用，而TCP连接的数据包机会性地使用任何可用的网络带宽。您可以给TCP一个可变大小的数据块（例如，一个电子邮件或一个网页），它会尽可能在最短的时间内传输它。 TCP连接空闲时，不使用任何带宽

如果数据中心网络和互联网是电路交换网络，那么在建立电路时就可以建立一个保证的最大往返时间。但是，它们并不是：以太网和IP是分组交换协议，这些协议可以从排队中获得，从而使网络无限延迟。这些协议没有电路的概念。

不可靠的时钟

在分布式系统中，时间是一件棘手的事情，因为通信不是即时的：消息通过网络从一台机器传送到另一台机器需要时间。收到消息的时间总是晚于发送的时间，但是由于网络中的可变延迟，我们不知道多少时间。这个事实有时很难确定在涉及多台机器时发生事情的顺序。

而且，网络上的每台机器都有自己的时钟，这是一个实际的硬件设备：通常是石英晶体振荡器。这些设备不是完全准确的，所以每台机器都有自己的时间概念，可能比其他机器稍快或更慢。可以在一定程度上同步时钟：最常用的机制是网络时间协议（NTP），它允许根据一组服务器报告的时间来调整计算机时钟。服务器则从更精确的时间源（如GPS接收机）获取时间。

时钟

时钟是您直观地了解时钟的依据：它根据某个日历（也称为挂钟时间（wall-clock time））返回当前日期和时间。例如，Linux上的clock_gettime(CLOCK_REALTIME)和Java中的System.currentTimeMillis()返回自epoch（1970年1月1日 午夜 UTC，格里高利历）以来的秒数（或毫秒），根据公历日历，不包括闰秒。

单调钟

单调钟适用于测量持续时间（时间间隔），例如超时或服务的响应时间：Linux上的clock_gettime(CLOCK_MONOTONIC)，和Java中的System.nanoTime()都是单调时钟。这个名字来源于他们保证总是前进的事实（而时钟可以及时跳回）。

你可以在某个时间点检查单调钟的值，做一些事情，且稍后再次检查它。这两个值之间的差异告诉你两次检查之间经过了多长时间。但单调钟的绝对值是毫无意义的：它可能是计算机启动以来的纳秒数，或类似的任意值。特别是比较来自两台不同计算机的单调钟的值是没有意义的，因为它们并不是一回事。

在分布式系统中，使用单调钟测量经过时间（elapsed time）（比如超时）通常很好，因为它不假定不同节点的时钟之间存在任何同步，并且对测量的轻微不准确性不敏感。

时钟同步与准确性

单调钟不需要同步，但是时钟需要根据NTP服务器或其他外部时间源来设置才能有用。不幸的是，我们获取时钟的方法并不像你所希望的那样可靠或准确——硬件时钟和NTP可能会变幻莫测。

计算机中的石英钟不够精确：它会漂移（drifts）（运行速度快于或慢于预期）。时钟漂移取决于机器的温度。

有序事件的时间戳

因为采用最后写入为准（LLW）的策略，两个节点的时间有可能不是同步的，有可能出现实际上先写的被认为是后写。

比如，尽管通过保留最“最近”的值并放弃其他值来解决冲突是很诱惑人的（LWW），但是要注意，“最近”的定义取决于本地的时钟，这很可能是不正确的。即使用频繁同步的NTP时钟，一个数据包也可能在时间戳100毫秒（根据发送者的时钟）时发送，并在时间戳99毫秒（根据接收者的时钟）处到达——看起来好像数据包在发送之前已经到达，这是不可能的。

时钟读数存在置信区间

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

因此，将时钟读数视为一个时间点是没有意义的——它更像是一段时间范围：例如，一个系统可能以95％的置信度认为当前时间处于本分钟内的第10.3秒和10.5秒之间，它可能没法比这更精确了【58】。如果我们只知道±100毫秒的时间，那么时间戳中的微秒数字部分基本上是没有意义的。

全局快照的同步时钟

快照隔离最常见的实现需要单调递增的事务ID。如果写入比快照晚（即，写入具有比快照更大的事务ID），则该写入对于快照事务是不可见的。在单节点数据库上，一个简单的计数器就足以生成事务ID。

但是当数据库分布在许多机器上，也许可能在多个数据中心中时，由于需要协调，（跨所有分区）全局单调递增的事务ID可能很难生成。事务ID必须反映因果关系：如果事务B读取由事务A写入的值，则B必须具有比A更大的事务ID，否则快照就无法保持一致。在有大量的小规模、高频率的事务情景下，在分布式系统中创建事务ID成为一个站不住脚的瓶颈

Spanner以这种方式实现跨数据中心的快照隔离【59，60】。它使用TrueTime API报告的时钟置信区间，并基于以下观察结果：如果您有两个置信区间，每个置信区间包含最早和最近可能的时间戳（ $A = [A{earliest}, A{latest}]$， $B=[B{earliest}, B{latest}] $），这两个区间不重叠（即：$A{earliest} < A{latest} < B{earliest} < B{latest}$），那么B肯定发生在A之后——这是毫无疑问的。只有当区间重叠时，我们才不确定A和B发生的顺序。

为了确保事务时间戳反映因果关系，在提交读写事务之前，Spanner在提交读写事务时，会故意等待置信区间长度的时间。通过这样，它可以确保任何可能读取数据的事务处于足够晚的时间，因此它们的置信区间不会重叠。

响应时间保证

某些软件的运行环境要求很高，不能在特定时间内响应可能会导致严重的损失：飞机主控计算机，火箭，机器人，汽车和其他物体的计算机必须对其传感器输入做出快速而可预测的响应。在这些系统中，软件必须有一个特定的截止时间（deadline），如果截止时间不满足，可能会导致整个系统的故障。这就是所谓的硬实时（hard real-time）系统。

“实时”与“高性能”不一样——事实上，实时系统可能具有较低的吞吐量，因为他们必须优先考虑及时响应高于一切

知识、真相与谎言

真理由多数所定义

设想一个具有不对称故障的网络：一个节点能够接收发送给它的所有消息，但是来自该节点的任何传出消息被丢弃或延迟。即使该节点运行良好，并且正在接收来自其他节点的请求，其他节点也无法听到其响应。经过一段时间后，其他节点宣布它已经死亡，因为他们没有听到节点的消息。这种情况就像梦魇一样：半断开（semi-disconnected）的节点被拖向墓地，敲打尖叫道“我没死！” ——但是由于没有人能听到它的尖叫，葬礼队伍继续以坚忍的决心继续行进。

防护令牌

当使用锁或租约来保护对某些资源的访问时，需要确保一个被误认为自己是“天选者”的节点不能中断系统的其它部分。实现这一目标的一个相当简单的技术就是防护（fencing）

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

如果将ZooKeeper用作锁定服务，则可将事务标识zxid或节点版本cversion用作屏蔽令牌。由于它们保证单调递增

拜占庭将军问题

拜占庭将军问题是所谓“两将军问题”的概括【78】，它想象两个将军需要就战斗计划达成一致的情况。由于他们在两个不同的地点建立了营地，他们只能通过信使进行沟通，信使有时会被延迟或丢失（就像网络中的信息包一样）

当一个系统在部分节点发生故障、不遵守协议、甚至恶意攻击、扰乱网络时仍然能继续正确工作，称之为拜占庭容错（Byzantine fault-tolerant）的

第九章：一致性与共识

现在我们将继续沿着同样的路线前进，寻求可以让应用忽略分布式系统部分问题的抽象概念。例如，分布式系统最重要的抽象之一就是共识（consensus）：就是让所有的节点对某件事达成一致。

一旦达成共识，应用可以将其用于各种目的。例如，假设你有一个单主复制的数据库。如果主库挂点，并且需要故障切换到另一个节点，剩余的数据库节点可以使用共识来选举新的领导者。例如，如果两个节点都认为自己是领导者，这种情况被称为脑裂（split brain），且经常导致数据丢失。正确实现共识有助于避免这种问题。

一致性保证

大多数复制的数据库至少提供了最终一致性，这意味着如果你停止向数据库写入数据并等待一段不确定的时间，那么最终所有的读取请求都会返回相同的值。换句话说，不一致性是暂时的，最终会自行解决（假设网络中的任何故障最终都会被修复）。最终一致性的一个更好的名字可能是收敛（convergence），因为我们预计所有的复本最终会收敛到相同的值

分布式一致性模型和我们之前讨论的事务隔离级别的层次结构有一些相似之处。尽管两者有一部分内容重叠，但它们大多是无关的问题：事务隔离主要是为了，避免由于同时执行事务而导致的竞争状态，而分布式一致性主要关于，面对延迟和故障时，如何协调副本间的状态。

线性一致性

在最终一致的数据库，如果你在同一时刻问两个不同副本相同的问题，可能会得到两个不同的答案。这很让人困惑。如果数据库可以提供只有一个副本的假象，那么事情就简单太多了。那么每个客户端都会有相同的数据视图，且不必担心复制滞后了。

这就是线性一致性（linearizability）背后的想法（也称为原子一致性（atomic consistency），强一致性（strong consistency），立即一致性（immediate consistency）或外部一致性（external consistency ））

维护数据的单个副本的错觉是指，系统能保障读到的值是最近的，最新的，而不是来自陈旧的缓存或副本。换句话说，线性一致性是一个新鲜度保证（recency guarantee）。

如果读取（与写入同时发生时）可能返回旧值或新值，则称该寄存器为常规寄存器（regular register）

线性一致性与可序列化

线性一致性容易和可序列化相混淆，因为两个词似乎都是类似“可以按顺序排列”的东西。但它们是两种完全不同的保证，区分两者非常重要：

  • 可序列化（Serializability）是事务的隔离属性，每个事务可以读写多个对象（行，文档，记录）。它确保事务的行为，与它们按照某种顺序依次执行的结果相同（每个事务在下一个事务开始之前运行完成）。这种执行顺序可以与事务实际执行的顺序不同。
  • 线性一致性（Linearizability）是读取和写入寄存器（单个对象）的新鲜度保证。它不会将操作组合为事务，因此它也不会阻止写偏差等问题

一个数据库可以提供可串行性和线性一致性，这种组合被称为严格的可串行性或强的单副本强可串行性（strong-1SR）

锁定和领导选举

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

诸如Apache ZooKeeper 和etcd 之类的协调服务通常用于实现分布式锁和领导者选举。它们使用一致性算法，以容错的方式实现线性一致的操作

约束和唯一性保证

唯一性约束在数据库中很常见：例如，用户名或电子邮件地址必须唯一标识一个用户，而在文件存储服务中，不能有两个具有相同路径和文件名的文件。如果要在写入数据时强制执行此约束（例如，如果两个人试图同时创建一个具有相同名称的用户或文件，其中一个将返回一个错误），则需要线性一致性。

这种情况实际上类似于一个锁：当一个用户注册你的服务时，可以认为他们获得了所选用户名的“锁定”。该操作与原子性的比较与设置非常相似：将用户名赋予声明它的用户，前提是用户名尚未被使用。

实现线性一致的系统

单主复制（可能线性一致）：

在具有单主复制功能的系统中，主库具有用于写入的数据的主副本，而追随者在其他节点上保留数据的备份副本。如果从主库或同步更新的从库读取数据，它们可能（protential）是线性一致性的。然而，并不是每个单主数据库都是实际线性一致性的。使用异步复制，故障切换时甚至可能会丢失已提交的写入，这就不是线性一致性了。

共识算法（线性一致）：

一些在本章后面讨论的共识算法，与单领导者复制类似。然而，共识协议包含防止脑裂和陈旧副本的措施。由于这些细节，共识算法可以安全地实现线性一致性存储。例如，Zookeeper 和etcd

多主复制（非线性一致）：

具有多主程序复制的系统通常不是线性一致的，因为它们同时在多个节点上处理写入，并将其异步复制到其他节点。因此，它们可能会产生冲突的写入，需要解析

无主复制（也许不是线性一致的）：

对于无领导者复制的系统，有时候人们会声称通过要求法定人数读写（ $w + r> n$ ）可以获得“强一致性”。这取决于法定人数的具体配置，以及强一致性如何定义（通常不完全正确）。

基于时钟（例如，在Cassandra中）的“最后写入胜利”冲突解决方法几乎可以确定是非线性的，由于时钟偏差，不能保证时钟的时间戳与实际事件顺序一致。松散的法定人数也破坏了线性一致的可能性

线性一致性的代价

在单主配置的条件下，如果数据中心之间的网络被中断，则连接到从库数据中心的客户端无法联系到主库，因此它们无法对数据库执行任何写入，也不能执行任何线性一致的读取。它们仍能从从库读取，但结果可能是陈旧的（非线性一致）。如果应用需要线性一致的读写，却又位于与主库网络中断的数据中心，则网络中断将导致这些应用不可用。

如果客户端可以直接连接到主库所在的数据中心，这就不是问题了，哪些应用可以继续正常工作。但直到网络链接修复之前，只能访问从库数据中心的客户端会中断运行。

CAP定理（这是一个定义不严格的定理）

问题面临的权衡如下：

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

CAP有时以这种面目出现：一致性，可用性和分区容错性：三者只能择其二。不幸的是这种说法很有误导性，因为网络分区是一种错误，所以它并不是一个选项：不管你喜不喜欢它都会发生。

在网络正常工作的时候，系统可以提供一致性（线性一致性）和整体可用性。发生网络故障时，你必须在线性一致性和整体可用性之间做出选择。

顺序保证

顺序（ordering）这一主题在本书中反复出现，这表明它可能是一个重要的基础性概念。让我们简要回顾一下其它顺序曾经出现过的上下文：

  • 在第5章中我们看到，领导者在单主复制中的主要目的就是，在复制日志中确定写入顺序（order of write）——也就是从库应用这些写入的顺序。如果不存在一个领导者，则并发操作可能导致冲突
  • 在第7章中讨论的可序列化，是关于事务表现的像按某种序列顺序（some sequential order）执行的保证。它可以通过字面意义上地序列顺序（serial order）执行事务来实现，或者通过允许并行执行，同时防止序列化冲突来实现（通过锁或中止事务）
  • 在第8章讨论过的在分布式系统中使用时间戳和时钟是另一种将顺序引入无序世界的尝试，例如，确定两个写入操作哪一个更晚发生。
顺序与因果

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

因果关系对事件施加了一种顺序：因在果之前；消息发送在消息收取之前。而且就像现实生活中一样，一件事会导致另一件事：某个节点读取了一些数据然后写入一些结果，另一个节点读取其写入的内容，并依次写入一些其他内容，等等。这些因果依赖的操作链定义了系统中的因果顺序，即，什么在什么之前发生。

如果一个系统服从因果关系所规定的顺序，我们说它是因果一致（causally）的。例如，快照隔离提供了因果一致性：当你从数据库中读取到一些数据时，你一定还能够看到其因果前驱（假设在此期间这些数据还没有被删除）。

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

线性一致性隐含着（implies）因果关系：任何线性一致的系统都能正确保持因果性

使系统线性一致可能会损害其性能和可用性，尤其是在系统具有严重的网络延迟的情况下（例如，如果系统在地理上散布）。出于这个原因，一些分布式数据系统已经放弃了线性一致性，从而获得更好的性能，但它们用起来也更为困难。

好消息是存在折衷的可能性。线性一致性并不是保持因果性的唯一途径 —— 还有其他方法。一个系统可以是因果一致的，而无需承担线性一致带来的性能折损（尤其对于CAP定理不适用的情况）。

在许多情况下，看上去需要线性一致性的系统，实际上需要的只是因果一致性，因果一致性可以更高效地实现。

序列号顺序

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

但还有一个更好的方法：我们可以使用序列号（sequence nunber）或时间戳（timestamp）来排序事件。时间戳不一定来自时钟（或物理时钟，存在许多问题）。它可以来自一个逻辑时钟（logical clock），这是一个用来生成标识操作的数字序列的算法，典型实现是使用一个每次操作自增的计数器。

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

兰伯特时间戳

实际上有一个简单的方法来产生与因果关系一致的序列号。它被称为兰伯特时间戳：每个节点都有一个唯一标识符，和一个保存自己执行操作数量的计数器。 兰伯特时间戳就是两者的简单组合：（计数器，节点ID）$(counter, node ID)$。两个节点有时可能具有相同的计数器值，但通过在时间戳中包含节点ID，每个时间戳都是唯一的。

兰伯特时间戳与物理时间时钟没有任何关系，但是它提供了一个全序：如果你有两个时间戳，则计数器值大者是更大的时间戳。如果计数器值相同，则节点ID越大的，时间戳越大。

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

全序广播

如果吞吐量超出单个主库的处理能力，这种情况下如何扩展系统；以及，如果主库失效（“处理节点宕机”），如何处理故障切换。在分布式系统文献中，这个问题被称为全序广播（total order broadcast）或原子广播（atomic broadcast），注意这里的原子与ACID事务的原子性没有任何关系

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

  • 可靠交付（reliable delivery）：没有消息丢失：如果消息被传递到一个节点，它将被传递到所有节点。
  • 全序交付（totally ordered delivery）：消息以相同的顺序传递给每个节点。

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

分布式事务与共识

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

领导选举：

在单主复制的数据库中，所有节点需要就哪个节点是领导者达成一致。如果一些节点由于网络故障而无法与其他节点通信，则可能会对领导权的归属引起争议。在这种情况下，共识对于避免错误的故障切换非常重要。错误的故障切换会导致两个节点都认为自己是领导者（脑裂）。如果有两个领导者，它们都会接受写入，它们的数据会发生分歧，从而导致不一致和数据丢失。

原子提交：

在支持跨多节点或跨多分区事务的数据库中，一个事务可能在某些节点上失败，但在其他节点上成功。如果我们想要维护事务的原子性（就ACID而言），我们必须让所有节点对事务的结果达成一致：要么全部中止/回滚（如果出现任何错误），要么它们全部提交（如果没有出错）。这就是原子提交（atomic commit）问题。

在本节中，我们将首先更详细地研究原子提交问题。具体来说，我们将讨论两阶段提交（2PC, two-phase commit）算法，这是解决原子提交问题最常见的办法，并在各种数据库、消息队列和应用服务器中实现。事实证明2PC是一种共识算法，但不是一个非常好的算法。

通过对2PC的学习，我们将继续努力实现更好的一致性算法，比如ZooKeeper（Zab）和etcd（Raft）中使用的算法。

2PC

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

事务提交必须是不可撤销的

两阶段提交（two-phase commit）是一种用于实现跨多个节点的原子事务提交的算法，即确保所有节点提交或所有节点中止。 它是分布式数据库中的经典算法。

2PC包括协调者（coordinator）与参与者（participants）。正常情况下，协调者通常以库的形式实现，也可以是单独的进程或服务。2PC事务以应用在多个数据库节点（参与者）上读写数据开始。

当应用准备提交时，协调者开始阶段 1 ：它发送一个准备（prepare）请求到每个节点，询问它们是否能够提交。

然后协调者会跟踪参与者的响应：

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

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

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

因此，该协议包含两个关键的“不归路”点：当参与者投票“是”时，它承诺它稍后肯定能够提交（尽管协调者可能仍然选择放弃）。一旦协调者做出决定，这一决定是不可撤销的。这些承诺保证了2PC的原子性。 （单节点原子提交将这两个事件混为一谈：将提交记录写入事务日志。）

回到婚姻的比喻，在说“我是”之前，你和你的新娘/新郎有中止这个事务的自由，通过回复 “没门！”（或者有类似效果的话）。然而在说了“我愿意”之后，你就不能撤回那个声明了。如果你说“我愿意”后晕倒了，没有听到司仪说“你们现在是夫妻了”，那也并不会改变事务已经提交的现实。当你稍后恢复意识时，可以通过查询司仪的全局事务ID状态来确定你是否已经成婚，或者你可以等待司仪重试下一次提交请求（因为重试将在你无意识期间一直持续）。

协调者失效

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

没有协调者的消息，参与者无法知道是提交还是放弃。原则上参与者可以相互沟通，找出每个参与者是如何投票的，并达成一致，但这不是2PC协议的一部分。
可以完成2PC的唯一方法是等待协调者恢复。这就是为什么协调者必须在向参与者发送提交或中止请求之前，将其提交或中止决定写入磁盘上的事务日志：协调者恢复后，通过读取其事务日志来确定所有存疑事务的状态。任何在协调者日志中没有提交记录的事务都会中止。因此，2PC的提交点归结为协调者上的常规单节点原子提交。

3PC

两阶段提交被称为阻塞（blocking）原子提交协议，因为存在2PC可能卡住并等待协调者恢复的情况。理论上，可以使一个原子提交协议变为非阻塞（nonblocking）的，以便在节点失败时不会卡住。但是让这个协议能在实践中工作并没有那么简单。

3PC作为2PC的替代方案，但是3PC假定网络延迟有界，节点响应时间有限，但在大多具有无限网络延迟的实际系统中，它并不能保证原子性

通常，非阻塞原子提交需要一个完美的故障检测器（perfect failure detector）—— 即一个可靠的机制来判断一个节点是否已经崩溃。在具有无限延迟的网络中，超时并不是一种可靠的故障检测机制，因为即使没有节点崩溃，请求也可能由于网络问题而超时。出于这个原因，2PC仍然被使用，尽管大家都清楚可能存在协调者故障的问题。

容错共识

非正式地，共识意味着让几个节点就某事达成一致。例如，如果有几个人同时（concurrently）尝试预订飞机上的最后一个座位，或剧院中的同一个座位，或者尝试使用相同的用户名注册一个帐户。共识算法可以用来确定这些互不相容（mutually incompatible）的操作中，哪一个才是赢家。

共识问题通常形式化如下：一个或多个节点可以提议（propose）某些值，而共识算法决定（decides）采用其中的某个值。在座位预订的例子中，当几个顾客同时试图订购最后一个座位时，处理顾客请求的每个节点可以提议正在服务的顾客的ID，而决定指明了哪个顾客获得了座位。

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

  • 一致同意（Uniform agreement）：没有两个节点的决定不同。
  • 完整性（Integrity）：没有节点决定两次。
  • 有效性（Validity）：如果一个节点决定了值 v ，则 v 由某个节点所提议。
  • 终止（Termination）：由所有未崩溃的节点来最终决定值。

一致同意和完整性属性定义了共识的核心思想：所有人都决定了相同的结果，一旦决定了，你就不能改变主意。有效性属性主要是为了排除平凡的解决方案：例如，无论提议了什么值，你都可以有一个始终决定值为null的算法。；该算法满足一致同意和完整性属性，但不满足有效性属性。

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

时代编号和法定人数

迄今为止所讨论的所有共识协议，在内部都以某种形式使用一个领导者，但它们并不能保证领导者是独一无二的。相反，它们可以做出更弱的保证：协议定义了一个时代编号（epoch number）（在Paxos中称为投票编号（ballot number），视图戳复制中的视图编号（view number），以及Raft中的任期号码（term number）），并确保在每个时代中，领导者都是唯一的。

每次当现任领导被认为挂掉的时候，节点间就会开始一场投票，以选出一个新领导。这次选举被赋予一个递增的时代编号，因此时代编号是全序且单调递增的。如果两个不同的时代的领导者之间出现冲突（也许是因为前任领导者实际上并未死亡），那么带有更高时代编号的领导说了算。

领导必须从法定人数（quorum）的节点中获取选票（参阅“读写的法定人数”）。对领导者想要做出的每一个决定，都必须将提议值发送给其他节点，并等待法定人数的节点响应并赞成提案。法定人数通常（但不总是）由多数节点组成。只有在没有意识到任何带有更高时代编号的领导者的情况下，一个节点才会投票赞成提议。

因此，我们有两轮投票：第一次是为了选出一位领导者，第二次是对领导者的提议进行表决。关键的洞察在于，这两次投票的法定人群必须相互重叠（overlap）：如果一个提案的表决通过，则至少得有一个参与投票的节点也必须参加过最近的领导者选举。因此，如果在一个提案的表决过程中没有出现更高的时代编号。那么现任领导者就可以得出这样的结论：没有发生过更高时代的领导选举，因此可以确定自己仍然在领导。然后它就可以安全地对提议值做出决定。

这一投票过程表面上看起来很像两阶段提交。最大的区别在于，2PC中协调者不是由选举产生的，而且2PC则要求所有参与者都投赞成票，而容错共识算法只需要多数节点的投票。而且，共识算法还定义了一个恢复过程，节点可以在选举出新的领导者之后进入一个一致的状态，确保始终能满足安全属性。这些区别正是共识算法正确性和容错性的关键。

共识的局限性

共识系统必须需要严格多数来运转，比如至少需要三个节点来容忍单节点故障，至少五个节点来容忍两个节点故障

共识系统通常依靠超时来检测失效的节点，但如果网络延迟经常变化，频繁的领导者选举会导致糟糕的性能，比如Raft已被证明在一条特定网络连接不可靠时，Raft会进入领导频繁二人转的局面

成员与协调服务

像ZooKeeper或etcd这样的项目通常被描述为“分布式键值存储”或“协调与配置服务”。这种服务的API看起来非常像数据库：你可以读写给定键的值，并遍历键。所以如果它们基本上算是数据库的话，为什么它们要把工夫全花在实现一个共识算法上呢？是什么使它们区别于其他任意类型的数据库？

ZooKeeper和etcd被设计为容纳少量完全可以放在内存中的数据（虽然它们仍然会写入磁盘以保证持久性），所以你不会想着把所有应用数据放到这里。这些少量数据会通过容错的全序广播算法复制到所有节点上。

共识协议保证了操作的原子性和线性一致性，即使节点发生故障或网络在任意时刻中断。分布式锁通常以租约（lease）的形式实现，租约有一个到期时间，以便在客户端失效的情况下最终能被释放

当某个资源受到锁或租约的保护时，你需要一个防护令牌来防止客户端在进程暂停的情况下彼此冲突。防护令牌是每次锁被获取时单调增加的数字。 ZooKeeper通过全局排序操作来提供这个功能，它为每个操作提供一个单调递增的事务ID（zxid）和版本号（cversion）

失效检测：客户端在ZooKeeper服务器上维护一个长期会话，客户端和服务器周期性地交换心跳包来检查节点是否还活着。即使连接暂时中断，或者ZooKeeper节点失效，会话仍保持在活跃状态。但如果心跳停止的持续时间超出会话超时，ZooKeeper会宣告该会话已死亡。当会话超时（ZooKeeper调用这些临时节点）时，会话持有的任何锁都可以配置为自动释放（ZooKeeper称之为临时节点（ephemeral nodes））。

变更通知：客户端不仅可以读取其他客户端创建的锁和值，还可以监听它们的变更。因此，客户端可以知道另一个客户端何时加入集群（基于新客户端写入ZooKeeper的值），或发生故障（因其会话超时，而其临时节点消失）。通过订阅通知，客户端不用再通过频繁轮询的方式来找出变更。

服务发现

ZooKeeper，etcd和Consul也经常用于服务发现——也就是找出你需要连接到哪个IP地址才能到达特定的服务。在云数据中心环境中，虚拟机连续来去常见，你通常不会事先知道服务的IP地址。相反，你可以配置你的服务，使其在启动时注册服务注册表中的网络端点，然后可以由其他服务找到它们。

成员服务

ZooKeeper和它的小伙伴们可以看作是成员服务研究的悠久历史的一部分，这个历史可以追溯到20世纪80年代，并且对建立高度可靠的系统（例如空中交通管制）非常重要。

成员资格服务确定哪些节点当前处于活动状态并且是群集的活动成员。正如我们在第8章中看到的那样，由于无限的网络延迟，无法可靠地检测到另一个节点是否发生故障。但是，如果你通过一致的方式进行故障检测，那么节点可以就哪些节点应该被认为是存在或不存在达成一致。

小结

尽管单领导者数据库可以提供线性一致性，且无需对每个写操作都执行共识算法，但共识对于保持及变更领导权仍然是必须的。因此从某种意义上说，使用单个领导者不过是“缓兵之计”：共识仍然是需要的，只是在另一个地方，而且没那么频繁。好消息是，容错的共识算法与容错的共识系统是存在的，我们在本章中简要地讨论了它们。

像ZooKeeper这样的工具为应用提供了“外包”的共识、故障检测和成员服务。它们扮演了重要的角色，虽说使用不易，但总比自己去开发一个能经受第8章中所有问题考验的算法要好得多。如果你发现自己想要解决的问题可以归结为共识，并且希望它能容错，使用一个类似ZooKeeper的东西是明智之举。

尽管如此，并不是所有系统都需要共识：例如，无领导者复制和多领导者复制系统通常不会使用全局的共识。这些系统中出现的冲突（参见“处理冲突”）正是不同领导者之间没有达成共识的结果，但也这并没有关系：也许我们只是需要接受没有线性一致性的事实，并学会更好地与具有分支与合并版本历史的数据打交道。

第三部分：衍生数据

现实世界中的数据系统往往更为复杂。大型应用程序经常需要以多种方式访问和处理数据，没有一个数据库可以同时满足所有这些不同的需求。因此应用程序通常组合使用多种组件：数据存储，索引，缓存，分析系统，等等，并实现在这些组件中移动数据的机制。

本书的最后一部分，会研究将多个不同数据系统（可能有着不同数据模型，并针对不同的访问模式进行优化）集成为一个协调一致的应用架构时，会遇到的问题。软件供应商经常会忽略这一方面的生态建设，并声称他们的产品能够满足你的所有需求。在现实世界中，集成不同的系统是实际应用中最重要的事情之一。

从高层次上看，存储和处理数据的系统可以分为两大类：

  • 记录系统（System of record）：记录系统，也被称为真相源（source of truth），持有数据的权威版本。当新的数据进入时（例如，用户输入）首先会记录在这里。每个事实正正好好表示一次（表示通常是标准化的（normalized））。如果其他系统和记录系统之间存在任何差异，那么记录系统中的值是正确的（根据定义）。
  • 衍生数据系统（Derived data systems）：衍生系统中的数据，通常是另一个系统中的现有数据以某种方式进行转换或处理的结果。如果丢失衍生数据，可以从原始来源重新创建。典型的例子是缓存（cache）：如果数据在缓存中，就可以由缓存提供服务；如果缓存不包含所需数据，则降级由底层数据库提供。非规范化的值，索引和物化视图亦属此类。在推荐系统中，预测汇总数据通常衍生自用户日志。从技术上讲，衍生数据是冗余的（redundant），因为它重复了已有的信息。但是衍生数据对于获得良好的只读查询性能通常是至关重要的。它通常是非规范化的。可以从单个源头衍生出多个不同的数据集，使你能从不同的“视角”洞察数据。

大多数数据库，存储引擎和查询语言，本质上既不是记录系统也不是衍生系统。数据库只是一个工具：如何使用它取决于你自己。记录系统和衍生数据系统之间的区别不在于工具，而在于应用程序中的使用方式。

第十章：批处理

我们来看看三种不同类型的系统：

  • 服务（在线系统）：服务等待客户的请求或指令到达。每收到一个，服务会试图尽快处理它，并发回一个响应。响应时间通常是服务性能的主要衡量指标，可用性通常非常重要（如果客户端无法访问服务，用户可能会收到错误消息）。
  • 批处理系统（离线系统）：一个批处理系统有大量的输入数据，跑一个作业（job）来处理它，并生成一些输出数据，这往往需要一段时间（从几分钟到几天），所以通常不会有用户等待作业完成。相反，批量作业通常会定期运行（例如，每天一次）。批处理作业的主要性能衡量标准通常是吞吐量（处理特定大小的输入所需的时间）。本章中讨论的就是批处理。
  • 流处理系统（准实时系统）：流处理介于在线和离线（批处理）之间，所以有时候被称为准实时（near-real-time）或准在线（nearline）处理。像批处理系统一样，流处理消费输入并产生输出（并不需要响应请求）。但是，流式作业在事件发生后不久就会对事件进行操作，而批处理作业则需等待固定的一组输入数据。这种差异使流处理系统比起批处理系统具有更低的延迟。由于流处理基于批处理，我们将在第11章讨论它。

使用Unix工具的批处理

统一的接口

如果你希望一个程序的输出成为另一个程序的输入，那意味着这些程序必须使用相同的数据格式 —— 换句话说，一个兼容的接口。如果你希望能够将任何程序的输出连接到任何程序的输入，那意味着所有程序必须使用相同的I/O接口。

在Unix中，这种接口是一个文件（file）（更准确地说，是一个文件描述符）。一个文件只是一串有序的字节序列。因为这是一个非常简单的接口，所以可以使用相同的接口来表示许多不同的东西：文件系统上的真实文件，到另一个进程（Unix套接字，stdin，stdout）的通信通道，设备驱动程序（比如/dev/audio或/dev/lp0），表示TCP连接的套接字等等。很容易将这些设计视为理所当然的，但实际上能让这些差异巨大的东西共享一个统一的接口是非常厉害的，这使得它们可以很容易地连接在一起

然而，Unix工具的最大局限在于它们只能在一台机器上运行 —— 而Hadoop这样的工具即应运而生。

MapReduce和分布式文件系统

MapReduce有点像Unix工具，但分布在数千台机器上。像Unix工具一样，它相当简单粗暴，但令人惊异地管用。一个MapReduce作业可以和一个Unix进程相类比：它接受一个或多个输入，并产生一个或多个输出。

和大多数Unix工具一样，运行MapReduce作业通常不会修改输入，除了生成输出外没有任何副作用。输出文件以连续的方式一次性写入（一旦写入文件，不会修改任何现有的文件部分）。

虽然Unix工具使用stdin和stdout作为输入和输出，但MapReduce作业在分布式文件系统上读写文件。在Hadoop的Map-Reduce实现中，该文件系统被称为HDFS（Hadoop分布式文件系统），一个Google文件系统（GFS）的开源实现

HDFS包含在每台机器上运行的守护进程，对外暴露网络服务，允许其他节点访问存储在该机器上的文件（假设数据中心中的每台通用计算机都挂载着一些磁盘）。名为NameNode的中央服务器会跟踪哪个文件块存储在哪台机器上。因此，HDFS在概念上创建了一个大型文件系统，可以使用所有运行有守护进程的机器的磁盘。

MapReduce作业执行

MapReduce是一个编程框架，你可以使用它编写代码来处理HDFS等分布式文件系统中的大型数据集。理解它的最简单方法是参考“简单日志分析”中的Web服务器日志分析示例。MapReduce中的数据处理模式与此示例非常相似：

  • 读取一组输入文件，并将其分解成记录（records）。在Web服务器日志示例中，每条记录都是日志中的一行（即\n是记录分隔符）。
  • 调用Mapper函数，从每条输入记录中提取一对键值。在前面的例子中，Mapper函数是awk '{print $7}'：它提取URL（$7）作为关键字，并将值留空。
  • 按键排序所有的键值对。在日志的例子中，这由第一个sort命令完成。
  • 调用Reducer函数遍历排序后的键值对。如果同一个键出现多次，排序使它们在列表中相邻，所以很容易组合这些值而不必在内存中保留很多状态。在前面的例子中，Reducer是由uniq -c命令实现的，该命令使用相同的键来统计相邻记录的数量。

Mapper会在每条输入记录上调用一次，其工作是从输入记录中提取键值。对于每个输入，它可以生成任意数量的键值对（包括None）。它不会保留从一个输入记录到下一个记录的任何状态，因此每个记录都是独立处理的。

Reducer MapReduce框架拉取由Mapper生成的键值对，收集属于同一个键的所有值，并使用在这组值列表上迭代调用Reducer。 Reducer可以产生输出记录（例如相同URL的出现次数）。

分布式执行MapReduce

MapReduce与Unix命令管道的主要区别在于，MapReduce可以在多台机器上并行执行计算，而无需编写代码来显式处理并行问题。Mapper和Reducer一次只能处理一条记录；它们不需要知道它们的输入来自哪里，或者输出去往什么地方，所以框架可以处理在机器之间移动数据的复杂性。

在分布式计算中可以使用标准的Unix工具作为Mapper和Reducer，但更常见的是，它们被实现为传统编程语言的函数。在Hadoop MapReduce中，Mapper和Reducer都是实现特定接口的Java类。

虽然Map任务的数量由输入文件块的数量决定，但Reducer的任务的数量是由作业作者配置的（它可以不同于Map任务的数量）。为了确保具有相同键的所有键值对最终落在相同的Reducer处，框架使用键的散列值来确定哪个Reduce任务应该接收到特定的键值对

只要当Mapper读取完输入文件，并写完排序后的输出文件，MapReduce调度器就会通知Reducer可以从该Mapper开始获取输出文件。Reducer连接到每个Mapper，并下载自己相应分区的有序键值对文件。按Reducer分区，排序，从Mapper向Reducer复制分区数据，这一整个过程被称为混洗（shuffle）（一个容易混淆的术语 —— 不像洗牌，在MapReduce中的混洗没有随机性）。

MapReduce工作流

一个作业的输出成为下一个作业的输入。 Hadoop Map-Reduce框架对工作流没有特殊支持，所以这个链是通过目录名隐式实现的：第一个作业必须将其输出配置为HDFS中的指定目录，第二个作业必须将其输入配置为从同一个目录。从MapReduce框架的角度来看，这是是两个独立的作业。

因此，被链接的MapReduce作业并没有那么像Unix命令管道（它直接将一个进程的输出作为另一个进程的输入，仅用一个很小的内存缓冲区）。它更像是一系列命令，其中每个命令的输出写入临时文件，下一个命令从临时文件中读取。

处理倾斜

如果存在与单个键关联的大量数据，则“将具有相同键的所有记录放到相同的位置”这种模式就被破坏了。例如在社交网络中，大多数用户可能会与几百人有连接，但少数名人可能有数百万的追随者。这种不成比例的活动数据库记录被称为关键对象（linchpin object）或热键（hot key）。

在单个Reducer中收集与某个名流相关的所有活动（例如他们发布内容的回复）可能导致严重的倾斜（也称为热点（hot spot））—— 也就是说，一个Reducer必须比其他Reducer处理更多的记录。由于MapReduce作业只有在所有Mapper和Reducer都完成时才完成，所有后续作业必须等待最慢的Reducer才能启动。

如果连接的输入存在热点键，可以使用一些算法进行补偿。例如，Pig中的倾斜连接（skewed join）方法首先运行一个抽样作业来确定哪些键是热键。连接实际执行时，Mapper会将热键的关联记录随机（相对于传统MapReduce基于键散列的确定性方法）发送到几个Reducer之一。对于另外一侧的连接输入，与热键相关的记录需要被复制到所有处理该键的Reducer上.

Hadoop与分布式数据库的对比

正如我们所看到的，Hadoop有点像Unix的分布式版本，其中HDFS是文件系统，而MapReduce是Unix进程的怪异实现（总是在Map阶段和Reduce阶段运行sort工具）。我们了解了如何在这些原语的基础上实现各种连接和分组操作。

当MapReduce论文发表时，它从某种意义上来说 —— 并不新鲜。我们在前几节中讨论的所有处理和并行连接算法已经在十多年前所谓的大规模并行处理（MPP， massively parallel processing）数据库中实现了。

最大的区别是，MPP数据库专注于在一组机器上并行执行分析SQL查询，而MapReduce和分布式文件系统的组合则更像是一个可以运行任意程序的通用操作系统。

存储多样性

Hadoop开放了将数据不加区分地转储到HDFS的可能性，允许后续再研究如何进一步处理【53】。相比之下，在将数据导入数据库专有存储格式之前，MPP数据库通常需要对数据和查询模式进行仔细的前期建模。

不加区分的数据转储转移了解释数据的负担：数据集的生产者不再需要强制将其转化为标准格式，数据的解释成为消费者的问题

针对频繁故障设计

如果一个节点在执行查询时崩溃，大多数MPP数据库会中止整个查询，并让用户重新提交查询或自动重新运行它。由于查询通常最多运行几秒钟或几分钟，所以这种错误处理的方法是可以接受的，因为重试的代价不是太大。 MPP数据库还倾向于在内存中保留尽可能多的数据（例如，使用散列连接）以避免从磁盘读取的开销。

另一方面，MapReduce可以容忍单个Map或Reduce任务的失败，而不会影响作业的整体，通过以单个任务的粒度重试工作。它也会非常急切地将数据写入磁盘，一方面是为了容错，另一部分是因为假设数据集太大而不能适应内存。

MapReduce方式更适用于较大的作业：要处理如此之多的数据并运行很长时间的作业，以至于在此过程中很可能至少遇到一个任务故障。在这种情况下，由于单个任务失败而重新运行整个作业将是非常浪费的。

这就是MapReduce被设计为容忍频繁意外任务终止的原因：不是因为硬件很不可靠，而是因为任意终止进程的自由有利于提高计算集群中的资源利用率。

MapReduce之后

物化中间状态

如前所述，每个MapReduce作业都独立于其他任何作业。作业与世界其他地方的主要连接点是分布式文件系统上的输入和输出目录。如果希望一个作业的输出成为第二个作业的输入，则需要将第二个作业的输入目录配置为第一个作业输出目录，且外部工作流调度程序必须在第一个作业完成后再启动第二个。

很多情况下，你知道一个作业的输出只能用作另一个作业的输入，这些作业由同一个团队维护。在这种情况下，分布式文件系统上的文件只是简单的中间状态（intermediate state）：一种将数据从一个作业传递到下一个作业的方式。

将这个中间状态写入文件的过程称为物化（materialization）。

数据流引擎

Spark、Tez、Flink等数据流引擎有一个共同点：把整个工作流作为单个作业来处理，而不是把它分解为独立的子作业。由于它们将工作流显式建模为 数据从几个处理阶段穿过，所以叫做数据流引擎

与MapReduce不同，这些功能不需要严格扮演交织的Map与Reduce的角色，而是可以以更灵活的方式进行组合。我们称这些函数为算子（operators），数据流引擎提供了几种不同的选项来将一个算子的输出连接到另一个算子的输入：

MapReduce模型相比，它有几个优点：

  • 排序等昂贵的工作只需要在实际需要的地方执行，而不是默认地在每个Map和Reduce阶段之间出现。
  • 没有不必要的Map任务，因为Mapper所做的工作通常可以合并到前面的Reduce算子中（因为Mapper不会更改数据集的分区）。
  • 由于工作流中的所有连接和数据依赖都是显式声明的，因此调度程序能够总览全局，知道哪里需要哪些数据，因而能够利用局部性进行优化。例如，它可以尝试将消费某些数据的任务放在与生成这些数据的任务相同的机器上，从而数据可以通过共享内存缓冲区传输，而不必通过网络复制。
  • 通常，算子间的中间状态足以保存在内存中或写入本地磁盘，这比写入HDFS需要更少的I/O
  • 算子可以在输入就绪后立即开始执行；后续阶段无需等待前驱阶段整个完成后再开始。
  • 与MapReduce（为每个任务启动一个新的JVM）相比，现有Java虚拟机（JVM）进程可以重用来运行新算子，从而减少启动开销。
容错

完全物化中间状态至分布式文件系统的一个优点是，它具有持久性，这使得MapReduce中的容错相当容易：如果一个任务失败，它可以在另一台机器上重新启动，并从文件系统重新读取相同的输入。

Spark，Flink和Tez避免将中间状态写入HDFS，因此它们采取了不同的方法来容错：如果一台机器发生故障，并且该机器上的中间状态丢失，则它会从其他仍然可用的数据重新计算（在可行的情况下是先前的中间状态，要么就只能是原始输入数据，通常在HDFS上）。

第十一章：流处理

批处理有一个很大的假设，即输入是有界的，所以批处理知道它何时完成输入的读取。例如，MapReduce核心的排序操作必须读取其全部输入，然后才能开始生成输出：可能发生这种情况：最后一条输入记录具有最小的键，因此需要第一个被输出，所以提早开始输出是不可行的。

实际上，很多数据是无界限的，因为它随着时间的推移而逐渐到达：你的用户在昨天和今天产生了数据，明天他们将继续产生更多的数据。除非你停业，否则这个过程永远都不会结束，所以数据集从来就不会以任何有意义的方式“完成

为了减少延迟，我们可以更频繁地运行处理 —— 比如说，在每秒钟的末尾 —— 或者甚至更连续一些，完全抛开固定的时间切片，当事件发生时就立即进行处理，这就是流处理（stream processing）背后的想法

在本章中，我们将把事件流（event stream）视为一种数据管理机制：无界限，增量处理

传递事件流

在批处理中，文件被写入一次，然后可能被多个作业读取。类似地，在流处理术语中，一个事件由 生产者（producer） （也称为 发布者（publisher） 或 发送者（sender） ）生成一次，然后可能由多个 消费者（consumer） （ 订阅者（subscribers） 或 接收者（recipients） ）进行处理。在文件系统中，文件名标识一组相关记录；在流式系统中，相关的事件通常被聚合为一个 主题（topic） 或 流（stream） 。

数据库虽然可以足以连接生产者和消费者，但是轮训开销很大，最好能在新事件出现时直接通知消费者，虽然有触发器，但是功能有限

消息系统

向消费者通知新事件的常用方式是使用消息传递系统（messaging system）：生产者发送包含事件的消息，然后将消息推送给消费者。

像生产者和消费者之间的Unix管道或TCP连接这样的直接信道，是实现消息传递系统的简单方法。但是，大多数消息传递系统都在这一基本模型上进行扩展。特别的是，Unix管道和TCP将恰好一个发送者与恰好一个接收者连接，而一个消息传递系统允许多个生产者节点将消息发送到同一个主题，并允许多个消费者节点接收主题中的消息。

有两个问题值得注意：

  • 如果生产者发送消息的速度比消费者能够处理的速度快会发生什么？一般来说，有三种选择：系统可以丢掉消息，将消息放入缓冲队列，或使用背压（backpressure）（也称为流量控制（flow control）；即阻塞生产者，以免其发送更多的消息）。例如Unix管道和TCP使用背压：它们有一个固定大小的小缓冲区，如果填满，发送者会被阻塞，直到接收者从缓冲区中取出数据（参见“网络拥塞和排队”）。
    如果消息被缓存在队列中，那么理解队列增长会发生什么是很重要的。当队列装不进内存时系统会崩溃吗？还是将消息写入磁盘？如果是这样，磁盘访问又会如何影响消息传递系统的性能？
  • 如果节点崩溃或暂时脱机，会发生什么情况？ —— 是否会有消息丢失？与数据库一样，持久性可能需要写入磁盘和/或复制的某种组合（参阅“复制和持久性”），这是有代价的。如果你能接受有时消息会丢失，则可能在同一硬件上获得更高的吞吐量和更低的延迟，
直接从生产者传递给消费者

许多消息传递系统使用生产者和消费者之间的直接网络通信，而不通过中间节点：

  • UDP组播广泛应用于金融行业，例如股票市场，其中低时延非常重要。虽然UDP本身是不可靠的，但应用层的协议可以恢复丢失的数据包（生产者必须记住它发送的数据包，以便能按需重新发送数据包）。
  • 无代理的消息库，如ZeroMQ和nanomsg采取类似的方法，通过TCP或IP多播实现发布/订阅消息传递。
  • StatsD 和Brubeck使用不可靠的UDP消息传递来收集网络中所有机器的指标并对其进行监控。
  • 如果消费者在网络上公开了服务，生产者可以直接发送HTTP或RPC请求（参阅“通过服务进行数据流：REST和RPC”）将消息推送给使用者。这就是webhooks背后的想法【12】，一种服务的回调URL被注册到另一个服务中，并且每当事件发生时都会向该URL发出请求。
消息代理/消息队列

一种广泛使用的替代方法是通过消息代理（message broker）（也称为消息队列（message queue））发送消息，消息代理实质上是一种针对处理消息流而优化的数据库。它作为服务器运行，生产者和消费者作为客户端连接到服务器。生产者将消息写入代理，消费者通过从代理那里读取来接收消息。

通过将数据集中在代理上，这些系统可以更容易地容忍来来去去的客户端（连接，断开连接和崩溃），而持久性问题则转移到代理的身上。一些消息代理只将消息保存在内存中，而另一些消息代理（取决于配置）将其写入磁盘，以便在代理崩溃的情况下不会丢失。针对缓慢的消费者，它们通常会允许无上限的排队（而不是丢弃消息或背压），尽管这种选择也可能取决于配置。

消费者通常是异步的

消息代理与数据库的差异
  • 数据库通常保留数据直至显式删除，而大多数消息代理在消息成功递送给消费者时会自动删除消息。这样的消息代理不适合长期的数据存储。
  • 由于它们很快就能删除消息，大多数消息代理都认为它们的工作集相当小—— 即队列很短。如果代理需要缓冲很多消息，比如因为消费者速度较慢（如果内存装不下消息，可能会溢出到磁盘），每个消息需要更长的处理时间，整体吞吐量可能会恶化。
  • 数据库通常支持二级索引和各种搜索数据的方式，而消息代理通常支持按照某种模式匹配主题，订阅其子集。机制并不一样。
  • 查询数据库时，结果通常基于某个时间点的数据快照；如果另一个客户端随后向数据库写入一些改变了查询结果的内容，则第一个客户端不会发现其先前结果现已过期（除非它重复查询或轮询变更）。相比之下，消息代理不支持任意查询，但是当数据变化时（即新消息可用时），它们会通知客户端
多个消费者

当多个消费者从同一主题中读取消息时，有使用两种主要的消息传递模式，：

  • 负载均衡（load balance）：每条消息都被传递给消费者之一，所以处理该主题下消息的工作能被多个消费者共享。代理可以为消费者任意分配消息。当处理消息的代价高昂，希望能并行处理消息时，此模式非常有用。

  • 扇出（fan-out）：每条消息都被传递给所有消费者。扇出允许几个独立的消费者各自“收听”相同的消息广播，而不会相互影响 —— 这个流处理中的概念对应批处理中多个不同批处理作业读取同一份输入文件

两种模式可以组合使用：例如，两个独立的消费者组可以每组各订阅一个主题，每一组都共同收到所有消息，但在每一组内部，每条消息仅由单个节点处理。

使用日志进行消息存储

日志只是磁盘上简单的仅追加记录序列。我们先前在第3章中日志结构存储引擎和预写式日志的上下文中讨论了日志，在第5章复制的上下文里也讨论了它。

同样的结构可以用于实现消息代理：生产者通过将消息追加到日志末尾来发送消息，而消费者通过依次读取日志来接收消息。如果消费者读到日志末尾，则会等待新消息追加的通知。 Unix工具tail -f 能监视文件被追加写入的数据，基本上就是这样工作的。

为了扩展到比单个磁盘所能提供的更高吞吐量，可以对日志进行分区（在第6章的意义上）。不同的分区可以托管在不同的机器上，且每个分区都拆分出一份能独立于其他分区进行读写的日志。一个主题可以定义为一组携带相同类型消息的分区。

在每个分区内，代理为每个消息分配一个单调递增的序列号或偏移量（offset）。这种序列号是有意义的，因为分区是仅追加写入的，所以分区内的消息是完全有序的。没有跨不同分区的顺序保证。

消费者偏移量

顺序消费一个分区使得判断消息是否已经被处理变得相当容易：所有偏移量小于消费者的当前偏移量的消息已经被处理，而具有更大偏移量的消息还没有被看到。因此，代理不需要跟踪确认每条消息，只需要定期记录消费者的偏移即可。在这种方法减少了额外簿记开销，而且在批处理和流处理中采用这种方法有助于提高基于日志的系统的吞吐量。

磁盘空间使用

如果只追加写入日志，则磁盘空间终究会耗尽。为了回收磁盘空间，日志实际上被分割成段，并不时地将旧段删除或移动到归档存储。 （我们将在后面讨论一种更为复杂的磁盘空间释放方式）

这就意味着如果一个慢消费者跟不上消息产生的速率而落后的太多，它的消费偏移量指向了删除的段，那么它就会错过一些消息。实际上，日志实现了一个有限大小的缓冲区，当缓冲区填满时会丢弃旧消息，它也被称为循环缓冲区（circular buffer）或环形缓冲区（ring buffer）。不过由于缓冲区在磁盘上，因此可能相当的大。

流与数据库

我们看到基于日志的消息代理已经成功地从数据库中获取灵感并将其应用于消息传递。我们也可以反过来：从消息传递和流中获取灵感，并将它们应用于数据库。

我们之前曾经说过，事件是某个时刻发生的事情的记录。发生的事情可能是用户操作（例如键入搜索查询）或读取传感器，但也可能是写入数据库。某些东西被写入数据库的事实是可以被捕获，存储和处理的事件。这一观察结果表明，数据库和数据流之间的联系不仅仅是磁盘日志的物理存储 —— 而是更深层的联系。

事实上，复制日志（参阅“复制日志的实现”）是数据库写入事件的流，由主库在处理事务时生成。从库将写入流应用到它们自己的数据库副本，从而最终得到相同数据的精确副本。复制日志中的事件描述发生的数据更改。

保持系统同步

大多数重要应用都需要组合使用几种不同的技术来满足所有的需求：例如，使用OLTP数据库来为用户请求提供服务，使用缓存来加速常见请求，使用全文索引搜索处理搜索查询，使用数据仓库用于分析。每一个组件都有自己的数据副本，以自己的表示存储，并根据自己的目的进行优化。

如果周期性的完整数据库转储过于缓慢，有时会使用的替代方法是双写（dual write），其中应用代码在数据变更时明确写入每个系统：例如，首先写入数据库，然后更新搜索索引，然后使缓存项失效（甚至同时执行这些写入）。

但是，双写有一些严重的问题，其中一个是竞争条件

双重写入的另一个问题是，其中一个写入可能会失败，而另一个成功。这是一个容错问题，而不是一个并发问题，但也会造成两个系统互相不一致的结果。确保它们要么都成功要么都失败，是原子提交问题的一个例子，解决这个问题的代价是昂贵的

变更数据捕获

大多数数据库的复制日志的问题在于，它们一直被当做数据库的内部实现细节，而不是公开的API。客户端应该通过其数据模型和查询语言来查询数据库，而不是解析复制日志并尝试从中提取数据。

数十年来，许多数据库根本没有记录在档的，获取变更日志的方式。由于这个原因，捕获数据库中所有的变更，然后将其复制到其他存储技术（搜索索引，缓存，数据仓库）中是相当困难的。

最近，人们对变更数据捕获（change data capture, CDC） 越来越感兴趣，这是一种观察写入数据库的所有数据变更，并将其提取并转换为可以复制到其他系统中的形式的过程。 CDC是非常有意思的，尤其是当变更能在被写入后立刻用于流时。

流处理

流分析

使用流处理的另一个领域是对流进行分析。 CEP与流分析之间的边界是模糊的，但一般来说，分析往往对找出特定事件序列并不关心，而更关注大量事件上的聚合与统计指标 —— 例如：

  • 测量某种类型事件的速率（每个时间间隔内发生的频率）
  • 滚动计算一段时间窗口内某个值的平均值
  • 将当前的统计值与先前的时间区间的值对比（例如，检测趋势，当指标与上周同比异常偏高或偏低时报警）

这些统计值通常是在固定时间区间内进行计算的，例如，你可能想知道在过去5分钟内服务每秒查询次数的均值，以及此时间段内响应时间的第99百分位点。在几分钟内取平均，能抹平秒和秒之间的无关波动，且仍然能向你展示流量模式的时间图景。聚合的时间间隔称为窗口（window），我们将在“理解时间”中更详细地讨论窗口。

流分析系统有时会使用概率算法，例如Bloom filter来管理成员资格，HyperLogLog用于基数估计以及各种百分比估计算法

许多开源分布式流处理框架的设计都是针对分析设计的：例如Apache Storm，Spark Streaming，Flink，Concord，Samza和Kafka Streams

窗口类型

当你知道如何确定一个事件的时间戳后，下一步就是如何定义时间段的窗口。然后窗口就可以用于聚合，例如事件计数，或计算窗口内值的平均值。有几种窗口很常用：

  • 滚动窗口（Tumbling Window）：滚动窗口有着固定的长度，每个事件都仅能属于一个窗口。例如，假设你有一个1分钟的滚动窗口，则所有时间戳在10:03:00和10:03:59之间的事件会被分组到一个窗口中，10:04:00和10:04:59之间的事件被分组到下一个窗口，依此类推。通过将每个事件时间戳四舍五入至最近的分钟来确定它所属的窗口，可以实现1分钟的滚动窗口。
  • 跳动窗口（Hopping Window）：跳动窗口也有着固定的长度，但允许窗口重叠以提供一些平滑。例如，一个带有1分钟跳跃步长的5分钟窗口将包含10:03:00至10:07:59之间的事件，而下一个窗口将覆盖10:04:00至10:08:59之间的事件，等等。通过首先计算1分钟的滚动窗口，然后在几个相邻窗口上进行聚合，可以实现这种跳动窗口。
  • 滑动窗口（Sliding Window）：滑动窗口包含了彼此间距在特定时长内的所有事件。例如，一个5分钟的滑动窗口应当覆盖10:03:39和10:08:12的事件，因为它们相距不超过5分钟（注意滚动窗口与步长5分钟的跳动窗口可能不会把这两个事件分组到同一个窗口中，因为它们使用固定的边界）。通过维护一个按时间排序的事件缓冲区，并不断从窗口中移除过期的旧事件，可以实现滑动窗口。
  • 会话窗口（Session window）：与其他窗口类型不同，会话窗口没有固定的持续时间，而定义为：将同一用户出现时间相近的所有事件分组在一起，而当用户一段时间没有活动时（例如，如果30分钟内没有事件）窗口结束。会话切分是网站分析的常见需求（参阅“GROUP BY”）。
幂等性

我们的目标是丢弃任何失败任务的部分输出，以便能安全地重试，而不会生效两次。分布式事务是实现这个目标的一种方式，而另一种方式是依赖幂等性（idempotence）。

幂等操作是多次重复执行与单次执行效果相同的操作。例如，将键值存储中的某个键设置为某个特定值是幂等的（再次写入该值，只是用同样的值替代），而递增一个计数器不是幂等的（再次执行递增意味着该值递增两次）。

即使一个操作不是天生幂等的，往往可以通过一些额外的元数据做成幂等的。例如，在使用来自Kafka的消息时，每条消息都有一个持久的，单调递增的偏移量。将值写入外部数据库时可以将这个偏移量带上，这样你就可以判断一条更新是不是已经执行过了，因而避免重复执行。

第十二章：数据系统的未来

（水平有限，囫囵吞枣看了一遍，似懂非懂，就不做笔记了）