基于日志结构合并树的轻量级分布式索引实现方法

针对现有基于日志结构合并树(LSM-Tree)实现的分布式数据库仅支持高效的主键查询,无法让用户快速地应用在自己的集群中的问题,提出了基于LSM-Tree的轻量级分布式索引实现方法 SIBL。首先,通过对主键属性列建立索引来提高非主键属性的查询效率;然后,提出了分布式索引构建算法以及基于等距取样的索引区间划分算法,从而保证了索引在系统中的均匀分布,并且优化了传统索引的查询算法,将索引文件看作特殊的数据文件分布式地存储在系统中,从而保证了系统的负载均衡和可扩展性;最后,将该方法与华为二级索引方案HIndex在HBase数据库上进行实验来比较二者的索引构建的时间和空间开销、索引的查询性能和系统的负载均衡等性能,验证得出所提出的方法使查询性能提升了50~200倍。

面向时序数据的两阶段日志结构合并树文件合并框架

时序数据库中日志结构合并树(LSM-tree)在高写入负载或资源受限情况下的不及时的文件合并会导致LSM的C_0层数据大量堆积,从而造成近期写入数据的即席查询延迟增加。针对上述问题,提出了一种在保持面向大块数据的高效查询的基础上实现对最新写入的时序数据的低延迟查询的两阶段LSM合并框架。首先将文件的合并过程分为少量乱序文件快速合并与大量小文件合并这两个阶段,然后在每个阶段内提供多种文件合并策略,最后根据系统的查询负载进行两阶段合并的资源分配。通过在时序数据库Apache IoTDB上分别实现传统的LSM合并策略以及两阶段LSM合并框架和测试,结果表明与传统的LSM相比,两阶段的文件合并模块在提升策略灵活性的情况下使即席查询读盘次数大大降低,并且使历史数据分析查询性能提升了约20%。实验结果表明,两阶段的LSM合并框架能够提高近期写入数据的即席查询效率,提高历史数据分析查询性能,而且提升合并策略的灵活性。

面向键值存储的日志结构合并树优化技术

日志结构合并树(log-structured merge tree, LSM-Tree)是一种针对写优化的数据结构,广泛应用于当代主流键值存储系统之中,用于处理当今世界海量多样化的数据.LSM-Tree通过批量处理的方式将随机写请求转换为顺序写请求,以保持极高的写效率.但LSM-Tree仍存在2个不足:一是数据的流动方向是单向的且固定不变.存储在LSM-Tree底部的数据将被一直保留底部,直到它们成为旧数据被压缩操作删除.访问这些数据将使读放大问题变得更加严重.二是LSM-Tree中的数据分布并未考虑访问频率的影响,这将导致访问延迟不平衡的问题.访问高频的低层数据将产生更高的访问延迟.提出了一种基于访问频率分布的上浮式键值存储结构(floating key-value, FloatKV).FloatKV首先在内存中提出了一种新的数据存储结构(LRU and FIFO, LRFO),其次在外存中设计了一种基于访问频率分布的上浮式键值存储策略.FloatKV记录外存中数据的访问频率,并根据访问频率来调整数据的存储位置,以减少访问延迟.为了验证FloatKV的可行性以及性能,使用标准数据库性能测试工具YSCB(yahoo! cloud serving benchmark)来进行评估,并将FloatKV与当前主流的技术进行比较.实验结果表明,FloatKV能够显著地提高读效率,并有效地减少了读放大问题.

日志结构合并树的查询优化技术

针对基于日志结构合并树(Log Structured Merge Tree, LSM-tree)的数据库查询性能较差的问题,目前的研究工作主要集中在利用索引和缓存技术提升LSM-tree的查询性能.本文主要从以下几个方面对LSM-tree的查询优化技术进行了综述.第一,介绍了LSM-tree的基础架构,分析了影响查询的因素.第二,分析了当前的LSM-tree查询优化技术,包括索引优化技术和缓存优化技术.第三,分析了索引和缓存技术是如何提升基于LSM-tree的数据库查询性能的,并总结了一些现有的研究工作.最后,总结并给出了未来可能的研究方法.

