前四章讨论适用于所有数据系统的基本idea，无论是运行在单个机器还是集群之上：

  1. 第一章 第一章 介绍了整本书使用的术语和方法，并且阐述了所谓的可靠性、可扩展性和可维护性的实际含义，以及如何尝试实现这些目标
  2. 第二章 从开发者最关注的角度，比较了几种不同的数据模型和查询语言。我们可以看到为了适配不同的场景，数据模型的区别有多大
  4. 第三章 深入存储引擎内部，了解数据库的数据如何存储在硬盘上。不同的存储引擎是为了不同的工作负载类型优化的，选择适当的存储引擎可以带来巨大的性能提升
  5. 第四章 比较几种格式的数据编码方案（序列化），尤其检验它们在应用要求发生变更和模式需要随着时间适应的环境中的表现

稍后，第二部分 将讨论一些分布式数据系统的特定问题

互联网做的如此之优秀以至于人们习以为常的认为这是一种例如太平洋的自然资源而不是人造的。谁还记得上一次如此规模而且没有差错的技术是什么时候

​ ----- Alan Kay

今天的许多应用是数据密集型的而不是计算密集型的。基本的 CPU 资源已经不是这些应用的瓶颈，更大的问题是数据的规模，复杂性以及变化的速度。

数据密集型的应用通常是通过提供常用功能的标准标准组件构建的。比如，许多应用需要：

  • 存储数据，使得另一个应用稍后可以查询到（databases）
  • 记录一次开销巨大的计算结果，加速读（caches）
  • 允许用户通过多重组合对关键字进行搜索过滤（search indexes）
  • 向另一个进程发送消息，异步处理（stream processing）
  • 定期处理大量的累积数据（batch processing）

如果这听起来很痛苦，那是因为数据系统做了相当成功的抽象：我们只用不需要太多思考使用它们即可。当构建一个应用时，大多数工程师不会考虑写一个新的数据引擎，因为数据库已经用起来相当完美。

但是实际情况并不是那么简单。许多数据库系统具有不同的特性，因为不同的应用有不同的要求。存在多种进行缓存，多重构建索引的方法等等。当构建一个应用时，我们需要找到最适合手边任务的工具和方法。尤其是当单一工具无法完成你的任务时，将多重工具组合起来是一个挑战。

这本书是一个关于数据系统原理和实用性以及如何使用它们构建应用的探讨过程。我们将探讨不同工具的共同点，区别以及它们如何实现其特性。

在本章，我们将从探索基础概念开始：数据系统的可靠性、可扩展性、可维护性。我们将阐明这些名词的含义，为后续章节奠定基础。随后，在后面的章节中，我们将逐层展开，探讨当设计一个数据密集型的应用时，需要考虑的不同设计决策。

Thinking about Data Systems

可靠性：系统可以持续正确的工作，即使出现硬件，软件甚至人为故障的时候

可扩展性：当系统的流量，数据量和复杂度增长时，有方式处理这种增长

可维护性：在一段时间里，会有许多不同的工作人员参与系统的开发和运营，他们应该都能有效的参与

可靠性

可扩展性

即使系统在今天可靠运行，也不意味着将来一定会可靠运行，降级的一个常见原因就是增加的负载：系统可能从 1 万并发用户增长到 10 万并发用户，或者从 1 百万增长到 1 千万。也许需要处理比之前大得多的数据量

可扩展性就是我们用来描述系统处理负载增长的能力。需要注意的是，对于系统的单个维度可扩展的标签是没有意义的（比如说 x 是可扩展的或者 y 是不可扩展的），对于讨论可扩展性的问题应该是这样的：“如果系统以特定的方式增长，我们应对增长的方式是什么？”或者 “我们如何为了处理增长的负载在系统中加入计算资源？”

描述负载

首先，我们需要能描述系统的当前负载，然后才能讨论负载增长的问题。负载可以通过一些量化的数字参数来描述。参数最好的选择依赖于系统的体系结构：web 服务的处理每秒请求量，数据库的读写速率，讨论组的真实在线用户，缓存命中率等等。或许你需要的是平均值，或者你需要的是限制瓶颈的少数参数值。

为了使得这个 idea 更加具体，我们拿 Twitter 来举例子，使用 2012 年 11 月发布的数据，Twitter 的两个主要操作是：

  • 推送 tweet 一个用户可以将消息推送给关注他的用户（平均 4.6k 条请求每秒，峰值超过 12k 条请求每秒）
  • 拉取 tweet 一个用户可以拉取关注的其他用户的消息（300k 条请求每秒）

简单处理 12k 写操作每秒（推送 tweet 的峰值量）相当简单，但是 Twitter 的可扩展性挑战不主要是 tweet 的数据量，而是扇出（fan-out），每个用户关注了很多用户，每个用户又被许多用户关注。有两种常见方案实现这两种操作：

  1. 推送 tweet，就是在一个全局的 tweet 集合中插入新的 tweet。当一个用户拉取他所关注的用户消息时，查询，通过实践合并所有消息，在关系型数据库中，可以这样写一个查询：

    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_user

    image-20200817132238941

  2. 为每个用户的关注列表建立一个缓存--就像每个收信用户的邮箱。当一个用户推送了一条 tweet，查询所有关注此用户的用户，在每个用户对应的缓存里插入一条 tweet。请求读的处理才能快速，因为结果是提前计算的 image-20200817132338775

第一个版本的 Twitter 使用方案 1，但是系统难以跟上查询关注用户的负载增长，所以公司改进为方案 2。这种方案的效果良好，因为推送的请求数量级比查询的数量级低两个，因此最好在写入时做更多的工作，读取时才能简单

但是，方案 2 的缺点就是需要在推送请求中做大量工作，平均一下，一条 tweet 需要传递给大概 75 个用户，所以每秒 4.6k 条 tweet 变成，每秒向缓存写入 345k 条请求。但是平均掩盖了一个存在大 V 的情况，有些用户可能有超过 3 千万的关注。这就意味着，一条推送 tweet 导致 3 千万的写缓存请求！及时做到这一点（Twitter 尝试在五秒内推送到所有关注者）是一项重大挑战。

在 Twitter 的例子中，每个用户的关注者分布（可能由用户的推送频率加权）就是讨论负载的一个关键负载参数，因为它确定了扇出（fan-out）负载。你的应用程序可能具有不同的特征，但是可以使用相似的原理来导出负载

Twitter 例子的最后总结：现在方案 2 已经被非常好的实现了，Twitter 正在尝试将方案 1 和方案 2 结合起来。大多数用户的 tweet 会在发布时扇出到缓存上，但是拥有大量关注者的少量用户除外。大 V 的推文像方案 1 一样被每个用户读取的时候分别拉取然后合并。这种混合方案能够提供出色的性能。我们会在介绍了更多的基础之后，在第 12 章重新研究此案例。

描述性能

当成功描述系统的负载之后，你可以发现当系统负载提高时，发生了什么，你可以从两个角度来看：

  • 当你提升了负载，但是保持系统的资源（CPU，内存，网络带宽）不变时，你的系统性能表现如何？
  • 当你提升了负载，为了保持系统性能不变，需要增加多少资源？

两个问题都需要性能量化，所以让我们来简单描述一下系统的性能。

在批处理系统中，比如 Hadoop，我们通常关心吞吐量-系统每秒能处理的记录条数，或者在一定体量的数据集上完成任务的时间。在在线系统中，服务的响应时间更为重要-从客户端发送请求到收到响应之间的时间段。

延迟和响应时间

延迟和响应时间通常被认为是同义的，但是并不完全对。响应时间是从客户端角度来看：包括服务端真实的处理时间，网络延迟和排队延迟。延迟就是一段等待处理的时间。

即使你一次又一地发出相同的请求，每次尝试的响应时间也会有所不同。实际上，系统处理不同请求的响应时间天差地别。因此考虑响应时间时不能作为单纯的一个数字，而是统计出来的数字的分布。

在下图中，每个灰色直方图表示一个请求，高度表示响应时间长短。大多数请求在合理时间内得到响应，但是偶尔会有异常情况导致的长时间开销。慢速处理的请求本质上可能开销确实更大，比如处理更多的数据。但是即使在同一个场景下的同一种请求也会出乎意料的存在不同的响应时间：随机延迟的引入可能是由后台进程的上下文切换，网络丢包，TCP 重连，GC，缺页中断，服务器基架的震动等许多问题造成的。

image-20200817170607899

可维护性

众所周知，软件的大部分成本不在最初的开发中，而是在持续的维护时中修复 bug，保持系统的稳定运行，调查故障，适配新平台，为了新用途修改，还技术债，以及增加新功能。

但是不幸的是，大多数开发者不喜欢维护所谓的遗产系统--工作内容包括修复他人的错误，使用落后的平台，或者尝试开发本来系统没有规划的功能。每个遗产系统都以其自己的方式令人不快，因此很难给出处理这个问题的通用建议。

但是，我们在设计软件的时候，就应该采用使得维护过程痛苦最小化的方案。所以，我们在设计软件系统时，应该关注三点原则：

  • 可运维性：使得运维团队可以轻松的保持系统正常运行
  • 简单化：通过消除尽可能多的系统复杂性，使得新开发人员容易理解系统
  • 可演化性：使得开发人员将来可以简单的修改系统，并根据需求的变化将其适用于没有规划过的用例。也被称为可扩展性、可修改性或者可塑性

就像之前讨论的可靠性和可扩展性，没有简单的方案来达成这一目标，但是，我们将尽可能来遵循可操作性、简单化、可演化性的原则来设计系统。

可运维性

有人提出，良好的运维性可以掩盖不良（或者不完整）软件的局限性，但是良好的软件不能通过差的运维可靠运行。尽管有些运维应该实现自动化，但是仍然需要人工来首先设置自动化参数并确保其正常工作。

运营团队对于保持软件系统的平稳运行至关重要。一个好的运维团队通常负责以下工作：

  • 监控系统的健康程度，当发现系统不健康时迅速的恢复
  • 追踪错误的原因，比如系统错误或者性能退化
  • 保持软件和平台更新，包括安全补丁
  • 密切关注不同系统之间的相互影响，从而避免在造成损坏之前进行修复
  • 预测未来的可能问题，并在问题出现之前解决（比如服务容量的规划）
  • 建立良好的部署，配置管理的习惯和工具
  • 执行复杂的维护任务，比如将一个应用程序从一个平台迁移到另一个平台
  • 在进行配置更改时维护系统的安全
  • 定义操作流程使得操作可预期，并帮助保持生产系统的稳定
  • 即使人员去留，保持对于系统的整体知识

好的运维意味着简单的日常任务，使得运维团队可以集中精力在更高价值的活动上。数据系统可以通过多种方式来简化日常运维：

  • 提供可视化能力来监控系统的运行状态
  • 提供自动化的良好支持和标准工具的整合
  • 避免对于单个机器的依赖（在系统连续运行时，允许停止单个机器来维护）
  • 提供良好的文档和容易理解的系统操作模型（如果操作 X，结果为 Y）
  • 提供良好的默认行为，但是也要允许管理员自由的更改默认值
  • 进行适当的自我修复，但是在需要时也可以让管理员手动控制系统状态
  • 展现可预测的行为，最大程度减少意外

简单化：管理复杂性

小型的软件项目可以具有令人愉悦的简单和富有表现力的代码，但是当项目变大时，它们通常变得复杂，难以理解。这种复杂性减缓了系统新开发人员熟悉系统的速度，提升了维护成本。又是这种陷入了复杂性的软件被称为烂泥（big ball of mud）

可能存在多种复杂性的症状：状态空间爆炸，模块的紧耦合，依赖纠缠，不一致的命名空间和术语，旨在解决性能的 hack 代码，特列的专门处理代码等等，有太多这种话题。

当复杂性使得难以维护时，预算和计划就会超支。在复杂的软件中，进行更改时还存在引入错误的巨大风险：当开发人员难以理解系统时，更容易忽略隐藏的假设，意外的结果，**意外的交互。**相反，降低复杂度可以极大提高软件的可维护性，因此简化应该是构建系统的关键目标。

使系统更简单并不意味着减少功能；虽然这也意味着降低复杂性。Moseley 和 Marks 定义复杂性是偶然的，如果这不是因为解决某个软件问题必须引入的，而仅仅是因为具体实现。

我们移除偶然复杂性的最好工具就是抽象。好的抽象可以在干净，易于理解的接口内部隐藏大量实现细节。好的抽象还可以用于一系列不同的应用中。这种重用不仅比多次实现类似的东西高效，而且也能引导更高的软件质量，这会使得所有使用抽象的应用获得收益。（ps. 中间件？）

比如，高级编程语言就是隐藏了机器代码，CPU 寄存器，系统调用的抽象。SQL 是一种隐藏了复杂的磁盘和内存数据结构的，并行处理来自其他客户端请求以及 crash 后不一致情况的抽象。当然，当使用高级编程语言编程时，我们还是运行的机器码，只是没有直接编写机器码，高级编程语言的抽象使我们从其中解脱出来。

但是，发现好的抽象是挺困难的。在分布式系统领域，尽管有很多优秀的算法，但是我们如何将它们打包抽象来帮助将系统的复杂性降低保持到可管理的水平还不清楚。

在本书中，我们将始终保持良好的抽象态度，使得能够提取大型系统中良好的，可重用的组件。

可演化性：使改变简单

你的系统永远保持不变的可能性很小。它们更有可能保持不断变化：你了解到新的事实，出现了未预料的用例，业务优先级的改变，用户要求新的功能，新平台替代老平台，法律法规变更，系统增长导致的系统结构变化等。

在组织开发流程方面，敏捷开发模式提供了一个适应变化的开发框架。敏捷社区开发了技术工具和模式来帮助适应在频繁变化的环境中的软件开发，比如测试驱动开发（TDD）和重构。

大多数关于敏捷开发的讨论集中于相当小的，局部的规模（同一个应用的源代码）。在本书中，我们寻求在更大的数据系统中提升敏捷能力的方法，这个系统或许包括几种不同特性的多个应用或服务组成。例如，你如何为了缓存使用将 Twitter 的体系结构（描述负载一节提到）从方案 1 重构为方案 2。

你可以轻松的修改数据系统，使之适应修改的需求，这与它的简单性和良好抽象有关：简单和易于理解的系统比负载系统更容易修改。但是因为这是一个如此重要的观点，我们将使用一个不同的单词来表征数据系统的敏捷能力：可演化性。

总结

在本章中，我们探讨了一些有关数据密集型应用程序的基本思考方法。这些原则将指导我们完成本书的剩余部分，将深入技术细节。

一个应用必须能够满足各种需求。有功能需求（能做什么，比如允许数据存储，检索，搜索和以不同的方法处理），非功能性需求（像安全性，可靠性，合规性，可扩展性，兼容性以及可维护性这些通用特性）。这本章中，我们详细讨论了可靠性，可扩展性和可维护性。

可靠性意味着即使出现故障系统也能正常工作。故障可能出现在硬件（通常是随机且不相关的）、软件（bug 通常是系统性的且难以处理）、人（不可避免的时常犯错）。容错技术可以将其对终端用户隐藏起来。

可扩展性意味着即使负载提升，也能保持良好性能。为了讨论课扩展性，我们首先需要量化描述负载和性能。我们简单地讨论了 Twitter 的案例。在一个可扩展性系统中，你可以为了在高负载下保持可靠增加系统容量。

