数据系统基础

可靠、可扩展与可维护的应用系统

对于数据密集型应用，CPU的处理能力往往不是第一限制性因素，在于数据量、数据的复杂度及数据的快速多变性。数据密集型应用通常也是基于标准模块构建而成，每个模块负责单一的常用功能。例如，许多应用系统都包含以下模块：

• 数据库： 用以存储数据，这样之后应用可以再次访问
• 调整缓存：缓存那些复杂或操作代价昂贵的结果，以加快下一次访问。
• 索引：用户可以按安搜索数据并支持各种过滤。
• 流式处理：持续发送消息臻另一个进程，处理采用异步方式
• 批处理：定期处理大量的累积数据。

可靠性

当出现意外情况，如硬件、软件故障、人为失误等，系统应可以继续正常运转：虽然性能可能有所降低，但确保功能正确。对于软件,典型的可靠性期望包括:

• 应用程序执行用户据期望的功能.
• 可以容忍用户出现错误或者不正确的软件使用方法
• 性能可以应对典型场景, 合理负载原动力和数据量
• 系统可防止任何示经授权的访问和滥用

• 硬件故障

• 软件故障

  • 原因

    • 由于软件错误
    • 一个应用进程使用了某些共享资源,但却不幸失控
    • 系统统带于某些服务,但该服务突然或无响应
    • 级联故障

• 人为失误

  • 如果假定人是不可靠的,那么该如何保证系统的可靠性?

    • 以最小出错的方式来设计系统.
    • 想办法分离最容易出错的地方,容易引发故障的接口.
    • 充分的测试
    • 当出现人为失误时,提供快速的恢复机制以尽量减少故障影响
    • 设置详细而清晰的监控子系统
    • 推行管理流程并加以培训.

• 可靠性的重要性

可扩展性

随着规模的增长，例如数据量、流量或复杂性，系统应以合理的方式来匹配这种增长。可扩展性是描述系统应对负载增加能力的术语。它并不是衡量一个系统的一维指标，谈论“x是可扩展的”或“y不扩展”没有太大意义。相反，讨论可扩展性通常要考虑这类问题：“如果系统以某种方式增长，我们应对增长的措施有哪些”，“我们该如何添加计算资源来处理额外的负载”。

• 描述负载

  负载可以用称为负载参数的若干数字来描述，参数的最佳选择取决于系统的体系结构。如Web服务器的每秒请示处理次数，数据库中定稿的比例等。

• 描述性能

  • 延迟和响应时间

    延迟和响应时间容易混淆使用，通常响应时间是客户端看到的：除了处理请示时间外还包括来回网络延迟和各种排除延迟。延迟是请示花费在处理上的时间。有时，即使所有请示都相同，也会由于其他变量因素而引入一些延迟拉动，这些因素包括上下文切换和进程调度、网络数据包丢失和TCP重传、垃圾回收暂停、缺页中断和磁盘IO,甚至服务器机架的机械振动等。我们经常考察的是服务请示的平均响应时间，然后如果想知道更典型的响应时间，平均值并不是合适的指标，因为它掩盖了一些信息，无法告诉有多少用户实际经历了多少延迟。因此最好使用百分位数(percentiles)。如果已经搜集到了响应时间信息，将其从最快到最慢排序，中位数(median)就是列表中间的响应时间。中位数指标非常适合描述多少用户需要等待多长时间，通常缩写为p50。为了弄清楚异常值有多糟糕，需要关注更大的百分位数，如觉的p95, p99和p999。采用较高的响应时间百分位数很重要，因为它们直接影响用户的总体服务体验。百分位数通常用于描述、定义服务质量目标（Service Level Objectives, SLO）和服务质量协议（Service Level Agreements, SLA），这些是规定服务预期质量和可用性的合同。排队延迟往往在高百分数响应时间中影响很大。由于服务器并行处理的请示有限，正在处理的少数请示可能会阻挡后续请示，这种情况有时被称为队头阻塞。即使后续请示可能处理很简单，但它阻塞在等待先前请示的完成，客户端会观察到极慢的响应时间。

• 应对负载增加的方法

  把无状态服务分布然后扩展臻多台机器相对比较容易，而有状态服务从单个节点扩展到分布式多机环境的复杂性会大大增加。出于这个原因，址到最近通常的做法一直是，将数据库运行在一个节点上（采用垂直扩展策略），直到高扩展性或高可用性的要求近使不得不做水平扩展。超大规模的系统往往针对特定应用而高度定制，很验证有一种通用的架构。背后取舍因素包括数据读取量、写入量、待存储的数据量、的复杂程度、响应时间要求、访问模式等，或者更多的是上述所有因素的叠加，再加上其他更复杂的问题。对于特定应用来说，扩展能力好的架构通常会做出某些假设，然后有针对性地优化设计，如哪些操作是最频繁的，哪 些负载是少数情况。可扩展架构通常都是从通用模块逐步构建而来， 背后往往有规律可循。

可维护性

随着时间的失衡，许多新的人员参与到系统开发和运维，以维护现有功能或甜酸新场景等，可维护性包括维护与缺陷修复，监控系统来保持正常运行、故障排查、适配新平台、搭配新场景、技术担风险的完善以及增加新功能等。

• 我们需要特别关注软件系统的三个设计原则

  • 可运维性

    方便运营团队来保持系统平衡运行。

    • 运营团队负责的主要内容

      1. 监视系统的健康状况，并在服务出现异常状态时快速恢复服务。
      2. 追踪问题的原因，例如系统故障或性能下降。
      3. 保持软件和平台臻最新状态
      4. 了解不同系统如何相互影响，避免执行带有破坏性的操作。
      5. 预测未来可能的问题，并在问题发生之前即解决。
      6. 建立用于部署、配置管理待良好的实中规范和工具包。
      7. 执行复杂的维护任务
      8. 当配置更改时，维护系统的安全稳健
      9. 制定流程来规范操作行为，并保持生产环境稳定。
      10. 保持相关知识的传承（如对系统的理解）。

    • 数据系统设计要点

      1. 提供对系统运行时行为和内部的可观测性，方便监控。
      2. 支持自动化，与标准工具集成。
      3. 避免绑定特定的机器，这样在整个系统不间断运行的同时，允许机器停机维护。
      4. 提供良好的文档和易于理解的操作模式。
      5. 提供良好的默认配置，且允许管理员在需要时方便地修改默认值。
      6. 尝试自我修复，在需要时让管理员手动控制系统状态。
      7. 行为可预测，减少意外发生。

  • 简单性

    简化系统复杂性，使新工程师能够轻松理解系统。复杂性有各种各样的表面方式：状态空间的膨胀，模块紧耦合，令人纠结的相互依赖关系，不一致的命名和术语，为了性能而的特殊片，为解决某特定问题而引入的特殊框架等。简化系统设计并不意味关减少系统功能，而主要意味着意外方面的复杂性。消除意外复杂性最好手段之一是抽象。

  • 可演化性

    后续工程师能够轻松地对系统进行改进，并根据需求变化将其适配到非典型场景，也称为可延伸性、易修改性可可塑性。

数据模型与查询语言

关系模型与文档模型

• 关系模型

  关系模型所做的是定义了所有数据的模式：关系（表）只是元组（行）的分文不值一，公此而已。没有复杂的嵌套结构，也没胡复杂的访问路径。可以读取表中的任何一行或者所有行，支持任意条件查询。可以指定某些列作为键并匹配这些列来读取特定行。可以在任何表中插入新行，而不必担心与其他表之间的外键关系。关系模型的一个核心要点是：只需要构建一次查询优化器，然后使用该数据库的所有应用程序都可以从中受益。

• NoSQL

  • 采用NoSQL数据库的驱动因素

    1. 比关系数据库更好的扩展性需求，錍巴拉圭超 大数据集或超市写入吞量
    2. 普通偏爱免费和开源软件而不是商业数据库产品。
    3. 关系模型不能很好地支持一些特定的查询操作。
    4. 对关系模式一些限制性感到沮丧，渴望更具动态和表达力的数据模型。

• 对象-关系不匹配

• 多对一与多对多的关系

  • 使用ID比使用纯文本字符串的优势

    1. 所有的数据保持和输入值一致。
    2. 避免歧义。
    3. 易于更新。
    4. 本地化支持。
    5. 更好的搜索支持。

• 网络模型

  也被称为CODASYL模型，是层次模型的推广。在层次模型的要结构中，每个记录只有一个父结点；而在网络模型中，一个记录可能有多个父结点。

• 关系数据库与文档数据库现状

  支持文档数据模型的主要论点是模式灵活性，由于局部性而带来较好的性能，对于某些应用来说，它更接近于应用程序据使用的数据结构。关系模型则强在联结操作、多对一和多对多关系更简洁的表达上。

  • 哪种数据模型的应用代码更简单？

    如果应用数据具有类似文档的结构，那么使用文档模型更为合适。而关系型模型则倾向于某种数据分解，它把文档结构分解为多个表，有可能使得模式更为笨重，以及不必要的应用代码复杂化。文档也有一定的局限性：例如，不能直接引用文档中的嵌套项，然而只要文档嵌套不太深，这通常不是问题。在文档数据库中，对联结的支持不足是否是问题取决于应用程序。但是如果应用程序确实使用了多对多关系，那么文档模型就变得不太吸引人。通常无法一概而论哪种数据模型的应用代码更简单。这主要取决于数据项之间的关系类型。

  • 文档模型中的模式灵活性

    文档数据库有时被称为无模型，wxjg这具有误导性，因为读数据的代码通常采用某种结构因而存在某种隐形模式，而不是由数据库强制执行。更准确的术语应该是读时模型，与写时模式（关系数据库的一种传统方法，模式是显式的，并且数据库确保数据写入时都必须遵循）相对应。读时模式类似编程语言中的动态（运行时）类型检查，而写时模式类似于静态（编译时）类型检查。

  • 查询数据局部性

    文档通常存储为编码为JSON、XML或其它二进制变化的连接字符串。如果应用程序需要频繁访问整个文档，则存储局部性具有性能优势。如果数据被在多个表中，则需要进行多次索引查找来检索所有数据，蹭可能需要更多的duteIO并花费更多的时间。局部性优势公适用需要同时访问文档大部分内容的场景。由于数据库通常会加载整个文档，如果应用只是访问其中的一小部分，则对于大型文档数据来讲就有些浪费。对于文档更新时，通常会重写整个文档，而只有修改量不改变源文件大小时，原地覆盖更新有更有效。因此，通常建议文档应该尽量小且避免定稿时增加文档大小。这些性能方面的不利因素大大限制了文档数据库的适用场景。

  • 文档数据库与关系数据库的融合

数据查询语言

• 声明式查询

  声明式查询语言很有吸引力，它比命令式API更加简洁和容易使用。但更重要的是，它对外隐藏了数据库引擎的很多实现细节，这样数据库系统能够在不改变查询语句的情况下提高性能。声明式语言通常适合于并行执行,它仅仅指定了结果所满足的模式，而不指定如何得到结果的具体算法。所以如果可以的话，数据库者倾向于采用并行方式实现查询语言。

  • Web上的声明式查询

    • css
    • xpath

  • MapReduce查询

    MapReduce既不是声明式查询语言，也不是一个完全命令式的查询API,而是介于两者之间：查询的逻辑用代码片段来表示，这些代码片段可以被处理框架重复地调用。它主要基于许多函数式编程语言中的map（也称为collect)和reduce(也称为fold或inject)函数。 map和reduce函数对于可执行的操作有所限制。它们必须是纯函数，这意味着只能使用传递进去的数据作为输入，而不能执行额外的数据库查询，也不能有任何副作用。这些限制使得数据库能够在任何位置、以任意顺序来运行函数，并在失败时重新运行这些函数。

图状数据模型

如果多对多的关系在数据中很觉，随着数据之间的关联越来越复杂，将数据建模转的为图模型会更加自然。图由两种对象组成：顶点（也称为结点或实体）和边（也称为关系或弧）。很多数据可以建模为图，例如：社交网络，web图，公路或铁路网。有多种不同但相关的方法可以构建和查询图中的数据。我们讨论属性图模型（property graph, 以Neo4j、Titan和InfiniteGraph为代表）和三元存储模型（triplestore、以Datomic、AllegroGraph等为代表）。讨论三种声明式图查询语言：Cypher、SPARQL和Datalog.这外，还有像Gremlin这样的命令式图查询语言，以及Pregel这样的图处理框架。

• 图属性

  在属性图模型中，每个顶点包括：

  • 唯一的标识符
  • 出边的集合
  • 入边的集合
  • 属性的集合（键值对）

  每个边包括：

  • 唯一的标识符
  • 边开始的顶点（尾部顶点）
  • 边结束的顶点（头部顶点）
  • 描述两个顶点间关系类型的标签
  • 属性的集合（健值对）

  可以将图存储看作由两个关系表组成，一个用于顶点，一个用于边。关于图模型一些值得注意的地方：

  1. 任何顶点都可以连接到其他任何顶点。没有模式限制哪种事物可以或不可以关联。
  2. 给定某个顶点，可以高效地得到它的所有入边和出边，从而遍历图，即沿着这些顶点链条一直有向前或向后。
  3. 通过对不同类型的关系使用不同的标签，可以在单个图中存储多种不同类型的信息，同时仍然保持整洁的数据模型。

• Cypher查询语言

  Cypher是一种用于属性图的声明式查询语言，最早为Neo4j图形数据库而创建。一个例子：

  create
    (NAmerica:Location {name: 'North America', type:'continet'}),
    (USA:Location {name: 'United States', type:'country'})
    (Idaho:Location {name:'Idaho', type:'state'}),
    (Lucy:Person {name:'Lucy'}),
    (Idaho) - [:WITHIN]-> (USA) -[:WITHIN]->(NAmerica),
    (Lucy) -[:BORN_IN]-> (Idaho)
  

• SQL中的图查询

  Crypher可以用:WITHIN*0..非常简洁地表达它沿着一个WINTHIN边遍历零次或多次。SQL:1999标准以后，查询过程中这种可变的遍历路径可以使用称为递归公用表表达式（即WITH RECURSIVE语法）来表示，但与Cypher相比，语法仍显得非常笨拙。

