数据密集型系统设计

数据系统的基石

本文将会介绍数据系统底层的基础概念，⽆论是在单台机器上运⾏的单点数据系统，还是分布在多台机器上的分布式数据系统都适⽤。

1. 第⼀部分将介绍本书使⽤的术语和⽅法。可靠性，可扩展性和可维护性 ，这些词汇到底意味着什么？如何实现这些⽬标？
2. 第⼆部分将对⼏种不同的数据模型和查询语⾔进⾏⽐较。从程序员的⻆度看，这是数据库之间最明显的区别。不同的数据模型适⽤于不同的应⽤场景。
3. 第三部分将深⼊存储引擎内部，研究数据库如何在磁盘上摆放数据。不同的存储引擎针对不同的负载进⾏优化，选择合适的存储引擎对系统性能有巨⼤影响。
4. 第四部分将对⼏种不同的 数据编码进⾏⽐较。特别研究了这些格式在应⽤需求经常变化、模式需要随时间演变的环境中表现如何。
   

一、可靠性、可扩展性、可维护性

• 目标与意义
  现今很多应⽤程序都是 数据密集型（data-intensive） 的，⽽⾮ 计算密集型（compute-intensive）
  的。因此CPU很少成为这类应⽤的瓶颈，更⼤的问题通常来⾃数据量、数据复杂性、以及数据的变更速
  度。
  数据密集型应⽤通常由标准组件构建⽽成，标准组件提供了很多通⽤的功能；例如，许多应⽤程序都需
  要：

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

  如果这些功能听上去平淡⽆奇，那是因为这些 数据系统（data system） 是⾮常成功的抽象：我们⼀直不假思索地使⽤它们并习以为常。绝⼤多数⼯程师不会幻想从零开始编写存储引擎，因为在开发应⽤时，数据库已经是⾜够完美的⼯具了。
  但现实没有这么简单。不同的应⽤有着不同的需求，因⽽数据库系统也是百花⻬放，有着各式各样的特性。实现缓存有很多种⼿段，创建搜索索引也有好⼏种⽅法，诸如此类。因此在开发应⽤前，我们依然有必要先弄清楚最适合⼿头⼯作的⼯具和⽅法。⽽且当单个⼯具解决不了你的问题时，组合使⽤这些⼯具可能还是有些难度的。
  本部分将从我们所要实现的基础⽬标开始：可靠、可扩展、可维护的数据系统，以及探讨考量这些⽬标的⽅法。

• 可靠性（Reliability）

  • 可靠性意味着即使发⽣故障，系统也能正常⼯作。故障可能发⽣在硬件（通常是随机的
    和不相关的），软件（通常是系统性的Bug，很难处理），和⼈类（不可避免地时不时出错）。容错技术可以对终端⽤户隐藏某些类型的故障。

  • 容错

    • 造成错误的原因叫做故障（fault），能预料并应对故障的系统特性可称为容错（fault tolerant）或韧性（resilient）。
      “容错”⼀词可能会产⽣误导，因为它暗示着系统可以容忍所有可能的错误，但在实际中这是不可能的时，只有谈论特定类型的错误才有意义。
    • 注意，故障（fault）不同于失效（failure）。故障通常定义为系统的⼀部分状态偏离其标准，⽽失 效则是系统作为⼀个整体停⽌向⽤户提供服务。故障的概率不可能降到零，因此最好设计容错机制以防因故障⽽导致失效。而我们的目的就是要利⽤不可靠的部件构建可靠系统的技术。

• 可扩展性（Scalability）

  • 可扩展性意味着即使在负载增加（数据量、流量、复杂性）的情况下也有保持性能的策略。为了讨论可扩展性，我们⾸先需要定量描述负载和性能的⽅法。

  • 描述负载

    • 负载可以⽤⼀些称为负载参数（load parameters）的数字来描述。参数的最佳选择取决于系统架构，它可能是每秒向Web服务器发出的请求、数据库中的读写⽐率、聊天室中同时活跃的⽤户数量、缓存命中率或其他东⻄。
      除此之外，也许平均情况对你很重要，也许你的瓶颈是少数极端场景。

  • 描述性能

    • ⼀旦系统的负载被描述好，就可以研究当负载增加会发⽣什么。我们可以从两种⻆度来看：
      a。增加负载参数并保持系统资源（CPU、内存、⽹络带宽等）不变时，系统性能将受到什么影响？
      b。增加负载参数并希望保持性能不变时，需要增加多少系统资源？
      这两个问题都需要性能数据，所以让我们简单地看⼀下如何描述系统性能。

    • 吞吐量（throughput）：即每秒可以处理的记录数量，或者在特定规模数据集上运⾏作业的总时间。

    • 响应时间（response time）：即客户端发送请求到接收响应之间的时间。

    • 测量的数值分布（distribution）指标

      • 算术平均值（arithmetic mean）：平均值并不是⼀个⾮常好的指标，

      • 百分位点（percentiles）法：如果你想知道“典
        型（typical）”响应时间，通常使⽤百分位点会更好。如果将响应时间列表按最快到最慢排序，那么中位数（median）就在正中间。中位数也被称为第50百分位点，有时缩写为p50。

        • 百分位点通常⽤于服务级别⽬标（SLO, service level objectives）和服务级别协议（SLA, service level agreements），即定义服务预期性能和可⽤性的合同。 SLA可能会声明，如果服务响应时间的中位数⼩于200毫秒，且99.9百分位点低于1秒，则认为服务⼯作正常；如果响应时间更⻓，就认为服务不达标。

      • 响应时间的⾼百分位点（也称为尾部延迟（tail latencies））⾮常重要，因为它们直接影响⽤户的服务体验。

  • 应对负载的⽅法

    • ⼈们经常讨论纵向扩展（scaling up）（垂直扩展（vertical scaling），转向更强⼤的机器）和横向扩展（scaling out）（⽔平扩展（horizontal scaling），将负载分布到多台⼩机器上）之间的对⽴。
      跨多台机器分配负载也称为“⽆共享（shared-nothing）”架构。可以在单台机器上运⾏的系统通常更简单，但⾼端机器可能⾮常贵，所以⾮常密集的负载通常⽆法避免地需要横向扩展。现实世界中的优秀架构需要将这两种⽅法务实地结合，因为使⽤⼏台⾜够强⼤的机器可能⽐使⽤⼤量的⼩型虚拟机更简单也更便宜。
    • 有些系统是弹性（elastic）的，这意味着可以在检测到负载增加时⾃动增加计算资源，⽽其他系统则是⼿动扩展（⼈⼯分析容量并决定向系统添加更多的机器）。如果负载极难预测（highly
      unpredictable），则弹性系统可能很有⽤，但⼿动扩展系统更简单，并且意外操作可能会更少（参阅“重新平衡分区”）。

