DDIA学习笔记

数据系统的基石

可靠性、可伸缩性、可维护性

Reliability

• 系统在 困境（adversity，比如硬件故障、软件故障、人为错误）中仍可正常工作（正确完成功能，并能达到期望的性能水准）

• 造成错误的原因叫做 故障（fault），能预料并应对故障的系统特性可称为 容错（fault-tolerant） 或 韧性（resilient）

• 注意 故障（fault） 不同于 失效（failure）。故障 通常定义为系统的一部分状态偏离其标准，而 失效 则是系统作为一个整体停止向用户提供服务。故障的概率不可能降到零，因此最好设计容错机制以防因 故障 而导致 失效

• 硬件故障（hardware faults）:

  1. 硬盘崩溃、内存出错、机房断电、有人拔错网线……

  2. 硬盘的 平均无故障时间（MTTF, mean time to failure） 约为 10 到 50 年

  3. 对策：

     • 增加单个硬件的冗余度
     • 云平台的设计优先考虑 灵活性（flexibility） 和 弹性（elasticity），而不是单机可靠性
     • 在硬件冗余的基础上进一步引入软件容错机制

• 软件错误 系统性错误（systematic error）

1. 例子：

   • 接受特定的错误输入，便导致所有应用服务器实例崩溃的 BUG。例如 2012 年 6 月 30 日的闰秒，由于 Linux 内核中的一个错误，许多应用同时挂掉了。
   • 失控进程会用尽一些共享资源，包括 CPU 时间、内存、磁盘空间或网络带宽。
   • 系统依赖的服务变慢，没有响应，或者开始返回错误的响应。

2. 导致这类软件故障的 BUG 通常会潜伏很长时间，直到被异常情况触发为止。这种情况意味着软件对其环境做出了某种假设 —— 虽然这种假设通常来说是正确的，但由于某种原因最后不再成立了

3. 对策：

   • 仔细考虑系统中的假设和交互

   • 彻底的测试

   • 进程隔离；允许进程崩溃并重启

   • 测量、监控并分析生产环境中的系统行为。如果系统能够提供一些保证（例如在一个消息队列中，进入与发出的消息数量相等），那么系统就可以在运行时不断自检，并在出现 差异（discrepancy） 时报警

• 人为错误

  1. 设计并构建了软件系统的工程师是人类，维持系统运行的运维也是人类。即使他们怀有最大的善意，人类也是不可靠的。

  2. 对策：

     • 以最小化犯错机会的方式设计系统。例如，精心设计的抽象、API 和管理后台使做对事情更容易，搞砸事情更困难。但如果接口限制太多，人们就会忽略它们的好处而想办法绕开。很难正确把握这种微妙的平衡。
     • 将人们最容易犯错的地方与可能导致失效的地方 解耦（decouple）。特别是提供一个功能齐全的非生产环境 沙箱（sandbox），使人们可以在不影响真实用户的情况下，使用真实数据安全地探索和实验。
     • 在各个层次进行彻底的测试，从单元测试、全系统集成测试到手动测试。自动化测试易于理解，已经被广泛使用，特别适合用来覆盖正常情况中少见的 边缘场景（corner case）。
     • 允许从人为错误中简单快速地恢复，以最大限度地减少失效情况带来的影响。 例如，快速回滚配置变更，分批发布新代码（以便任何意外错误只影响一小部分用户），并提供数据重算工具（以备旧的计算出错）。
     • 配置详细和明确的监控，比如性能指标和错误率。 在其他工程学科中这指的是 遥测（telemetry）（一旦火箭离开了地面，遥测技术对于跟踪发生的事情和理解失败是至关重要的）。监控可以向我们发出预警信号，并允许我们检查是否有任何地方违反了假设和约束。当出现问题时，指标数据对于问题诊断是非常宝贵的。

• 可靠性有多重要

  1. 即使在 “非关键” 应用中，我们也对用户负有责任。

  2. 我们偷工减料时，应该清楚意识到自己在做什么。

Scalability

• 有合理的办法应对系统的增长（数据量、流量、复杂性）

