基于LSM Tree的分布式索引实现

Distributed secondary index based on LSM Tree

近年来Log-Structured-Merge(LSM)Tree在NoSQL系统中得到了广泛地应用.主要是因为LSM Tree架构提出了延迟更新和批量写入的算法,将随机写转换为批量写,减少了磁盘臂的移动开销,从而大大地提升了数据库的写入性能.然而,读性能却也因此受到影响.LSM Tree和B Tree之间的本质区别使得NoSQL系统不适宜直接引用B Tree作为辅助索引结构.本文实现了LSM Tree下的一种分布式辅助索引结构,提出针对这种读写分离架构的索引批量加载策略,并对LSM Tree的查询计划树进行了缓冲优化,避免了重复的查询解析,使得索引读的性能得到了相应的提升.

In recent years, Log-Structured-Merge Tree has been widely used in NoSQL systems. This is mainly because it has proposed two algorithms： update delayed and batch write, convert random write to batch write, reducing the cost of moving the disk arm therefore the write performance of database has been enhanced greatly. However, the read performance of database has also been affected negatively. The essential difference between LSM Tree and B Tree makes NoSQL not suitable for using B Tree as index structure directly. This paper implements a distributed secondary index based on LSM Tree, and proposes a bulk loading method in this read and write separation architecture. We also do lots of works on the optimization of index query plan to avoid repeatly query parsing IO so that the performance of index read has been greatly improved.