分布式数据系统
- 扩展性
- 容错与高性能
- 延迟考虑
- 系统扩展能力
- 无共享结构
- 复制与分区
数据复制
- 目的
- 使数据在地理位置上更接近用户，从而降低访问延迟
- 当部分组件出现位障，系统依然可以继续工作，从而提高可用性
- 扩展至多台机器以同时提供数据访问服务，从而提高读吞吐量
- 三种复制方案
- 主从复制
- 工作原理
- 指定某一个副本为主副本(或称为主节点)。当客户写数据库时，必须将写请求首先发送给主副本，主副本首先将新数据写入本地存储
- 其他副本全部称为从副本或称为从节点。主副本把新数据写入本地存储后，然后将数据更改作为复制的日志或更改流发送给所有从副本。每个从副本获得更改日志之后将其应用到本地，且严格保持与主副本相同的写入顺序。
- 客户端从数据库中读数据时，可以在主副本或者从副本上执行查询。再次强调，只有主副本才可以接受写请求,从客户端的角度来看，从副本都是只读的。
- 同步复制与异步复制
- 同步复制数据强一致性，但是会阻塞后续的写操作
- 异步响应速度快
- 实践中把一个副节点设置为同步复制，其他副节点设置为异步复制，当主节点不可用时，提升另一个副节点到主节点
- 全异步复制吞吐高，存在数据丢失问题，复制滞后问题
- 配置新的从节点
- 在某个时间点对主节点的数据副本产生一个一致性快照，这样避免长时间锁定整个数据库
- 将此快照拷贝到新的从节点
- 从节点连接到主节点并请求快照点之后所发生的数据更改日志
- 获得日志之后，从节点来应用这些快照点之后所有数据变更，这个过程称之为追赶。接下来，它可以继续处理主节点上新的数据变化
- 处理节点失效
- 从节点失效
- 从节点根据复制日志，知道故障之前最后一笔事务，然后连接到主节点，请求那笔事务后面所有的数据变更。
- 主节点失效
- 确认主节点失效，心跳检测
- 选举出新的主节点，共识算法
- 重新配置系统使得新节点生效，原主节点重新上线后要降级成从节点
- 变数
- 使用异步复制丢失数据，主从切换过程中丢失数据
- 其他依赖数据库的内容在一起使用
- 集群脑裂
- 不合适的超时检测
- 复制日志的实现
- 基于语句的复制
- 主节点记录所执行的每个写请求(操作语句)并将该操作语句作为日志发送给从节点
- 问题
- 调用 date()，rand()等函数会在从节点产生不一样的值
- 并发事务限制
- 有副作用的语句会在不同的节点产生不同的副作用
- 基于 WAL 传输
- 从节点收到日志进行处理，建立与主节点内容完全相同的数据副本
- 问题
- 基于行的逻辑日志复制
- 关系数据库的逻辑日志通常是指一系列记录来描述数据表行级别的写请求
- 对于行插入，日志包含所有相关列的新值。
- 对于行删除，日志里有足够的信息来唯一标识已删除的行，通常是靠主键，但如果表上没有定义主键，就需要记录所有列的旧值。
- 对于行更新，日志包含足够的信息来唯一标识更新的行，以及所有列的新值(或至少包含所有已更新列的新值)。
- 优势
- 与存储引擎结耦，更容易向后兼容
- 容易解析，可以发送到外部数据源
- 基于触发器的复制
- 触发器支持注册自己的应用层代码，使得当数据库系统发生数据更改(写事务)时自动执行上述自定义代码。通过触发器技术，可以将数据更改记录到一个单独的表中，然后外部处理逻辑访问该表，实施必要的自定义应用层逻辑，例如将数据更改复制到另一个系统。
- 问题
- 复制滞后问题
- 主从复制要求所有写请求经过主节点，而任何副节点只能接收只读查询。
- 当从节点变多时，可以提高读请求的服务吞吐量，但是写请求吞吐变低
- 副节点落后与主节点，读到过期数据，一段时间后达成最终一致性
- 解决复制滞后的问题
- 写后读一致性
- 如果用户访问可能会被修改的内容，从主节点读取;否则，在从节点读取
- 客户端还可以记住最近更新时的时间戳 ，并附带在读请求中，据此信息，系统可以确保对该用户提供读服务时都应该至少包含了该时间戳的更新 。如果不够新，要么交由另一个副本来处理，要么等待直到副本接收到了最近的更新。
- 如果副本分布在多数据中心，情况会更复杂些。必须先把请求路由到主节点所在的数据中心
- 跟踪最近更新的时间，如果更新后一分钟之内，则总是在主节点读取;并监控从节点的复制滞后程度，避免从那些滞后时 间超过一分钟的从节点读取
- 需要考虑的问题
- 记住用户上次更新时间戳的方法实现起来会比较困难，因为在一台设备上运行的代码完全无法知道在其他设备上发生了什么。此时，元数据必须做到全局共享
- 如果副本分布在多数据中心, 无法保证来自不同设备的连接经过路由之后都到达同一个数据中心，需要想办法确保将来自不同设备的请求路由到同一个数据中心
- 单调读
- 一个比强一致性弱，但比最终一致性强的保证。当读取数据时，单调读保证，如果某个用户依次进行多次读取，则他绝 不会看到回滚现象，即在读取较新值之后又发生读旧值的情况
- 一种实现方法是每个用户总是从同一副本执行读取
- 前缀一致读
- 保证是说，对于一系列按照某个顺序发生的写请求，那么读取这些内容时也会按照当时写入的顺序
- 一个解决方案是确保任何具有因果顺序关系的写入都交给一个分区来完成
- 多主节点复制
- 单节点单点失败问题
- 适用场景
- 多数据中心
- 在每个数据中心都配置主节点
- 每个数据中心内，采用常规的主从复制方案
- 数据中心之间，由各个数据中心的主节点来负责同其他数据中心的主节点进行数据的交换、更新
- 与单节点的主从复制方案的区别
- 就近访问，降低写入延迟，异步同步到其他数据中心
- 容忍数据中心失效，每个数据中心的主节点独立运行，失效主节点恢复后可以重新从其他主节点获取最新数据
- 容忍网络问题，主从模式写入是同步操作，需要更可靠的网络性能，多主节点是异步复制，可以更好容忍不可靠的网络
- 离线客户端操作
- 协作编辑
- 当一个用户编辑文档时，所做的更改会立即应用到本地副本，然后异步复制到服务器以及编辑同一文档的其他用户。
- 如果要确保不会发生编辑冲突，则应用程序必须先将文档锁定，然后才能对其进行编辑。如果另一个用户想要编辑同一个文档，首先必须等到第一个用户提交修改并释放锁。这种协作模式相当于主从复制模型下在主节点上执行事务操作。
- 为了加快协作编辑的效率，可编辑的粒度需要非常小。
- 处理写冲突
- 在不同的数据中心修改统一记录，在数据中心内部完成写入，在跨数据中心同步的时候出现写冲突
- 同步与异步冲突检测
- 避免冲突
- 在应用层保证对同一记录的写请求只通过同一个主节点
- 由于主节点失效或者客户端漫游因为转到其他数据中心，此方法不再有效
- 收敛于一致状态的几个方案
- 给每个写入分配唯一的 ID，例如，一个时间戳，二个足够长的随机数，一个 UUID 或者一个基于键-值的哈希，挑选最高 ID 的写入作为胜利者，并将其他写入丢弃。如果基于时间戳，这种技术被称为最后写入者获胜。虽然这种方法很流行，但是很容易造成数据丢失。
- 为每个副本分配一个唯一的 ID，并制定规则，例如序号高的副本写入始终优先于序号低的副本 。这种方法也可能会导致数据丢失。
- 以某种方式将这些值合并在一起
- 利用预定义好的格式来记录和保留冲突相关的所有信息，然后依靠应用层的逻辑，事后解决冲突
- 自定义冲突解决逻辑
- 在写入时执行
- 只要数据库系统在复制变更日志时检测到冲突，就会调用应用层的冲突处理程序
- 在读取时执行
- 当检测到冲突时，所有冲突写入值都会暂时保存下来。下一次读取数据时，会将数据的多个版本读返回给应用层。应用层可能会提示用户或自动解决冲突，并将最后的结果返回到数据库。
- 自动冲突解决
- 无冲突的数据结构
- 可合并的持久数据结构，三向合并功能
- 操作转换，为可同时编辑的有序列表设计
- 拓扑结构
- 复制的拓扑结构描述了写请求从一个节点传播到其他节点的通信路径。
- 多个主节点存在多个可能的同步的拓扑结构。
- 环形和星形拓扑的问题是，如果某一个节点发生了故障，在修复之前，会影响其他节点之间复制日志的转发。
- 全链接拓扑也存在一些自身的问题。主要是存在某些网络链路比其他链路更快的情况，从而导致复制日志之间的覆盖
- 为了使得日志消息正确有序，可以使用一种称为版本向量的技术
- 无主节点复制
- 选择放弃主节点，允许任何副本直接接受来自客户端的请求
- 节点失效时写入数据库
- 半数写入确认即可认为写入成功，读取时从多个副本同时读取，按照版本号确定那个值是最新的
- 读修复与反熵
- 失效节点上线后如何恢复错过的请求
- 读修复
- 当客户端并行读取多个副本时，可以检测到过期的返回值，然后将新值写入到该副本。这种方怯主要适合那些被频繁读取的场景。
- 反熵过程
- 数据存储用后台进程不断寻找副本之间的差异，将缺少的数据复制过去。如果没有反熵过程的存储系统只有在读的时候可以修复数据
- 读写 quorum
- 如果有 n 个副本，写人需要 w 个节点确认，读取必须至少查询 r 个节点， 则只要 w + r > n ，读取的节点中一定会包含最新值，一个常见的选择是设置 n 为某奇数(通常为 3 或 5), w = r = (n + 1) / 2
- 仲裁条件 w + r > n 定义了系统可容忍的失效节点数，如下所示:
- 当 w < n，如果一个节点不可用，仍然可以处理写入。
- 当 r < n，如果一个节点不可用，仍然可以处理读取。
- 假定 n=3, w=2, r=2，则可以容忍一个不可用的节点。
- 假定 n=5, w=3, r=3，则可以容忍两个不可用的节点
- 通常，读取和写入操作总是并行发送到所有的 n 个副本。参数 w 和参数 r 只是决定要等待的节点数。即有多少个节点需要返回结果，我们才能判断出结果的正确性。
- Quorum 一致性的局限性
- w + r > n 一定可以读到最新值，但是不一定要多数，只要读写之间有重叠就可以，可以等待更少的时间就可以返回。
- 即使 w + r > n 也可能读到旧值：
- 如果采用了 sloppy quorum，写操作的 w 节点和读取的 r 节点可能完全不同，因此无法保证读写请求一定存在重叠的节点
- 如果两个写操作同时发生，则无法明确先后顺序，需要根据时间戳来确定胜者，但由于时钟偏差问题，某些写入可能会被错误的抛弃
- 如果写操作与读操作同时发生 ，写操作可能仅在一部分副本上完成。此时，读取时返回旧值还是新值存在不确定性。
- 如果某些副本上已经写入成功，而其他一些副本发生写入失败，且总的成功副本数少于 w，那些已成功的副本上不会做回滚。这意味着尽管这样的写操作被视为失败，后续的读操作仍可能返回新值。
- 如果具有新值的节点后来发生失效，但恢复数据来自某个旧值， 则总的新值副本数会低于 w，这就打破了之前的判定条件
- 即使一切正常工作，也会出现一些边界情况。
- 监控旧值
- 即使应用可以容忍旧值，也需要了解复制当前的运行状态，如果出现了明显的滞后，它就是个重要的信号提醒我们需要采取必要的措施来排查原因。
- 对于主从复制的系统，由于主节点和从节点上写人都遵从相同的顺序，而每个节点都维护了复制日志执行的当前偏移量。通过对比主节点和从节点当前偏移量的差值，即可衡量该从节点落后于主节点的程度
- 对于无主节点的系统，还没有一个可用的方案。
- 宽松的 quorum 与数据回传
- 当客户端连不上存储节点时，把数据写入一个可访问的节点，这个节点不在 n 的结合中，等到恢复后，把这个数据的节点回传到 n 原始节点中。
- 多数据中心操作
- 副本的数量 n 是包含所有数据中心的节点总数。配置时，可以指定每个数据中心各有多少副本。每个客户端的写入都会发送到所有副本，但客户端通常只会等待来自本地数据中心内的 quorum 节点数的确认，这样避免了高延迟和跨数据中心可能的网络异常。尽管可以灵活配置，但对远程数据中心的写入由于延迟很高，通常都被配置为异步方式
- 检测并发写
- 最后写入者获胜
- 数据带上时间戳，丢弃较早的写入，牺牲了数据持久性，如果不能接收丢失数据的话，可以为每一次写入分配 UUID 主键
- Happen-before 关系和并发
- 如果一个操作无能意识到另一个操作，那么旧可以称他们时并发操作
- 确定前后关系
- 服务器为每个主键维护一个版本号，每当主键新值写入时递增版本号，并将新版本号与写入的值一起保存。
- 当客户端读取主键时，服务器将返回所有当前值以及最新的版本号。且要求写之前，客户必须先发送读请求。
- 客户端写主键，写请求必须包含之前读到的版本号、读到的值和新值合并后的集合。写请求的响应可以像读操作一样，会返回所有当前值，这样就可以像购物车例子那样一步步链接起多个写入的值。
- 当服务器收到带有特定版本号的写入时，覆盖该版本号或更低版本的所有值，但必须保存更高版本号的所有值。
- 合并同时写入的值
- 一个简单的方法是基于版本号或时间戳来选择其中的一个值，但这意味着会丢失部分数据。所以，需要在应用程序代码中额外做些工作。
- 考虑到在应用代码中合并非常复杂且容易出错，因此可以设计一些专门的数据结构来自动执行合并，例如， Riak 支持称为 CRDT 一系列数据结构，以合理的方式高效自动合并，包括支持删除标记。
- 版本矢量
- 当多个副本同时接受写入时，我们需要为每个副本和每个主键均定义一个版本号。每个副本在处理写入时增加自己的版本号，并且跟踪从其他副本看到的版本号。通过这些信息来指示要覆盖哪些值、该保留哪些并发值。
数据分区
- 面对一些海量数据集或非常高的查询压力，复制技术还不够，我们还需要将数据拆分成为分区，也称为分片
- 分区通常是这样定义的，即每一条数据(或者每条记录，每行或每个文档)只属于某个特定分区
- 采用数据分区的主要目的是提高可扩展性。不同的分区可以放在一个无共享集群的不同节点上。这样一个大数据集可以分散在更多的磁盘上，查询负载也随之分布到更多的处理器上。
- 对单个分区进行查询时，每个节点对自己所在分区可以独立执行查询操作，因此添加更多的节点可以提高查询吞吐量。超大而复杂的查询尽管比较困难，但也可能做到跨节点的并行处理。
- 数据分区与数据复制
- 分区通常与复制结合使用，即每个分区在多个节点都存有副本。这意味着某条记录属于特定的分区，而同样的内容会保存在不同的节点上以提高系统的容错性。
- 一个节点可能即是某些分区的主副本，同时又是其他分区的从副本
- 键-值数据的分区
- 分区的主要目标是将数据和查询负载均匀分布在所有节点上
- 分区不均匀，则会出现某些分区节点比其他分区承担更多的数据量或查询负载，称之为倾斜。
- 负载严重不成比例的分区即成为系统热点
- 基于关键字区间分区
- 为每个分区分配一段连续的关键字或者关键宇区间范围，如果知道关键字区间的上下限，就可以轻松确定那个分区包含这些关键字。如果还知道哪个分区分配在哪个节点，就可以直接向该节点发出请求
- 为了更均匀地分布数据，分区边界理应适配数据本身的分布特征
- 每个分区内可以按照关键字排序保存，这样可以轻松支持区间查询，即将关键字作为一个拼接起来的索引项从而一次查询得到多个相关记录
- 分区热点问题
- 基于关键字哈希值分区
- 一个好的哈希函数可以处理数据倾斜并使其均匀分布
- 丧失了良好的区间查询特性
- Cassandra 中的表可以声明为由多个列组成的复合主键。复合主键只有第一部分可用于哈希分区，而其他列则用作组合索引来对 Cassandra SSTable 中的数据进行排序
- 基于哈希的分区方法可以减轻热点，但是无法做到完全避免。
- 一个简单的解决方法是对这小部分热点数据添加随机数再次分区，缺点是查询时需要查询所有分区再做合并。
- 分区与二级索引
- 基于文档的二级索引
- 每个列表都有一个唯一的文档 ID，用此 ID 对数据库进行分区
- 每个分区完全独立，各自维护自己的二级索引
- 二级索引的查询代价高昂，容易导致读延迟显著放大
- 基于此条的二级索引分区
- 对所有的数据构建全局索引，而不是每个分区维护自己的本地索引
- 全局索引也必须进行分区，且可以与数据关键字采用不同的分区策略
- 分区再平衡
- 查询压力增加，因此需要更多的 CPU 来处理负载
- 数据规模增加，因此需要更多的磁盘和内存来存储数据
- 节点可能出现故障，因此需要其他机器来接管失效的节点
- 所有这些变化都要求数据和请求可以从一个节点转移到另一个节点。这样一个迁移负载的过程称为再平衡
- 需求
- 平衡之后，负载、数据存储、读写请求等应该在集群范围更均匀地分布。
- 再平衡执行过程中，数据库应该可以继续正常提供读写服务。
- 避免不必要的负载迁移，以加快动态再平衡，并尽量减少网络和磁盘 I/O 影响。
- 动态再平衡策略
- 固定数量的分区
- 首先创建远超实际节点数的分区数，然后为每个节点分配多个分区。
- 接下来，如果集群中添加了一个新节点，该新节点可以从每个现有的节点上匀走几个分区，直到分区再次达到全局平衡
- 分区的数量再创建数据库时就确定好，原则上可以拆分和合并
- 需要分区规模和数据规模相适应
- 动态分区
- 每个分区总是分配给一个节点，而每个节点可以承载多个分区，这点与固定数量的分区一样。当一个大的分区发生分裂之后，可以将其中的一半转移到其他某节点以平衡负载。
- 分区数量可以自动适配数据总量
- 少量的数据，少量的分区就足够了
- 大量的数据，每个分区的大小则被限制在一个可配的最大值
- 按节点比例分区
- 每个节点具有固定数量的分区。此时，当节点数不变时，每个分区的大小与数据集大小保持正比的增长关系;当节点数增加时，分区则会调整变得更小。较大的数据量通常需要大量的节点来存储，因此这种方式也使每个分区大小保持稳定。
- 全自动的平衡会出现难以预测的结果，将自动平衡与自动故障相结合也可能存在一定风险，让管理员介入再平衡是个更好的选择
- 请求路由
- 允许客户端链接任意的节点。如果某节点恰好拥有所请求的分区，则直接处理该请求:否则，将请求转发到下一个合适的节点，接收答复，并将答复返回给客户端。
- 将所有客户端的请求都发送到一个路由层，由后者负责将请求转发到对应的分区节点上
- 客户端感知分区和节点分配关系
- 并行查询执行
- 典型的数据仓库查询包含多个联合、过滤、分组和聚合操作。MPP 查询优化器会将复杂的查询分解成许多执行阶段和分区，以便在集群的不同节点上并行执行。尤其是涉及全表扫描这样的查询操作，可以通过并行执行获益颇多。
事务
- 出错
- 数据库软件或硬件可能会随时失效(包括正在执行写操作的过程中)。
- 应用程序可能随时崩溃(包括一系列操作执行到中间某一步)。
- 应用与数据库节点之间的链接可能随时会中断，数据库节点之间也存在同样问题。
- 多个客户端可能同时写入数据库 ，导致数据覆盖。
- 客户端可能读到一些无意义的、部分更新的数据。
- 客户端之间由于边界条件竞争所引入的各种奇怪问题。
- 深入理解事务
- ACID
- 原子性(Atomicity)
- 一致性(Consistency)
- 指对数据有特定的预期状态，任何数据更改必须满足这些状态约束(或者恒等条件)
- 如果某事务从一个有效的状态开始，并且事务中任何更新操作都没有违背约束，那么最后的结果依然符合有效状态。
- 隔离性(Isolation)
- 并发执行的多个事务相互隔离，它们不能互相交叉，数据库系统要确保当事务提交时，其结果与串行执行完全相同
- 持久性(Durability)
- 提供一个安全可靠的地方来存储数据而不用担心数据丢失，一且事务提交成功，即使存在硬件故障或数据库崩溃，事务所写入的任何数据也不会消失
- 单对象和多对象事务操作
- 单对象写入
- 基于日志恢复实现原子性，对每个对象采取加锁的方式来实现隔离
- 通常意义上的事务针对的是多个对象，将多个操作聚合为一个逻辑执行单元
- 多对象事务的必要性
- 当出现跨分区时，多对象事务非常难以正确实现，同时在高可用或者极致性能的场景下也会带来很多负面影响
- 没有原子性保证时，错误处理就会异常复杂，而缺乏隔离性则容易出现并发性方面的各种奇怪问题
- 处理错误与中止
- 如果存在违反原子性、隔离性或持久性的风险，则完全放弃整个事务，而不是部分放弃。
- 支持安全的重试机制才是中止流程的重点
- 弱隔离级别
- 某个事务修改数据而另一个事务同时要读取该数据，或者两个事务同时修改相同数据时，才会引发并发问题
- 可串行化的隔离会严重影响性能，而许多数据库却不愿意牺牲性能，因而更多倾向于采用较弱的隔离级别，它可以防止某些但并非全部的并发问题
- RC
- 读数据库时，只能看到已成功提交的数据
- 写数据库时，只会覆盖已成功提交的数据
- 脏读
- 一个事物写入部分数据，但是没有提交，另一个事务可以看到尚未提交的数据，意味着出现了脏读
- 防止脏读
- 如果事务需要更新多个对象，脏读意味着另一个事物可能会看到部分实现
- 事务中止，所有写入操作需要回滚，脏读导致另一个事务读取到需要被回滚的数据
- 防止脏写
- 后面的事务覆盖前面事务对同一个值的修改，RC 隔离级别可以防止脏写，通常的方法是推迟第二个写请求，知道前面的事务完成提交。
- 实现 RC
- 数据库通常采用行级锁来防止脏写:当事务想修改某个对象时，它必须首先获得该对象的锁;然后一直持有锁直到事务提交(或中止)
- 同样采用行锁来防止脏读:所有试图读取该对象的事务必须先申请锁，事务完成后释放锁。从而确保不会发生读取一个脏的、未提交的值
- 快照隔离级别与 RR
- RC 存在不可重复读的问题，在同一事物的多次读取中读到不同的值
- 场景
- 总体想法
- 每个事务都从数据库的一致性快照中读取，事务一开始所看到是最近提交的数据，即使数据随后可能被另一个事务更改，但保证每个事务都只看到该特定时间点的旧数据。
- 快照级别隔离对于长时间运行的只读查询(如备份和分析)非常有用。如果数据在执行查询的同时还在发生变化，那么查询结果对应的物理含义就难以理清。而如果查询的是数据库在某时刻点所冻结的一致性快照，则查询结果的含义非常明确。
- 实现快照级别隔离
- 与读-提交隔离类似，快照级别隔离的实现通常采用写锁来防止脏写，这意味着正在进行写操作的事务会阻止同一对象上的其他事务
- 读取时不需要加锁，这使得数据库在写入的同时不会影响长时间的只读查询。
- 多版本并发控制
- 考虑到多个正在进行的事务可能会在不同的时间点查看数据库状态，所以数据库保留了对象多个不同的提交版本
- 实现快照级别隔离
- 事务开始时，首先赋予一个唯一的、单调递增的事务 ID(txid)。每当事务向数据库写入新内容时，所写的数据都会被标记写入者的事务 ID。表中的每一行都有一个 created_by 字段，其中包含了创建该行的事务 ID。每一行还有一个 deleted_by 字段，初始为空。如果事务要删除某行，主行实际上并未从数据库中删除，而只是将 deleted_by 字段设置为请求删除的事务 ID 。事后，当确定没有其他事务引用该标记删除的行时，数据库的垃圾回收进程才去真正删除并释放存储空间。
- 一致性快照的可见性规则
- 每笔事务开始时，数据库列出所有当时尚在进行中的其他事务，然后忽略这些事务完成的部分写入，即不可见。
- 所有中止事务所做的修改全部不可见
- 较晚事务 ID 所做的任何修改不可见，不管这些事务是否完成了提交。
- 除此之外，其他所有的写入都对应用查询可见
- 可见性条件
- 事务开始的时刻，创建该对象的事务已经完成了提交
- 对象没有被标记为删除; 或者即使标记了，但删除事务在当前事务开始时还没有完成提交
- 索引与快照隔离级别
- 一种方案是索引直接指向对象的所有版本，然后想办法过滤对当前事务不可见的那些版本。当后台的垃圾回收进程决定删除某个旧对象版本时，对应的索引条目也需要随之删除
- 另一种追加/写时复制的技术，当需要更新时，不会修改现有的页面，而总是创建一个新的修改副本，拷贝必要的内容，然后让父结点，或者递归向上直到树的 root 结点都指向新创建的结点。那些不受更新影响的页面都不需要复制，保持不变并被父结点所指向
- 可重复读与命名混淆
- 快照级别隔离对于只读事务特别有效。但是，具体到实现，许多数据库却对它有着不同的命名。Oracle 称之为可串行化，PostgreSQL 和 MySQL 则称为可重复读
- SQL 标准对隔离级别的定义还是存在一些缺陷，某些定义模棱两可，不够精确，且不能做到与实现无关。尽管有几个数据库实现了可重复读，表面上看符合标准，但它们实际所提供的保证却大相径庭
- 防止更新丢失
- 应用程序从数据库读取某些值，根据应用逻辑做出修改，然后写回新值。 当有两个事务在同样的数 据对象上执行类似操作时，由于隔离性，第二个写操作并不包括第一个事务修改后的值，最终会导致第一个事务的修改值可能会丢失
- 几种解决方案
- 原子写操作
- 原子操作通常采用对读取对象加独占锁的方式来实现，这样在更新被提交之前不会其他事务可以读它。这种技术有时被称为游标稳定性。另一种实现方式是强制所有的原子操作都在单线程上执行。
- 显示加锁
- FOR UPDATE 指令指示数据库对返回的所有结果行要加锁
- 自动检测更新丢失
- 先让他们并发执行，但如果事务管理器检测到了更新丢失风险，则会中止当前事务，并强制回退到安全的“读-修改-写回”方式
- 原子比较与设置
- UPDATE wiki_pages SET content = ’new content’ WHERE id = 1234 AND content = ‘old content’
- 冲突解决与复制
- 对于多副本数据库，加锁和原子不再有效，通常采用异步的方式来更新，目前许多多副本数据库采用 LWW 策略，但是容易丢失更新
- 写倾斜与幻读
- 即如果两个事务读取相同的一组对象，然后更新其中一部分: 不同的事务可能更新不同的对象，则可能发生写倾斜; 而不同的事务如果更新的是同一个对象，则可能发生脏写或更新丢失
- 先前方案的限制
- 单对象的原子操作无效
- 自动检测不支持检测写倾斜
- 数据库不支持此约束
- 一个较优的选择是显示对依赖的数据加锁
- 在一个事务中的写入改变了另一个事务查询结果的现象，称为幻读
- 快照级别隔离可以避免只读查询时的幻读，但是对于我们上面所讨论那些读-写事务，它却无法解决棘手的写倾斜问题。
- 实体化冲突
- 如果查询结果没有对象可以加锁，人为引入一些可以加锁的对象
- 串行化
- 实际串行执行
- 解决并发问题最直接的方法是避免并发
- 可行性
- 内存越来越便直，现在讲多应用可以将整个活动数据集都加载到内存中。当事务所需的所有数据都在内存中时，事务的执行速度要比等待磁盘 I/O 快得多。
- 数据库设计人员意识到 OLTP 事务通常执行很快，只产生少量的读写操作。相比之下，运行时间较长的分析查询则通常是只读的，可以在一致性快照上运行，而不需要运行在串行主循环里。
- 采用存储过程封装事务
- 数据库设计者认为，如果整个过程是一个事务，那么就可以方便地原子化执行。
- 采用单线程串行执行的系统往往不支持交互式的多语句事务
- 优缺点
- 语言并没有跟上通用编程语言的发展，语义都相当丑陋、过时，而且缺乏如今大多数编程语言所常用的函数库。
- 在数据库中运行代码难以管理
- 数据库中一个设计不好的存储过程要比同样低效的应用服务器代码带来更大的麻烦
- 分区
- 为了扩展到多个 CPU 核和多节点，可以对数据进行分区
- 对于跨分区的事务，数据库必须在涉及的所有分区之间协调事务。存储过程需要跨越所有分区加锁执行，以确保整个系统的可串行化。
- 由于跨分区事务具有额外的协调开销，其性能比单分区内要慢得多
- 串行执行约束条件
- 事务必须简短而高效，否则一个缓慢的事务会影响到所有其他事务的执行性能
- 仅限于活动数据集完全可以加载到内存的场景
- 写入吞吐量必须足够低，才能在单个 CPU 核上处理; 否则就需要采用分区，最好没有跨分区事务。
- 跨分区事务虽然也可以支持，但是占比必须很小。
- 两段式加锁
- 多个事务可以同时读取同一对象，但只要出现任何写操作，则必须加锁以独占访问
- 如果事务 A 已经读取了某个对象，此时事务 B 想要写入该对象，那么 B 必须等到 A 提交或中止之才能继续。以确保 B 不会在事务 A 执行的过程中间去修改对象。
- 如果事务 A 已经修改了对象，此时事务 B 想要读取该对象，则 B 必须等到 A 提交或中止之后才能继续。对于 2PL，不会出现读到旧值的情况
- 实现
- 如果事务要读取对象，必须先以共享模式获得锁。可以有多个事务同时获得一个对象的共享锁，但是如果某个事务已经获得了对象的独占锁，则所有其他事务必须等待。
- 如果事务要修改对象，必须以独占模式获取锁。不允许多个事务同时持有该锁(包括共享或独占模式)，换言之，如果对象上已被加锁，则修改事务必须等待。
- 如果事务首先读取对象，然后尝试写入对象，则需要将共享锁升级为独占锁。升级锁的流程等价于直接获得独占锁。
- 事务获得锁之后，一直持有锁直到事务结束(包括提交或中止)。这也是名字“两阶段”的来由，在第一阶段即事务执行之前要获取锁，第二阶段(即事务结束时)则释放锁。
- 由于使用了这么多的锁机制，所以很容易出现死锁现象，数据库系统会自动检测事务之间的死锁情况，并强行中止其中的一个以打破僵局，这样另一个可以继续向前执行。而被中止的事务需要由应用层来重试。
- 性能
- 降低了事务的并发性
- 2PL 模式下数据库的访问延迟具有非常大的不确定性
- 谓词锁
- 它的作用类似于之前描述的共享/独占锁，而区别在于，它并不属于某个特定的对象(如表的某一行)，而是作用于满足某些搜索条件的所有查询对象
- 如果事务 A 想要读取某些搞足匹配条件的对象，例如采用 SELECT 查询，它必须以共享模式获得查询条件的谓词锁。如果另一个事务 B 正持有任何一个匹配对象的互斥锁，那么 A 必须等到 B 释放锁之后才能继续执行查询。
- 如果事务 A 想要插入、更新或删除任何对象，则必须首先检查所有旧值和新值是否与现有的任何谓词锁匹配(即冲突)。如果事务 B 持有这样的谓词锁，那么 A 必须等到 B 完成提交(或中止)后才能继续。
- 索引区间锁
- 谓词锁性能不佳 :如果活动事务中存在许多锁，那么检查匹配这些锁就变得非常耗时
- 大多数使用 2PL 的数据库实际上实现的是索引区间锁(或者 next key locking) ，本质上它是对谓词锁的简化或者近似
- 索引区间锁扩大了锁定了对象的范围，但是开销低了很多
- 如果没有合适的索引可以施加区间锁，数据库退回到添加表锁
- 可串行化的快照隔离
- 悲观与乐观的并发控制
- 可串行化的快照隔离是一种乐观并发控制
- 当事务提交时 (只有可串行化的事务被允许提交)，数据库会检查是否确实发生了冲突(即违反了隔离性原则)，如果是的话，中止事务并接下来重试。
- 基于过期的条件做决定
- 检测是否读取了过期的 MVCC 对象
- 当事务提交时，数据库会检查是否存在一些当初被忽略的写操作现在已经完成了提交，如果是则必须中止当前事务。
- 检测写是否影响了之前的读
- 当另一个事务尝试修改时，它首先检查索引，从而确定是否最近存在一些读目标数据的其他事务。这个过程类似于在受影响的宇段范围上获取写锁，但它并不会阻塞读取，而是直到读事务提交时才进一步通知他们 :所读到的数据现在已经发生了变化。
- 可串行化快照隔离的性能
- 可串行化快照隔离的一大优点是事务不需要等待其他事务所持有的锁
- 可串行化快照隔离可以突破单个 CPU 核的限制。
分布式系统的挑战
- 即使系统面临各种出错可能，也需要完成预定工作
- 故障与部分失效
- 单节点：要么工作，要么出错
- 分布式系统：部分失效和不确定性
- 云计算和超算
- 超算：定时备份任务状态，然后保存在持久存储上，当某节点出现故障，停止整个集群的任务，修复后从最近的检查点开始运行。
- 云计算
- 都是在线服务，无法容忍完全不可用
- 普通硬件，故障率较高
- 基于 IP 和以太网通信
- 总是会有部分组建故障
- 容忍系统部分失败
- 网络慢且不可靠
- 我们需要依靠软件提供容错，在不可靠系统上构建可靠的系统
- 需要知道在发生故障时，系统的预期行为是什么
- 不可靠的网络
- 系统的可靠性取决于最不可靠的组件
- 常见出错场景
- 请求可能已经丢失
- 请求还在队列，无法马上发送
- 请求接收方已经宕机
- 远程接收节点暂时无法响应
- 消息在回复过程中丢失
- 远程接收方已经处理请求，但回复却被延迟处理
- 现实中的网络故障
- 检测故障
- 负载均衡器需要避免向己失效的节点继续分发请求
- 对于主从复制的分布式数据库，如果主节点失败，需要将某个从节点提升为主节点，不过由于网络的不确定性很难判断节点是否确实失效。
- 然而不幸的是，由于网络的不确定性使得判断节点是否失效非常困难;而只有在某些特定场景下，或许你可以明确知道哪里出错了
- 假设可以登录节点，但发现服务进程没有侦听目标端口，那么操作系统会返回 RST 或 FIN 标志的数据包来辅助关闭或拒绝 TCP 连接。但是，如果节点在处理请求的过程中发生了崩溃，则很难知道该节点实际处理了多少数据
- 如果服务进程崩溃，但操作系统仍正常运行，可以通过脚本通知其他节点，以便新节点来快速接管而跳过等待超时。
- 如果有权访问数据中心网络交换机，则可以通过管理接口查询是否存在硬件级别的链路故障
- 如果路由器已经确认目标节点不可访问，则会返回 ICMP “目标不可达”数据包来回复请求
- 超时和无限期的延迟
- 较长的超时时间意味着更长时间的等待，才能宣告节点失败。
- 较短的时间可以快速帮助检测，但是可能出现误判，导致同一操作在不同节点执行了两次。
- 当一个节点故障，其承担的职责需要交给其他节点，这个过程会给其他节点和网络带来压力，特别是系统此时处于高负荷状态。转移负载会导致失效扩散，从而造成所有节点崩溃，服务完全不可用。
- 网络拥塞与排队
- 当多个不同节点同时发送数据包到相同的目标节点时，网络交换机会出现排队，然后依次将数据包转发到目标网络。如果网络负载过重，数据包可能必须等待一段时间才能获得发送机会。如果数据量太大，交换机队列塞满，之后的数据包则会被丢弃，网络还在运转，但会引发大量数据包重传。
- 当数据包到达目标机器后，如果所有 CPU 核都处于繁忙状态，则网络数据包请求会被操作系统排队，直到应用程序能够处理。根据机器的配置和负载情况，这里也会引人一段不确定的等待时间
- 在虚拟化环境下，CPU 核会切换虚拟机，从而导致正在运行的操作系统会突然暂停几十毫秒。在这段时间，客户虚机无屈从网络中接收任何数据，入向的包会被虚拟机管理器排队缓冲，进一步增加了网络延迟的不确定性
- TCP 执行流量控制时，节点会主动限制自己的发送 速率以避免加重网络链路或接收节点负载。这意味着数据甚至在进入网络之前，已经在发送方开始了排队。
- 如采延迟或丢弃的数据价值不大， UDP 是个不错的选择
- 超时设置并不是一个不变的常量，而是持续测量响应时间及其变化，然后根据最新的响应时间分布来自动调整
- 同步和异步网络
- 固定电话有持续端到端的低延迟和足够的带宽来传输音频文件。
- 当通过电话网络拨打电话时，系统会动态建立一条电路:在整个线路上为呼叫分配一个固定的、带宽有保证通信链路，该电路一直维持到通话结束
- 这种网络本质是同步的:即使数据中间经过了多个路由器，16bit 空间在电路建立时已经在网络中得到预留，不会受到排队的影响。由于没有排队，网络最大的端到端延迟是固定的。我们称之为有界延迟。
- 网络
- 固定电话独占一段连接，网络连接则是尽可能使用所有带宽。
- 基于分组交换协议的网络注定收到排队的影响
- TCP 动态调整传输速率则可以充分利用所有可用的网络容量
- 当前广泛部署的技术无法为我们提供延迟或可靠性方面的硬件级保证，我们必须假设会出现网络拥塞，排队和无上限的延迟
- 不可靠的时钟
- 但是由于网络的不确定延迟，精确测量面临着很多挑战。这些情况使得多节点通信时很难确定事情发生的先后顺序。
- 通过 NTP 服务器同步机器时间的时钟
- 单调时钟和墙上时钟
- 墙上时钟
- 与 NPT 同步，可以回退到过去，时间精度较为粗糙。
- 单调时钟
- 保证时间单调往前
- 不同的 CPU 有不同过得单调时间，任务在不同 CPU 调度时需要调整之间偏差。
- 精度高，可以计算微秒甚至更短的间隔。
- 时钟同步与准确性
- 计算机中的石英钟不够准确
- 如果与 NTP 服务器的时钟差别过大，可能会出现拒绝同步，或者本地时间将被强制重置
- 与 NTP 服务器同步失败
- 网络延迟导致的 NTP 服务器延迟
- NTP 服务器故障，或者配置错误
- 闰秒处理，在一天的周期内逐步调整闰秒
- 虚拟机中的时钟会突然因为切换出现暂停，然后突然向前发生了跳跃
- 不信任不可控设备上的时钟
- 依赖同步的时钟
- 如果应用需要精确同步的时钟，最好仔细监控所有节点上的时钟偏差。如果某个节点的时钟漂移超出上限，应将其宣告为失效，并从集群中移除。这样的监控的目的是确保在造成重大影响之前尽早发现并处理问题
- 时间戳与事件顺序
- 多主节点复制的分布式数据库依赖墙上时钟，导致在 LWW 中，错误写入旧值
- 时钟的置信区间
- 时间存在误差，因此，我们不应该将时钟读数视为一个精确的时间点，而更应该视为带有置信区间的时间范围。
- 大多数系统不提供置信区间的信息，所以无法知道误差范围
- 全局快照的同步时钟
- 当数据库分布在多台机器上时，由于需要复杂的协调以产生全局的单调递增的事务 ID
- 进程暂停
- 其他节点该如何确信该主节点没有被宣告失效，可以安全地写入
- 定时从其他节点获取租约，只要租约不过期它就是主节点
- 进程暂停导致租约过期，被其他节点接管
- GC
- 虚拟机暂停
- 终端休眠
- 上下文切换
- 磁盘 I/O 和网络 I/O
- 内存访问出现缺页异常
- 使用 SIGSTOP 暂停进程
- 保证响应时间
- 实时操作系统
- 内存分配收到严格限制或被禁止
- 需要大量测试验证
- 调整 GC 的影响
- 把 GC 暂停视为节点的一个计划内的临时离线，当节点启动垃圾回收时，通知其他节点来接管客户端的请求。此外 ，系统可以提前为前端应用发出预警，应用会等待当前请求完成，但停止向该节点发送新的请求，这样垃圾回收可以在无干扰的情况下更加高效运行。这个技巧以某种方式对客户端隐藏垃圾回收，降低负面影响
- 只对短期对象执行垃圾回收，然后在其变成长期存活对象之前，采取定期重启的策略从而避免对长期存活对象执行全面回收。每次选悻一个节点重新启动，在重启之前，重新平衡节点之间的流量，思路与读动升级类似
- 知识，真相与谎言
- 当节点不通时，无法判断是网络原因还是节点原因
- 真相由多数决定
- 超过一半的节点收不到某节点的回复则视为失败
- 节点不能判断自身的状态，需要依靠多数投票
- 主节点与锁
- 只允许一个节点作为数据库分区的主节点，以防止出现脑裂
- 只允许一个事务或客户端持有特定资源的锁，以防止同时写入从而导致数据破坏。
- 只允许一个用户来使用特定的用户名，从而确保用户名可以唯一标识用户
- 出错
- 节点的唯一锁失效之后认为自己还持有锁导致导致多个客户端同时写入出错
- Fencing 令牌
- 我们假设每次锁服务在授予锁或租约时，还会同时返回一个 fencing 令牌，该令牌(数字)每授授予一次就会递增(列如，由锁服务增加)。然后，要求客户端每次向存储系统发送写请求时，都必须包含所持有的 fencing 令牌.
- 靠客户端自己检查锁状态是不够的，这种机制要求资掘本身必须主动检查所持令牌信息，如果发现已经处理过更高令牌的请求，要拒绝持有低令牌的所有写请求
- 服务端不能假设所有客户端都表现异常
- 拜占庭故障
- 弱的谎言形式
- 网络丢包，包损坏
- 客户端的输入
- NTP 配置多个服务器得出正确的时间
- 理论系统模型与现实
- 计时模型
- 同步模型
- 同步模型假定有上界的网络延迟，有上界的进程暂停和有上界的时钟误差
- 部分同步模型
- 部分同步意味着系统在大多数情况下像一个同步系统一样运行，但有时候会超出网络延迟，进程暂停和时钟漂移的预期上界
- 异步模型
- 在这个模型中，一个算法不会对时机做任何的假设，甚至里面根本没有时钟
- 失效模型
- 崩溃-中止模型
- 在崩溃-中止模型中，算在去假设一个节点只能以一种方式发生故障，即遭遇系统崩溃。这意味着节点可能在任何时候突然停止响应，且该节点以后永远消失，无法恢复。
- 崩溃-恢复模型
- 节点可能会在任何时候发生崩溃，且可能会在一段(未知的)时间之后得到恢复并再次响应。在崩溃-恢复模型中，节点上持久性存储(即非易失性存储)的数据会在崩溃之后得以保存，而内存中状态可能会丢失。
- 拜占庭(任意)失效模型
- 算法的正确性
- 唯一性
- 单调递增
- 如果请求 x 返回了令牌 tx，请求 y 返回了令牌 ty，且 x 在 y 开始之前先完成，那么 tx<ty
- 可用性
- 安全与活性
- 唯一性和单调递增属于安全属性，而可用性则属于活性。
- 安全性通常可以理解为“没有发生意外”，而活性则类似“预期的事情最终一定会发生”
- 如果违反了安全属性，我们可以明确指向发生的特定的时间点，且一旦违反安全属性，违规行为无法撤销，破坏已实际发生。
- 活性则反过来:可能无法明确某个具体的时间点，但总是希望在未来某个时间点可以满足要求
- 将系统模型映射到现实世界
- 现实远比理论复杂，系统需要现实大量验证，理论性分析与实证性检验对最终的成功同等重要。
一致性与共识
- 分布式系统最重要的抽象之一就是共识
- 一致性保证
- 大多数多副本的数据库至少提供了最终一致性，不写入的情况下，经过足够长的时间，预期所有的副本会收敛到相同的值。
- 在最终一致性之前，系统可能会在多次请求中读到不一致的值
- 更强的一致性模型
- 分布式一致性主要是针对延迟和故障等问题来协调副本之间的状态
- 线性化
- 时间顺序问题，因果顺序和全局顺序
- 自动提交事务达成共识
- 可线性化
- 让每个客户端都拥有相同的数据视图，而不必担心复制滞后
- a.k.a 原子一致性，强一致性
- 在一个可线性化的系统中，一旦某个客户端成功提交写请求，所有客户端的读请求一定都能看到刚刚写入的值
- 如何达成线性化
- 基本思想：使系统看起来只有一个数据副本
- 约束：一旦某个读操作返回了新值，那么后续的写操作都必须返回新值
- 线性化的依赖条件
- 加锁与主节点选举
- 主从复制的系统需要确保有且只有一个主节点，否则会产生脑裂
- 选举新的主节点常见的方住是使用锁: 即每个启动的节点都试图获得锁，其中只有一个可以成功即成为主节点
- 提供协调者服务的系统如 Apache ZooKeeper 和 etcd 等通常用来实现分布式锁和主节点选举
- 线性化存储服务是所有这些协调服务的基础
- 约束与唯一性保证
- 唯一性约束在数据库中很常见, 用户名或电子邮件地址必须唯一, 这种情况本质上与加锁非常类似: 用户注册等同于试图对用户名进行加锁操作。该操作也类似于原子比较和设置: 如果当前用户名尚未被使用，就设置用户名与客户 ID 进行关联
- 唯一性约束需要线性化保证
- 跨通道的时间依赖
- 线性化违例之所以被注意到，是因为系统中存在其他的通信渠道
- 图片服务器的例子，发送消息比存储更快导致图片处理模块读不到图片
- 实现线性化系统
- 主从复制
- 部分支持可线性化
- 从主节点或者同步更新的节点读取满足线性化需要
- 节点失效重连后依然认为自己是主节点对外服务违反线性化
- 共识算法
- 可线性化
- ZK 和 etcd 等系统用共识算法保证线性化
- 多主复制
- 无主复制
- 线性化与 quorum
- 严格遵从 quorum 可实现可线性化
- 同步读损失性能
- 线性化的代价
- 网络中断后无法实现可线性化
- 不要求线性化，服务可用
- CAP
- CAP 有时也代表一致性，可用性，分区容错性，系统只能支持其中两个特性
- 分区是一种故障，当网络通常的时候可以满足 CAP，当网络出现的问题的时候需要在 CP 和 AP 中取舍
- 可线性化与网络延迟
- 实际上很少有系统真正满足线性化
- 现代多核 CPU 的内存屏障或者 fence 指令
- 多数系统不选择可线性化是为了性能而不是容错，无论是否有网络故障，可线性化对性能的影响都是巨大的
- 顺序保证
- 顺序与因果关系
- 果关系的依赖链条定义了系统中的因果页序，即某件事应该发生另一件事情之前
- 如果系统服从因果关系所规定的顺序，我们称之为因果一致性
- 因果关系并非全序
- 可线性化
- 在一个可线性化的系统中，存在全序操作关系。系统的行为就好像只有一个数据副本，且每个操作都是原子的，这意味着对于任何两个操作，我们总是可以指出哪个操作在先
- 因果关系
- 如果两个操作都没有发生在对方之前，那么这两个操作是并发关系。换言之，如果两个事件是因果关系，那么这两个事件可以被排序;而并发的事件则无法排序比较。这表明因果关系至少可以定义为偏序，而非全序。
- 可线性化系统里不存在并发操作，一定有一个时间线可以把所有操作都全序执行。
- 并发意味着时间线出现分支和合并，而不同分支上的操作无法直接比较
- 可线性化强于因果一致性
- 可线性化一定意味着因果关系
- 线性化并非是保证因果关系的唯一途径
- 捕获因果依赖关系
- 为保持因果关系，需要知道哪个操作发生在前
- 为了确定请求的因果依赖关系，我们需要一些手段来描述系统中节点所知道的“知识”。如果节点在写入 Y 时已经看到 X 值，则 X 和 Y 可能是属于因果关系。
- 序列号排序
- 使用序列号或时间戳来排序事件
- 它可以只是一个逻辑时钟，例如采用算法来产生一个数字序列用以识别操作，通常是递增的计数器。
- 序列号很紧凑，但是他们保证了全序关系，总是可以通过比较来确定大小。
- 非因果序列发生器
- 如果系统不存在这样唯一的主节点, 如何产生序列号就不是那么简单了
- 每个节点都独立产生自己的一组序列号
- 可以把墙上时间戳信息附加到每个操作上，LLW 采用这种方式。
- 可以预先分配序列号的区间范围
- 相比于把所有请求全部压给唯一的主节点具有更好的扩展性
- 所产生的序列号与因果关系并不严格一致
- 每个节点可能有不同的处理速度
- 物理时钟的时间戳会受到时钟偏移的影响
- 对于欲分配区间，操作被路由到不同分区
- Lamport 时间戳
- 首先每个节点都有一个唯一的标识符，且每个节点都有一个计数器来记录各自已处理的请求总数。
- Lamport 时间戳是一个值对(计数器，节点 ID)。两个节点可能会有相同的计数器值，但时间戳中还包含节点 ID 信息，因此可以确保每个时间戳都是唯一的。
- 给定两个 Lamport 时间戳，计数器较大那个时间戳大;如计数器值正好相同，则节点 ID 越大，时间戳越大。
- 每个节点以及每个客户端都跟踪迄今为止所见到的最大计数器值，并在每个请求中附带该最大计数器值。当节点收到某个请求(或者回复)时，如果发现请求内嵌的最大计数器值大于节点自身的计数器值，则它立即把自己的计数器修改为该最大值
- 只要把最大计数器值嵌入到每一个请求中，该方案可以确保 Lamport 时间戳与因果关系一致，而请求的因果依赖性一定会保证后发生的请求得到更大的时间戳。
- 时间戳排序依然不够
- 全序关系广播
- 如何扩展系统的吞吐量使之突破单一主节点的限制，以及如何处理主节点失效时的故障切换，在分布式系统研究文献中，这些问题被称为全序关系广播或者原子广播
- 全序关系广播通常指节点之间交换消息的某种协议
- 可靠发送
- 没有消息丢失，如果消息发送到了某一个节点，则它一定要发送到所有节点
- 严格有序
- 全序关系广播正是数据库复制所需要的: 如果每条消息代表数据库写请求，并且每个副本都按相同的顺序处理这些写请求，那么所有副本可以保持 一致
- 可以使用全序关系广播来实现可串行化事务
- 全序关系广播的另一个要点是顺序在发送消息时已确定
- 采用全序广播实现线性化存储
- 全序关系广播是基于异步模型: 保证消息以固定的顺序可靠地发送，但是不保证消息何时发送成功
- 可线性化则强调就近性:读取时保证能够看到最新的写入值。
- 步骤
- 在日志中追加一条消息
- 广播给所有节点，等待回复
- 如果全都成功，那么返回给客户端成功的消息，否则失败
- 满足写顺序化，不满足读取顺序话
- 可以采用追加的方式把读请求排序、广播，然后各个节点获取该日志，当本节点收到消息时才执行真正的读操作
- 如果可以以线性化的方式获取当前最新日志中消息的位置，则查询位置，等待直到该位置之前的所有条目都已经发送给你，接下来再执行读取。
- 可以从同步更新的副本上进行读取，这样确保总是读取最新值。
- 采用线性化存储实现全序广播
- 假设有一个线性化的寄存器来存储一个计数，然后使其支持原子自增-读取操作或者原子比较-设置操作
- 对于每个要通过全序关系广播的消息，原子递增并读取该线性化的计数，然后将其作为序列号附加到消息中。接下来，将消息广播到所有节点，而接受者也严格按照序列化来发送回复消息
- 难点在于处理节点的网络中断，以及节点失效时如何恢复该值
- 分布式事务与共识
- 主节点选举
- 对于基于主从复制的数据库，由于网络问题出现节点之间无法通信，容易出争议。共识算法对于避免错误的故障切换非常重要。如果存在两个主节点，会导致数据不一致甚至丢失。
- 原子事务提交
- 对于支持跨节点跨区事务的数据库，事务在部分节点成功了，为了维护原子性，要么全部成功要么全部回退。
- 原子提交与两段式提交
- 单节点的原子提交
- 当客户端请求数据库节点提交事务时，数据库首先使事务的写入持久化，然后把提交记录追加写入到磁盘的日志文件中。如果数据库在该过程中间发生了崩溃，那么当节点重启后，事务可以从日志中恢复: 如果在崩溃之前提交记录已成功写入磁盘，则认为事务己安全提交;否则，回滚该事务的所有写入。
- 两阶段提交是一种在多节点之间实现事务原子提交的算法，用来确保所有节点要么全部提交，要么全部中止
- 当应用程序启动一个分布式事务时，它首先向协调者请求事务 ID。该 ID 全局唯一。
- 应用程序在每个参与节点上执行单节点事务，并将全局唯一事务 ID 附加到事务上。此时，读写都是在单节点内完成。如果在这个阶段出现问题，则协调者和其他参与者都可以安全中止。
- 当应用程序准备提交时 ，协调者向所有参与者发送准备请求 ，并附带全局事务 ID。如果准备请求有任何一个发生失败或者超时，则协调者会通知所有参与者放弃事务。
- 参与者在收到准备请求之后 ，确保在任何情况下都可以提交事务 ，包括安全地将事务数据写入磁盘，并检查是否存在冲突或约束违规。 一且向协调者回答“是”，节点就承诺会提交事务。换句话说，尽管还没有真正提交，但参与者已表态此后不会行使放弃事务的权利。
- 当协调者收到所有准备请求的答复肘，就是否提交或放弃事务要做出明确的决定。协调者把最后的决定写入到磁盘的事务日志中，防止稍后系统崩愤，并可以恢复之前的决定。这个时刻称为提交点。
- 协调者的决定写入磁盘之后 ，接下来向所有参与者发送提交或放弃请求。如果此请求出现失败或超时，则协调者必须一直重试，直到成功为止。此时，所有节点不允许有任何反悔:开弓没有回头箭，一旦做了决定，就必须贯彻执行，即使需要很多次重试。而如果有参与者在此期间出现故障，在其恢复之后，也必须继续执行。这是因为之前参与者都投票选择了“是”，对于做出的承诺同样没有反悔的余地。
- 参与者发生故障
- 在第一阶段，任何一个准备请求发生了失败或者超时，那么协调者就会决定中止事务
- 在第二阶段发生提交或中止请求失败，则协调者将无限期重试
- 协调者发生故障
- 如果协调者在发送准备请求之前就已失败，则参与者可以安全地中止事务
- 如果参与者接受了请求并做了投票是，它只能无限期等待协调者的决定。
- 部分节点没有接收到提交确认请求，在超时过后决定丢弃，导致数据不一致。
- 2PC 能够顺利完成的唯一方法就是等待协调者恢复。
- 实践中的分布式事务
- 数据库内部的分布式事务
- 异构分布式事务
- 在异构分布式事务中，存在两种或两种以上不同的参与者实现技术。例如来自不同供应商的数据库，甚至是非数据库系统
- Exactly-once 消息处理
- 异构的分布式事务旨在无缝集成多种不同的系统
- 当且仅当数据库中处理消息的事务成功提交，消息队列才会标记该消息已处理完毕
- 这个过程是通过自动提交消息确认和数据库写入来实现的。即使消息系统和数据库两种不同的技术运行在不同的节点上，采用分布式事务也能达到上述目标。
- 如果消息发送或数据库事务任何一个发生失败，则两者都须中止，消息队列可以在稍后再次重传消息。
- 只有在所有受影响的系统都使用相同的原子提交协议的前提下，这种分布式事务才是可行
- XA 事务
- 异构环境下实施两阶段提交的一个工业标准
- 协调所有实现 API 的参与者进行同一的提交或者回滚
- 停顿时仍持有锁
- 在与协调者失去连接的时间内，参与者持有的锁将不会释放，这可能导致部分上层服务崩溃
- 从协调者故障中恢复
- 协调者崩溃恢复有各种不确定情况
- 允许参与者节点可以在紧急情况下单方面做出决定，放弃或者继续那些停顿的事务，而不需要等到协调者发出指令
- 分布式事务的限制
- 协调者不支持数据复制，单点故障
- 协调者不是无状态
- XA 需要和各种数据系统兼容，无法深入不同系统的死锁条件
- 2PC 事务失败有扩大事务失败的风险
- 支持容错的共识
- 共识算法必须满足一下性质
- 协商一致性, 所有的节点都接受相同的决议。
- 诚实性，即对同一提议不能有两次决定
- 合法性，如果决定了值 v，则 v 一定是由某个节点所提议的
- 可中止性，节点不崩溃则最终一定可以达成决议
- 共识算法与全序广播
- VSR，Paxos，Raft，Zab
- 全序关系广播
- 由于协商一致性，所有节点决定以相同的顺序发送相同的消息
- 由于诚实性，消息不能重复
- 由于合法性，消息不会被破坏，也不是凭空捏造的
- 由于可终止性，消息不会丢失
- VSR，Raft 和 Zab 采用了全序关系广播，Paxos 的对应优化版本为 Multi-Paxos
- 主从复制和共识
- 一些数据库支持自动选举主节点和故障切换，通过选举把某个从节点者提升为新的主节点
- 所有的节点都需要同意主节点，否则两个主节点会导致数据库出现不一致。因此，我们需要共识算在去选出一位主节点
- Epoch 和 Quorum
- 目前所讨论的所有共识协议在其内部都使用了某种形式的主节点，虽然主节点并不是固定的。相反，他们都采用了一种弱化的保证 : 协议定义了一个世代编号(epoch number，对应于 Paxos 中的 ballot number，VSP 中 view number，以及 Raft 中的 term number)，并保证在每个世代里，主节点是唯一确定的。
- 如果当前主节点失效，节点就开始议论投票选举新的主节点。选举会赋予一个单调自增的 epoch 号。如果出现了两个不同的主节点对应不同 epoch 号码，具有更好 epoch 号码的主节点将获胜。
- 在主节点做出任何决定之前，它必须首先检查是否存在比它更高的 epoch 号码，否则就会产生冲突的决定
- 它必须从 quorum 节点中收集投票，主节点如果想要做出某个决定，须将提议发送给其他所有节点，等待 quorum 节点的响应。quorum 通常由多数节点组成。并且，只有当没有发现更高 epoch 主节点存在时，节点才会对当前的提议进行投票。
- 两轮投票
- 首先是投票决定谁是主节点，然后是对主节点的提议进行投票
- 如果某个提议获得通过，那么其中参与投票的节点中必须至少有一个也参加了最近一次的主节点选举
- 换言之，如果在针对提议的投票中没有出现更高 epoch 号码，那么可以得出这样的结论:因为没有发生更高 epoch 的主节点选举，当前的主节点地位没有改变，所以可以安全地就提议进行投票。
- 共识的局限性
- 在达成一致性决议之前，节点投票的过程是一个同步复制过程
- 共识体系需要严格的多数节点才能运行。这意味着需要至少三个节点才能容忍一个节点发生故障
- 多数共识算在是假定一组固定参与投票的节点集，这意味着不能动态、添加或删除节点
- 共识系统通常依靠超时机制来检测节点失效。在网络延迟高度不确定的环境中，特别是那些跨区域分布的系统，经常由于网络延迟的原因，导致节点错误地认为主节点发生了故障。虽然这种误判并不会损害安全属性，但频繁的主节点选举显著降低了性能，系统最终会花费更多的时间和资晾在选举主节点上而不是原本的服务任务
- 共识算法往往对网络问题特别敏感，可能导致主节点频繁切换
- 成员与协调服务
- ZK 和 etcd 通常被成为分布式键值存储或者协调与服务配置。
- ZooKeeper 和 etcd 主要针对保存少量、可完全载入内存的数据而设计。
- 特性
- 使用场景
- 节点任务分配
- 服务发现
- 把服务和 ip 注册到 ZK
- 服务发现是否需要共识存在争论，可以起到复制作用
- 成员服务
- 成员服务用来确定当前哪些节点处于活动状态并属于集群的有效成员