• 系统今天能可靠运行，并不意味未来也能可靠运行。服务 降级（degradation） 的一个常见原因是负载增加，例如：系统负载已经从一万个并发用户增长到十万个并发用户，或者从一百万增长到一千万。也许现在处理的数据量级要比过去大得多。

• 描述负载

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

  2. 例子：twitter业务:

     • 发布推文

       用户可以向其粉丝发布新消息（平均 4.6k 请求 / 秒，峰值超过 12k 请求 / 秒）

     • 主页时间线

       用户可以查阅他们关注的人发布的推文（300k 请求 / 秒）

     • 方法一：全局推文集合，关系型数据库

       发布推文时，只需将新推文插入全局推文集合即可。当一个用户请求自己的主页时间线时，首先查找他关注的所有人，查询这些被关注用户发布的推文并按时间顺序合并。

       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

     • 方法二：为每个用户的主页时间线维护一个缓存。

       当一个用户发布推文时，查找所有关注该用户的人，并将新的推文插入到每个主页时间线缓存中。 因此读取主页时间线的请求开销很小，因为结果已经提前计算好了。

     • 推特的第一个版本使用了方法 1，但系统很难跟上主页时间线查询的负载。所以公司转向了方法 2，方法 2 的效果更好，因为发推频率比查询主页时间线的频率几乎低了两个数量级，所以在这种情况下，最好在写入时做更多的工作，而在读取时做更少的工作。

     • 然而方法 2 的缺点是，发推现在需要大量的额外工作。平均来说，一条推文会发往约 75 个关注者，所以每秒 4.6k 的发推写入，变成了对主页时间线缓存每秒 345k 的写入。但这个平均值隐藏了用户粉丝数差异巨大这一现实，一些用户有超过 3000 万的粉丝，这意味着一条推文就可能会导致主页时间线缓存的 3000 万次写入！及时完成这种操作是一个巨大的挑战 —— 推特尝试在 5 秒内向粉丝发送推文。

     • 在推特的例子中，每个用户粉丝数的分布（可能按这些用户的发推频率来加权）是探讨可伸缩性的一个关键负载参数，因为它决定了扇出负载。你的应用程序可能具有非常不同的特征，但可以采用相似的原则来考虑它的负载。

     • 推特轶事的最终转折：现在已经稳健地实现了方法 2，推特逐步转向了两种方法的混合。大多数用户发的推文会被扇出写入其粉丝主页时间线缓存中。但是少数拥有海量粉丝的用户（即名流）会被排除在外。当用户读取主页时间线时，分别地获取出该用户所关注的每位名流的推文，再与用户的主页时间线缓存合并，如方法 1 所示。这种混合方法能始终如一地提供良好性能。

