DDIA 笔记

2020-08-09 10:03:53 浏览数 (1)

本文为 design data-intensive applications 的读书笔记

第一部分：数据系统的基石

第一章：可靠性、可扩展性、可维护性

  • 现今很多应用程序都是 数据密集型（data-intensive） 的，而非 计算密集型（compute- intensive）的。因此CPU很少成为这类应用的瓶颈，更大的问题通常来自数据量、数据复杂 性、以及数据的变更速度。
  • 许多应 用程序都需要：
    • 存储数据，以便自己或其他应用程序之后能再次找到 （数据库（database））
    • 记住开销昂贵操作的结果，加快读取速度（缓存（cache））
    • 允许用户按关键字搜索数据，或以各种方式对数据进行过滤（搜索索引（search indexes））
    • 向其他进程发送消息，进行异步处理（流处理（stream processing））
    • 定期处理累积的大批量数据（批处理（batch processing））
  • 推特的例子，两种实现方式的组合
    • 读时间线时直接查询
    • 写时主动推送关注者的推文收件箱
  • 描述性能：
    • 如果想知道典型场景下用户需要等待多长时间，那么中位数是一个好的度量标准
    • 为了弄清异常值有多糟糕，可以看看更高的百分位点，例如第95、99和99.9百分位点
    • 例如亚马逊在描述内部服务的响应时间要求时以99.9百分位点为准，即使它只影响一千个请求中的一个。这是因为请求响应最慢的客户往往也是数据最多的客户，也 可以说是最有价值的客户。
  • 简单性：管理复杂度
    • 用于消除额外复杂度的最好工具之一是抽象（abstraction）。一个好的抽象可以将大量实现 细节隐藏在一个干净，简单易懂的外观下面。一个好的抽象也可以广泛用于各类不同应用。比起重复造很多轮子，重用抽象不仅更有效率，而且有助于开发高质量的软件。抽象组件的 质量改进将使所有使用它的应用受益。
    • 例如，高级编程语言是一种抽象，隐藏了机器码、CPU寄存器和系统调用。 SQL也是一种抽 象，隐藏了复杂的磁盘/内存数据结构、来自其他客户端的并发请求、崩溃后的不一致性。当然在用高级语言编程时，我们仍然用到了机器码；只不过没有直接（directly）使用罢了，正是因为编程语言的抽象，我们才不必去考虑这些实现细节。

第二章：数据模型与查询语言

  • 关系模型与文档模型
    • 关系模型：数据被组织成关系（SQL中称作表），其中每个关系是元组（SQL中称作行)的无序集合
    • 对象关系不匹配：如果数据存储在关系表中，那么需要一个笨拙的转换层，处于应用程序代码中的对象和表，行，列的数据库模型之间。模型之间的不连贯有时被称为阻抗不匹配（impedance mismatch）
      • 像ActiveRecord和Hibernate这样的 对象关系映射（ORM object-relational mapping） 框架可以减少这个转换层所需的样板代码的数量，但是它们不能完全隐藏这两个模型之间的差 异。
      • 对于一个像简历这样自包含文档的数据结构而言，JSON表示是非常合适的，JSON模型减少了应用程序代码和存储层之间的阻抗不匹配，有更好的局部性（locality）
    • 关于关系模型的文献区分了几种不同的规范形式，但这些区别几乎没有实际意义。一 个经验法则是，如果重复存储了可以存储在一个地方的值，则模式就不是规范化 （normalized）的
    • 文档数据库一对一关系可以嵌套记录，但是由于对连接的支持弱，很难应对多对多的关系。
    • 文档数据库有时称为无模式（schemaless），但这具有误导性，因为读取数据的代码通常假 定某种结构——即存在隐式模式，但不由数据库强制执行。一个更精确的术语是读时 模式（schema-on-read）（数据的结构是隐含的，只有在数据被读取时才被解释），相应的是写时模式（schema-on-write）（传统的关系数据库方法中，模式明确，且数据库确保所 有的数据都符合其模式）
    • 多对多关系是不同数据模型之间具有区别性的重要特征。如果你的应用程 序大多数的关系是一对多关系（树状结构化数据），或者大多数记录之间不存在关系，那么 使用文档模型是合适的
    • 关系模型和文档模型的混合是未来数据库一条很好的路线
  • 数据查询语言：声明式查询的好处
    • 声明式查询语言是迷人的，因为它通常比命令式API更加简洁和容易。
    • 隐藏了数据库引擎的实现细节，这使得数据库系统可以在无需对查询做任何更改的情况下进行性能提升。
    • 声明式语言往往适合并行执行。
  • 图数据模型
    • Cypher查询语言
    • 三元组存储和SPARQL

