Question

键 - 值存储（Key-value store）是数据库的一种。在云计算愈发流行的今天，键 - 值存储正在受到越来越多的关注。以关系型数据库管理系统（RDBMS）为代表的现有数据库系统正接近其极限，而键 - 值存储则拥有超越这种极限的可能性。

键 - 值存储是通过由键对象到值对象的映像来保存数据的，具体原理我们稍后会详细讲解。

例如，旅游预订网站“乐天旅游”¹中可以显示“最近浏览过的酒店”，其数据中，键为“用户 ID”，值为“酒店 ID（多个）”，即通过和用户 ID 相关联，来保存用户浏览过的酒店 ID。

^{1 乐天旅游（楽天トラベル）：}http://travel.rakuten.co.jp/

对于熟悉 Ruby 的读者，可以将这种方式理解为和 Ruby 内建的 Hash 类具有相同的功能。但不同的是，Hash 只能存在于内存中，而键 - 值存储是数据库，因此它具备将数据永久保存下来的能力。

使用键 - 值存储方式的数据库，大多数都在数据查找技术上使用了散列表这种数据结构。散列表是通过调用散列函数来生成由键到散列值（一个和原始数据一一对应的固定位数的数值）的映射，通过散列值来确定数据的存放位置。散列表中的数据量无论如何增大，其查找数据所需的时间几乎是固定不变的，因此是一种非常适合大规模数据的技术。

要讲解键 - 值存储，我们先从它的基本工作方式 Hash 开始讲起吧。

Hash 类

一般意义上说，Hash（散列表）指的是通过创建键和值的配对，由键快速找到值的一种数据结构。

作为例子，我们来看一看 Ruby 的 Hash 类。该类拥有 147 种方法，不过其本质可以通过下列 3 个方法来描述。

hash[key] hash[key] = value hash.each {|k,v| ...}

hash[key] 方法用于从 Hash 中取出并返回与 key 对象相对应的 value 对象。当找不到与 key 相对应的对象时，则返回 nil。hash[key] = value 方法用于将与 key 对象相对应的 value 对象存放到 Hash 中。当已经存在与 key 相对应的对象时，则用 value 覆盖它。最后是 hash.each 方法，用于按顺序遍历 Hash 中的键 - 值对。

也就是说，Hash 对象是用于保存 key 对象到 value 对象之间对应关系的数据结构。这种数据结构在其他编程语言中有时也被称为 Map（映像）或者 Dictionary（字典）。我觉得用字典这个概念来描述 Hash 的性质挺合适的，因为字典就是从一个词条查询其对应释义的工具。

DBM 类

Hash 类中的数据只能存在于内存中，在程序运行结束之后就会消失。为了超越进程的范围保存数据，可以使用 Ruby 的“DBM”类这样的键 - 值存储方式。

DBM 类的用法和 Hash 几乎一模一样，但也有以下这些区别：

· key 和 value 只能使用字符串。

· 创建新 DBM 对象时，需要指定用于存放数据的文件路径名称。

· 数据会被保存在文件中。

像这样，可以超越进程的范围来保存数据的特性，在编程的世界中被称为“永久性”（persistence）。

数据库的 ACID 特性

下面我们来分析一下“为什么在云计算时代键 - 值存储模型会受到关注”。

问题的关键在于 RDBMS 数据库所具备的 ACID 这一性质，我们就从这里开始讲起。ACID 是 4 个单词首字母的缩写，它们分别是：Atomicity（原子性）、Consistency（一致性）、Isolation（隔离性）和 Durability（持久性）。

所谓 Atomicity，是指对于数据的操作只允许“全部完成”或“完全未做改变”这两种状态中的一种，而不允许任何中间状态。因为操作无法进一步进行分割，所以用了“原子”这个词来表现。例如，银行在进行汇款操作的时候，要从 A 账户向 B 账户汇款 1 万元，假设当中由于某些原因发生中断，这时 A 账户已经扣掉 1 万元，而 B 账户中还没有存入这 1 万元，这就是一个中间状态。

