【KV存储系统】设计核心

学习核心

• 如何设计一个【KV存储】/【缓存架构】系统？（系统的核心功能）
• 沟通对齐
  • ① 需求分析：put、get 核心API 接入，构建高可用、高性能的KV存储系统
  • ④ 难点/要点分析：支持大数据量存储、高可用、高性能、可扩展等
• 整体设计
  • ① 服务设计（分层设计）：单一服务器的键值存储（基于内存存储）、分布式键值存储（一致性哈希分布，降低单个服务节点压力）
  • ② 核心问题 & 技术方案：
    • （1）大数据存储能力支持：使用一致性哈希将负载分散到多个服务器上，采用【数据分区】避免将完整数据集集中在一个服务器上，将数据集通过分区拆分到其他服务器，一致性哈希方案也为增量可扩展性提供支持
    • （2）高可用性（读取/写入）：
      • 高可用性写入：采用向量时钟（vector clock）进行版本控制和冲突解决
      • 高可用性读取：数据复制、多数据中心设置
    • （3）一致性问题
      • 一致性：由于数据同步场景下网络故障可能导致的数据不一致性（对CAP方案的讨论）
      • 不一致解决方案：向量时钟（版本控制）
    • （4）故障处理：故障检测 & 故障场景处理
      • 故障检测：
        • all to all：服务节点过多时效率低下
        • 分散的故障检测方法（gossip协议）：引入心跳机制，每个节点维护各个节点的心跳次数，如果一段实现内发现某个节点心跳异常则进行反馈，如果反馈得到验证则标记该异常节点
      • 故障场景处理
        • 临时性故障：草率仲裁和暗示切换
        • 永久性故障：Markle 树
        • 数据中心中断：跨数据中心复制（多数据中心设置）
    • （5）读写（基于Cassandra体系结构设计）
      • 写入路径：数据写入日志（请求持久保存提交日志文件）和内存（存储数据），当内存缓存到达阈值则刷入磁盘SSTable
      • 读取路径：先判断内存中是否存在数据，如果存在则直接返回，如果不存在则经由bloom过滤器验证决定是否进一步从磁盘中获取结果集，将获取到的结果集返回给客户端
• 总结陈述

学习资料

• 【高并发架构实战课】key-value存储设计

🟢【KV存储系统】场景核心

​ 键值存储，也称为键值数据库，是一种非关系数据库。每个唯一标识符都存储为一个键及其关联值，这种数据配对称为“键值”对。在键值对中，键必须是唯一的，通过键可以访问与键关联的值。键可以是纯文本或散列值。出于性能原因，短键效果更好。键是什么样子的？

• 纯文本键："last_logged_in_at"
• 哈希键：253DDEC4

​ 键值对中的值可以是字符串、列表、对象等。在键值存储中，值通常被视为不透明的对象，如Amazon dynamo、Memcached、Redis 等

​ 此处需设计一个支持put、get操作的键值存储：

• put(key, value) // 插入与“key”关联的“value”
• get(key) // 获取与“key”关联的“value”

🚀【xx系统】场景实战

1.沟通对齐

​ 此处的沟通对齐方向，主核心方向是需求分析、请求量分析、精准度分析、难点/要点分析，可能还有涉及到其他的一些容量、设计等方面的对齐

① 需求分析

【KV存储】系统核心功能

​ 要设计一个支持KV存储的系统，首先需要梳理键值存储的特征，可以从以下几个方面切入：

• 键值对大小：不到10KB
• 大数据存储能力支持：支持存储大数据
• 高可用性：系统响应迅速，即使出现故障时也能够及时反馈
• 高可扩展性：系统可以扩展支持大数据集
• 自动缩放：服务器的添加/删除应该根据流量自动进行
• 可调节的一致性
• 低延迟

业务流程分析

② 请求量分析

③ 精准度分析

④ 难点/要点分析

2.整体设计（架构设计）

① 服务设计（分层设计）

（1）单一服务器的键值存储（内存存储）

​ 开发一个驻扎在单个服务器中的键值存储很容易，一种直观的方法是将键值对存储在哈希表中，该哈希表将所有内容保存在内存中。为了在一个服务器中容纳更多的数据，可以做两个优化措施：

• 数据压缩
• 只在内存中存储经常使用的数据，其余的存储在磁盘上

​ 即使进行了这些优化，单个服务器也可以很快达到其容量。因此需要分布式键值存储来支持大数据

（2）分布式键值存储

​ 分布式键值存储也称为分布式哈希表，它将键值对分布在许多服务器上。在设计分布式系统时，了解 CAP（C一致性、A可用性、P分区容错性）定理很重要。

