本发明属于数据存储，具体涉及一种使用底层信息建立查询索引的lsm-tree键值存储系统。
背景技术：
：：1、由于互联网的普及、个人电脑(pc)互联网逐步向移动互联网发展，数据库的应用场景不断丰富，并随着工业互联网、能源互联网、智慧城市、智慧医疗、车联网、金融科技、智慧教育、数据乡村等数字化发展项目的提出，数据规模飞速增长。市场规模不断提高，这给数据的存储和分析带来了巨大的挑战。高效且安全的存储是对海量数据分析处理利用的基础，为了应对数据规模不断增加带来的挑战，存储系统和存储硬件也在不断的发展进化。而由于数据的类型逐渐丰富，内容逐渐多样化，关系型(sql)数据库在步入21世纪后逐渐向可扩展性更好的非关系型的(nosql)数据库发展，并得到了广泛的应用。2、在非关系型数据库中包含键值数据库、时序数据库、图数据库、向量数据库、文档数据库、列式数据库等。在ccsa tc601的统计中，键值数据库共82个，占非关系型数据库344个中的23.8％，在非关系型(nosql)的数据库中占比最高。键值数据库的特点是采用键值对来存储数据，结构简单易理解，典型系统包括bigtable、redis、memcached、rocksdb、leveldb、forestdb。而键值存储数据库中，日志结构合并树(lsm-tree)作为键值存储系统中应用最广泛的一种写优化型的分层数据结构，通过追加写(append only)日志的形式将数据写入到内部有序的数据块有序字符串表(sorted string table，简称为sstable)之中。由于其充分利用了磁盘的写入特性，极大提高了写入(put)性能；之后，日志结构合并树(lsm-tree)通过将删除和修改的操作转化为写入操作，避免了每次修改和删除前的查询操作，以这种被称为异地(out-of-place)的更新方式，提升了删除(delete)和修改(update)的性能。但是这些操作会破坏掉数据间的关系，使查询(query)过程成为了一个难题。故日志结构合并树(lsm-tree)提出分层的想法，将所有数据的整体结构划分为存储量逐渐提升的多层结构，从上而下逐层存储数据；而后经过压缩(compaction)操作，使各层的数据会变为有序状态，这样就可以在每层中通过二分查找比较快的进行点查询(point query)操作，同时有序的数据也很利于范围查询(range query)操作。为了进一步提升查询性能，日志结构合并树(lsm-tree)还在有序字符串表(sstable)中加入了数据范围和布隆过滤器(bloomfilter)，提升查询(query)过程中对数据块的筛选速度。这些特性使得日志结构合并树(lsm-tree)在键值存储系统中占据了重要的地位。3、但是日志结构合并树(lsm-tree)的设计也导致了一些新的问题，那就是读写放大和空间放大。4、1.读放大(read amplification)：5、在进行点查询时(point query)时由于各层中存储数据的有序字符串表之间有序，且有序字符串表内部数据也都处于有序状态，所以在点查询(point query)时，日志结构合并树(lsm-tree)会从上至下挑选读取有序字符串表的头文件，并根据头文件中记录的该文件范围和布隆过滤器(bloom filter)对有序字符串表进行筛选。由于数据均是以追加写(append only)的方式写入至日志结构合并树(lsm-tree)中，故从上而下寻找到的第一个值即为最新值。通过这种方式，可以避免日志结构合并树(lsm-tree)中所存储值的多版本问题。6、在进行范围查询(range query)时，由于各层中存储数据的有序字符串表之间有序，且有序字符串表内部数据也都处于有序状态，所以在范围查询(range query)时，日志结构合并树(lsm-tree)会从上至下通过有序字符串表的头文件挑选各层中范围内的数据块，最后将所有符合要求的有序字符串表读取到内存中，并进行排列整合最后输出查询的结果。7、2.写放大(write amplification)：8、写放大指的是实际写入传统硬盘驱动器(hard disk drive,hdd)/固态硬盘(solid state drive,ssd)的数据大小和程序要求写入数据大小之比。在进行压缩(compaction)的操作时，会不断的将数据读出，进行合并(merge)和排序(sort)后再写入，导致数据实际写入量远大于程序要求写入量。9、3.空间放大(space amplification)：10、因为所有的写入都是顺序写入的，并以异地更新(out-of-place update)，而非原地更新(in-place update)的方式进行删除(delete)和修改(update)，所以过期数据不会马上被清理掉，从而会继续占用空间。11、综上所述，在基于日志结构合并树(lsm-tree)的键值存储领域展开研究，研究如何优化现有的键值存储系统，既保留其优异的性能，又尽可能的减小读放大、写放大和空间放大的带来的影响，研究并实现一个性能更优的键值存储系统，是十分有必要且值得去做的。技术实现思路1、针对上述问题，本发明公开了一种使用底层信息建立查询索引的lsm-tree键值存储系统(bivxdb)，该系统使用底层信息建立查询索引的底层信息倒排索引(bottominformation invert index，简称为bivx)，可以加速lsm-tree键值存储系统的查询操作。2、bivx利用lsm-tree的底层存储单元文件——有序字符串表的边界为索引键，通过lsm-tree键值存储系统中的压缩过程遍历生成的有序字符串表中的所有键值对，将与索引键的范围相交的上有序字符串表的文件编号作为索引值构建索引。在查找过程中，利用索引，首先从lsm-tree的底层找出目标键值对存在的范围，之后通过索引寻找出可能包含目标值的所有有序字符串表的文件编号，之后利用字符串表的边界值信息与自身的布隆过滤器对目标值是否存在于表中进行判断。使用bivx本发明可以充分利用lsm-tree的写入优势而不牺牲其查询性能。3、本发明构建了bivxdb，这是一个结合了bivx索引的单lsm-tree键值存储系统。通过整合压缩阶段顺便地构建bivx，使bivxdb同时实现了低写放大和快速搜索。4、本发明的技术方案包括以下技术内容。5、一种使用底层信息建立查询索引的lsm-tree键值存储系统，所述系统包括：内存数据存储模块、lsm-tree结构的磁盘数据存储模块和索引模块；6、内存数据存储模块，用于生成存储数据的memtable数据结构，并在所述memtable数据结构被写满数据后，将该memtable数据结构转化为immutable memtable数据结构的同时，生成新的memtable数据结构来继续承接写入的数据；7、磁盘数据存储模块，用于将immutable memtable数据结构转换为有序字符串表文件后存储到lsm-tree结构的l0层，并在lsm-tree结构的li层中的文件数达到阈值后进行压缩操作，将生成的有序字符串表存入到lsm-tree结构的li+1层；其中，i为自然数；8、索引模块，用于构建底层信息倒排索引；其中，所述底层信息倒排索引的索引键为lsm-tree结构底层的有序字符串表文件的边界值，所述底层信息倒排索引的索引值为lsm-tree结构底层中有序字符串表文件的文件号。9、进一步地，在所述压缩操作的输入文件为非底层的有序字符串表文件，输出文件为写入到底层的有序字符串表文件的情况下，更新所述底层信息倒排索引的过程包括：10、获取输出文件的索引键；11、将该输出文件的索引键插入到底层信息倒排索引的同时，在底层信息倒排索引的所有索引值中删除输入文件对应的文件号，以得到更新后的底层信息倒排索引。12、进一步地，在所述压缩操作的输入文件为底层的有序字符串表文件，输出文件为写入到底层的有序字符串表文件的情况下，更新所述底层信息倒排索引的过程包括：13、步骤s31：获取输出文件的索引键；14、步骤s32：判断底层信息倒排索引中是否与所述输出文件的索引键的范围存在交集；15、步骤s33：如果底层信息倒排索引中存在与所述输出文件的索引键的范围存在交集，则跳转到步骤s34，否则跳转到步骤s38；16、步骤s34：备份底层信息倒排索引中的原索引键，并将该原索引键从底层信息倒排索引中删除；17、步骤s35：将输出文件的索引键插入到底层信息倒排索引；18、步骤s36：对比原索引键和插入到底层信息倒排索引的新索引键的索引值交集，并有交集的索引值复制到新索引键之中，得到初步更新后的底层信息倒排索引；19、步骤s37：在初步更新后的底层信息倒排索引的所有索引值中删除输入文件对应的文件号，得到更新后的底层信息倒排索引；20、步骤s38：将该输出文件的索引键插入到底层信息倒排索引的同时，在底层信息倒排索引中删除输入文件的索引键，以得到更新后的底层信息倒排索引。21、进一步地，在所述压缩操作的输入文件为非底层文件，输出文件为写入到非底层的文件的情况下，更新所述底层信息倒排索引的过程包括：22、按照底层信息倒排索引中的索引键构建一标记列表；23、在标记压缩过程输出的键值对与各索引键代表的数据区域有交集的情况下，将该数据区域标记在标记列表中；24、根据标记列表更新底层信息倒排索引，并删除底层信息倒排索引中特定的索引值；其中，所述特定的索引值包括：过期的索引值、与边界值不想交的索引值和与该数据区域不相交的索引值。25、进一步地，在所述压缩操作的输入文件为底层文件，输出文件为写入到非底层的文件的情况下，更新所述底层信息倒排索引的过程包括：26、遍历压缩过程时输出的所有键值对，其中，该压缩过程是输入文件为非底层文件且输出文件为写入到非底层的文件的压缩过程；27、将键值对的信息插入到当前的底层信息倒排索引之中；28、将输入文件的信息删除，将该输入文件的信息备份到第一个大于要删除索引键的区域之中；29、在底层信息倒排索引后端存储一个最大值标记信息来缓冲，以使该最大值标记信息从lsm-tree的n层删除并逐步存储到max区域后，过渡到lsm-tree的第n+1层之中。30、进一步地，所述系统还包括：信息同步模块，所述信息同步模块用于将底层信息倒排索引中的索引信息同步存储到磁盘中。31、一种基于权利要求上述任一所述lsm-tree键值存储系统的范围查询方法，包括：32、步骤s71：构建一迭代器；33、步骤s72：利用所述迭代器对memtable数据结构中的数据进行范围查询，并将基于memtable数据结构得到的筛选文件加入到迭代器后，跳转到步骤s73；34、步骤s73：利用所述迭代器对immutable memtable数据结构中的数据进行范围查询，并将基于immutable memtable数据结构得到的筛选文件加入到迭代器后，跳转到步骤s74；35、步骤s74：利用所述迭代器对lsm-tree结构的l0层中的有序字符串表文件进行范围查询，并将基于lsm-tree结构的l0层得到的筛选文件加入到迭代器后，跳转到步骤s75；36、步骤s75：在底层信息倒排索引中获取满足查询条件的有序字符串表文件的文件号，并将基于底层信息倒排索引得到的筛选文件加入到迭代器后，跳转到步骤s76；37、步骤s76：综合基于memtable数据结构得到的筛选文件、基于immutable memtable数据结构得到的筛选文件、基于lsm-tree结构的l0层得到的筛选文件以及基于底层信息倒排索引得到的筛选文件，得到符合该查询条件的范围查询结果。38、进一步地，所述对有序字符串表文件进行处理，包括：39、在有序字符串表文件中筛选出目标范围内的数据；40、对筛选出的数据进行合并和/或更新，以生成初步查询结果；41、对初步查询结果进行排序，得到符合查询条件的范围查询结果。42、一种基于上述任一所述lsm-tree键值存储系统的点查询方法，包括：43、步骤s91：获取符合查询条件所对应的目标键；44、步骤s92：在memtable数据结构进行目标键查询，并在获取到该目标键时，跳转到步骤s97；否则，跳转到步骤s93；45、步骤s93：在immutable memtable数据结构进行目标键查询，并在获取到该目标键时，跳转到步骤s97；否则，跳转到步骤s94；46、步骤s94：在lsm-tree结构的l0层进行目标键所对应的目标值查询，并基于该目标值获取到该目标键时，跳转到步骤s96；否则，跳转到步骤s95；47、步骤s95：基于底层信息倒排索引定位到可能包含目标键的键值范围，并通过布隆过滤器对该可能包含目标键的键值范围进行筛选后，跳转到步骤s96；48、步骤s96：输出符合查询条件的点查询结果。49、一种基于上述任一所述lsm-tree键值存储系统的数据写入方法，包括：50、将原始数据写入memtable数据结构；51、在所述memtable数据结构达到容量上限时，将该memtable数据结构转化为immutable memtable数据结构的同时，生成新的memtable数据结构来继续承接写入的数据；52、将immutable memtable数据结构转换为有序字符串表文件后存储到lsm-tree结构的l0层；53、在lsm-tree结构的li层中的文件数达到阈值后进行压缩操作，将生成的有序字符串表存入到lsm-tree结构的li+1层；其中，i为自然数；54、基于lsm-tree结构底层的有序字符串表文件的边界值将数据空间划分为若干个数据域，并使用与各数据域有交集的有序字符串表文件的文件号来填充底层信息倒排索引。55、与现有技术相比，本发明的有益效果如下：56、1.高性能的点查询及范围查询能力。57、本发明根据lsm-tree存储于底层的有序字符串表文件的边界信息作为索引键，将整个数据域划分成多个区域；并将上层有序字符串表中的键值对与划分后的数据域进行比较，将与底层数据域有明确交集的有序字符串表的文件号作为索引值记录于索引之中。在无论点查询还是范围查询的过程中，本发明都可以直接通过索引中存储的范围信息直接筛选出需要查询和读取的有序字符串表文件，这样就可以跳过lsm-tree原有的逐层遍历过程，大大节约了查询阶段的时间开销，可以显著提升系统的点查询与范围查询能力。58、2.低开销的索引建立过程。59、本发明利用lsm-tree的压缩过程进行索引建立，在该过程中建立索引的原因是：首先其会删除过期的文件并插入新的文件，会对原有数据库中的文件进行集中的修改，这时就需要对索引进行同步的更新；其次，在该过程中，有序字符串表会被从磁盘中读取到内存中，其中的键值对会被遍历，这个有序字符串表中所有键值对被遍历的窗口期可以使本发明准确的将信息记录于索引之中，可以避免原有的只记录有序字符串表的边界值和布隆过滤器所造成的查找误读问题。根据以上两个原因，本发明在压缩阶段进行索引的建立，且由于索引建立过程集合于压缩阶段之中，并未大量的引入新的文件i/o开销，所以本系统实现了低成本，高回报的索引构建过程。当前第1页12当前第1页12
技术特征：1.一种使用底层信息建立查询索引的lsm-tree键值存储系统，其特征在于，所述系统包括：内存数据存储模块、lsm-tree结构的磁盘数据存储模块和索引模块；
2.根据权利要求1所述的系统，其特征在于，在所述压缩操作的输入文件为非底层的有序字符串表文件，输出文件为写入到底层的有序字符串表文件的情况下，更新所述底层信息倒排索引的过程包括：
3.根据权利要求1所述的系统，其特征在于，在所述压缩操作的输入文件为底层的有序字符串表文件，输出文件为写入到底层的有序字符串表文件的情况下，更新所述底层信息倒排索引的过程包括：
4.根据权利要求1所述的系统，其特征在于，在所述压缩操作的输入文件为非底层文件，输出文件为写入到非底层的文件的情况下，更新所述底层信息倒排索引的过程包括：
5.根据权利要求4所述的系统，其特征在于，在所述压缩操作的输入文件为底层文件，输出文件为写入到非底层的文件的情况下，更新所述底层信息倒排索引的过程包括：
6.根据权利要求1至5任一所述的系统，其特征在于，所述系统还包括：信息同步模块，所述信息同步模块用于将底层信息倒排索引中的索引信息同步存储到磁盘中。
7.一种基于权利要求1至6任一所述lsm-tree键值存储系统的范围查询方法，其特征在于，所述范围查询方法包括：
8.根据权利要求7所述的范围查询方法，其特征在于，所述对有序字符串表文件进行处理，包括：
9.一种基于权利要求1至6任一所述lsm-tree键值存储系统的点查询方法，其特征在于，所述点查询方法包括：
10.一种基于权利要求1至6任一所述lsm-tree键值存储系统的数据写入方法，其特征在于，所述数据写入方法包括：
技术总结本发明公开一种使用底层信息建立查询索引的LSM‑Tree键值存储系统，属于数据存储技术领域。该系统利用LSM‑Tree的底层SSTable边界为索引键，通过压缩过程遍历生成的SSTables中的所有键值对，将与索引键的范围相交的上层SSTable文件编号作为索引值构建索引。本发明加速LSM‑Tree键值存储系统的查询操作。
技术研发人员：周江,姚泽坤,古晓艳,李波,王伟平
受保护的技术使用者：中国科学院信息工程研究所
技术研发日：技术公布日：2024/12/17
