SLIK：高扩展、低延时的键值存储索引实现（RAMCloud）

本文首发于王豪迈的个人博客，经作者推荐分享至InfoQ 中文站。

RAMCloud 是新起的内存存储系统的典范，本文是 SLIK 论文实现部分的译文。原文： SLIK: Scalable Low-Latency Indexes for a Key-Value Store 。另外，在阅读这篇论文之前建议首先了解 RAMCloud 重要的存储格式论文 Log-structured Memory for DRAM-based Storage ，在这篇里面会以这个为基础，也可以参考本博的简要介绍 FAST 14 论文推荐 (上) ，这篇论文是 FAST 14 的最佳论文。

Contents

• 译文
• 1. 介绍
• 2. RAMCloud 概述
• 3. 目标
• 4. 数据模型
• 5. SLIK 架构
  • 5.1 索引分片
  • 5.2 基本操作
  • 5.3 对象的键哈希值
  • 5.4 一致性
  • 5.5 崩溃后的持久性和高可用性
  • 5.6 表的索引管理
  • 5.7 崩溃后的一致性

译文

摘要：大量的高扩展存储系统牺牲了功能或者一致性来弥补扩展性或者性能。与之相反，本文描述的SLIK 实现了对已存在的高性能键值存储系统（RAMCLOUD）增加次要索引，并且没有牺牲延迟或者扩展性。通过在内存中维护索引数据，SLIK 在索引下提供了20us 的读延迟和50us 的写延迟。与此同时，SLIK 支持索引数据的横向扩展并可以覆盖上以千计的节点上。SLIK 允许索引数据在代码实现上的内部不一致来获得高效的性能，而且面向客户端的索引数据是保证强一致性的。SLIK 使用RAMCLOUD 已经实现的片式设计来存储节点上的B 树索引，使得SLIK 能重用已经存在的方法来实现持久和故障恢复能力。

1. 介绍

在过去的几年了，一类新的存储系统为了满足大规模 Web 应用的需求而诞生，像 Bigtable、Cassandra、LevelDB、RAMCloud 和 Redis，这些系统都能扩展到成百上千的服务器，来提高到前所未有的整体性能。然后，为了满足它们的扩展性，大部分大规模存储系统都接受了功能上的妥协。比如非常多键值存储系统没有次要索引，当应用检索数据需要利用其他属性而不是主键时，这就会成为一个问题。除此之外，大部分大规模存储系统都是弱一致性的模型，它们也不支持原子性的涉及多对象事务，在一些情况它们甚至不支持原子性的多副本单对象更新。因此，大规模存储系统相比之前的不能大规模扩展的“前辈”使得应用更难以编程。

RAMCloud 是上述提到的大规模存储系统的一个例子，它通过汇聚一个数据中心上千台服务器的内存来提供服务并将所有数据存储在内存中来提供快速的访问 (小块读 5us 左右)，它对于存储数据也提供了高层次的持久性和一致性。然而，它的数据模型是一个多表的键值存储，因此不支持次要索引和多对象事务。

这篇论文主要描述了一个针对 RAMCloud 的实验，通过修改 RAMCloud 来支持次要索引。主要目的是看看一个内存系统能否在不牺牲延迟或者扩展性的情况下支持次要索引。此外，次要索引也需要持久性和一致性。

这个实验系统称为 SLIK（Scalable，Low-latency Indexes for a Key-value store）。SLIK 实现了以下几个：

1. 数据模型是多键 - 值存储，每个对象会有多个键来对应一个不可解释的二进制数据
2. 索引数据像普通数据一样存储在不同的服务器，这就造成了可能的不一致更新。SLIK 的实现允许这个现象，但是它只是在内部发生不一致，而客户端只能看到一致的 (线性化) 的接口。
3. SLIK 使用了已存在的日志结构表存储方法来存储索引数据，使得 SLIK 能够利用已存在的 RAMCloud 实现来实现高性能的持久性和崩溃恢复。

SLIK 提供了高性能、低延迟读写和高扩展的吞吐量：

• SLIK 完成一个简单的被索引对象读操作在 20us 左右
• SLIK 更新一个被索引的对象时间在 50us 以内
• 整个索引的吞吐量可以通过大量服务器能线性扩展

SLIK 的延迟低于其他存储系统像 Hyperdex，并且有数量级的差距。

次要部分介绍了 RAMCloud 的背景信息，第三部分介绍了索引的设计目标，第四部分描述了 SLIK 可以提供给客户端应用的功能，第五部分讨论了 SLIK 的内部实现。第六部分评估了 SLIK 的性能。第七部分将 SLIK 与其他索引方法进行了对比。