• 描述性能

  1. 一旦系统的负载被描述好，就可以研究当负载增加会发生什么。我们可以从两种角度来看：

     • 增加负载参数并保持系统资源（CPU、内存、网络带宽等）不变时，系统性能将受到什么影响？
     • 增加负载参数并希望保持性能不变时，需要增加多少系统资源？

  2. 对于 Hadoop 这样的批处理系统，通常关心的是 吞吐量（throughput），即每秒可以处理的记录数量，或者在特定规模数据集上运行作业的总时间

  3. 对于在线系统，通常更重要的是服务的 响应时间（response time），即客户端发送请求到接收响应之间的时间

     • 延迟（latency） 和 响应时间（response time） 经常用作同义词，但实际上它们并不一样。

     • 响应时间是客户所看到的，除了实际处理请求的时间（ 服务时间（service time） ）之外，还包括网络延迟和排队延迟。

     • 延迟是某个请求等待处理的 持续时长，在此期间它处于 休眠（latent） 状态，并等待服务

     • 即使不断重复发送同样的请求，每次得到的响应时间也都会略有不同。现实世界的系统会处理各式各样的请求，响应时间可能会有很大差异。因此我们需要将响应时间视为一个可以测量的数值 分布（distribution），而不是单个数值。

     • 响应时间的高百分位点（也称为 尾部延迟，即 tail latencies）非常重要，因为它们直接影响用户的服务体验。例如亚马逊在描述内部服务的响应时间要求时是以 99.9 百分位点为准，即使它只影响一千个请求中的一个。这是因为请求响应最慢的客户往往也是数据最多的客户，也可以说是最有价值的客户 ——因为他们掏钱了。保证网站响应迅速对于保持客户的满意度非常重要，亚马逊观察到：响应时间增加 100 毫秒，销售量就减少 1%；而另一些报告说：慢 1 秒钟会让客户满意度指标减少 16%。

       另一方面，优化第 99.99 百分位点（一万个请求中最慢的一个）被认为太昂贵了，不能为亚马逊的目标带来足够好处。减小高百分位点处的响应时间相当困难，因为它很容易受到随机事件的影响，这超出了控制范围，而且效益也很小。

     • 百分位点通常用于 服务级别目标（SLO, service level objectives） 和 服务级别协议（SLA, service level agreements），即定义服务预期性能和可用性的合同。 SLA 可能会声明，如果服务响应时间的中位数小于 200 毫秒，且 99.9 百分位点低于 1 秒，则认为服务工作正常（如果响应时间更长，就认为服务不达标）。这些指标为客户设定了期望值，并允许客户在 SLA 未达标的情况下要求退款。

     • 排队延迟（queueing delay） 通常占了高百分位点处响应时间的很大一部分。由于服务器只能并行处理少量的事务（如受其 CPU 核数的限制），所以只要有少量缓慢的请求就能阻碍后续请求的处理，这种效应有时被称为 头部阻塞（head-of-line blocking） 。即使后续请求在服务器上处理的非常迅速，由于需要等待先前请求完成，客户端最终看到的是缓慢的总体响应时间。因为存在这种效应，测量客户端的响应时间非常重要。

     • 为测试系统的可伸缩性而人为产生负载时，产生负载的客户端要独立于响应时间不断发送请求。如果客户端在发送下一个请求之前等待先前的请求完成，这种行为会产生人为排队的效果，使得测试时的队列比现实情况更短，使测量结果产生偏差。

• 应对负载的方法

  1. 纵向伸缩（scaling up，也称为垂直伸缩，即 vertical scaling，转向更强大的机器）

  2. 横向伸缩（scaling out，也称为水平伸缩，即 horizontal scaling，将负载分布到多台小机器上）

  3. 跨多台机器部署 无状态服务（stateless services） 非常简单，但将带状态的数据系统从单节点变为分布式配置则可能引入许多额外复杂度。出于这个原因，常识告诉我们应该将数据库放在单个节点上（纵向伸缩），直到伸缩成本或可用性需求迫使其改为分布式。

  4. 随着分布式系统的工具和抽象越来越好，至少对于某些类型的应用而言，这种常识可能会改变。可以预见分布式数据系统将成为未来的默认设置，即使对不处理大量数据或流量的场景也如此。本书的其余部分将介绍多种分布式数据系统，不仅讨论它们在可伸缩性方面的表现，还包括易用性和可维护性。

  5. 大规模的系统架构通常是应用特定的 —— 没有一招鲜吃遍天的通用可伸缩架构（不正式的叫法：万金油（magic scaling sauce） ）。应用的问题可能是读取量、写入量、要存储的数据量、数据的复杂度、响应时间要求、访问模式或者所有问题的大杂烩。

     举个例子，用于处理每秒十万个请求（每个大小为 1 kB）的系统与用于处理每分钟 3 个请求（每个大小为 2GB）的系统看上去会非常不一样，尽管两个系统有同样的数据吞吐量。

  6. 一个良好适配应用的可伸缩架构，是围绕着 假设（assumption） 建立的：哪些操作是常见的？哪些操作是罕见的？这就是所谓负载参数。如果假设最终是错误的，那么为伸缩所做的工程投入就白费了，最糟糕的是适得其反。在早期创业公司或非正式产品中，通常支持产品快速迭代的能力，要比可伸缩至未来的假想负载要重要的多。

Maintainability