第三章：存储与检索

  • 两大类存储引擎：日志结构（log-structured）的存储引擎，以及面向页面（page-oriented） 的存储引擎（例如B 树）。
  • 如果我们只是追加写入一个文件 —— 所以如何避免最终用完磁盘空间？一种好的解决 方案是，将日志分为特定大小的段，当日志增长到特定尺寸时关闭当前段文件，并开始写入 一个新的段文件。然后，我们就可以对这些段进行压缩（compaction）
  • 要求键值对的序列按键排序(每个键只在每个合并的段文件中出现一次) => 排序字符串表（Sorted String Table），简称SSTable。
  • 构建和维护SSTables（LevelDB 和RocksDB 就是这么做的）:
    • 写入时，将其添加到内存中的平衡树数据结构（例如，红黑树）。这个内存树有时被称 为内存表（memtable）。
    • 当内存表大于某个阈值（通常为几兆字节）时，将其作为SSTable文件写入磁盘。这可以 高效地完成，因为树已经维护了按键排序的键值对。新的SSTable文件成为数据库的最新 部分。
    • 当SSTable被写入磁盘时，写入可以继续到一个新的内存表实例。 为了提供读取请求，首先尝试在内存表中找到关键字，然后在最近的磁盘段中，然后在 下一个较旧的段中找到该关键字。
    • 有时会在后台运行合并和压缩过程以组合段文件并丢弃覆盖或删除的值。
    • 我们可以在磁盘上保存一个单独的日志，每 个写入都会立即被附加到磁盘上, 用于崩溃后恢复内存表
    • 基于这种合并和压缩排序文件原 理的存储引擎通常被称为LSM存储引擎
  • B树
    • B树的基本底层写操作是用新数据覆盖磁盘上的页面：这与日志结构索引（如LSM树）形成鲜明对 比，后者只附加到文件（并最终删除过时的文件），但从不修改文件
    • 如果多个线程要同时访问B树。通常通过使用锁存器（latches）（轻量级 锁）保护树的数据结构来完成。日志结构化的方法在这方面更简单，因为它们在后台进行所 有的合并，而不会干扰传入的查询。
  • 比较
    • ，LSM树通常能够比B树支持更高的写入吞吐量，部分原因是它们有时具有较低的写放大
    • LSM树可以被压缩得更好，因此经常比B树在磁盘上产生更小的文件。 B树存储引擎会由于分割而留下一些未使用的磁盘空间：当页面被拆分或某行不能放入现有页面时，页面中的某些 空间仍未被使用。由于LSM树不是面向页面的，并且定期重写SSTables以去除碎片，所以它 们具有较低的存储开销，特别是当使用平坦压缩时
    • 但是压缩过程有时会干扰正在进行的读写操作，而且磁盘的有限写入带宽需要在初始写入和在后台运行的压缩线程之间共享。
    • B树的一个优点是每个键只存在于索引中的一个位置，而日志结构化的存储引擎可能在不同的 段中有相同键的多个副本。这个方面使得B树在想要提供强大的事务语义的数据库中很有吸引力：在许多关系数据库中，事务隔离是通过在键范围上使用锁来实现的，在B树索引中，这些 锁可以直接连接到树
  • 内存数据库
    • 内存数据库的性能优势并不是因为它们不需要从磁盘读取的事实。即使是基于 磁盘的存储引擎也可能永远不需要从磁盘读取，因为操作系统缓存最近在内存中使用了磁盘块。相反，它们更快的原因在于省去了将内存数据结构编码为磁盘数据结构的开销。
  • OLTP： 应用程序通常使用索引通过某个键查找少量记录。根据用户的输入插入或更新记录。由于这些应用程序是交互式的，因此访问模式被称为 在线 事务处理（OLTP, OnLine Transaction Processing）
  • OLAP: 分析查询需要扫描大量记录，每个记录只读取几列，并计算汇总统计信息
  • 数据仓库: 包含公司各种OLTP系统中所有的只读数据副本。从OLTP数据库中提 取数据（使用定期的数据转储或连续的更新流），转换成适合分析的模式，清理并加载到数 据仓库中。将数据存入仓库的过程称为“抽取-转换-加载（ETL）
  • 列存储: 不要将所有来自一行的值存储在一起，而是将来自每一列 的所有值存储在一起。
    • 面向列的存储通常很适合压缩。
    • 数据仓库的另一个值得一提的是物化汇总，物化视图是查询结果的实际副本，写入磁盘，而虚拟视图只是写入查询的捷径。

