sparkey

Sparkey是一个简单的常量键/值存储库。它主要适用于读取频繁但大批量插入不频繁的系统。它包括一个用于处理Sparkey索引和日志文件的C库（libsparkey），以及一个用于获取Sparkey索引/日志信息和读取值的命令行工具（sparkey）。

Travis

使用travis进行持续集成。

依赖项

GNU构建系统（autoconf, automake, libtool）
Snappy

可选

Doxygen

构建

autoreconf --install
./configure
make
make check

可以使用doxygen生成API文档。

安装

sudo make install && sudo ldconfig

描述

Sparkey是一个极其简单的持久化键值存储。你可以将它视为磁盘上的只读哈希表，这样理解并不算偏差太远。它是为Spotify的一些服务器端用例设计和优化的，但它的编写是完全通用的，不对存储的数据类型做任何假设。

一些主要特点：

支持最大2^63 - 1字节的数据大小。
支持迭代、获取、放置、删除操作。
针对批量写入进行了优化。
不可变的哈希表。
允许任意数量的并发独立读取。
每个存储单元一次只允许一个写入者。
跨平台存储文件。
每个条目的开销较低。
读取启动成本恒定。
每次读取的磁盘寻道次数较少。
支持块级压缩。
数据无关，只是将字节数组映射到字节数组。

它不是：

它不是分布式键值存储 - 它只是磁盘上的一个哈希表。
它不是压缩数据存储，但如果需要，可以在其基础上实现。
它不能防止数据损坏。

我们在Spotify的用例是为用户或其他服务提供很少更新的数据。快速高效的批量写入使得定期重建数据变得可行，而快速的随机访问读取使其适用于高吞吐量低延迟的服务。对于某些服务，我们能够在保持CPU使用率非常低的同时饱和网络接口。

限制

哈希写入过程需要分配num_entries * 16 * 1.3字节的内存。这意味着如果尝试为太多条目写入哈希索引，可能会耗尽内存。例如，有16 GB可用RAM时，你可以写入8.25亿个条目。

这个限制在sparkey-java中已经被移除，但尚未在此版本中实现。

使用方法

Sparkey旨在作为嵌入其他软件的库使用。查看API文档，其中给出了如何使用它的示例。

许可证

Apache License, Version 2.0

设计

Sparkey使用磁盘上的两个文件来存储数据。第一个是Sparkey日志文件（.spl），它只是一系列键值对。这是一个只追加文件。不允许在中间修改它，也不能使用多个写入者来追加。

另一个文件是Sparkey索引文件（.spi），它只是一个指向日志中条目的哈希表。这是一个不可变文件，因此通常只在完成批量追加后更新它。

进行随机查找涉及首先在哈希表中找到适当的条目，然后在日志文件中寻找正确的偏移量。平均而言，对于冷磁盘缓存，这意味着每次访问需要两次磁盘寻道。如果你锁定索引文件，寻道次数会减少到一次。对于我们的某些用例，总数据集小于可用RAM，因此锁定所有内容是有意义的。

与只有一个文件相比（另一种解决方案是在末尾附加哈希表），使用两个文件的优势在于可以轻松地锁定其中一个文件而不锁定另一个。它还使我们能够在已经使用的日志文件中追加更多数据。

历史

Sparkey是Spotify黑客日的产物，在那里我们的开发人员可以花一些时间研究他们认为有趣的任何东西。

我们有几个用例需要以高吞吐量和低延迟提供大量静态数据。为此，我们构建了自己的服务，由各种存储系统支持。我们的流程包括首先在离线系统中生成大型静态存储文件，然后将其推送到面向用户的服务以提供数据。

我们用于此目的的存储解决方案曾经都很好地为我们服务过一段时间，但它们有一些限制，最终成为问题。

我们过去大量依赖CDB（这是一个非常棒的软件）。它性能极快，生成的文件很紧凑。我们只是在数据开始接近4 GB限制时才停止使用它。
我们还使用（并仍在使用）Tokyo Cabinet处理一堆用例。它在读取方面表现出色，但当你无法再将整个数据集保存在内存中时，写入吞吐量会大大下降，而且从同一进程多次打开同一文件时会出现问题。

我们需要一个具有以下特征的键值存储：

随机读取吞吐量与Tokyo Cabinet和CDB相当。
高吞吐量批量写入。
低开销。
数据大小限制高。

为了好玩，我们在内部黑客日开始开发一个新的键值存储，开发人员可以在这一天研究他们感兴趣的任何东西。结果就是这个项目。

性能

包含了一个非常简单的基准程序 - 参见src/bench.c。该程序设计为易于扩展，以测量其他键值存储（如果有人想这么做的话）。在类生产服务器（Intel(R) Xeon(R) CPU L5630 @ 2.13GHz）上运行它，我们得到以下结果：

测试1000个元素的批量插入和1000,000次随机查找
  候选：Sparkey
    创建时间（墙钟时间）：     0.00
    创建时间（CPU时间）：      0.00
    吞吐量（写入/CPU秒）： 1098272.88
    文件大小：                28384
    查找时间（墙钟时间）：       0.50
    查找时间（CPU时间）：        0.58
    吞吐量（查找/CPU秒）： 1724692.62