• 三元存储与SPARQL

  三元存储模式几乎等同于 属性图模型，只是使用不同的名词描述了相同的思想。在三元存储中，所有信息都以非常简单的三部分形式存储（主体，谓语，客体）。三元组的主体相当于图中的顶点。而客体则是以下两种之一：

  • 原始数据类型中的值，如字符串或数字。在这种情况下，三元组的谓语和客体分别相当于主体（顶点）属性中的键和值。
  • 图中的另一个顶点。此时，谓语是图中的边，主体是尾部顶点，而客体是头部顶点。
  • 语义网
  • RDF数据模型

  • SPARQL查询语言

    SPARQL是一种采用RDF数据模型的三元存储查询语言，名字是SPARQL Protocol和RDF Query Language的缩写一个例子：

    PREFIX : <urn:example:>
    select ?personName where {
      ?person :name ?personName.
      ?person :bornIn / :within* / :name "United States".
      ?person :livesIn / :within* / :name "Europe".
    }
    

    可以看到总体结构与Cypher非常相似。

    (person) -[:BORN_IN]-> () -[:WITHIN*0..] -> (location)  #Cypher
    ?person :bornIn / :within* ?location.   #SPARQL
    

    由于RDF不区分属性和边，可以同时对两者执行谓语操作，所以可以采用相同的语法来匹配属性上的查询条件。

• Datalog基础

  Datalog的数据模型类似于三元存储模式，但更为通用一些。它采用“谓语（主体，客体）”的表达方式而不是三元组（主体，谓语，客体）。已经定义好了数据之后，可以执行之前类似的查询，Datalog是Prolog的子集。一个例子：

  name(usa, 'United States').
  type(usa, country).
  within(usa, namerica).
  
  within_recursive(Location, Name) :- name(Location, Name). # 规则1
  within_recursive(Location, Name) :- within(Location, Via),
                                       within_recursive(Via, Name).   # 规则2
  magrated(Name, BornIn, LivingIn) :- name(Person, name),
                                       born_in(Person, BornLoc),
                                       within_recursive(BornLoc, BornIn),
                                       livs_in(Person, LivingLoc),
                                       within_recursive(LivingLoc, LivingIn).   # 规则3
  ?- migrated(Who, 'United States', "Europe").
  

  Datalog方法需要采取与其他查询语言略有不同的思维方式，但它非常强大，特别是规则可以在不同的查询中组合和重用。对于简单的一次性查询来说，这或许不太方便，但是如果数据非常复杂，处理起来会更加游刃有余。

小结

历史上，数据最初被表示为一棵大树（层次模型），但是这不利于表示多对多关系，所以发明了关系模型来解决这个问题。最近，开发人员发现一些应用程序也不太适合关系模型。新的非关系“NoSQL”数据存储在两个主要方向上存在分歧：

1. 文档数据库的目标用例是数据来自于自包含文档，且一个文档与其他文档之间的关联很少。
2. 图数据库则针对相反的场景，目标用命是所有数据都可能会互相关联。所有这三种模型（文档模型、关系模型和图模型），如今都有广泛使用，并且在各有自的目标领域都足够优秀。

数据存储与检索

从最基本的层面看，数据库只需要做两件事情：向它插入数据时，它就保存数据；之后查询时，它应该返回那些数据。

数据库核心：数据结构

• 索引

  索引是基于原始数据派生而来的额外数据结构。由于每次写数据时，需要更新索引，因此任何类型的索引通常都会降低写的速度。这里涉及存储系统中重要的权衡设计：适当的索引可以加速读取查询，但每个索引都会减慢写速度。为此，默认情况下，数据库通常不会对所有内容进行fphx,它需要应用开发人员或数据库管理员，基于对应用程序典型查询模式的了解，来手动选择索引。目的是为了应用程序提供最有利加速的同时，避免引入过多不必要的开销。

  • 哈希索引

    • 哈希索引的局限性

      • 哈希表必须全部放入内存，所以如果有大量的键，就没那么幸运了。原则上，可以在磁盘上维护hash map,但是不幸的是，很难使磁盘上的hash map表现良好。它需要大量的随机访问IO,当哈希变满时，继续增长代价昂贵，并且哈希冲突时需要复杂的处理逻辑。
      • 区间查询效率不高。

  • SSTables和LSM-Tree

    简单改变key-value日志文件的格式：要求key-value对的顺序按键排序。这种格式称为排序字符串表，或简称为SSTable.它要求每个键在每个合并的段文件中只能出现一次。 SSTable相比哈希索引的日志段，具有以下优点：

    1. 合并段更加简单高效，即使文件大于可用内存。
    2. 在文件中查找特定的键时，不再需要在内存中保存所有键的索引。
    3. 由于读请示往往需要扫描后未范围内的多个key-value对，可以考虑将这些记录保存到一个上并在写磁盘之前将其压缩。然后稀疏内存索引的每个条目指向压缩块的开头。除了节省磁盘空间，压缩还减少了IO带宽的占用。

    • 构建和维护SSTables

      • 存储引擎的基本工作流程如下：

        1. 当写入时，将其添加到内存跌平衡树数据结构中（例如红黑树）。这个内存中的树有时被称为内存表。
        2. 当内存表大于某个阈值（通常为几兆字节）时，将其作为SSTable文件写入磁盘。由于树已经维护了按键排序的key-value对，写磁盘可以比较高效。新的SSTable文件成为数据库的最新部分。当SSTable写磁盘的同时，写入可以继续添加到一个新的内存表实例。
        3. 为了处理读请示，首先尝试在内存表中查找键，然后是最新的段文件，接下来是次新的谁的，以此类推，直到找到目标（或为空）。
        4. 后台进程周期性地执行段合并与压缩过程，以合并多个段文件，并丢弃那些已经被覆盖或删除的值。上述方案可以很好地工作。但它还存在一个问题：如果数据库崩溃，最近的定稿（在内存表中但尚未写入磁盘）将会丢失。

    • 从STables到LSM-Tree

      基于合并和压缩排序文件原理的存储引擎通常都被称为LSM存储引擎。

  • 性能优化

    查找数据库中某个不存在的键时，LSM-Tree算法可能很慢：在确定键不存在之前必须先检查内存表，然后将段一直回溯访问到最旧的段文件。为了优化这种访问，存储引擎通常使用额外的过滤器。还有一同的策略会影响甚至决定SSTables压缩和合并时的具体顺序和时机。最觉的方式是大小分组和分层压缩。在大小分级的压缩中，较新的和较小的SSTables被连续合并到较旧和较大的SSTables.在分层中，键的范围分裂成多个更小的SSTables,旧数据被移动到单独的“层级”，这样压缩可以逐步进行并节省磁盘空间。

  • B-trees

    B-tree将数据库分解成固定大小的块或页、传统上大小为4KB（有时更大），页是内部读/写的最小单元。这种设计更接近底层硬件，因为磁盘也是以固定大小的块排列。每个页面都可以使用地址或位置进行标识，这样可以让一个页面引用另一个页面，类似指针，不过是指向磁盘地址，而不是内存。可以使用这些页面引用来构造一个树状页面，某一页被指定为B-tree的楖每当查询索引中的一个键时，总是从这里开始。该页面包含若干个键和对子页的引用。每个孩子 都负责一个连续范围内的键，相信引用之间的键可以指示这些范围之间的边界。 B-tree中一个页所包含的子页引用数量称为分支因子。在实际中，分支因素取决于存储页面引用和范围边界据需的空间总量，通常为几百个。如果需要更新B-tree中现有的值，首先搜索包含该键的叶子页，更改该页的值，并将页写回到磁盘。如果要添加新键，则需要找到其范围包含新键的页，并将其添加到该页。如果页中没有足够的可用空间来容纳新的那家，则将其分裂为两个半满的页，并且父页也需要更新以包含分裂之后的新的键范围。该算法确保树保持平衡：具有N个键的B-tree总是具有O(log n)的深度。

    • 使B-tree可靠

      B-tree底层的基本写操作操作是使用新数据覆盖磁盘上的旧页。它假设覆盖不会改变页的磁盘存储位置，也就是说，当页被覆盖时，对该页的所有引用保持不变。为了使数据库能从崩溃中恢复，常见B-tree的实现需要支持磁盘上的额外的数据结构：预写日志（write-ahead log, WAL），也称为重做日志。这是一个公支持追加修改的文件，每个B-tree的修改必须先更新WAL然后再修改树本身的页。原地更新页的另一个复杂因素是，如果多个线程要同时访问B-tree,则需要注意并发控制，否则线程可能会看到树处于不一致的状态。通常使用锁存器（轻量级锁）保护树的数据结构来完成。

    • 优化B-tree

      • 一些数据库不使用覆盖页和维护RAL来进行崩溃恢复，而是使用写时复制方案。修改的页被定稿不同的位置，树中父页的新版本被创建，并指向新的位置。这种方法对于前功尽弃控制也很有帮助。
      • 保存键的缩略信息，而不是完整的键，这样可以节省页空间。
      • 一般来说，页可以放在磁盘上的任何位置；没有要求相信的页需要放在磁盘的相信位置。如果查询需要按照排序扫描大段的键范围，考虑到每个读取的页都可能需要磁盘IO,所以逐页的而已可能是低效的。因此，许多B-tree的实现深度对树进行布局，以便相信叶子页可以按顺序保存在磁盘上。
      • 添加额外的指针到上。例如每个叶子页面可能会向左和向右引用其同级的兄弟页，这样可以顺序扫描键，而不用跳回到父页。
      • B-tree的谈何如分形树，借鉴了一些日志结构的想法来减少磁盘寻道。

  • 对比B-tree和LSM-tree

    根据经验，LSM-tree通常对于定稿更快，而B-tree被认为对于读取更快。

    • LSM-tree的优点

      • LSM-tree通常能够承受比B-tree更高的写入吞量，原因是磁盘的顺序写比随机写要快的多。
      • LSM-tree可以支持更好的压缩，因此通常磁盘上的文件比B-tree小很多。

    • LSM-tree的缺点

      • 日志结构存储的缺点是压缩过程有时会干扰正在进行的读写操作。
      • 高写入吞量时，磁盘的有一般说来a要在初始写入和后台运行的压缩线程之间所共享。如果写入吞量很高并且压缩没有仔细配置，那么就会发生压缩无法匹配新数据定稿速率的情况。

  • 其它索引结构

    • 在索引中存储值

      索引中的键是查询搜索的对象，而值则可以是以下两类之一：它可能是实际行，也可以是对其他地方存储的行的引用。在保存其他地方引用时，存储行的具体位置被称为堆文件，并且它不以特定的顺序存储数据。在某些情况下，从索引到堆文件的额外跳转对于读取来说意味着太多的性能损失，因此可能希望交款地直接存储在索引中，这被称为聚焦索引。例如MySQL InnoDB存储引擎中，表的主键始终是聚集索引，二级索引引用主键。

    • 多列索引

      最常见的多列索引类型称为级联索引，它通过将一列追加到另一列，将几个字段简单地组合成一个键。

    • 全文搜索和模糊索引

      全文搜索引擎通常支持对一个音讯的所有同义词进行查询，并忽略音讯语法上的变化，在同一文档中搜索彼此接近的音讯珠出现，并且支持多种依赖语言分析的其他高级功能。

    • 在内存中保存所有内容

      内存数据库的性能优势并不是因为它们不需要从磁盘读取，而是因为它们避免使用写磁盘的格式对内存数据结构编码的开销。

事务处理与分析处理

事务主要指组成一个逻辑单元的一组读写操作。

• 数据仓库

  使用单独的数据仓库而不是直接查询OLTP系统进行分析，很大的优势在于数据仓库可以针对分析访问模式进行优化。

  • OLTP数据库和数据仓库之间的差异

    数据仓库的数据模型最常见的是关系型，因为SQL通常适合分析查询。

  • 星型与雪花型分析模式

    许多数据仓库都相当公式化的使用了星型模式，也称为维度建模。模式的中心是一个所谓的事实表。青衫表的每一行表示在特定的时间发生的事件。事实表中的列是属性, 其他列可能会引用其他表的外键，称为维度表。该模板一个谈何称为雪花模式，其中维度进一步细分为子空间。

列式存储

面向列存储的想法很简单：不要将一行中的所有值存储在一起，而是将每列中的所有值存储在一起。如果每个列存储在一个单独的文件中，查询只需要读取和解析在该查询中使用的那些列，这可以节省大量的工作。面向列的存储布局依赖一组列文件，每个文件以相同顺序保存着数据行。

• 列压缩

  除了公从磁盘中加载查询所需的迾这个，还可以通过压缩数据来进一步降低对磁盘吞量的要求。

• 内存带宽和矢量化处理

• 列存储的排序

  在列存储中，行的存储顺序并不太重要。最简单的是插入顺序保存。

• 列存储的写操作

  面向列的存储、压缩和排序都非常有乃至于加速读取查询。但是，它们的缺点是让写入更加困难。我们可以使用LSM-tree.将所有的写入首行进入内存存储区，将其添加到已排序的结构中，接着再准备写入磁盘。执行查询时，需要检查磁盘上的烈vrnt内存中的最近的定稿，并结合这两者。

• 聚合：数据立方体与物化视图

  如果许多不同查询使用相同的聚合，每次都处理原始数据将非常浪费，我们可以创建一种缓存：物化视图。物化视图是查询结果的实际副本，并被写到磁盘，而虚拟视图只是用于编写查询的快捷方式。当底层数据发生变化时，物化视图也需要随之更新，因为它是数据的非规范化副本。数据库可以自动执行，但这种更新方式会影响数据写入性能，这就是为什么在OLTP数据库中不经常使用物化视图的原因。

数据编码与演化

数据编码格式

• 程序通常使用（至少）两种不同的数据表示形式：

  • 在内存中，数据保存在对象、结构体、列表、数组、哈希表和树等结构中。这些数据结构针对CPU的高效访问和操作进行了优化（通常使用指针）。
  • 将数据写入文件或通过网络发送时，必须将其编码为某种自包含的字节序列（例如JSON文档）。由于指针对其他进程没有意义，所以这个字节序列表示看起来与内存中使用的数据结构大不一样。

  因此，在这两种表示之间需要进行类型的转化。

  • 从内存中的表示到字节序列的转化称为编码（或序列化等），相反的过程称为解码（或解析，反序列化）。

• 语言特定的格式

  许多编程语言都内置支持将内存跌对象编码为字节序列。这些编码库使用起来非常方便，然后这里也有一些深层次的问题：

  • 编码通常与特定的编程语言绑定在一起，而用另一种语言访问数据就非常困难。
  • 为了在相同的对象类型中恢复数据，解码过程需要能够实例化任意的类型。这经常导致一些安全问题。
  • 在这些库中，多版本数据通常是次要的，主要目标是快速且简单地编码数据，所以它们经常忽略向前和向后兼容性等问题。
  • 效率（编码或解码花费的CPU时间，以及编码结构的大小）通常也是次要的。

• JSON、XML与二进制变体

  目标转向可由不同编程语言编写和读取的标准化编码，显然JSON和XML是其中佼佼者。CSV是另一种流行的与语言无关的格式，尽管功能较弱。

  • JSON、xml和CSV都是文件格式，因此具有不错的可读性

  • 它们一些微妙的问题

    • 数字编码有很多模糊之处。
    • JSON和XML对Unicode字符串（即人类可读文本）有很好的支持，但是它们不支持二进制字符串（没有字符编码的字节序列）。
    • JSON和XML都有可选的模式支持。
    • CSV没有任何模式，因此应用程序需要定义每行和每列的含义。如果应用程序更改添加新的行或列，则必须手动处理该更改。