2. RAMCloud 概述

RAMCloud 是一个将所有数据存储在成千上百台在一个数据中心的服务器内存的存储系统，它通过利用低延迟的网络来提供 5us 的读请求和 16us 的写时间（对于小对象而言）。所有的 RAMCloud 数据在所以时间都在内存中存在。

RAMCloud 的数据模型包括了一系列的表，每个表都拥有任意数量的对象。每个对象都包括一个可变长度键值和一个版本数。对象通过其唯一性的键来获取，对象必须是全读或者全写，RAMCloud 不会假设任何特殊结构的键值。

每个大表都都被分成多片存储在不同的服务器上，每片数据都会拥有两个哈希键，每个键会被哈希得到 64 位值，这片数据所有的对象的内容也会产生一个哈希值。

每个 RAMCloud 存储服务器都有两个组件，一个 Master 模块用来处理来自客户端的读写请求，它管理着服务器的内存并且用日志结构的方式来存储数据片，使用哈希表来快速定位数据。每个 Master 的日志都会分成 8MB 的数据段，并且每个段会形成多个副本来保证可用的备份。Backup 模块使用本地的磁盘或者闪存来存储其他服务器上被 Master 模块管理的数据拷贝，数据段副本允许 Master 的数据在崩溃后迅速重新组建起来。

Master 和 Backup 都会通过一个中心化的协同模块管理，这个协同模块用来处理配置相关的问题像集群的成员关系和数据片的分布情况，但是并不参与到数据读写操作中。

3. 目标

SLIK 被设计成支持在每个表上拥有一系列的次要索引，并且允许不同的键类型和排序方法。举个例子，一些索引可能使用按照字母顺序排列的字符串，另一些使用按数字大小排列的浮点数。此外，SLIK 仍然需要使 RAMCloud 系统维持原来的一些重要属性：

• 低延迟：所有的索引必须一直被存在在内存中，索引操作的延迟应该尽量接近原来 RAMCloud 的操作（比如原来是 1us，现在可以是 10us，但不能是 ms）
• 扩展：SLIK 必须支持超过一个服务器存储容量的索引。索引即使扩展到上千的服务器也保持稳定的性能（一个简单的操作不随着索引数据的扩展而增加延迟），索引的总吞吐量应该随着服务器的扩展而增加
• 持久性和可用性：与已经存在的 RAMCloud 数据一样，只有一份索引数据拷贝会存在在内存里。索引数据必须被持久复制直到写操作返回并且它必须能够在 Master 崩溃后在 1-2s 内恢复数据
• 一致性：RAMCloud 的目标是所有操作的线性化。对于索引数据而言，这意味着在一个对象写入、更新时，所有相关索引数据必须随之更新并且保持原子性，甚至在并发访问或者服务器崩溃时
• 弹性：必须允许任何时间并且不影响正常数据操作的情况下，进行像创建索引或者删除索引这类模式修改

就目前而言，没有其他系统能够提供这些功能，特别是在非常低延迟的情况下。

4. 数据模型

这个部分描述 SLIK 提供的给客户端应用的 API 及其动机。

第一个问题是解决存储次要索引的问题。一个方法是存储每个对象的次要索引键并作为对象的一部分，这个方法保持了对象的基本键值结构，但是它要求客户端和服务器统一一个对象的结构以便于服务器能找到这些键（当一个对象被删除后，存储系统必须找到所有的次要索引键来删除）。多个存储系统像 CouchDB 和 MongoDB 都是采用这个方法，并且 CouchDB 和 MongoDB 都需要对象以 JSON 格式存储，每个次要索引根据 JSON 值里特定的路径才能定位到键。

传统的键值存储对于值并没有任何约束。SLIK 也希望保持这个属性，提供了客户端最大的弹性来根据需要去优化它们的表示格式，但是它要求所有值都以 JSON 格式存储会对 SLIK 应用带来额外的 JSON 解析负担。

因此，SLIK 需要选择一个能最小化结构给客户端带来影响的数据模型。SLIK 实现了多键 - 值存储方式，每个对象都拥有多个可变长度的键和一个可变长度的值。跟原来的 RAMCloud 一样，值是不能被存储系统解释的。键都是通过 8 位整数来区分，比如从 0 开始分配（让客户端自己决定索引的符号名字）。键 0 是主键，也就是最初 RAMCloud API 用来读写对象的键。每个对象必须拥有一个在表中唯一的主键。除了键 0 以外其他键都称为次要键，次要键在表中可以相同。