面向内存表的可动态配置预写日志框架

通常情况下,NoSQL数据库管理系统启动后,其多个数据库或数据分区的预写日志(WAL)会固定地写入一个或多个日志文件,因而形成强耦合的对应关系。由于数据库逻辑模型与分区配置是由应用业务和计算环境所决定的,在预写日志被强耦合的情况下,数据库管理系统无法对预写日志的个数、大小等进行配置以实现性能调优。针对该问题,提出了一种面向内存表的可动态配置预写日志框架,该框架记录了重写日志,内存表可以动态地被分配给不同的预写日志队列,支持可变的对应关系,实现了预写日志与具体应用之间的解耦。在物联网时序数据库Apache IoTDB上实现了该框架,并进行了相关实验,结果表明使用可动态配置预写日志框架后可以找到比强耦合的预写日志更优的配置方案,写入性能可提高8%~19%,说明该框架能针对不同计算环境和应用负载实现动态性能调优。

基于SSD-SMR混合存储的LSM树键值存储系统的性能优化

大数据对存储系统的可扩展性、性能和成本等方面提出了更高的要求。瓦记录(Shingled Magnetic Recording,SMR)硬盘由于存储密度高、价格便宜,正逐步被广泛应用于大数据存储系统。但是,SMR硬盘的随机写性能较差,与快速的基于闪存的固态硬盘(Solid State Drive,SSD)一起构成混合存储时可以显著提升性能。同时,基于写优化的日志结构合并(Log-Structured Merge,LSM)树的键值存储已被广泛应用于许多NoSQL系统,如BigTable,Cassandra和HBase等。因此,如何基于新型的SSD-SMR混合存储构建出高性能的LSM树键值存储系统是一个具有很大研究价值的问题。首先建立基于SSD-SMR混合存储的LSM树键值系统的性能模型,然后针对SSD和SMR的硬件特征以及LSM树键值存储的软件特点,设计了一套面向SSD-SMR混合存储进行性能优化的LSM树键值存储系统,并基于LevelDB实现了该系统。在仅仅使用0.4%~2%空间的SSD的情况下,所提方法可以使SSD-SMR混合存储方案比普通磁盘方案的随机写性能提高20%,随机读性能提高5倍。

LSM树中基于热度预测的异构布隆过滤器方案

日志结构合并(Log-Structured-Merge,LSM)树中常使用布隆过滤器减少无效磁盘I/O.但是用户无法无限制地细化布隆过滤器的粒度,原因是在一些数据量庞大而数据项较小的工作流中,这些元数据需要占用大量存储空间.其次在一些内存受限的环境下,内存缓冲区无法容纳更多的过滤器数据,造成缓冲区与磁盘的频繁数据交换.针对上述问题本文提出LSM树中的异构布隆过滤器方案,在LSM树的每一层维护热度预测模型,新生成的SSTable通过预测的热度来分配不同粒度的布隆过滤器,然后使用特定缓存管理方案来维护缓存中的过滤器数据并处理工作流热度发生改变的情况.实验证明,本文的方案在保持相同外存占用与内存消耗的情况下,读取吞吐量比采用原始LSM树结构的LevelDB提升22%~53%.

基于birch聚类的可更新机器学习索引模型

为满足大数据时代下数据库系统高吞吐、低内存占用的索引设计需求,提出一种面向海量数据的基于birch聚类可更新机器学习索引模型。将数据集使用birch聚类进行划分,对分段数据分别使用前馈神经网络进行训练拟合,采用基于日志结构合并树延迟更新思路的异地插入策略,实现索引更新操作。使用真实数据集进行实验,其结果表明,相比传统索引和当前先进机器学习索引结构,该模型在检索速度上有一定提升,在插入性能、内存占用和训练时间上有较大优化。

基于更新热点感知的LSM-Tree查询优化