“从 A 账户余额中扣掉 1 万元”和“向 B 账户余额中增加 1 万元”这两个操作，如果只完成了其中一个的话，两个账户的余额就会发生矛盾。

所谓 Consistency，是指数据库的状态必须永远满足给定的条件这一性质。例如，当给定“存款账户余额永远为正数”这一条件时，“取出大于账户余额的款项”这一操作就无法被执行。

所谓 Isolation，是指保持原子性的一系列操作的中间状态，不能由其他事务进行干涉这一性质，由此可以保持隔离性而避免对其他事务产生影响。

所谓 Durability，是指当保持原子性的一系列操作完成时，其结果会被保存并且不会丢失这一性质。

整体来看，ACID 非常重视数据的完整性，而 RDBMS 正是保持着这样的 ACID 特性而不断进化至今的。

但近年来，要满足这样的 ACID 特性却变得越来越困难。这正是 RDBMS 的极限，也就是我们希望通过键 - 值存储来克服的问题。

CAP 原理

近年来，人类可以获得的信息量持续增加，如此大量的数据无法存放在单独一块硬盘上，也无法由单独一台计算机进行处理，因此通过多台计算机的集合进行处理成为了必然的趋势。这样一来，在实际运营时就会发生延迟、故障等问题。多台计算机之间的通信需要通过网络，而网络一旦饱和就会产生延迟。

计算机的台数越多，机器发生故障的概率也随之升高。在万台数量级的数据中心中，据说每天都会有几台计算机发生故障。当由于延迟、故障等原因导致“计算机的集合”之间的连接被切断，原本的集合就会分裂成若干个小的集合。

当组成计算环境的计算机数量达到几百台以上（有些情况下甚至会达到万台规模）时，ACID 特性就很难满足，换句话说，ACID 是不可扩展的。

对此，有人提出了 CAP 原理，即在大规模环境中：

· Consistency（一致性）

· Availability（可用性）

· Partition Tolerance（分裂容忍性）

这三个性质中，只能同时满足其中的两个。

在大规模数据库中如何保持 CAP，很难从一般系统的情况进行类推。因为在大规模系统中，延迟、故障、分裂都是家常便饭。

在我们平常所接触的数台规模的网络环境中，计算机的故障是很少发生的，但对于数万、数十万台规模的集群来说，这样的“常识”是无效的。在这样的数量级上，就会像墨菲定律所说的一样，“只要存在故障的可能性就一定会发生故障（而且是在最坏的时间点上）”。

据说 CAP 原理已经通过数学方法得到了证明。CAP 中的 C 是满足 ACID 的最重要因素，如果 CAP 原理真的成立的话，我们就可以推断，像 RDBMS 这样传统型数据库，在大规模环境中无法达到期望值（或者说无法充分发挥其性能）。这可真是个难题。

CAP 解决方案——BASE

根据 CAP 原理，C（一致性）、A（可用性）和 P（分裂容忍性）这三者之中，必须要舍弃一个。

如果舍弃分裂容忍性的话，那么只有两个选择：要么根本不会发生分裂，要么在发生分裂时能够令其中一方失效。

根本不会发生分裂，也就意味着需要一台能够处理大规模数据的高性能计算机。而且，如果这台计算机发生故障，则意味着整个系统将停止运行。现代的数据规模靠一台计算机来处理是不可能完成的，因此从可扩展性的角度来看，这并不是一个有效的方案。

此外，当发生分裂时，例如大的计算机集群被分割为两个小的集群，要区分哪一个才是“真身”也并非易事。如果准备一台主控机，以主控机所在的集群为“真身”，这的确可以做到。但如果主控机发生故障的话，就等于整个系统发生了故障，风险也就大大增加了。

在分布式系统中，像这样“局部故障会导致整体故障”的要害，被称为 Single point of failure（单一故障点），在分布式系统中是需要极力避免的。

不能舍弃可用性