可维护性有很多方面，但是本质上改善该系统的开发和运维。良好的抽象可以降低复杂性，使得系统更容易修改和适应新需求。良好的运维性意味着系统健康度的可视化，以及有高效的方法管理系统。

不幸的是，没有使得应用可靠、可扩展或者可维护的简单修补程序。但是，某些模式和技术会在不同的应用中不断出现。在接下来的几章中，我们将研究一些数据系统示例并分析它们如何朝着这个目标努力。

稍后，在本书第三部分中，我们将研究多个组件协同工作的系统的模式。

语言的限制意味着世界的限制 -- Ludwig Wittgenstein

数据模型可能是软件开发最重要的一部分，因为它们的影响是如此巨大：不仅是软件如何写，而且关于我们对于问题解决的思考。

大多数应用是通过在不同层级堆叠数据模型构建的。对于每层关键问题是：如何在下一层表现它？比如：

  1. 作为一个应用开发者，你看到了真实世界（有人，组织，商品，行为，货币流，传感器等），然后通过对象的数据结构来建模它们，并通过 APIs 来操作它们。这些结构通常是应用特定的
  2. 当你想要存储这些数据结构时，你可以使用通用数据模型表达，比如JSON或者XML，关系型数据库中的表，或者图模型
  3. 你的软件数据库决定了你的数据使用第2点中提到的哪种数据模型存储在硬盘上。然后通过不同的方式来对数据进行查询，索引，操作和处理。
  4. 在底层，硬件工程师已经解决了如何在电流，光脉冲，磁场中表示字节

在一个复杂的应用中可能有更多的内部层级，比如在 APIs 上构建 APIs，但是基本思想是相同的：每一层都通过提供一个干净的数据模型隐藏了下面层的复杂性。这些抽象允许不同的人群--比如，数据库工程师和应用开发者一起高效使用数据库

存在很多不同类型的数据模型，每种都体现了如何使用的假设。某种用法很容易，有些不支持；一些操作很快，有些很差；有些数据转换很自然，有的很丑陋。

掌握一种数据模型就要花费大量精力（想想看有多少本介绍关系数据模型的书）。构建软件是困难的，即使只使用一种数据模型并且不考虑内部如何工作。同时数据模型的选择又对软件能做什么不能做什么有着巨大影响，应用关于数据模型的选择是如此重要

在本章我们将要讨论一系列通用数据模型以及查询。尤其是，我们比较关系模型，文档模型以及少部分图模型。我们将讨论一些查询语言并对比它们的使用。在第三章，我们讨论存储引擎如何工作，详细说明了数据模型如何实现。

Relational Model Versus Document Model

当今最知名的数据模型是 SQL，基于 Edgar Codd 在 1970 年提出的关系模型：数据被组织成关系（ SQL 中称为 table），每组关系时无序的 tuple 集合（SQL 中称为 row）

关系模型是作为理论被提出来的，当时很多人怀疑这种模型能否被高效实现。但是在20世纪80年代中期，RDBMS 和 SQL 已经成为人们存储和查询数据的首选。关系数据库的主导地位持续了 25-30 年，在计算机历史上是不朽的

关系数据库的根源是20世纪6,70年代的大型机上执行的业务数据处理。从今天的角度看：经典的事务处理（销售，银行交易，航空公司订单，仓库中的股票保留）和批处理（发票，工资单，报告）

其他数据库强制应用开发者思考数据库中的数据表示。关系模型的目标就是将实现细节隐藏于清晰的接口后

多年来，数据存储和查询一直处于很活跃的状态，在20世纪70年代和80年代早期，网络模型和层级模型是主要替代者，但是最终关系模型胜出。对象数据库在20世纪80年代末期和90年代初再次回归。在2000年出现了 XML 数据库，但是应用范围很窄。每个竞争对手都会发起挑战，但是最终都是关系模型胜出。

随着计算机越来越强大，并且联网，数据库被用于更多的目的。关系型数据库开始延伸到业务数据处理和批处理之外的领域。今天你看到的 Web，在线发布，讨论，社交网络，电子商务，游戏，SaaS产品，大多数也是由关系型数据库支撑的

The Birth of NoSQL

现在，21世纪10年代，NoSQL 是推翻关系型数据库的最新尝试，NoSQL这个名字是不幸的，因为实际上没有引用任何特定的技术--他最初是 Twiiter 在一次开源，分布式，非关系型数据库会议上提出的。尽管如此，这个名词还是循序传播到 Web 的各处。现在很多有趣的数据库都关联了 #NoSQL 标签，而且被引申为 Not Only SQL

NoSQL 数据有几种驱动力，包括：

  • 比关系型数据库更好的可扩展性，包括非常大的数据集或者很高的写吞吐
  • 很多开源免费软件超过了商业软件
  • 有些特殊的查询操作不被关系型数据库支持
  • 关系模式的限制，对于更多动态和表现力数据模型的追求

不同的应用有不同的要求，对一种场景的技术选择不适用另一种场景。因此，在可预见的未来，关系数据库与非关系数据库会一直一起使用。

The Object-Relational Mismatch

今天的大多数应用由面向对象语言开发，这导致 SQL 数据模型有一个共有的问题：如果数据存储在关系表中，需要一个丑陋的转换层将对象转换为表的 row，或者转换回来。模型间的关系有时被称为阻抗匹配

Object-relational Mapping(ORM) 框架减少了转换层所需的样板代码量，但是无法完全隐藏两种模型之间的差异

比如，图 2-1 表明简历可以存储为关系模式。这份建立可以由唯一的 user_id 确定。像 first_name last_name 等字段只会出现一次，所有可以保存在 users 表中，但是大多数人有多个工作经历，并且可能有不同的教育经历，以及不等数目的联系方式。这些项目存在单对多的关系，可以以不同的方式表达：

image-20210705203147234

  • 在传统 SQL 模型中，最常用的方法是正则化表达，将工作经历，教育经历，联系方式分别放在单独的表中，然后关联到 users 表的外键，如图 2-1 中表示
  • SQL 更高的版本增加了对结构化数据类型和 XML 数据的支持；这允许将多值数据存储在单行中，并支持在这些文档中进行查询和索引。Oracle、IBM DB2、MS SQL Server 和 PostgreSQL 都在不同程度上支持这些特性。一些数据库也支持 JSON 数据类型，包括 IBM DB2、MySQL 和 PostgreSQL。
  • 第三个选择是编码工作经历，教育经历和联系方式为 JSON 或者 XML 文档，然后存储在数据库中为 text 列，然后应用在解析内容。这种方法，显然你不能使用数据库的查询。

对于简历这样的数据结构，是自包含文档，JSON相当适合，如下：

{   
  "user_id":     251,   
  "first_name":  "Bill",   
  "last_name":   "Gates",   
  "summary":     "Co-chair of the Bill & Melinda Gates... Active blogger.",   
  "region_id":   "us:91",   
  "industry_id": 131,   
  "photo_url":   "/p/7/000/253/05b/308dd6e.jpg",
  "positions": [     
    {"job_title": "Co-chair", "organization": "Bill & Melinda Gates Foundation"},     
    {"job_title": "Co-founder, Chairman", "organization": "Microsoft"}   
  ],   
  "education": [     
    {"school_name": "Harvard University",       "start": 1973, "end": 1975},     
    {"school_name": "Lakeside School, Seattle", "start": null, "end": null}  
  ],   
  "contact_info": {     
    "blog":    "http://thegatesnotes.com",     
    "twitter": "http://twitter.com/BillGates"   
  } 
}

一些开发者认为 JSON 模型降低了应用代码和存储层的阻抗匹配。然而，JSON也存在数据编码格式的问题。缺乏模式通常被引用为优势。

JSON 表示有更好的局部性，当你想要从关系型存储中拉取一份简历时，需要执行多次查询。JSON 表示，所有相关数据都存储在一起，一次查询搞定

单对多关系可以表示为树状，JSON 使得这种结构更清晰

image-20210705212108563

Many-to-One and Many-to-Many Relationships

上面的 json 例子中居住地使用id，是为了减少重复，但是 id 到人类可读的地名映射需要 join 到查询中，通常文档型数据库对 join 的支持比较弱，这是多对单的关系。如果数据库不支持 join，这部分开发量就转移到了应用代码中，通常需要多次查询，本例中地区的列表比较少，应该还不是什么大问题。

但是即使原始版本的应用很适合没有join的文档模型，数据都有内部不断连接的趋势。比如，考虑我们的简历例子

  • 组织和学校改为对应的网站连接
  • 互相写推荐信

下图表明，这些新特性需要多对多关系

image-20210705213326688

方块可以归类为某个文档，但是组织，学校的引用，以及互相的推荐，都是引用，并且查询时需要 join

Are Document Databases Repeating History?

多对多关系重新引发了人们对于数据如何表示的讨论，是关系数据库，文档数据库，还是 NoSQL 数据库。但是这种讨论实际比 NoSQL 早多了，事实上，需要回溯到计算机数据库系统早期

20世纪70年代对于业务数据处理最知名的数据库是 IBM 的 IMS，首次发布于 1968年。今天仍然在 OS/390 中使用

IMS 的设计使用了相当简单的数据模型，层级模型，类似JSON，将数据表示为树形嵌套结构

如同文档数据库，IMS 对于 单对多关系处理的很好，但是难以处理多对多关系，不支持 join。开发者不得不考虑复制数据多份到各处，这个问题很像现在人们对于文档数据库的质疑

为了解决层级模型的限制，多种方案被提出。最突出的就是关系模型（占领世界）和网络模型，两个阵营的伟大争论在20世纪70年代一直持续。

由于这两个模型所解决的问题在今天仍然如此重要，因此在今天的情况下，值得简要回顾一下。

network model

是对层级结构的延展，层级结构中，每个 record 有一个父亲，但是在网络模型中，每个 record 有多个父亲。

网络模型中的 record 之间的链接不是外键，更像是编程语言中的指针。

the relational model

comparison to document databases

Relational Versus Document Databases Today

Query Languages for Data

Declarative Queries on the Web

MapReduce Querying

Graph-like Data Models

Property Graphs

The Cypher Query Language

Graph Queries in SQL

Triple-Stories and SPARQL

The Foundation: Datalog

Summary

数据模型是个相当大的主题，本章中我们快速浏览了几种不同的数据模型。没有对每种数据模型进行详细展开，但是希望概述已经可以帮助你发现更多模型信息使之更好的适配你的应用要求。

从历史上看，数据开始表示为一个大树（分层模型），但这对表示多对多关系不利，所以关系模型被发明来解决这个问题。最近，开发者发现一些应用不适合使用关系模型，新的非关系型 "NoSQL" 数据存储主要向两个方向发展：

  1. 文档数据库，目标场景是数据来自与自包含的文档，文档之间关系很弱
  2. 图数据库，与文档数据库相反，数据之间的联系更重要

这三种模型（document, relational, graph）今天都被广泛应用，每种都有自己的杀手场景。一种模型可以模拟为另一种模型，比如，图数据可以存储在关系数据库中，但是结果通常比较丑陋。这就是我们需要不同系统的原因，没有统一的解决方案。

文档和图数据库的共同点是不强制它们存储数据的 schema，使得应用适配更新更容易。但是，你的应用还是假设数据有一种结构；只是 schema 是显式还是隐式的问题。

每种数据模型都有自己的查询语言和框架，我们讨论了集中例子：SQL，MapReduce，MongoDB 的聚集 pipeline，Cypher，SPARQL，和 Datalog。我们还涉及了 CSS 和 XSL/XPath，不是查询语言但是有相似之处。

尽管我们涉及了很大的范围，但是还有很多数据模型我们没有讨论到。这里给一个简单例子：

  • 基因数据的研究者需要执行序列相似度查询，意思是有一个非常长的字符串（表示基因序列），然后从很大的字符串数据库中挑选出与之最相似的一个，但是不能相同。没有现存的数据库可以处理这种操作，所有研究者开发了这种数据库，比如 GenBank
  • 粒子物理学家数十年一直进行大数据规模的数据分析，像大型强子对撞机这样的项目需要处理数百 PB 级别的数据！这样的规模下，需要定制解决方案来防止硬件成本无限上涨
  • 全文检索也是一种常见的数据模型。信息检索是一个大型专业主题，我们不会在本书中详细介绍，但是我们会在第三章涉及到搜索索引

我们不得不先暂停这个话题了。在下一章中，我们将要讨论在实现本章讨论数据模型时的权衡。

如果你保持事务的有序性，你就懒得去寻找 -- German proverb

在最共有的常识层面上讲，数据库需要做两件事：存储你的数据，当你需要时将数据给你。

在第 2 章我们讨论了数据模型和查询语言--即你给数据库的你的数据格式，以及你如何查询到你存储的数据。本章中，我们继续延续这个视角讨论：我们如何存储数据，以及如何检索到它。

为什么一个应用开发者需要关系数据库内部如何存储和检索数据？你可能不会实现自己的存储引擎，但是你肯定需要从多个存储引擎中挑选适合自己应用的。为了针对你的业务负载调优存储，你需要更深入的了解存储引擎。

尤其是，在优化事务和分析方面，存储引擎的差异是巨大的。我们在稍后的"事务处理或者分析？"一节讨论，然后在 "Column-Orented Storage"讨论一系列为了分析优化的存储引擎

然后，本章让我们首先来讨论你很熟悉的存储引擎：传统关系型数据库，以及 NoSQL 数据库。我们将要讨论两种存储引擎家族：log-structured 存储引擎， page-oriented 存储引擎比如 B-tree

数据结构使能你的数据库 (Data Structures That Power Your Database)

考虑最简单的数据库，使用两个 Bash 函数实现 :

#!/bin/bash

db_set() {
	echo "$1,$2" >> database 
}

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

这两个函数实现了一个 key-value 存储。你可以调用 db_set key value，就可以将 key 和 value 存储到数据库。key 和 value 可以是任何类型--比如，value 可以是 json 文档。然后你可以调用 db_get key，可以检索到对应 key 的最新的 value 返回。

比如下面的流程

$ db_set 123456 '{"name":"London","attractions":["Big Ben","London Eye"]}'
$ db_set 42 '{"name":"San Francisco","attractions":["Golden Gate Bridge"]}'
$ db_get 42
{"name":"San Francisco","attractions":["Golden Gate Bridge"]}

底层的存储格式非常简单：文本文件一行包含一个 key-value 对，通过逗号分隔（类似 csv 文件）。每次db_set的调用都会追加在文件末尾，即使你更新 key 的 value，老版本的 value 也不会被覆盖--你需要查看文件中 key 对应的最新的 value

$ db_set 42 '{"name":"San Francisco","attractions":["Exploratorium"]}'
$ db_get 42
{"name":"San Francisco","attractions":["Exploratorium"]}
$ cat database
123456,{"name":"London","attractions":["Big Ben","London Eye"]} 
42,{"name":"San Francisco","attractions":["Golden Gate Bridge"]} 
42,{"name":"San Francisco","attractions":["Exploratorium"]}

我们的db_set函数如此简单而且高性能，因为在文件末尾追加效率很高。类似db_set做的事情一样，很多数据库内部使用 log，就是一个只追加的数据文件。生产环境的数据库更多的还要处理比如并发控制，回收硬盘空间，log 不能一直增长，错误处理，部分写入记录等问题，但是基本原理是相同的。Log 是非常有用的，我们将在本书的其余部分经常提到

*log *通常表示应用的日志，描述应用行为的文本记录。在本书中，log 更多的表示这样的场景：一个只追加的 record 序列。不一定有对人类友好的可读性，可能是二进制或者只会被其他程序读取

