论文部分内容阅读
当前数据中心单一服务器上的数据存储容量能够达到数十亿条键值( KV, Key-Value)对,并且单个键值对通常很小。如何有效地组织超大型键值存储系统使其支持快速访问是一项艰巨的工作。LSM-trie是一个基于日志结构合并树(LSM-tree, Log-Struct Merge-Tree)的面向海量小数据存储的超大型KV存储系统。相比LevelDB, LSM-trie采用前缀树结构和线性增长模式,有效地缓解写放大问题、减少定位数据时所需元数据体量,使得读写性能得到较大提升。但是LSM-trie仍存在两个问题:LSM-trie使用哈希方式组织数据,不支持范围查找;LSM-trie的串行查找机制限制了随机查找性能。 针对LSM-trie存在的问题,本文提出两种优化方案。针对范围查找问题,直接使用key排列数据以支持范围查找;采用RemainingTable和数据迁移策略来解决因取消SHA-1对key哈希计算后所导致的数据分布不均匀问题。针对随机读性能问题,优化了LSM-trie的查找流程,在Level0—Level3与Level4之间采用并行查找方式代替逐层串行查找方式,从而提高数据随机查找性能。 实验结果表明,相比于LevelDB,优化后的LSM-trie的范围查找性能提升最高达30%;相比于原LSM-trie,优化后的LSM-trie随机读性能提升最高达60%。