那么，舍弃 A（可用性）这个选择又如何呢？这里的关键字是“等待”。也就是说，当发生分裂时，服务需要停止并等待分裂的恢复。另外，为了保持一致性，也必须等待所有数据都确实完成了记录。

然而，用户到底能够等待多长时间呢？仅仅作为一个用户的我，是相当没有耐心的，等上几秒钟就开始感到烦躁了，如果几分钟都没有响应，我想我就再也不会使用这个服务了。假设分裂和延迟的原因是由于机器故障，即便是准备了完善的备份机制，想要在几秒钟之内恢复也几乎是不可能的。所以结论就是，除非是不怎么用得上的服务，否则是不能舍弃可用性的。

那么现在就只剩下 C（一致性）了，舍弃一致性是否现实呢？仔细想想的话，在现实世界中严密的一致性几乎是不存在的。例如，A 要送个包裹给 B，在现实世界中是不可能瞬间送到的。A 需要将包裹交给物流公司，然后通过卡车等途径再送到 B 的手上，这个过程需要消耗一定的时间（无 Atomicity）。而且，配送中的状态是可以追踪的（无 Isolation），运输过程中如果发生事故包裹也可能会损坏（无 Consistency）。再有，即便对损坏和遗失上了保险，此次运输交易行为本身也不可能“一笔勾销”。

即便现实世界如此残酷，我们却还是进行着各种交易（事务）。这样看来，即便是在某种程度上无法满足一致性的环境中，数据处理也是能够完成的。例如，网上商城的商品信息页面上明明写着“有货”，到实际提交订单的时候却变成了“缺货”，这种事已经是家常便饭了，倒也不会产生什么大问题。和银行汇款不同，其实大多数处理都不需要严格遵循 ACID 特性。

在这样的环境中，BASE 这样的思路也许会更加合适。BASE 是下列英文的缩写：

· Basically Available

· Soft-state

· Eventually consistent

ACID 无论在任何情况下都要保持严格的一致性，是一种比较悲观的模式。而实际上数据不一致并不会经常发生，因此 BASE 比较重视可用性（Basically Available），但不追求状态的严密性（Soft-state），且不管过程中的情况如何，只要最终能够达成一致即可（Eventually consistent）。这种比较乐观的模式，也许更适合大规模系统。说句题外话，一开始我觉得 BASE 这个缩写似乎有点牵强，但其实 BASE（碱）是和 ACID（酸）相对的，这里面包含了一个文字游戏。

大规模环境下的键 - 值存储

好，下面该进入正题——键 - 值存储了。键 - 值存储的一个优点，是可以通过“给定键返回对应的值”这一简单的模式，来支撑相当大规模的数据。键 - 值存储之所以适合大规模数据，除了使用散列值这一点外，还因为它结构简单，容易将数据分布存储在多台计算机上。

不过，在实际的大规模键 - 值存储系统中，还是存在一些必须要注意的问题。下面我们通过一个大体的框架，来探讨一下可扩展的键 - 值存储架构。

分布键 - 值存储的基本架构并不复杂。多台计算机（节点）组成一个虚拟的圆环，其中每个节点负责某个范围的散列值所对应的数据。

当应用程序（客户端程序）对数据进行访问时，首先通过作为键的数据（字符串）计算出散列值，然后找到负责该散列值的节点，直接向该节点请求取出或者存放数据即可（图 1）。怎么样，很简单吧？然而，要实现一个具备实用性和可扩展性的键 - 值存储系统，需要注意的问题还有很多。下面我们来看看这个系统的具体实现。

图 1 键 - 值存储架构示例

通过散列值判断存放数据的节点并直接进行访问。为了提高可用性，两端相邻的节点都拥有数据的副本。

先声明一下，这里要讲解的可扩展键 - 值存储架构，基本上是以乐天开发的 ROMA 为基础的。可扩展键 - 值存储系统的实现有很多种，这里所介绍的架构并不是唯一一种。另外，为了讲解上方便，这里介绍的内容和实际的 ROMA 实现是有一些偏差的。