​ CAP 定理指出，分布式系统不可能同时提供以下三种保证中的两种以上：一致性（Consistency）、可用性（Availability）和分区容错性（Partition Tolerance）

• 一致性：一致性意味着所有客户端无论连接到哪个节点，都在同一时间看到相同的数据

• 可用性：可用性意味着即使某些节点已关闭，任何请求数据的客户端都会得到响应

• 分区容忍度：分区表示两个节点之间的通信中断，分区容错意味着系统在网络分区的情况下继续运行

CAP 定理指出，必须牺牲三个属性之一来支持 3 个属性中的 2 个：

• （CP）一致性和分区容错系统：CP 键值存储在牺牲可用性的同时支持一致性和分区容错
• （AP）可用性和分区容错系统：AP 键值存储支持可用性和分区容错，同时牺牲一致性
• （CA）一致性和可用性系统 ❌：CA 键值存储支持一致性和可用性，同时牺牲分区容错性。由于网络故障是不可避免的，分布式系统必须容忍网络分区。因此，CA 系统不能存在于现实世界的应用程序中

​ 上述内容分析趋于理论定义，此处结合场景案例分析理解各个特性：在分布式系统中，数据通常会被复制多次。假设数据被复制到三个副本节点n1、n2和n3上

​ 理想情况：理想世界中设定网络分区永远不会发生，写入n1的数据会自动复制到n2、n3，进而实现了一致性和可用性

​ 真实世界：在分布式系统场景中，分区是不可避免的。当出现分区时，必须在一致性和可用性之间做出选择.。结合下图所示分析，如果n3宕机，则无法与n1、n2进行通信，如果此时有新的数据写入n1、n2，那么该数据无法传播到n3；同理，如果此时有新的数据更新至n3，但此时无法传播至n1、n2，就会导致n1、n2存在旧数据没有得到更新

​ 基于上述分析，如果要确保分区容错，则必须牺牲掉C、A中的其中一个，下述讨论方案选择：

• 如果选择CP（一致性和分区容错），则必须阻止所有对n1和n2的写操作，以避免这三个服务器之间的数据不一致，这使得系统不可用（也就是牺牲了A可用性）
  • 对于金融场景来说（银行系统），其通常有极高的一致性要求。例如，对于银行系统来说，显示最新的余额信息是至关重要的。如果由于网络分区而发生不一致，在不一致问题解决之前，银行系统会返回一个错误
• 如果选择AP（可用性和分区容错），对于【读操作】系统会一直接受读取（即使可能会返回旧数据），对于【写操作】n1、n2将会继续接受写，待网络分区解决之后数据会被同步到n3

​ 基于上述讨论，选择正确的CAP模式是构建分布式键值存储的重要步骤

② 存储设计（存储选型）

③ 业务设计（业务流程）

3.要点分析

​ 基于三个流行的键值存储系统（Dynamo、Cassandra、BigTable ）进一步讨论构建键值存储的核心组件和技术：

• 数据处理：数据分区 & 数据复制
• 一致性：一致性 & 不一致解决方案
• 故障处理：故障检测 & 故障处理
• 系统架构图
• 读写：写入路径 & 读取路径

① 数据处理：数据分区 & 数据复制

（1）数据分区

对于大型应用程序，将完整的数据集放在单个服务器中是不可行的。实现这一点的最简单方法是将数据拆分为更小的分区并将它们存储在多个服务器中。分区数据时有两个挑战：

• 跨多个服务器平均分配数据
• 当节点被添加或删除时，尽量减少数据移动

​ 一致性哈希是解决这些问题的一种很好的技术，理解一致性哈希在高层次上的工作原理：

​ 首先，服务器被放置在哈希环上。结合图示分析，共有 8 个服务器节点，分别用 s0、s1、...、s7 表示，放在哈希环上。接下来，将一个键散列到同一个环上，并将其存储在顺时针方向移动时遇到的第一个服务器上。例如，key0 使用此逻辑会被存储在 s1 中

​ 使用一致性哈希对数据进行分区有以下优点：

• 自动缩放：可以根据负载自动添加和删除服务器
• 异构性：服务器的虚拟节点数与服务器容量成正比。例如，容量越大的服务器分配的虚拟节点越多

（2）数据复制

​ 为了实现高可用性和可靠性，必须在 N 个服务器上异步复制数据，其中 N 是一个可配置参数。这N台服务器的选择逻辑如下：将key映射到哈希环上的某个位置后，从该位置顺时针走，选择环上的前N台服务器存储数据副本。如下图示（N = 3）中，key0 被复制到 s1、s2 和 s3

