Monthly Archives: May 2014

介绍TokuDB存储引擎是Tokutek2009年发布的一个数据库存储引擎，于2013年4月开源。支持MySQL/MariaDB。它和InnoDB一样支持事务、MVCC。 特色： Franctal Tree而不是B-Tree 内部结点不仅有指向父子的指针还有Buffer区，数据写入先写buffer区，FIFO结构，写入只需要顺序添加到Buffer区就可返回，后续满时一次性刷新到下面的子树中，插入数据基本上是一个顺序添加的过程。可轻松应对随机IO，减少空间碎片。 出色的压缩性能 块大小默认是4MB 在线DDL数据结构： 一、Buffered Tree：类B-Tree，写时直接写到Root结点，如果Root结点满了，就把数据刷新到它子结点上，如果子结点满了就继续刷新到子子结点，一直这样下去。因此，只有当结点满时才有Disk Seek产生。Node大小可设置很大，比如4MB，为提高读，需要对Node做更细划分，分成小块，随机读IO复杂度也为O(logN)。 写： 写时不产生disk seek，因为总是先写Root，由于经常被操作，可认为树顶部结点一直在Page Cache中。 节点数据紧凑，大Node压缩有优势 天然适合做事务，没有undo log，叶子结点上做mvcc二、Fractal-Tree（Buffer-Tree的变种）buffered(4,16)-tree，OMT结构维护结点数据，大小4MB，nonleaf节点OMT结构，leaf节点多个OMT（4MB/64KB) OMT：Order Maintenance Tree元素用数组表示，具有父子关系的元素尽量相邻存储，cpu cache line（如果一个节点的周边节点能在文件中紧邻的被存储，当读取其中一个的时候，其他节点被prefetching出来，io数则可以减少。这就是vEB layout） 结点刷新：Node完成写时检查是否满足flush条件，满足加到flush队列，后台线程并行处理从队列中读取的任务。 CheckPoint：60秒一次，sharp checkpoint无Fuzz Checkpoint，会对所有索引加只读锁，其它线程写node时，会clone一个Node。做完后检查LSN，以清理无用的log。基本上这个操作不影响前台读写操作，但是因为会进行数据压缩和clone node、写磁盘的操作，会造成一定的性能波动。 Cache：LRU，写cache时添加node到cache链表，然后检查cache状态，设置了四个水平位（低水平位，低警示点，高警示点,高水平位），高于高水平位，客户端线程进入等待状态，超过低警示点，开始收集逐出数据。 三、读： KEY读：每次读数据都要从ROOT到LEAF，做数据合并，才能得到完整的ROW数据。 范围读：对树做深度优先遍历，在LEAF结点返回，痛苦。四、Schema Changes列修改：Broadcast类型的Message，从Root广播到每一节点，最后到达LEAF结点。（Mysql对列修改会先关闭表，再打开表，关闭时Tokudb会把脏Node写盘，有些性能消耗），腾讯的游戏运维部门在InnoDB上实现了类似的功能。 索引：两种索引，cst_（clustering index）和cvr_（covering index），每个都是一个单独的F-tree文件 offline方式：启动多个线程，遍历记录生成索引，速度快，但创建过程中写操作不可用。 hot方式：速度慢，创建过程读写不受影响log：log manager来管理log文件，无重做日志组的概念，当日志写满后重新生成一个文件继续写，checkpoint后检查数据都被刷新到磁盘后会删除，达到InnoDB类似的效果；分in … Continue reading →