ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2018, Vol. 55 ›› Issue (9): 2066-2082.doi: 10.7544/issn1000-1239.2018.20180254

所属专题: 2018新型存储系统结构前沿技术专题

• 系统结构 • 上一篇    下一篇

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

陈玉标1,李建中1,李英姝1,2,李发明1,高宏1   

  1. 1(哈尔滨工业大学计算机科学与技术学院 哈尔滨 150001); 2(佐治亚州立大学计算机科学与技术学院 佐治亚州亚特兰大 30303) (chenyubiao@hit.edu.cn)
  • 出版日期: 2018-09-01
  • 基金资助: 
    国家重点研发计划项目(2016YFB1000703) This work was supported by the National Key Research and Development Program of China (2016YFB1000703).

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

Chen Yubiao1, Li Jianzhong1, Li Yingshu1,2, Li Faming1, Gao Hong1   

  1. 1(College of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001); 2(College of Computer Science and Technology,Georgia State University, Atlanta, Georgia 30303)
  • Online: 2018-09-01

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

关键词: 固态硬盘, 内部并行性, 批量提交, R-树, 加速比

Abstract: 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.

Key words: solid state disk, internal parallelism, batch submit, R-tree, speed up

中图分类号: