设计一个键值数据库,支持以下操作:
其中key是唯一的,value可以是任何类型。
理解题意,确定设计范围
这里以满足以下要求为例设计键值数据库:
- 每个键值对大小不超过10KB
- 能够存储海量的键值对
- 高可用性:响应迅速,即使服务端出现错误
- 高可扩展性:可扩展以支持海量数据
- 自动扩展:可根据流量自动增加或删除服务器
- 可调整的数据一致性
- 低延迟
单服务器的键值数据库
单服务器的设计比较简单,使用一个大的哈希表即可,所有数据存储在内存中。由于内存不可能无限大,所以要进行优化,比如使用数据压缩技术,或是将不常使用的数据存储到磁盘。
即使应用优化措施,单服务器也难以应对海量数据的存储,必须要使用分布式设计来支持海量数据。
分布式键值数据库
也称为分布式哈希表,使用分布式环境来存储键值。设计分布式系统时,需要了解CAP原则。CAP是指一致性(Consistency)、可用性(Availability)、部分容错性(Partition Tolerance)。
CAP原则描述的是一个分布式系统最多只能同时满足CAP中的两项,不可能同时满足三项。根据侧重点的不同,分布系统可以有以下几种类型:
CP系统:满足一致性和部分容错能力,以牺牲可用性为代价。
AP系统:满足可用性和部分容错能力,以牺牲一致性为代价。
CA系统:满足一致性和可用性,不支持部分容错。因为现实环境中系统总有可能出现异常情况,所以这种系统在现实世界不并不存在。
以下面的分布式系统为例,这里有n1~n3三个结点,数据需要同时在n1~n3上复制存储:
理想情况下,网络分区(network partiton)不会发生。写向n1的数据可以自动复制到n2和n3,一致性和可用性都能满足。
现实场景中,网络分区无法避免,当某个结点发生网络分区时(并不一定是宕机和停止服务,也可能只是单纯因为网络问题导致与其他结点无法通信,而结点本身仍然是处于正常状态的),系统必须在高可用性和高一致性之间作出选择,这里以n3出现故障为例进行说明:
当n3出现故障时,如果客户端写n1和n2,那么数据不能被同步到n3,如果客户端写n3,那n1和n2无法从n3同步数据,即n1和n2的数据有可能过时。
如果系统优先考虑一致性,那当n3出现故障后,系统应该立即停止任何对n1和n2的写操作,以避免数据不一致,这就导致可用性无法满足。
如果系统优先考虑可用性,则n3出现故障后,n1和n2仍旧可供读写,但数据有可能是过时的,这就导致一致性无法满足。
应该根据实际应用场景来选择合适的CAP策略。
系统组件
讨论分布式键值数据库的核心组件:
- 数据分区
- 数据复制
- 一致性
- 非一致性问题处理
- 容错处理
- 系统架构图
- 写过程
- 读过程
数据分区
指的是将数据拆分成几部分存储在不同的服务器上,因为单个的服务器无法满足存储海量数据的需求。数据拆分有以下几项挑战:
- 将数据平均分布到各个服务器
- 在增加或删除服务器时,尽量减少数据的移动
前一章节讨论的一致性哈希可用于解决上述问题,这里简要描述一下过程:
- 服务器按哈希值映射到哈希环上,下面的例子包含s0~s7共8个服务器
- 将key也按相同的哈希算法映射到哈希环上,并将数据存储在顺时钟方向上第一个相邻的服务器,这里key0存储在s1中。
根据负载情况,服务器可自动增加或删除。可按服务器的存储能力比例分配虚拟结点的数量,比如大容量的服务器可分配较多的虚拟结点。
数据复制
为提高可用性和可靠性,数据一般会通过异步复制技术存储在N台服务器上,N是一个可配置的参数。这里的N台服务器可以用下面的方式来选择:
- 当把key映射到哈希环上后,按顺时针方向选择前N个服务器进行存储,比如在下面的示例中,N=3,key0被存储在s1,s2,s3中。
如果使用了虚拟结点,则在选择前N个服务器时应跳过属于同一个服务器的虚拟结点。
一致性
数据在多个结点之间复制时必须保证同步。Quorum机制(参考Quorum (分布式系统) - 维基百科,自由的百科全书)可用于保证在读写时的一致性。以下是一些相关的定义:
N
= 复制数
W
= 写票数,写操作需要至少收到W份写成功的响应才算写成功
R
= 读票数,读操作需要至少收到R份读成功的响应才算写成功
以下面的示例来说明Quorum机制,这里N = 3。
W = 1并不是表示数据只会存储在一个服务器上,而是指在写s0~s2时,只要收到至少一个写成功的响应,就认为已写入成功,换句话说,数据有可能在s0~s2上都写成功了,但只要收到了其中一个的响应,写操作就会成功返回,而不再等待另外两个结点的响应。
对W, R, N的配置决定了系统的响应延迟和数据一致性。如果W=1或N=1,则任何读写操作都会快速返回,因为只要收到1个成功响应就认为操作成功。如果W或R大于1,则响应会慢一些,因为要等多个结点响应操作成功,但一致性会更好。
如果W + R > N, 则系统有较强的一致性,因为可以保证系统至少有一个重叠的结点存储的数据是最新的。以下是一些可能的W,N, R配置及其效果:
- 如果R = 1并且W = N,则系统优化为支持快速读取。
- 如果W = 1并且 R = N,则系统优化为支持快速写入。
- 如果W + R > N,则系统保证了较强的一致性(通常是N=3, W = R = 2)。
- 如果 W + R < N,则系统并不保证强一致性。
根据实际场景,可灵活配置W,R,N以适应需求。
关于一致性模型:
强一致性:总是保持所有数据最新,客户端不会读到过时数据
弱一致性:客户端有可能读到过时的数据
最终一致性:客户端有可能读到过时数据,但给予系统足够的时间,所有数据会最终同步到最新
强一致性一般是通过在更新数据之前屏蔽所有的读写操作来实现的,不适合高可用性系统。如果使用最终一致性模型,则客户端有可能读到两份不同的数据,这里需要由客户端处理冲突。
非一致性问题处理:版本管理
数据复制在提供了高可用性的同时也导致了数据在各备份结点不一致的问题,版本管理和向量时钟算法(vector clock)可用于解决该问题。版本管理的意思是把每次对数据的修改当成一个新的版本来对待,而向量时钟算法则是一种生产版本信息和判断判断冲突的算法,参考vector clock向量时钟算法简介 - 简书。
容错
错误检测
处理临时错误
处理永久错误
处理数据中心宕机
系统架构设计