访问键 - 值存储

我们先来看一个简单的应用程序实现。应用程序一侧要执行的处理并不多，大体上可以分成“初始化”和“访问（获取、保存等）”两个步骤。

首先是初始化。应用程序在初始化时，需要指定几个构成键 - 值存储系统的节点。指定的节点并不需要是特殊节点，只要是参加键 - 值存储系统组成的节点都可以。之所以要指定多个，是考虑到在这其中至少应该有一个是存活的。

应用程序按顺序访问指定的节点，并向第一个应答的节点传达要访问键 - 值存储的请求。接着，建立连接的节点向客户端发送“哪个节点负责哪个范围的散列值”的信息（即路由表）。收到路由表之后，剩下的访问操作就比较简单了。根据要获取的键数据计算出散列值，然后通过路由表查询出负责该散列值的节点，并向该节点 发送请求。请求的内容分为获取、保存等很多种类，在 ROMA 中所支持的请求如表 1 所示。比 Hash 要稍微复杂一些呢。

表1 ROMA的访问请求

访问请求

内 容

get

获取键所对应的值

set

设置键所对应的值

add

当键不存在时设置值

replace

当键存在时设置值

append

在当前值的末尾附加

prepend

在当前值的开头附加

delete

删除键所对应的值

inc

将键所对应的值加1

del

删除键所对应的值

每次进行数据访问时，应用程序都需要与负责各个键（的散列值）的节点建立连接并进行通信。这个通信过程都是通过套接字来完成的。通过套接字与远程主机建立连接，实际上需要很大的开销。ROMA 早期的原型中，每次都需要建立这样的连接，于是这个部分就成了瓶颈，导致系统无法发挥出期望的性能。

所幸，一般情况下，对键 - 值存储的访问都具有局部性，也就是说对同一个键的访问可能会连续发生。在这样的情况下，池（pooling）技术就会比较有效。所谓池，就是指对使用过的资源进行反复利用的技术。这个案例中，也就是指对一定数量的套接字连接进行反复利用。特别是在访问具有局部性的情况下，连接池的效果是非常好的。

在键 - 值存储的运用中，难免会遇到由于延迟、故障、分裂等导致某些节点无法访问的状况。在 ROMA 中，各应用程序都持有一张记载组成键 - 值存储系统所有节点信息的表（路由表），并直接对节点进行访问。在这种类型的系统中，保持路由表处于最新状态是非常重要的。

ROMA 会定期对路由表进行更新。每隔一段时间，客户端会向路由表中的任意节点发出获取最新路由信息的请求。

此外，对各个节点的请求也设置了超时时间，如果某个节点未在规定时间内响应请求，则会被从路由表中删除。

键 - 值存储的节点处理

与应用程序相比，组成系统的节点的行为十分复杂，特别是像 ROMA 这样不存在承担特殊工作的主节点，且各节点之间相互平等的 P2P 型系统。

节点的工作大体包括以下内容：

· 应对访问请求

· 信息保存

· 维护节点构成信息

· 更新节点构成信息

· 加入处理

· 终止处理

正如图 1 所示，系统中的节点构成了一个圆环，其中每个节点的结构如图 2 所示。

图 2 节点的结构

存储器

存储器（storage）就是实际负责保存信息的部分。在 ROMA 中，存储器是作为插件存在的，通过启动时的设置可以对存储器进行切换。目前实现的存储器包括下列这些：

· RH 存储器：将信息保存在 Ruby 的 Hash 对象中的存储器。这种方式无法将信息保存到文件中，因此 ROMA 整体运行停止后信息就消失了。

· DBM 存储器：将信息保存在 DBM（实际上是 GDBM）中的存储器。

· File 存储器：将信息保存在文件中的存储器。每个键都会产生一个独立的文件，因此磁盘目录可以用作索引。

· SQLite3 存储器：将信息保存在 SQLite3 中的存储器。SQLite3 是一种很有名的公有领域 RDBMS。