• 二进制编码

  对于仅在组织内部使用的数据，使用二进制编码格式则较为顺畅。

• Thrift与Protocol Buffers

  Thrift与protocol Buffers都需要要模式来编码任意的数据。

  • 字段标签和模式演化

    模式不可避免地需要随着时间而不断变化，称之为模式演化。一条编码记录只是一组编码字段的拼接。每个字段由其标签号标识，并使用数据类型进行注释。如果没有设置字段值，则将其从编码的记录中简单地忽略。由此可以看出，字段标签（filed tag）对编码数据的含义至关重要。可以轻松更改模式中字段的名称，而编码永远不直接引用字段名称。但是不能随便更改字段的标签，它会导致所有现有编码数据无效。可以添加新的字段到模式，只要给每个字段一个新的标记号码。如果旧的代码（不知道添加的新标记号码）试图读取新代码写入的数据，包括一个它不能识别的标记号码中新的字段，则它可以简单地忽略该字段。实现时，通过数据类型的注释来通知解析器跳过特定的字节数。这样可以实现向前兼容性，即旧代码可以读取由新代码编写的记录。

  • 数据类型和模式演化

    如果改变字段的数据类型，已存在值会丢失精度或被截断的风险。

• Avro

  Apache Avro是另一种二进制编码格式。 Avro也使用模式来指定编码的数据结构。它有两种模式语言：一种Avro IDL用于人工编辑，另一种基于JSON更易于机器读取。

  • 写模式与读模式

    模式解析通过字段名匹配字段。如果读取数据的代码遇到出现在写模式但不在上的字段，则忽略。如果读取数据的代码需要某个字段，但是写模式不包含该名称的字段，则使用在读模式中声明的默认值填充。

  • 模式演化规则

    使用Avro,向前兼容意味着可以将新版本的模式作为writer,并将旧版本的模式作为reader.相反，向后兼容意味着可以用新版本的模式作为reader, 并用旧版本的模式作为writer. 为了保持兼容性，只能添加或删除具有默认值的字段。在某些编程语言中，null是所有变量可以接受的默认值。但是在Avro中并非如些：如果要允许字段为null,则必须使用联合类型。例出:union{null, long, string}.只有当null是联合的分支之一时，才可以使用它作为默认值。

  • 动态生成的模式
  • 代码生成和动态类型语言

• 模式的优点

  • 它们可以比各种“二进制JSON”变体更紧凑，可以省略编码数据中的字段名称。
  • 模式是一种有价值的文档形式，因为模式是解码所必需的，所以可以确定它是最新的
  • 模式数据库允许在部署任何内容之前检查模式更改的向前和向后兼容性。
  • 对于静态类型编程语言的用户来说，从模式生成代码的能力是有用的，它能够在编译时进行类型检查。

数据流模式

• 基于数据库的数据流

  • 不同时间写入不同的值

    数据库通常支持在任何时候更新任何值。这意味着在单个数据库中，可能有一些值是在5ms前写入的，而有一些值在5年前写入的。

  • 归档存储

• 基于服务的数据流：REST和RPC

  对于需要通过网络进行通信的进程，有多种不同的通信方式。面向服务/微服务体系结构的一个关键的设计目标是：通过使服务可独立部署和演化，让应用程序更易于更改和维护。

  • 网络服务

    有两种流行的web服务方法： REST和SOAP.

    • Rest

      rest不是一种协议，而是一个基于HTTP原则的设计理念。它强调简单工，使用URL来标识资源，并使用HTTP功能进行缓存控制、身份验证和内容类型协商。

    • SOAP

      SOAP是一种基于XML的协议，用于发出网络API请求。

  • 远程过程调用（RPC）的问题

• 基于消息传递的数据流

  • 与直接RPC相比，使用消息代理的优点

    • 如果接收方不可用或过载，它可以充当缓冲区，从而提高系统的可靠性。
    • 它可以自动将消息重新发送到崩溃的进程，从而防止消息丢失。
    • 它避免了发送方需要知道的接收方的IP地址和端口号
    • 它支持将一条消息发送给多个接收方。
    • 它在逻辑上将发送方与接收方分离。

分布式数据系统

出于以下目的，我们需要在多台机器上分布数据：

• 扩展性当数据量或者读写负载巨大，严重超出了单台机器的处理上限，需要将负载分散到多台机器上。
• 容错与高可用性
• 延迟

数据复制

复制主要指通过互联网络在多台机器上保存相同数据的副本。

• 通过复制方案，通常希望达到以下目的

  • 使数据在地理位置上更接近用户，从而降低访问延迟
  • 当部分组件出现故障，系统依然可以继续工作，从而提高可用性
  • 扩展至多台机器以同时提供数据访问服务，从而搞读吞吐量

主节点与从节点

• 主从复制的工作原理

  1. 指定某一个副本为主副本（或称为主节点）。当客户写数据库时，必须将写请求首行发送给主副本，主副本首行将新数据定稿本地存储。
  2. 其他副本则全部称为从副本（或称为从节点）。主副本把新数据写入本地存储后，然后将数据更改作为复制的日志或更改流发送给所有从副本。每个从副本获得更改日志之后将其应用到本地，且严格保持与主副本相同的写入顺序。
  3. 客户端从数据库中读数据时，可以在主副本或者从副本上执行查询。

• 同步复制与异步复制

• 配置新的从节点

  • 逻辑上添加新节点的主要步骤

    1. 在某个时间节点对主节点的数据副本产生一个一致性快照，这样避免长时间锁定整个数据库。
    2. 将此快照拷贝到新的从节点。
    3. 从节点连接到主节点并请求快照点之后所发生的数据更改日志。
    4. 获得日志之后，从节点来应用这些快照点之后所有数据变更。

• 处理节点失效

  • 从节点失效：追赶式恢复

    如果失效的是从节点，而且从节点还能重新启动连接，那么只需要从失效的最后一条事务追赶日志即可。

  • 从节点失效：节点切换

    如果失效的是主节点，需要选择某个从节点将其提升为主节点，客户端也需要更新，这样之后的写请求会发送给新的主节点，然后其他从节点要接受来自新的主节点上的变更数据。

    • 自动切换主节点的步骤

      1. 确认主节点失效。
      2. 选举新的主节点。
      3. 重新配置系统使新主节点生效。

    • 常见问题

      • 如果使用了异步复制，且失效前，新的主节点并未收到原主节点的所有数据，在选举之后，原主节点很快又重新上线并加入到集群，接下来的写操作时新的主节点很可能会收到冲突的写请求，这是因为原主节点未意识到角色的yoqx,还会深度同步其他从节点，但其中的一个现在已经接管成为现任主节点。常见的方案是，原主节点上未完成复制的写请求就此丢弃。
      • 如果在数据库之外有其他系统依赖玗数据库的内容并在一起协同使用，丢弃数据的方案就特别危险。
      • 在某些故障情况下，可能会发生两个节点同时都自认为是主节点。
      • 如何设置合适的超时来检测主节点失效？主节点失效后，超时时间设置得越长也意味着总体恢复时间就越长。

• 复制日志的实现

  • 基于语句的复制

    主节点记录所执行的每个写请求并将该操作语句作为日志发送给从节点。

    • 不适用场景

      • 调用任何非确定性函数的语句，如now()。
      • 如果语句中使用了自增列，或者依赖于数据库的现有数据，则所有副本必须按照完全相同的顺序执行，否则可能会带来不同的结果。
      • 有副作用的语句，可能会在每个副本上产生不同的副作用。

  • 基于预写日志（WAL）传输

    主要缺点是日志描述的数据结果非常底层：一个WAL包含了哪些磁盘块的哪些字节发生改变，诸如此类的细节。这使得复制方案和存储引擎紧密耦合。如果数据库的存储格式从一个版本改为另一个版本，那么系统通常无法支持主从节点上运行不同版本的软件。

  • 基于行的逻辑日志复制

    关系数据库的逻辑日志通常是指一系列记录来描述数据表行级别的写请求：

    • 对于行插入，日志包含所有相关列的新值。
    • 对于行删除，日志里有足够的信息来唯一标识已删除的行，通常是靠主键，但如果表上没有定义主键，就需要记录所有列的旧值。
    • 对于行更新，日志包含足够的信息来唯一标识更新的行，以及所有列的新值（或至少包含所有已更新列的新值）。

    如果一条事务涉及多行的修改，则会产生多个这样的日志记录，并在后面跟着一条记录，指出该事务已提交。 MySQL的二进制日志binlog（当配置为基于行的复制时）使用该方式。由于逻辑日志与存储引擎逻辑解耦，因此可以更容易地保持向后兼容，从而使主节点能够运行不同版本的软件甚至是不同的存储引擎。

  • 基于触发器的复制

    基于触发器的复制通常比其他复制方式开销更高，也比数据库内置复制更容易出错，或者暴露一些限制。然而，其调度灵活性仍有用武之地。

• 复制滞后问题

  如果一个应用正好从一个异步的从节点读取数据，而该副本落后于主切点，则应用可能会读到过期的信息。

  • 读自己的写

    • 基于主从复制的系统该如何实现写后读一致性？

      • 如果用户访问可能会被修改的内容，从主切点读取；否则，在从节点读取。
      • 如果应用的大部分内容都可能被所有用户修改，那么上衣服针不太有效，它会导致大部分内容都必须经由主节点。
      • 客户端还可以记住最近更新捍的时间戳，并附带在誌上，据此信息，系统可以确保对该用户提供读服务时都应该至少包含了该时间戳的更新。
      • 如果副本分布在多数据中心，情况会照相结。必须先把请求路由到主节点所在的数据中心。

    • 如果同一用户可能会从多个设备访问数据，情况会变得更加复杂，需要考虑更多的一些问题

      • 记住用户上次更新时间戳的方法实现起来会比较困难，因为在一台设备上运行的代码完全无法知道在其他设备上发生了什么。些时，元数据必须做到全局共享。
      • 如果副本分布在多数据中心，无法保证来自不同设备的连接经过路由之后都到达同一个数据中心。

  • 单调读

    单调读保证，如果某个用户依次进行多次读取，则他绝不会看到回滚现象，即在读取较新值之后又发生读旧值的情况。实现单调读的一种方式是，确保每个总是从固定的同一副本执行读取。

    • 前缀一致读

      如果数据库总是以相同的顺序写入，则读取总是看到一致的序列，不会发生逻辑混乱。然后，在许多分布式数据库中，不同的分区独立运行，因此不存在是全局写入顺序。这就导致当用记从数据库中读数据时，可能会看到数据库的某部分旧值和另一部分新值。一个解决方案是确保任何具有因果顺序关系的写入都交给一个分区来完成，但该方案真实实现效率会大打折扣。

    • 复制滞后的解决方案

      使用最终一致性系统时，最好事先京思考这样的问题：如果复制延迟增加到几分钟甚至几小时，那么应用层的行为会是什么样子？如果答案是“没问题”，那没得说。但是，如果带来糟糕的用户体验，那么在设计系统时，就要考虑提供一个更xkjr一致性保证，比如写后读。

多主节点复制

• 主从复制明显的缺点

  系统只有一个主节点，而所有写入都必须经过主节点。如果由于某种原因，例如与主节点之间的网络中断而导致主节点无法连接，主从复制方案就会影响所有的写入操作。

• 适用场景

  在一个数据中心内部使用多主节点基本没有太大意义，其复杂性已经超过所能带来的好处。

  • 多数据中心

    在每个数据中心都配置主节点，在每个数据中心内，采用常规的主从复制议案而在数据中心之间，由各个数据中心的主节点来负责同其他数据中心的主节点进行数据的交换、更新。

    • 缺点

      不同的数据中心可能会同时修改相同的数据，因而必须解决潜在的写冲突。

  • 离线客户端操作

    另一种多主复制比较适合的场景是，应用在与网络断开后还需要继续工作。

  • 协作编辑

• 处理写冲突

  • 同步与异步冲突检测

    理论上，也可以做到同步冲突检测，即等待写请求完成所有副本的同步，然后再通知用户写入成功。但是，这样做将会失去多主节点的主要优势：允许每个主节点独立接受写请求。如果确实想要同步方式冲突检测，或许应该考虑采用单主节点的主从复制模型。

  • 避免冲突

  • 收敛于一致状态

    • 实现收敛的冲突解决有以下可能的方式

      • 给每个写入分配唯一的ID。挑选最高ID的写入作为胜利者，并将其他写入丢弃。虽然这种方法很流行，但是很容易千万数据丢失。
      • 为每个副本分配一个唯一的ID,并制定规则，例如序号高的副本写入始终优先于序号低的副本。这种方法也可能会导致数据丢失。
      • 以某种方式将这些值合并在一起。
      • 利用邓定义好的格式来记录和保留冲突相关的所有信息，然后依靠应用层的逻辑，事后解决冲突。
  • 自定义冲突解决逻辑

• 拓扑结构

  最常见的拓扑结构是全部-全部，即每个主节点将其写入同步到其他所有主节点。还是环形拓扑，星形拓扑，星形拓扑还可以推到树状拓扑。

无主节点复制

客户端直接将其写请求发送到多副本。

• 节点失效时写入数据库

  • 读修复与反熵

    复制模型应确保所有数据最终复制到所有的副本。当一个失效的节点重新上线之后，它如何赶上中间错过的那些写请求：

    • 读修复当客户端并行读取多个副本时，可以检测到过期的返回值。然后客户端判断最新的过期值，写入数据库。
    • 反熵过程一些数据存储有后台进程不断查找副本之间数据的差异，将任何缺少的数据从一个副本复制到另一个副本。
  • 读写quorum

• 监控旧值

  从运维角度来看，监视数据库是否返回最新结果非常重要。即使应用程序可以容忍读取旧值，也需要仔细复制的当前运行状态。如果已经出现了明显的滞后，它就是个重要的信号提醒我们需要采取必要措施来排查原因。对于主从复制的系统，数据库通常会导出复制滞后的相关指标，可以将其集成到统一监控模块。

