说说 TokuDB 与 Fractal Tree Index

版权声明: 允许非商业性转载，但转载时必须标明原作者 fcicq、原始链接 http://www.fcicq.net/wp/?p=892 及本声明。

BDB 和 TCHDB / TCBDB 可能大家玩厌了.
Tokyo (Cabinet|Tyrant) pluggable abstract api 挺好玩的. 这个早就在 mixi Engineers’ Blog 上写过, 不提.
可是如果把 TC / TT 和下面这个东西接在一起…

—

2009 年以索引技术创业的 TokuTek 发布了 TokuDB for MySQL, 看性能参数是挺不错的.
当时就对它产生了极大的兴趣. 但非常不幸偶没有理解它的索引原理 (Tokutek 也不说). 再加上它不是很成熟, 没有 ACID, 多核支持也不好, 所以暂时搁置了.

推荐大家都看看这个幻灯片 How Fractal Trees Work
还有个讲课视频, 这个就不给出了, youtube 上有.

设有 n 个数据吧.
基本意思是有 log2(n) 个索引块, 块的大小分别是 1, 2, 4… 直到 2^k, 其和大于 n (要不就存不下了 ). 每个块只有空和填满两种状态.
插入时如果碰到块满的情况就把两个小块合并为更大的块.
因为较小的块可以在内存中合并 (反正内存中怎么折腾都不会慢的), 对较大的块来说在旋转存储器上的归并速度也是很快的, 这就是 TokuDB 高速最直接的原因. 压缩是另一个加分的因素.

查询的问题幻灯片讲的比较清楚, 优化上也不难, 这里就不再写第二遍了.

看来最大的问题就是, 两个块合成新块时, 如果两个块都很大就比较麻烦了. 这也是 Page 23-25 提到的问题.

关于删除的问题幻灯片没有说. 不过考虑到它作为数据仓库的用途, 这一点可以暂时原谅. 删除也可以用对数据加 flag 的方法解决. 好像更新也不是简单的事情.
看起来整个用 BigTable 的方法也行, 只是不知道现在 Google 改造存储系统的情况如何. kumofs 的作者说 kumofs 是第二代分布式存储系统(彻底没有单点问题), 这个情况有感兴趣的自己去研究吧.

Page 28, 变长的数据是容易处理的. 搜索的复杂度降到 O(logB(N)), 存储的只要是块的位置(或编号)就可以了(注). 事务(包括灾难恢复)和并行化可能是难度最大的部分.

注: 细节看这个 http://tokutek.com/presentations/bender-Scalperf-9-09.pdf

说到对存储到硬盘上的数据进行整理, 就不得不提到 Reiser4 引入的 Dancing Tree.
写入之前对 Block 做整理的操作, 这是对 B-Tree 的一个比较有效的优化, 只是可惜了…

Cache-Oblivious Search Trees 是 Fractal Trees 出现之前的成果. 一年前偶就顺着网页看到了它, 可是偶不明白具体原理. hmm…

—

TokuDB 还有 covering index (试译: 覆盖索引) 的支持. 覆盖索引要求所有要查询的列都在索引之中.
http://tokutek.com/presentations/kuszmaul-mysqluc-percona-09-slides.pdf
如果有 (a, b, c) 的覆盖索引, 则查询 select b, c where a = xx 这类是很快的.
(覆盖索引和多维排序索引有什么区别? 如果后者不能完成这个任务, 那是 MySQL 的错, 这绝对不是 TokuDB 的首创)

但偶不明白二维索引的实现方式. Page 15 有 38<=a and a<=42 and 90<=b and b<=99, 谁能解释一下应该怎么做?
当然, 偶知道有其它的解法, 二维线段树偶知道, GeoHash 这种方法也可以考虑, 但前提都要预先知道取值范围. 如果 Page 15 的问题是用这种索引解决的, 那可真要仔细看看了. 暂时继续抱怀疑态度.

当然说到这个幻灯片, Page 14 的均摊分析把偶吓了一下.
B-Tree 的 Point Query 的复杂度是 O(logN/logB), 实际上就等于 O(logB(N)), 你是不是忘了换底公式了?
不知道这是否是故意的, 给偶一个错觉, 幸好偶的数学还不是非常差劲. 这种模糊手法要明确指出来, 不能再吓着别人.
关于 Insert 的复杂度, B-Tree 的优化是允许多个块写到一起(包括内存上的优化). 但随机的场合性能不佳是自然的.
Fractal Tree 索引的效率和内存的关系并不大, 但实现上看起来挺吃 CPU 的.
仔细想来, Fractal Tree Index 大批量的插入均摊复杂度确实是 O(logN / B).

—

Tokutek 的收费政策是生产环境未压缩纯数据(不算索引) 50 GB 以下不收费,
包括所有的副本(也就是说 Replication 的话就要算多次了), 当然也没有技术支持.

超过部分每 100 GB / 年收费 $1000 (换算一下是 $0.83 / GB * Month ).
Tokutek 认为单台机器能承担 5 TB 的数据, 这个数字偶是要怀疑的. 而且偶不愿意承担单点的风险.
显然可以谈个优惠价出来, 实际上偶愿意接受的价格不超过 $0.05 / GB * Month.
这个收费比 GAE DataStore 和 Amazon SimpleDB 都贵太多了, 实在不合算. 有人还在想 Oracle 怎样怎样…

换一个角度说, 如果你用 NoSQL 存数据, 用它当索引(注意别涉及删除问题), 偶想肯定不会超过 50 GB 的 这个引擎存文本虽然没问题, 可是偶肯定不会这样推荐的.

—

TokuDB 的下载页面提供了 Fractal Tree Library 的下载, 只有 x86_64 的版本.
(需要注册, 随便填填就过了, 需要验证 E-Mail, 没有审核)
解压出来有一个大号的 .so 文件, include 目录下有 tokudb.h. 实现还算是比较完整. 提供了测试的程序, 但有说要是作为嵌入式数据库的话需要获得许可.

Fractal Tree Library 可以当 BDB 用, 也可以当 TCBDB 用.
于是乎, 就有了文章最开始的那一幕.

—

ps:
最近发现偶 blog 上文章的题目和实际内容是两回事, 还是改一改吧.

ps2:
因为某保护条例第十七条的规定, 所以允许某人盗版 XP 而不支付报酬, 这对吗?
(话说要是没有 Google Translate 的话, 就可以换一种更明确的表达方式了)

ps3:
有人说 Oracle 应该买下 Tokutek. 或者别的什么公司也可以买它. 你觉得呢?

ps4:
Tokutek 说未来的数据库都要以它为索引, 偶承认这是项不错的技术, 不过这是不是技术幻想?

ps5:
大网站的技术团队都那么强, 为什么这篇文章的作者是偶呢? 偶期待着有人用和偶一样少的资源写出一样好的东西. 偶的 reco 都停了有一年了, 等着大家来追偶.
当然如果你觉得偶写的不好的话可以扔邮件到偶这里来.

ps6:
文章加粗的地方都有用, 相信偶.

友情提示: 请注意文章的时效性与准确性, 作者不对文章的有效性负责.