• 许多不同的人（工程师、运维）在不同的生命周期，都能高效地在系统上工作（使系统保持现有行为，并适应新的应用场景）

• 可操作性（Operability）

  便于运维团队保持系统平稳运行

• 简单性（Simplicity）

  从系统中消除尽可能多的 复杂度（complexity），使新工程师也能轻松理解系统（注意这和用户接口的简单性不一样）

  1. 简化系统并不一定意味着减少功能；它也可以意味着消除 额外的（accidental） 的复杂度。 Moseley 和 Marks把 额外复杂度 定义为：由具体实现中涌现，而非（从用户视角看，系统所解决的）问题本身固有的复杂度。

  2. 用于消除 额外复杂度 的最好工具之一是 抽象（abstraction）。一个好的抽象可以将大量实现细节隐藏在一个干净，简单易懂的外观下面。一个好的抽象也可以广泛用于各类不同应用。比起重复造很多轮子，重用抽象不仅更有效率，而且有助于开发高质量的软件。抽象组件的质量改进将使所有使用它的应用受益。

     例如，高级编程语言是一种抽象，隐藏了机器码、CPU 寄存器和系统调用。 SQL 也是一种抽象，隐藏了复杂的磁盘 / 内存数据结构、来自其他客户端的并发请求、崩溃后的不一致性。当然在用高级语言编程时，我们仍然用到了机器码；只不过没有 直接（directly） 使用罢了，正是因为编程语言的抽象，我们才不必去考虑这些实现细节。

• 可演化性（evolvability）

  使工程师在未来能轻松地对系统进行更改，当需求变化时为新应用场景做适配。也称为 可伸缩性（extensibility）、可修改性（modifiability） 或 可塑性（plasticity）

数据模型与查询语言

多数应用使用层层叠加的数据模型构建。对于每层数据模型的关键问题是：它是如何用低一层数据模型来 表示 的？例如：

1. 作为一名应用开发人员，你观察现实世界（里面有人员、组织、货物、行为、资金流向、传感器等），并采用对象或数据结构，以及操控那些数据结构的 API 来进行建模。那些结构通常是特定于应用程序的。
2. 当要存储那些数据结构时，你可以利用通用数据模型来表示它们，如 JSON 或 XML 文档、关系数据库中的表或图模型。
3. 数据库软件的工程师选定如何以内存、磁盘或网络上的字节来表示 JSON / XML/ 关系 / 图数据。这类表示形式使数据有可能以各种方式来查询，搜索，操纵和处理。
4. 在更低的层次上，硬件工程师已经想出了使用电流、光脉冲、磁场或者其他东西来表示字节的方法。

一个复杂的应用程序可能会有更多的中间层次，比如基于 API 的 API，不过基本思想仍然是一样的：每个层都通过提供一个明确的数据模型来隐藏更低层次中的复杂性。这些抽象允许不同的人群有效地协作（例如数据库厂商的工程师和使用数据库的应用程序开发人员）。

关系模型与文档模型

• NoSQL 被追溯性地重新解释为 不仅是 SQL（Not Only SQL），其背后的驱动因素有：

  1. 需要比关系数据库更好的可伸缩性，包括非常大的数据集或非常高的写入吞吐量
  2. 相比商业数据库产品，免费和开源软件更受偏爱
  3. 关系模型不能很好地支持一些特殊的查询操作
  4. 受挫于关系模型的限制性，渴望一种更具多动态性与表现力的数据模型

• 新的非关系型 “NoSQL” 数据存储在两个主要方向上存在分歧：

  1. 文档数据库 的应用场景是：数据通常是自我包含的，而且文档之间的关系非常稀少。
  2. 图形数据库 用于相反的场景：任意事物都可能与任何事物相关联。

• 在可预见的未来，关系数据库似乎可能会继续与各种非关系数据库一起使用 - 这种想法有时也被称为 混合持久化（polyglot persistence）。

