目前在科学研究如地质考察, 城市规划等活动, 以及各种基于LBS(Location Based Service)的生活类应用中产生了大量与空间二维坐标相关的数据, 如何组织和管理这些数据是当前需要面临的一个问题.在一些高频率产生空间数据的场景下, 传统的关系型数据库不能提供较好的支持, 新型的NoSQL(Not only SQL)数据库缺少二级索引相关的设计.因此, 为了满足高频率的空间数据存取和组织的需求, 针对空间二维坐标数据开发对应的存储架构是有必要的.
键值对数据库(Key-Value数据库, 简称KV数据库)是近年来新兴的一种NoSQL数据库. KV数据库中数据以Key-Value的对应形式组织、存储.这种特性使其在存储二元数据时相比传统关系数据拥有更好的读写性能.但是KV数据库在设计上只能通过key找到对应的value, 无法根据value反向查找key.为了适应空间查找的场景, 需要在KV数据库上引入value上的二级索引.
LevelDB[1]是由Google的两位员工Sanjay Ghemawat, Jeff Dean开发的开源KV数据库, 具有着如下特点:
(1) LevelDB是持久化的KV存储系统, 运行占用内存低, 数据安全性和持久性有保障.
(2) LevelDB是有序的, 数据按照主键进行排序, 也可以自定义排序规则.
(3) LevelDB支持数据快照(snapshot), 使用快照查询数据不会受到后续读写操作的影响, 可以保证一致性.
(4) LevelDB支持数据压缩, 便于减小存储空间和提高I/O.
LevelDB使用了LSM-tree(Log-Structured Merge-tree)作为存储架构, 将随机写入转化为顺序写入, 极大地提高了数据库的写入性能. LevelDB的存储分为由跳表组成的内存存储和由SSTable(Sorted String Table)组成的磁盘存储, 而磁盘存储的SSTable又分为若干个level. LevelDB的这种设计缓解了将数据存储在一个文件中带来的存储和读写压力, 但是也为二级索引的设计带来了问题.
对于空间坐标的存储和索引问题目前有若干种解决方案, R-tree[2]是其中性能较为出色的一种.在一维数据的场景下, B-tree是目前公认的性能较好的索引结构, R-tree将B-tree的思想扩展到了高维空间, 引入MBB(Minimum Bounding Box)的概念, 将一维数据的比较转换为空间中交叉关系和包含关系的比较.由此R-tree构建了一棵可以存储高维数据的平衡树.
本文调研了目前在LSM结构上构造二级索引的研究成果, 从索引的结构、维护、一致性能等角度做了具体的设计.结合LevelDB和R-tree实现了一个支持二维坐标存储与索引的数据库系统.本文的主要贡献如下:
(1) 综合LSM结构的特点设计了完整的二级索引查询、存储和维护方案.
(2) 基于LevelDB实现了二维坐标二级索引的设计, 并拥有较好的读写性能.
本文后续结构为:第1节介绍LSM结构的特点和当前基于LSM的二级索引的国内外研究现状; 第2节介绍二级索引的具体设计和实现; 第3节通过一系列实验测试二级索引的性能; 第4节总结二级索引所做的工作并展望未来研究的方向.
1 研究现状二级索引源于关系型数据库中非聚簇索引的概念.在关系型数据库中, 聚簇索引是索引结构与数据存储物理结构一致的一种索引, 索引指向的地址即是数据实际物理存储的地址, 通常用于主键.非聚簇索引记录的物理顺序与逻辑顺序没有必然的联系, 与数据的存储物理结构也没有关系.关系型数据库中的二级索引通常建立在非主键列上, 指向的是主键的值.根据二级索引查找时, 先通过二级索引找到主键, 再根据主键找到数据记录的位置.关系型数据库中的二级索引技术较为成熟, 但是在NoSQL数据库中, 由于数据库结构和设计思路的多样化, 需要针对不同的结构设计合适的二级索引.因此如果要为LevelDB设计二级索引, 首先需要了解LSM-tree的结构和目前在LSM结构上二级索引的研究进展.
1.1 LevelDB与LSM-tree结构LevelDB的核心架构LSM-tree并非传统的多叉树结构，而是由多个SSTable以不同的level组织在一起构成.图 1展示了LevelDB的存储, 分为内存存储和磁盘存储两个方面.内存存储被称为MemTable, 以跳表作为存储结构.发生插入操作时先将数据顺序写入log文件中持久化, 随后将其插入到MemTable中.当MemTable的容量达到上限时将其锁定并转换为Immutable MemTable, 同时生成新的MemTable, 被锁定的MemTable随后会被dump到磁盘上形成一个新的SSTable.磁盘存储由SSTable组成, SSTable分为若干个level, 由MemTable直接dump到磁盘上的SSTable处于level0层, 下一层的SSTable由上一层的SSTable通过合并生成, 每一层的SSTable数量和容量依次提高, LevelDB由此得名.
|
图 1 LevelDB的LSM-tree结构 Fig.1 LSM-tree structure of LevelDB |
LevelDB没有更新操作, 每一条记录在插入的时候都有一个递增的SequenceNumber, 同一个key在LevelDB中可能有多个SequenceNumber不同的value, 在进行合并操作时, 同一个key只有最近插入的一个值会被保留. LevelDB的删除也不是直接在调用删除接口时删除, 而是插入一个删除标记, 在合并时会将数据物理删除.
LevelDB在查询数据时根据MemTable, Immutable MemTable再到level0的SSTable逐层向下的顺序查找, 直到找到第一个符合要求的记录为止.由于SequenceNumber的引入, LevelDB存在快照(Snapshot)的概念.快照指定了一个SequenceNumber, 使用该快照进行查询只会查询到不大于该SequenceNumber的结果.
1.2 LSM上的二级索引研究现状目前对LSM上的二级索引研究主要集中在索引结构, 索引维护和分布式索引[3]几个方面.以下对这几个方面的研究分别进行概述.
(1) 索引结构方面, 针对字段为字符串类型的二级索引有Log-Structured Inverted Index[4]结构, 这种结构对需要进行索引的字段进行倒排索引, 然后根据重要性和更新频率分别存储在磁盘和内存中.针对空间索引例如地理标记坐标的数据, 常使用基于LSM结构的R-tree, DHB-tree(Dynamic Hilbert B+-tree), Spatial Inverted File (SIF)[5]等技术.为了在多个索引文件中迅速找到有效的索引文件, 还可以对每个索引文件创建过滤器, 但是这种方案一般应用在和时序相关且界限分明的数据上.根据二级索引key列表的维护方式, 可以将二级索引分为主动更新和懒更新两种方式[6].主动更新方式下每次插入数据时都会更新全局的二级索引列表, 这种方式速度快但会造成严重的写放大.懒更新方式维护多个分散的索引列表, 每次更新单独的索引列表, 通过一定的策略在后台保持索引文件的有效性.
(2) 索引维护方面, 需要面对的最大问题就是如何保持二级索引和主索引更新的一致性.对此Diff-Index[7]提出了4种二级索引更新的策略: sync-full, sync-insert, async-simple和async-session.二级索引的更新操作通常分为插入新数据和删除旧数据两部分, 对于LSM结构来说插入操作较为简单, 但是删除操作由于需要先查找旧的数据再删除, 导致效率很低. sync-full模式下插入和删除操作同时进行, 这种模式查询速度快但是插入较慢. sync-insert模式只进行插入操作, 旧的数据一直保留, 直到被查询出来后进行校验删除. aysnc-simple模式异步执行插入和删除操作, 通过维护一个异步更新队列保证最终结果按照正确的顺序执行. aysnc-session对aysnc-simple模式进行了改进, 通过session将更新操作保存到客户端的缓存中, 减轻了服务器端的压力.
(3) 分布式索引方面, 主要有全局二级索引和本地二级索引两种实现[8].全局二级索引维护一张包含着所有二级索引和其对应主键的表格, 这种方法易于实现但是会在插入数据时产生较高的时延.本地二级索引方式下每个节点独立维护自己的二级索引, 这种方式虽然不会产生额外的时延, 但是在查询时需要遍历所有的节点.为了提高分布式索引的更新效率, 可以使用增量表的方式先把更新操作生成为一个增量表, 随后将增量表分发到子节点上.
2 二级索引的设计 2.1 设计思路在LevelDB上添加二级索引的目标是使其可以支持对空间二维数据的快速查找, 同时尽量不影响LevelDB本身的查询性能.首先, 从读写两个方面对LevelDB的架构进行分析. LevelDB在执行写操作时会先将Put请求封装成WriteBatch批量写请求, 随后直接写入内存中, 等到合并阶段再进行持久化.对于更新和删除操作, LevelDB也不会立刻对原数据进行改动, 而是插入新的值或插入删除标记, 这会导致在同一时间内一个key会存在多个不同版本的值, 而这些不同版本的值根据LevelDB生成的SequenceNumber进行区分.这就意味着二级索引为了和主索引保持数据的一致性, 也需要具备即时插入、延迟更新的特性.从读的角度来看, LevelDB的读操作依照MemTable, Immutable MemTable, 低level的SSTable, 高level的SSTable的次序读取, 直到读取到第一个符合key的value为止.因为根据二级索引查询到的是主键key的值, 但是二级索引在查询出结果后由于延迟更新的原因不能保证查到的值是否有效, 所以需要在二级索引查出key值后再用key去查询主索引进行校验.这会导致二级索引查询实际包含了查询二级索引和查询主索引校验两个部分, 会极大降低二级索引的查询效率, 因此需要为二级索引设计缓存以提高查询速度, 并使用SequenceNumber减少校验次数.
其次, 从LevelDB的LSM结构分析, LevelDB的合并操作根据数据分布的特点可以分为两类, 第一类是内存中的MemTable直接dump到磁盘上, 生成level0的SSTable, 这一层的SSTable每个表内部有序, 但是整体无序, 不同的SSTable之间存在数据范围的交叉.第二类是level0及以上的SSTable合并到更上一层的level, 生成新的SSTable, level0以上的level里的SSTable每个表内部有序, 且所有的表整体有序.从文件大小和更新频率来说, level0的SSTable生成频率高, 合并频率高且文件之间无序, level0以上的SSTable生成频率低, 合并频率低且有序.为了配合LevelDB的LSM结构, 本文提出了同样是LSM结构的二级索引架构.图 2展示了二级索引的架构设计.
|
图 2 二级索引架构 Fig.2 Secondary index structure |
二级索引分为3种类型, 分别索引MemTable中的数据, 每个level0中SSTable的数据和level0以上level的所有SSTable的数据.每个二级索引均由独立的R-tree组成.考虑到LevelDB中不同level的数据特点, 该设计保证了二级索引和主索引中数据的一致性. LevelDB的MemTable和level0的SSTable之间的数据可能存在一个key对应多个value的情况, 而在level0之上的level内的SSTable之间一个key只会对应一个value.基于这种结构, 首先考虑为每个MemTable和SSTable设计一个对应的二级索引, 但是这样会产生大量的索引文件, 不利于查找.因此考虑到level0以上level的特点, 使用一个大型的R-tree保存所有level0以上的SSTable数据的索引, 最终形成MemTable索引, level0索引和level1及以上大型索引的三层结构.
2.2 二级索引的一致性设计二级索引必须要考虑与主索引中数据的一致性问题, 由于LevelDB使用了延迟更新机制, 因此需要确保二级索引也要在延迟更新时同步更新. MemTable索引和level0索引由于与对应的MemTable和SSTable的内容完全一致故无需考虑一致性问题. LevelDB的更新和删除仅在SSTable合并时产生, 这是导致二级索引数据不一致的根源.因此在合并时需要通过生成一个更新表确定有变动的key和value, 并将其在SSTable合并后应用到大型的R-tree中.通过这种方式可以保证主索引中数据的变动同步更新到二级索引上, 从而保持了数据的一致性.
3 二级索引的实现在确定二级索引的存储结构后, 还需要设计和实现对应的插入、查询和更新算法, 图 3显示了二级索引在插入和更新时数据的流向.插入新数据时直接插入内存的跳表和二级索引中, 跳表写满后锁定并落盘到level0, 在满足合并条件后二级索引合并到level1以上的大二级索引中.
|
图 3 二级索引数据流向图 Fig.3 Secondary index data flow |
二级索引的插入操作和LevelDB本身的WriteBatch操作整合在一起, 在将数据插入LevelDB的MemTable之后再插入二级索引的内存部分.算法1详细描述了这个过程.
| 算法1 二级索引插入算法 |
| 输入:待插入的坐标cord和对应的key |
| 输出:二级索引数据文件 |
| 1:解析和封装输入的key和value//value必须是长度为2的double数组 |
| 2:生成SequenceNumber |
| 3:将输入的key和value保存到Write Ahead Log中 |
| 4:将key和value保存到MemTable中 |
| 5:读取内存二级索引的R-tree |
| 6:根据value的坐标cord找到待插入的节点 |
| 7:将cord插入到索引树中, 封装key, cord和SequenceNumber插入到二级索引的数据块中 |
3.2 二级索引的查询算法
考虑到空间数据的应用场景主要集中在范围查询而非单点查询, 本文实现了K-NN(K Nearest Neighbors)最近邻查询用来查询距离输入的目标点最近的K个位置.以10-NN查询为例, 查询需要同时搜索所有的二级索引文件, 先根据目标点在每个索引文件中查找距离其最近的10个点, 再按照距离目标点的远近汇总所有的查询结果, 汇总后从近到远依次校验结果.校验分为两部分, 先判断结果的SequenceNumber是否超过当前查询制定的SequenceNumber以保证版本一致, 再使用结果的key到主索引中查询, 比较查询出的value是否和结果中value一致以避免结果失效.通过的校验结果放入输出队列, 达到10个结果或者全部校验完成后输出.算法2详细描述了这个过程.
| 算法2 二级索引查询算法 |
| 输入:待查询的坐标cord |
| 输出: K个和cord最相邻的数据 |
| 1:从内存到磁盘依次查询所有的二级索引文件, 在每个索引中分别进行K-NN查询 |
| 2:统计所有的K-NN查询结果, 按照距离和先后顺序排序保存在结果队列queue中 |
| 3: for queue中所有的数据do |
| 4: 检查SequenceNumber是否过期 |
| 5: 在主索引中查询该key校验value是否过期 |
| 6: if value未过期then |
| 7: 输出该记录, count加1 |
| 8: else |
| 9: 跳过该记录 |
| 10: end if |
| 11: if count等于10或queue已空then |
| 12: 结束循环 |
| 13: end if |
| 14: end for |
3.3 二级索引的更新算法
二级索引的更新操作跟随LevelDB的合并操作, 分为两类:内存中的二级索引持久化到磁盘和磁盘中level0的二级索引合并到更高级的大索引中.算法3和算法4详细描述了这个过程.
| 算法3 内存二级索引更新算法 |
| 输入:内存二级索引文件 |
| 输出:磁盘二级索引文件 |
| 1: LevelDB的MemTable达到上限并转为Immutable MemTable |
| 2:锁定当前内存二级索引并生成新的内存索引文件 |
| 3:LevelDB开始将Immutable MemTable转存为Level0的磁盘SSTable |
| 4:为新SSTable生成对应的磁盘二级索引文件IDX中 |
| 5:遍历锁定的内存二级索引, 将数据依次插入新的磁盘索引IDX中 |
| 算法4 磁盘二级索引更新算法 |
| 输入:待更新的二级索引文件 |
| 输出:更新后的磁盘二级索引文件 |
| 1: LevelDB触发SSTable的合并 |
| 2:查找合并过程中删除和更新的key, value放入delete和update队列 |
| 3: if是level0的SSTable合并then |
| 4: 去除删除和更新的key, value, 剩余的数据放入insert队列 |
| 5: 删除该二级索引文件 |
| 6: end if |
| 7:对磁盘大二级索引分别使用ins |
4 实验 4.1 实验环境
本文在开源的LevelDB上实现了二级索引机制, 实验机器配置如下: Intel(R) Core(R) i5-6500 CPU, 16 GB内存, 256 GB SSD, 操作系统为Ubuntu 18.04.2 LTS.
4.2 二级索引插入性能实验目的:测试单实例情况下二级索引插入的性能.
实验设置:本测试使用随机生成的128字节key和0~1 000 000范围内的double型坐标值, 并生成1万条, 10万条, 50万条, 100万条测试数据.测试使用的R-tree每个节点的孩子数为25.实验结果如图 4所示.可以发现插入性能基本上随着数据规模线性增长.
|
图 4 二级索引插入效率 Fig.4 Secondary index insertion efficiency |
实验目的:测试单实例下对二级索引进行随机的10-NN查询的效率.
实验设置:本测试基于插入性能测试中的100万数据集, 使用0~1 000 000范围内的double型坐标值分别进行1万, 10万, 50万, 100万次随机10-NN查询.实验结果如图 5所示.可以发现查询性能基本上随着数据规模线性增长.
|
图 5 二级索引查询效率 Fig.5 Secondary index query efficiency |
随着NoSQL型数据库在各行各业应用的增长, 基于NoSQL型数据库的二级索引也将迎来越来越多的应用.本文基于LevelDB和R-tree, 设计了支持LSM结构的空间二维坐标数据索引.通过实验证明, 本文所设计的二级索引具备可用性, 对二维数据常用的10-NN最近邻查询有较好的支持.由于时间有限, 本文并未对引入该索引后LevelDB本身的插入查询性能变化有较多的探讨, 因此该研究后续仍有极大优化的空间.
| [1] |
Google Inc. LevelDB[EB/OL].[2019-06-20]. https://githbu.com/google/leveldb.
|
| [2] |
BECKMANN N, KRIEGEL H P, SCHNEIDER R, et al. The R*-tree: An efficient and robust access method for points and rectangles[C]//ACM Sigmod Record. ACM, 1990, 19(2): 322-331.
|
| [3] |
LUO C, CAREY M J. LSM-based storage techniques: A survey[J/OL]. arXiv preprint, arXiv: 1812.07527, 2018.
|
| [4] |
WU L, LIN W, XIAO X, et al. LSⅡ: An indexing structure for exact real-time search on microblogs[C]//2013 IEEE 29th International Conference on Data Engineering (ICDE). IEEE, 2013: 482-493.
|
| [5] |
KHODAEI A, SHAHABI C, LI C, et al. Hybrid indexing and seamless ranking of spatial and textual features of web documents[C]//International Conference on Database and Expert Systems Applications. Berlin: Springer, 2010: 450-466.
|
| [6] |
QADER M A, CHENG S, HRISTIDIS V. A comparative study of secondary indexing techniques in LSM-based NoSQL databases[C]//Proceedings of the 2018 International Conference on Management of Data. ACM, 2018: 551-566.
|
| [7] |
TAN W, TATA S, TANG Y, et al. Diff-Index: Differentiated index in distributed log-structured data stores[C]//EDBT. 2014: 700-711.
|
| [8] |
DSILVA J V, RUIZCARRILLO R, YU C, et al. Secondary indexing techniques for key-value stores: Two rings to rule them all[C]//Proceedings of the 20th International Conference on Extending Database Technology and 20th International Conference on Database Theory 2017. 2017: 21-24.
|