测试批量插入1,000,000个元素和1,000,000次随机查找候选者: Sparkey 创建时间(墙钟时间): 0.50 创建时间(CPU时间): 0.69 吞吐量(插入/CPU秒): 1,448,618.25 文件大小: 34,177,984 查找时间(墙钟时间): 1.00 查找时间(CPU时间): 0.78 吞吐量(查找/CPU秒): 1,284,477.75

测试批量插入10,000,000个元素和1,000,000次随机查找候选者: Sparkey 创建时间(墙钟时间): 7.50 创建时间(CPU时间): 7.73 吞吐量(插入/CPU秒): 1,294,209.62 文件大小: 413,777,988 查找时间(墙钟时间): 1.00 查找时间(CPU时间): 0.99 吞吐量(查找/CPU秒): 1,014,608.94

测试批量插入100,000,000个元素和1,000,000次随机查找候选者: Sparkey 创建时间(墙钟时间): 82.00 创建时间(CPU时间): 81.58 吞吐量(插入/CPU秒): 1,225,726.75 文件大小: 4,337,777,988 查找时间(墙钟时间): 2.00 查找时间(CPU时间): 1.98 吞吐量(查找/CPU秒): 503,818.84

测试批量插入1,000个元素和1,000,000次随机查找候选者: Sparkey压缩(1024) 创建时间(墙钟时间): 0.00 创建时间(CPU时间): 0.00 吞吐量(插入/CPU秒): 1,101,445.38 文件大小: 19,085 查找时间(墙钟时间): 3.50 查找时间(CPU时间): 3.30 吞吐量(查找/CPU秒): 303,335.78

测试批量插入1,000,000个元素和1,000,000次随机查找候选者: Sparkey压缩(1024) 创建时间(墙钟时间): 0.50 创建时间(CPU时间): 0.75 吞吐量(插入/CPU秒): 1,333,903.25 文件大小: 19,168,683 查找时间(墙钟时间): 3.00 查找时间(CPU时间): 2.91 吞吐量(查找/CPU秒): 343,833.28

测试批量插入10,000,000个元素和1,000,000次随机查找候选者: Sparkey压缩(1024) 创建时间(墙钟时间): 8.50 创建时间(CPU时间): 8.50 吞吐量(插入/CPU秒): 1,176,634.25 文件大小: 311,872,187 查找时间(墙钟时间): 3.00 查找时间(CPU时间): 2.99 吞吐量(查找/CPU秒): 334,490.22

测试批量插入100,000,000个元素和1,000,000次随机查找候选者: Sparkey压缩(1024) 创建时间(墙钟时间): 90.50 创建时间(CPU时间): 90.46 吞吐量(插入/CPU秒): 1,105,412.00 文件大小: 3,162,865,465 查找时间(墙钟时间): 3.50 查找时间(CPU时间): 3.60 吞吐量(查找/CPU秒): 277,477.41

文件格式详情

日志文件格式

日志文件的内容以固定大小的头部开始，描述了一些关于日志文件的元数据。之后是一系列条目，每个条目由类型、键和值组成。

每个条目以两个可变长度数量(VLQ)非负整数A和B开始。类型由A决定。如果A = 0，它是一个DELETE操作，B表示要删除的键的长度。如果A > 0，它是一个PUT操作，键长度为A - 1，值长度为B。

(如果使用了块级压缩，情况会稍微复杂一些，但我们暂时忽略这一点。)

哈希文件格式

哈希文件的内容与日志文件类似，以固定大小的头部开始。文件的其余部分是一个哈希表，表示为容量 * 槽大小字节。容量只是活动条目数的上限乘以一个大于1.0的哈希密度因子。默认实现使用密度因子 = 1.3。每个槽由两部分组成：哈希值部分和地址。哈希值的大小为4或8字节，取决于哈希算法。目前，如果条目数量小，则使用murmurhash32；如果条目数量大，则使用murmurhash128的64位截断。地址只是对日志文件的引用，根据日志文件的大小为4或8字节。这意味着对于任何相当大的条目集，槽大小通常为16字节。通过在每个槽中存储哈希值本身，我们浪费了一些空间，但作为回报，我们可以期望在大多数情况下避免访问日志文件。

哈希查找算法

Sparkey中为数不多的非平凡部分之一是它进行哈希查找的方式。使用哈希表时，总是存在冲突的风险。即使哈希本身可能不会冲突，分配的槽也可能会。

(最近我意识到下面描述的方法基本上与带有后移删除的Robin Hood哈希相同)

让我们定义位移为给定哈希的计算最优槽到实际放置槽的距离。在这种情况下，距离定义为从最优槽向前移动到达实际槽所需的步数。

对此的简单和朴素解决方案是从一个空的哈希表开始，遍历条目并将它们放入第一个可用槽中，从最优槽开始，这几乎就是我们所做的。

如果我们考虑平均位移，我们确实无法做得更好。然而，我们可以最小化最大位移，这给我们带来了一些不错的特性：

