【系统设计】分布式键值数据库

目录

  设计要求  

  单机版 - 键值存储  

  分布式 - 键值存储  

  CAP 定理  

  核心组件和技术  

  数据分区  

  数据复制  

  一致性  

  一致性模型  

  不一致的解决方案：版本控制  

  故障处理  

  故障检测  

  处理临时故障  

  处理长时间故障  

  系统架构图  

  写入流程  

  读取流程  

  Reference  

键值存储 ( key-value store )，也称为 K/V 存储或键值数据库，这是一种非关系型数据库。每个值都有一个唯一的 key 关联，也就是我们常说的 键值对。

常见的键值存储有 Redis, Amazon DynamoDB，Microsoft Azure Cosmos DB，Memcached，etcd 等。

你可以在 DB-Engines 网站上看到键值存储的排行。

  设计要求  

在这个面试的系统设计环节中，我们需要设计一个键值存储， 要满足下面的几个要求

• • 每个键值的数据小于 10kB。

• • 有存储大数据的能力。

• • 高可用，高扩展性，低延迟。

  单机版 - 键值存储  

对于单个服务器来说，开发一个键值存储相对来说会比较简单，一种简单的做法是，把键值都存储在内存中的哈希表中，这样查询速度非常快。但是，由于内存的限制，把所有的数据放到内存中明显是行不通的。

所以，对于热点数据（经常访问的数据）可以加载到内存中，而其他的数据可以存储在磁盘。但是，当数据量比较大时，单个服务器仍然会很快达到容量瓶颈。

  分布式 - 键值存储  

分布式键值存储也叫分布式哈希表，把键值分布在多台服务器上。在设计分布式系统时，理解 CAP（一致性，可用性，分区容错性） 定理很重要。

  CAP 定理  

CAP 定理指出，在分布式系统中，不可能同时满足一致性、可用性和分区容错性。让我们认识一下这三个定义：

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

• • 可用性：可用性意味着任何请求数据的客户端都会得到响应，即使某些节点因故障下线。

• • 分区容错性：分区表示两个节点之间的网络通信中断。分区容错性意味着，当存在网络分区时，系统仍然可以继续运行。

通常可以用 CAP 的两个特性对键值存储进行分类：

CP（一致性和分区容错性）系统：牺牲可用性的同时支持一致性和分区容错。

AP（可用性和分区容错性）系统：牺牲一致性的同时支持可用性和分区容错。

CA（一致性和可用性）系统：牺牲分区容错性的同时支持一致性和可用性。

由于网络故障是不可避免的，所以在分布式系统中，必须容忍网络分区。

让我们看一些具体的例子，在分布式系统中，为了保证高可用，数据通常会在多个系统中进行复制。假设数据在三个节点 n1, n2, n3 进行复制，如下：

理想情况

在理想的情况下，网络分区永远不会发生。写入 n1 的数据会自动复制到 n2 和 n3，实现了一致性和可用性。

现实世界的分布式系统

在分布式系统中，网络分区是无法避免的，当发生分区时，我们必须在一致性和可用性之间做出选择。

在下图中，n3 出现了故障，无法和 n1 和 n2 通信，如果客户端把数据写入 n1 或 n2，就没办法复制到 n3，就会出现数据不一致的情况。

如果我们选择一致性优先（CP系统），当 n3 故障时， 就必须阻止所有对 n1 和 n2 的写操作，避免三个节点之间的数据不一致。涉及到钱的系统通常有极高的一致性要求。

如果我们选择可用性优先（AP系统），当 n3 故障时，系统仍然可以正常的写入读取，但是可能会返回旧的数据，当网络分区恢复后，数据再同步到 n3 节点。

选择合适的 CAP 是构建分布式键值存储的重要一环。

  核心组件和技术  

接下来，我们会讨论构建键值存储的核心组件和技术：

• • 数据分区

• • 数据复制

• • 一致性

• • 不一致时的解决方案

• • 故障处理

• • 系统架构图

• • 数据写入和读取流程

  数据分区  

在数据量比较大场景中，把数据都存放在单个服务器明显是不可行的，我们可以进行数据分区，然后保存到多个服务器中。

需要考虑到的是，多个服务器之间的数据应该是均匀分布的，在添加或者删除节点时，需要移动的数据应该尽量少。

一致性哈希非常适合在这个场景中使用，下面的例子中，8台服务器被映射到哈希环上，然后我们把键值的 key 也通过哈希算法映射到环上，然后找到顺时针方向遇到的第一个服务器，并进行数据存储。

使用一致性哈希，在添加和删除节点时，只需要移动很少的一部分数据。

  数据复制  

为了实现高可用性和可靠性，一条数据在某个节点写入后，会复制到其他的节点，也就是我们常说的多副本。

那么问题来了，如果我们有 8 个节点，一条数据需要在每个节点上都存储吗？

并不是，副本数和节点数没有直接关系。副本数应该是一个可配置的参数，假如副本数为 3，同样可以借助一致性哈希环，按照顺时针找到 3 个节点，并进行存储，如下

  一致性  

因为键值数据在多个节点上复制，所以我们必须要考虑到数据一致性问题。

Quorum 共识算法可以保证读写操作的一致性，我们先看一下 Quorum 算法中 NWR 的定义。

N = 副本数, 也叫复制因子，在分布式系统中，表示同一条数据有多少个副本。

W = 写一致性级别，表示一个写入操作，需要等待几个节点的写入后才算成功。

R = 读一致性级别，表示读取一个数据时，需要同时读取几个副本数，然后取最新的数据。

如下图，N = 3

注意，W = 1 并不意味着数据只写到一个节点，控制写入几个节点的是 N 副本数。

N = 3 表示，一条数据会写入到 3 个节点，W = 1 表示，只要收到任何节点的第一个写入成功确认消息（ACK）后，就直接返回写入成功。

这里的重点是，对 N、W、R的值进行不同的组合时，会产生不同的一致性效果。

• • 当 W + R > N 的时候，通常是 N = 3, W = R = 2，对于客户端来讲，整个系统能保证强一致性，一定能返回更新后的那份数据。

• • 当 W + R