• 可维护性（Maintainability）

  • 可维护性有许多⽅⾯，但实质上是关于⼯程师和运维团队的⽣活质量的。良好的抽象可以帮助降低复杂度，并使系统易于修改和适应新的应⽤场景。良好的可操作性意味着对系统的健康状态具有良好的可⻅性，并拥有有效的管理⼿段。

  • 我们应该以这样⼀种⽅式来设计软件：在设计之初就尽量考虑尽可能减少维护期间的痛苦，从⽽避免⾃⼰的软件系统变成遗留系统。为此，我们将特别关注软件系统的三个设计原则：

    • 可操作性（Operability）：便于运维团队保持系统平稳运⾏。
    • 简单性（Simplicity）：从系统中消除尽可能多的复杂度（complexity），使新⼯程师也能轻松理解系统。
    • 可演化性（evolability）：使⼯程师在未来能轻松地对系统进⾏更改，当需求变化时为新应⽤场景做适配。也称为可扩展性（extensibility），可修改性（modifiability）或可塑性（plasticity）。

二、数据模型&查询语言

• 目标与意义：数据模型可能是软件开发中最重要的部分了，因为它们的影响如此深远：不仅仅影响着软件的编写⽅式，⽽且影响着我们的解题思路。
  多数应⽤使⽤层层叠加的数据模型构建。每个层都通过提供⼀个明确的数据模型来隐藏更低层次中的复杂性。这些抽象允许不同的⼈群有效地协作，例如数据库⼚商的⼯程师和使⽤数据库的应⽤程序开发⼈员。
  因为数据模型对上层软件的功能（能做什
  么，不能做什么）有着⾄深的影响，所以选择⼀个适合的数据模型是⾮常重要的。