属性

事务处理 OLTP

分析系统 OLAP

主要读取模式

查询少量记录，按键读取

在大批量记录上聚合

主要写入模式

随机访问，写入要求低延时

批量导入（ETL），事件流

主要用户

终端用户，通过Web应用

内部数据分析师，决策支持

处理的数据

数据的最新状态（当前时间点）

随时间推移的历史事件

数据集尺寸

GB ~ TB

TB ~ PB

第四章：编码与演化

  • 编码数据的格式：程序通常（至少）使用两种形式的数据
    • 在内存中，数据保存在对象，结构体，列表，数组，哈希表，树等中。这些数据结构针 对CPU的高效访问和操作进行了优化（通常使用指针）
    • 如果要将数据写入文件，或通过网络发送，则必须将其 编码（encode）为某种自包含 的字节序列（例如，JSON文档）
  • JSON，XML和CSV是文本格式 存在一些问题
    • 数字的编码多有歧义之处，例如JSON虽然区分字符串和数字，但不区分整数和浮点数，而且不能指定精度。
    • 不支持二进制，Json 需要base64处理
  • 二进制编码格式，如 Thrift和 Protocol Buffers

第二部分：分布式数据

  • 共享内存（垂直扩展（vertical scaling）或向上扩展（scale up）））方法的问题在于，成本增长速度快于线性增长：一台有着双倍处理器数量，双倍内 存大小，双倍磁盘容量的机器，通常成本会远远超过原来的两倍
    • 在大型机中，尽管任意处理器都可以访问内存的任意部分，但总有一些内存区域与一些 处理器更接近（称为非均匀内存访问（nonuniform memory access, NUMA）
  • 另一种方法是共享磁盘架构（shared-disk architecture），它使用多台具有独立处理器和内 存的机器，但将数据存储在机器之间共享的磁盘阵列上，这些磁盘通过快速网络连接。这种架构用于某些数据仓库，但竞争和锁定的开销限制了共享磁盘方法的可扩展性。
  • 相比之下，无共享架构（shared-nothing architecture）（有时称为水平扩展（horizontal scale） 或向外扩展（scale out））已经相当普及。
  • 数据分布在多个节点上有两种常见的方式：
    • 复制（Replication）：在几个不同的节点上保存数据的相同副本，可能放在不同的位置
    • 分区 (Partitioning)：将一个大型数据库拆分成较小的子集（称为分区（partitions）），从而不同的分区可以指派给不同的节点（node）（亦称分片（shard））
    • 复制和分区是不同的机制，但它们经常同时使用

