基于闪存固态硬盘内部并行机制的R-树优化方法

R-Tree Optimization Method Using Internal Parallelism of Flash Memory-Based Solid-State Drives

近年来,闪存固态硬盘内部结构有了很大的改进,使得它已拥有丰富的内部并行性.R-树是一种被广泛应用于空间数据管理的索引结构.但是,基于传统机械硬盘和闪存固有特点优化的R-树索引,并没有利用固态硬盘内部并行性来提高查询和更新效率.针对R-树索引,提出一种利用固态硬盘内部并行机制加速查询和更新的方法.首先,实现一种适合于固态硬盘内部并行性的异步I?O提交技术.在此基础上,针对R-树的查询和更新操作,通过聚集读写请求批量提交,以达到利用固态硬盘内部并行性加速的目的.此外,通过理论分析证明该优化方法,即使在并行通道只有4或者8时,依然可以提供1.86和2.93的期望加速比.通过真实数据在3款固态硬盘上的实验测试结果表明,利用优化策略的查询算法可实现高达3倍的稳定加速比,优化后的更新算法可达到2倍以上的加速比.无论是查询密集型或是更新密集型应用场景均有介于两者之间的加速比.

Recently, flash memory-based solid state disk has more magnificent improvement on internal design than before, which brings rich internal parallelism to solid state disk. R-tree index is widely applied in spatial data management, but up to now, the proposed R-tree optimization methods on solid state disk do not take the internal parallelism into consideration, and also the approach designed for traditional magnetic disk is not suitable for solid state disk. So all of the previous R-tree optimization doesn’t use internal parallelism mechanism of solid state disk to make the query and update operation more efficient. In order to exploit internal parallelism to speed up R-tree. Firstly, a parallel batch asynchronous I/O submitting library is realized. Secondly, optimizing algorithms to accelerate the R-tree search and update operations are achieved by aggregating read or write operations to batch submit through the previous library, Thirdly, we analyze the minimal speed up expectation theoretically, and prove that normal solid state can achieve speed up of at least 1.86 times expectation speed-up with 4 channels and 2.93 times expectation speed-up with 8 channels. Through the experiments on two kind of solid state disk, our optimization R-tree can achieve stable 3 times speed up for query operation compared with original R-tree, and also speed up of about 2 times for update operation. No matter for query intensive or update intensive application scenarios, there is speedup between them.