Redis / 字典 / sqlite3 在数百万对上的应用

Question

我有一对对的（键，值），其中键是字符串，值是整数。我想从一个很大的文本库中建立一个索引，所以我存储字符串和一个标识符。每次我从文本库中读取一个词时，都需要检查这个索引，看它是否存在，因此我需要快速查找（如果可以的话，最好是O(1)）。我之前使用Python的字典来创建这个索引，但问题是我的内存不够用了（16GB内存）。我的替代方案是继续使用字典，当我的内存使用达到90%时，我就用sqlite3数据库把这些对存储到硬盘上。但现在的问题是，查找的时间太长了（先检查字典，如果失败再去检查硬盘上的数据库）。

我在考虑换用Redis数据库。我的问题是，我应该把键值存储为字符串，还是应该先对它们进行哈希处理再存储？（键是字符串，长度在2到100个字符之间）。那么值呢，我需要对它们做什么处理吗？（值是int32类型的数字）

补充：

我想存储每个词及其标识符（唯一的对），如果我读取一个词，它在索引中存在，就直接跳过。

补充2：

我尝试使用Redis，但似乎速度很慢（？），我用的代码和之前的字典一样，只是把字典的set和get换成了Redis的，这应该是O(1)的复杂度，但建立索引的时间还是太慢了。有什么建议吗？

Answer 1

我应该把键值存储为字符串，还是先进行哈希处理再存储呢？那值呢？

在你的情况下，最简单的方法就是对每一对唯一的键值使用 SET 命令，比如 SET foo 1234 这样。

不过，像Instagram那样，你可以使用Redis的哈希功能，这样在后台会有更好的内存优化：

哈希表 [...] 当元素数量小于某个特定值，并且元素大小不超过最大限制时，会以一种非常节省内存的方式编码，使用的内存最多可以少到10倍。

（更多细节可以查看Redis的内存优化文档。）

根据Instagram的建议，你可以这样做：

1. 用64位哈希函数对每个键进行哈希处理： n = hash(key)
2. 计算对应的桶： b = n/1000 （每个桶包含1,000个元素）
3. 在这个桶中存储哈希和对应的值（i）对： HSET b n i

注意：保持你的整数值 i 不变，因为在后台，整数是用可变字节数在ziplists中编码的。

当然，要确保将Redis配置为 hash-max-ziplist-entries 1000，以确保每个哈希都能进行内存优化（xx）。

为了加快初始插入速度，你可能想通过批量插入来使用原始的Redis协议。

(x) 在Redis中存储数亿个简单的键值对.

编辑：

(xx) 实际上，由于哈希函数的稀疏性，你的大多数（如果不是全部）哈希将只包含一个元素。换句话说，因为你的键是哈希字符串，而不是像Instagram示例中的单调递增ID，这种方法在节省内存方面可能不那么有趣（所有的ziplists将只包含一对）。你可能想加载你的数据集，看看与基本的 SET key(= string) value(= integer) 方法相比，实际数据的表现如何。

Answer 2

用C语言的哈希表可以很容易地模拟Python的字典。Glib提供了一个可以使用的哈希实现，只要你有一些C语言的基础，就不难上手。这样做的好处是，它的速度会更快，而且占用的内存会少很多，相比于Python的字典来说：

https://developer.gnome.org/glib/2.40/glib-Hash-Tables.html

GLib哈希表循环问题

你还可以添加一些算法来提高性能。例如，可以存储一个压缩过的键。

更简单的方法是把你的大段文本分成几个部分，为每个部分创建一个独立的索引，然后再把这些索引“合并”在一起。

比如，索引1的样子是：

key1 -> page 1, 3, 20
key2 -> page 2, 7
...

索引2的样子是：

key1 -> page 50, 70
key2 -> page 65
...

然后你可以把索引1和索引2合并：

key1 -> page 1, 3, 20, 50, 70
key2 -> page 2, 7, 65
...

你甚至可以把这个过程分散到N台机器上进行。