第五章：复制

  • 三种流行的变更复制算法：
    • 单领导者（single leader）
    • 多领导者（multi leader）
    • 无领导者（leaderless）
  • 复制系统的一个重要细节是：复制是同步（synchronously）发生还是异步 （asynchronously）发生。通常情况下，基于领导者的复制都配置为完全异步。（这里的复制只考虑简单复制，而不考虑共识（consensus））
  • 复制日志的实现
    • 基于语句的复制，实际使用很少。非确定函数（如 Now()）,自增列,副作用语句的影响很难控制
    • 传输预写式日志(WAL): 主要缺点是日志记录的数据非常底层： WAL包含哪些磁盘块中的哪些字节发生了更改, PostgreSQL和Oracle等使用这种复制方法
    • 逻辑日志复制: MySQL的二进制日志（当配置为使用基于行的复制时）使用这种方法
    • 基于触发器的复制: 触发器允许您注册在数据库系统中发生数据更改（写入事务）时自动执行的自定义应用程序 代码
  • 复制延迟问题 (保证最终一致性（eventually consistency）)
    • 读己之写：写之后立刻读数据可能看不到数据，这种情况下，我们需要读写一致性（read-after-write consistency），也称为读己之写一致性（read-your-writes consistency）。解决的策略：
      • 从主库读取用户自 己的档案，在从库读取其他用户的档案 （因为用户的数据一般只能自己编辑）
      • 跟踪上次更新的时间，在上次更新后的一分钟内，从主库读。
      • 客户端可以记住最近一次写入的时间戳，系统需要确保从库为该用户提供任何查询时， 该时间戳前的变更都已经传播到了本从库中。如果当前从库不够新，则可以从另一个从 库读，或者等待从库追赶上来
    • 单调读：单调读（Monotonic reads）是一个比强一致性 （strong consistency）更弱，但比最终一致性（eventually consistency）更强的保证。 当读取数据时，您可能会看到一个旧值；单调读取仅意味着如果一个用户顺序地进行多次读 取，则他们不会看到时间后退，即，如果先前读取到较新的数据，后续读取不会得到更旧的数据。
      • 实现单调读取的一种方式是确保每个用户总是从同一个副本进行读取（不同的用户可以从不同的副本读取）。例如，可以基于用户ID的散列来选择副本，而不是随机选择副本。但是，如果该副本失败，用户的查询将需要重新路由到另一个副本。
    • 一致前缀读：这个保证说：如果一系列写入按某个顺序发生，那么任何人读取这些写入时，也会看见它们以同样的顺序出现。这是分区（partitioned）（分片（sharded））数据库中的一个特殊问题
  • 多主复制，常用于多个数据中心，离线操作，协同编辑的场景
    • 尽管多主复制有这些优势，但也有一个很大的缺点：两个不同的数据中心可能会同时修改相 同的数据，写冲突是必须解决的。
    • 避免冲突的方式包括：确保来自特定用户的请求始终路由到 同一数据中心，并使用该数据中心的领导者进行读写。不同的用户可能有不同的“家庭”数据中 心（可能根据用户的地理位置选择），但从任何用户的角度来看，配置基本上都是单一的领导者。
    • 需要以一种收敛（convergent）的方式解决冲突，比如用 ID 大小，时间戳用于合并：最后写入胜利（LWW, last write wins），或者都保留，提示冲突
  • 无主复制：一些数据存储系统采用不同的方法，放弃主库的概念，并允许任何副本直接接受来自客户端 的写入。在亚马逊将其用于其内部的Dynamo系统之后，它再 一次成为数据库的一种时尚架构。Riak，Cassandra和Voldemort是由Dynamo启发的 无领导复制模型的开源数据存储，所以这类数据库也被称为Dynamo风格。
    • 读写的时候都发送请求到多个副本
    • 读修复（Read repair）：当客户端并行读取多个节点时，它可以检测到任何陈旧的响应，将正确的新值写回错误副本.
    • 反熵过程（Anti-entropy process）：后台进程不断查找副本之间的数据差异，并将任何缺少的数据从一个副本复制到另一个副本。
    • 存在很多边缘情况，即使读写法定人数满足时也会发生，如
      • 两个写入同时发生
      • 读写同时发生，不清楚哪个先发生..
    • 尤其是，通常没有得到“与延迟有关的问题”（读取您的写入，单调读取或一致的前缀读取） 中讨论的保证，因此前面提到的异常可能会发生在应用程序中。更强有力的保证通常需要事务或共识。
    • LWW实现了最终收敛的目标，但以持久性为代价：如果同一个Key有多个并发写入，即使它 们都被报告为客户端成功（因为它们被写入 w 个副本），但只有一个写入将存活，而其他写 入将被静默丢弃