​ 对于虚拟节点，环上的前 N 个节点可能由少于 N 个物理服务器拥有。为避免此问题，在执行顺时针行走逻辑时仅选择唯一的服务器

​ 由于停电、网络问题、自然灾害等原因，同一数据中心内的节点经常同时发生故障。为了更好的可靠性，副本被放置在不同的数据中心，数据中心之间通过高速网络连接

② 一致性：一致性 & 不一致解决方案

（1）一致性

​ 由于数据在多个节点进行复制，因此必须跨副本同步。Quorum 共识可以保证读写操作的一致性，先理解几个定义：

• N = 副本数
• W = 大小为 W 的规定写入。要将写入操作视为成功，必须从 W 个副本确认写入操作
• R = 大小为 R 的读取规定人数。为了使读取操作被认为是成功的，读取操作必须等待至少R个副本的响应

​ 结合图示分析（其中 N = 3，ACK 表示 acknowledgement）

​ 此处【协调器充当客户端和节点之间的代理】，W=1 并不意味着数据写在一台服务器上。 结合上述图示配置分析，数据被复制到 s0、s1 和 s2。 W = 1 表示协调器必须至少收到一个确认才能认为写操作成功。例如，如果收到来自 s1 的确认，就不再需要等待来自 s0 和 s2 的确认

​ W、R和N的配置是一个典型的延迟和一致性之间的权衡

• 如果 W = 1 或 R = 1，操作会很快返回，因为协调器只需要等待来自一个副本的写/读响应
• 如果 W 或 R > 1，系统提供更好的一致性； 但是，查询会变慢，因为协调器必须等待最慢副本的响应
• 如果 W+R>N，就能保证强一致性，因为至少有一个重叠的节点拥有最新的数据，以保证一致性

​ 基于上述分析，则可通过设定不同的W R N组合配置来适应应用场景，以达到理想的一致性水平

• 如果R=1，W=N，系统被优化为快速读取
• 如果W=1，R=N，系统被优化为快速写入
• 如果W+R>N，就可以保证强一致性（通常N=3，W=R=2）。
• 如果W+R<=N，则不能保证强一致性

一致性模型

一致性模型是设计键值存储时要考虑的另一个重要因素。 一致性模型定义了数据一致性的程度，并且存在多种可能的一致性模型：

• 强一致性：任何读操作都会返回一个与最新的写数据项的结果相对应的值（客户端永远不会看到过期的数据）
• 弱一致性：后续的读操作可能看不到最新的值
• 最终一致性：这是弱一致性的一种特殊形式。只要有足够的时间，所有的更新都会被传播，而且最终所有的副本都是一致的

​ 强一致性通常是通过强迫一个副本不接受新的读/写，直到每个副本都同意当前的写来实现的。这种方法对于高可用系统来说并不理想，因为它可能会阻塞新的操作。Dynamo和Cassandra采用最终一致性，这是我们推荐的键值存储的一致性模型。

​ 从并发写入来看，最终一致性允许不一致的值进入系统，并迫使客户端读取这些值来进行调和

（2）不一致解决方案：版本控制

​ 问题切入：数据复制提供了高可用性，但会导致副本之间的不一致。 版本控制和矢量锁用于解决不一致问题。版本化意味着将每一次数据修改都视为一个新的不可更改的数据版本

不一致场景分析

① n1、n2节点副本值相同（原始值），server1、server2分别通过get操作可以获取相同的值

② server1、server2分别通过put操作同时更新name属性，此时出现两个与原始值不同的版本v1、v2（冲突值）

​ 基于此示例，可以忽略原始值，因为修改是基于它的。 但是，没有明确的方法来解决最后两个版本的冲突。 为了解决这个问题，需要一个可以检测冲突并协调冲突的版本控制系统

检测、协调冲突的版本控制系统：向量时钟

​ 向量时钟是与数据项关联的键值 [server, version] 对， 它可用于检查一个版本是否先于、成功或与其他版本冲突。假设一个向量时钟用 D([S1, v1], [S2, v2], ..., [Sn, vn]) 表示，其中 D 是数据项，v1 是版本计数器，s1 是服务器数字等。如果数据项 D 被写入服务器 Si，系统必须执行以下任务之一：

• 如果 [Si, vi] 存在，则增加 vi
• 否则，创建一个新的条目[Si, 1]

​ 结合图示理解分析（此处客户端向系统写入数据，其是经由某个服务器处理，下述简化术语表达）：可以理解为如果服务关联版本存在则版本加1，如果不存在则新建条目，请求由哪个服务处理就新增/更新哪个条目