• 常见数据模型

  • 关系模型

    • 现在最著名的数据模型可能是SQL。它基于Edgar Codd在1970年提出的关系模型【1】：数据被组织成关系（SQL中称作表），其中每个关系是元组（SQL中称作⾏)的⽆序集合。

    • 特点

      • 事务处理
      • 批处理
      • 阻抗不匹配：数据存储在关系表中，那么需要⼀个笨拙的转换层，处于应⽤程序代码中的对象和表，⾏，列的数据库模型之间。模型之间的不连贯有时被称为阻抗不匹配（impedance mismatch）。
      • 多对⼀和多对多的关系
      • 查询数据简单：在关系数据库中，“访问路径”是由查询优化器⾃动⽣成的，⽽不是由程序员⽣成。

  • 文档模型

    • Nosql

      • “NoSQL”这个名字让⼈遗憾，因为实际上它并没有涉及到任何特定的技术。最初它只是作为⼀个醒⽬的Twitter标签，⽤在2009年⼀个关于分布式，⾮关系数据库上的开源聚会上。后被追溯性地重新解释为不仅是SQL（Not Only SQL）。

      • 驱动Nosql数据库的几个因素：

        • i. 需要⽐关系数据库更好的可扩展性，包括⾮常⼤的数据集或⾮常⾼的写⼊吞吐量。
          ii. 相⽐商业数据库产品，免费和开源软件更受偏爱。
          iii. 关系模型不能很好地⽀持⼀些特殊的查询操作。
          iv. 受挫于关系模型的限制性，渴望⼀种更具多动态性与表现⼒的数据模型。

    • 数据通常是⾃我包含的，⽽且⽂档之间的关系⾮常稀少。

    • 在表示多对⼀和多对多的关系时，关系数据库和⽂档数据库并没有根本的不同：在这两种情况
      下，相关项⽬都被⼀个唯⼀的标识符引⽤，这个标识符在关系模型中被称为外键，在⽂档模型中称为⽂档引⽤【9】。该标识符在读取时通过连接或后续查询来解析。

    • 访问记录的唯⼀⽅法是跟随从根记录起沿这些链路所形成的路径。这被称为访问路径（access path）。

  • 对比关系模型和文档模型

    • 使应用程序代码更简单方面

      • 如果应⽤程序中的数据具有类似⽂档的结构（即，⼀对多关系树，通常⼀次性加载整个树），那么使⽤⽂档模型可能是⼀个好主意。
        关系模型可能导致繁琐的模式和不必要的复杂的应⽤程序代码。
      • ⽂档数据库对连接的糟糕⽀持有可能会是⼀个问题，这取决于应⽤程序。如果你的应⽤程序确实使⽤多对多关系，文档模型通过反规范化可以减少对连接的需求，但是应⽤程序代码需要做额外的⼯作来保持数据的⼀致性。这也将复杂性转移到应⽤程序中，并且通常⽐由数据库内的专⽤代码执⾏的连接慢。在这种情况下，使⽤⽂档模型会导致更复杂的应⽤程序代码和更差的性能。

    • 灵活性方面

      • ⽂档数据库有时称为⽆模式（schemaless），但这具有误导性，因为读取数据的代码通常假定某种结构，即存在隐式模式，但不由数据库强制执⾏。⼀个更精确的术语是读时模式schema-onread：数据的结构是隐含的，只有在数据被读取时才被解释，相应的是写时模式schema-onwrite：传统的关系数据库⽅法中，模式明确，且数据库确保所有的数据都符合其模式。
      • 当由于某种原因（例如，数据是异构的）集合中的项⽬并不都具有相同的结构时,读时模式更具优势。但是，当所有记录都具有相同的结构，那么写时模式是记录并强制这种结构的有效机制。

    • 查询数据的局部性方面

      • ⽂档通常以单个连续字符串形式进⾏存储，编码为JSON，XML或其⼆进制变体（如MongoDB的BSON）。如果应⽤程序经常需要访问整个⽂档（例如，将其渲染⾄⽹⻚），那么存储局部性会带来性能优势。如果将数据分割到多个表中，则需要进⾏多次索引查找才能将其全部检索出
        来，这可能需要更多的磁盘查找并花费更多的时间。
      • 局部性仅仅适⽤于同时需要⽂档绝⼤部分内容的情况。数据库通常需要加载整个⽂档，即使只访问其中的⼀⼩部分，这对于⼤型⽂档来说是很浪费的。更新⽂档时，通常需要整个重写。且只有不改变⽂档⼤⼩的修改才可以容易地原地执⾏。这些性能限制⼤⼤减少了⽂档数据库的实⽤场景。

  • 图数据模型

    • 如果你的应⽤程序⼤多数的关系是⼀对多关系（树状结构化数据），或者⼤多数记录之间不存在关系，那么使⽤⽂档模型是合适的。
      但是，要是多对多关系在你的数据中很常⻅，随着数据之间的连接变得更加复杂，使用图数据模型更加⾃然。

    • ⼀个图由两种对象组成：顶点（vertices）（也称为节点（nodes） 或实体（entities）），和边 （edges）（ 也称为关系（relationships）或弧 （arcs） ）。

    • 有⼏种不同但相关的⽅法⽤来构建和查询图中的数据。如属性图模型和三元组存储模型（triple-store）。

      • 属性图模型

        • 在属性图模型中，每个顶点（vertex）包括：
          唯⼀的标识符

• ⼀组出边（outgoing edges）

• ⼀组⼊边（ingoing edges）

• ⼀组属性（键值对）
  每条边（edge）包括：

• 唯⼀标识符

• 边的起点/尾部顶点（tail vertex）

• 边的终点/头部顶点（head vertex）

• 描述两个顶点之间关系类型的标签

• ⼀组属性（键值对）
  可以将图存储看作由两个关系表组成：⼀个存储顶点，另⼀个存储边。可以用头部和尾部顶点⽤来存储每条边；顶点的输⼊或输出边也同理。
  - 关于这个模型的⼀些重要特性，这些特性为数据建模提供了很⼤的灵活性：

1. 任何顶点都可以有⼀条边连接到任何其他顶点。没有模式限制哪种事物可不可以关联。

2. 给定任何顶点，可以⾼效地找到它的⼊边和出边，从⽽遍历图，即沿着⼀系列顶点的路径前后移动。

3. 通过对不同类型的关系使⽤不同的标签，可以在⼀个图中存储⼏种不同的信息，同时仍然保持⼀个清晰的数据模型。
   4.在可演化性方面富有优势：当向应⽤程序添加功能时，可以轻松扩展图以适应应⽤程序数据结构的变化。
   - Cypher查询语⾔

    - Cypher是属性图的声明式查询语⾔，为Neo4j图形数据库⽽发明。（它是以电影“⿊客帝国”中的⼀个⻆⾊来命名的，⽽与密码术中的密码⽆关。）

通常对于声明式查询语⾔来说，在编写查询语句时，不需要指定执⾏细节：查询优化程序会⾃动选择预测效率最⾼的策略，因此你可以继续编写应⽤程序的其他部分。

- 三元组存储模型- 三元组存储模式⼤体上与属性图模型相同，⽤不同的词来描述相同的想法。在三元组存储中，所有信息都以⾮常简单的三部分表示形式存储（主语，谓语，宾语）。例如，三元组(吉姆, 喜欢 ,⾹蕉)中，吉姆是主语，喜欢是谓语（动词），⾹蕉是宾语。- 三元组的主语相当于图中的⼀个顶点。⽽宾语是下⾯两者之⼀：

1. 原始数据类型中的值，例如字符串或数字。在这种情况下，三元组的谓语和宾语相当于主语顶点上的属性的键和值。例如， (lucy, age, 33) 就像属性 {“age”：33} 的顶点lucy。