第六章：分区

  • 对于非常大的数据集,或非常高的吞吐量，仅仅进行复制是不够的：我们需要将数据进行分区（partitions），也称为分片 （sharding）
    • 分区(partition),在MongoDB,Elasticsearch和Solr Cloud中被称为分片(shard), 在HBase中称之为区域(Region)，Bigtable中则是表块（tablet），Cassandra和Riak中 是虚节点（vnode), Couchbase中叫做虚桶(vBucket).但是分区(partition) 是约定俗成的 叫法。
  • 一种常用的分区方式是根据键的散列分区，但是并不能消除负载倾斜（热点），比如某个主题是热点。如今，大多数数据系统无法自动补偿这种高度偏斜的负载，因此应用程序有责任减少偏斜，例如，如果一个主键是非常火爆的，一个简单的方法是在主键的开始或结尾添加一个随机数，读的时候则需要合并。
  • 二级索引：
    • 本地索引（各个分片维护自己的索引，需要分散/聚集（scatter/gather））
    • 全局索引（但是索引本身也可以分片，用户加速读取效率，读取更有效率，但是写入速度较慢且复杂，因为写入单个文档可能影响多个分区-Key 可 能位于不同的分区或者不同的节点上）
  • 分区再平衡（reblancing）
    • 创建比节点更多的分区，并为每个节点分配多个分区。例如，运行在10个节点的集群上的数据库可能会从一开始就被拆分为1,000个分区，因此大约有100个分区被分配给每个节点，这样 relbancing 的时候，只有分区在节点之间的移动。分区的数量不会改变，键所指定的分区也不会改变。唯一改变 的是分区所在的节点。
    • 现代数据库允许不通策略的动态分区
  • 分区通常和服务发现(service discovery)紧密相关，即客户端应该怎么知道访问哪个分区:
    1. 允许客户联系任何节点: 如果该节点恰巧拥有请求的分区，则它可以直接处理该请求;否则，它将请求转发到适当的节点，接收回复并传递给客户端。
    2. 首先将所有来自客户端的请求发送到路由层，它决定了应该处理请求的节点，并相应地转发
    3. 要求客户端知道分区和节点的分配。在这种情况下，客户端可以直接连接到适当的节点，而不需要任何中介。
imageimage