基于LSM-Tree的键值存储已经得到广泛使用。LSM-Tree通过将更新的数据缓存在内存中、随后批量写入磁盘的优化措施取得极高的写性能。然而,在基于LSM-Tree的键值存储中,被更新键值对的旧数据不会立即从存储系统中清除,导致整个存储系统中积累大量的无效数据,最终会显著降低键值存储的读性能。针对以上问题,提出一种更积极的压缩(compaction)方法,通过记录键值对更新的历史信息,识别出更新热点,在整个LSM-Tree存储系统中寻找无效数据大量聚集的SSTable,尽早实施压缩,清除无效数据,缓解写放大效应,从而提升读性能。实验表明,该方法能够降低LevelDB 65.2%的平均读时延、69.4%的99%读尾时延以及71.4%的写放大。

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

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

一种读写均衡的高性能键值存储系统

日志结构合并树(LSM-tree)因能利用外存设备的顺序访问性能,被广泛应用于键值存储系统的核心数据结构.由于LSM-tree层次化的、有序的数据组织结构需要通过大量的数据合并操作维护,故引起了严重的写放大效应.最近的研究工作提出了若干优化方案缓解LSM-tree的写放大,但是牺牲了查询性能和空间利用率.为此基于LSM-tree的键值存储系统提出一种新的架构,其核心设计是采用键值分离的方案降低数据合并开销,并以一种新型的树状结构vTree为值维护一定程度有序性,保障高效的范围查询;同时为vTree设计了相应的数据合并和空间回收方法.实验结果表明,基于该架构实现的键值存储系统在写入、点查询、范围查询各方面有均衡的高性能表现,且空间开销较低.

用于联盟链的布隆过滤器优化

布隆过滤器常用于联盟链Hyperledger Fabric状态数据库LevelDB的读性能优化,但布隆过滤器本身存在误报现象,且LevelDB只能对布隆过滤器进行统一配置而无法自适应调整。为此,提出一种单元化的部分计数式布隆过滤器(partial counting Bloom filter,PCBF)构造方案,设计可并行计算的元素插入与查询机制并结合双重哈希及非加密哈希来实现快速插入与查询;基于开启过滤器单元与访问次数构建排序字符串表优先级,使用时间片轮询算法对过滤器单元进行自适应调整,实现了资源的合理分配。实验结果表明:PCBF具有较高的插入效率,并能减少20%左右的误报数量,适用于联盟链的高并发场景。

基于增量学习的RocksDB键值系统主动缓存机制

由于分层结构的约束,基于日志结构合并(LSM)树的RocksDB键值存储系统面临着读取性能低下的问题。一种有效的解决方法是对热点数据进行主动缓存,但其面临两个挑战:一是如何在数据分布持续动态变化时对热点数据进行预测,二是如何将主动缓存机制与RocksDB存储结构衔接起来。针对这些挑战,基于预测分析技术,构建了由数据采集、系统交互、系统测试等部分组成的面向RocksDB键值系统的主动缓存框架,能够将热点数据缓存在LSM树的较低层级中;并对数据访问模式进行建模,设计并实现了基于增量学习的热点数据预测分析方法,能够有效减少存储介质的I/O访问次数。实验结果表明该机制能有效提升RocksDB在不同动态工作负载下的数据读取性能。

基于SCM与SSD的混合高效键值存储系统研究

具有高性能以及非易失特性的SCM(Storage Class Memory,存储级内存)技术逐渐成熟并开始运用到存储系统设计中,而传统的SSD仍然在存储容量上具有优势,为键值存储系统提供大容量存储的支持。现有键值存储系统不能充分发挥SCM与SSD混合存储架构的优势,需要对数据布局以及系统结构进行重新设计。针对SCM和SSD的特点,设计了基于SCM与SSD的混合式高效键值存储系统(SCM and SSD Hybrid Key-Valuestore,SSHKV)。SSHKV通过将键值存储中元数据信息存储到SCM中,将数据部分以日志方式存储到SSD中,实现性能与容量的兼顾。在SSD空间管理上,SSHKV采用逻辑空间放大策略,通过重映射TRIM指令释放的无效空间,减小了垃圾回收带来的数据迁移开销。SSHKV基于半异步半同步式IO模型实现,经过对比测试,SSHKV的随机写入性能相较于传统基于LSM-Tree的LevelDB提升了约20倍。