2. 图中的另⼀个顶点。在这种情况下，谓语是图中的⼀条边，主语是其尾部顶点，⽽宾语是其头部顶点。例如，在 (lucy, marriedTo, alain) 中主语和宾语 lucy 和 alain 都是顶点，并且谓语
   marriedTo 是连接他们的边的标签。
   - SPARQL查询语⾔

    - SPARQL是⼀种⽤于三元组存储的⾯向RDF数据模型的查询语⾔。（它是SPARQL协议和RDF查询语⾔的缩写，发⾳为“sparkle”。）SPARQL早于Cypher，并且由于Cypher的模式匹配借鉴于

SPARQL，这使得它们看起来⾮常相似【37】。

- 特点- 多对多的关系：任意事物都可能与任何事物相关联。- 查询和更新数据库的代码变得复杂不灵活。- 更改应⽤程序的数据模型很难。

• 查询语言

  • 当引⼊关系模型时，关系模型包含了⼀种查询数据的新⽅法：SQL是⼀种【声明式】查询语⾔，⽽IMS和CODASYL使⽤【命令式】代码来查询数据库。

  • 声明式查询语言

    • 声明式查询语言紧密地遵循关系代数的结构。

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

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

    • 适合并⾏执⾏：声明式语⾔往往适合并⾏执⾏。现在，CPU的速度通过内核的增加变得更快，⽽不是以⽐以前更⾼的时钟速度运⾏。命令代码很难在多个内核和多个机器之间并⾏化，因为它指定了指令必须以特定顺序执⾏。

    • 图的声明式查询语⾔

      • Cypher，SPARQL和Datalog。

  • 命令式查询语言

    • 命令式语⾔告诉计算机以特定顺序执⾏某些操作。
    • 在数据库中，使⽤像SQL这样的声明式查询语⾔⽐使⽤命令式查询API要好得多 6 。
    • 声明式查询语⾔的优势不仅限于数据库。
    • MapReduce既不是⼀个声明式的查询语⾔，也不是⼀个完全命令式的查询API，⽽是处于两者之间：查询的逻辑⽤代码⽚断来表示，这些代码⽚段会被处理框架重复性调⽤。

• 其他(专业)数据模型

  • 使⽤基因组数据的研究⼈员通常需要执⾏序列相似性搜索，这意味着需要⼀个很⻓的字符串（代表⼀个DNA分⼦），并在⼀个拥有类似但不完全相同的字符串的⼤型数据库中寻找匹配。这⾥所描述的数据库都不能处理这种⽤法，这就是为什么研究⼈员编写了像GenBank这样的专⻔的基因组数据库软件的原因【48】。
  • 粒⼦物理学家数⼗年来⼀直在进⾏⼤数据类型的⼤规模数据分析，像⼤型强⼦对撞机（LHC）这样的项⽬现在可以⼯作在数百亿兆字节的范围内！在这样的规模下，需要定制解决⽅案来阻住硬件成本的失控【49】。
  • 全⽂搜索可以说是⼀种经常与数据库⼀起使⽤的数据模型。信息检索是⼀个很⼤的专业课题，我们不会在本书中详细介绍，但是我们将在第三章和第三章中介绍搜索索引。

三、存储与检索

• 目标&意义

  • 本章主题：在第2章中，我们讨论了数据模型和查询语⾔，即程序员将数据录⼊数据库的格式，以及再次找回需要的数据的机制。在本章中我们会从数据库的视⻆来讨论同样的问题：数据库如何存储我们提供的数据，以及如何在我们需要时重新找到数据。
  • 数据库的根本功能：⼀个数据库在最基础的层次上需要完成两件事情：当你把数据交给数据库时，它应当把数据存储起来；⽽后当你向数据库要数据时，它应当把数据返回给你。
  • 目标：作为⼀名应⽤程序开发⼈员，如果您掌握了有关存储引擎内部的知识，那么您就能更好地了解哪种⼯具最适合您的特定应⽤程序。以及需要调整数据库的什么参数，以达到期望的效果。