另一方面，我们的db_set函数性能又很差，如果你在数据库中有巨量的数据的话。每次你检索一个 key，db_get要扫描整个数据库文件，找到 key 出现的位置。在算法角度，这个检索的复杂度是 O(n)：如果你的数据量成倍增长，检索时间也会成倍增长。

为了更有效率的检索特定的 key，我们需要另一个数据结构：index（索引）。在本章中，我们将会探讨一系列的索引结构，然后对比它们。它们背后共同的思想就是维持一些额外的 metadata，来像路标一样帮助你定位你要检索的数据。如果你想要通过不同的方法检索相同的数据，你可能需要为这份数据建立不同的索引

索引就是建立于你的数据的额外结构。很多数据库允许你建立和移除索引，同时不会影响到数据库的数据，只会影响检索的效率。建立额外的数据结构意味着增加开销，尤其是写入开销。对于写入来说，很难超越直接追加文件的性能，因为是最简单的写入操作。任何类型的索引通常会减慢写入，因为每次写入数据都要更新索引

这在存储系统中时一个重要的权衡：良好的索引可以加速查询，但是每个索引都会降低写入性能。因此，数据库默认不建立索引，而是要求你--应用开发者或者数据库管理员选择如何建立索引，来适用于你的应用的特定查询。你就可以为自己的应用选择最适合的索引建立，又不会引入过多的写入开销。

Hash Indexes

让我们首先讨论 key-value 数据的索引。这不是仅有的可以索引的数据类型，但是很常见，而且对于更复杂索引的子块。

key-value 存储非常类似于你可以在大多数编程语言中看到的字典类型，其通常使用 hash map（hash table）实现。hash map 很多算法书中都有描述，所以这里不展开。所以我们已经在内存有了 hash map，为什么还要在硬盘中建立数据的索引

假设我们的数据文件如同上文所述，是只追加的文件。最简单的建立索引的策略是：在内存的 hash map 中维护 key-file offset 的数据。当你新追加数据到数据库中时，还要更新内存中的 hash map。检索数据时，先查内存的 hash map，然后按照得到的 offset 直接读文件即可

如下图所示

image-20210325172644811

这听起来可能很简单，但是是一种可行的办法。实际上，这基本就是 Bitcask （Riak 的默认存储引擎）。Bitcask 提供了高性能读写，但是要求 key 尽可能小能在 RAM 存储，因为 hash map 全部保持在内存中。值可以用比内存更多的空间，因为可以从硬盘中加载。如果数据文件在文件系统的 cache 中，读操作都不需要硬盘 I/O

Bitcask 存储引擎适合频繁更新的场景。比如，key 是一个猫片的 url，value 是播放次数。这个场景中，写入次数太多，而且没有很多 key，每个 key 都要大量写入，就很适合使用 Bitcask

上文中，我们将所有数据追加到一个文件中，所以如何避免撑爆硬盘空间？一个好的解决方案是通过将达到一定大小的文件 close，然后新 open 一个文件继续操作。然后我们可以在关闭的文件上执行 compaction 操作，如下图所示。Compaction 意味着丢弃 log 中的重复 key，只保持最新的 value 行

image-20210325173501283

此外，compaction 通常会是段文件变小（假设一个 key 会在一个段文件中重复几次），因此我们还可以合并几个段文件，如下图所示。段文件在写入到硬盘后不会发生变更，所以合并后的段文件要写到新的文件中。merge 和 compaction 的操作可以在后台线程中完成。前台线程可以使用老的段文件正常服务。在 merge 过程完成后，将读请求切换到合并后的段文件中即可，老的文件可以被删除

image-20210325173837859

图 3-3

每个段文件有自己的内存 hash map，其中存储了 file offset，为了检索到 key 的 value，首先要查看最新的段 hash map，如果 key 不存在，查第二新的段，如此等等。合并过程可以保持段数量较小，所以这个过程不会遍历很多 hash map

想把这个简单的想法实现需要考虑很多细节。这里简单罗列了一些实现时的重要问题：

  • File format CSV 不是 log 的最好格式。将其编码为二进制格式更快更简单
  • Deleting records 如果你想删除一个 key-value 对，只需要追加一个特殊的删除记录到数据文件中（有时被称为 tombstone）。当 log segments 被合并时，tombstone 告诉合并线程这是被删除的 key-value
  • Crash recovery 数据库进程重启，内存中的 hash map 就会丢失。原则上，你可以从所有 segment file 中恢复出 hash map，但是如果数据文件巨大这会消耗太长时间以至于数据库不可用。Bitcask 通过存储 hash map 的快照到硬盘来加速恢复过程，可以直接加载到内存中
  • Partially written records 数据库可能任何时刻 crash，包括在 log 中追加写中途。Bitcask 文件包括 cheksums，可以检测出未完成记录
  • Concurrency control 因为要写入以严格顺序追加到 log，最常见的实现时只有一个写入线程。数据文件段要不是可追加状态，要不是不可变状态，所以可以被多个线程读

猛地一看，只追加的 log 很浪费：为什么不能原地更新文件，使用新值覆盖老值？但是追加的设计是由于以下原因：

  • 追加和 segments 合并都是序列写操作，比随机写快很多，尤其是 HHD 硬盘上。在某种方面，在 SSD 上顺序写也是可取的，在稍后的 Comparing BTrees and LSM-Trees 中讨论这个问题
  • 并发和故障恢复更简单。比如，你不用担心在覆盖过程中的故障，不会存在一半老一半新的值
  • 合并过程避免了数据文件不断发散的问题

但是，hash tables 索引有几点限制：

  • hash tables 必须在内存中，如果你有非常大的 key，GG。原则上，你可以将 hash map 建立在硬盘上，但是硬盘上操作 hash table 性能很差，因为其需要大量随机读写，当硬盘变满时会更慢，而且还需要避免 hash 碰撞
  • 范围检索效率不高。比如如果要 scan kitty00000 到 kitty99999 的 key，你需要 look up hash table 中的所有 key

下一节我们来讨论一些没有这些限制的索引结构

SSTables and LSM-Trees

在图 3-3 中，每个 log-structured 存储 segment 是序列 key-value 对。这些对顺序就是写入顺序，相同 key 的顺序很重要，后面的 value 更新，键值对之间的顺序无关紧要。

现在我们将这个结构改一下：要求 key-value 对的顺序是根据 key 排序的。乍一看，该要求似乎打破了顺序写入的能力，但是不会的。

我们称这种格式为 Sorted String Table 或者 SSTable。我们还要求每个 key 在已经合并过的 segment 文件里只出现一次（这个在合并过程中保证了）。*SSTable *相比 hash 索引的 log segments 有几个巨大的优势：

  1. 合并 segment 简单效率，即使文件比可用内存还大。这个方法就像归并排序算法，下图是示意图：依次读取输入文件，对比每个文件的第一个 key，拷贝最小的 key 到输出文件，然后重复这个过程。输出的合并后的 segment file，也是按照 key 排序的 image-20210325210446129 如果多个输入文件中存在相同 key 怎么办？请记住，每个 segment 包含了一段时间数据库的所有值，这意味着一个文件里的所有值一定新于老文件的所有值，所以如果有多个 segment 包含相同 key，选择最新的文件中的记录，老文件的都可以丢弃
  2. 为了检索文件中特定 key，你不需要在内存中维护所有 key 的索引。看下图：比如你在检索 key handiwork, 但是不知道这个 key 的 segment file offset。然而，你知道 handbag 和 handsome 的 offset，因为是排序的，所以 handiwork 一定在这两个 key 中间。这意味着你可以从 handbag 的 offset 开始搜索 image-20210325212359453 你仍然需要内存索引来告诉你一些 key 的 offset，但是可以是稀疏的，一个 segment file 每隔几千字节一个 key 就足够了，因为少量的遍历也很快
  3. 由于读请求无论如何都需要在请求范围内扫描多个 key，因此可以将一组 record 作为 block，压缩写入硬盘（图 3-5 中的阴影部分）。然后稀疏的内存索引的每个 entry 都在压缩块的起始点。除了节省硬盘空间，压缩还可以降低硬盘 I/O 带宽的使用

Constructing and maintaining SSTables

但目前为止不错--但是如何在开始就将数据按 key 排好序？到来的写入可以是任何顺序。

在硬盘上维护一个排序结构是可能的（参见下面"B-Trees"一节），不过在内存中维护更为容易。有很多树结构供你选择，比如红黑树或者 AVL 树。使用这些数据结构，你可以任意顺序插入 key，然后按序读取

现在我们可以是存储引擎如下工作：

  • 写入到来，将其加入内存的平衡树结构（比如，红黑树）。这个内存中的树也被称为 memtable
  • 当 memtable 大小超过阈值，写入硬盘的 SSTable 文件。这个操作效率很高，因为树结构已经保证了按 key 排序。新的 SSTable 文件称为数据库最新的 segment。当 SSTable 被写入到硬盘，新的写入请求被加到新的 memtable 实例
  • 为了服务读请求，首先在 memtable 中查找 key，然后再最近的硬盘 segment，依次查找。
  • 从始至终，后台都会运行 merge 和 compaction 进程合并 segment 文件以及丢弃应该删除的 value

这个方案非常好。只有一个问题了：如果数据库崩溃了，最近的写入（在 memtable 中但是没有写到硬盘）就丢了。为了解决这个问题，我们可以单独维护一个 log，每次写入马上写到硬盘上，就像最开始那样。这个 log 不是排序的，但是无所谓，因为只是为了数据库崩溃后恢复 memtable。每次 memtable 落盘到 SSTable，对应的 log 就可以被丢弃

Making an LSM-tree out of SSTables

这里描述的算法本质上是 LevelDB 和 RocksDB，key-value 存储引擎中使用的，作为库为嵌入到其他应用中。除此之外，LevelDB 可用于 RIAK 作为 Bitcask 的替代品。类似的存储引擎还用于 Cassandra 和 HBase，都是受 Google 的 Bigtable 论文启发（其中介绍了 SSTable 和 memtable）

最开始这种索引结构是被 Patrik ONeil 在论文 *Log-Structtured Merge-Tree *中描述，建立了 log-structured 文件系统的早期工作。基于此论文中合并压缩有序文件的概念的存储引擎通常被称为 LSM 存储引擎

Lucene，全文检索的索引引擎，被 Elasticsearch 和 Solr 使用，使用了类似的方法存储它的 term dictionary。全文索引比 key-value 索引更加复杂，但是基于相似的想法：给一个 word 查询，找到所有包含这个单词的文档。可以通过 key-value 结构实现，key 是 word（term），value 是包含这个 word 的文档 ID 列表。在 Lucene 中，从 term 到 文档 id 列表的映射保存在 SSTable-like 的有序文件中，也需要后台进程合并。

Performance optimizations

一如既往，生产环境的存储引擎还需要很多细节填充。比如，LSM-tree 算法在检索不存在的 key 时效率很低：你要检索 memtable 和所有的 SSTable。为了优化这个过程，存储引擎通常使用额外的布隆过滤器来辅助完成这个过程。

还有不同的策略来决定何时 SSTables 进行压缩合并。通常有两个选项 size-tiered 和 leveled 压缩。LevelDB 和 RocksDB 使用 leveled 压缩（LevelDB 名字的由来），HBase 使用 size-tiered，Cassandra 同时支持。size-tiered 压缩，新而小的 SSTable 不断地合并到老而大的 SSTable 中。leveled 压缩，key 被分段成小的 SSTable，然后老数据被移动到单独的 level，可以使压缩过程是增量的，并使用更少的硬盘空间。

即使存在很多细节，LSM-tree 的基本思路是简单而且效率的--维护 SSTables，并在后台压缩合并。即使数据库数据远大于可用内存，也可以工作很好。而且因为数据是排序的，你可以高效执行范围检索，因为硬盘写入是顺序的，LSM-tree 可以支持很高的写入吞吐

B-Trees

到目前为止，我们讨论的 log-structured 索引正在被接受的阶段，但是它们不是最常见的索引类型。最广泛使用的索引结构是：B-tree

在 1970 年被发明，之后不到 10 年号称无处不在，B-tree 已经经历了时间的考验。他仍然是几乎所有关系型数据库的标准索引实现，并且很多非关系数据库中也使用它们

像 SSTables，B-trees 也按照 key 序排序 key-value，可以支持高效查询和范围检索。但是其余有很大不同，设计思路是迥异的。

我们之前讨论的 log-structure 索引将数据库切割为可变大小的 segment，通常是 MB 或者再大点，而且总是顺序写入。相反，B-tree 将数据库切割为固定大小的 block 或者 page，典型是 4KB（有时会大点），一次读写一 page。这种设计更加贴近底层硬件，硬盘也被划分为固定大小的 blocks

每 page 使用 address 表示，这可以允许一个 page 引用另一个 page，类似指针，但是在硬盘而不是内存中。我们可以使用这些 page reference 构造 page 的树，如图 3-6：

image-20210326111104300

一个 page 被指定为 B-tree 的根；无论你想要检索什么 key，都要从根开始。这个 page 包含几个 key 和一些孩子 page 的 reference。每个孩子负责连续的 key 范围，reference 之间的 key 明确了孩子 page 的边界

在图 3-6 中，我们查找 key 251，我们知道要在 key 200 和 300 之间找。所以我们去到孩子 page，然后知道要在 250 和 270 之间，直到到了叶子节点，叶子节点的 page 中没有 refernces，而是保存了 value。

一个 page 中孩子 page 的 reference 数量叫做 branching factor。比如，在图 3-6 中，branching factor 是 6。实际上，branching factor 取决于存储 page 的空间和范围边界，不过通常是几百。

如果你要在 B-tree 中更新一个已经存在的 key，你查找到包含这个 key 的叶子 page，然后在 page 中修改，写回 page 到硬盘中。如果想要新增一个 key，你需要找到包含在这个范围的 page，然后写进去。如果没有足够的空间容纳一个新的 key，会被分隔成两个半满的 page，然后再父 page 中更新 key 范围，如下图 3-7 所示：

image-20210326123707858

这个算法保证树是平衡的：n 个 key 的 B-tree 深度为 O(log(n))。大多数数据库的 B-tree 是三层或者四层，所以你在检索时不需要遍历太多 page reference。（四层的 4KB page 树，分支因子为 500，可以存储 250TB 内容）

书中提示，这里插入是符合直觉的，但是删除 key 为了保持树平衡，比较繁琐

Making B-trees reliable

B-tree 基本的写入操作是在硬盘上覆写 page。假定覆写 page 不会改变 page 的 location，当 page 被覆盖写的时候，所有的 reference 保持不变。这与 log-structured 索引比如 LSM-tree 完全不同。

你可以认为覆盖写 page 是真实硬盘硬件的一个基本操作。在 HHD 上，这意味着，硬盘头移动到正确位置，等待旋转磁盘到正确位置，将新数据写入到适当的扇区。在 SSD 上，由于 SSD 一次必须重新很大的一块 block，这反而变得更复杂了。

此外，某些操作需要几个不同的 page 被覆盖写入。比如，如果你由于插入操作要拆分一个 page，并更新父 page 的 reference。这是危险的操作，因为如果数据库在只写了两个分离 page，没有更新父 page reference 就崩溃了，你得到了有问题的索引（比如，可能有一个没有父 page 的孤儿 page）

为了使数据库应付崩溃，通常 B-tree 实现中会包含一个额外的数据结构：write-ahead log(WAL, 也被称为 redo log)。这是只追加的文件，每次 B-tree 的更改之前都会马上记录到 WAL。当数据库从崩溃中恢复时，可以使用 log 将 B-tree 恢复到之前的一致状态。