• 检测并发写

  • 最后写入者获胜（丢弃并发写入）

    需要确认哪个写入是最后的，可以为每个写入添加一个时间戳。

  • Happens-before关系和并发

  • 确定前后关系

    服务器判断操作是否并发的依据主要依靠对比版本号，而并不需要解释新旧值本身（值可以是任何数据结构）。算法的工作流程如下：

    1. 服务器为每个主键维护一个版本号，每当主键新值写入时递增版本号，并将新版本号与写入的值一起保存。
    2. 当客户端读取主键时，服务器将返回所有（未被覆盖的）当前值以及最新的版本号。且要求写之前，客户必须先发送读请求。
    3. 客户端写主键，写请求必须包含之前读到的版本号、读到的值和新值合并后的集合。写请求的响应可以像读操作一样，会返回所有当前值。
    4. 当服务器收到带有特定版本号的写入时 ，覆盖该版本号或更低版本的所有值（因为知道这些值已经被合并到新传的值集合中），但必须保存更高版本号的所有值（因为这些值与当前的写操作属于并发）。

    当写请求包含了前一次读取的版本号时，意味着修改的是基于以前的状态。如果一个写请求没有包含版本号，它将与所有其他写入同时进行，不会覆盖任何已民有值，其传入的值将包含在后续读请求的返回值列表当中。

  • 合并同时写入的值
  • 版本矢量

数据分区

分区通常是这样定义的，即每一条数据（或者每条记录，每行或每个文档）只属于某个特定的分区。采用数据分区的主要目的是提高可扩展性。不同的分区可以放在一个无共享集群的不同节点上。这样一个大数据集可以分散在更锪磁盘上，查询负载也随之分布到时更多的处理器上。

数据分区与数据复制

分区通常与复制结合使用，即每个分区在多个节点都丰有副本。这意味着某条记录属于特定的分区，而同样的内容会保存在不同的节点上以提高系统的容错性。

键值数据的分区

分区的主要目标是将数据和查询负载均匀分布在所有节点上。

• 基于关键字区间分区

  一种分区方式是为每个分区分配一段连续的关键字或者关键字区间范围。基于关键字的区间分区的缺点是某些访问模式会导致热点。

• 基于关键字哈希值分区

  这种方式可以很好地将关键字均匀地分配到多个分区中。然而，通过关键字哈希进行分区，我们丧失了良好的区间查询特性。

• 负载倾斜与热点

分区与二级索引

二级索引是关系数据库的必备特性，在文档数据库中应用也非常普遍。但考虑到其复杂性，许多键-值存储并不支持二级索引； 但其他一些如Riak则开始患难夫妻二级索引的支持。此外，二级索引技术也是Solr和Elasticsearch等 全文索引服务器存在之根本。二级索引带来的主要挑战是它们不能规整的映射到分区中。有两种主要的方法来支持对二级索引进行分区：基于文档的分区和基于词条的分区。

• 基于文档分区的二级索引

  在这种索引方法中，每个分区完全独立，各自维护自己的二级索引，且只负责自己分区内的文档而不关心其他分区中数据。

• 基于词条二级索引分区

  这种方式，我们可以对所有的数据构建全局索引，而不是每个分区维护自己的本地索引。而且，为避免成为瓶颈，不能将全局索引存储在一个节点上，否则就破坏了设计分区均衡的目标。所以，全局索引也必须进行分区，且可以与数据关键字采用不同的分区策略。

分区再平衡

随着时间的失衡，数据库可能总会出现某些变化：

• 查询原动力增加，因此需要更多的CPU来处理负载。
• 数据规模增加，因此需要更多的磁盘和内存来存储数据。
• 节点可能出现故障，因此需要其他机器来接管失效的节点。

这些变化都要求数据和请求可以从一个节点转移到另一个节点。这样一个迁移负载的过程称为再平衡。无论哪种分区方案，分区再平衡通常至少要满足：

• 平衡之后，负载、数据存储、读写请求等应该在集群范围更均匀地分布。
• 再平衡执行过程中，数据库应该可以继续正常提供读写服务。
• 避免不必要的负载迁移，以加快动态再平衡，并尽量减少网络和磁盘IO影响。

• 动态再平衡的策略

  • 为什么不用取模

    对节点取模方法的问题是，如果节点数N发生了变化，会导致很多字需要从现有的节点迁移到另一个节点。

  • 固定数量的分区

    固定分区是创建远超实际节点数的分区数，然后为每个节点分配多个分区。不过每个分区也有些额外的管理开销，所以要根据实际情况选择分区总数。

  • 动态分区

    当分区的数据增长超过一个可配的参数阈值，它京拆分为两个分区，每个承担一半的数据量。相反，如果大量数据被删除，并且分区缩小到某个阈值以下，则将其与相信分区进行合并。该过程类似于B树的分裂操作。

  • 按节点比例分区

    使分区数与集群节点数成正比关系。每个节点具有固定数量的分区。当一个新节点加入集群时，它随机选择固定数量的现有分区进行分裂，然后拿走这些分区的一半数据量，将另一半数据留存原节点。随机选择分区边界的前提要求采用基于哈希分区。

• 自动与手动再平衡操作

  全自动式再平衡会更加方便，它在正常维护之外所增加听操作很少。但是，也有可能出现结果难以预测的情况。再平衡总体讲是个比较昂贵的操作，它需要重新路由请求并将大量数据从一个节点迁移到另一个节点。万一执行过程中间出现异常，会使网络或节点的负载过重，并影响其他请求的性能。出于这样的考虑，让管理员介入到再平衡可能是个更好的选择。

请求路由

将数据集分布到多个节点后，我们需要考虑，当客户端需要发送请求时，如何知道应该连接哪个节点？如果发生了分区再平衡，分区与节点的对应关系随之还会变化。概括来讲，这是一个服务发现问题，这个问题有以下几种不同的处理策略：

1. 允许客户端连接任意的节点。如果节点恰好拥有所请求的分区，则直接处理该请求；否则，将请求转发到下一个合适的节点，接收答复，并将答复返回给客户端。
2. 将所有端的请求都发送到一个路由层，由后者负责将请求转到对应的分区节点上。路由层本身不处理任何请求，它仅充当一个分区感知的负载均衡器。
3. 客户端感知分区和节点分配关系。此时，客户端可以直接连接到目标节点，而不需要任何中介。

不管哪种方法，核心问题是：作出路由决策的组件如何知道分区与节点的对应关系以及其变化情况？

并行查询执行

事务

事务是指将应用的多个读、写操作捆绑在一起成为一个逻辑操作单元。即事务中的所有读写是一个执行的整体，整个事务要么成功，要么失败。如果失败，应用程序可以安全地重试。

深入理解事务

• ACID的含义

  • A Atomicity 原子性
  • C Consistency 一致性
  • I Isolation 隔离性
  • D Durability 隔离性

  • 原子性

    ACID中的原子性并不关税多个操作的并发性，它并没有描述多个线程试图访问相同的数据会发生什么情况，这是ACID的隔离性所定义。 ACID原子性其实描述了客户端发起一个包含多个写操作的请求时可能发生的情况；把多个写操作纳入到一个原子事务，万一出现了上述故障而导致没法完成最终提交时，则事务会中止，并且数据库须丢弃或撤销那些局部完成的更改。因此ACID中原子性所定义的特殊是：在出错时中止事务，并将部分完成的写入全部丢弃。也许可中止性比原子性更为准备，不过我们还是沿用原子性这个惯用术语。

  • 一致性

    一致性在不同场景有着不同的具体含义：

    • 副本一致性以及异步复制模型时，引出了最终一致性问题
    • 一致性哈希则是某些系统用于动态分区再平衡的方法
    • CAP理论中，一致性一词用来表示线性化
    • 而在ACID中，一致性主要指数据库处于应用程序所期待的“预期状态”。

    ACID中的一致性的主要是指对数据有特定的预期状态，任何数据更改必须满足这些状态约束（或者恒等条件）。这种一致性本质上要求应用层来维护状态一致（或者恒等），应用程序有责任正确地定义事务来保持一致性。原子性，隔离性和持久性是数据库自身的属性，而ACID中的一致性更多是应用层的属性。应用程序可能借助数据库提供的原子性和隔离性，以达到一致性，但一致性本身并不源于数据库。

  • 隔离性

    ACID主义中的隔离性意味着并发执行的多个事务相互隔离，它们不能互相交叉。经典的数据库教材把隔离定义为可串行化，这意味着可以假装它是数据库上运行的唯一事务。虽然实际上它们可能同时运行，但数据库系统要确保当事务提交时，其结果与品德执行完全相同。

  • 持久性

    持久性保证一旦事务提交成功，即使存在硬件故障或数据库崩溃，事务所写入的任何数据也不会消失。

• 单对象与多对象事务操作

  • 单对象写入

  • 多对象事务的必要性

    许多分布式数据存储系统不支持多对象事务，主要是因为当出现跨分区时，多对象事务非常难以正确实现，同时在高可用或者极致性能的场景下也会带来很多负面影响。的确有一些情况，只进行单个对象的插入、更新和删除就足够了。但是，还有许多其他情况要求写入多个不同的对象进行协调：

    • 对于关系数据模型，表中的某行可能是另一个表中的外键。类似地，在图数据模型中，顶点具有多个边链接到其他的顶点。多对象事务用以确保这些外键引用的有效性。
    • 对于文档数据模型，如果待更新的字段都在同一个文档中，则可视为单个对象，此时不需要多对象事务。但是，缺少join支持的文档数据库往往会滋生反规范化，当更新这种非规范化数据时，就需要一次更新多个文档。
    • 对于带有二级索引的数据库，每次更改值时都需要同步更新索引。从事务角度来看，这些索引是不同的数据库对象：如果没有事务隔离，就会出现部分索引更新。

  • 处理错误与中止

    事务的一个关键特性是，如果发生的意外，所有操作被中止，之后可以安全地重试。ACID数据库基于这样的一个理念：如果存在违反原子性、隔离性或持久性的风险，则安全放弃整个事务，而不是部分放弃。重试中止的事务虽然是一个简单有效的错误处理机制，但它并不完美：

    • 如果事务实际已经执行成功，但返回给客户端的消息在网络传输时发生意外，那么重试就会导致重复执行，此时需要额外的应用级重复数据删除机制。
    • 如果错误是由于系统超所导致，则重试事务将使情况变得更糟。为此，可以设定一个重试次数上限，例如指数回退，同时要尝试解决系统过载本身的问题。
    • 由临时性故障所导致的错误需要重试。但出现了永久性故障，则重试毫无意义。
    • 如果在数据库之外，事务还产生其他副作用，即事务被中止，这些副作用可能已事实生效。如果想要确保多个不同的系统同时提交或者放弃，可以考虑采用两阶段提交。
    • 如果客户端进程在重试过程中也发生失败，没有其他人继续负责重试，则那些待写入的数据可能会因此而丢失。

弱隔离级别

并发相关的错误很难通过测试发现，这类错误通常只在某些特定时刻才会触发，这种时机相关的问题发生概率低，稳定重现比较困难。实现隔离绝不是想象的那么简单。可串行化的隔离会严重影响性能，而许多数据库去函 愿意牺牲性能，因而更多倾向于采用较弱的隔离级别，它可以防止某些但并非全部的并发问题。

• 读-提交

  读-提交是最基本的事务隔离级别，它只提供以下两个保证：

  1. 读数据库时，只能看到已成功提交的数据（防止“脏读”）。
  2. 写数据时，只会覆盖已成功提交的数据（防止“脏写”）。

  • 防止脏读

    假定某个事务已经完成部分数据写入，但事务尚未提交或中止，此时另一个事务是否要以看到沿未提交的数据呢？如果是的话，那就是脏读。当有以下需求时，需要防止脏读：

    • 如果事务需要更新多个对象，脏读意味着另一个事务可能会看到部分更新，而非全部。
    • 如果事务发生中止，则所有写入操作都需要回滚。

  • 防止脏写

    如果两个事务同时尝试更新相同的对象，不清楚写入顺序，但是可以想象后写的操作会覆盖较早的写入。但是，如果先前的写入是尚未提交事务的一部分，如果还被覆盖的话，就是脏写。读-提交隔离级别下所提交的事务可以防止脏写，通常的方式是推迟第二个写请求，直到前面的事务完成提交或中止。防止脏写可以避免以下并发问题：

    • 如果事务需要更新多个对象，脏写会带来非预期的错误结果。

    但是，读-提交隔离并不能解决计数器增量的竞争情况。

  • 实现读-提交

    数据库通常采用行级锁来防止脏写：娄事务想修改某个对象时，它必须首先获取该对象的鎻；然后一直持有鎻到事务提交或中止。给定时刻，只有一个事务可以拿到特定对象的鎻，如果有另一个事务尝试更新同一个对象，则必须等待，直到前面的事务完成了提交或中止后，才能获得鎻并继续。要防止脏读，一种选择是使用相同的鎻，所有试图读取该对象的事务必须先申请鎻，事务完成后释放鎻。然而，读鎻的方式在实际中并不可行，因为运行时间较长的写事务会导致许多只读的事务等待太长时间，这会严重影响只读事务的响应延迟，县域可操作性差：由于读鎻，应用程序任何局部的性能问题会扩散进而影响整个应用，产生连锁反应。因此，大多数数据库采用，对于每个待更新的对象，数据库都会维护其旧值和当前持鎻事务将要设置的新值两个版本。在事务提交之前，所有其他读操作都读取旧值；仅当写事务提交之后，才会切换到读取新值。

• 快照级别隔离与可重复读

  快照级别隔离可以防止不可重复读取或读倾斜。

  • 实现快照级别隔离

    为了实现快照级别隔离，考虑到多个正在进行的事务可能会在不同的时间点查看数据库状态，所以数据库保留了对象多个不同的提交版本，这种技术因此也被称为多版本并发控制（Multi-Version Concurrency Control MVCC）。

  • 一致性快照的可见性规则

    当事务读数据库时，通过事务ID可以决定哪些对象可见，哪些不可见。要想对上层应用维护好快照的一致性，需要精心定义数据的可见性规则。例如：

    1. 每笔事务开始时，数据库列出所有当时尚在进行中的其他事务，然后忽略这些事务完成的部分写入，即不可见。
    2. 所有中止事务所做的修改全部不可见。
    3. 较晚事务ID所做的任何修改不可见，不管这些事务是否完成了提交。
    4. 除此之外，其他所有的写入都对应用查询可见。换句话说，仅当以下两个条件都成立，则该数据对象对事务可见：
       • 事务开始的时刻，创建该对象的事务已经完成了提交。
       • 对象没有被标记为删除；或者即使标记了，但删除事务在当前事务开始时还没有完成提交。
  • 索引与快照级别隔离
  • 可重复读与命名混淆