索引和次要键是独立的关系，一个包含次要键的对象可以没有相应的索引，它也可以删除次要键但是其索引是存在的。如果一个对象删除了一个次要键，那么通过对应的索引不会查找到这个对象。也有可能在某些状况下，一个对象拥有次要键但是并没有包含在对应的索引中。同时也有可能去维持对象和索引的强一致关系，并且我们期望大部分应用维护这种强一致关系，但是允许不一致的情况可以让索引可以在线改变。

当一个表的新索引创建时，它开始是空的，即使这个早已经存在对象。为了协同已经存在的对象和新索引，客户端可以扫描表的所有对象（使用 RAMCloud 的表遍历方法）来重写每个对象。当一个对象被写入时，它会自动加上这个对象包含的所有索引键。这个方法主要是为了扩展性考虑，它避免了当索引创建时自动索引所有表中已存在对象的问题。这样一个操作对于一个跨越大量服务器的大表来说非常艰巨。

索引的删除也是采用类似方式，当一个索引被删除时，对于表中对象而言没有变化，它们仍然保持已经存在的次要键。如果客户端不需要这些键，它可以重新遍历表来重写对象使得删除次要键。

5. SLIK 架构

这个部分主要讨论了为了满足第三部分提出的目标带来的设计问题和最终的内部架构。

5.1 索引分片

为了得到扩展性，SLIK 必须支持无论是对象还是索引数据的无法放到一个服务器上的大表。在一个极端情况下，一个应用可能只有一个表并且它的数据被存储到上千服务器上。因此，它必须可能支持将索引分片。每个分片都可以存储在不同的服务器上，下面主要考虑两个不同的方法来支持分片。

范围分片：这个方法就是根据索引的排序方法将索引数据连续分片到多个服务器上，像按数字排序索引，一个索引片可能包括所有小于零的键，另一个索引片可能包括所有大于或等于零的。这个方法提供了范围查询的局部性考虑，一些小的范围查询很困难会在一个索引片上完成。

范围分片允许索引片数据存储在不同的服务器上而不是它的对象存储位置，当这种情况发生时，范围读操作就需要一个二阶段的方法。首先，一个或多个索引服务器必须沟通来得到相应的服务器范围根据所需的键范围。然后一个或多个对象所处的服务器必须沟通来得到这个范围内的对象。这就意味着一个范围读操作最少需要两倍于原来的时间。多个服务器必须参与到写操作中来以便于更新对象及其相关索引。

哈希分片：这个方法是将每个索引片存储到相同的数据片上。也就是在这个范围的索引键会和主键及其值存储在一个服务器上。如果一个表拥有多个索引，那么每个服务器都会存储这个数据片的多个索引片。

哈希分片的优点是写操作可以在一个服务器上完成，范围读操作可以通过一个阶段的 RPC 处理：每个服务器扫描自己的索引然后查询特定的索引并返回。

不幸的是，这个哈希分片的扩展非常困难，每个范围读都必须查询每个存储这个表的数据片的服务器。特别是这里并没有特殊的索引范围和索引片的联系，那些只存在少量服务器上的表通过哈希分片会更快。然后随着表跨越服务器的增加，广播数据的时间最后会线性增加。

根据 RAMCloud 多读操作的测量，这个并发请求的转折点是 5 个请求，如果一个表超过 5 个服务器，那么它会花费更少的时间相对于两次 RPC 请求的范围分片。当表跨越更多的服务器时，哈希分表会导致两个问题，首先广播会使得范围读操作更慢，另外一个索引的总吞吐量将不会随着索引片的增加而增加，因为每个索引片都需要参加所有的范围读操作。因此，我们可以认为哈希分片不能满足扩展性的要求。SLIK 将会使用范围分片的方式。

另一个范围分片的优点是它允许数据片和索引片分离并且根据容量和负载独立的移动。相对的，哈希分片只能让索引片和数据片同时分片。

5.2 基本操作

索引的主要操作就是范围读，根据索引来获得一系列对象。然后就是写请求，会创建和删除索引记录。SLIK 实现了这些操作的低层次的 RPC 调用。

对于范围读操作，客户端库会以下面这些步骤操作：首先发出 lookup 请求给一个或多个索引服务器来区分这些次要键的范围。然后它发出 readHashes 请求来得到真正的对象。另一个可选的实现是让索引服务器来获得这些对象并返回，但是这个方法要求对象在网络上传输两次并且增加索引服务器的额外工作，而客户端只能等待操作完成。