• 驱动数据库的数据结构

  • 哈希索引

    • 索引（index）为了⾼效查找数据库中特定键的值的一种数据结构。添加与删除索引，不会影响数据的内容，只影响查询的性能。维护额外的结构会产⽣开销，特别是在写⼊时。
      存储系统中⼀个重要的权衡：精⼼选择的索引加快了读查询的速度，但是每个索引都会拖慢写⼊速度。

    • 内存中的哈希映射，其中每个键都映射到⼀个数据⽂件中的字节偏移量，指明可以找到对应值的位置。当你想查找⼀个值时，使⽤哈希映射来查找数据⽂件中的偏移量，寻找（seek）该位置并读取该值。

    • 如果只是追加写⼊⼀个⽂件，如何避免最终⽤完磁盘空间？⼀种好的解决⽅案是：分段压缩和合并算法

      • i。将⽇志分为特定⼤⼩的段，当⽇志增⻓到特定尺⼨时关闭当前段⽂件，并开始写⼊⼀个新的段⽂件。然后，我们就可以对这些段进⾏压缩（compaction）。压缩意味着在⽇志中丢弃重复的键，只保留每个键的最近更新。
        ii。由于压缩经常会使得段变得很⼩（假设在⼀个段内键被平均重写了好⼏次），我们也可以在执⾏压缩的同时将多个段合并在⼀起。
        iii。段被写⼊后永远不会被修改，所以合并的段被写⼊⼀个新的⽂件。冻结段的合并和压缩可以在后台线程中完成，在进⾏时，我们仍然可以继续使⽤旧的段⽂件来正常提供读写请求。合并过程完成后，我们将读取请求转换为使⽤新的合并段⽽不是旧段 —— 然后可以简单地删除旧的段⽂件。

    • 为什么不更新⽂件，只能追加设计的原因
      有⼏个：

      • i。追加和分段合并是顺序写⼊操作，通常⽐随机写⼊快得多，尤其是在磁盘旋转硬盘上。
      • ii。如果段⽂件是附加的或不可变的，并发和崩溃恢复就简单多了。例如，您不必担⼼在更新值时发⽣崩溃的情况，⽽将包含旧值和新值的⼀部分的⽂件保留在⼀起。
      • iii。合并旧段可以避免数据⽂件随着时间的推移⽽分散的问题。

    • 哈希表索引的局限性：

      • i。散列表必须能放进内存。磁盘哈希映射表现较差。它需要⼤量的随机访问I/O，当它变满时增⻓是很昂贵的，并且散列冲突需要很多的逻辑。
      • ii。范围查询效率不⾼。

  • SSTable和LSM树

    • SSTable：在普通⽇志结构存储段都是⼀系列键值对，键值对的顺序为写⼊的顺序出现，⽇志中稍后的值优先于⽇志中较早的相同键的值。此时，如果我们要求键值对的序列按键排序。则这种格式就是【排序字符串表（Sorted String Table）】，简称SSTable。

    • SSTable的优势：

      • 1.合并段是简单⽽⾼效的，即使⽂件⼤于可⽤内存。
      • 2.因为键是有序的，所以在⽂件中找到⼀个特定的键，不再需要保存内存中所有键的索引。
      • 3.可以将记录分组到块中，并在写⼊磁盘之前进⾏压缩 ，稀疏内存中索引的每个条⽬。不仅节省了磁盘空间，压缩还可以减少IO带宽的使⽤。

    • 构建和维护SSTables

      • a。写⼊时，将其添加到内存中的平衡树数据结构（例如，红⿊树）。这个内存树有时被称为【内存表（memtable）】。
      • b。当内存表⼤于某个阈值（通常为⼏兆字节）时，将其作为SSTable⽂件写⼊磁盘。这可以⾼效地完成，因为树已经维护了按键排序的键值对。新的SSTable⽂件成为数据库的最新部分。当SSTable被写⼊磁盘时，写⼊可以继续到⼀个新的内存表实例。
      • c。为了提供读取请求，⾸先尝试在内存表中找到关键字，然后在最近的磁盘段中，然后在下⼀个较旧的段中找到该关键字。
      • d。有时会在后台运⾏合并和压缩过程以组合段⽂件并丢弃覆盖或删除的值。
      • e。这个⽅案效果很好。它只会遇到⼀个问题：如果数据库崩溃，则最近的写⼊（在内存表中，但尚未写⼊磁盘）将丢失。为了避免这个问题，我们可以在磁盘上保存⼀个单独的⽇志，每个写⼊都会⽴即被附加到磁盘上。每当内存表写出到SSTable时，相应的⽇志都可以被丢弃。该⽇志的唯⼀⽬的是在崩溃后恢复内存表。

    • SSTables的应用

      • 以上描述的算法本质上正是LevelDB和RocksDB所使用的，主要用于嵌入到其他应用程序的key-value存储引擎库。类似的引擎还被用于Cassandra和HBase。

    • LSM存储引擎

      • 基于SSTable和内存表memTable的这种索引结构最初被成为基于日志的合并树，即LSM（Log-Structure Merge Tree）。这种基于合并和压缩排序文件原理的存储引擎通常都被成为LSM存储引擎，

    • Lucene索引引擎

      • Lucene是Elasticsearch和Solr使⽤的⼀种全⽂搜索的索引引擎，它使⽤类似的⽅法来存储它的词典。全⽂索引⽐键值索引复杂得多，但是基于类似的想法：在搜索查询中给出⼀个单词，找到
        提及单词的所有⽂档（⽹⻚，产品描述等）。这是通过键值结构实现的，其中键是单词（关键词
        （term）），值是包含单词（⽂章列表）的所有⽂档的ID的列表。在Lucene中，从术语到发布列表的这种映射保存在SSTable类的有序⽂件中，根据需要在后台合并。

    • 性能优化：

      • LSM树算法在大多数情况向性能表现良好，但当查找数据库中不存在的键时，LSM树算法可能会很慢：您必须检查内存表，然后将这些段⼀直回到最⽼的（可能必须从磁盘读取每⼀个），然后才能确定键不存在。为了优化这种访问，存储引擎通常使⽤额外的Bloom过滤器。

      • 不同的策略来也会影响SSTables被压缩和合并顺序和时机。最常⻅的选择是⼤⼩分级压缩和分层压缩。

        • 大小分级压缩

          • HBase使⽤⼤⼩分级压缩，Cassandra同时⽀持。
          • 在大小分级压缩中，较新的和较小的SSTable被连续合并到较旧和较大的SSTables。

        • 分层压缩

          • LevelDB和RocksDB使⽤分层压缩（LevelDB因此得名），Cassandra同时⽀持。
          • 在分层压缩中，键的范围分裂成多个更小的SSTable，旧数据被移动到单独的“层级”，这样压缩可以逐步进行并节省磁盘空间。

      • LSM树的基本思想简单⽽有效：保存⼀系列在后台合并的SSTables。
        即使数据集⽐可⽤内存⼤得多，它仍能继续正常⼯作。由于数据按排序顺序存储，因此可以⾼效地执⾏范围查询（扫描所有⾼于某些最⼩值和最⾼值的所有键），并且因为磁盘写⼊是连续的，所以LSM树可以⽀持⾮常⾼的写⼊吞吐量。

  • B树

    • 以上讨论的⽇志结构索引正处在逐渐被接受，而应用最广泛的索引结构是B树。
      像SSTables⼀样，B树保持按键排序的键值对，这允许⾼效的键值查找和范围查询。
      ⽇志结构索引将数据库分解为可变⼤⼩的段，通常是⼏兆字节或更⼤的⼤⼩，并且总是按顺序编写段。而B树将数据库分解成固定⼤⼩的块或⻚⾯，传统上⼤⼩为4KB（有时会更⼤），并且⼀次只能读取或写⼊⼀个⻚⾯。这种设计更接近于底层硬件，因为磁盘也被安排在固定⼤⼩的块中。
      每个⻚⾯都可以使⽤地址或位置来标识，这允许⼀个⻚⾯引⽤另⼀个⻚⾯，类似于指针。我们可以在磁盘中使⽤这些⻚⾯引⽤来构建⼀个⻚⾯树，⽽不是在内存中。

    • 让B树更可靠

      • B树的基本底层写操作是⽤新数据覆盖磁盘上的⻚⾯。假定覆盖不改变⻚⾯的位置; 即当⻚⾯被覆盖时，对该⻚⾯的所有引⽤保持完整。这与⽇志结构索引（如LSM树）形成鲜明对⽐，后者只附加到⽂件（并最终删除过时的⽂件），但从不修改⽂件。但此过程是一个复杂的操作，会产生各种问题，如下：
      • 问题1: 页分裂过程中，如果此时数据库崩溃，可能导致损坏的索引，如产生孤儿页面，既不是任何父页的子页。
        解决方案：预写式⽇志（WAL,write-ahead-log），也称为重做⽇志（redo log）。该磁盘数据结构是⼀个仅追加的⽂件，每个B树修改都可以应⽤到树本身的⻚⾯上。当数据库在崩溃后恢复时，这个⽇志被⽤来使B树恢复到⼀致的状态。
      • 问题2: 并发问题：更新⻚⾯的⼀个额外的复杂情况是，如果多个线程要同时访问B树，则需要仔细的并发控制，否则线程可能会看到树处于不⼀致的状态。
        解决方案：这种情况通常通过使⽤【锁存器（latches）】（轻量级锁）保护树的数据结构来完成。⽇志结构化的⽅法在这⽅⾯更简单，因为它们在后台进⾏所有的合并，⽽不会⼲扰传⼊的查询，并且不时地将旧的分段原⼦交换为新的分段。

    • B树优化

      • a。写时复制技术：⼀些数据库（如LMDB）使⽤写时复制⽅案【21】，⽽不是覆盖⻚⾯并维护WAL进⾏崩溃恢复。修改的⻚⾯被写⼊到不同的位置，并且树中的⽗⻚⾯的新版本被创建，指向新的位置。这种⽅法对于并发控制也很有⽤，数据库“快照隔离和可重复读”中也有类似用法。
      • b。压缩键的⼤⼩：可以通过压缩键，不存储整个键来节省⻚⾯空间，特别是在树内部的⻚⾯上，键需要提供⾜够的信息来充当键范围之间的边界。在⻚⾯中包含更多的键允许树具有更⾼的分⽀因⼦，因此更少的层次。
      • c。布局树：通常，⻚⾯可以放置在磁盘上的任何位置，如果查询需要按照顺序扫描⼤部分关键字范围，每个读取的⻚⾯都可能需要磁盘查找，性能不太好。因此，许多B树实现尝试布局树，使得叶⼦⻚⾯按顺序出现在磁盘上。但是，随着树的增⻓，维持这个顺序是很困难的。相⽐之下，由于LSM树在合并过程中⼀次⼜⼀次地重写存储的⼤部分，所以它们更容易使顺序键在磁盘上彼此靠近。
      • d。树中添加额外的指针。例如，每个叶⼦⻚⾯可以在左边和右边具有对其兄弟⻚⾯的引⽤，这允许不跳回⽗⻚⾯就能顺序扫描。
      • e。B树的变体如分形树借⽤⼀些⽇志结构的思想来减少磁盘寻道（⽽且它们与分形⽆关）。

  • 比较B树与LSM树

    • 我们将简要讨论⼀些在衡量存储引擎性能时值得考虑的事情

      • 写放⼤（write amplification）：在数据库的⽣命周期中写⼊数据库导致对磁盘的多次写⼊，被称为写放⼤。
        在写⼊繁重的应⽤程序中，性能瓶颈可能是数据库可以写⼊磁盘的速度。在这种情况下，写放⼤会导致直接的性能代价，降低每秒的写入次数。

    • LSM树

      • 优点

        • 通常LSM树的写⼊速度更快。顺序写⼊⽐随机写⼊快得多。
        • 数据在磁盘上更靠近，减少磁盘查找。由于LSM树在合并过程中⼀次⼜⼀次地重写存储的⼤部分，所以它们更容易使顺序键在磁盘上彼此靠近。
        • 没有并发问题。⽇志结构化的⽅法在后台进⾏所有的合并，⽽不会⼲扰传⼊的查询，并且不时地将旧的分段原⼦交换为新的分段。
        • 更⾼的写⼊吞吐量：LSM树通常能够⽐B树⽀持更⾼的写⼊吞吐量，部分原因是它们有时具有【较低的写放⼤】（这取决于存储引擎配置和⼯作负载），部分是因为它们顺序地写⼊紧凑的SSTable⽂件⽽不是必须覆盖树中的⼏个⻚⾯。这种差异在磁性硬盘驱动器上尤其重要，【顺序写⼊⽐随机写⼊快得多】。
        • LSM树可以被压缩得更好，碎片更少。LSM树不是⾯向⻚⾯的，并且定期重写SSTables以【去除碎⽚】，所以它们具有较低的存储开销，特别是当使⽤平坦压缩时。
          B树存储引擎会由于页分裂，⽽留下⼀些不能使用的磁盘空间，从而产生磁盘碎片。

      • 缺点

        • LSM树上的读取通常⽐较慢。因为它们必须在压缩的不同阶段检查⼏个不同的数据结构和SSTables。
        • 读写操作与压缩公用磁盘资源，进而影响读写操作速度。⽇志结构存储的缺点是压缩过程有时会⼲扰正在进⾏的读写操作。尽管存储引擎尝试逐步执⾏压缩⽽不影响并发访问，但是磁盘资源有限，所以很容易发⽣请求需要等待⽽磁盘完成昂贵的压缩操作。
          在更⾼百分⽐的情况下（参阅“描述性能”），⽇志结构化存储引擎的查询响应时间有时会相当⻓，⽽B树的⾏为则相对更具可预测性。
        • 写入与压缩公用磁盘带宽，进而影响写入吞吐量。压缩的另⼀个问题出现在⾼写⼊吞吐量：磁盘的有限写⼊带宽需要在初始写⼊（记录和刷新内存表到磁盘）和在后台运⾏的压缩线程之间共享。
        • 压缩速率影响读取速度。如果写⼊吞吐量很⾼，并且压缩没有仔细配置，压缩跟不上写⼊速率。在这种情况下，磁盘上未合并段的数量不断增加，直到磁盘空间⽤完，读取速度也会减慢，因为它们需要检查更多段⽂件。通常情况下，即使压缩⽆法跟上，基于SSTable的存储引擎也不会限制传⼊写⼊的速率，此时需要进⾏明确的监控来检测这种情况。
        • 不支持事务。⽇志结构化的存储引擎可能在不同的段中有相同键的多个副本，不利于实现事务。B树的⼀个优点是每个键只存在于索引中的⼀个位置，⽽这使得B树在想要提供强⼤的事务语义的数据库中很有吸引⼒：在许多关系数据库中，事务隔离是通过在键范围上使⽤锁来实现的。

    • B树

      • 优点

        • 通常B树的读取速度更快。LSM树的写⼊速度更快。
        • 强大的事务支持。

      • 缺点

        • 维持数据的顺序较难。随着树的增⻓，维持叶⼦⻚⾯按顺序出现在磁盘上是很困难的，即使B树实现使用布局树。
        • 并发问题。需要通过使⽤锁存器（latches）（轻量级锁）保护树的数据结构来完成。
        • B树的写入速度较慢。B树索引必须⾄少两次写⼊每⼀段数据：⼀次写⼊预先写⼊⽇志，⼀次写⼊树⻚⾯本身（也许再次分⻚）。即使在该⻚⾯中只有⼏个字节发⽣了变化，也需要⼀次编写整个⻚⾯的开销。
        • B树索引必须⾄少两次写⼊每⼀段数据：⼀次写⼊预先写⼊⽇志，⼀次写⼊树⻚⾯本身（也许再次分⻚）。即使在该⻚⾯中只有⼏个字节发⽣了变化，也需要⼀次编写整个⻚⾯的开销。

  • 其他结构

    • 主键索引primary index：
      主键唯⼀标识关系表中的⼀⾏，或⽂档数据库中的⼀个⽂档或图形数据库中的⼀个顶点。数据库中的其他记录可以通过其主键（或ID）引⽤该⾏/⽂档/顶点，并且索引⽤于解析这样的引⽤。

    • 二级索引：
      ⼀个⼆级索引可以很容易地从⼀个键值索引构建。⼆级索引的键不是唯⼀的，可能有许多⾏（⽂档，顶点）具有相同的键。

    • 聚簇索引clustered index：
      在索引中存储所有⾏数据。在某些情况下，从索引到堆⽂件的额外跳跃对读取来说性能损失太⼤，因此可能希望将索引⾏直接存储在索引中，这被称为聚集索引。例如，在MySQL的InnoDB存储引擎中，表的主键总是⼀个聚簇索引，⼆级索引⽤主键⽽不是堆⽂件中的位置。

    • 非聚簇索引nonclustered index：
      仅在索引中存储对数据的引⽤。

    • 覆盖索引covering index：
      在聚集索引和⾮聚集索引之间的折衷被称为包含列的索引（index with included columns） 或覆盖索引，其存储表的⼀部分在索引内。这允许通过单独使⽤索引来回答⼀些查询，这种情况叫做：索引覆盖（cover）了查询。

    • 内存数据库

      • Memcached
      • Redis
      • VoltDB，MemSQL和Oracle TimesTen等