我们可以将最大位移存储在头部，这样我们就有了遍历的上限。我们甚至可能使用这个信息来对条目进行二分查找。
一旦我们遇到位移大于我们正在查找的条目的位移，我们就可以中止查找。

这样设置哈希表非常容易，我们只需要将插入操作改为插入到槽中，而不是追加。一旦我们遇到位移小于我们自己的槽，我们就将后面的槽向上移动一步，直到第一个空槽，然后插入我们自己的元素。

让我们用一个例子来说明 - 让我们从一个容量为7的空哈希表开始：哈希值日志偏移量最优槽位偏移量 +------------+------------+ 槽位 0 | | | +------------+------------+ 槽位 1 | | | +------------+------------+ 槽位 2 | | | +------------+------------+ 槽位 3 | | | +------------+------------+ 槽位 4 | | | +------------+------------+ 槽位 5 | | | +------------+------------+ 槽位 6 | | | +------------+------------+

我们添加键"key0"，它刚好落在槽位3，h("key0") % 7 == 3。该槽位是空的，所以这很简单：

         哈希值   日志偏移量    最优槽位    偏移量
       +------------+------------+
槽位 0 |            |            |
       +------------+------------+
槽位 1 |            |            |
       +------------+------------+
槽位 2 |            |            |
       +------------+------------+
槽位 3 | h(key0)    | 1          |  3               0
       +------------+------------+
槽位 4 |            |            |
       +------------+------------+
槽位 5 |            |            |
       +------------+------------+
槽位 6 |            |            |
       +------------+------------+

现在我们添加"key1"，它刚好落在槽位4：

         哈希值   日志偏移量    最优槽位    偏移量
       +------------+------------+
槽位 0 |            |            |
       +------------+------------+
槽位 1 |            |            |
       +------------+------------+
槽位 2 |            |            |
       +------------+------------+
槽位 3 | h(key0)    | 1          |  3               0
       +------------+------------+
槽位 4 | h(key1)    | 11         |  4               0
       +------------+------------+
槽位 5 |            |            |
       +------------+------------+
槽位 6 |            |            |
       +------------+------------+

现在我们添加"key2"，它也想要在槽位3。这是一个冲突，所以我们向前跳过，直到找到一个偏移量小于我们当前偏移量的槽位。当我们找到那个槽位时，所有后续条目直到下一个空槽位都向下移动一步：

         哈希值   日志偏移量    最优槽位    偏移量
       +------------+------------+
槽位 0 |            |            |
       +------------+------------+
槽位 1 |            |            |
       +------------+------------+
槽位 2 |            |            |
       +------------+------------+
槽位 3 | h(key0)    | 1          |  3               0
       +------------+------------+
槽位 4 | h(key2)    | 21         |  3               1
       +------------+------------+
槽位 5 | h(key1)    | 11         |  4               1
       +------------+------------+
槽位 6 |            |            |
       +------------+------------+

让我们添加"key3"，它映射到槽位5。我们不能下推key1，因为它已经有了偏移量1，而我们当前key3的偏移量是0，所以我们必须向前移动：

         哈希值   日志偏移量    最优槽位    偏移量
       +------------+------------+
槽位 0 |            |            |
       +------------+------------+
槽位 1 |            |            |
       +------------+------------+
槽位 2 |            |            |
       +------------+------------+
槽位 3 | h(key0)    | 1          |  3               0
       +------------+------------+
槽位 4 | h(key2)    | 21         |  3               1
       +------------+------------+
槽位 5 | h(key1)    | 11         |  4               1
       +------------+------------+
槽位 6 | h(key3)    | 31         |  5               1
       +------------+------------+

添加"key4"到槽位3。它最终在槽位5，偏移量为2，而key3绕回到槽位0：

         哈希值   日志偏移量    最优槽位    偏移量
       +------------+------------+
槽位 0 | key(key3)  | 31         |  5               2
       +------------+------------+
槽位 1 |            |            |
       +------------+------------+
槽位 2 |            |            |
       +------------+------------+
槽位 3 | h(key0)    | 1          |  3               0
       +------------+------------+
槽位 4 | h(key2)    | 21         |  3               1
       +------------+------------+
槽位 5 | h(key4)    | 41         |  3               2
       +------------+------------+
槽位 6 | h(key1)    | 11         |  4               2
       +------------+------------+

现在，如果我们搜索映射到槽位3的key123（但它不存在！），我们可以在到达槽位6时停止扫描，因为此时当前偏移量（3）高于当前槽位条目的偏移量（2）。

压缩

Sparkey还支持使用Google Snappy进行块级压缩。你可以选择一个块大小，然后用它来将日志内容分割成块。每个块都使用Snappy独立压缩。如果你的瓶颈是文件大小，并且相邻条目之间有大量冗余数据，这可能会很有用。使用这种方法的缺点是在查找过程中，至少需要解压一个块。你选择的块越大，可能获得的压缩效果越好，但查找成本也会更高。这是一个需要针对每个用例进行实证评估的权衡。