MySQL高压缩引擎TokuDB 揭秘( 三 ) _TokuDB

文章插图

3,4,5,6,7,8,9是中间数据块，10,11,12,13,14,15,16,17是叶子数据块；
上图中，每个中间数据块的fanout是2，表示至多有2个下一级数据块；中间节点的msg buffer用来缓存下一级数据块的msg，橘黄色表示有数据，黄绿色表示msg buffer是空的。
如果需要读block11的数据，需要先把数据块3和数据块6中的msg apply到叶子数据块11，然后去11上读数据。
Msg apply的过程也叫合并（merge），所有基于LSM原理的k-v引擎（比方LevelDB，RocksDB）读数据时都要先做merge，然后去相应的数据块上读数据。
读合并

文章插图

如上图所示，绿色是中间数据块，紫色是叶数据块；中间数据块旁边的黄色矩形是msg buffer 。
如要要query区间[5-18]的数据

以5作为search key从root到leaf搜索>=5的数据，每个数据块内部做binary search，最终定位到第一个leaf块。读数据之前，判断第一个leaf块所包含的[5,9]区间存在需要apply的msg（上图中是6,7,8），需要先做msg apply然后读取数据（5,6,7,8,9）；
第一个leaf块读取完毕，以9作为search key从root到leaf搜索>9的数据，每个数据块内部做binary search，最终定位到第二个leaf块。读数据之前，判断第二个leaf块所包含的[10,16]区间存在需要apply的msg（上图中是15），需要先做msg apply然后读取数据(10,12,15,16);
第二个leaf块读取完毕，以16作为search key从root到leaf搜索>16的数据，每个数据块内部做binary search，最终定位到第三个leaf块。第三个数据块所包含的[17,18]区间不存在需要apply的msg，直接读取数据（17,18）。

优化range query
为了减少merge代价，TokuDB提供bulk fetch功能：每个basement node大小64K（这个是数据压缩解压缩的单位）只要做一次merge操作；并且TokuDB的cursor支持批量读，一个batch内读取若干行数据缓存在内存，之后每个handler::indexnext先去缓存里取下一行数据，只有当缓存数据全部被消费过之后发起下一个batch读，再之后handler::indexnext操作还是先去缓存里取下一行数据。

文章插图

Batch读过程由cursor的callback驱动，直接把数据存到TokuDB handler的buffer中，不仅减少了merge次数，也减少了handler::index_next调用栈深度。
异步合并
TokuDB支持后台异步合并msg，把中间数据块中缓存的msg逐层向下刷，直至leaf数据块。
这过程是由周期运行的cleaner线程完成的，cleaner线程每秒被唤醒一次。每次执行扫描一定数目的数据块，寻找缓存msg最多的中间数据块；扫描结束后，把msg buffer中的msg刷到（merge）下一层数据块中。

文章插图

前面提到，大部分写数据并不会把msg直接写到leaf，而是把msg缓存到root或者某一级中间数据块上。虽然promotion缓解了root块热点问题，局部热点问题依然存在。
假设某一个时间段大量并发更新某范围的索引数据，msg buffer短时间内堆积大量msg；由于cleaner线程是单线程顺序扫描，很可能来不及处理热点数据块，导致热点数据msg堆积，并且数据块读写锁争抢现象越来越严重。
为了解决这个问题，TokuDB引入了专门的线程池来帮助cleaner线程快速处理热点块。大致处理是：如果msg buffer缓存了过多的msg，写数据上下文就会唤醒线程池中的线程帮助cleaner快速合并当前数据块。
刷脏
为了加速数据处理过程，TokuDB在内存缓存数据块，所有数据块组织成一个hash表，可以通过hash计算快速定位，这个hash表被称作cachetable 。InnoDB也有类似缓存机制，叫做buffer pool（简记bp）。
内存中数据块被修改后不会立即写回磁盘，而是被标记成dirty状态。Cachetable满会触发evict操作，选择一个victim数据块释放内存。如果victim是dirty的，需要先把数据写回。Evict操作是由后台线程evictor处理的，缺省1秒钟运行一次，也可能由于缓存满由server上下文触发。
TokuDB采用激进的缓存策略，尽量把数据保留在内存中。除了evictor线程以外，还有一个定期刷脏的checkpoint线程，缺省60每秒运行一次把内存中所有脏数据回刷到磁盘上。Checkpoint结束后，清理redo log文件。
TokuDB采用sharp checkpoint策略，checkpoint开始时刻把cachetable中所有数据块遍历一遍，对每个数据块打上checkpointpending标记，这个过程是拿着client端exclusive锁的，所有INSERT/DELETE操作会被阻塞。标记checkpointpending过程结束后，释放exclusive锁，server的更新请求可以继续执行。