第七章：事务

  • 事务所提供的安全保证，通常由众所周知的首字母缩略词ACID来描述，ACID代表原子性 （Atomicity），一致性（Consistency），隔离性（Isolation）和持久性（Durability）
    • 原子性（Atomicity）的定义特征是：能够在错误时中止事务，丢弃该事务进行的所有写入变更的能力。 系统只能处于操作之前或操作之后的状态，而不是介于两者之间的状态。【或许可中止性（abortability） 是更好的术语。】
    • 一致性（Consistency）的概念是，对数据的一组特定陈述必须始终成立：原子性，隔离性和持久性是数据库的属性，而一致性（在ACID意义上）是应用程序的属性。应用可能依赖数据库的原子性和隔离属性来实现一致性，但这并不仅取决于数据库。因此，字母C不属于ACID。另外一致性这个词的重载很严重，有多种含义：
      • 副本一致性，以及异步复制系统中的最终一致性。
      • 一致性散列（Consistency Hash）)是某些系统用于重新分区的一种分区方法。
      • 在CAP定理中，一致性一词用于表示可线性化。
      • 在ACID的上下文中，一致性是指数据库在应用程序的特定概念中处于“良好状态”。
    • 隔离性（Isolation）意味着，同时执行的事务是相互隔离的：它们不能相互冒犯，。例如，如果一个事务进行多次写入，则另一个事务要么看到全部写入结果，要么什么都看不到，但不应该是一些子集。传统的数据库教科书将隔离性形式化为串行化（Serializability），这意味着每个事务可以假装它是唯一在整个数据库上运行的事务。实践中很少会使用串行化隔离，因为它有性能损失。一些流行的数据库如Oracle 11g， 甚至没有实现它。一般使用如 快照隔离和其他形式的隔离。
    • 持久性（Durability）：一旦事务成功完成，即使发生硬件故障或数据库崩溃，写入的任何数据也不会丢失
  • 对于单个对象的原子性、隔离性比较好实现，如自增这样的原子操作，或者 CAS，但是 事务通常被理解为，将多个对象上的多个操作合并为一个执行单元的机制
  • 弱隔离级别：读已提交
    • 读已提交需要实现：
      1. 从数据库读时，只能看到已提交的数据（没有脏读（dirty reads））。
      2. 写入数据库时，只会覆盖已经写入的数据（没有脏写（dirty writes））
    • 读已提交是一个非常流行的隔离级别。这是Oracle 11g，PostgreSQL，SQL Server 2012， MemSQL和其他许多数据库的默认设置。
    • 防止脏写的实现：常见的数据库通过使用行锁（row-level lock）来防止脏写：当事务想要修改特定对象（行或文档）时，它必须首先获得该对象的锁。
    • 防止脏读的实现：用行锁性能不好，所以大多数数据库用这种方式实现：对于写入的每个对象，数据库都会记住旧的已提交值，和由当前持有写入锁的事务设置的新值。 当事务正在进行时，任何其他读取对象的事务都会拿到旧值。只有当新值提交后，事务才会切换到读取新值。
  • 弱隔离级别：快照隔离和可重复读
    • 快照隔离（snapshot isolation）的想法是，每个事务都从数据库的一致快照（consistent snapshot）中读取——也就是说，事务可以看到事务开始时在数据库中提交的所有数据。即使这些数据随后被另一个事务更改，每个事务也只能看 到该特定时间点的旧数据。快照隔离对长时间运行的只读查询（如备份和分析）非常有用。如果查询的数据在查询执行的同时发生变化，则很难理解查询的含义。当一个事务可以看到数据库在某个特定时间点冻结时的一致快照，理解起来就很容易了。快照隔离是一个流行的功能：PostgreSQL，使用InnoDB引擎的MySQL，Oracle，SQL Server等都支持
    • 实现方式：数据库必须可能保留一个对象的几个不同的提交版本，因为各种正在进行的事务可能需要看到数据库在不同的时间点的状态。因为它并排维护着多个版本的对象，所以这种技术被称为多版 本并发控制（MVCC, multi-version concurrentcy control）（如果一个数据库只需要提供读已提交的隔离级别，而不提供快照隔离，那么保留一个对象的两个版本就足够了：提交的版本和被覆盖但尚未提交的版本）
  • 防止丢失更新：两个事务并发写入的问题
    • 原子写，如 update A set a = a 1
    • 显式锁定, 如 select for update
    • 自动检测丢失的更新
    • CAS, Update A set a = 1 where a = 0
  • 写入偏差与幻读
    • 写入偏差既不是脏写，也不是丢失更新：两个医生同时休班的例子，在这里发生的冲突并不是那么明显，但是这显然是一个竞争条件：如果两个事务一个接一个地运行，那么第二个医生就不能歇班了。异 常行为只有在事务并发进行时才有可能。
    • 可以将写入偏差视为丢失更新问题的一般化。如果两个事务读取相同的对象，然后更新其中 一些对象（不同的事务可能更新不同的对象），则可能发生写入偏差。
    • 自动防止写入偏差需要真正的可串行化隔离，如果无法使用可序列化的隔离级别，则此情况下的次优选项可能是显式锁定事务所依赖的行 （select for update）
    • 其他导致 写入偏差 的例子：预定会议，抢注用户名 ...这些例子都遵循类似的模式:
      • 一个 SELECT 查询找出符合条件的行，并检查是否符合一些要求
      • 按照第一个查询的结果，应用代码决定是否继续
      • 如果应用决定继续操作，就执行写入（插入、更新或删除），并提交事务
    • 在医生值班的例子中，可以通过锁 定步骤1 中的行（ SELECT FOR UPDATE ）来使事务安全并避免写入偏差。但是其他几个例子是不同的：它们检查是否不存在某些满足条件的行，写入会添加一个匹配相同条件的行。如果步骤1中的查询没有返回任何行，则 SELECT FOR UPDATE 锁不了任何东西。这种效应：一个事务中的写入改变另一个事务的搜索查询的结果，被称为幻读。
    • 如果幻读的问题是没有对象可以加锁，也许可以人为地在数据库中引入一个锁对象。这种方法被称为物化冲突（materializing conflicts）因为它将幻读变为数据库中一组具体 行上的锁冲突。不幸的是，弄清楚如何物化冲突可能很难，也很容易出错，而让并发控制机制泄漏到应用数据模型是很丑陋的做法。出于这些原因，如果没有其他办法可以实 现，物化冲突应被视为最后的手段。在大多数情况下。可串行化（Serializable） 的隔离级别 是更可取的。
  • 可串行化
    • 可串行化（Serializability）隔离通常被认为是最强的隔离级别。它保证即使事务可以并行执 行，最终的结果也是一样的，就好像它们没有任何并发性，连续挨个执行一样。
    • 串行执行事务的方法在VoltDB/H-Store，Redis和Datomic中实现。
    • 大约30年来，在数据库中只有一种广泛使用的序列化算法：两阶段锁定（2PL，two-phase locking）
      • 两阶段锁定对锁的要求更强。只要没有写入，就允许多个事务同时读取同一个对象。但对象只要有写入（修改或删除），就需要独占访问（exclusive access） 权限 （读取旧版本的对象在2PL下是不可接受的）
      • 在2PL中，写入不仅会阻塞其他写入，也会阻塞读，反之亦然。快照隔离使得读不阻塞写，写 也不阻塞读，这是2PL和快照隔离之间的关键区别。
      • 具有可串行化隔离级别的数据库必须防止幻读：从概念上讲，我们需要一个谓词锁（predicate lock）。它类似于前面描述的共享/排它锁，但不属于特定的对象（例如，表中的一行），它属于所有符合某些搜 索条件的对象。
      • 不幸的是谓词锁性能不佳：如果活跃事务持有很多锁，检查匹配的锁会非常耗时。因此，大多数使用2PL的数据库实际上实现了索引范围锁（也称为间隙锁（next-key locking））。索引范围锁并不像谓词锁那样精确（它们可能会锁 定更大范围的对象，而不是维持可串行化所必需的范围），但是由于它们的开销较低，所以 是一个很好的折衷
  • 在存储过程中封装事务
    • 现代的存储过程实现放弃了PL/SQL，而是使用现有的通用编程语言：VoltDB使用Java或Groovy，Datomic使用Java或Clojure，而Redis使用Lua
  • 悲观与乐观的并发控制
    • 两阶段锁是一种所谓的悲观并发控制机制（pessimistic） ：它是基于这样的原则：如果有事情可能出错（如另一个事务所持有的锁所表示的），最好等到情况安全后再做任何事情。
    • 快照隔离是一种乐观（optimistic） 的并发控制技术