原地更新 page 的另一个问题是并发控制，如果多个线程要同时访问 B-tree，其中线程会不会查看到不一致的状态。这个问题的方案通常使用 latch 来保护树结构。而 Log-structure 方式就比较简单，因为在后台进行合并，而不会直面查询请求，不断原子地使用新 segment 替换旧 segment。

B-tree optimizations

B-tree 已经存在很久了，多年来已经有了很多优化，这里列举几个：

  • 不覆盖写 page，也不维护 WAL 来应对崩溃恢复，有些数据库（比如 LMDB）使用 copy-on-write 方案。修改后的 page 被写到不同的 location，新的父 page 在树中创建，指向新的 location。这个方法也有利于并发控制，我们将会在 "Snapshot Isolation and Repeatable Read"
  • 我们可以通过不直接存储 key-value，压缩来节省空间。尤其是树的内部 page 节点，key 只是用来提供足够的信息来划分查询范围。将更多的 key 打包到 page 可以提高分支因子，使得层数更少【这个变体通常称为 B+ tree】
  • 通常，page 可以是硬盘的任意位置；没有严格要求相邻的 key page 要在硬盘上也相邻。如果查询需要扫描大量的有序 key，一页一页的读效率很低，因为每次都会重新寻道。因此很多 B-tree 实现试图将叶子节点按顺序放在硬盘的相邻位置。但是，在树增长下，一直维护这个特性很难。相反，因为 LSM-tree 在合并过程重写大的 segment，很容易保持相邻 key 保存在硬盘相邻位置
  • 添加额外的指针到树中。比如，每个叶子节点也连接它的兄弟节点，这可以不用跳回父 page 来扫描 key
  • B-tree 变体比如 fractal tree 借鉴了很多 log-structrue 的思想来减少磁盘寻道次数

Comparing B-trees and LSM-Trees

即使 B-tree 的实现相比 LSM-tree 要成熟很多，LSM-tree 的性能也很受关注。原理上，LSM-tree 对写入更友好，B-tree 对读取更友好。在 LSM-tree 上读取更慢，是因为要检查不同的数据结构，以及所有压缩后的 SSTable。

然而，benchmark 通常需要绑定特定的工作场景。你需要针对你特定的业务流测试系统得到确切的孰优孰劣。本节偶尔们将要讨论在测试存储引擎性能时要考虑的一些问题。

Advantages of LSM-trees

B-tree 索引必须写两次数据：一次写到 WAL，一次写到树本身。即使一次只修改一个 page 中的几个字节，也要覆盖写整个 page。有些存储引擎甚至会为了避免断电导致的部分更新覆盖写相同的 page 两次。

Log-structure 索引也会在压缩合并 SSTable 时多次写数据。这导致一次数据库写入会引起多次写盘，也被称为 write amplification。尤其在 SSD 上需要注意，在报废前只能写有限次。

在写负载重的应用中，数据库的性能瓶颈可能就是写盘速度。这种场景下，写扩大有直接的性能影响：存储引擎写盘越多，每秒的写入越少。

此外，LSM-tree 通常比 B-tree 有更高的写入性能，部分原因是一半的写扩大比较低（依赖存储引擎配置和工作负载），部分原因是顺序写入硬盘而不是覆盖写 page。这点在磁盘上体现的很明显，因为顺序写入比随机写快得多。

LSM-tree 可以更好的压缩，因此可以使用比 B-tree 更小的空间。B-tree 存储引擎会碎片化导致更多的空间浪费：当 page 被分离或者一些 row 不匹配 page 剩余空间，有些 page 中的空间不会被利用。因为 LSM-tree 不是 page-oriented 并且会周期重写 SSTable 消除碎片化，能更好的节省空间，尤其是 leveled compaction

在很多 SSD 上，固件内部使用 log-structure 算法将随机写入转换为顺序写入到底层存储片上，所以存储引擎的写模式影响不太明显。但是更低的写扩大和空间碎片的减少还是有利于 SSD 的使用：更紧凑的数据在有限的 I/O 带宽上实现更高的读写能力。

Downsides of LSM-trees

log-structure 存储的缺点是压缩合并过程有时会影响读写性能。即使存储引擎尽可能增量执行合并压缩，但是硬盘的资源是有限的，很容易发生请求需要等待硬盘完成昂贵的压缩操作。对于吞吐和平均响应时间的影响一般很小，但是偶尔查询的耗时会很高，而 B-tree 的时间就很确定

另一个问题是，压缩合并会引起很高的写存储：硬盘有限的写带宽需要初始化写（logging 和 flushing a memtable to disk）与压缩合并线程共享。当写一个空数据库时，所有的硬盘带宽用于初始化写，但是当数据库越来越大，很多带宽用于压缩合并。

如果写入吞吐很高并且压缩合并配置不好，就会发生压缩合并速度跟不上写入请求。这时，未完成合并的 segment 就会堆积知道撑满硬盘，读取效率也会迅速下降因为要遍历更多的 segment 文件。通常，基于 SSTable 的存储引擎不会限制写入速度，即使合并压缩跟不上，所以你需要特别关注这方面的监控。

B-tree 的优势是每个 key 只会在索引中存在一份，而 log-structure 存储引擎一般会存储多个 key 的副本。这就使得 B-tree 在提供强大事务性语义的数据库中很具有吸引力：在许多关系型数据库中，事务隔离使用范围 key 的锁来实现，可以直接在 B-tree 的索引中加锁。在第 7 章中我们更详细讨论这个问题。

B-tree 在数据库体系中地位非常稳固，长期以来对很多工作提供了良好的性能支持，所以不会发生短期内迅速消亡的事情。在新的数据存储中，log-structure 索引变得越来越流行。没有简单快速的方法来判断你使用哪种数据引擎更好，都依赖于真实的测试结论。

Other Indexing Structures

到目前为止，我们只讨论了 key-value 索引，这就像关系数据模型中的 primary key 索引。主键唯一确定了关系表中的一行，或者文档数据库中的一篇文档，或者图数据库中的一个点。数据库中的其他 record 可以由主键（或者 ID）关联起来，并且索引就是用于搞定这种关联。

还有经常用的二级索引。在关系型数据库汇总，你可以在相同的表中通过CREATE INDEX命令创建二级索引，通常对于执行 join 有很好的的效果。比如在第二章的图 2-1 中，你在 user_id列上有二级索引，从而你可以发现属于相同 user 在所有表中的所有行。

Storing values within the index

（译者增：）LSM-tree and B-tree references

https://stratos.seas.harvard.edu/files/stratos/files/dostoevskykv.pdf

https://www.scylladb.com/2018/01/31/compaction-series-leveled-compaction/

http://smalldatum.blogspot.com/2015/11/read-write-space-amplification-b-tree.html

https://github.com/facebook/rocksdb/wiki/Leveled-Compaction

https://zouzls.github.io/2016/11/23/LevelDB%E4%B9%8BLSM-Tree/

事务处理或者分析？(Transaction processing or Analytics?)

在业务数据处理的早期，对数据库的写入通常与发生的商业交易相对应：进行销售，向供应商下单，支付员工工资等。随着数据库的扩展，并不涉及货币交易的增加，事务一次却停滞不前，指的是一组交易的读取和写入

事务不必要有 ACID 特性。事务处理仅仅意味着允许客户端低延迟读写----与批处理任务不同。我们在第 7 章讨论 ACID 特性，在第 10 章讨论批处理

即使数据库开始用于许多不同类型的数据---博客的评论，游戏中的动作，地址簿中的联系人等，基本访问模式还是类似于处理业务交易。应用程序通常需要使用索引或者键来查询少量记录。记录的插入和更新基于用户的输入。因为这些应用程序是交互式的，因此这种访问模式被称为 online transaction processing(OLTP)。

然而，数据库也越来越多用于数据分析，这具有不同的数据分析。通常，分析查询需要扫描大量记录，仅读取每条记录的几列，然后计算汇总统计信息（比如计数，总和以及平均值）而不是返回原始数据给用户。比如，如果你的数据是销售交易表，则分析查询可能是：

  • 一月份我们每家商店的总收入是多少
  • 我们最近促销期间卖出的香蕉比平时多了多少
  • 哪个品牌的婴儿食品最常与 X 品牌的尿布一起购买

这些查询通常由业务分析师编写，有助于公司管理层作出更好的决策（业务职能的报告）。为了将这种使用数据库的模式与事务处理分开，被称为 online analytic processing(OLAP)。在 OLTP 和 OLAP 之间的区别并不总是很明确，但是下表列出了一些典型特征：

PropertyOLTPOLAP
主要读模式每个查询少量记录，通过键统计大量记录
主要写模式随机访问、通过用户输入低延迟写入ETL 或者时间流
优先被谁使用终端用户，通过 web 应用内部分析，为了决策支持
数据表征什么最新的数据一段时间的事件历史
数据库规模GB 或者 TBTB 或者 PB

首先，将相同的数据库用于事务处理和分析查询。事实证明，SQL 在这方面相当灵活：它对于 OLTP 类型的查询和 OLAP 类型的查询都适用。尽管如此，在 1980 年代和 1990 年代初，公司有一种趋势是停止适用 OLTP 系统进行分析，改为单独的数据库来分析。这个独立的数据库被称为数据仓库。

数据仓库

一个企业可能具有数十种不通的交易处理系统：为面向客户的网站提供动力的系统，实体商店中的销售（结账）系统，仓库中的库存跟踪，车辆路线规划，管理供应商，员工管理等。这些系统都是复杂的，需要一组人来维护，所以这些系统会彼此自动运行。

通常 OLTP 系统处理事务有很高的性能，很低的延迟，因为它们通常对于业务运营至关重要。数据库管理员因此密切保护他们的 OLTP 数据库。他们通常不愿意让业务分析人员在 OLTP 数据库上运行临时分析查询，因为这些查询开销很大，会扫描数据集的大部分，这可能会损害并发执行事务的性能。

相比之下，数据仓库是一个独立的，提供给分析人员查询关心内容的数据库，不会影响 OLTP 操作。数据仓库包含公司内各种类型 OLTP 数据库的数据副本。从 OLTP 数据库中提取数据，转换成易于分析的格式，清理，然后加载到数据仓库中。获取数据并放入数据仓库中的过程称为 Extract-Transform-Load (ETL)，如下图所示

image-20200922104602123

现在几乎所有大型企业都存在数据仓库，但在小型企业中几乎闻所未闻。这可能是因为大多数小型公司没有太多不同的 OLTP 系统，并且大多数小型公司具有的数据量不够规模，可以在常规 SQL 数据库中查询，甚至可以在电子表格中分析。在大型公司中，要做一些在小型公司很简单，但是规模大了之后比较复杂的事情。

一个不从 OLTP 系统直接分析，而使用分离的数据仓库最大的优势是，数据仓库可以为了分析访问模式优化。事实证明，本章上半部分讨论的索引算法对于 OLTP 效果很好，但是在分析查询方面不是很好。

在本章的剩余部分，我们将要看看存储引擎如何为了分析优化。

OLTP 数据库与数据仓库之间的差异

数据仓库的数据模型通常是关系型的，因为 SQL 通常非常适合分析查询。有很多图形分析工具可以生成 SQL 查询，可视化结果并允许分析人员（通过诸如 drill-down and slicing and dicing）浏览数据。

从表面看，数据仓库和关系型 OLTP 数据看起来相似，因为它们都具有 SQL 查询接口。但是内部相当不同，因为它们针对不同的查询模式进行了不同的优化。现在，许多数据库供应商都专注于支持事务处理或者分析工作负载，而不是同时支持两者。

某些数据库（例如 Microsoft SQL Server 和 SAP HANA），在同一产品中支持事务处理和数据仓库。但是，它们越来越成为两个独立的存储和查询引擎，它们可以通过公共 SQL 接口进行访问。

数据仓库供应商例如 Teradata，Vertica，SAP HANA 和 ParAccel 通常会以昂贵的商业授权出售系统。Amazon RedShift 是 ParAccel 的托管版本。最近，出现了许多开放源代码的基于 SQL 的 Hadoop 项目；它们都很年轻但是旨在与商业数据仓库竞争。其中包括 Apache Hive，Spark SQL，Cloudera Impala，Facebook Presto， Apache Tajo 和 Apache Drill。其中一些是基于 Google 的 Dremel。

星星和雪花：分析结构

如第二章所述，根据应用程序的需求，在事务处理领域中使用了各种不同的数据模型。另一方面，在分析场景中，数据模型的多样性要少得多。许多数据仓库都以相当公式化的方式（称为星型模式（也被称为dimensional modeling））使用。

下图展示了可以用于杂货店零售商的数据仓库。schema 的中心是 fact table（在这个例子中，是 fact_sales）。fact table 的每一行表示在特定时间发生的事件（这个例子中，每行表示客户购买产品）。如果我们在分析网站流量而不是零售量，则每行可能代表用户的页面浏览量或者点击次数。

image-20200922110502630

通常，将事实捕获为单个事件，因为这样可以在以后最大程度地灵活分析。但是，这意味着 fact table 可能会变得非常大。像 Apple，Walmart 或者 eBay 这样的大企业可能在数据仓库中拥有几十 PB 的交易历史记录，其中大多数实际上是 fact table。

fact table 中的某些列是属性，例如产品的销售价格和从供应商处购买产品的成本。其他列是对其他表的外键引用。由于 fact table 中每一行都代表一个事件，因此其他被引用的表表示事件的 who, what, where, when, who and why。

星型结构的命名来自以下事实：可视化表关系时，fact table 是中心，并由其维度表围绕；这些表格的链接就像星星放射光芒一样。

此模式的一种变体是雪花结构(snowflake schema)，维度表进一步细分为更细维度的表。比如，就不举例子了。雪花结构比星型结构更加规范化，但是星型模式通常是首选，因为星型模式更易于分析师使用。

在典型的数据仓库中，表通常是非常宽的：fact table 通常有超过 100 列，有时数百。维度表也可能非常宽，因为它们包含了可能与分析相关的所有元数据，例如 dim_store 表可能包括每个商店提供的服务的详细信息。

列式存储

如果事实表中有数万亿行，PB 规模的存储，那么有效的存储和查询它们将成为一个有挑战的问题。维度表通常小得多（几百万和行），所以我们将主要集中于事实表的存储。

尽管事实表通常大于 100 列，但是分析查询的典型查询一次只访问 4，5 列。

SELECT   dim_date.weekday, dim_product.category,   SUM(fact_sales.quantity) AS quantity_sold 
FROM fact_sales   
JOIN dim_date    ON fact_sales.date_key   = dim_date.date_key   
JOIN dim_product ON fact_sales.product_sk = dim_product.product_sk 
WHERE   dim_date.year = 2013 AND   dim_product.category IN ('Fresh fruit', 'Candy') 
GROUP BY   dim_date.weekday, dim_product.category;

如何高效执行这个查询？

在大多数 OLTP 系统中，存储以面向行的方式进行布局：表的一行所有值都彼此相邻存储。文档数据库是类似的：整个文档通常存储为一个连续的字节序列。

为了处理上面的 SQL 查询，你可能在 fact_sales.date_key 和/或 fact_sales.product_sk 上都有索引，这些索引告诉存储引擎在哪里可以找到特定日期或者特定产品的所有销售额。但是，面向行的存储引擎仍然需要将所有这些行（每个行都包含了 100 多个属性）从硬盘加载到内存中，进行解析，然后过滤掉不符合要求的条件。那可能要花很长时间。