• 防止更新丢失

  更新丢失可能发生在这样一个操作场景中：应用程序从数据库读取某些值，根据应用逻辑做出修改，然后写回新值。当有两个事务在同样的数据对象上执行类似操作时，由于隔离性，第二个写操作并不包括第一个事务修改后的值，最终会导致第一个事务的修改值可能会丢失。这种冲突还可能在其他不同的场景下发生，例如：

  • 递增计数器，或更新账户余额。
  • 对某复杂对象的一部分内容执行修改。
  • 两个用户同时编辑wiki页面，且每个用户都尝试将整个页面发送到服务器，覆盖数据库中现有内容以使更改生效。

  • 原子写操作

    许多数据库提供了原子更新操作，以避免在应用层代码完成“读-修改-写回”操作，如果支持的话，通常这就是最好的解决方案。原子操作通常采用对读取对象加独占鎻的方式来实现，这样在更新被提交之前不会其他事务可以读它。这种技术有时被称为游标稳定性。另一种实现方式是强制所有的原子操作都在单线程上执行。

  • 显式加鎻

    如果数据库不支持内置原子操作，另一种防止更新丢失的方法是由应用程序显式锁定待更新的对象。

  • 自动检测更新丢失

    原子操作和tjbj通过强制“读-修改-写回”操作序列串行扫行来防止丢失更新。另一种思路则是先让他们并发执行，但如果事务管理器检测到了更新丢失风险，则会中止当前事务，并强制回退到安全的“读-修改-写回”方式。

  • 原子比较和设置

    在不提供事务支持的数据库中，有时你会发现它们支持原子“比较和设置”操作。即只有在上次读取的数据没有发生变化时才允许下最新，如果已经发生了变化，则回退到“读-修改-写回”方式。

  • 冲突解决与复制

    对于支持多副本的数据库，防止丢失下最新还需要考虑另一个维度：由于多节点上的数据副本，不同的节点可能会并发修改数据，因此必须采取一些额外的措施来防止丢失下最新。

• 写倾斜与幻读

  写倾斜可视为一种更广义的下最新丢失问题。即如果两个事务读取相同的一组对象，然后下最新其中一部分：不同事务可能下最新不同的对象，则可能发生写倾斜；而不同的事务如果下最新的是同一个对象，则可能发生脏写或更新丢失。对于写倾斜，可选的方案有很多限制：

  • 由于涉及多个对象，单对象的原子操作不起作用。
  • 基于快照级别隔离来实现更新丢失自动检测也有问题。
  • 某些数据库支持自定义约束条件，然后由数据库代为检查、执行约束。
  • 如果不能使用可串行化级别隔离，一个次优的选择是对事务依赖的行来的加鎻。

串行化

• 实际串行执行

  解决并发问题最直接的方法是避免并发。

  • 采用存储过程封装事务

    • 存储过程的优缺点

      • 每家数据库厂商都有自己的存储过程语言。
      • 在数据库中运行代码难以管理。
      • 因为数据库实例往往被多个应用服务器所共享，所以数据库通常比应用服务器要求更多的性能。数据库中一个设计不好的存储过程要比同样的应用服务器代码带来更大的麻烦。

      存储过程与内存式数据存储使得单线程上报告所有事务变得可行。

  • 分区

    串行执行所有事务使得前功尽弃控制更加简单，但是数据库的吞量被限制在单机单个CPU核上。为了扩展到多个CPU核和多节点，可以对数据进行分区。如果你能找到一个方法来对数据集进行分区，使得单个事务只在单个分区内读写数据，这样每个分区都可以有自己的事务处理线程且独立运行。

  • 小结

    当满足以下约束条件时，串行执行可以实现串行化隔离：

    • 事务必须简短而高效。
    • 仅限于活动数据集完全可以加载到内存的场景。
    • 写入吞量必须足够低，才能在单个CPU核上处理；否则就需要采用分区，最好没有跨分区事务。
    • 跨分区事务虽然也可以支持，但是占比必须很小。

• 两阶段加鎻

  两阶段加鎻，可以让多个事务同时读取同一对象，但只要出现任何写操作，则必须加鎻以独占访问：

  • 如果事务A已经读取了某个对象，此时事务B想要写入该对象，那么B必须等到A提交或中止之后才能继续。
  • 如果事务A已经修改了对象，此时事务B想要读取该对象，则B必须等到A提交或中止之后才能继续。

  • 实现两阶段加鎻

    • 如果事务要读取对象，必须先以共享模式获得鎻。可以有多个事务同时获得一个对象的共享鎻，但是如果某个事务已经获得了对象的独占鎻，则所有其他事务必须等待。
    • 如果事务要修改对象，必须以独占模式获取鎻。不允许多个事务同时持有该鎻，换言之，如果对象上已被加鎻，则修改事务必须等待。
    • 如果事务首行读取对象，然后尝试写入对象，则需要将共享鎻升级为独占鎻。
    • 事务获得鎻之后，一直持有鎻直到事务结束。

  • 两阶段加鎻的性能

    两阶段加鎻的主要缺点是性能：其事务吞吐量和查询响应时间相比于其他弱隔离级别下降了非常多。部分原因在于qimr获取和释放本身的开销，但更重要的是其降低了事务的并发性。

• 可串行化的快照隔离

  • 悲观与乐观的并发控制

    相比于两阶段加鎻，可串行化的快照隔离则是一种乐观并发控制。在这种情况下，如果可能发生潜在冲突，事务会继续执行而不是中止，寄希望一切相安无事；而当事务提交时，数据库会检查是否确实发生了冲突，如果是的话，中止事务并接下来重试。

  • 基于过期的条件做决定

  • 检测是否读取了过期的MVCC对象

    当事务提交时，数据库检查是否存在一些当初被忽略的写操作现在已经完成了提交，如果是则必须中止当前事务。

  • 检测写是否影响了之前的读

  • 可串行化快照隔离的性能

    与两阶段加鎻相比，可串行化快照隔离的一大优点是事务不需要等待其他事所持有的鎻。这一点和快照隔离一样，读写通常不会互相阻塞。这样的设计使得查询延迟更加稳定、可预测。与串行执行相比，可串行化快照隔离可以突破单个CPU核的限制。需要指出，事务中止比例会显著影响SSI的性能表现。

分布式系统的挑战

故障和部分失效

单台节点上的软件通常不应该出现模棱两可的现象，一个合格的软件状态要么是功能正常，要么是完全失效，而不会介于两者之间。在分布式系统中，可能会出现系统的一部分工作正常，但其他某些部分出现难以预测的故障，我们称之为“部分失效”。问题的难点在于这种部分失效是不确定的。正是因为这种不确定性和部分失效大大提高了分布式系统的复杂性。

• 云计算和超算

  构建大规模计算系统有以下几种不同的思路：

  • 高性能计算（HPC），包含成千上万个CPU的超级计算机构成一个庞大的集群。
  • 另一个极端是云计算。
  • 企业数据中心则位于以上两个极端之间。

不可靠网络

• 发送请求之后等待响应过程中，有很多事情可能会出错

  • 请求可能已经丢失
  • 请求可能正在某个队列中等待，无法马上发送
  • 远程接收节点可能已经失效
  • 远程接收节点可能暂时无法响应
  • 远程接收节点已经完成了请求处理，但回复却在网络中丢失
  • 远程接收节点已经完成了请求处理，但回复却被延迟处理

  处理这些问题通常采用超时机制，在等待一段时间之后，如果仍然没有收到回复则选择放弃，并且认为响应不会到达。

• 现实中的网络故障

  处理网络故障并不意味着总是需要复杂的容错措施：一种简单的方法是对用户提示错误信息。但前提是，必须非常清楚接下来软件会如何应对，以确保系统最终可以恢复。

• 检测故障

  许多系统都需要自动检测节点失效这样的功能。

  • 超时与无限期的延迟

    如果超时是故障检测唯一可串行的方法，那么超时应该设多长呢？不幸的是没有标准答案。

  • 网络拥塞与排队

    计算机网络上的数据包延迟的变化根源往往在于排队：

    • 当多个不同节点册时发送数据包到相同的目标节点时。
    • 当数据包到达目标机器drgk,如果所有CPU核都牌繁忙状态。
    • 在虚拟化环境下，CPU核会切换虚拟栅，从而导致正在运行的操作系统会突然暂停几十毫秒。
    • TCP执行流量控制。

• 同步与异步网络

不可靠时钟

• 单调时钟与墙上时钟

  • 墙上时钟

    根据某个日历返回当前的日期与时间。墙上时钟可以与NTP同步。

  • 单调时钟

    更适合测量持续时间段。

• 时钟同步与准确性

  单调时钟不需要同步，但是墙上时钟需要根据NTP服务器或其他外部时间源做必要的调整。

• 依赖同步的时钟

  • 时间戳与事件顺序
  • 时钟的置信区间
  • 全局快照的同步时钟

• 进程暂停

  • 响应时间保证

    在一些软件系统中，软件有一个必须做出响应的上限：如果无法满足，会情致系统级故障，这就是的硬实时系统。提供实时保证需要来自软件栈的多个层面的支持：首先是一个实时操作系统，保证进程在给定的时间间隔内完成CPU时间片的调度分配；其次，库函数也必须考虑最坏的执行时间；然后，动态内存分配很可能要受限或者完全被禁止；最终还是需要大量、充分的测试和验证，以确保满足要求。

  • 调整垃圾回收的影响

• 知识，真相与谎言

  • 真相由多数决定

    节点不能根据自己的信息来判断自身的状态 。分布式系统不能完全依赖于单个节点。目前，许多分布式算法都依靠法定票数，即在节点之间进行投票。任何决策都需要来自多个节点的最小投票数，从而减少对特定节点的依赖。最常见的法定票数是取系统节点半数以上。

    • 主节点与鎻

      有很多情况，我们需要在系统范围内只能有一个实例，例如：

      • 只允许一个节点作为数据库分区的主节点，以防止出现脑裂。
      • 只允许一个事务或客户端持有特定资源的鎻，以防止同时写入从而导致数据破坏。
      • 只允许一个用户来使用特定的用户名，从而确保用户名可以唯一标识用户。

    • Fencing令牌

      当使用鎻和租约机制来保护资源的并发访问时，必须确保过期的“唯一的那个”节点不能影响其他正常部分。要实现这一目标，可以采用一种相当简单的技术fencing(栅栏，隔离之意)。我们假设每次锁服务在授予鎻或租约时，还会同时返回一个fencing令牌，该令牌每授予一次都会递增。然后，要求客户端每次向存储系统发送写请求时，都必须包含所持有的fencing令牌。

  • 拜占庭故障

    如果某个系统中即使发生部分节点故障，甚至不遵从协议，或者恶意攻击、干扰网络，但仍可继续正常运行，那么我们称之为拜占庭式容错系统。

    • 弱的谎言形式

      尽管我们假设节点通常是诚实的，但依然推荐增加必要的机制来防范一些不那么恶意的“谎言”。例如由于硬件问题千万的无效消息、软件BUG和配置错误。

• 理论系统模型与现实

  关于计时方面，有三种常见的系统模型：

  • 同步
  • 部分同步
  • 异步

  三种常见的节点失效系统模型：

  • 崩溃-中止模型
  • 崩溃-恢复模型
  • 拜占庭失效模型

  • 算法正确性

    为了定义算法的正确性，我们可以描述它的属性令牌。

  • 安全与活性

    安全性通常可以理解为“没有发生意外”，而活性则类似“预期的事情最终一定会发生”。

• 将系统模型映射到现实世界

  证明算法正确工不意味着真实系统上的某个具体实现一定是正确的。

一致性与共识

一致性保证

可线性化

可线性化基本想法是让一个系统看起来好像只有一个数据副本，且所有的操作都是原子的。在一个可线性化的系统中，一旦某个客户端成功提交写请求，所有客户端的读请求一定都能看到刚刚写入的值。

• 如何达到线性化

• 线性化的依赖条件

  • 加鎻与主节点选举

    主从复制的系统需要确保有且只有一个主节点，否则会产生脑裂。选举新的主节点常见的方法是使用鎻：即每个启动的节点都试图获得鎻，其中只有一个可以成功即成为主节点。

  • 约束与唯一性保证

    研发的唯一性约束，常见如关系型数据库中主键的约束，则需要线性化保证。其他如外键或属性约束，则并不需要一定线性化。

  • 跨通道的时间依赖

    线性化违例之所以被注意到，是因为系统中存在其他的通信渠道。

• 实现线性化系统

  系统容错最常见的方法就是采用复制机制。

  1. 主从复制：部分支持可线性化
  2. 共识算法：可线性化
  3. 多主复制（不可线性化）
  4. 无主复制：可能不可线性化

  • 线性化与quorum

    最安全的假定是类似Dynamo风格的无主复制系统无法保证线性化。

• 线性化的代价

  • CAP理论

    • 如果应用要求线性化，但由于网络方面的问题，某些副本与其他副本断开连接后无法继续处理请求，就必须等待网络修复，或者直接返回错误。无论哪种方式，结果是服务不可用。
    • 如果应用不要求线性化，那么断开连接之后，每个副本可独立处理请求例如写操作（多主复制）。此时，服务可用，但结果行为不符合线性化。

  • 可线性化与网络延迟

    虽然线性化是个很有用的保证，但实际上很少有系统真正满足线性化。如果想要满足线性化，那么读、写请求的响应时间至少要与网络中延迟成正比。考虑到多数计算机网络高度不确定的网络延迟，线性化冠以写的性能势必非常差。虽然没有足够快的线性化算法，但弱一致性模型的性能则快得多，这种聚会对于延迟敏感的系统非常重要。

顺序保证

• 顺序与因果关系

  因果关系对所发生的事件施加了某种排序，因果关系的依赖链条定义了系统跌因果顺序，即某件事应该发生另一件事情之前。如果系统服从因果关系所规定的顺序，我们称之为因果一致性。

• 因果顺序并非全序

  全序关系支持任何两个元素之间进行比较，即对于任意两个元素，总是可以指出哪个更大，哪个更小。在一个可线性化的系统中，存在全序操作关系。在可线性化数据存储中不存在并发操作，一定有一个时间线将所有操作都全序执行。可能存在多个请求牌等待处理的状态，但是数据存储保证了在特定的时间点执行特定的操作，所以是单个时间轴，单个数据副本，没有并发。

• 可线性化强于因果一致性

  任何可线性化的系统都将正确地保证因果关系。

• 捕获因果依赖关系

  当事务提交时，数据库要检查事务读取的数据版本现在是否仍是最新的。为些，数据库需要跟踪事务读取了哪些版本的数据。

