论文部分内容阅读
键值数据库由于其结构简单、查询速度快，具有高可靠性和高扩展性的特点，·得到了广泛的应用。各类应用对键值存储系统读写性能的要求也越来越高，要求存储设备提供更快的读写性能。Intel公司为了解决SSD和内存中存在的巨大性能差异，推出了Optane系列产品。傲腾固态盘作为非易失存储器的硬盘产品，有良好的读写性能同时随机读写与顺序读写性能差异不大。传统的键值存储系统采用LSM-Tree(Log Structure Merged Tree)将随机写转化成顺序写来提高系统的性能，但在新型介质傲腾固态盘下带来的收益有限。KVell采用内存和傲腾固态盘混合使用的方式，把索引信息记录在内存、数据记录在固态盘中，获得良好的性能，但在数据量过大、索引信息无法全部存入内存时读写性能下降明显且尾延严重。
本文基于傲腾固态盘优秀的随机读写性能，放弃了传统的LSM-Tree的数据结构，采用类似于B+树的数据组织方式，设计了一个BagTree的数据结构。一方面，BagTree使用树型结构组织数据，通过给叶子节点增加背包节点来扩充其容量的方式，保证了叶子节点空间合理利用的同时也灵活的控制了树形结构里中间节点的数量，使得BagTree能在内存较小时也正常使用。另一方面，BagTree使用多层结构的私有缓存，通过给不同层缓存结构设置不同的淘汰级别以及淘汰算法，使得BagTree树形结构的中间节点常驻内存，叶子节点和背包节点通过多层LRU的方式进行缓存替换，以提高存储系统的效率。
测试结果显示，BagTree的随机读性能是LevelDB的30倍，是rocksDB的20倍，是KVell的1.7倍，随机写性能是LevelDB的3倍、RocksDB的2倍，略好于KVell。YCSB测试中，在单线程单队列测试，BagTree读性能是LevelDB和RocksDB的2倍以上，写性能是LevelDB和RocksDB的6倍以上；在多线程多队列测试，BagTree性能最高达到1441KIOPS，性能是KVell的2倍，且尾延也低于KVell。
本文基于傲腾固态盘优秀的随机读写性能，放弃了传统的LSM-Tree的数据结构，采用类似于B+树的数据组织方式，设计了一个BagTree的数据结构。一方面，BagTree使用树型结构组织数据，通过给叶子节点增加背包节点来扩充其容量的方式，保证了叶子节点空间合理利用的同时也灵活的控制了树形结构里中间节点的数量，使得BagTree能在内存较小时也正常使用。另一方面，BagTree使用多层结构的私有缓存，通过给不同层缓存结构设置不同的淘汰级别以及淘汰算法，使得BagTree树形结构的中间节点常驻内存，叶子节点和背包节点通过多层LRU的方式进行缓存替换，以提高存储系统的效率。
测试结果显示，BagTree的随机读性能是LevelDB的30倍，是rocksDB的20倍，是KVell的1.7倍，随机写性能是LevelDB的3倍、RocksDB的2倍，略好于KVell。YCSB测试中，在单线程单队列测试，BagTree读性能是LevelDB和RocksDB的2倍以上，写性能是LevelDB和RocksDB的6倍以上；在多线程多队列测试，BagTree性能最高达到1441KIOPS，性能是KVell的2倍，且尾延也低于KVell。