对于写请求，客户端发出一个请求给存储这个对象的 Master 服务器，Master 会修改这个对象然后调用 entryInsert 和 entryRemove 来更新相关索引记录。对于这个请求，这里采用了 Master 服务器而不是客户端发出 RPC。另一个可选的方法是让客户端并发的发出请求给对象的 Master 服务器和索引服务器，但是这需要客户端维护索引和对象的一致性。通常来说，RAMCloud 不会依赖客户端来保证内部的一致性。因此，会造成不一致的写请求必须被 RAMCloud 服务器管理。

在设计 SLIK 时通常尽可能的将功能放在客户端库，使得服务器的负载更小并提高可扩展性。然后，这个方法只对读操作有用，大部分修改数据进而影响一致性的操作都需要在服务器端完成。

5.3 对象的键哈希值

当设计 SLIK 时，最初假设索引记录会映射次要键到主键，然后每次 lookup 请求会返回一系列主键和对应的对象。然后，最后决定存储主键的哈希值而不是主键在索引上。主键哈希包括了足够的信息去寻找对象：它被用来得知哪个服务器存储对象，并被服务器根据哈希表用来查找对应的位置。键哈希的另一优点是比键更短，被固定在 8 个字节。

而缺点是它可能不是唯一的，两个不同的主键可能产生相同的哈希值，当然这个可能性很小。当这种情况发生时，readHashesRPC 将会返回所有这个哈希值的对象，客户端库会过滤掉不符合的对象。

在这个罕见情况下，因为索引记录只会得知一个哈希值，它取决于对象的 Master 服务器来维持这些重复哈希值并准确发出 entryInsert 和 entryRemove 请求。举个例子，如果相同哈希值的两个对象存在并且一个被删除，Master 服务器必须不能删除这个索引值，因为两个相同哈希值的对象必定存在于同一个服务器上，因此检测相同的哈希值问题会比较简单。

5.4 一致性

允许索引数据和对象数据存储在不同的服务器造成了可能的不一致问题。如果一个对象首先被更新写入然后再写入相应的索引记录，它可能因为客户端并发操作而造成读不到对象。

在 SLIK 中，为了给客户端提供一致性模型需要确保两个属性：

• 如果一个对象拥有次要键并且在一个时间这个次要键被写入时对应的次要索引存在，那么一个 readRange 请求包括这个次要键时，这个次要键可以返回这个对象
• 如果一个对象被 readRange 返回，那么返回的对象包括了对应索引的这个次要键，并且这个键在 readRange 指定的范围内

已经存在的存储系统通常来说处理这个索引问题有两种方法。大部分大规模数据系统都简单允许不一致来简化实现和提高性能，像 Espresso 和 Megastore 为了全局索引使用了弱一致性，让应用方来保证一致性。第二个方法类似于小规模系统包装了更新在一个事务里确保原子性。然而，在 RAMCloud 这类分布式系统需要复杂且低效的两段式提交协议。

SLIK 使用了不同的方法，它允许实现的不一致，但是会在客户端接口中掩盖这些不一致。这就是成为一个相对简单但是高效的实现，并且让客户端具备上述两个属性。

特别的，SLIK 会按照下面顺序更新会导致有时候出现不相干的索引记录，这种情况不会太少。当 Master 收到写请求时，它会执行如下动作：

步骤一: 发出 entryInsert 请求并行的创建新的索引记录对于每个次要键
步骤二: 一旦所有的 entryInsert 请求成功完成，写新的对象并且复制分发。这时候会安全的返回回应给客户端
步骤三: 当写请求替代了原来的对象，发出 entryRemove 请求来并行的移除原来的索引记录。这个动作会在返回回应给客户端后异步发生

移除对象也会有类似的行为，除了第一个步骤外。总而言之，这个方法保证了两条一致性属性的第一条。

但是，这个算法满足不了第二条一致性要求，因为这里可能会存在旧的索引记录指向已不存在的对象或者没有对象的满足的键。不过幸运的是，这两个异常都可以简单的在 RAMCloud 的客户端库解决，当客户端收到 readHashes 请求时，它可以比较每个对象的次要键，然后最后给应用返回符合范围的对象。因此，一致性的成本就是一些额外的范围检查加上极少可能出现的需要被丢弃的额外对象。

5.5 崩溃后的持久性和高可用性