• 序列号排序

  虽然因果关系很重要，但实际上口口口敁所有的因果关系不切实际。这里还有一个更好的方法：我们可以使用序列号或时间戳来排序事件。

  • 非因果序列发生器

    如果系统不存在这样唯一的主节点，如何产生序列号就不是那么简单了。在实中中可以采用以下方法：

    • 每个节点都独立产生自己的一组序列号。还可以在序列号中保留一些位物于嵌入所属节点的唯一标识符，确保不同的节点户均不会生成相同的序列号。
    • 可以把墙上时间戳信息附加到每个操作上。
    • 可以预告分配序列号的区间范围。

    上述三种思路都可行，相比于把所有请求全部压给唯一的主节点具有更好的扩展性。它们为每个操作生成一个唯一的、挖增加的序列号。不过，它们也都存在一个问题：所产生的序列号与因果关系并不严格一致。所有这些序列号发生器都无法保证正确捕获跨节点操作的顺序，因而存在因果关系方面的问题：

    • 每个节点可能有不同的处理速度。
    • 物理时钟的时间戳会受到时钟偏移的影响，也可能导致与实际因果关系不一致。
    • 对于区间分配器，一个操作可能被赋予1001-2000之之之间的某个序列号，而后发生的操作则路由到另一个节点，拿到了某个1-1000之间的序列号，导致与因果关系不一致。

  • Lamport时间戳

    还有一个简单的方法可以产生与因果关系一致qkgn.它被称为兰伯特时间戳（Lamport timestamp）。 Lamport时间戳与物理墙上时钟并不存在直接对应关系，但它可以保证全序：给定两个Lamport时间戳，计数器较大的那个时间戳大；如果计数器值正好相同，则节点ID越大，时间戳越大。 Lamport时间戳的核心亮点在于使它们与因果性保持一致，具体如下：每个节点以及每个客户端都跟踪迄今为止所见到的最大计数器值，并在每个请求中附带该最大计数器值。当节点收到 某个请求（或者回复）时，如果发现请求内嵌的最大计数器值大于节点自身的计数器值，则它立即把自己的计数器修改为该最大值。只要把最大计数器值嵌入到每一个请求中，该方案可以确保Lamport时间戳与因果关系一致，而请求的因果依赖性一定会保证最后发生的请求得到更大的时间戳。

  • 时间戳排序依然不够

• 全序关系广播

  全序关系广播通常指节点之间交换消息的某个协议。下面是一个非正式的定义，它要求满足两个基本安全属性：

  • 可靠发送没有消息丢失，如果消息发送到某一个节点，则它一定要发送到所有节点。
  • 严格有序消息总是以相同的顺序发送给每个节点。

  • 使用全序关系广播

    全序关系广播另一个要点是顺序在发送消息时已经确定，如果消息发送成功，节点不允许追溯地将某条消息插入到先前的某个位置上。理解全序关系广播的另一种方式是将其视为日志。

  • 采用全序关系广播实现线性化存储

    全序关系广播是基于异步模型：保证消息以固定的顺序可靠地发送，但是不保证消息何时发送成功（因此某个接收者可能明显落后于其他接收者）。而可线性化则强调就近性：读取时保证能够看到最新的写入值。

  • 采用线性化存储实现全序关系广播

    与Lamport时间戳不同，通过递增线性化寄存器获得的数字不会存在任何间隙，如果节点完成了消息4的发送，且接收到了序列化6的消息，那么它对消息6回复之前必须等待消息5.Lamport时间戳则不是这样，而这也是区别全序关系广播与基于时间戳排序的关键。

分布式事务与共识

共识问题是分布式计算中最重要也是最基本的问题之一。非正式地讲，目标只是让几个节点达成一致。节点能达成一致，在许多场景下都非常重要，例如：领导选举，原子提交。

• 原子提交与两阶段提交

  事务原子性的目的是在多次写操作中途出错的情况下，提供一种简单的语义。事务的结果要么是成功提交，在这种情况下，斩所有写入都是持久化的;要么是中止，在这种情况下，事务的所有写入都被回溯。

• 从单节点到分布式原子提交

  在单节点上，事务的提交主要取决于数据持久化落盘的顺序。

• 两阶段提交简介

  两阶段提交是一种用于实现跨多个节点的原子事务提交的算法，即确保所有节点提交或所有节点中止。 2PC使用一个通常不会出现在单节点事务中的新组件：协调者（coordinator）也称为事务管理器（transaction manager）。正常情况下，2PC事务以应用在多个数据库节点上读写数据开始。我们称这些数据库节点为参与者（participants）。当应用准备提交时，协调者开始阶段1：它发送一个准备（prepare）请求到每个节点，询问它们是否能够提交。然后协调者会跟踪参与者的响应：

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

• 系统承诺

  该协议包含两个关键的“不归路”点：当参与者投票“是”时，它承诺它稍后肯定能够提交（尽管协调者可能仍然选择放弃）;以及一旦协调者做出决定，这一决定是不可撤销的。这些承诺保证了2PC的原子性。

• 协调者失败

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

• 三阶段提交

• 实践中的分布式事务

  • 数据库内部的分布式事务所有参与事务的节点都运行相同的数据库软件
  • 异构分布式事务参与者是同两种以上的不同技术组成的。

• 恰好一次的消息处理

• XA事务

  eXtended Architecture 扩展事务，是跨异构技术实现两阶段提交的标准。 XA不是一个网络协议，它只是一个用来与事务协调者连接的C API. XA假定你的应用使用网络驱动或客户端来与参与者进行通信。如果驱动支持XA,则意味着它会调用XA API以查明操作是否为分布式事务的一部分，如果是，则将必要的信息发往数据库服务器。

• 怀疑时持有锁

  为什么我们这么关心存疑事务？问题在于锁。正如在“读已提交”中所讨论的那样，数据库事务通常获取待修改的行上的行级排他锁，以防止脏写。在事务提交或中止之前，数据库不能释放这些锁。因此，在使用两阶段提交时，事务必须在整个存疑期间持有这些锁。如果协调者已经崩溃，需要20分钟才能重启，那么这些锁将会被搬起石头砸自己的脚0分钟。如果协调者的日志由于某种原因彻底丢失，这些锁将被永久持有。当这些锁被持有时，其他事务不能修改这些行。这可能会导致应用大面积进入不可用状态，赶到存疑事务被解决。

• 从协调者故障中恢复

  因为在2PC的正确实现中，即使重启也必须保留存疑事务的锁。但是如果出现协调者无法确定事务的结果，这些事务无法自动解决，所以它们会永远待在数据库中，持有锁并阻塞其他事务。唯一的出路是让管理员手动决定提交还是回滚事务。许可XA的实现都有一个叫做启发式决策的紧急逃生窗口：允许参与者单方面决定放弃或提交一个存疑事务，而无需协调者做出最终决定。

• 分布式事务的限制

  XA事务解决了保持多个参与者相互一致的现实的和重要的问题，但正如我们看到的那样，它也引入了严重的运维问题。事务协调者本身就是一种数据库（存储了事务的结果），因此需要像其他重要数据库一样小心地打交道：

  • 如果协调者没有复制，而是只在单台机器上运行，那么它是整个系统的失效单点。
  • 许多服务器端应用都是使用无状态模式开发的，所有持久状态都存储在数据库中，因此具有应用服务器可随意按需添加删除的优点。但是，当协调者成为应用服务器的一部分时，它会改变部署的性质。
  • 由于XA需要兼容各种数据库系统，因此它必须是所有系统的最小公分母。
  • 对于数据库内部的分布式事务，限制没有这么大。然而仍然存在问题：2PC成功提交一个事务需要所有参与者的响应。因此，如果系统的任何部分损坏，事务也会失败。因此，分布式事务又有扩大失效的趋势。

• 容错共识

  算法可以容忍的失效数量是有限的：事实上可以证明，任何共识算法都需要至少占有总体多数的节点正确工作，以确保终止属性。

• 共识算法和全序广播

  最著名的容错共识算法是视图戳复制（VSR, Viewstamped Replication）, Paxos, Raft以及Zab. 全序广播相当于重复进行多轮共识：

  • 由于一致同意属性，所有节点决定以相同的顺序传递相同的消息。
  • 由于完整性属性，消息不会重复。
  • 由于有效性属性，消息不会被损坏，也不能凭空编造。
  • 由于终止属性，消息不会丢失。

• 单领导者复制与共识

  它将所有的写入操作都交给主库，并以相同的顺序将它们应用到从库，从而使副本保持在最新状态。

• 纪元编号和法定人数

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

• 共识的局限性

• 成员与协调服务

  Zookeeper构建了一组有趣的特性：

  • 线性一致性的原子操作
  • 操作的全序排序
  • 失效检测
  • 变更通知

• 将工作分配给节点

• 服务发现

• 成员资格服务

衍生数据

批处理

三种不同类型的系统：服务（在线系统），批处理系统（离线系统），流处理系统（准实时系统）。

使用Unix工具的批处理

• 简单日志分析

  可以使用Unix提供的各种工具联合分析Nginx的日志中最多访问的请求等等。

• 命令链与自定义程序

  也可以自已写程序去做Unix工具能做的相同的工作。

• 排序VS内存中的聚合

• Unix哲学

  1978年Unix哲学表述如下：

  1. 让每个程序都做好一件事。要做一件新的工作，写一个新程序，而不是通过添加“功能”让老程序复杂化。
  2. 期待每个程序的输出成为另一个程序的输入。不要将无关信息混入输出。避免使用严格的列数据或二进制输入格式。要不坚持交互式输入。
  3. 设计和构建软件时，即使是操作系统，也让它们能够尽早地被试用，最好在几周内完成。不要犹豫，扔掉笨拙的部分，重建它们。
  4. 优先使用工具来减轻编程任务，即使必须曲线救国编写工具，且在用完后很可能要抛掉大部分。

• 统一的接口

  如果希望一个程序的输出成为另一个程序的输入，那意味着这些程序必须使用相同的数据格式。

• 逻辑与布线相分离

  Unix工具的另一个特点是使用标准输入和标准输出。但是你也可以将输入和输出重定向到文件。

• 透明度和实验

  使用Unix工具，它使查看正在发生的事情变得非常容易：

  • Unix命令的输入文件通常被视为不可变的。这意味着你可以随意运行命令，尝试各种命令行选项，而不会损坏输入文件。
  • 你可以将一个流水线阶段的输出写入文件，并将该文件用作下一阶段的输入。这意味着你可以重新启动后面的阶段，而不需要重新运行整个管道。

  然而Unix工具的最大局限在于它们只能在一台机器上运行。

MapReduce和分布式文件系统

MapReduce有点像Unix工具，但分布在数千台机器上。一个MapReduce作业可以和一个Unix进程相类比：它接受一个或多个输入，并产生一个或多个输出。

• MapReduce作业执行

  MapReduce是一个编程框架，你可以使用它编写代码来处理HDFS等分布式文件系统中的大型数据集。理解它的最简单方法是参考“简单日志分析”中的Web服务器日志分析示例。要创建MapReduce作业，你需要实现两个架设函数，Mapper和Reducer,其行为如下：

  • Mapper Mapper会在每条输入记录上调用一次，其工作是从输入记录中提取键值。对于每个输入，它可以生成任意数量的键值对。它不会保留从一个输入记录到下一个记录的任何状态，因此每个记录都是独立处理的。
  • Reducer MapReduce框架拉取由Mapper生成的键值对，收集属于同一个键的所有值，并在这组值上迭代调用Reducer.Reducer可以产生输出记录。

  • 分布式执行MapReduce

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

  • MapReduce工作流

    单个MapReduce作业可以解决的问题范围很有限。因此将MapReduce作业链接成为工作流（workflow）中是极为常见的。Hadoop MapReduce框架对工作流没有特殊支持，所以这个链是通过目录名隐匿实现的：第一个作业必须将其输出配置为HDFS中的指定目录，第二个作业必须将其输入配置为同一个目录。从MapReduce框架的角度来看，这是两个独立的作业。不过目前有很多针对Hadoop的工作流调度器被开发出来，而且Hadoop的各种高级工具也能自动布线组装多个mapReduce阶段，生成合适的工作流。

• Reduce侧连接与分组

  当我们在批处理的语境中讨论连接时，我们指的是在数据集中解析某种关联的全量存在。

  • 排序合并连接
  • 把相关数据放在一起

  • 分组

    除了连接之外，“把树洞和在一起”的另一种常见模式是，按某个键对刻录分组。

  • 处理偏斜

    如果存在与单个键关联的大量数据，则“将具有相同键的所有记录放到相同的位置”这种模式就被破坏了。这种不成比例的活动数据库记录被称为关键对象或热键。在单个Reducer中收集与某个名人相关的所有活动可能导致严重的偏斜。如果连接的输入存在热键，可以使用一些算法进行补偿。

• Map端join操作

  上一节描述的join算法在reducer中执行实际的join逻辑，因此被称为reduce端join.mapper负责准备输入数据：从每个输入记录中提取关键字和什，将键值对分配给reducer分区，并按关键字排序。

  • 广播哈希join

    实现map端join的最简单方法特别适合大数据集与小数据集join，尤其是小数据集能够全部加载到每个mapper的内存中。Map任务依然可以有多个：大数据集的每个文件块对应一个mapper.每个mapper还负责将小数据集全部加载到内存中。这种简单而有效的算法被称为广播哈希join： “广播”一词主要是指大数据集每个分区的mapper还读取整个小数据集，“哈希”意味着使用哈希表。

  • 分区哈希join

    这种方式只适用于两个JOIN的输入具有相同数量的分区，根据相同的关键字和相同的哈希函数将记录分配至分区。

  • Map端合并join

    如果输入灵气集不公以相同的方式进行分区，而且还基于相同的字进行了排序，则可以应用map端join的另一种变化。这时，输入是否足够小以载入内存并不重酬发，因为mapper可以执行通常由reducer执行的合并操作：按关键字升序增量读取两个输入文件，并且匹配具有相同关键字的记录。

  • 具有map端join的MapReduce工作流

    当下流作业使用MapReduce join的输出时，map端或reduce端join的不同造势刽高中生以输出结构。reduce端join的输出按join关键字进行分区和排序，而map端join的输出按照与大数据集相同的方式进行分区和排序。

• 批处理工作流的输出

  批处理过程的输出通常不是报告，而是其他类型的数据结构。

  • 生成搜索索引
  • 批处理输出键值

  • 批处理输出的哲学

    MapReduce作业的输出处理遵循与Unix工具相同的原理。将输入视为不可变，避免副作用，批处理作业不仅实现了良好的性能，而且更容易维护：

    • 如果在代码中引入了漏洞，输出错误或者损坏，那么可以简单地回滚到先前版本，然后重新运行该作业，将再次生成正确的输出。
    • 与发生错误即意味着不可挽回的损害相比，易于回滚的特性更有利于快速开发新功能。这种使不可逆性最小化的原则对于敏捷开发是有益的。
    • 如果map或redice任务失败，MapReduce框架会自动重新安排作业并在同一个输入上再次运行。
    • 相同的文件可用作各种不同作业的输入。
    • 与Unix工具类似，MapReduce作业将逻辑与连线分开，从而可以更好地隔离问题，重用代码。

• 对比Hadoop与分布式数据库

  • 存储多样性

    数据库要求根据特定的模型来构造数据，而分布式文件系统中的文件只是字节序列，可以使用任何数据模型和编码来编写。不加区分地数据转储也转移了数据解释的负担：不是强迫数据集的生产都将其转化为标准化格式，而是将解释数据变为消费都的问题。

  • 处理模型的多样性

    MapReduce使工程师能够轻松地在大型数据食相 运行自己的代码。如果你有HDFS和MapReduce,可以在它上面建立一个SQL查询执行引擎，事实上这就是Hive项目所做的事情。

  • 针对频繁故障的设计

    与在线系统相比，批处理对故障的敏感度较低，因为如果遇到失败的任务，它们不会立即影响用户，而是总是可以重新运行。

