DDIA-分布式存储组织

冗余

冗余（Replication） 是指将同一份数据复制多份，放到通过网络互联的多个机器上去。其可以降低延迟（就近提供服务）、提高可用性和读吞吐。

单主复制

根据请求返回时刻是否等待到副本写入完成时刻，复制分为同步（synchronously）复制和异步（asynchronously）复制。

在服务不是只读的情况下，如何不停机地复制数据到一个新副本上？

  1. 主副本在本地做一致性快照，将快照复制到从副本节点。

  2. 从主副本拉取快照之后的操作日志，应用到从副本。（根据序列号）

日志复制是怎么实现的？

在数据库中，基于领导者的多副本在不同层次有多种方法，包括：

  1. 语句层面的复制。 对于非确定性函数，同步值。

  2. 预写日志的复制。 存储引擎本身维护一个追加写入、可重放的结构WAL，天然适合备份同步。本质是因为磁盘的读写特点和网络类似：磁盘是顺序写比较高效，网络是只支持流式写。 遇到数据库版本升级的话，可以先升级从库，再切换升级主库。

  3. 逻辑日志的复制。 对于关系型数据库来说，行是一个合适的粒度。 方便新旧版本的代码兼容，并允许不同副本使用不同的存储引擎。

  4. 触发器的复制。（灵活配置）

对于一个系统来说，多副本同步的是增量修改。

主副本宕机：故障转移（failover）

首先要选出新的主副本，然后要通知所有客户端主副本变更。具体如下：

  1. 确认主副本故障。要防止由于网络抖动造成的误判。一般会用心跳探活，并设置合理超时（timeout）阈值

  2. 选择新的主副本。新的主副本可以通过选举（共识）或者指定（外部控制程序）来产生。选主时，要保证备选节点数据尽可能的新，以最小化数据损失。

  3. 让系统感知新主副本。系统其他参与方，包括从副本、客户端和旧主副本。旧主副本在恢复时，需要通过某种手段，让其知道已经失去领导权，避免脑裂（多主提供服务）。

复制滞后问题

读写一致性

（read-after-write consistency）对于单个客户端来说，就一定能够读到其所写变动，因果一致。实现可思考：

  1. 仅对于客户端可能修改的内容集，读主副本。无修改的可能性的，不限制。

  2. 可以按时间分情况讨论，在时间阈值内改动过的，读主副本。否则不限制。

  3. 客户端记录本客户端上次改动时的逻辑时间戳，判断是否必须读主副本。

单调读

image.png

读写一致性保证的是写后读顺序，单调读（Monotonic reads）保证的是多次读之间的一致。实现方案：

  1. 限定读取的副本为同一个。

  2. 逻辑时间戳比较。

一致前缀读

image.png

如果数据库由多个分区（Partition）组成，分区间的事件顺序无法保证，如果有因果关系的两个事件落在了不同分区，则有可能会出现果在前，因在后。

一致前缀读（consistent prefix reads）：对于一系列按照某顺序发生的写请求，读取这些内容时也会按照当时写入的顺序。

一种解决方案是不分区，或者可以通过识别因果关系，让所有有因果关系的事件路由到同一个分区。

多副本异步复制所带来的一致性问题，终极解决方案：事务（transaction） !

多主节点复制

单主模型存在单点问题：所有写入都要经过主节点，如果客户端无法连接到主副本，就无法向数据库写入。当系统负载超过单主的性能极限，可能需要考虑横向扩容（多主模型）。

多主复制（multi-leader replication）：有多个可以接受写入的主副本，每个主副本在接收到写入之后，都要转给所有其他副本。即一个系统，有多个写入点。适合数据库横跨多个数据中心、离线协同的场景。当然，如果两个数据中心同时修改同样的数据，必须合理解决写冲突。这比较难。

处理写冲突

有同步或者异步的方式进行冲突检测。对于单主模型，当检测到冲突时，由于只有一个主副本，可以同步的检测冲突（让第二个写入阻塞或者一直重试）。

对于多主模型，两个写入可能会在不同主副本立即成功。然后异步同步时，发现冲突，但没有办法简单决定解决冲突的方式。如果要多主间同步，退化成单主模型。

在多主模型中，很多冲突无法定序：从每个主副本来看，事件顺序是不一致的，并且没有哪个更权威一些，那么就无法让所有副本最终收敛（convergent）。

