设计一个键值数据库，支持以下操作：

• 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的数据有可能过时。