数据密集型系统设计

数据系统的基石

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

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.消息中的数据流：异步消息传递

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