列存背后的想法很简单：不按行存储，而是按列存储。如果每一列存储在单独的文件中，这个查询可能只需要读取用到的列，这可以节省很多工作。这个思路由下图( Figure 3-10)可以很好的表示

列存在关系型数据模型中很容易理解，但是在非关系数据中也可以有列存，比如基于 Google Dremel 支持文档数据模型的列存

image-20210510150021500

面向列的存储布局依赖于包含以相同顺序排列的行的每个列文件。因此，如果你需要重新组装整行，则可以从每个单独的列文件中获取第 23 个记录并放在一起形成表的第 23 行。

列压缩

除了只从硬盘加载必要的列数据到内存，我们还可以通过压缩数据减少硬盘吞吐。幸运的是，列存很适合压缩。

从上面的图 Figure3-10 中观察每列的数据：看起来有重复，这对于压缩来说是个好信号。根据列中的数据，可以使用不同的压缩技术。一种在数据仓库中特别有效的技术是 bitmap encoding，如图 Figure 3-11

image-20210510152953525

通常，与分行来说，列中的数据取值范围更小（举例来说，零售商可能有数十亿比交易，但是产品只有100000个不同的）。我们可以将 n 个不同的列值映射到一个 n 个不同 bitmap 上：每个列值一个 bitmap，每一位表示一行。bit 为1表示这一行有这个值，0表示没有

如果 n 非常小（比如，如果一列表示国家，那就200多个不同值），那么 bitmap 可以每行占用一个 bit。但是如果 n 非常大，在 bitmap 中可能会有很多0（稀疏的）。这种稀疏情况，bitmap 可以进一步编码，如同 Figure3-11 中最下面 Run-length encoding 的结果。这样的压缩比就很大了。

Bitmap index 非常适合数据仓库的查询，举例：

WHERE product_sk IN (30, 68, 69):
# 加载三个 bitmap， product_sk=30/68/69 ，位或计算，非常快速
WHERE product_sk = 31 AND product_sk = 3;
# 加载两个 bitmap， product_sk=3/31 ，位与计算

对于不同类型的数据，还有其他各种压缩方案，但是我们不会详细讨论他们，见[The Design and Implementation of Modern Column-Oriented Database Systems]的概述

Column-oriented storage and column families

Cassandra 和 HBase 有一个 column families 的概念，从 BigTable 继承的。但是称他们为 column-oriented 的是误导的：在每个 column family 下，它们存储一行的所有列数据，以及row key，不使用列压缩，所以，Bigtable 模型还是 row-oriented

Memory bandwidth and vectorized processing

对于数据仓库的查询来说，需要扫描数百万行数据，一个很大的瓶颈是从硬盘到内存的数据带宽。然而，这不是仅有的瓶颈。分析数据的开发者还会受到从内存到 CPU Cache 的带宽制约，avoiding branch mispredic‐tions and bubbles in the CPU instruction processing pipeline, and making use of single-instruction-multi-data (SIMD) instructions in modern CPUs。

不只能降低从硬盘加载数据的规模，列存还有利于高效利用 CPU 周期。比如，查询引擎可以将一块压缩的列式数据加载到 CPU L1 Cache 中，然后在没有函数调用的 loop 中迭代。CPU 可以执行这种没有函数调用的 loop 更快。列压缩可以让更多的列数据加载到 CPU L1 Cache中。操作符，例如位或，位与，可以直接在压缩列数据块上执行。这种技术被称为 vectorized processing

列存储中的排序

在列式存储中，行的顺序无关紧要。最简单的方法就是按照插入的顺序存储，插入新行只需要在每个列的文件后追加一个值即可。然而，我们可以强制指定一个顺序，就像我们之前在 SSTables 中做的一样，使用一个索引机制。

需要注意的是，单独对每个列排序没有意义，因为我们将不知道列中的数据属于哪一行。我们需要可以从一列的第 k 个数据与另一列的第 k 个数据重建一行。

还有就是，即使是通过列存储，一行的数据要同时存储。数据库管理员可以使用他们对于常见查询的了解来选择对表的哪些列进行排序。例如，如果查询经常以日期为范围，比如上个月，可以将 date_key 设置为第一个排序键。然后，查询优化器就可以只扫描上个月的行，比扫全表快很多

第二列可以确定在第一列中具有相同的值的行的排序顺序。例如，如果 date_key 是 Figure 3-10 中的第一个排序键，可以使用 product_sk 作为第二个排序键，就可以对同一天的同一产品的销售在存储中分组。可以加速查询。

另一个排序的优势可以辅助列压缩。如果主排序列没有很多不同值，在排序之后，编码为更高的压缩比，可以结合图 Figure 3-11 中的例子理解。

在第一个排序键上的压缩效果最强。第二个，第三个键更混乱，因此没有第一个键那么长的重复值序列。效果逐级递减知道跟随机差不多效果，不过第一个排序键的压缩效果通常就很不错了。

Several different sort orders

这个思想被引入到 C-Store 以及商业数据仓库 Vertica。不同的查询可以从不同的排序中获益，**所以为什么不将一份数据以多种顺序存储多份呢？**数据可以通过复制到不同的机器来防止丢失。同样的，可以按照不同顺序存储多份，当一个查询执行时，可以选择最适合这个查询的存储顺序的数据来执行查询。

在列式存储中保存多个排序的数据类似于行存中有多个二级索引。但是不同的是行存在同一个地方存储每行（heap file or a clusted index），二级索引只包含指向行的指针。列存中，就是值。

写入列存

这些优化在数据仓库中是有意义的，因为分析师运行的是只读的大型查询。列存，压缩，排序都可以使得查询加速。但是，也使得写入更困难。

在B-tree 中使用的 update-in-place 方法在压缩的列存中时不可用的。如果你想要插入一行到排序后的文件中间，你必须重写整个文件。由于在列中存储需要保存行的标识，插入必须一致性更新所有列。

幸运的是，在本章之前我们已经看到了一个很好的解决方案：LSM-tree。所有的写先存储在内存排序的 tree 中，准备写入磁盘。内存那种的数据不关心是行存还是列存。有足够的写入之后，合并到硬盘的列存文件中，然后写入对应的新文件。Vertica 就是这么做的

查询需要硬盘中的数据以及内存中的数据，不过查询优化器将这些细节对用户隐藏起来。从分析师的角度，数据就是直观的插入、更新、删除。

聚集：Data Cubes and Materialized Views

不是所有的数据仓库都是列存：也有传统的行存数据库或者其他的结构。但是，列存使得分析查询更快，所以在快速普及。

另一个数据仓库中值得一提的一点是固化聚集。如之前讨论，数仓中的查询经常使用聚集函数，比如 COUNT, SUM, AVG, MIN, MAX。如果相同的聚集在不同的查询中使用，每个都计算就很傻。为什么不缓存经常使用的聚集结果呢？

创建这个缓存的一个方法是 materialized view。在关系型数据模型中，通常定义为 standard(virtual) view：类似 table 的一个对象，包含了一些查询的结果。materialized view不同的是保存的是查询结果的一份拷贝，写入到硬盘，virtual view 只是保存了查询的快照，当从 virtual view 中获取数据，会展开查询重新执行一次查询。

底层的数据更新时，materialized view 也要更新。数据库可以自动执行更新，但是这使得写入开销昂贵，这也是为什么在 OLTP 数据库中没有 materialized view 的原因。在侧重读的数仓中，这可以更好的发挥作用

materialized view 的一种常见特殊 case 被称为 data cube 或者 OLAP cube。是不同维度的聚集的网格。Figure 3-12 展示了一个例子：

image-20210510163553003

假设 fact table 只有两个外键关联 dimension table，如同 Figure 3-12，是 date 和 product，你可以在横纵坐标轴上画出两个维度表，每个 cell 包含了一个聚集的属性，date-product 的组合。

通常，fact table 有超过两个维度表。在 Figure 3-9 中有5个：date, product, store, promotion, customer。很难在书上画出来，但是原理是相同的，每个 cell 包含了多维度组合之后的聚集属性。

meterialized data cube 的优势在于将结果保存下来，查询时就不需要计算。比如，如果你想要知道昨天每个store的sales求和，只需要查询到 cube 对应的结果，不需要扫描成千上百行数据来计算。

data cube 的劣势就是相对于原始数据灵活性不足。比如就没有办法计算cost > $100 的条件的查询，因为 price 不是维度。因此，大多数数仓也会保存原始数据，然后将 data cube 用于加速查询。

总结

本章中，我们试图深入了解数据库如何处理存储和检索。将数据存储在数据库中时会发生什么，以后再查询数据时数据库会做什么？

从高层次看，我们发现存储引擎分为两大类：针对事务处理（OLTP）优化的引擎和针对分析优化（OLAP）的引擎。在这些用例中，访问模式之间存在很大差异：

  • OLTP 系统通常是面向用户的，这意味着它们会看到大量的请求。为了处理负载，应用通常在每个查询中访问少量记录。该应用程序使用某些键来请求记录，存储引擎使用索引找到请求键的数据记录。磁盘寻道时间通常是这里的瓶颈。
  • 数据仓库和类似的分析系统鲜为人知，因为它们主要由业务分析人员而非最终用户使用。与 OLTP 系统相比，它们处理的查询量要少得多，但是每个查询的要求很高，需要在短时间内扫描数百万条记录。硬盘带宽（不是寻道时间）通常是这里的瓶颈，而面向列的存储是此类工作负载日益流行的解决方案。

在 OLTP 角度，我们看到了来自两个主要思想流派的存储引擎：

  • 日志结构的流派，仅允许附加到文件和删除过时的文件，而从不更新已写入的文件。Bitcask，SSTables，LSM 树，LevelDB，Cassandra，HBase，Lucene 等属于该组。
  • 就地更新流派，它将硬盘视为一组可以覆盖的固定大小的页面。B 树是这种哲学的例子，被用于所有主要的关系数据库以及许多非关系数据库中

日志结构的存储引擎是较新的发展。他们的关键思想是将随机访问写入转换为硬盘上的顺序写入，由于硬盘驱动和 SSD 性能特点而提高了吞吐量。

在 OLTP 讨论结束时，我们简要浏览了一些更复杂的索引结构以及为了将所有数据保留在内存中而进行了优化的数据库。

然后我们绕开了存储引擎的内部，以了解典型的数据仓库的高级体系结构。说明了为什么分析工作的负载与 OLTP 是如此不同：当你的查询需要顺序扫描大量行时，索引的就没什么用了。取而代之的是，紧凑的数据编码以最小化查询需要从磁盘读取的数据量变得很重要。我们讨论了面向列的存储如何帮助实现此目标

作为应用开发者，如果你具备有关存储引擎内部知识，那么你将可以更好地了解哪种数据库更适合你的应用程序。如果你需要调整数据库的参数，则可以通过这种理解来预测哪些参数会导致什么影响。

尽管本章不能让你成为特定数据库调优的专家，但是希望为你提供了足够的知识和建议，使你可以从所选数据库的文档中获得启发。

应用不可避免会随着时间而变化。随着新产品发布，用户需求更好被理解，或者业务环境的变化，增加特性或者修改特性。在第一章中我们介绍了演化的观点：我们应该在构建系统时考虑到系统方便修改。

在大多数场景中，对应用的功能变更也意味着存储的变化：可能需要新的字段或者记录类型，或者需要以新的方式表现数据。

在第二章中我们讨论了不同数据模型应对这种变化的方式。关系型数据库假设数据库中的所有数据符合一个 schema：即使 schema 也会改变（比如通过 ALTER 命令），在特定时间存在一个固定的 schema。相反，schema-on-read 数据库不会强制 schema，所以这种数据库中包含了新老格式数据的混合。

当数据格式或者 schema 改变，对应应用程序的代码需要修改（比如，增加一个字段，应用程序代码也要修改）。但是，在大型应用中，代码修改不会马上生效：

  • server端的应用你可能希望进行滚动升级，一次将新版本部署到一些节点，检查新版本是否运行良好，然后再对全部节点执行升级。这需要服务不停机升级，并且鼓励更频繁的发布，需要更好的演进性
  • client端的应用，用户可能并不会升级

这意味着新代码和老代码，新老数据格式会在系统中同时存在。为了系统持续运行，我们需要兼容：

  • Backward compatibility 新代码可以读老代码写的数据
  • Forward compatibility 老代码可以读新代码写的数据

向后兼容通常不难：新代码写的时候，是知道老代码是什么样的，所以直接实现兼容性。向前兼容可能会比较难，因为要求老代码忽略新代码。

本章我们讨论集中不同的编码数据格式，包括 JSON，XML， Protocol Buffers， Thrift 和 Avro。尤其是，我们要讨论它们如何处理 schema 变更，如何支持新老代码，新老数据同时存在。然后讨论将这些数据格式用于数据存储和通信：在 Web 服务，Representational State Transfer （REST），RPC，以及消息传递系统比如 actor 和 消息队列。

Formats for Encoding Data

程序中的数据表示至少两种：

  1. 内存中，数据表示为 objects, structs, lists, arrays, hash tables, trees等。这些数据结构对 CPU 访问做了优化
  2. 当你想写数据到硬盘或者通过网络发送，你必须将其编码成自包含的字节序列（比如，JSON 文档）。因为指针对其他进程没有意义，所以字节序列看起来与其在内存中的表示迥然不同

因此，我们需要两种表示之间的转换。从内存中表示到字节序列的转换称为 encoding（serialization or marshalling），反过来的过程称为 decoding（parsing, deserialization, unmarshalling）。

Serialization 同样用在了 transaction 的上下文中，但是具有完全不同的意义。为了避免疑义，本书中只用 encoding ，尽管 serializations 用的更多

因为这是一个很通用的问题，所以存在很多不同的库来解决。让我们先概览一下。

Language-Specific Formats

很多编程语言内建了序列化内存对象到字节序列的方法，比如Java 有 java.io.Serializable，Ruby 有Marshal，Python 有 pickle 等，也有一些第三方库，比如 Java 的 Kryo

这些序列化库很方便，可以用较少的代码完成。但是也有几个很明显的缺点：

  • 只能用于特定语言，使用另一种语言读取比较困难
  • 为了在相同的对象恢复数据，解码过程需要可以实例化 arbitrary class 【译者注：类似 Java 中的 Class】。这经常是安全问题的来源：如果攻击者获取你的应用然后从字节序列反序列化，他们可以实例化 arbitrary class，这就可以让他们做一些恶意攻击
  • 版本管理做得不好：由于做得比较简单，所以他们通常在数据前后兼容上做的不好
  • 效率通常一般

基于上述缺点，使用语言内建编码数据通常是个糟糕的选择

JSON, XML, and Binary Variants

多种语言读写方便的标准序列化，JSON 和 XML 。广为人知，广泛支持，同样的广泛为人诟病。XML 经常由于其冗余和过分复杂被人批评。JSON 的流行主要因为是 Web 浏览器内置支持（JavaScript 子集），以及相对于 XML 的简洁。CSV 是另一种语言无关的格式，但是能力不行