第八章：分布式系统的麻烦

  • 不可靠的网络
    • 一些对延迟敏感的应用程序（如视频会议和IP语音（VoIP））使用UDP而不是TCP, 在延迟数据毫无价值的情况下，UDP是一个不错的选择。
  • 不可靠的时钟
    • 一个例子
  • 如果存在节点可能“撒谎”（发送任意错误或损坏的响应）的风险，则分布式系统的问题变得 更困难了——例如，如果节点可能声称其实际上没有收到特定的消息。这种行为被称为拜占 庭故障（Byzantine fault），在不信任的环境中达成共识的问题被称为拜占庭将军问题。制作拜占庭容错系统的协议相当复杂，而容错嵌入式系统依赖于硬件层面的支持。在大多数服务器端数据系统中，部署拜占庭容错解决方案的成 本使其变得不切实际。
  • 关于定时假设的三种模型：同步模型, 部分同步模型, 异步模型
  • 三种故障模型：崩溃-停止故障，崩溃-恢复故障，拜占庭（任意）故障
代码语言：txt复制
while(true){ 
    request = getIncomingRequest(); 
    // 确保租约还剩下至少10秒 
    if (lease.expiryTimeMillis-System.currentTimeMillis()< 10000){
        // 时间可能不同步
        lease = lease.renew(); 
    }
    if(lease.isValid()){ 
        // 如果处理/或者 gc/虚拟机被挂起 超过 10秒，可能已经丢掉了租约
        process(request); 
    }} 
}