· TC 存储器：将信息保存在 Mixi 开发的 TokyoCabinet 中的存储器。是在 ROMA 实际运用中最为常用的一种。

各个存储器都定义为“Roma::Storage::BasicStorage”的子类，其定义采用模板方法的形式。在运用中，ROMA 可以根据数据库所需特性来选择合适的存储器。从实际来看，大多数案例都可以用 TC 存储器来解决。

写入和读取

当应用程序发起写入请求时，在确认键的散列值属于本节点负责范围后，该节点会通过存储器对数据进行保存。

这个时候，如果数据只保存在一个节点上的话，万一这个节点发生故障，数据就会丢失。为了提高可用性和分裂容忍性，写入必须由多个节点共同完成。

如果重视响应速度的话，可以在本节点完成写入操作之后，马上对请求进行响应，剩下的写入操作则可以在后台完成。在 ROMA 中由于对响应速度并不是非常重视，而是需要追求可靠性，因此所有的写入操作是同步执行的。不过，如果由于某些原因导致数据复制写入失败，则会在后台重新尝试执行写入操作。

如果由于应用程序所持有的路由表信息过期等原因，导致请求写入的键不属于本节点负责的范围，该节点会将请求转发出去。

读取的处理和写入差不多，但由于不需要出于冗余的目的对其他节点发出请求，因此处理方式更加简单。

节点追加

分布式键 - 值存储系统的优点就是运用的灵活性。当数据过多、访问速度下降时，只要追加新的节点就可以进行应对。

追加新节点时，需要指定一个现有的节点作为入口，然后启动新的节点。新启动的节点和指定的现有节点进行通信，申请加入环状结构，然后向全体节点发送对节点间数据分配进行调整的请求。刚刚启动的新节点并不包含任何数据（在启动时显式指定了已永久保存的数据库的情况除外），随着节点调整的进行，数据会逐步分配给新的节点。

故障应对

作为可扩展的键 - 值存储系统来说，最重要的恐怕就是对故障的容忍性了。正如之前讲过的，随着组成系统的计算机台数的增加，发生故障的概率也会大幅度上升。在大规模系统中，即便组成系统的一部分计算机发生故障，系统也必须能够继续运行。

发生频率最高的，应该是单台计算机的故障。由于故障导致一台计算机从系统中消失，这样的例子十分常见。

当由于故障导致一个节点失去响应时，应用程序会尝试访问其他节点。在 ROMA 中，由于数据总是存放在多个节点中，因此通过路由表就可以找到其他的替代节点。

另一方面，出现无响应的节点，就意味着数据的冗余度下降了。为了避免这种情况，其他节点需要将消失的节点排除，然后重新组织节点的结构，根据需要向相邻节点复制数据，最终维持数据的平衡。新的节点结构信息，会通过定期更新发送给应用程序，而作为整个键 - 值存 储来说，会像什么都没有发生一般继续运行。

比较麻烦的情况是，暂时“消失”的节点又复活了。这种情况的发生可能是由于网线被拔出（这是在运营工作中经常会出现的意外），或者由于网络故障导致大规模网络延迟，这些应该还是比较常见的。

在以简洁为信条的 ROMA 中，遇到这样的情况，会将已经分离的节点完全舍弃。如果出现“复活”的情况，该节点需要作为一个新节点重新加入 ROMA 系统。ROMA 会将新加入的节点更新到路由表中，并重新对数据进行分配。

另一种故障也可能发生，那就是多个节点同时消失。在 ROMA 中，和一个节点消失的情况一样，会将这些节点舍弃。在多个节点同时消失的情况下，可能会发生冗余备份的数据同时丢失的问题。要找回丢失的数据是不可能的，因此系统就会报错。在这种情况下，就无法区分该数据是一开始就不存在，还是由于大量节点消失而导致的数据丢失。这当然会引发一些问题，但失去的东西总归无法复得，也就没必要进行任何特殊的处理了。