JSON，XML，CSV 都是文本格式，因此是人类可读的，除了语法问题，也有一些难以捉摸的问题：

  • 歧义。在 XML 和 CSV 中，你不能区分是数字还是数字组成的字符串。JSON 不区分数字和字符创，同样不区分整数还是浮点数，并且没有精度 处理大数的时候有问题；有些例子略
  • JSON 和 XML 对于 Unicode 表示支持很好，但是不支持二进制字符串。二进制字符串很有用，人们使用 Base64 将二进制字符串编码来规避这个问题。这样可行，但是增大了 33% 的数据规模
  • XML 和 JSON 都有可选 schema，这些 schema 语言很强大，因此也很复杂，学习难度也比较高
  • CSV 没有很多 schema，只是在应用中定义每行和列数据，语义相当模糊

尽管存在这些缺陷，JSON，XML 和 CSV 对于很多场景足够好，仍然很受欢迎，特别作为数据交换格式。在这些情况下，只要人们对于数据格式达成一致，通常数据的是否漂亮，性能是否高都不是很重要

Binary encoding

对于只在组织内部使用的数据，没有使用公共编码格式的压力。比如，你可以选择尽可能紧密而且快的编码。对于小的数据集，收益可能不明显，但是一旦数据量变大，数据格式的选择变得很重要

JSON 比 XML 简洁，但是相对于二进制编码都比较冗长。这个明显的事实引出了很多关于 JSON 的二进制编码（MessagePack, BSON, BJSON, UBJSON 等），XML 的（WBXML 和 Fast Infoset。这些格式已经在各处被使用，但是没有像 JSON 和 XML 本身一样广为人知。

这里关于 MessagePack 的详细展开略过

Thrift and Protocol Buffers

Apache Thrift 和 Protocol Buffers(protobuf) 都是基于相同原则的二进制编码库。PB 由 Google 开发，Thrift 由 Facebook 开发，都在 2007~08 年开源。

Thrift 和 PB 都要求数据 schema。比如下面的 Thrift 代码

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

PB 相等的代码为

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

Thrift 和 PB 都有各种语言的代码生成器。你的应用可以使用生成的代码来编码解码 records of the schema

编码过程是什么样？令人困惑的是，Thrift 有两种二进制编码格式，BinaryProtocol 和 CompactProtocol。我们首先看 BinaryProtocol。编码

{
  "userName": "Martin",
  "favoriteNumber": 1337,
  "interests": ["daydreaming", "hacking"]
}

为 59 字节如图 Figure 4-2

image-20210510210104831

每个 field 有一个类型注解（指出是字符串，整数，list 等），以及一个长度标识（数据的长度）。数据也被编码为 ACSII

没有数据名称，使用 field tags，只是数字。这些数字出现在 shema 定义中

Thrift CompactProtocol 语义上与 BinaryProtocol 是相等的，如图 Figure 4-3 ，将相同的信息更紧凑使得数据压缩到 34 字节。通过将 field type 和 tag number 打包到一个字节中，并使用变长整数来做到。比如数字 1337 不使用完整的 8 个字节，编码为两个字节，每个字节的顶部表示是否有更多字节。这意味着一个字节可以编码 -64 到 63 的数，-8192 到 8191 可以使用两个字节编码等，更大的数使用更多的字节。

image-20210510210549211

最后，PB 只有一种二进制编码格式，如图 Figure 4-4。关于PB的详情请点击这里。使用不同的方式压缩数据，类似于 Thrift CompactProtocol，PB 将数据压缩到 33 字节

image-20210510211118340

一个细节需要注意：在前面的 schema 中，每 field 被标注为 required 或者 optional，但是对于编码没有意义（就是编码中不会体现这个）。不同的 required 在运行时会检查，如果该 field 没有设置就会失败，容易发现 bug

Field tags and schema evolution

我们先前提到了 schema 可能会随着时间被修改。我们称为 schema evolution。Thrift 和 PB 如何处理这种兼容呢？

我们看到，编码后的 record 就是编码 field 的一连串字节。每个 field 通过 tag number，annotated with a datatype 标识。如果 field 没有被设置，简单省略。这里你可以看到 field tag 对于编码数据至关重要。你可以改变 field 的名字，因为编码的数据并不关联 filed 名字，但是不能改变 field tag，这将会使得现有的编码数据失效。

你可以加入新的 field，提供一个新的 field tag。如果老代码（不知道你新增的 field tag number）尝试读取新代码写的数据，这个新的 tag number 不被识别，简单的忽略过去。datatype 注解允许解析器知道多少字节被忽略。这样就建立起了前向兼容：老代码可以读取新数据

那么后向兼容呢？每 field 有唯一的 tag number，新代码可以读老数据，因为 tag number 意义相同。你只需要注意一个细节，不要加新的 require field.

删除一个 field 就像加入一个 field 一样，你只能删除一个 optional field，并且不能重复使用删除的 tag number。

Datatypes and schema evolution

可以改变一个 field 的 datatype 吗？可以的，仔细阅读文档就知道，但是这是有风险的，可能丢失精度或者截断数据。例如，将 32 位整数变为 64 位。新代码可以轻松读取老代码写的数据，因为解析器会自动填充0，但是老代码读到新代码的数据时，老代码还是认为是32位数据，64 位数据会被截断。

PB 的细节是没有 list 或者 arrary 数据类型，但是有一个 repeated 标记。如图 Figure 4-4，编码 repeated field 时，相同 field tag number 会出现多次。这有一个好的结果就是可以将 optional 改为 repeated。新代码读老代码就是一个或者零个数据；老代码只会读到新代码的最后一个数据

Thrift 有表明的 list 数据类型，使用列表元素的数据类型进行参数化。这就不能像 PB 一样将改变类型，但是有可以嵌套的优势

Avro

Apache Avro 是另一种不同于 Thrift 和 Protobuffer 的二进制编码。始于 2009 年的 Hadoop 一个子项目，由于 Thrift 不太适合 Hadoop 使用

具体介绍略

The Merits of Schemas

正如我们所见，Protobuffer， Thrift 和 Avro 都是用 shema 来描述二进制编码格式。他们的 shema 语言比 XML 和 JSON 更简单，并且支持更详细的检查规则。由于 PB，Thrift 和 Avro 易用易实现，所以对它们的支持在编程语言中很广泛。

这些编码基于的想法都不是新的，例如，它们与 ASN.1（于1984年首次定义的标准化序列化语言）有很多共同点。ASN.1 可以用来定义不同的网络协议，其二进制编码（DER）还被用于编码 SSL certificates（X.509）。ASN.1 使用 tag number 支持 shema evolution，PB 和 Thrift 与之类似。但是因为非常复杂并且文档很烂，ASN.1 对于新应用来说并不是很好的选择。

很多数据系统实现了专有的二进制编码。比如，大多数关系型数据库有网络协议。这些协议通常用于特定的数据库，数据库供应商提供驱动（例如，使用 ODBC JDBC API），从数据库的网络响应中解码为内存结构

所以，我们看到尽管文本格式比如 JSON，XML 和 CSV 广为传播，基于 schema 的二进制编码也是一个切实可行的选择，它们还有一些良好性质：

  • 相比二进制 JSON，有更好的压缩比
  • schema 是一种有价值的文档形式，因为需要解码，你可以确定它是最新的（手动维护的文档很容易与现实发生分歧）
  • 更好的前后兼容性
  • 对于静态语言用户，从 schema 生成代码很有用，可以在编译器检查类型

总之，schema evolution 得到 schemaless/schema-on-read JSON 数据库提供的相似的灵活性，并且为你的数据提供了更好的保证和工具。

Modes of Dataflow

本章开始，我们说，无论何时你想要将一些数据发送给另一个没有共享内存的进程--比如，通过网络发送数据，或者写入文件--你需要将其编码为字节序列。然后我们讨论了不同的编码方式.

我们讨论了前后向兼容性，对于演进能力非常重要（可以方面的升级系统，而不用做过多修改）。兼容性就是一个进程编码，另一个进程可以解码。

这是个相当抽象的思想---有很多方法将数据从一个进程传递到另一个进程。谁编码数据，谁解码数据？在本省剩余部分，我们介绍最通用的集中传递数据方法

  • 通过数据库
  • 通过调用
  • 通过异步消息传递系统

Dataflow Through Databases

Dataflow Through Services: REST and RPC

Message-Passing Dataflow

Summary

本章中，我们讨论了几种将数据结构转化为网络或者硬盘字节序列的方法。我们看到这些编码细节不仅会影响它们的效率，更重要的是，也影响应用和你的部署选项。

特别地，很多服务需要支持滚动升级，新版本部署一部分节点，而不是同时部署到所有节点。滚动升级允许在服务不停机的情况下升级服务，并使部署风险降低。这些属性对于演进性非常有益，使得应用的变更更加简单

在滚动升级过程中，或者其他的原因，我们必须假设在不同的节点运行着不同版本的代码。因此，系统中数据编码的兼容性也很重要。

我们讨论了几种数据编码格式和它们的兼容性：

  • 特定语言提供的编码方法，一般兼容性很差
  • 文本格式，比如 JSON，XML，CSV。兼容性依赖于你怎么使用它们。有可选的 schema 语言，有些情况有用，有些反而没用。这些格式对于数据类型是含糊的，所以你需要特别注意字符串和数字类型
  • 二进制 schema-drivern 格式，比如 Thrift，PB 和 Arvo，可以编码的同时压缩数据，并且有很好的语义兼容性。可以生成静态语言的代码。但是，它们也有缺点，就是可读性差

我们还讨论了几种 dataflow 模式，表明不同场景中数据编码（序列化）的重要性：

  • 数据库，写入数据库的进程序列化数据，从数据库读取数据的进程反序列化数据
  • RCP 和 REST APIs。客户端序列化请求，服务端反序列化请求并序列化响应，客户端反序列化响应
  • 异步消息传递系统。发送消息的节点序列化，接收消息的节点反序列化

我们可以得出结论，前后向兼容性和滚动升级是可达成的。你的应用可以持续演进并快速频率部署。

在本书的 第一部分，我们讨论了存储于单机的数据系统的各个方面。现在，在 第二部分，我们升级一下问题：如果多台计算机参与数据存储和检索会发生什么？

出于多重原因，您可能希望数据系统跨计算机分布：

  • 可扩展性 如果你的数据量，读写负载已经超过了单机处理的最高水平，可能会想将负载均衡到多台计算机
  • 容错性/高可用性 如果你的应用在即使一台计算机（或者几台计算机，网络，甚至整个数据中心）发生宕机后仍然能继续工作，则需要多台机器提供冗余，当一个系统宕机，可以有备份系统来接管
  • 延迟 如果你的用户遍布全球，则可能需要在全球各地部署服务，以便全球的用户在最近的数据中心来访问服务。这样避免了用户网络的延迟

扩展到更高的负载

如果你需要提升负载，最简单的方案就是购买一台性能更好的机器（有时称为垂直扩展）。可以在一个操作系统下将许多 CPU，许多 RAM 芯片和许多磁盘连接在一起，并且快速互连允许任何 CPU 访问内存或磁盘的任何部分。在这种共享内存体系结构中，所有组件都可以视为一台机器。

这种共享内存的方法的问题是成本增长太快：两倍 CPU，两倍 RAM，两倍硬盘容量的机器的价格远不止两倍。而且由于系统瓶颈，两倍硬件的机器可能并不能处理两倍的负载。

这种共享内存的方法只能提供有限的容错能力，即使是高端热拔插组件的计算机在地理位置这个维度，容错能力也是有限的。

另一种方案是共享硬盘存储，可以多台机器有独立的 CPU 和 RAM，但是共享硬盘存储（通过快速的网络）。这种体系结构用于某些数据仓库的场景，但是数据竞争和锁限制了这种方案的可扩展性。

无共享架构

相比之下，无共享架构（有时也称为水平扩展）广受欢迎。这种方案中，每台运行数据库的物理机或者虚拟机被称为节点（node）, 每个节点使用独立的 CPU，RAM 和硬盘。节点之间的协调都通过网络在软件层面进行。

无共享系统不需要任何特殊的硬件，所以你可以最具性价比的机器。还可以将机器分布在不同的地理位置，从而使得用户都拥有最近的服务器使用，并且可以避免整个数据中心丢失。通过上云虚拟机的方式，即使对于小型公司，也可以采用多区域分布式架构了。

在本书的这一部分，我们重点关注无共享架构，并不是因为对于每种场景都是最佳选择，而是因为，对于开发者来说，这里面的坑最多。如果你的数据分布在不同的节点，你就需要了解在分布式系统中的约束和其中的关于一致性/正确性的权衡等。

尽管无共享分布式架构具有很多优点，但是它通常会给应用带来额外的复杂性，并且有时会限制数据模型的表达能力。（PS（译者著）.redis 单机版和集群版对比，集群版的数据支持要少于单机版）在某些情况下，一个简单的单线程程序可能要比具有 100 个 CPU 核心的集群程序性能要好。另一方面，无共享架构可以表现的非常强大。接下来的章节将讨论一些数据分布中出现问题的细节。

复制 VS 分区

有两种常见的方式将数据分布到多个节点上：

  • 复制 将相同的数据的副本保存在多个不同的节点（可能处于不同的地理位置）。复制提供冗余：即使某些节点不可用，仍然可以从其他节点提供数据。复制还可以提高性能，我们将在 第 5 章 讨论复制
  • 分区 将大型数据库拆分为较小的子集称为分区，以便可以将不同分区分配给不同的节点（也称为分片）。我们将在 第 6 章 讨论分区

这是两种独立的机制，而且它们经常并存，如图II-1

image-20210419003851551

了解了这些概念之后，我们需要在分布式系统中进行艰难的权衡。在 第 7 章 中，我们讨论事务，这将帮助你理解数据系统中可能出错的地方以及如何处理。在 第 8 章 和 第 9 章 中，我们讨论分布式系统重要的局限性。

然后，在本书的 第三部分，我们将讨论如何使用多重数据存储，并将其整合到一个巨大复杂的应用体系中。这种系统构建的需求通常被号称满足一切需求的供应商所忽略。首先，我们来讨论分布式数据。

有些作者表示由于性能或可用性问题，普通的两阶段提交开销太大。我们认为最好由应用开发者去优化事务滥用带来的性能问题，而不是不提供事务能力 -- James Corbett et al., Spanner: Google’s Globally-Distributed Database (2012)

在严格的数据系统中，会发生很多错误：

  • 数据库软件或者硬件随时会出错（包括写操作到一半）
  • 应用可能随时 crash （包括一系列操作没有完成时）
  • 网络可能随时中断，客户端到数据库，数据库节点之间
  • 多个客户端同时写入数据库，互相覆盖
  • 客户端可能读到没有意义的数据，因为只更新了一部分
  • 客户端之间的竞争可能导致神奇的bug

为了做一个可靠的系统，必须处理这些故障并且确保不会导致整个系统的灾难性故障。但是实现容错机制需要大量工作。需要仔细考虑所有可能出错的场景，并进行大量测试确保方案有效。

@todo 已看完，待重读的时候润色翻译

Summary

transaction 是一个可以将并发问题和软硬件错误对应用隐藏的抽象层。很大一类错误被简单的 transaction abort 消除，应用只需要重试一次即可。

本章中，我们看到 transaction 可以解决的很多具体问题实例。不是所有应用都对这些问题比较敏感： 一个访问数据模式很简单的应用，比如读写单条 record，可以完全不用 transaction。但是对于复杂访问模式而言，transaciton 可以大大降低应用开发可能的错误

如果没有 transaction，各种问题（进程 crash，网络中断，掉电，磁盘满，不可预测的并发问题等）导致数据不一致。比如， JSON 类型的部分更新很容易与源数据不一致。没有 transaction，对于数据库的复杂交互访问会很难定位影响。