• 目前大多数应用程序开发都使用面向对象的编程语言来开发，这导致了对 SQL 数据模型的普遍批评：如果数据存储在关系表中，那么需要一个笨拙的转换层，处于应用程序代码中的对象和表，行，列的数据库模型之间。模型之间的不连贯有时被称为 阻抗不匹配（impedance mismatch）

  1. 像 ActiveRecord 和 Hibernate 这样的 对象关系映射（ORM object-relational mapping） 框架可以减少这个转换层所需的样板代码的数量，但是它们不能完全隐藏这两个模型之间的差异。

  2. 对于一个像简历这样自包含文档的数据结构而言，JSON 表示是非常合适的。JSON 比 XML 更简单。面向文档的数据库（如 MongoDB ，RethinkDB ，CouchDB 和 Espresso）支持这种数据模型。

     {
       "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"
       }
     }

数据查询语言

• SQL 是一种 声明式 查询语言

• 许多常用的编程语言是命令式的。

• web上的声明式查询：用css选择器

  li.selected > p {
    background-color: blue;
  }

• web上的命令式查询：在 Javascript 中，使用 文档对象模型（DOM） API

  var liElements = document.getElementsByTagName("li");
  for (var i = 0; i < liElements.length; i++) {
      if (liElements[i].className === "selected") {
          var children = liElements[i].childNodes;
          for (var j = 0; j < children.length; j++) {
              var child = children[j];
              if (child.nodeType === Node.ELEMENT_NODE && child.tagName === "P") {
                  child.setAttribute("style", "background-color: blue");
              }
          }
      }
  }

• MapReduce 是一个由 Google 推广的编程模型，用于在多台机器上批量处理大规模的数据。一些 NoSQL 数据存储（包括 MongoDB 和 CouchDB）支持有限形式的 MapReduce，作为在多个文档中执行只读查询的机制。

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

图数据模型

一个图由两种对象组成：顶点（vertices，也称为 节点，即 nodes，或 实体，即 entities），和 边（edges，也称为 关系，即 relationships，或 弧，即 arcs）。多种数据可以被建模为一个图形。典型的例子包括：

• 社交图谱

  顶点是人，边指示哪些人彼此认识。

• 网络图谱

  顶点是网页，边缘表示指向其他页面的 HTML 链接。

• 公路或铁路网络

  顶点是交叉路口，边线代表它们之间的道路或铁路线。

可以将那些众所周知的算法运用到这些图上：例如，汽车导航系统搜索道路网络中两点之间的最短路径，PageRank 可以用在网络图上来确定网页的流行程度，从而确定该网页在搜索结果中的排名。

在刚刚给出的例子中，图中的所有顶点代表了相同类型的事物（人、网页或交叉路口）。不过，图并不局限于这样的同类数据：同样强大地是，图提供了一种一致的方式，用来在单个数据存储中存储完全不同类型的对象。例如，Facebook 维护一个包含许多不同类型的顶点和边的单个图：顶点表示人，地点，事件，签到和用户的评论；边缘表示哪些人是彼此的朋友，哪个签到发生在何处，谁评论了哪条消息，谁参与了哪个事件，等等。

存储与检索

• 数据模型和查询语言:

  程序员将数据录入数据库的格式，以及再次要回数据的机制。

• 存储与检索:

  数据库如何存储程序员提供的数据，以及如何在程序员需要时重新找到数据。

驱动数据库的数据结构

• bash: set与get

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

• 为了高效查找数据库中特定键的值，我们需要一个数据结构：索引（index）。索引背后的大致思想是通过保存一些额外的元数据作为路标来帮助你找到想要的数据。如果你想以几种不同的方式搜索同一份数据，那么你也许需要在数据的不同部分上建立多个索引。

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

散列索引

1. 键值数据（key-value Data） 的索引。

2. 键值存储与在大多数编程语言中可以找到的 字典（dictionary） 类型非常相似，通常字典都是用 散列映射（hash map） 或 散列表（hash table） 实现的。既然我们已经可以用散列映射来表示 内存中 的数据结构，为什么不使用它来索引 硬盘上 的数据呢？

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

