TokuDB 与 FT-Index 赖明星 数据库技术组 2015年1月22日

目录 TokuDB简介 Fractal-Tree Index 从存储角度理解TokuDB的优势 TokuDB的独有特性及原理 Benchmark，结论，参考资料

目录 TokuDB简介 Fractal-Tree Index 从存储角度理解TokuDB的优势 TokuDB的独有特性及原理 Benchmark，结论，参考资料

1. TokuDB简介 产品 团队 与innodb对比 人们对tokudb的印象

1.1 产品 07年开始开发，09年发布第一个版本，13年4月开源 TokuMX TokuDB tokudb-engine (handle) ft-index 07年开始开发，09年发布第一个版本，13年4月开源

1.2 团队 3位(Tokutek)创始人: Michael A. Bender , Martín Farach-Colton , Bradley C. Kuszmaul  TokuDB目前有５名研发: prohaska tokudb-engine研发，版本发布(一个人) Leif tokuFT研发，tokuMX研发(Bender学生) zkasheff tokuFT研发，tokuMX研发 (Kuszmaul学生) esmet tokuFT研发(Farach学生) fizzfaldt 算法优化(Bender学生)

1.3 与innodb对比 InnoDB TokuDB Index Type B-tree Fractal Tree® index Insertion Rate at Scale 100s / second 10,000s / second Compression ~2x 5x – 10x typical, up to 25x possible Hot Indexing No (hrs+) Yes (secs to mins) Hot Column Addition/Deletion/ Expansion/Rename Fast Loader No Yes Fragmentation Immunity Yes (no dump/reload downtime – no index fragmentation) Clustering Indexes Primary Key Only Multiple Eliminates Slave Lag

1.4 人们对tokudb的印象 tokudb是一个应用在MySQL和MariaDB中的存储引擎，它使用索引加快查询速度，具有高扩展性，并支持hot scheme modification。 特点： 1.插入性能比innodb快20~80倍； 2.压缩数据减少存储空间； 3.数据量可以扩展到几个TB； 4.不会产生索引碎片； 5.支持hot column addition，hot indexing，mvcc； 如何考虑使用： 1.如果要存储blob，不要使用tokudb，因为他的记录不能太大； 2.如果记录数过亿，使用tokudb； 3.如果注重update的性能，不要使用tokudb，他没有innodb快； 4.如果要存储旧的记录，使用tokudb； 5.如果要缩小数据占用的存储空间，使用tokudb；

目录 TokuDB简介 Fractal-Tree Index 从存储角度理解TokuDB的优势 TokuDB的独有特性及原理 Benchmark，结论，参考资料

2. Fractal Tree Index

2. Fractal Tree Index B-tree索引的缺陷 假设：B = 16KB 50GB / 16KB ~ 300w个node，太多了！ 缺点：不适合随机读写，大部分是寻道时间！

2. Fractal Tree Index Fractal-Tree® 索引 B = 4MB (块大，整块压缩，~1MB) 50GB / 4MB ~ 1w个node，node少！

2. Fractal Tree Index 每个node有4-16个子节点(fanout) 每个node都有一个message buffer Main memory Disk 每个node有4-16个子节点(fanout) 每个node都有一个message buffer 靠近root的节点在内存，靠近leaf的节点在磁盘

2. Fractal Tree Index INSEInsert/Update/Delete/Column等，均是message，可lazy式操作，延迟小RT Main memory Disk Main memory Disk

2. Fractal Tree Index

2. Fractal Tree Index

2. Fractal Tree Index

目录 TokuDB简介 Fractal-Tree Index 从存储角度理解TokuDB的优势 TokuDB的独有特性及原理 Benchmark，结论，参考资料

3.从存储角度理解TokuDB的优势 机械硬盘 SSD 读、写速度不对称 异地更新 写前擦除 写以页为单位、擦除以块为单位 有限次的擦除操作

目录 TokuDB简介 Fractal-Tree Index 从存储角度理解TokuDB的优势 TokuDB的独有特性及原理 Benchmark，结论，参考资料

4. TokuDB的独有特性及原理 超高的压缩比例 多个聚集索引 No Slave Lag Hot Schema Change

4.1 超高压缩比例 TokuDB支持的几种压缩算法（ROW_FORMAT） Tokudb_lzma Tokudb_zlib Tokudb_quicklz Tokudb_uncompressed 压缩算法都是公开的压缩算法，为什么TokuDB压缩比例能够如此之高？其他数据库/存储引擎是否可以采用相同的压缩算法，达到同样高的压缩比例？ 大块压缩

4.2 多个聚集索引 TokuDB的索引 covering index clustering index create table foo(a int primary key, b int, c int, d int); covering index：alter table foo add index cvr_xx(b, c); {key={len=xx data="b-c-a"} val={len=0 data=""}} clustering index：alter table foo add index cst_xx(b,c); {key={len=xx data="b-c-a"} val={len=xx data="d"}}

4.2 多个聚集索引 数据库中数据的组织方式 堆表 索引组织表

4.2 多个聚集索引 TokuDB Clustering Index A clustering index maintains a copy of the entire row, not just the primary key. advantages Clustering indexes can create indexes that would otherwise bounce up against the limits on the maximum length and maximum number of columns in a MySQL index. Clustering indexes simplify syntax making them easier and more intuitive to use. Clustering indexes have smaller key sizes leading to better performance.

4.3 No Slave Lag Read Free Replication When handling write rows, delete rows, and update rows log events, the MySQL replication slave uses extra queries to verify various properties of the slave's version of the table.  For a TokuDB fractal tree, these hidden queries have a very high cost. If the keys are accessed in a random sequence, then each replication event will result in a point query. These stalls are fatal to the slave's performance, and result in large slave lags. Read Free Replication

4.3 No Slave Lag Read Free Replication 主库配置必须BINLOG_FORMAT=ROW 主库上的操作不能违反唯一性约束（比如设置了＂unique_checks=OFF＂，否则主备同步会停止），这样到TokuDB备库的所有log event都默认不需要再做＂unique check＂ 备库只读 那么，使用了Read Free Replication，是否真的No Slave Lag 了呢？ TokuDB吹牛了！ Slave延迟是MySQL Server层的机制，只有Server层才能保证No Slave Lag，但是，是在牺牲性能的前提下(比如可以等备库返回，主库才认为此次操作成功， 如InnoSQL的VSR)，引擎无法保证No Slave Lag，只能Less Slave Lag。

目录 TokuDB简介 Fractal-Tree Index 从存储角度理解TokuDB的优势 TokuDB的独有特性及原理 Benchmark，结论，参考资料

Benchmark

5.2 结论 TokuDB存储引擎具有插入效率高、压缩效率优秀、在线DDL等诸多优势，在写性能要求较高的业务场景中提升非常明显 TokuDB存储引擎不如InnoDB通用，它并不能取代InnoDB存储引擎 较那些“动不动声称比InnoDB快N倍”的数据库有前途

5.3 参考文献 淘宝一工《高性能存储引擎TokuDB》 Martin《Fractal-Tree-Technology-and-The-Art-of-Indexing》 赵天元、姜承尧《TokuDB存储引擎在网易生产环境中的应用实践》 《TokuDB with Tractal Tree Indexing for MySQL：Quick Start Guide for linux》 Michael A Bender《Cache-Oblivious Streaming B-Trees》 http://en.wikipedia.org/wiki/Fractal_tree_index

谢谢！