第九章：一致性与共识

  • 分布式系统中的一致性指的是数据在多份副本中存储时，如何保障数据的一致性（所有客户端都能读到最新版本的数据）场景
  • 构建容错系统的最好方法，是找到一些带有实用保证的通用抽象，实现一次，然后让应用依 赖这些保证。比如事务：通过使用事务，应用可以假装没有崩溃（原子性），没有其他人同时访问数据库（隔离），存储设备是完全可靠的（持久性）。即使发生崩溃，竞态条件和磁盘故障，事务抽象隐藏了这些问题，因此应用不必担心它们。
  • 分布式系统最重要的抽象之一就是共识（consensus）：就是让所有的节点对某件事达成一致。
  • 大多数复制的数据库至少提供了最终一致性，这意味着如果你停止向数据库写入数据并等待 一段不确定的时间，那么最终所有的读取请求都会返回相同的值.
  • 线性一致性（也称为原子一致性（atomic consistency），强一致性（strong consistency），立即一致性（immediate consistency）或外部一致性（external consistency ））。基本的想法是让一个系统看起来好像只有一个数据副本，而且所有的操作都是原子性的。有了这个保证，即使实际中可能有多个副本，应用也不需要担心它们。
    • 任何一个读取返回新值后，所有后续读取（在相同或其他客户端上）也必须返回新值
  • 共识算法可以安全地实现线性一致性存储。
  • 不需要线性一致性（某个副本即使与其他副本断开连接，也可以独立处理 请求（例如多主复制））的应用对网络问题有更强的容错能力。这种见解通常被称为CAP定理
    • CAP 【一致性，可用性和分区容错性，3选2，更准确的说法是：在网络正常工作的时候，系统可以提供一致性（线性一致性）和整体可用性。发生网络故障时，你必须在线性一致性和整体可用性之间做出选择。】定理的正式定义仅限于很狭隘的范围，它只考虑了一个一致性模型（即线性一致性）和一种故障（网络分区，或活跃但彼此断开的节点）。它没有讨论任何关于网络延迟，死亡节点或其他权衡的事。因此，尽管CAP在历史上有一些影响力，但对于设计系统而言并没有实际价值。
    • 虽然线性一致是一个很有用的保证，但实际上，线性一致的系统惊人的少。例如，现代多核 CPU上的内存甚至都不是线性一致的。牺牲线性一致性的原因是性能（performance），而不是容错。
  • 顺序与因果：
    • 在线性一致的数据存储中是不存在并发操作的：必须有且仅有一条时间线，所有的操作都在这条时间线上，构成一个全序关系。
    • 任何线性一致的系统都能正确保持因果性
    • 在许多情况下，看上去需要线性一致性的系统，实际上需要的只是因果一致性，因果一致性 可以更高效地实现。基于这种观察结果，研究人员正在探索新型的数据库，既能保证因果一 致性，且性能与可用性与最终一致的系统类似
  • 全序广播通常被描述为在节点间交换消息的协议。非正式地讲，它要满足两个安全属性：
    • 可靠交付（reliable delivery）没有消息丢失：如果消息被传递到一个节点，它将被传递到所有节点。
    • 全序交付（totally ordered delivery） 消息以相同的顺序传递给每个节点。
  • 全序广播是异步的：消息被保证以固定的顺序可靠地传送，但是不能保证消息何时被送达 （所以一个接收者可能落后于其他接收者）。相比之下，线性一致性是新鲜性的保证：读取 一定能看见最新的写入值。但如果有了全序广播，你就可以在此基础上构建线性一致的存储。
  • 可以证明，线性一致的CAS（或自增并返回）寄存器与全序广播都都等价于共 识问题
  • 分布式事务与共识：
    • 2PC（原子提交与二阶段提交）是一种共识算法，但不是一个非常好的算法。
    • 两阶段提交（two-phase commit）是一种用于实现跨多个节点的原子事务提交的算法，即 确保所有节点提交或所有节点中止。【当参与者投票“是”时，它承诺它稍后肯定能够提交】
    • 这种做法中事务协调者本身就是 一种数据库，如果协调者没有副本，那么它是整个系统的单点。
  • 共识算法
    • 大多数共识算法假设不存在拜占庭式错误
    • 单领导者复制和共识:在第5章中，我们讨论了单领导者复制（参见“领导者和追随者”），它将所有的写入操作都交给主库，并以相同的顺序将它们应用到从库，从而使副本保持在最新状态。这实际上不就是一个全序广播吗？为什么我们在第五章里一点都没担心过共识问题呢？答案取决于如何选择领导者。如果主库是由运维人员手动选择和配置的，那么你实际上拥有一种独裁类型的“共识算法”：只有一个节点被允许接受写入（即决定写入复制日志的顺序），如果该节点发生故障，则系统将无法写入，直到运维手动配置其他节点作为主库。这样的系统在实践中可以表现良好，但它无法满足共识的终止属性，因为它需要人为干预才能取得进展.
    • 共识的局限性：共识算法对于分布式系统来说是一个巨大的突破：它为其他充满不确定性的系统带来了基础的安全属性（一致同意，完整性和有效性），然而它们还能保持容错（只要多数节点正常工作且可达，就能取得进展）。它们提供了全序广播，因此它们也可以以一种容错的方式实现线性一致的原子操作。
      • 节点在做出决定之前对提议进行投票的过程是一种同步复制：性能问题
      • 共识系统总是需要严格多数来运转
      • 大多数共识算法假定参与投票的节点是固定的集合，这意味着你不能简单的在集群中添加或 删除节点
      • 共识系统通常依靠超时来检测失效的节点
      • 有时共识算法对网络问题特别敏感

第三部分：衍生数据

  • 记录系统，也被称为真相源（source of truth），持有数据的权威版本
  • 衍生数据系统：衍生系统中的数据，通常是另一个系统中的现有数据以某种方式进行转换或处理的结果。如果丢失衍生数据，可以从原始来源重新创建。典型的例子是缓存。
数据库 数据结构 sql 云数据库MongoDB

0 人点赞