此时，我们就需要自定义一些收敛规则：

  1. 给每个写入一个序号，并且后者胜。(Last Writer Win)本质上是使用外部系统对所有事件进行定序。但可能会产生数据丢失。举个例子，对于一个账户，原有 10 元，客户端 A - 8，客户端 B - 3，任何一个单独成功都有问题。

  2. 给每个副本一个序号，序号更高的副本有更高的优先级。这也会造成低序号副本的数据丢失。

  3. 提供一种自动的合并冲突的方式。

  4. 使用程序定制一种保留所有冲突值信息的冲突解决策略。允许用户回调代码，写时执行或读时执行。

复制拓扑

复制拓扑（replication topology）描述了数据写入从一个节点到另一个节点的传播路径。下图表示了 ≥ 4 个主副本时，常见的复制拓扑：

image.png

  1. 环形拓扑。通信跳数少，但是在转发时需要带上拓扑中前驱节点信息。如果一个节点故障，则可能中断复制链路。

  2. 星型拓扑。中心节点负责接受并转发数据。如果中心节点故障，则会使得整个拓扑瘫痪。

  3. 全连接拓扑。每个主库都要把数据发给剩余主库。通信链路冗余度较高，能较好的容错。

对于环形拓扑和星型拓扑，为了防止广播风暴，需要对每个节点打上一个唯一标志（ID），在收到他人发来的自己的数据时，及时丢弃并终止传播。全连接拓扑也有自己问题：尤其是所有复制链路速度不一致时。考虑下面一个例子： image.png

可以用一种叫做版本向量（version vectors） 的策略，对多个副本的事件进行排序，解决因果一致性问题： image.png

缺点也是有的： 1. 向量版本中的[server: version]对可能会快速增长。为了解决这个问题，我们为长度设置了一个阈值，如果超过了限制，则删除最旧的对。这可能导致协调效率低下，因为后代关系无法准确确定。然而，基于Dynamo论文，亚马逊在生产中还没有遇到这个问题；因此，这可能是大多数公司可以接受的解决方案。 2. 增加了客户端的复杂性，因为它需要实现冲突解决逻辑。

无主模型

通常来说，在无主模型中，写入时可以：

  1. 由客户端直接写入副本。

  2. 由协调者（coordinator） 接收写入，转发给多副本。但与主副本不同，协调者并不负责定序。

基于主副本的模型，在有副本故障时，需要进行故障切换。在无主模型中，简单忽略它就行。在读取时，同时读取多个副本，选取最新版本的值。如果副本总数为 n，写入 w 个副本才认定写入成功，并且在查询时最少需要读取 r 个节点。只要满足 w + r > n，我们就能读到最新的数据（鸽巢原理）。此时 r 和 w 的值称为 quorum 读写。当然也存在一些corner case，如：

  1. LWW + 物理时间戳，可能由于时钟偏差造成数据丢失。

  2. 虽然写入时，成功节点数 > w，但中间有故障造成了一些副本宕机，导致成功副本数 < w，则在读取时可能会出现问题。

  3. 放松的Quorum机制；读时修复和提示转交时

  4. 对于时间间隔很短（并发）的相同 key 两个写入，不同副本上收到的顺序可能不一致。

image.png

某个节点宕机重启后，如何恢复数据？

  1. 读时修复（read repair），本质上是一种捎带修复，在读取时发现旧的就顺手修了。（with 版本ID）

  2. 反熵过程（Anti-entropy process），本质上是一种兜底修复，读时修复不可能覆盖所有过期数据，因此需要一些后台进程，持续进行扫描，寻找陈旧数据，然后更新。这个博文对该词有展开描述。

放松的 Quorum 和提示转交

可能最初选中的 n 台机器，由于种种原因（宕机、网络问题），导致无法达到法定读写数目。宽松的法定数目 （sloppy quorum）要求写和读仍然需要 w 和 r 个成功返回，但是其所在节点集合可以发生变化。（将新的写入暂时交给一些正常节点）等待其恢复上线，再回传到相应节点。

并发写入控制

LWW 有一个问题，就是多个并发写入的客户端，可能都认为自己成功了，但是最终只有一个值被保留了，其他都在后台被丢弃了。即，其迅速再读，会发现不是自己写入的数据。唯一安全的方法是：key 是一次可写，后变为只读。

Happens-before和并发关系