• ① 客户端写入数据经由服务器Sx处理，Sx写入数据D1，新增了一个新的条目D1([Sx,1])
• ② 另一个客户端读取D1并更新为D2并写回（D2继承D1因此会覆盖D1），写入数据经由服务器Sx处理，将其更新为数据D2，此时更新版本得到D2([Sx,2])
• ③ 另一个客户端读取最新的D2将其更新为D3并写回，写入数据经由服务器Sy处理，得到向量时钟为D3([Sx,2],[Sy,1])（因为[Sy,Vi]不存在，因此创建一个新的条目）
• ④ 同理，另一个客户端同时读取最新的D2将其更新为D4并写回，写入数据经由服务器Sz处理，得到向量时钟为D4([Sx,2],[Sz,1])（因为[Sz,Vi]不存在，因此创建一个新的条目）
• ⑤ 当另一个客户端读取D3、D4的时候会发现版本冲突（这是由于数据项D2同时被Sy、Sz修改导致），冲突由客户端解决，并将更新的数据发送到服务器。 假设写入由 Sx 处理，它现在有向量时钟 D5([Sx, 3], [Sy, 1], [Sz, 1])（因为[Sx,Vi]已存在则版本+1）

​

​ 向量时钟的冲突检测分析：校验两个版本是上下级（祖先）/ 平级（兄弟）关系，则通过版本中每个参与者（服务器）版本的对应版本比较分情况讨论

• ① 如果Y的向量时钟中的每个参与者的版本计数器大于或等于版本X中的版本计数器，则很容易判断版本X是版本Y的祖先（即无冲突）Y 均 大于 X，则 X 是 Y 的祖先

  • 例如 向量时钟 D([s0, 1], [s1, 1])] 是 D([s0, 1], [s1, 2]) 的祖先。因此，未记录任何冲突。

• ② 如果 Y 的向量时钟中有任何参与者的计数器小于其在 X 中对应的计数器，则可以判断版本 X 是 Y 的兄弟版本（即存在冲突）Y 中存在 小于 X，则 X 是 Y 的兄弟

  • 例如，以下两个矢量时钟表示存在冲突：D([s0, 1], [s1,2]) 和 D([s0, 2], [s1, 1])

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

③ 故障处理：故障检测 & 故障处理

（1）故障检测

​ 在分布式系统中，仅因为另一台服务器这样说就认为一台服务器已宕机是不够的。 通常，至少需要两个独立的信息源才能将服务器标记为宕机

① all-to-all 多播是一种直接的解决方案（但是，当系统中有很多服务器时，这是低效的）

② 采用分散的故障检测方法（例如gossip协议），其工作原理分析如下：

• 每个节点维护一个节点成员列表，其中包含成员ID和心跳计数器
• 每个节点定期增加它的心跳计数器
• 每个节点定期向一组随机节点发送心跳，然后再传播到另一组节点上
• 一旦节点收到心跳，成员名单就会更新到最新信息
• 如果心跳没有增加，且超过预定的时间，该成员被认为是离线的

​ 结合上图示分析，理解其工作原理：

• ① 节点s0维护一个节点成员列表（记录了每个节点的心跳计数和更新时间）
• ② 但在某个时间段内，节点s0注意到节点s2（成员ID=2）的心跳计数器很长时间没有增加
• ③ 于是节点s0向一组随机节点发送信息（包括s2的信息和心跳），一旦其他节点确认s2的心跳计数器长时间没有更新，节点s2就会被标记下来，这个信息会传播给其他节点

（2）故障处理

⚽ 处理暂时性故障：提示切换

​ 通过gossip协议检测到故障后，系统需要部署一定的机制来确保可用性。 在严格的仲裁方法(quorum)中，读取和写入操作可以被阻止，如仲裁共识部分所示。

​ 一种称为“草率仲裁(sloppy quorum)”的技术用于提高可用性。 系统不会强制执行法定人数要求，而是选择前 W 个健康的服务器进行写入，并选择前 R 个健康的服务器进行哈希环上的读取（离线服务器将被忽略）

​ 如果由于网络或服务器故障导致服务器不可用，将由另一台服务器临时处理请求，当宕机服务器启动时，更改将被推回以实现数据一致性。这个过程称为暗示切换（hinted handof）。结合下图示分析s2不可用，读写暂时交由s3处理，当 s2 重新上线时，s3 会将数据交还给 s2

⚽ 处理永久性故障：反熵协议

​ 提示切换用于处理临时故障，但如果副本永久不可用怎么办？ =》为了处理这种情况，实施了一个反熵协议（anti-entropy protocol） 来保持副本同步。 反熵需要比较副本上的每条数据，并将每个副本更新为最新版本