话虽如此，但丢失数据这种事，作为数据库来说确实是个不小的问题。为了拯救数据，ROMA 中提供了一个命令，可以将切断前已经由存储器写入文件的数据重新上传回 ROMA。这个操作只是将存储器数据读取出来并添加到 ROMA 中，基本的部分是非常简单的。不过，如果上传的数据中有一些键已经在 ROMA 中存在，且它们所对应的值不相同的情况下，必须决定选用其中某一个值来解决冲突。到底是分离之后 ROMA 一侧的数据被更新了，还是对节点的数据写入由于某些原因没有反映到 ROMA 一侧？仅凭键和值的数据是无法判断的。

实际上，在 ROMA 中对每份数据都附加了一个叫做“逻辑时钟”（logical clock）的信息，它是一种在每次数据被更新时进行累进的计数器。当上传的数据和 ROMA 中已经存在的数据发生冲突时，通过逻辑时钟就可以判断应该以哪一方的数据为准。

在各种故障中，还可能发生分裂的情况，也就是在完全隔绝的网络中，还在继续独立工作的意思。在 ROMA 中，要应对这种故障，只能将分裂开的 ROMA 系统中的其中一个手动停止。虽然这种手段非常原始，但分裂这样的故障并不会经常发生，这样的应对应该已经足够了。从分裂故障中进行恢复，和上述情况一样，也是通过使用从存储器上传数据的功能来完成的。

终止处理

出人意料的是，在 P2P 型结构中，最麻烦的操作居然是终止。要进行终止操作，首先要向任意节点发送终止请求，然后，该节点就自动成为负责终止的主节点，由它对全体节点发送“即将终止”的声明。收到声明之后，各节点停止接受新的请求，并在当前时间点正在处理的请求全部完成之后，对存储器执行文件的写入（内存存储的情况除外），完成后向终止主节点发送回复。回复完毕后，结束该节点的进程。

负责终止的主节点在收到全部节点（故障、无应答的节点除外）的回复后，结束自身进程。至此，ROMA 系统的运行就全部停止了。

其他机制

除了上述讲到的内容之外，ROMA 中还有以下这些机制：

1. 有效期

ROMA 中的数据都设置了有效期，因此如果要实现“这个数据仅在今天有效，明天就需要删掉”这样的规则是很容易的。

2. 虚拟节点

为了让节点之间因分配调整而进行的数据传输更加高效，系统中采用了将若干个键组织起来形成“虚拟节点”的机制。

3. 散列树

如图 1 所示，ROMA 使用了环状节点分布和浮点小数散列值，实际上的算法使用的是 SHA-1 ²散列和 Merkle 散列树³，这种方式的效率更高。

^{2 SHA-1 是 SHA 系列的成员之一。SHA（Secure Hash Algorithm，安全散列算法）是由美国国家安全局设计的一套散列算法，是美国的国家标准，被广泛应用于各种安全协议中。SHA 系列包括 SHA-1、SHA-224、SHA-256、SHA-384 和 SHA-512 共 5 个成员。}

^{3 散列树（hash tree）是用于存放大量数据（如文件）的散列信息的一种数据结构，用于对数据进行验证。这种数据结构是列表和链表的组合，是对散列算法的一种扩展。散列树又被称为 Merkle 树，该命名来源于 Ralph Merkle（1952— ），他是公钥加密算法的创始人之一，同时也是一位研究人体冷冻技术和分子纳米技术的科学家。}

性能与应用实例

在乐天旅游的“最近浏览过的酒店”和乐天市场⁴ 的“浏览历史”等功能中，都采用了 ROMA，每个用户的访问历史记录都是保存在 ROMA 中的。ROMA 基本上都是用 Ruby 编写的，但是它所提供的性能却足够支持日本最大级网站的应用。

^{4 乐天市场：}http://www.rakuten.co.jp/

小结

除了 ROMA 之外，还有很多键 - 值存储系统的实现方式，它们也都具备各自的特点。由于这些项目大多数都是开源的，因此通过阅读源代码来研究一下或许也是一件很有意思的事。