本章中，我们深入探究了并发控制的话题。我们谈论了多种隔离 level，read committed, snapshot isolatio(也被称为 repeatable read)，和 serializable。我们通过讨论了下面的竞争条件来区分多种 level

  • Dirty reads : 一个客户端读到了另一个客户端还没有 commited 的写。 read commited isolation level 或者更强的 level 消除了脏读
  • Diry writes : 一个客户端覆盖了另一个客户端还没有 commited 的写。所有 transaction 的实现都会消除脏写
  • Read Skew (nonrepeatable reads) : 一个客户端在不同的时间点看到数据不同。这个问题基本由 snapshot isolation 消除，使一次 transaction 一次读到的数据是一致的。通常使用 MVCC 实现
  • Lost updates : 两个客户端并发执行 read-modify-write 过程，一个会覆盖掉另一个的写入，所有数据丢失了。有些 snapshot isolation 实现避免了这个问题，但是有些需要显式加锁 (SELECT FOR UPDATE)
  • Write Skew : 一次 transaction 读一些数据，然后根据读到的信息做一些决策，写回数据库。但是，写入后，决策的前提条件数据实际已经不满足做决策时的数据条件。只有 serializable isolation 可以消除这个问题
  • Phantom reads : 一次 transaction 读到了满足搜索条件的一些数据。另一个客户端的写会影响搜索的结果。 snapshot isolation 可以消除直接的 phantom read，但是 write skew 上下文中的 phantoms 需要特别处理，比如 index-range locks (next-key lock)

Weak isolation level 处理了一些问题，但是还留下一些给开发者来显式处理（比如使用显式锁。只有 serializable isolation 可以消除所有这些问题。我们讨论了三种实现 serializable isolation 的方式：

  • Literally executing transactions in a serial order : 如果你可以使得每个 transaction 执行的飞起，然后单 CPU core 足够处理 transaction 的吞吐，这是简单有效的方法
  • Two-phase locking : 过去多年这是标准实现，但是很多应用避免使用因为性能有点差
  • Serializable snapshot isolation (SSI) : 比较新的算法，可以很大程度避免上述两种方法的缺点。使用乐观方法，允许 transaction 无锁执行。当 transaction 要 commit 的时候，检查是否 serializable 决定是否 abort

本章的这些例子使用了关系数据模型。但是正如提到过的 multi-object transactions 的需要，transaction 是一个有价值的数据库特性，与数据模型无关

本章，我们更多探讨数据库运行在单节点这样上下文的 idea 和算法。 Transactions 在分布式数据库中有新的困难与挑战，我们在接下来的两章中讨论

Faults and Partial Failures

单机被设计成出现错误就宕机

但是在写运行在多个计算机上的软件时，通过网络连接，事情变得不一样了。在分布式系统中，我们无法在完美系统模型中操作 -- 别无选择只能面对这个操蛋的现实世界。在现实世界中，有一系列问题出现。

分布式系统中，有多种方式部分系统会以不可预料的方式宕机，即使其他部分仍然正常工作。这被称为 partial failure，困难在于这是不确定的： 从调用方角度来看时而正常，时而不正常。因此，你不能确定调用是否完成，并且消息也是时而可达，时而不可达。

这种不确定性使得分布式系统变得难

Cloud Computing and Supercomputing

不可靠的时钟

时钟和时间是重要的。应用通过多种方式依赖时钟：

  1. 请求是否超时？
  2. 该服务的 99%的响应时间是多少？
  3. 过去的五分钟里该服务平均每秒能响应多少查询？
  4. 用户花了多长时间在站点？
  5. 该文章何时发布的？
  6. 具体什么时间催单邮件该被发送？
  7. 缓存何时过期？
  8. 日志中的错误信息时间戳是什么？

问题 1-4 度量的是时间段（比如请求到来-回应返回的时间差），问题 5-8 描述的是时间点（时间发生的特定日期，时间）。

在分布式系统中，时间是一件棘手的事务，因为通信不是即时的：通过网络从一台机器传递到另一台机器的消息需要花费一些时间。由于网络延迟的存在，我们不知道接受者接收消息的时间比发送时晚多少。这个现象有时使得确认涉及多台机器的事件发生顺序变得困难。

此外，网络中的每台机器都有自己的时钟，这通常是石英晶体震荡器这种硬件设备。这些设备的精度不是很高，所以每台机器都有自己的时间，可能相对于其他机器是或快或慢的。可以在某种程度上同步时钟：最常用的机制是 NTP 服务，它可以根据一组服务器上报的时间来调整计算机时钟。服务器轮流通过比如 GPS 接收器这种更精确的时钟源获取时间。

单调时钟与日期时钟

现代计算机至少有两种时钟：日期时钟和单调时钟，尽管它们都是用来度量时间，但是需要要知道，这两种时钟是为了不同的目的设计的。

日期时钟

日期时钟符合你的直观期望：获取具体的日期和时间（也称为挂钟时间）。例如，类 Linux 操作系统中的clock_gettime(CLOCK_REAL_TIME)和 Java 中的System.currentTimeMillis()返回的是自 UTC 时间 1970 年 1 月 1 日 0 点的秒数（或者毫秒数）PS: 忽略闰秒。一些系统也已其他时间点作为参考。

日期时钟通常通过 NTP 服务来同步，这意味着一台计算机上的时间戳与另一台计算机上的相同。然而，如同下一节描述的一样，日期时钟也有不同的可能性。特别地，如果本地时钟距离 NTP 服务器太远，则可能会被强制跳转到上一个时间点。这些跳跃以及经常忽略闰秒的事实，使得日期时钟不适合度量时间段。

从历史角度，日期时钟有过很粗糙的分辨率，比如老的 windows 系统上，时钟以 10ms 的步长前进。当然在最新的系统中，这已经不是问题了。

####单调时钟

单调时钟非常适合用于度量时间段，比如超时或者服务的响应时间：Linux 系统的clock_gettime(CLOCK_MONOTONIC)和 Java 的System.nanoTime()都是获取单调时钟。名字来源于总是向前移动的事实，而日期时钟可能会由于 NTP 等导致往回的跳变。

你可以在某个时间点检查单调时钟的值，然后执行一些操作，稍后再次检查单调时钟的值，差值就是时间段。要注意的是，单调时钟的绝对值是没有意义的：它可能是计算机启动以来的纳秒数或者类似的什么值。特别注意的是，比较两台计算机的单调时钟更加没有意义。

在具有多个 CPU 的计算机上，每个 CPU 可能有一个有别于其他 CPU 的单独的计时器。操作系统会尝试补偿 CPU 之间的差异，并为应用线程提供一个单调的时钟值，即使它们在不同的 CPU 之间调度。当然，更聪明的做法是有所保留地相信单调时钟。

如果 NTP 检测到计算机本地的时钟运行频率的快慢与 NTP 服务不同，会调整单调时钟向前移动的频率（被称为slewing the clock）。默认情况下，NTP 允许加快或者降低频率最多 0.05%，但是 NTP 不会使得单调时钟向回跳跃。单调时钟的频率通常很高，在大多数系统中可以度量毫秒或者更短的时间段。

在分布式系统中，使用单调时钟来度量时间段是优秀的，因为它不假定不同节点时钟之间存在同步，并且对于微小的度量误差不敏感。

时钟同步和准确性