​ Merkle树用于检测不一致，并尽量减少传输的数据量（哈希树或 Merkle 树是一棵树，其中每个非叶节点都标有其子节点的标签或值（如果是叶子）的哈希值。 哈希树允许对大型数据结构的内容进行高效和安全的验证）

Merkle 树的构建（突出显示的框表示不一致）

① 第1步（划分桶）：将key空间划分为桶（案例设定为4个）， 一个桶被用作根级节点，以保持树的有限深度

② 第2步（散列桶数据）：一旦创建了桶，使用统一的散列方法对桶中的每个key进行散列

③ 第3步（为桶创建哈希节点）：

④ 第4步（建树：计算子代哈希值，向上建树）：通过计算子代的哈希值，向上建立树，直到根

​ 要比较两个Merkle树，首先要比较根哈希值：

• 如果根哈希值匹配，则两个服务器有相同的数据
• 如果根哈希值不一致，那么就比较左边的子哈希值，然后是右边的子哈希值。可以遍历该树，找到哪些桶没有被同步，并只同步这些桶。

​ 使用Merkle树，需要同步的数据量与两个副本之间的差异成正比，而不是它们包含的数据量。在现实世界的系统中，桶的大小是相当大的。例如，一个可能的配置是每十亿个键有一百万个桶，所以每个桶只包含1000个键

⚽处理数据中心的中断故障：多数据中心备份

​ 数据中心的中断可能是由于停电、网络中断、自然灾害等原因造成的。为了建立一个能够处理数据中心中断的系统，在多个数据中心之间复制数据是非常重要的。即使一个数据中心完全离线，用户仍然可以通过其他数据中心访问数据

④ 系统架构图

​ 基于上述讨论，分析了键值存储的不同技术考虑，可进一步分析其核心架构图：

• ① 操作：客户端通过简单的API（get、put）与键值存储进行通信
• ② 协调器（coordinator）：协调器是一个节点，在客户端和键值存储之间充当代理
• ③ 数据分布：节点采用一致性hash的散列方式分布在一个环上
• ④ 去中心化：该系统是完全去中心化的，所以添加和移动节点可以自动进行
• ⑤ 数据复制：数据在多个节点上复制
• ⑥ 高可用：不存在单点故障，因为每个节点都有相同的职责（每个节点执行许多任务）

⑤ 读写：写入路径 & 读取路径

​ 写/读路径设计参考是基于Cassandra的体系结构，下图示分析解释了将写/读请求定向到特定的节点之后的流程

（1）写入路径

【写入路径】分析

• ① 写入请求持久保存在提交日志文件中
• ② 数据保存在内存缓存中
• ③ 当内存缓存已满或达到预定义的阈值时，数据将刷新到磁盘上的 SSTable（注意：排序字符串表 (SSTable) 是 <key, value> 对的排序列表）

（2）读取路径

【读取路径】分析

​ 当读取请求被引导到一个特定的节点后，它首先检查数据是否在内存缓存中。如果是，数据就会被返回给客户端；如果数据不在内存中，就会从磁盘中检索出来

​ 因此需要一个有效的方法来找出哪个SSTable中包含了该键，布隆过滤器则是通常被用来解决这个问题：

• ① 系统先检查数据是否在内存中，如果不存在于内存则跳转步骤②
• ② 如果数据不在内存中则系统先检查Bloom过滤器
• ③ Bloom过滤器会计算哪些SSTables可能包含key
• ④ SSTables 返回数据集的结果
• ⑤ 数据集的结果被返回客户端

4.总结陈述

• 深刻总结
• 要点牵引
• 收尾请教

​ 基于上述讨论，KV存储的应用API设计是比较纯粹的，但是为了支持KV存储系统的高可用、高性能，其中则涵盖了很多技术组件的组合应用，结合上述分析可进一步掌握分布式键值存储的特点和相应的技术实现，总结分析如下：

目标/问题	技术
大数据存储	使用一致性哈希将负载分散到多个服务器上
高可用（写入、读取）	① 高可用写入：使用向量时钟（vector clocks）进行版本控制和冲突解决 ② 高可用读取：数据复制、多数据中心设置
数据分区	一致性哈希（避免将完整的数据集放在单个服务器中，将数据拆分为更小的分区并存储在多个服务器中）
增量可扩展性	一致性哈希
异质性（heterogeneity）	一致性哈希
故障处理	① 处理临时性故障：草率仲裁（sloppy quorum）和暗示切换（hinted handoff） ② 处理永久性故障：Merkle 树 ③ 处理数据中心中断：多数据中心设置（跨数据中心复制）

🚀实战案例