设计一个键值数据库,支持以下操作:
- put(key, value)
- get(key)
其中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的数据有可能过时。