• 事务处理还是分析处理？

  • 存储引擎分类

    • a.在线事务处理（OLTP, OnLine
      Transaction Processing）

      • 通常⾯向⽤户
      • 可能会接受处理⼤量的请求；每个查询仅接受少量记录，要求较低。
      • 磁盘寻道时间往往是这⾥的瓶颈。
      • 存储引擎使⽤索引来提高查询效率。

    • b.在线分析处理（OLAP, OnLine Analytice
      Processing）

      • 主要由业务分析⼈员使⽤
      • 处理⽐OLTP系统少得多的查询量；但是每个查询通常要求很⾼，需要在短时间内扫描数百万条记录。
      • 磁盘带宽（不是查找时间）往往是瓶颈。
      • 列式存储是这种⼯作负载较为流⾏的解决
        ⽅案。

    • c.OLTP对比OLAP

  • OLTP两大主流存储引擎

    • a。日志结构学派

      • 特点：只允许追加写⽂件(append only)和删除过时的⽂件，但不会更新已经写⼊的⽂件。主要想法是，他们系统地将随机访问写⼊顺序写⼊磁盘，由于硬盘驱动器和固态硬盘的性能特点，可以实现更⾼的写⼊吞吐量。
      • 案例： Bitcask，SSTables，LSM树，
        LevelDB，Cassandra，HBase，Lucene等。

    • b。就地更新学派

      • 特点：将磁盘视为⼀组可以覆盖的固定⼤⼩的⻚⾯。
      • 案例：基于B树实现数据库。