索引服务在崩溃后会引入持久性和高可用性的问题。第一个问题就是在内存的索引数据会丢失，SLIK 必须维护冗余的信息用来重建。第二，重建必须快速发生来避免长时间的不可用。RAMCloud 恢复分片数据在 1-2s 内。SLIK 恢复索引数据的时间也在需要达到这个时间。目前主要有两种方法，分别是重建和备份。

重建方法：重建方法主要是基于所有索引片的数据来自于索引对象并且它们都是冗余的，如果索引片在崩溃后丢失，它可以快速重建在表中的所有对象的索引数据。如果崩溃同时导致了索引对象的数据丢失，那么这些对象可以首先被 RAMCloud 已经存在的机制去恢复。

备份方法：主要是存储索引到第二级存储，像对象数据一样。当 RAMCloud 写一个对象时，它会把对象的键值添加到 Master 的内存日志后，然后这些日志会被转发到多个备份服务器上，然后在这些非易失性介质上临时存储日志最后写入硬盘或者闪存。写操作直到备份服务已经得到这些数据才会返回。如果一个 Master 崩溃，在日志中会有最近的完全拷贝最后回放去重组丢失数据。索引的备份方法就是如此，索引服务器在写入索引时可以先写到本地日志最后分发到备份服务器才回应客户端请求。如果一个索引服务崩溃，索引信息会从备份中得到来重建。

重建方法看起来会更加吸引人，因为它在常规操作中有显著的性能优势，且没有额外的负担让索引变得持久化。相比之下，备份方法需要每个索引服务去分发索引数据到备份服务才能回应一个请求。基于目前 RAMCloud 的性能评测，这个过程会增加 30% 的额外时间。

但是重建方法显然有致命的漏洞，它满足不了在 1-2s 内崩溃恢复的要求。这里同样存在两个性能问题，首先，当一个索引服务崩溃后，其他每个 master 必须扫描所有的属于这个索引表的在内存的对象，这个对于一个有 250GB 内存的 master 而言通常需要 5s 以上，并且这个时间随着容量增长变得更糟。第二，在索引服务器上去重建一个 B tree 的索引是不可接受的。这个过程单线程需要 15s 以上的时间。当然，多线程可能可以提高速度但是显然不能满足 1-2s 的需求。因此重建方法不能提供可接受的恢复性能，这里只能不情愿的选择备份方法。

5.6 表的索引管理

在决定索引记录必须被写入 RAMCloud 日志后，这里就需要使用 RAMCloud 的表来存储索引，SLIK 为每个索引分片分配一个表用来存储索引片的 B 树信息。这个表成为后端表，不为用户所见。它总是存储在服务器上管理索引片。

使用表来存储索引数据后有几个有点，首先它简化了灾难恢复，后端表可以使用 RAMCloud 原有机制，一旦对象恢复到内存中，没有其他额外的工作需要重新去创建整个索引片的数据。

这也大大简化了内存的管理，一个单独的服务器可以存储索引数据和普通数据片，服务器的内存容量可以被共同使用。使用表作为索引存储方法后意味着可以使用相同的内存管理方法作为数据片，因此内存的分配可以根据需要前后移动。如果内存不使用日志的方式，那么就需要将内存分成两部分来提供给内存日志（对象采用的存储策略）和索引，然后这个分配就需要一直调整。

这个方式的问题是使得 B 树的查找会缓慢一些，从父节点到子节点的链接是通过子节点的主键确定的，因此，横穿父节点到子节点需要在 Master 服务的哈希表中将主键翻译到对应对象的地址。

5.7 崩溃后的一致性

服务器崩溃后会导致额外的不一致可能，第一个一致性问题索引片内部的 B 树结构，索引在插入和删除有时会造成 B 树的分裂或者合并，导致一次插入或者删除会对多个节点进行更新，为了维护索引的一致性，这些节点的更新必须是原子性的。

SLIK 利用了 RAMCloud 日志结构存储管理方法去实现原子性，多节点更新会在一条日志记录里合并，这样备份服务也会原子性地写入这一条日志记录。RAMCloud 早已经利用这个方法来处理对象的覆盖写问题来解决新旧对象更替。这里扩展了 RAMCloud 的通用目的方法允许任意数量的更新（取决于一个单一日志段长度）去原子性的分发，然后在 B 树中使用这个方法。

第二个一致性问题是索引记录和对应对象的问题，SLIK 允许日志记录没有对应的对象在处理更新请求时，当崩溃在此时发生，会留下一条没有被删除的索引记录，这些垃圾记录会慢慢累计然后在扫描索引时删除。