高效的字典数据库（唯一词到唯一ID及反向）

Question

我在寻找一个解决方案，能够做到以下几点：

• 存储任意大小的独特单词，以及它们各自的64位无符号整数标识符和32或64位无符号整数的引用计数
• 快速访问这些数据，具体要求如下：
  • 查找一个单词时，返回它的uint64标识符
  • 查找一个标识符时，返回对应的单词
• 插入新记录，最好是自动递增的标识符和原子递增的引用计数，最好能批量提交（也就是说，不是一个个单词插入，每个都单独交易，而是一次性插入多个单词）
• 原子删除引用计数为零的记录（这可以通过限制速率的全表扫描来完成，遍历所有记录并在一个事务中删除引用计数为0的记录）
• 在传统的硬盘上存储大量记录，记录数量在1亿到1000亿之间（1000*10^9）
• 平均单词大小在25到80字节之间
• 最好有Python接口（用于原型开发）和C接口，主要是可嵌入的，或者一个高效的“远程”API（只在本地使用）

例如，一个MySQL的架构可能是这样的：

CREATE TABLE words (
    id SERIAL,
    word MEDIUMTEXT,
    refcnt INT UNSIGNED,
    INDEX(word(12)),
    PRIMARY KEY (id)
)

当然，这样是可行的，但MySQL并不适合这个任务，而且由于需要为单词搜索建立索引，它会多存储一些冗余信息。

在寻找最有效的解决方案时，我发现了以下几点： - 由于这些单词有很多共同点（大多数是各种语言和字符集中的普通词汇），像这个链接的方案会不错：http://www.unixuser.org/~euske/doc/tcdb/index.html - 到目前为止，我找到的最好方案是东京柜的TDB：packages.python.org/tokyocabinet-python/TDB.html，但我还需要评估它的性能和可能的设置（在哪里存储什么，使用什么样的索引以获得最佳的时间和空间效率）

有没有什么想法、算法，或者更好的是，现成的产品和设置？

谢谢，

Answer 1

你可以试试Redis。它几乎能满足你所有的需求。对于你的使用场景，它的性能很好，支持原子性增减操作，可以用来创建引用计数和唯一标识符，并且有适用于多种语言的客户端，包括Python和C。你还可以把一系列命令放在一个事务中执行。它还支持列表、集合、排序集合以及其他一些你可能会觉得有用的功能。

如果你能把工作分开，就可以从多个主机并行加载和处理数据。考虑到Redis的速度，你可能不需要把数据批量处理，但这也是可以做到的（使用MSET命令）。

另一个不错的地方是，你可以通过命令行与Redis互动，使用redis-cli命令。这样你可以在写代码之前先试试或调试一系列命令。假设Redis在本地运行，使用默认端口，你可以输入：

% redis-cli
redis>

我写了一组快速的命令，支持你的使用场景。

这个代码片段创建了一个名为next.words.id的整数键，并原子性地将其递增，返回新的值。为了说明，我把这个序列的起始值设为123455。(integer) 123456就是会返回给你的客户端的值：

redis> SET next.words.id 123455
OK
redis> INCR next.words.id
(integer) 123456

然后我们把单词映射到它的ID"chaos" -> 123456，接着创建一个反向映射id:123456 -> "chaos"，最后创建一个引用计数键，初始值设为0。前缀id:、ref:和next.words.id只是我选择的约定——你可以使用任何你喜欢的命名。

redis> SET chaos 123456
OK
redis> SET id:123456 chaos
OK
redis> SET ref:chaos 0
OK

要增加单词"chaos"的引用计数：

redis> INCR ref:chaos
(integer) 1
redis> INCR ref:chaos
(integer) 2

要减少引用计数，可以使用DECR：

redis> DECR ref:chaos
(integer) 1
redis> DECR ref:chaos
(integer) 0

此时你的代码可以检测到"chaos"的引用计数已经变为0，并在一个事务中执行以下命令：删除这个单词，以及它的id:和ref:键。我使用了WATCH命令来避免竞争条件：如果在我们的事务提交之前，其他客户端更改了ref:chaos键，事务将会被中止。

redis> WATCH ref:chaos
OK
redis> GET chaos
(integer) 123456
redis> MULTI
redis> DEL chaos
QUEUED
redis> DEL id:123456
QUEUED
redis> DEL ref:chaos
QUEUED
redis> EXEC
1) (integer) 1
2) (integer) 1
3) (integer) 1

希望这些对你有帮助。