系统中任意的两个写入 A 和 B，只可能存在三种关系：

  1. A happens before B -> LWW

  2. B happens before A -> LWW

  3. A B 并发 -> 引入冲突解决

image.png

算法如下：

  1. 服务器为每个键分配一个版本号 V ，每次该键有写入时，将 V + 1，并将版本号与写入的值一块保存。

  2. 当客户端读取该键时，服务器将返回所有未被覆盖的值以及最新的版本号。

  3. 客户端在进行下次写入时，必须包含之前读到的版本号 Vx（说明基于哪个版本进行新的写入），并将读取的值合并到一块。

  4. 当服务器收到特定版本号 Vx 的写入时，可以用其值覆盖所有 V ≤ Vx 的值。

将该算法扩展到无主多副本模型时，只使用一个版本值显然不够，这时需要给每个副本的键都引入版本号，对于同一个键来说，不同副本的版本会构成版本向量（version vector）。跟踪从其他副本中看到的版本号，通过比较版本号大小，来决定哪些值要覆盖哪些值要保留。

分区

分区（Partition / Shard）是为了解决数据集尺度与单机容量、负载不匹配的问题，以利用多机容量和负载。

键值分区策略

  1. 按键范围（Key Range）分区 在Key的定义域内按某种维度排序。 可以进行快速的范围查询（Rang Query）， 但是可能负载倾斜，一个解决办法是分级或者混合。

  2. 按键哈希分区 选择尽量均匀的hash函数，均摊负载。 选择一致性哈希策略，易于拓展，实现半自动的增量迁移。

次级索引

次级索引（secondary index），即主键以外的列的索引；由于分区都是基于主键的，在针对有分区的数据建立次级索引时，就会遇到一些困难。

本地索引

就是对每个数据分区独立地建立次级索引，优点是维护简单，缺点是，查询效率相对较低，所有基于索引的查询请求，都要发送到所有分区，并将结果合并，该过程也称为 scatter/gather 。即使用多分区并发（而非顺序）进行索引查询优化，也仍然容易在某些机器上发生长尾请求（由于机器负载过高或者网络问题，导致写请求返回特别慢，称为长尾请求），导致整个请求过程变慢。

全局索引

即每个次级索引条目都是针对全局数据。但为了避免索引查询热点，我们会将索引数据本身也分片，分散到多个机器上。为了避免增加写入延迟，在实践中，全局索引多为异步更新。但由此会带来短暂（有时可能会比较长）的数据和索引不一致。

分区再平衡

Naive 的直接取模限制了扩展的性能，有以下方式：

静态分区

逻辑分区阶段的分区数量是固定的，并且最好让分区数以数量级别大于机器数。一般来说，可以取将来集群可能扩展到的最多节点数量作为初始分区数量。

image.png

动态分区

由于数据在定义域内并不均匀分布，如果固定分区数量，则天然地难以均衡。因此，对于按键范围进行分区的策略来说，都会支持动态分区。随着数据量不断增长，单个分区超过一定上界，则按尺寸一分为二，变成两个新的分区。

小数据量时，如果只有一个分区，会限制写入并发。因此，工程中有些数据库支持预分区（pre-splitting）

按节点比例分区

保持总分区数量和节点数量成正比，也即，保持每个节点的分区数量不变。即，当节点数增加时，分区则会调整变小。

请求路由

一个服务发现（service discovery）问题：当客户端请求到来时，我们如何决定将请求路由到哪台机器？

需要维护两层映射record -> partition -> node。三种方案：

  1. 每个节点都有全局路由表。客户端可以连接集群中任意一个节点，如该节点恰有该分区，则处理后返回；否则，根据路由信息，将其路由合适节点。

  2. 由一个专门的路由层来记录。客户端所有请求都打到路由层，路由层依据分区路由信息，将请求转发给相关节点。路由层只负责请求路由，不处理具体逻辑。

  3. 让客户端感知分区到节点映射。客户端可以直接根据该映射，向某个节点发送请求。

如何让相关组件（节点本身、路由层、客户端）及时感知（分区到节点）的映射变化，将请求正确的路由到相关节点？依赖外部协调组件（如 Zookeeper、Etcd），他们高可用、可以维护轻量的路由表，并提供发布订阅接口，在有路由信息更新时，让外部所有节点快速达成一致。

上一页DDIA-数据系统基础下一页DDIA-分布式系统服务

最后更新于

这有帮助吗？