超越MapReduce

针对直接使用的困难，在MapReduce上创建了各种高级编程模型（Pig, Hive, Cascading, Crunch）进一步封闭抽象。如果了解MapReduce的工作原理，那么学习这些模型也相当容易，而且它们的高级构造使许多常见的批处理任务更加容易实现。

• 中间状态实体化

  每个MapReduce作业都独立于其他任何作业。作业与其他任务的主要联系点是分布式文件系统上的输入和输出目录。但是，在很多情况下，我们知道一个作业的输出只能用作另一个作业的输入，这个作业由同一个团队维护。在这种情况下，分布式文件系统上的文件只是中间状态。与Unix管道相比，MapReduce完全实体化中间状态的方法有一些不利之处：

  • MapReduce作业只有在前面作业中的所有任务都完成时才能启动，而通过Unix管道连接的进程同时启动，输出一旦生成就会被使用。
  • Mapper通常是冗余的：它们只是读取刚刚由reducer写入的同一个文件，并为下一个分区和排序阶段做准备。
  • 将中间状态存储在分布式文件系统中意味着这些文件被复制到多个节点，对于这样的临时数据来说通常是大材小用了。

• 数据流引擎

  为了解决MapReduce的这些问题，开发了用于分布式批处理的新的执行引擎，其中最著名的是Spark,Tez和Flink.它们的设计方式有很多不同之处，但是有一个共同点：它们把整个工作流作为一个作业来处理，而不是把它分解成独立的子作业。与MapReduce不同，这些功能不需要严格交替map和reduce的角色，而是以更灵活的方式进行组合。我们称为函数运算符，数据流引擎提供了多种不同的选项来连接一个运算符的输出到另一个的输入：

  • 一个选项是通常关键字对记录进行重新分区和排序，就像在MapReduce的shuffle阶段一样。
  • 另一个可能性是读取若干个输入，并以相同的方式进行分区，但忽略排序。
  • 对于广播哈希join，可以将一个运算符的输出发送到join运算符的所有分区。

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

  • 排序等 计算代价昂贵的任务只在实际需要的地方进行。
  • 没有不必要的map任务
  • 由于工作流中的所有join和数据依赖性都是明确声明的，因此调度器知道哪些数据在哪里是必须的，因此它可以进行本地优化。
  • 将运算符之间的中间状态保存在内存中或写入本地磁盘通常就足够了，这比将内容写入HDFS需要更少的IO.
  • 运算符可以在输入准备就绪后立即开始执行，在下一个开始之前不需要等待前一个阶段全部完成。
  • 与MapReduce相比，现有的Java虚拟机进程可以被重用来运行新的运算符，从而减少启动开销。

  • 容错

    将中间状态完全实体化到分布式文件系统的一个优点是持久化，这使得在MapReduce中实现容错变得相当容易。

• 图与迭代处理

  • Pregel处理模型

  • 容错

    容错方式是通过在迭代结束时定期快照所有顶点的状态来实现，即全部状态写入持久存储。

  • 并行执行

    由于编程模型一次仅处理一个顶点，所以框架能够以任意方式划分图。

• 高级API和语言

  由于手工编写MapReduce作业太过耗时费力，因此Hive,Pig,Cascading和Crunch等高级语言和API变得非常流行。除了减少代码的明显优势之外，这些高级接口还允许交互式使用。此外，这些高级接口不仅提高了系统利用率，而且提高了机器级别的作业执行效率。

  • 转向声明式查询语言

    轻松运行任意代码是MapReduce之类的批处理系统与MPP数据库的区别所在. 通常将声明式特征与高级API结合，使查询优化器在执行期间可以利用这些优化方法，仳处理框架看起来就更像MPP数据库了。同时，通过具有运行任意代码和读取任意格式数据的可扩展性，它们依然保持了灵活性的优势。

  • 不同领域的专业化

• 小结

  分布式批处理框架需要解决的两个主要问题是：

  • 分区在MapReduce中，mapper根据输入文件块进行分区。mapper的输出被重新分区，排序，合并成一个可配置数量的reducer分区。这个过程的目的是把所有的相关数据都放在同一个地方。除非必需，后MapReduce的数据流引擎都尽量避免排序，但它们采取了大致类似的分区方法。
  • 容错 MapReduce需要频繁写入磁盘，这使得可以从单个失败任务中轻松恢复，而无需重新启动整个作业，但在无故障情况下则会减慢执行速度。数据引擎执行较少的中间状态实体化并保留更多的内存，这意味着如果节点出现故障，他们需要重新计算更多的数据。确定性运算符减少了需要重新计算的数据量。

流处理系统

发送事件流

在流处理的上下文中，记录通常被称为事件。，它本质上也是一个小的、独立的、不可变的对象，该对象包含某个时间点发生的事情的细节。每个事件通常包含一个时间戳，用于指示事件发生的墙上时间。原则上，通过文件或数据库也可以连接生产者和消费者：生产者将其生成的每个事件写入数据存储，并且每个消费者定期轮询数据存储以检查自上次运行以来出现的事件。

• 消息系统

  向消费者通知新事件的常见方法是使用消息系统：生产者发送包含事件的消息，然后该消息被推送给一个或多个消费者。在这种发布/订阅模式中，不同的系统采取了不同的方法，没有一个标准和答案满足所有的目的。为了区分这些系统，提出以下两个问题对区分有帮助：

  1. 如果生产者发送消息的速度比消费者所能处理的快，会发生什么？有三种选择：丢弃消息，将消息缓存在队列中，激活背压。
  2. 如果节点崩溃或者暂时离线，是否会有消息丢失？

• 生产者与消费者之间的直接消息传递

  直接消息传递通常都要求应用程序代码意识消息丢失的可能性。如果消费者处于离线状态，则可能会遗漏当他们掉线时发送的消息。

• 消息代理

  一种广泛使用的替代方法是通过消息代理（也称为消息队列）发送消息，消息代理实质上是一种针对处理消息流而优化的数据库。

• 消息代理与数据库对比

  一些消息代理甚至可以使用XA或JTA参与两阶段提交协议。这个特性使它们在本质上与数据库非常相似，虽然消息代理和数据库之间仍然存在着重要的实际差异：

  • 数据库通常会保留数据直到被明确要求删除，而大多灵敏消息代理在消息成功传递给消费者就会自动删除。
  • 由于消息代理很快删除了消息，多数消息系统会假定当前工作集相当小，即队列很短。
  • 数据库通常支持二级索引和各种搜索数据的方式，而消息代理通常支持某种方式订阅匹配特定模式的主题。
  • 查询数据库时，结果通常基于数据的时间点快照。消息代理不支持任意的查询，但是当数据发生变化时，它们会通知客户端。

• 多个消费者

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

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

• 确认与重新传递

  确认是指客户端必须显式告知代理消息处理完毕的时间，以便代理能将消息从队列中移除。

分区日志

通过网络发送数据包或向网络服务发送请求通常是短暂的操作，不会留下永久的痕迹。

• 使用日志进行消息存储

  生产者通过将消息追加到日志末尾来发送消息，而消费者通过依次读取日志来接收消息。如果消费者读到日志末尾，则会等等新消息追加的通知。为了伸缩走出单个磁盘所能提供的更高吞吐量，可以对日志进行分区。不同的分区可以托管在不同的机器上，使得每个分区都有一份能独立于其他分区进行读写的日志。一个主题可以定义为一组携带相同类型消息的分区。

• 日志与传统的消息传递相比

  基于日志的方法天然支持扇出式消息传递，因为多个消费者可以独立读取日志，而不会相互影响。然后每个客户端将消费被指派分区的所有消息。

• 消费者偏移量

  顺序消费一个分区使得判断消息是否已经被处理变得相当容易：所有偏移量小于消费者的当前偏移量的消息已经被处理，而具有更大偏移量的消息还没有被看到。

• 磁盘空间使用

  如果只追加写入日志，则磁盘空间终究会耗尽。为了回收磁盘空间，日志实际上被分割成段，并不时地将旧段删除或移到到归档存储。

• 当消费者跟不上生产者时

• 重播旧消息

  除了消费者的任何输出之外，处理的唯一副作用是消费者偏移量的前进。

数据库与流

• 保持系统同步

  在实际使用中，没有一个系统能够满足所有的数据存储、查询和处理需求。大多数重要应用都需要组合使用几种不同的技术来满足所有的需求。每一种技术都有自己的数据副本，并根据自己的目的进行存储方式的优化。由于相同或相关的数据出现在了不同的地方，因此相互间需要保持同步：如果某个项目在数据库中被更新，它也应当在缓存、搜索索引和数据仓库中被更新。如果周期性完整数据库转储过于缓存，有时会使用的替代方法是双写，其中应用代码在数据变更时明确写入每个系统。但是，双写有一些严重的问题，其中一个是竞争条件。双重写入的另一个问题是，其中一个写入可能会失败，另一个成功。

• 变更数据捕获

  大多数数据库的复制日志的问题在于，它们一直被当做数据库的内部实现细节，而不是公开的API。最近人们对变更数据捕获（change data capture,CDC）越来越感兴趣，这是一种观察写入数据库的所有数据变更，并将其提取并转换为可以复制到其他系统跌形式的过程。

  • 变更数据捕获的实现

    我们可以将日志消费者叫做衍生数据系统。变更数据捕获是一种机制，可确保对记录系统所做的所有理性都反映在衍生数据系统中，以便衍生系统具有数据准确副本。从本质上说，变更数据使得一个数据库成为领导者，并将其他组件变为追随者。像消息代理一样，变更数据捕获通常是异步的：记录数据库系统不会等待消费者应用变更再进行提交。

  • 日志压缩

  • 变更流的API支持

    越来越多的数据库开始将变更流作为第一等的接口，而不像传统上要去做加装改造，或者费工夫逆向工程一个CDC.

• 事件溯源

  与变更数据捕获类似，事件溯源涉及到将所有对应用状态的变更存储为变更事件日志。最大的区别是事件溯源将这一想法应用到了一个不同的抽象层次上：

  • 在变更数据捕获中，应用以可变方式使用数据库，可以任意更新和删除记录。变更日志是从数据库的底层提取的，从而确保从数据库中提取的写入顺序与实际写入的顺序相匹配，从而避免竞态条件。写入数据库的应用不需要知道CDC的存在。
  • 在事件溯源中，应用逻辑显式构建在写入事件日志的不可变事件之上。在这种情况下，事件存储是仅追加写入的，更新与删除是不鼓励的或禁止的。事件被设计为旨在反映应用层面发生的事情，而不是底层的状态变更。

  事件溯源是一种强大的数据建模技术：从应用的角度来看，将用户的行为记录为不可变的事件更有意义，而不是在可变数据库中记录这些行为的影响。事件溯源使得应用随时间演化更为容易，通过更容易理解事情发生的原因来帮助调试的进行，并有利于防止应用Bug.

  • 从事件日志中派生出当前状态

    事件日志本身并不是很有用，因为用户通常期望看到是系统当前状态，而不是变更历史。因此，使用事件溯源的应用需要拉取事件日志，并将其转换为适合向用户显示的应用状态。与变更数据捕获一样，重播事件日志允许你重新构建系统的当前状态。不过日志压缩需要采用不同的方式处理：

    • 用于记录更新的CDC事件通常包含记录的完整版本，因此主键的当前值完全由该主键的最近事件确定，而日志压缩可以丢弃相同主键的先前事件。
    • 另一方面，事件溯源在更高层次进行建模：事件通常表示用户操作的意图，而不是因为操作而发生的状态更新机制。在这种情况下，后面的事件通常不会覆盖先前的事件，所以你需要完整的历史事件来重新构建最终状态。这里进行同样的日志压缩是不可能的。

  • 命令和事件

    事件溯源的哲学是仔细区分事件（event）和命令（command）。当来自用户的请求刚到达时，它一开始是一个命令：在这个时间点上它仍然可能失败。应用必须首先难它是否可以执行该命令。如果难成功并且命令被接受，则它变为一个持久化且不可变的事件。当事件生成的时刻，它就成为了事实。事件流的消费者不允许拒绝事件：当消费者看到事件时，它已经成为日志中不可变的一部分，并且可能已经被其他消费者看到了。因此任何对命令的验证，都需要在它成为事件之前同步完成。

• 状态、流和不变性

  可变的状态与不可变事件的仅追加日志相互之间并不矛盾：它们是一体两面。所有变化的日志表示了随时间演变的状态。如果你持久存储了变更日志，那么重现状态就非常简单。如果你认为事件日志是你的记录系统，而所有的衍生状态就从派生而来，那么系统中的流数据流动就容易理解的多。

  • 不可变事件的优点

    使用不可变事件的仅追加日志，诊断问题与故障恢复就要容易的多。不可变的事件也包含了比当前状态更多的信息。

  • 从同一事件日志中派生多个视图

    通过从不变的事件日志中分享出可变的状态，你可以针对不同的读取方式，从相同的事件日志中衍生出几种不同的表现形式。

  • 并发控制

    事件和溯源和变更数据捕获的最大缺点是，事件日志的消费者通常是异步的，所以可能会出现这样中：用户会写入日志，然后从日志衍生视图中读取，结果发现他的写入还没有反映在读取视图中。一种解决方案是将事件追加到日志时同步执行读取视图的更新。

  • 不变性的局限性

流处理

• 流处理的应用

  长期以来，流处理一直用于监控目的。

  • 复合事件处理（complex event processing, CEP）

    CEP允许你指定规则以在流中搜索某些事件模式。 CEP系统通常使用高层次的声明式查询语言，比如SQL或者图形界面，来描述应该检测到的事件模式。

  • 流分析

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

    • 测量某种类型事件的速率
    • 滚动计算一段时间窗口内某个值的平均值
    • 将当前的统计值与先前的时间区间的值对比。

  • 维护物化视图

    原则上，任何流处理组件都可以用于维护物化视图，尽管“永远运行”与一些面向分析的框架假设的“主要在有限时间段窗口上运行”背道而驰。

  • 在流上搜索

    传统的搜索引擎首先索引文件，然后在索引上跑查询。相比之下，搜索一个数据流则反过来：查询被存储下来，文件从查询中流过，就像在CEP中一样。

  • 消息传递与RPC

    RPC类系统与浪处理之间有一些交叉领域。

