第一期先介绍下TokuDB团队吧。  TokuDB自从开源后（更赞的是开源了所有的commits），逐渐被大家所熟悉，MariaDB 5.5系列和Percona Server 5.6的GA版本中，都以plugin的方式集成。 3位(Tokutek)创始人: [Michael A. Bender](http://www.cs.stonybrook.edu/~bender/) , [Martín Farach-Colton](http://www.cs.rutgers.edu/~farach/) , [Bradley C. Kuszmaul](http://people.csail.mit.edu/bradley/)   2012年他们合发了一篇208页的pdf[[Data Structures and Algorithms for Big Databases](http://www.tokutek.com/wp-content/uploads/2012/09/BenderKuszmaul-tutorial-xldb12.pdf)]，热爱存储引擎算法的朋友们一定要看 :D TokuDB目前有５名研发: ~~~ @prohaska --tokudb-engine研发，版本发布(一个人) @Leif --tokuFT研发(Bender学生) @zkasheff --tokuFT研发(Kuszmaul学生) @esmet --tokuFT研发(Farach学生) @fizzfaldt --算法优化(Bender学生) ~~~ 可以说是个很＂精致＂团队，是研发也是测试，tokuFT的测试代码达~18w行(而tokuFT的核心代码才~9w行)，在代码把控上也很严格，要求所有代码在valgrind(helgrind和drd)下，没有memory、data race(资源竞争)和lock order(死锁)警告，质量很有保障。(BTW:我们也在借鉴和运用)   同时@Leif和@zkasheff也是tokuMX的研发，不久前，他俩就MongoDB Replication可能＂丢数据＂的问题，写了篇[[Ark: A Real-World Consensus Implementation](http://arxiv.org/abs/1407.4765)]，对Paxos和Raft感兴趣的同学可以去看下。 更有意思的是，当工程中遇到难题，研发们先讨论出方案，递给三位创始人，得到更权威的指导，如果问题不错，他们就深入研究，出paper，工程与学术相结合。

最近，TokuDB的创始人Dr. Bradley Kuzmaul发表了一篇文章: [A Comparison of Log-Structured Merge (LSM) and Fractal Tree Indexing](http://forms.tokutek.com/acton/attachment/6118/f-0039/1/-/-/-/-/lsm-vs-fractal.pdf)，从write amplification(WAMP), read amplification(RAMP), and space amplification三个方面对B-Trees，LSM-Trees(LSM)以及Fractal-Trees(FT)进行了详细的分析和对比。 Dr. Bradley Kuzmaul的结果是(页13):   从结果来看： ~~~ 在WAMP上，FT跟LSM(leveled)是相同的 在RAMP(range)上，LSM(leveled)的复杂度明显要高不少(FT的O(logN/B)倍) ~~~ 不过，RAMP这块的分析有个小问题：  LSM(leveled)在实现上(比如LevelDB)，可以通过meta-info打＂锚点＂的方式，把RAMP(range)降低甚至做到跟FT一样，如果是point queries的RAMP，则可以通过Bloom filter来降低。 具体的推导过程请阅读原作，下面简单分析下FT的RAMP为啥比LSM的要低。  FT的读方式比较＂特殊＂，由于每个节点都有个message buffer，当有读请求时，需要把inner node的message buffer数据（部分）推(apply)到leaf node，最后只在leaf node上做二分查找，所以RAMP基本就是树的高度。 另外，在数据流向上(compaction过程中数据走向)，LSM强调"level"(横向)，从level-L根据规则选取部分数据merge到level-(L+1)，如果选取数据的策略不好，会抢占磁盘带宽，容易引起性能抖动，而FT强调"root-to-leaf"(纵向)，数据从root有序的逐层merge到leaf节点，每条数据的merge路径是很明确的。

Bulk Fetch是为了提升区间操作性能的，聊它之前，先简单唠叨下读取机制，TokuDB由两部分组成: [tokuFT](https://github.com/Tokutek/ft-index)和 [tokudb-engine](https://github.com/Tokutek/tokudb-engine) 。  tokuFT是个支持事务的key/value存储层，tokudb-engine是MySQL API对接层，调用关系为:tokudb-engine ->tokuFT。  tokuFT里的一个value，在tokudb-engine里就是一条row数据，底层存储与上层调用解耦，是个很棒的设计。  在tokuFT是个key里，索引的每个node都是大块头(4MB)，node又细分为多个＂小块＂(internal node的叫做partition，leaf node的叫做basement)。  从磁盘读取数据到内存的方式有２种： 1. 仅读一个＂小块＂的数据，反序列化到内存（提升point query性能，只读取需要的那部分数据即可) 2. 读取整个node数据，反序列化到内存（提升区间性能，一次读取整个node磁盘数据） 对于tokudb-engine层的区间操作（比如get_next等），tokuFT这层是无状态的，必须告诉当前的key，然后给你查找next，流程大体是: ~~~ tokudb-engine::get_next(current_key) --> tokuFT::search_next(current_key) --> tokuFT::return next ~~~ 这样，即使tokuFT缓存了整个node数据，tokudb-engine还是遍历着跟tokuFT要一遍：tokuFT每次都要根据当前key，多次调用compare操作最终查出next，路径太长了！  有什么办法优化呢？这就是Bulk Fetch的威力: tokudb-engine向tokuFT一次要回整个node的数据，自己解析出next row数据，tokuFT的调用就省了: ~~~ tokudb-engine::get_next(current_key) --> tokudb-engine::parse_next ~~~ 从Tokutek的测试看，在使用Bulk Fetch后，能有2x-5x的性能提升。  但并不是所有的区间操作都可以Bulk Fetch的(比如涉及update/delete)，TokuDB目前实现了:SELECT、CREATE_TABLE、INSERT_SELECT和REPLACE_SELECT的Bulk Fetch功能，预计发布在7.1.8版，更多Bulk Fetch介绍：  [https://github.com/Tokutek/tokudb-engine/wiki/Bulk-Fetch](https://github.com/Tokutek/tokudb-engine/wiki/Bulk-Fetch)

**背景** 随着存储设备越来越快，InnoDB许多原有的设计不再适合新的高速硬件，因此MariaDB 10.1 Alpha版本针对FusionIO PCI-E SSD做出了专门的优化，充分利用了Fio的硬件特性。 MDEV-6246这个需求改造了MariaDB，以利用fio的Atomic writes和文件系统压缩特性。 ~~~ revno: 3988 [merge] committer: Jan Lindström <jplindst@mariadb.org> branch nick: 10.1 timestamp: Thu 2014-05-22 14:24:00 +0300 message: MDEV-6246: Merge 10.0.10-FusionIO to 10.1. ~~~ 为何Fio会更快呢，因为传统的存储设备读取，是左图的方式，要经过RAID控制器，来回的路径就长了。而Fio才有右图的方式，设备通过PCI槽直接与CPU交互，大大缩短了路径。  **Atomic writes** InnoDB一直存在一个叫做Double Write Buffer的东西，目的就是为了防止页面写到一半系统崩溃，导致页面损坏，因为InnoDB的Page是16K，而一般的机械硬盘扇区是512字节，SSD大都是4K的块大小，都不能保证16K的写入是完整的。 而Fio的NVMFS文件系统则提供了原子写的保证，只要对文件句柄增加DFS_IOCTL_ATOMIC_WRITE_SET的ioctl标记位，就可以启用这个文件的原子写支持。 ~~~ ioctl(file, DFS_IOCTL_ATOMIC_WRITE_SET, &atomic_option) ~~~ MariaDB新增了一个参数来启用这个特性，一旦开启，所有文件会用DFS_IOCTL_ATOMIC_WRITE_SET标记打开。 ~~~ innodb_use_atomic_writes = 1 ~~~ 这样一来Double Write Buffer就没有存在的价值了，因为不会出现部分写，每个write下去都可以保证所写内容全部完成，这可以相当程度上提升InnoDB的性能。 **Page compression** InnoDB标准的页面大小是16K，InnoDB也提供1K、2K、4K、8K的压缩页面大小，通过KEY_BLOCK_SIZE来设置压缩大小，使用zlib标准库来进行压缩。 但是Page是频繁被更新的，如果每次修改都重新压缩页面，代价很高，InnoDB就采用了modification log来暂存部分修改信息，而避免了频繁解压缩，待modification log存满时，再重新对整个Page做一次重构压缩。 但是Compressed Page载入InnoDB Buffer Pool时，InnoDB只能处理未压缩的页面，因此还要在内存中存一份解压页面，回写到磁盘时再次压缩。 总而言之，InnoDB的Compressed Page有这些缺点： ~~~ 内存开销 空间: 压缩和解压缩页面都要存在InnoDB Buffer Pool 访问: 修改需要同时写入到压缩页面和未压缩页面 CPU开销 软件压缩库zlib (从磁盘读取时需要解压缩放入内存, 页面分裂时需要重新压缩) Split & Recompress & Rebalance when mlog overflows 空间收益 固定的页面压缩大小 – 给压缩的效果设置了一个固定的边界 Modification log和Page预留空间弱化了压缩带来的空间缩减 糟糕的实现 代码过于复杂而导致压缩和未压缩的表性能差距非常明显 ~~~ MariaDB与FusionIO合作利用NVMFS文件系统的特性，修改InnoDB的Page结构来支持文件系统级的压缩。 Page compression要求InnoDB做了如下配置： ~~~ innodb_file_per_table = 1 innodb_file_format = Barracuda. ~~~ 它的实现方法是，只在Page即将写入到文件系统时，才进行压缩，因此最终只有压缩后的容量被写入到磁盘，如果压缩失败，那么就把没有压缩的容量写入磁盘。另外还会对Page内的512字节的倍数的未使用空间清理掉，不占用实际存储： ~~~ fallocate(file, FALLOC_FL_PUNCH_HOLE | FALLOC_FL_KEEP_SIZE, off, trim_len); ~~~ 当页面被读取时，会在放入Buffer Pool之前进行解压缩，将原始页面载入内存。因此需要在文件头中加入一个新的Page type：FIL_PAGE_PAGE_COMPRESSED  综合起来可以这样定义一张表： ~~~ CREATE TABLE t3 (a int KEY, b int) DATA DIRECTORY=’/dev/fioa’ PAGE_COMPRESSED=1 PAGE_COMPRESSION_LEVEL=4 ATOMIC_WRITES=’ON’; ~~~ 意思是将t3表存到/dev/fioa盘，开启Page compression，采用4级压缩，开启原子写。 经过测试，可以看出，LZ4的压缩比例最好，而且，对性能影响非常小。  

## 背景 最近发布的MariaDB 10.1 Alpha版本，提交了一个改动，放宽了InnoDB Page<=16K的限制，将上限提高到64K。 从MDEV-6075需求文档中可以看出，目前只支持COMPACT的结构，DYNAMIC结构能否支持还在研究，COMPRESSED结构则确定无法支持。 ~~~ revno: 3987 committer: Jan Lindström <jplindst@mariadb.org> branch nick: 10.1 timestamp: Tue 2014-05-13 13:28:57 +0300 message: MDEV-6075: Allow > 16K pages on InnoDB This patch allows up to 64K pages for tables with DYNAMIC, COMPACT and REDUNDANT row types. Tables with COMPRESSED row type allows still only <= 16K page size. Note that single row size must be still <= 16K and max key length is not affected. ~~~ ## 业务应用 什么情况下需要64K这么大的页面呢？ 我们知道一个Page，不是所有的page_size都可以用来存数据，还有一些管理信息要存，例如页头和页尾（[InnoDB Page](https://raw.githubusercontent.com/jeremycole/innodb_diagrams/master/images/InnoDB_Structures/Basic%20Page%20Overview.png)）。 此外，InnoDB Buffer Pool管理页面本身也有代价，Page数越多，那么相同大小下，管理链表就越长。 因此当我们的数据行本身就比较长，尤其是做大块插入的时候，更大的页面更有利于提升如速度，因为一个页面可以放入更多的行，每个IO写下去的大小更大，就可以以更少的IOPS写更多的数据。 而且，当行长超过8K的时候，如果是16K的页面，就会强制转换一些字符串类型为TEXT，把字符串主体转移到扩展页中，会导致读取列需要多一个IO，更大的页面也就支持了更大的行长，64K页面可以支持近似32K的行长而不用使用扩展页。 但是，如果是短小行长的随机读取和写入，则不适合使用这么大的页面，这会导致IO效率下降，大IO只能读取到小部分有效数据，得不偿失。

TokuDB企业版提供热备功能(与社区版唯一的区别)。 该功能以plugin方式提供，当backup plugin加载后，它会拦截所有的文件操作(比如文件读写／目录操作等)，从而实现在备份的过程中增量同步，具体原理请看: [http://www.tokutek.com/2013/09/tokudb-hot-backup-part-1/](http://www.tokutek.com/2013/09/tokudb-hot-backup-part-1/)   [http://www.tokutek.com/2013/09/tokudb-hot-backup-part-2/](http://www.tokutek.com/2013/09/tokudb-hot-backup-part-2/)  社区版如何实现热备呢？ 官方推荐的方式是mylvmbackup，不过可能会有一些＂坑＂。 Percona的Vadim同学写过一篇[TokuDB tips](http://www.percona.com/blog/2014/07/15/tokudb-tips-mysql-backups/)，介绍了Percona在使用mylvmbackup热备TokuDB中遇到的＂坑＂及解决方法： 不能只备份TokuDB自身的数据以及日志文件，还要备份最新的binlog，否则启动的时候可能就＂跪＂了！ 还有一个比较geek的方式，直接基于TokuDB自身的机制，轻松的热备出一个备库。 上攻略： ~~~ 1) SET TOKUDB_CHECKPOINT_LOCK=ON; 2) 开始拷贝TokuDB的数据文件(不包含日志文件) 3) FLUSH TABLES WITH READ LOCK; 4) 记录binlog位置，拷贝最新的binlog和TokuDB的日志文件(*.tokulog) 5) UNLOCK TABLES; 6) SET TOKUDB_CHECKPOINT_LOCK=OFF; ~~~ ＂大杀器＂就是[TOKUDB_CHECKPOINT_LOCK](https://github.com/Tokutek/tokudb-engine/wiki/Checkpoint-Lock)，它的作用是允许拿到checkpoint锁，此时TokuDB的checkpoint会一直block到该锁释放(执行前要把tokudb_checkpoint_on_flush_logs关掉)，目的是防止拷贝TokuDB数据文件的过程中做sharp checkpoint(注意：由于不做checkpoint，TokuDB的日志文件会逐渐增多)，从而导致数据文件内部不一致(已拷贝的文件被修改)。 整个热备过程中，只有步骤4是阻塞写的，但耗时较短。

TokuDB里可调优的参数不多，今天把＂最重要＂的几个拉出来晒晒。 与性能相关的参数及说明: ~~~ tokudb_cache_size(bytes): 缓存大小，读写时候，数据会首先会缓存到这里。 默认大小为机器物理内存的一半。 tokudb_commit_sync(ON/OFF): 当事务提交的时候，是否要fsync log到磁盘。 默认开启(ON)，如果设置为OFF，性能会提升，但可能会丢失事务(commit记录到log buffer，但是未fsync到磁盘的事务)。 tokudb_directio(ON/OFF): 是否开启Direct I/O功能，TokuDB在写盘的时候，无论是否开启Direct I/O，都是按照512字节对齐的。 默认为OFF。 tokudb_fsync_log_period(ms): 多久fsync一下log buffer到磁盘，TokuDB的log buffer总大小为32MB且不可更改。 默认为0ms(此时做fsync的后台线程一直处于wait状态)，此时受tokudb_commit_sync开关控制是否要fsync log到磁盘(checkpoint也会fsync log buffer的，默认为1分钟)。 ~~~ 针对不同的使用场景： 1) 对数据要求较高(不允许丢失数据，事务ACID完整性)，只需根据内存调整tokudb_cache_size大小即可，建议开启tokudb_directio。 2) 对数据要求不太高(允许部分数据丢失，不要求事务ACID完整性)，可配置: ~~~ tokudb_commit_sync=OFF tokudb_fsync_log_period=1000 #1s ~~~ 在此配置下，每1秒对log buffer做下fsync，可充分利用log的group commit功能，如果TokuDB挂掉，则可能会丢失最多1秒的数据。

MariaDB 10.0.8 版本增加了一个CREATE OR REPLACE TABLE语法，这个语法的目的是让Replication更加可靠，为什么这个语句能让复制更可靠呢？ 例如用户使用CREATE ... SELECT语句，而这个语句回滚了又重新执行，备库有可能先收到一个CREATE语句，但是没收到INSERT的Events，主库重做一遍之后，备库收到CREATE语句时就会失败，而CREATE OR REPLACE则可以避免这个问题，存在的表会被替换掉。 最基本的使用例子： ~~~ CREATE OR REPLACE TABLE table_name (a int); ~~~ 这个语句其实等价于： ~~~ DROP TABLE IF EXISTS table_name; CREATE TABLE table_name (a int); ~~~ 这两个语句的执行结果。 * 如果 table_name被LOCK TABLES锁住了，CREATE OR REPLACE TABLE会忽略锁定，然后在语句执行完成后把新建的表加上锁定。 * 临时表只有在指定了TEMPORARY关键字时才会被DROP掉。（用DROP TABLE的话，同名的临时表会比普通表先被删除） 使用CREATE OR REPLACE TABL必须意识到的问题： * 表会首先被DROP掉（如果这张表存在的话），然后CREATE动作才会执行。正是因为如此，如果CREATE步骤失败了，那么执行这个语句后表可能会不存在了。如果表是被LOCK TABLES锁住的，那么表的锁会被释放掉先。 * OR REPLACE和IF EXISTS语句不可同时使用 * Slave在复制中当CREATE语句没有使用IF EXISTS标识时，会默认使用CREATE OR REPLACE语句来执行。这个行为可以通过slave-ddl-exec-mode变量来改变，设置为STRICT则不会做这个替换。 相关的新增参数： 　slave_ddl_exec_mode 　描述: Slave控制如何执行DDL的Event的模式。可选值有STRICT、IDEMPOTENT (默认值)。 　　在 IDEMPOTENT 模式下，Slave不会因为那些不会导致主备不一致的DDL执行失败而停止。 　　尤其是CREATE TABLE 会被当做 CREATE OR REPLACE TABLE，而 DROP TABLE 会被当做DROP TABLE IF EXISTS. 　默认值: IDEMPOTENT 　可选值: IDEMPOTENT, STRICT

MariaDB 10.0.8增加了一种新的执行计划——Extended Keys。 它充分利用了InnoDB的隐藏列来做执行计划，因为我们都知道InnoDB的索引组织表会把主键放在最末尾，所以实际上每个索引最后都包含了主键。 打开和关闭这个优化器选项的命令如下： Enable: ~~~ set optimizer_switch='extended_keys=on'; ~~~ Disable: ~~~ set optimizer_switch='extended_keys=off'; ~~~ MariaDB 10.0.8中默认选项是 'extended_keys=off'. MariaDB 10.0.9开始默认选项是 'extended_keys=on'. 看一个例子： 有一个DBT-3/TPC-H 测试中用到的SQL如下 ~~~ select o_orderkey from part, lineitem, orders where p_retailprice > 2095 and o_orderdate='1992-07-01' and o_orderkey=l_orderkey and p_partkey=l_partkey; ~~~ 这个查询是寻找发生在1992-07-01 并且零售价格高于2095的orderkeys. 通过 Extended Keys, 这个查询可以通过下面的计划执行: 扫描i_p_retailprice索引获得p_retailprice>2095的行，再从 extended keys中读取p_partkey（主键）的值。 对于每一个p_partkey的值，通过对lineitem表的i_l_partkey索引扫描，从 extended index中获取l_orderkey（主键）。 对于每一个被选中的l_orderkey值，再通过i_o_orderdate索引去查找o_orderkey（主键）的值。 这种访问方式所有的访问数据都没有回表，所以性能好的多。 下面是执行计划: ~~~ MariaDB [dbt3sf10]> explain -> select o_orderkey -> from part, lineitem, orders -> where p_retailprice > 2095 and o_orderdate='1992-07-01' -> and o_orderkey=l_orderkey and p_partkey=l_partkey\G *************************** 1\. row *************************** id: 1 select_type: SIMPLE table: part type: range possible_keys: PRIMARY,i_p_retailprice key: i_p_retailprice key_len: 9 ref: NULL rows: 100 Extra: Using where; Using index *************************** 2\. row *************************** id: 1 select_type: SIMPLE table: lineitem type: ref possible_keys: PRIMARY,i_l_suppkey_partkey,i_l_partkey,i_l_orderkey,i_l_orderkey_quantity key: i_l_partkey key_len: 5 ref: dbt3sf10.part.p_partkey rows: 15 Extra: Using index *************************** 3\. row *************************** id: 1 select_type: SIMPLE table: orders type: ref possible_keys: PRIMARY,i_o_orderdate key: i_o_orderdate key_len: 8 ref: const,dbt3sf10.lineitem.l_orderkey rows: 1 Extra: Using index 3 rows in set (0.00 sec) ~~~