• 列式存储

  • OLAP⼯作负载比OLTP高的原因：当您的查询需要在⼤量⾏中顺序扫描时，索引的相关性就会降低很多。相反，⾮常紧凑地编码数据变得⾮常重要，以最⼤限度地减少查询需要从磁盘读取的数据量。

四、编码与演化

• 可演化性：应⽤程序不可避免地随时间⽽变化。新产品的推出，对需求的深⼊理解，或者商业环境的变化，总会伴随着功能（feature）的增增改改。第⼀章介绍了可演化性(evolvability)的概念：应该尽⼒构建能灵活适应变化的系统（参阅“可演化性：拥抱变化”）。

  • 在⼤多数情况下，修改应⽤程序的功能也意味着其存储的数据格式的更改，当数据格式（format）或模式（schema）发⽣变化时，通常需要对应⽤程序代码进⾏相应的更改。但在⼤型应⽤程序中，一般需要执行滚动升级。
  • 滚动升级：新版本的服务逐步部署到少数节点，⽽不是同时部署到所有节点。滚动升级允许在不停机的情况下发布新版本的服务，并使部署⻛险降低。从⽽⿎励在罕⻅的⼤型版本上频繁发布⼩型版本，同时允许在影响⼤量⽤户之前检测并回滚有故障的版本。这些属性对于可演化性，以及对应⽤程序进⾏更改的容易性都是⾮常有利的。
  • 兼容性：滚动升级意味着新旧版本的代码，以及新旧数据格式可能会在系统中同时共处。系统想要继续顺利运⾏，就需要保持双向兼容性：
    i。向后兼容 (backward compatibility)：新代码可以读旧数据。
    ii。向前兼容 (forward compatibility)：旧代码可以读新数据。