4. 现实中，Bitcask 实际上就是这么做的（Riak 中默认的存储引擎）

   像 Bitcask 这样的存储引擎非常适合每个键的值经常更新的情况。例如，键可能是某个猫咪视频的网址（URL），而值可能是该视频被播放的次数（每次有人点击播放按钮时递增）。在这种类型的工作负载中，有很多写操作，但是没有太多不同的键 —— 每个键有很多的写操作，但是将所有键保存在内存中是可行的。

5. 直到现在，我们只是追加写入一个文件 —— 所以如何避免最终用完硬盘空间？一种好的解决方案是，将日志分为特定大小的段（segment），当日志增长到特定尺寸时关闭当前段文件，并开始写入一个新的段文件。然后，我们就可以对这些段进行 压缩（compaction）。这里的压缩意味着在日志中丢弃重复的键，只保留每个键的最近更新。

6. 可以同时执行压缩和分段合并

7. 每个段现在都有自己的内存散列表，将键映射到文件偏移量。为了找到一个键的值，我们首先检查最近的段的散列映射；如果键不存在，我们就检查第二个最近的段，依此类推。合并过程将保持段的数量足够小，所以查找过程不需要检查太多的散列映射。

8. 值得考虑的问题：

   • 文件格式

     CSV 不是日志的最佳格式。使用二进制格式更快，更简单：首先以字节为单位对字符串的长度进行编码，然后是原始的字符串（不需要转义）。

   • 删除记录

     如果要删除一个键及其关联的值，则必须在数据文件中追加一个特殊的删除记录（逻辑删除，有时被称为墓碑，即 tombstone）。当日志段被合并时，合并过程会通过这个墓碑知道要将被删除键的所有历史值都丢弃掉。

   • 崩溃恢复

     如果数据库重新启动，则内存散列映射将丢失。原则上，你可以通过从头到尾读取整个段文件并记录下来每个键的最近值来恢复每个段的散列映射。但是，如果段文件很大，可能需要很长时间，这会使服务的重启比较痛苦。 Bitcask 通过将每个段的散列映射的快照存储在硬盘上来加速恢复，可以使散列映射更快地加载到内存中。

   • 部分写入记录

     数据库随时可能崩溃，包括在将记录追加到日志的过程中。 Bitcask 文件包含校验和，允许检测和忽略日志中的这些损坏部分。

   • 并发控制

     由于写操作是以严格的顺序追加到日志中的，所以常见的实现是只有一个写入线程。也因为数据文件段是仅追加的或者说是不可变的，所以它们可以被多个线程同时读取。

9. append-only的优势：

   • 追加和分段合并都是顺序写入操作，通常比随机写入快得多，尤其是在磁性机械硬盘上。在某种程度上，顺序写入在基于闪存的 固态硬盘（SSD） 上也是好的选择。
   • 如果段文件是仅追加的或不可变的，并发和崩溃恢复就简单多了。例如，当一个数据值被更新的时候发生崩溃，你不用担心文件里将会同时包含旧值和新值各自的一部分。
   • 合并旧段的处理也可以避免数据文件随着时间的推移而碎片化的问题。

10. 散列表索引也有其局限性：

    • 散列表必须能放进内存。如果你有非常多的键，那真是倒霉。原则上可以在硬盘上维护一个散列映射，不幸的是硬盘散列映射很难表现优秀。它需要大量的随机访问 I/O，当它用满时想要再增长是很昂贵的，并且散列冲突的处理也需要很烦琐的逻辑。
    • 范围查询效率不高。例如，你无法轻松扫描 kitty00000 和 kitty99999 之间的所有键 —— 你必须在散列映射中单独查找每个键。

SSTable和LSM树

1. 排序字符串表（Sorted String Table），简称 SSTable

   • 对段文件的格式做一个简单的改变：要求键值对的序列按键排序
   • 还要求每个键只在每个合并的段文件中出现一次（压缩过程已经保证）

2. 现在我们可以让我们的存储引擎以如下方式工作：

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

3. 用SSTables制作LSM树（日志结构合并树）

   LSM 树的基本思想 —— 保存一系列在后台合并的 SSTables —— 简单而有效。即使数据集比可用内存大得多，它仍能继续正常工作。由于数据按排序顺序存储，你可以高效地执行范围查询（扫描所有从某个最小值到某个最大值之间的所有键），并且因为硬盘写入是连续的，所以 LSM 树可以支持非常高的写入吞吐量。