单调时钟不需要同步，但是日期时钟必须根据 NTP 服务器或者其他外部时钟源同步自身时钟。不幸的是，我们同步时间的结果不总是能得到期望的那样，因为硬件时钟或者 NTP 服务器可能出现问题，下面举几个例子：

  • 计算机中的石英钟不总是很准确的：它会漂移。时钟漂移取决于计算机机器温度。Google 假设其服务器时钟漂移为 200ppm(pars per million，百万分之一），相当于每 30s 有 6ms 的时钟差异，或者每天 17s。时钟漂移限制了你能得到的时钟精度，即使看起来一切正常。
  • 如果计算机的时钟跟 NTP 服务器差异巨大，可能就会拒绝同步，或者直接重置。应用在重置前后得到的时间可能会有大幅向前或者向后的跳变。
  • 如果一个节点偶然被 NTP 服务隔离，错误配置好长一段时间没有被发现。证据表明这种事情真实发生。
  • NTP 同步依赖与网络延迟稳定，在拥塞导致的延迟不稳定的网络中 NTP 的准确性不是很好。一个实验表明，一秒内的偶然延迟尖峰会导致最小 35ms 的差错。根据配置，较大的网络延迟可以使 NTP 客户端放弃同步
  • 有些 NTP 服务器运行错误或者配置错误，报告的时间少了几个小时。NTP 客户端非常强大，因为它们查询多个服务器并且忽略异常值。尽管如此，有时从网络上未知者发来的时间正确性还是需要担忧。
  • 闰秒导致的一分钟有 59 秒或者 61 秒，这在没有考虑闰秒的系统中会造成时间系统混乱时序。事实表明，闰秒造成过很多大型系统的崩溃，说明时钟的错误假设很容易潜伏在系统中。最好处理闰秒的方式是使 NTP 服务器逐步慢慢地在一天的时间内修复这个时间误差（被称为smearing），尽管真实的 NTP 服务行为会在修正过程有所不同。
  • 虚拟机中，硬件时钟是虚拟化的，这为需要精确计时的应用带来了额外的挑战。当一个 CPU 内核在多个虚拟机之间共享时，每个虚拟机会在另一个虚拟机运行时暂停数十毫秒。从应用程序的角度来看就是时钟突然向前跳变。
  • 如果将软件运行在你不能完全控制的设备上（比如手机或者嵌入式设备），你可能根本不能信任设备的硬件时钟。有些用户会特意错误地设置本地的硬件日期和时间，比如规避游戏中的时间限制。结果时钟可以被设置为过去或者未来的某个时间。

如果投入大量资源，你是可以获取足够准确性的时钟的。比如，针对金融机构的欧洲法规草案 MiFID II 要求所有的高频交易基金将其时钟同步在 UTC 的 100 毫秒以内，以帮助调试市场异常来帮助进行市场操控。

高级别的精确时钟可以通过 GPS 接收器，PTP 和仔细的部署和监控获得。然而这需要大量的精力和专业的只是，并且可以采用多种方式进行时钟同步。如果你的 NTP 服务错误配置，或者 NTP 流量被拦截，由于漂移导致的时钟错误会迅速扩大。

对同步时钟的依赖

时钟的问题在于，尽管它们看起来简单易用，但是可能有令人意外的陷阱：

处理停滞

让我们考虑另一个在分布式系统中使用危险时钟的示例。假设有一个每个分区只有一个领导者的数据库，只有领导者被允许执行写操作，节点如何知道它仍然是领导者（没有被其它节点声明为死亡状态），并且可以安全地接收写入请求？

一种选择是使领导者从其他节点获取租约，这类似一个具有超时的锁。任意时间，只有一个节点可以持有未到期的租约，这样它就知道自己是领导者。为了保持租约，领导节点必须不断续期。如果领导节点续期失败，另一个节点就会接管租约。

可以想象这样一个处理请求的循环例子：

while(true) {
  request = getIncomingRequest();
  // 保证租约持有 10s
  if (lease.expiryTimeMillis - System.currentTimeMillis() < 10000) {
    lease = lease.renew();
  }
  if (lease.isValid()) {
    process(request);
  }
}

这段代码有什么问题？首先，它依赖同步时钟：租约的过期时间是由另一台不同的计算机设置的（例如，过期时间可以设置为当前时间加上 30s），然后将其与本地时间进行比较。如果始终不同步超过几秒钟，这份代码可能就不会按照预期的逻辑运行。

第二，即使我们将协议更改为仅使用本地单调时钟，也存在一个问题：代码假定在检查时间和处理请求之间的时间很短。通常，此代码运行地很快，因此 10s 的缓冲区足以确保在处理请求的过程中租约不会到期。但是，如果在代码执行过程中存在意料之外的停滞会发生什么？比如，假设有一个线程在lease.isValid继续执行之前停滞了 15s，在这种情况下，到了处理请求的时候，租约已经过期，另一个节点已经变更成为领导者节点。然而，执行该处理的节点并不知道自己停滞了这么长时间，因此此代码在下一次循环之前不会注意到自己的租约已经到期了，届时它已经通过处理该请求做了一些不安全的事。

难道假定一个线程停滞了这么久很难以置信？不幸的是并没有，有很多理由证明这发生过：

  • 许多程序设计语言（比如 Java 虚拟机）有垃圾收集（GC）机制，使得偶尔需要停滞所有正在运行的线程。这些“stop-the-world”的 GC 暂停可能会持续几分钟。即使所谓的并发垃圾收集器（比如 HotSpot JVM's CMS）也不能与应用层代码并行运行，即它们也需要时不时地停滞整个世界的运行。尽管这些暂停可以通过更改分配模式或者调节 GC 参数来减少，但是如果想要提供可靠性保证，就必须假定最坏的情况会发生。
  • 在虚拟机环境中，虚拟机可以挂起（暂停所有进程并保存上下文到磁盘）或者恢复（从磁盘重新加载到内存并继续执行）。这种暂停可以发生在执行程序的任何时间并持续任意时间。有时，这个特性用来做不需重启的热迁移到另一台主机，这种情况下，暂停的时长取决于进程写入存储的速度。
  • 在个人终端比如笔记本电脑设备商，也可以任意暂停并恢复，比如当用户关闭笔记本电源时
  • 当操作系统进行上下文切换到另一个线程时，或者虚拟化程序调度另一台虚拟机的运行时，当前运行的线程就会在代码的任一行挂起。对于虚拟机，在其他虚拟机上的 CPU 时间消耗被称为时间窃取 (steal time)。如果计算机负载很高（即，等待执行的队列很长），则可能需要一段时间才能使暂停的线程恢复运行
  • 如果应用程序执行同步磁盘访问，线程可能会由于慢速的磁盘 IO 而挂起。在许多语言中，即使代码中看起来没有访问文件，也可能在执行过程中进行磁盘访问，比如 Java 类加载器会延迟执行加载类文件直到第一次使用该类，这就意味着可能发生在代码执行的任何时间。IO 挂起和 GC 挂起可能组合起来表现成延迟。如果是访问网络文件系统或者网络块设备，IO 延迟可以和网络延迟组合起来。
  • 如果操作系统配置成允许使用交换区，在缺页时就会触发磁盘访问（从磁盘加载到内存）。在执行慢速 IO 操作时，线程就会挂起。如果内存的压力过大，可能需要将不同的页面换到磁盘中存储，在极端情况下，换页频繁发生，而实际的工作很少完成（被称为thrashing）。为了避免这个问题，如果宁可杀死一个进程也要避免出现 thrashing，就应该关闭服务器的交换区功能（PS. 译者注：OOM）
  • Unix 进程可能会被SIGSTOP信号停滞，比如在 shell 中按下Ctrl-Z组合键。这个信号会立即停止直到获取SIGCONT信号，才会继续执行。即使你不会使用SIGSTOP信号，也无法保证其他的操作者不会。

在线程不知情的情况下，上述的任何情况发生都会抢占到当前运行线程的 CPU，然后再稍后恢复。这个问题有点像在同一台机器上的多进程代码所谓的线程安全：不能假定任何时间相关的前提，因为二进制层面的切换可能会在任何时刻发生。

当写多进程代码时，我们有相当多好用的工具来保证线程安全：锁，信号量，原子计数器，lock-free 数据结构，阻塞队列等。不幸的是，这些工具不能直接借用到分布式系统，因为分布式系统没有共享的存储，只能通过不可靠的网络来同步消息。

一个分布式系统中的节点必须假定，即使在函数中间，也能在任何时间将其暂停相当长的时间。在暂停期间，其他节点可以正常运行，甚至可能会因为没有响应而宣告暂停的节点死亡。最终，暂停的节点可能会恢复运行，甚至没有注意到自己有过暂停，直到稍后某个时间检查时钟。

响应的时间保证

在本书的第一部分和第二部分，我们从头开始组装进入分布式数据库的所有主要因素，从磁盘的数据布局一直到出现故障时分布式一致性的极限。但是，这些讨论假定应用中只有一个数据库

实际上，数据系统通常更加复杂。在大型应用中你经常需要通过不同的方式获取和处理数据，没有单一的数据库可以满足所有不同的需求。应用因此使用多种存储产品的组合，比如数据存储，索引，缓存，分析系统等，并且实现从一个存储移动到另一个存储的机制

在本书的最后一部分，我们将围绕多个不同的数据系统（可能具有不同的数据模型，并针对不同的访问模式进行优化）集成到一个一致的应用程序体系结构中的问题。供应商常常忽略系统构建这一方面，他们声称产品可以满足您的所有需求。实际上，集成不同的系统是非平凡应用中最重要的事情之一。

记录系统和派生数据系统

在一个高层次上，存储和处理数据的系统可以被分为两个大类：

  • 记录系统(OLTP, Online Transaction Processing) 记录系统（也称为事实来源）保存数据的权威版本。当输入新数据时（例如，用户输入）首先写入记录系统。每个事实仅表示一次（通常已经标准化）。如果另一个系统与记录系统中的数据存在差异，以记录系统为准
  • 派生数据系统(OLAP, Online Analytical Processing) 派生系统中的数据是从另一个系统获取一些现有数据并以某种方式对其进行转换或处理的结果。如果丢失了派生数据，还可以重建。典型的例子就是缓存：可以从缓存中提供数据，但是如果缓存中没有需要的数据，可以使用基础数据库中的数据。非规范化的值，索引和实例化视图也属于此类。在推荐系统中，预测性摘要数据通常来自使用日志。

从技术上来讲，派生的数据是冗余的，是信息的复制。然而，会在查询时提供良好的性能。通常将其归一化。你可以从单一数据源派以不同角度生出不同的数据集

不是所有的系统在体系结构上对记录和派生系统又严格的区分，但是区分它们是有帮助的，因为可以梳理你的系统中的数据流：将系统中哪些是输入，哪些是输出，以及之间的依赖关系展示清楚

大多数数据库，存储引擎，和查询语言本身都不是记录或者派生系统。数据库仅仅是工具：如何使用取决于你。它们之间的区别不在于工具，而是你在应用中如何使用它们。

通过清楚地知道哪些数据是从其他数据中得出的，可以使得本来令人困惑的系统体系结构更清晰。这一点将贯穿本部分

章节概览

我们将在第 10 章讨论批处理数据流的系统，比如 MapReduce，并了解它们如何向我们提供了构建大型数据系统的工具和原理。在第 11 章，我们将采用这些思路来应用到数据流，这使得我们可以以较低的延迟来做到同样的事。第 12 章通过探讨如何使用这些工具来构建可靠，可扩展以及可维护的应用总结了本书。

在第 10 章中，我们讨论了批处理--一种读入一堆文件作为输入，生成一堆新的输出文件的技术。输出是派生数据的形式，意味着，如果有必要可以通过批处理重新创建数据集。我们看到这是多么简单有力的思路在创建搜索索引，推荐分析系统的时候。

但是，存在一个假设：即输入是有界的（大小已知且有限），因此批处理可以知道何时读取完成它的输入。例如，MapReduce 的核心排序操作在生产输出前必须获得所有输入：可能会发生最后一个输入是最小键的情况，因此需要将它作为第一个输出，所以不能提前开始输出。

实际上，许多数据是无界的，因为它们会随着时间推移慢慢到达：你的用户昨天和今天都在生产数据，而且明天还会继续。除非你倒闭，这个过程不会停止，从这个意义上来说，数据不会完成。因此批处理程序必须人为将其划分为固定持续时间的块：例如，在每天的最后处理一天的数据，或者在每个小时结束处理一小时的数据。

每日批处理的问题在于输入的更改要在一天之后才反映在输出中，这对于很多用户来说太慢了。为了降低延迟，我们可以更加平滑的运行处理过程----例如，在每秒结束处理一秒的数据----或者甚至，连续地没有所谓的固定时间块，就当时间发生时就处理。这就是流处理背后的思想。

通常来说，"流"是指随着时间推移逐渐可用的数据。这个概念出现在许多地方：Unix 的stdin 和 stdout，编程语言（惰性列表），文件系统的 API，TCP 连接，互联网上的音视频传输等等。

在本章中，我们将事件流视为一种数据管理机制：对应上一章批处理的无界的，增量处理的对应物。首先讨论如何通过网络表示，存储和传输流。在 451 页的数据库和流中我们将研究流和数据库的关系，最后，在 464 页的流处理中，我们将探索用于连续处理这些流的方法和工具，以及可用于构建应用程序的方法。

传输事件流

在批处理系统，任务的输入和输出都是文件（可能来自分布式文件系统）。等效的流是什么样子？

当输入是文件（字节的序列）时，处理的第一步就是解析为记录序列。在流处理的上下文中，记录通常被成为 event，但是本质上是一个东西：小的，自包含的，不变的对象，其中包含了某个时间点发生的某件事的详细信息。event 通常包含时间戳标识发生于一天中的那个时间点。

举例来说，发生的事情可能是用户执行的操作，比如查看页面或者购买。它也可能源自机器，比如温度传感器的定期测量或者 CPU 利用率指标。在 391 页的使用 Unix 工具进行批处理的例子中，web 的日志每一行都是一个事件。

如同在第四章中讨论，事件可以被编码成为字符串或者 JSON，或者某种二进制。编码允许你存储事件，例如将事件附加到文件中，然后将其插入到关系表中，或者写到文档数据库中；还允许通过网络将事件发送到另一个节点以对其进行处理。

批处理中，文件被写入一次然后可能被多个任务读取。类似地，在流式术语中，事件由生产者（也被称为发布者或者发送者）生成一次，然后由多个消费者进行处理（订阅者或接收者）。文件系统中，文件表示一系列相关记录；在流系统中，相关的事件通常组合在一起被称为 topic 或者 stream.

原则上来说，一个文件或者数据库足以连接生产者和消费者：一个生产者将事件写入数据存储，然后每个消费者定期轮询数据检查自上次运行以来出现的事件。本质上，就是批处理在每天结束时处理一天数据的过程。

然而，当转向低延迟的连续处理时，如果数据存储不是为这种用途设计的轮询的开销变得相当巨大。越频繁地轮询，返回新事件的概率就越低，因此开销就越高。所以，最好是当新事件到来时通知消费者。

传统上的数据对于这种通知机制的支持不是很好：关系数据库通常具有触发器，它可以对类似表有插入动作作出反应，但是可以做的非常有限，而且在数据库设计中有些事后思考（文献 4，5）。代替的是，已经有了专门开发出来的工具来传递事件通知。

消息系统

一个通用的通知消费者新事件到来的方案是使用消息系统：生产者发送一个包含事件的消息，然后被推送给消费者。我们再 136 页的消息传递数据流中涉及到了，在这里详细阐述。

生产者和消费者之间利用直接通信通道（Unix 管道或者 TCP 连接）是实现消息传递系统的简单方法。但是，大多数消息系统会在此基础上进行扩展。尤其是，Unix 管道和 TCP 连接只是将一个生产者和一个消费者连接起来，而消息系统允许多对多的消息模式

在此发布/订阅模型中，不同的系统采用不同的方法，并且没有可以支持所有目的的答案。为了区分系统，提出以下两个问题会很有帮助：

  1. 如果生产者发送消息比消费者处理消息快会发生什么？广义上来讲，会有三种情况：系统丢掉消息，在队列中缓存消息，进行负反馈（流控，比如告诉生产者不要发送了）。举个栗子，Unix 管道和 TCP 使用负反馈：他们有一个很小的固定 buffer，如果被占满，发送端会被锁住直到 buffer 里的内容被使用。 如果消息在队列中被缓存，重要的是理解如果队列不够长怎么办？如果队列内存不足会 crash 吗或者把消息写到磁盘？如果这样做了，怎么保证消息队列的性能？
  2. 如果节点 crash 或者暂时掉线了会发生什么，会丢消息吗？与数据库一样，持久性可能需要写入磁盘或复制，这回产生开销。如果可以容忍丢失消息的后果，可以在同样的硬件上获得更高的吞吐和更小的延迟

消息丢失是否能够接受更多的取决于应用。比如，对于定期的传感器读写，偶尔的丢数据是可以接受的，因为无论如何稍后都会有新的数据发送。然而，请注意，如果丢弃了大量消息，可能会导致度量不准确。如果要对事件进行计数，那么可靠的传递就变得更为重要，因为每个丢失的消息都会导致错误计数。

我们在 10 章中讨论的批处理系统有一个很好的特性，就是有很强的可靠性保证：失败的任务自动重试，并自动丢弃失败任务的部分输出。这意味着输出跟没有发生故障一样，这有助于简化编程模型。在本章的稍后，我们将研究如何在流系统中提供一个类似的保证。

从生产者直接传递到消费者

许多消息系统使用网络通信在生产者和消费者直连，不经过任何中间节点：

  • UDP 多播在禁用也中广泛应用于流，例如股市摘要，其中低延迟很重要。尽管 UDP 本身是不可靠的，但是应用级别的协议可以恢复丢失的数据包（生产者必须记住已经发送的数据包，以便丢失重传）
  • 无代理的消息库，比如 ZeroMQ，或者采用类似的方法，通过 TCP 或者 IP 多播实现发布/订阅消息
  • StatsD 和 Brubeck 利用不可靠的 UDP 消息从网络中的所有计算机手机指标并监控它们。（在 Stats 协议中，只有收到所有消息的指标才正确；使用 UDP 使得指标最好近似）
  • 如果消费者在网络中提供服务，生产者可以直接通过 HTTP 或者 RPC 请求将消息推送给消费者。这是 webhooks 背后的思路，这种模式是一种服务的回调 URL 向另一种服务注册，并且每当发生事件时，都会向该 URL 发出请求

尽管这些直接的消息系统在设计他们的场景中工作的很好，但是他们通常需要应用程序的代码意识到消息丢失的可能性。他们可以容忍的错误非常有限：即使协议检测到并重新传输网络中丢失的数据包，他们通常也假定生产者和消费者一直在线

如果消费者离线，当发送的消息不可达时就可能丢失消息。有些协议允许生产者重传失败消息，但是这种如果生产者 crash，就不起作用了，从而丢失本应该重试的消息。

消息代理

消息代理对比数据库

多个消费者

ACK 和重传

分区日志

消息存储使用日志

日志对比传统消息

消费者补偿

硬盘空间的利用

当消费者无法跟上生产者速度

重放老消息

数据库和流

我们在消息代理和数据库之间进行了一些比较。即使传统上它们都被视作工具的单独类别，但是我们看到基于日志的消息代理已经成功从数据库中获取了思路并将其应用于消息传递。我们也可以反过来从消息和流中获得启发，将其应用于数据库

我们之前说过，事件就是某个时间点发生的事情的记录。发生的事情可以是用户操作（例如查询），或者传感器读数，也可能是写入数据库。事实是写入数据库的事件可以被捕获，存储和处理。这个事实表明，数据库和流之间的连接比磁盘上的日志的物理存储更深入---这是很基本的。

事实上，复制的日志（replication log）就是数据库写事件的流，由处理事务的领导者产生。跟随者将该写入流应用于自己的数据库副本，从而获得相同数据的准确副本。复制日志中的事件描述了数据发生了更改。

我们还从 348 页的 Total Order Broad-cast 中连接了复制状态机复制原理，该原理指出：如果每个事件表示一个数据库的写入，每个复制以相同的顺序处理相同事件，所有的复制最终会达到相同的状态。这只是事件流的另一种情况！

本节中我们首先研究异构数据系统中出现的问题，然后探讨如何通过事件流带入数据库的思想解决它。

保持系统同步

正如我们在本书中一直看到的，没有单一系统可以满足所有的数据存储，查询和处理需要。实际上，大多数不平凡的应用程序都需要组合几种不同的技术来满足其需求：比如，使用 OLTP 数据库服务用户请求，使用缓存来加速常见请求，全文索引来处理搜索查询，以及用于分析的数据仓库。其中每个都有自己的数据副本，并以自己的形式表示，针对自己的目的进行了优化

由于相同或者相关的数据出现在几个不同的位置，因此需要使它们彼此保持同步：如果在数据库中更新了一项，需要在缓存、索引和数据仓库中同步更新。对于数据仓库，通常这种同步由 ETL 来处理（查看 91 页的数据仓库），通常是获取数据库的完整副本，进行转换并将其批量加载到数据仓库中，换句话说，一个批处理。相似的，我们再 411 页的 The Output of Batch Workflows 中看到了如何使用批处理创建搜索索引，推荐系统和其他派生数据系统。

改变数据捕获

时间源

状态，流和不变性

处理流

到目前为止，在本章中，我们已经讨论了流的来源（用户活动事件，传感器和向数据库的写操作），并讨论了流的传输方式（通过直接消息，消息代理传递事件日志）

剩下的就是讨论有了流之后如何处理。大致来说，有三种选择：

  1. 你可以获取事件中的数据，并将其写入数据库，缓存，搜索索引和类似的存储系统，然后其他客户端从其查询。这是使数据库与系统其他部分中发生更改保持同步的一种好方法，尤其是流的消费者是唯一向数据库写入数据的客户端的情况下。写入存储系统相当于在 411 页的批处理工作流的输出中讨论的流式等效
  2. 你可以通过某种方式将事件推送给用户，比如发邮件，发通知，或者将事件流式传输到实时仪表版可视化。这种情况下，人是消费者
  3. 你可以处理一个或者多个输入流然后生产一个或者多个输出流。流会通过管道流经几个不通的处理阶段在最终输出之前（1 或 2）

在本章的剩余部分，我们将讨论选择 3：处理流生成其他流。像这样处理流的一段代码被称为* operator 或者 job*. 与我们再第 10 章讨论的 Unix 进程和 MapRedues 任务密切相关，数据流的模式是类似的：流处理包括只读的数据流输入，并在输出中将其附加到不同位置

流处理的分割和并行化模式也是跟 MapReduces 相似的，所以我们不再赘述。基于 map 的操作比如转换或者过滤记录也可以相同

与批处理任务的最大不同就是流是无界的，不会结束。这个不同有很多含义：如果章节开始讨论的，对于无界数据集，排序没有意义，因此无法使用排序-合并连接。错误容忍机制必须改变：对于已经运行了几分钟的批处理任务，可以简单地重启失败任务，但是对于已经运行了几年的流处理任务，在崩溃后从头开始不可行。

流处理的使用

Reasoning about time

Stream joins

错误容忍

总结

在本章中，我们讨论了事件流以及他们的目的，和如何处理它们。在某些程度上，流处理很像批处理（第 10 章讨论），但是无界流不是固定大小的输入。从这个角度，流式处理中的消息代理和事件日志就类似文件系统。

我们花了些时间来比较两种类型的消息代理：

  • AMQP/JMS-style message broker 代理将单个消息分配给使用者，并且当消息被成功处理后
  • Log-based message broker