• 编码影响点

  • 1.效率
  • 2.应用程序的体系结构和部署选项

• 编码格式及其兼容性

  • 概念

    • 程序通常（⾄少）使⽤两种形式的数据：

1. 在内存中，数据保存在对象，结构体，列表，数组，哈希表，树等中。 这些数据结构针对CPU的⾼效访问和操作进⾏了优化（通常使⽤指针）。

2. 如果要将数据写⼊⽂件，或通过⽹络发送，则必须将其编码（encode）为某种⾃包含的字节序列（例如，JSON⽂档）。 由于每个进程都有⾃⼰独⽴的地址空间，⼀个进程中的指针对任何其他进程都没有意义，所以这个字节序列表示会与通常在内存中使⽤的数据结构完全不同 1 。
   - 所以，需要在两种表示之间进⾏某种类型的翻译。 从内存中表示到字节序列的转换称为编码
   （Encoding）也称为序列化（serialization）或编组（marshalling），反过来称为解码
   （Decoding） 解析（Parsing），反序列化（deserialization），反编组(unmarshalling） 。

   • 1.编程语⾔特定的编码

     • 仅限于单⼀编程语⾔，并且往往⽆法提供前向和后向兼容性。

   • 2.JSON、XML和CSV等文本结构

     • ⾮常普遍，其兼容性取决于您如何使⽤它们。让不同的组织达成⼀致的难度较大。
     • 对于数据类型有些模糊，所以你必须⼩⼼数字和⼆进制字符串。
     • JSON虽然区分字符串和数字，但不区分整数和浮点数，⽽且不能指定精度。
     • CSV没有任何模式，因此应⽤程序需要定义每⾏和每列的含义。

   • 3.Thrift、Protocol Buffers和Avro等二进制模式驱动的格式

     • 紧凑，⾼效
     • 允许使⽤清晰定义的前向和后向兼容性语意，以提供较好的兼容性。
     • 这些模式可以用于静态类型语言的文档和代码生成，但是数据在解码前不可读

• 数据流的类型

  • 1.数据库中的数据流

    • 数据写入者对数据编码，数据读取者对数据解码。

  • 2.服务中的数据流：RPC和Rest API

    • 具象状态传输（REST）和远程过程调⽤（RPC）
    • 客户端对请求编码，服务端接受请求并解码，并对响应编码，客户端对响应解码。

  • 3.消息中的数据流：异步消息传递

    • 节点之间通过发送消息进行通信，消息有发送者编码，由接受者解码。