B树

1. 像 SSTables 一样，B 树保持按键排序的键值对，这允许高效的键值查找和范围查询。但这也就是所有的相似之处了：B 树有着非常不同的设计理念。

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

3. 每个页面都可以使用地址或位置来标识，这允许一个页面引用另一个页面 —— 类似于指针，但在硬盘而不是在内存中。我们可以使用这些页面引用来构建一个页面树

   一个页面会被指定为 B 树的根；在索引中查找一个键时，就从这里开始。该页面包含几个键和对子页面的引用。每个子页面负责一段连续范围的键，引用之间的键，指明了引用子页面的键范围。

4. 在 B 树的一个页面中对子页面的引用的数量称为分支因子。在实践中，分支因子取决于存储页面引用和范围边界所需的空间量，但通常是几百个。

5. 如果要更新 B 树中现有键的值，需要搜索包含该键的叶子页面，更改该页面中的值，并将该页面写回到硬盘（对该页面的任何引用都将保持有效）。如果你想添加一个新的键，你需要找到其范围能包含新键的页面，并将其添加到该页面。如果页面中没有足够的可用空间容纳新键，则将其分成两个半满页面，并更新父页面以反映新的键范围分区

6. 这个算法可以确保树保持平衡：具有 n 个键的 B 树总是具有 O (log n)的深度。大多数数据库可以放入一个三到四层的 B 树，所以你不需要追踪多个页面引用来找到你正在查找的页面（分支因子为 500 的 4KB 页面的四层树可以存储多达 256TB 的数据）。

7. 让B树更可靠:

   • B 树的基本底层写操作是用新数据覆写硬盘上的页面，并假定覆写不改变页面的位置：即，当页面被覆写时，对该页面的所有引用保持完整。这与日志结构索引（如 LSM 树）形成鲜明对比，后者只追加到文件（并最终删除过时的文件），但从不修改文件中已有的内容。
   • 你可以把覆写硬盘上的页面对应为实际的硬件操作。在磁性硬盘驱动器上，这意味着将磁头移动到正确的位置，等待旋转盘上的正确位置出现，然后用新的数据覆写适当的扇区。在固态硬盘上，由于 SSD 必须一次擦除和重写相当大的存储芯片块，所以会发生更复杂的事情
   • 注意，一些操作需要覆写几个不同的页面。例如，如果因为插入导致页面过满而拆分页面，则需要写入新拆分的两个页面，并覆写其父页面以更新对两个子页面的引用。这是一个危险的操作，因为如果数据库在仅有部分页面被写入时崩溃，那么最终将导致一个损坏的索引（例如，可能有一个孤儿页面不是任何父项的子项） 。
   • 为了使数据库能处理异常崩溃的场景，B 树实现通常会带有一个额外的硬盘数据结构：预写式日志（WAL，即 write-ahead log，也称为 重做日志，即 redo log）。这是一个仅追加的文件，每个 B 树的修改在其能被应用到树本身的页面之前都必须先写入到该文件。当数据库在崩溃后恢复时，这个日志将被用来使 B 树恢复到一致的状态
   • 另外还有一个更新页面的复杂情况是，如果多个线程要同时访问 B 树，则需要仔细的并发控制 —— 否则线程可能会看到树处于不一致的状态。这通常是通过使用 锁存器（latches，轻量级锁）保护树的数据结构来完成。日志结构化的方法在这方面更简单，因为它们在后台进行所有的合并，而不会干扰新接收到的查询，并且能够时不时地将旧的段原子交换为新的段。