• 时间推理

  流处理通常需要与时间打交道，尤其是用于分析目的时候，会频繁使用时间窗口。

  • 事件时间与处理时间

    很多原因都可能导致处理延迟，而且消息延迟还可能导致无法预测消息顺序。将事件时间和处理时间搞混会导致错误的数据。

  • 知道什么时候准备好了

    用事件时间来定义窗口的一个棘手的问题是，你永远也无法确定是不是已经收到了特定窗口的所有事件，还是说还有一些事件正在来的路上。

  • 你用的是谁的时钟？

    当事件可能在系统中的多个点缓冲时，为事件分配时间戳就比较困难。根据移动设备的本地时钟，事件的时间戳实际上指的是发生交互时的时间。然而，用户控制的设备上的时钟通常是不可信的，它可能会被意外或故意设置为错误的时间。服务器收到事件的时间更可能是准确的，因为服务器在你的控制之下，但是在描述用户交互方面意义就不大了。

  • 窗口类型

    一旦明确了如何确定事件的时间戳，下一步就是决定如何定义时间段即窗口了。有以下几种常见的窗口类型：

    • 轮转窗口翻滚窗口的长度是固定的，每个事件都属于一个窗口。
    • 跳跃窗口也具有固定长度，但允许窗口重叠以提供一些平滑过渡。
    • 滑动窗口滑动窗口包含在彼此的某个间隔内发生的所有事件。滑动窗口可以通过保留按时间排序的事件缓冲区并且在从窗口过期时移除旧事件来实现。
    • 会话窗口与其他窗口类型不同，会话窗口没有固定的持续时间。相反，它是通过将同一用户在时间上紧密相关的所有事件分级在一起而定义的，一旦用户在一段时间内处于非活动状态，则窗口结束。会话分析是网站分析中常见的一种需求。

• 流式join

  • 流和流join（窗口join）

  • 流和表join

    要执行此join,流处理过程需要一次查看一个活动事件，在数据库中查找事件的用户ID,然后将该概要信息添加到活动事件中。另一种方法是将数据库副本加载到流处理器中，以便在本地进行查询而无需经过网络往返。与批处理任务的区别在于，批处理任务使用数据库的时间点快照作为输入，而流处理是长时间运行的，并且数据库的内容可能随时间而改变，所以流处理数据库的本地副本需要保持最新。

  • 表和表join（物化视图维护）
  • join的时间依赖性

• 流处理的容错

  • 微批处理和校验点

    一种解决方案是将流分解成多个小块，并像小型批处理一样处理每个块。这种方法被称为微批处理，它已经用于Spark Streaming。

  • 重新审视原子提交

    在出现故障时，为了看起来实现恰好处理了一次，我们需要确保当且仅当处理成功时，所有输出和副作用才会生效。这包括发送给下游的操作或外部消息传递系统的任何消息，所有数据库的写入，以及对操作状态的理性和任何对输入消息的确认。这些事情要么原子的发生，要么都不发生，但不应该彼此不同步。

  • 幂等性

    我们的目标是丢弃任何失败任务的部分输出，以便它们可以安全地重试而不会两次生效。分布式事务是实现这一目标的一种方式，而另一种方式则是依赖幂等性。幂等操作是可以多次执行的操作，并且它与只执行一次操作具有相同的效果。

  • 故障后重建状态

    一种选择是将状态保存在远程存储中并采取复制，然后为每个消息去查询远程数据库可能会很慢。另一种方法是将状态在本地保存，并定期进行复制。之后，当流处理器从故障中恢复时，新任务可以读取副本的状态并且在不丢失数据的情况下恢复处理。

数据系统的未来

数据集成

对于任何给定的问题，都有多种解决方案，而这些解决方案都有各自优缺点和折中之处。因此，选择合适的软件组件也需要视情况而定。每一个软件，即使是所谓的“通用”数据库，也都是针对特定的使用模式而设计的。

采用派生数据来组合工具

随着不同类型的数据持续增加，集成问题会变得越来越困难。

• 为何需要数据流

• 派生数据与分布式事务

  为了保持不同的数据系统彼此之间的一致性，经典的方法是通过分布式事务，那么与分布式事务相比，派生数据系统的方法怎么样呢？抽象点说，它们通过不同的方式达到类似的目标。分布式事务通过使用锁机制进行互斥来决定写操作的顺序，而CDC和事件源使用日志进行排序。分布式事务使用原子提交来确保更改只生效一次，而基于日志的系统通常基于确定性重试和幂等性。最大的不同在于事务系统通常提供线性化，这意味着它可以保证读自己的写等一致性。另一方面，派生的数据系统通常是异步更新的，所以默认情况下它们无法提供类似级别的保证。

• 全序的局限

  对于非常小的系统，构建一个完全有序的事件日志是完全可行的。但是，随着系统越来越大，并且面对更为复杂的负载时，瓶颈就开始出现了：

  • 在大多数情况下，构建一个完全有序的日志需要所有事件都通过一个主节点来决定排序。如果事件吞量大于单台节点可处理的上报，则需要将其分区到多台节点上，这就使得两个不同分区中的事件顺序变得不明确了。
  • 如果服务器分布在多个不同地理位置的数据中心，为了避免整个数据中心不可用，且考虑到网络延迟使跨数据中心协调的同步效率很低，因此通常在每个数据中心都有独立的主节点。这意味着来自两个不同数据中心的事件顺序不确定。
  • 将应用程序部署为微服务时，常见的设计是将每个服务与其持久化的状态一起作为独立单元部署，而服务之间不共享持久化状态。当两个事件来自不同的服务时，这些事件没有清楚的顺序。
  • 某些应用程序在客户端维护一些状态，当用户输入时会立即更新，甚至可以继续离线工作。对于这样的应用程序，客户端和服务器很可能看到不同的事件顺序。

  从形式上讲，决定事件的全序关系称为全序关系广播，它等价于共识。大多数共识算法是针对单节点吞量足以处理整个事件流而设计的，并且这些算法不提供支持多节点共享事件排序的机制。设计单节点吞量甚至在广域地理环境分布的共识算法仍然是一个有待研究的开放性问题。

• 排序事件以捕获因果关系

  如果事件之间不存在因果关系，则不支持全序排序并不是一个大问题，因为并发事件可以任意排序。

批处理和流处理集成

数据融合的目标是确保数据在所有正确的地方以正确的形式结束。这样做涉及消费输入数据，转换，join，过滤，聚合，训练模型，评估并最终写入适当的输出。而批处理和流处理则是实现这一目标的有效工具。批处理的流处理有许多共同的原则，而根本区别在于流处理器运行在数据集上，而批处理的输入是已知的有限大小。

• 保持派生状态

  批处理具有相当强的功能我，包括倡导确定性、纯函数操作即输出仅依赖于输入，除了显式输出以外没有任何副作用，输入不可变，追加式输出结果等。流处理是类似的，但它扩展了操作来支持可管理的、容错的状态。

• 为应用程序演化而重新处理数据

  在需要维护派生数据时，批处理和流处理都会用得上。流处理可以将输入的变化数据迅速反映在派生视图中，而批处理则可以反复处理大量的累积数据，以便将新视图导出到现有数据集上。特别是对现有数据进行重新处理，为维护系统提供一个良好的机制，平滑支持新功能以及多变的需求。派生视图允许逐步演变。如果想重新构建数据集，无需采用高风险的陡然切换。而是可以在同一个基础数据上的两个独立派生视图来同时维护新老两种架构。然后逐步开始将少量用户迁移到新视图中，以测试其性能并发现是否有错误，而大多数用户将继续路由到旧视图。之后，逐渐增加访问新视图的用户比例，最终放弃旧视图。

• Lambda架构

  Lambda体系结构的核心思想是进来的数据以不可变事件形式追加到不断增长的数据集，类似于事件源。基于这些总事件，可以派生出读优化的视图。Lambda结构建议并行运行两个不同的系统：一个批处理系统如Hadoop MapReduce，以及一个单独的流处理系统，如Storm。

• 统一批处理和流处理

  在一个系统中统一批处理和流处理需要以下功能：

  • 支持以相同的处理引擎来处理最新事件和处理历史回放事件。
  • 支持只处理一次主义。
  • 支持依据事件发生时间而不是处理时间进行窗口化。

分拆数据库

Unix和关系型数据库采用了大不一样的哲学思想看待信息管理问题。Unix认为它的目的是为程序员提供一个逻辑的，但是相当低层次的硬件抽象，而关系型数据库则希望为应用程序员提供一个高层次的抽象，来隐藏磁盘上数据结构的复杂性、并发性、崩溃恢复等。Unix开发的管道和文件只是字节序列，而数据库开发了SQL和事务。

编排多种数据存储技术

数据库提供的种种功能及其工作原理：

• 二级索引： 根据字段值高效地搜索所有记录。
• 实体化视图： 预先计算查询结果并将其缓存。
• 复制日志： 使多节点上数据副本保持最新。
• 全文搜索索引： 在广西中进行关键字搜索并且内置于某些关系型数据库。

• 创建一个索引

• 元数据库

  • 可能的发展：

    • 联合数据库：统一读端
    • 分离式数据库：统一写端

• 分离式如何工作

  联合方式与分离方式可以看出同一个硬币的两面：用不同的组件构成一个可靠、可扩展的和可维护的系统。在单个存储系统内或流处理系统内的事务是可行的，但是当数据跨越不同技术的边界时，我认为具有幂等写入的异步事件日志是一种更加健壮和可行的方法。基于日志的集成的一大优势是各个组件之间的松耦合，这体现在两个方法：

  1. 在系统级别，异常事件流使整个系统在应对各个组件的中断或性能下降时表现更加稳健。
  2. 在人员角度看，分离式数据系统使得不同的团队可以独立的开发、改进和维护不同的软件组件和服务。专业化使得每个团队都可以专注于做好一件事情，且与其他系统维护清晰明确的接口。

• 分离式与集成式系统

  分离的目标不是要与那些针对特定负载的单个数据库来竞争性能。目标是让你可以将多个不同的数据库组合起来，以便在更广泛的工作负载范围内实现比单一软件更好的性能。

• 遗漏了什么？

  组合数据系统的工具正在变得越来越好，但是我认为还缺少一个主要部分：我们还没有与UNIX shell相媲美的分离型数据库。

围绕数据流设计应用系统

期望使用某种特定的语言、框架或工具来开发所有软件是不切实际的。

• 应用程序代码作为派生函数

  当某个数据集从另一个数据集派生而来时，它一定会经历某种转换函数。例如：

  • 二级索引是一种派生的数据集
  • 通过各种自然语言处理函数创建全文搜索索引，然后构建用于高效查找的数据结构。
  • 在机器学习系统中，可以考虑通过应用各种特等提取和统计分析功能从训练数据中导出模型。
  • 缓存通常包含那些即将显式在用户界面的聚合数据。

• 应用程序代码与状态分离

  理论上讲，数据库可以像操作系统那样成为任意应用程序代码的部署环境。但是我们认为系统的某部分专注于持久性数据存储，同时有另外一部分专门负责运行应用程序代码是有道理的。这两部分有交互，但是各自仍保持独立运行。但是在大多数编程语言中，无法订阅可变变量的更改信息，而只能定期不断地读取它。数据库继承了这种被动方法来处理可变数据：如果想知道数据库的内容是否发生了变化，唯一的选择就是轮询。订阅理性只是最近才出现的新功能。

• 数据流：状态变化和应用程序代码之间的相互影响

• 流式处理与服务

  当前流行的应用程序开发风格是将功能分解为一组通过同步同络请求进行通信的服务。这种面向服务的结构优于单体应用程序之处在于松耦合所带来的组织伸缩性：不同的团队可以在不同的服务上工作，这减少了团队之间的协调工作。

观察派生状态

• 实体化视图和缓存

  缓存、索引和实体化视图主要是调整读、写路径之间的边界。通过预先计算结果，写路径上承担了更多的工作，而读路径则可以简化加速。

• 有状态，可离线客户端

• 状态更改推送到客户端

• 端到端的事件流

• 读也是事件

• 多分区数据处理

端到端的正确性

• 数据库的端到端争论

  • Exactly-once执行操作

    如果在处理消息过程中出现意外，可以造势放弃或者再次尝试。exactly-once意味着合理安排计算，使得执行多次的最终效果与没有发生错误的结果一样，即使操作实际上由于某种故障而被重试。最有效的方法之一是使operator满足幂等性。

  • 消除重复

  • 操作标识符

    为了实现跨多次网络跳转请求而操作仍然具有幂等性，仅仅依靠数据库提供的事务机制是不够的，需要考虑请求的端到端过程。

  • 端到端的争论

    底层的可靠性功能本身不足以确保端到端的正确性。

  • 在数据系统中采用端到端的思路

• 强制约束

  • 唯一性约束需要达成共识

    如果有多个具有相同值的并发请求，系统需要决定接受哪一个操作，并由于违法约束因此拒绝其他的冲突操作。

  • 基于日志的消息传递唯一性

    任何可能冲突的写入都被路由到特定的分区并按顺序处理。

  • 多分区请求处理

• 时效性与完整性

  一致性这个术语将两个值得分开考虑的不同的需求：时效性和完整性合二为一了：

  • 时效性时效性意味着确保用户观察到系统的最新状态。
  • 完整性完整性意味着避免数据损坏，即没有数据丢失，也没有互相矛盾或错误的数据。

  简而言之，违反时效性导致“最终一致性”，而违反完整性则是“永久性不一致”。

  • 数据流系统的正确性

  • 宽松的约束

    如果可以有补偿事务，并且代价不高，可以考虑将约束放宽松。

  • 无需协调的数据系统

    根据自己的需求，选择一个合适点使得既不能有太多不一致，也不能出现太多可用性问题。

• 信任，但要确认

  • 软件缺陷时的完整性

    如果应用程序以一种错误地方式使用数据库，就不能保证数据库的完整性。

  • 不要盲目信任承诺

    硬件和软件并不能总是处于理想状态，数据损坏迟似乎只是尽早的事情而无法避免。因此，我们至少需要有办法来查明数据是否已经损坏，以便之后修复这些数据，并试图找出错误的根源。检查数据的完整性也被称为审计。

  • 验证的文化

    我们应该花些时间来思考一下关于可审计性的设计。

  • 可审计性的设计

  • 端到端论点的再讨论

    如果我们不能完全相信系统中的每个组件都能免于损坏，那么我们至少也要定期检查数据的完整性。检查数据系统的完整性最好以端到端的方式进行：在完整性检查中所包含的系统部件真金，则过程中某些阶段发生无千警的数据破坏的概率就越少。

  • 审计数据系统的工具

做正确的事情

• 预测性分析

  • 偏见与歧视

    算法所做出的决定不一定比人类做得更好或更糟。

  • 责任与问责

    自动决策引发了责任与问责方面的问题。

  • 反馈环路

• 数据隐私与追踪

  • 监控
  • 赞成与选择的自由
  • 数据隐私和使用
  • 数据作为资产和权力
  • 记住工业革命
  • 立法与自律