8. B树的优化：

   • 一些数据库（如 LMDB）使用写时复制方案，而不是覆盖页面并维护 WAL 以支持崩溃恢复。修改的页面被写入到不同的位置，并且还在树中创建了父页面的新版本，以指向新的位置。这种方法对于并发控制也很有用

   • B+树

     我们可以通过不存储整个键，而是缩短其大小，来节省页面空间。特别是在树内部的页面上，键只需要提供足够的信息来充当键范围之间的边界。在页面中包含更多的键允许树具有更高的分支因子，因此也就允许更少的层级

   • 额外的指针已被添加到树中。例如，每个叶子页面可以引用其左边和右边的兄弟页面，使得不用跳回父页面就能按顺序对键进行扫描。

• 比较LSM树和B树

  1. 根据经验，通常 LSM 树的写入速度更快，而 B 树的读取速度更快。 LSM 树上的读取通常比较慢，因为它们必须检查几种不同的数据结构和不同压缩（Compaction）层级的 SSTables。

  2. LSM树的优点：

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

     • 由于反复压缩和合并 SSTables，日志结构索引也会多次重写数据。这种影响 —— 在数据库的生命周期中每次写入数据库导致对硬盘的多次写入 —— 被称为 写放大（write amplification）。需要特别注意的是固态硬盘，固态硬盘的闪存寿命在覆写有限次数后就会耗尽。

     • LSM 树通常能够比 B 树支持更高的写入吞吐量，部分原因是它们有时具有较低的写放大（尽管这取决于存储引擎的配置和工作负载），部分是因为它们顺序地写入紧凑的 SSTable 文件而不是必须覆写树中的几个页面。这种差异在磁性硬盘驱动器上尤其重要，其顺序写入比随机写入要快得多。

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

     • 在许多固态硬盘上，固件内部使用了日志结构化算法，以将随机写入转变为顺序写入底层存储芯片，因此存储引擎写入模式的影响不太明显。但是，较低的写入放大率和减少的碎片仍然对固态硬盘更有利：更紧凑地表示数据允许在可用的 I/O 带宽内处理更多的读取和写入请求。

  3. LSM树的缺点:

     • 日志结构存储的缺点是压缩过程有时会干扰正在进行的读写操作。尽管存储引擎尝试增量地执行压缩以尽量不影响并发访问，但是硬盘资源有限，所以很容易发生某个请求需要等待硬盘先完成昂贵的压缩操作。对吞吐量和平均响应时间的影响通常很小，但是日志结构化存储引擎在更高百分位的响应时间有时会相当长，而 B 树的行为则相对更具有可预测性。

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

     • 如果写入吞吐量很高，并且压缩没有仔细配置好，有可能导致压缩跟不上写入速率。在这种情况下，硬盘上未合并段的数量不断增加，直到硬盘空间用完，读取速度也会减慢，因为它们需要检查更多的段文件。通常情况下，即使压缩无法跟上，基于 SSTable 的存储引擎也不会限制传入写入的速率，所以你需要进行明确的监控来检测这种情况。

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

事务处理还是分析

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

• 博客文章的评论，游戏中的动作，地址簿中的联系人，处理商业交易

• 应用程序通常使用索引通过某个键查找少量记录。根据用户的输入插入或更新记录。

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

• 哪个牌子的婴儿食品最常与 X 品牌的尿布同时购买？一月份每个商店的总收入是多少？

• 通常，分析查询需要扫描大量记录，每个记录只读取几列，并计算汇总统计信息（如计数、总和或平均值），而不是将原始数据返回给用户。

属性	事务处理系统 OLTP	分析系统 OLAP
主要读取模式	查询少量记录，按键读取	在大批量记录上聚合
主要写入模式	随机访问，写入要求低延时	批量导入（ETL）或者事件流
主要用户	终端用户，通过 Web 应用	内部数据分析师，用于决策支持
处理的数据	数据的最新状态（当前时间点）	随时间推移的历史事件
数据集尺寸	GB ~ TB	TB ~ PB

数据仓库

1. 在二十世纪八十年代末和九十年代初期，企业有停止使用 OLTP 系统进行分析的趋势，转而在单独的数据库上运行分析。这个单独的数据库被称为 数据仓库（data warehouse）。

2. 将数据存入仓库的过程称为 “抽取 - 转换 - 加载（ETL）”

   extract, transform, load

3. 事实表

4. 维度表