暂无图片
暂无图片
暂无图片
暂无图片
暂无图片
首页 / VLDB 2022 | Waffle：基于强化学习自动优化配置的移动对象内存网格索引系统

VLDB 2022 | Waffle：基于强化学习自动优化配置的移动对象内存网格索引系统

时空实验室 2023-01-09
314
移动对象的位置信息在人们生活中有着很多应用场景，现有的管理移动对象数据的系统普遍忽视了配置旋钮(Configuration Knobs)对于查询处理时间和索引内存使用的影响。本次为大家带来数据库领域顶级会议VLDB的论文：《Waffle：In-memory Grid Index for Moving Objects with Reinforcement Learning-based Configuration Tuning System》。

一．背景
随着GPS技术的逐渐发展，应用了GPS技术的移动对象实时地产生了大量的位置信息，这使得许多基于这些移动对象位置数据的服务或系统变得越来越流行且重要。例如出租车拼车服务、快递配送服务、交通流量管理系统、自动驾驶系统等等应用，如何高效地管理这些移动对象是当今研究的热点之一。移动对象的主要特征就是他们的地理位置是一直在变化更新的，所以能够支持快速的位置信息更新是首要要求。此外，很多应用场景还需要对移动对象进行诸如空间范围查询、k-NN查询这样的查询处理，所以能够支持快速的查询处理也是要求之一。现有的很多管理移动对象的系统采用内存网格索引技术来对移动对象建立索引，例如TwinGrid、PGrid、D-Grid等等，这种技术的优势在于能够很好地支持快速高效的位置信息更新以及查询处理。但是这些系统普遍忽视了配置旋钮对于查询处理时间和索引内存使用的影响，导致当一些环境因素变化时，系统的性能会受到很大的影响。
而这次带来的论文提出了一种新型的基于单元格和块定义的内存网格索引系统，Waffle，其建立的索引由几个配置旋钮决定，这些旋钮的值受到多种因素的影响，例如对象的分布、查询工作负载、硬件配置以及在查询处理时间和内存使用之间的权衡等等。就像上文提到的，这些配置旋钮会影响到系统的查询处理时间和索引内存使用，所以Waffle包含了一个自动优化配置旋钮的模块，WaffleMaker。WaffleMaker基于强化学习，并不需要提前训练，经过模型的不断学习收敛，最终输出一个优化的配置旋钮，Waffle在应用这个优化过的配置后可以提升其处理查询的性能，或者减少内存的使用。目前，Waffle支持处理插入、删除、空间范围以及k-NN四种查询。
二．方法介绍
2.1 总体框架
Waffle大体由网格索引模块、配置旋钮自动优化模块(WaffleMaker)以及索引重构模块三部分组成。Waffle为对象在内存中建立网格索引，并根据移动对象位置信息的变化不断更新索引，同时WaffleMaker持续地进行学习训练，输出优化的旋钮设置，Waffle接受新的旋钮设置并对索引进行重构。接下来为大家一一介绍三个模块。
2.2 网格索引模块
Waffle的索引结构是基于单元格（Cell）和块（Chunk）的概念。首先，移动对象的地理空间范围被定义为( [𝑚𝑖𝑛𝑙𝑎𝑡,𝑚𝑎𝑥𝑙𝑎𝑡], [𝑚𝑖𝑛𝑙𝑜𝑛,𝑚𝑎𝑥𝑙𝑜𝑛])，按照经纬度的最大值最小值生成的一个矩形空间，而一个对象O的坐标就是用其经纬度表示，(𝑂𝑙𝑎𝑡,𝑂𝑙𝑜𝑛).
（1）单元格：矩形空间被分为由等大的正方形单元格组成的网格，表示经度轴上的单元格数，表示纬度轴上的单元格数，每个单元格的坐标表示为(𝑐𝑒𝑙𝑙𝑙𝑎𝑡, 𝑐𝑒𝑙𝑙𝑙𝑜𝑛)，以下是一个对象O计算其所属单元格坐标的算法：
在Waffle中，一个单元格可能包含0个、1个或多个对象，MOPC(Maximum Objects Per Cell)表示每个单元格所包含对象数量的最大值。
（2）块：矩形空间又被分为由等大的矩形块组成的网格，一个块包含一个或多个单元格。类似于单元格，表示经度轴上的块数，表示纬度轴上的块数，每个块的坐标表示为(𝑐ℎ𝑢𝑛𝑘𝑙𝑎𝑡, 𝑐ℎ𝑢𝑛𝑘𝑙𝑜𝑛)，以下是一个单元格计算其所属块坐标的算法：
在Waffle中，块是主存中串行内存分配的单元，所以一个块中的单元格在主存中是连续分布的，但两个块是零散分布的。当一个单元格中对象数量超过了MOPC时，Waffle会新建一个块，用于储存多出来的对象。
 
图1 Waffle网格索引例子
图1展示了一个Waffle网格索引的例子，矩形空间为([0.3, 0.9], [0.3, 1.5])，各个对象、单元格、块的坐标在图中也有展示。在这个例子中，MOPC=2，=2，=4，=1，=2，因为cell(1,0)包含有三个对象，所以Waffle创建了一个chunk(0,0)2来储存多出来的一个对象。
2.3 配置旋钮自动优化模块(WaffleMaker)
（1）相关定义
i.State（S）：一个state是一个描述当前地理空间中移动对象分布情况的尺寸的网格，和是WaffleMaker中预先设置的超参数，每个单元格中储存着相应的对象。
ii.Action：一个action依据当前的state(S)决定一个新的旋钮设置（knob setting, KS)，KS包含五个旋钮值，。
iii.Reward（R）：一个reward用来评估一个action的质量，在按照action选择的KS建立的索引中，计算插入、删除、空间范围、k-NN查询以及内存使用五种reward。
𝑹{𝒊/𝒅/𝒓/𝒌 }表示插入、删除、空间范围、k-NN查询的reward，𝑥{𝑖/𝑑/𝑟 /𝑘 }表示某一种查询，𝑹{𝒊/𝒅/𝒓/𝒌 }的计算公式如下：
𝑹𝒎表示内存使用的reward，|𝑐ℎ𝑢𝑛𝑘𝑠|表示索引中chunk的总数量，𝑚𝐶ℎ𝑢𝑛k表示一个chunk使用的内存大小，𝑹𝒎的计算公式如下：
最后将计算得到的各个reward标准化，得到，w𝑡𝑖𝑚𝑒和w𝑚𝑒𝑚𝑜ry表示查询处理时间和索引内存使用的权重，并且有w𝑡𝑖𝑚𝑒 + w𝑚𝑒𝑚𝑜𝑟y = 1，最终R的计算公式如下：
iv.Experience：一个experience表示为(𝑆, 𝐾𝑆, 𝑅)三者的集合。
（2）学习模型
WaffleMaker使用卷积神经网络模型，包含卷积层、池化层和全连接层，该模型只需要从当前的state中进行学习，不需要额外的信息[1]。当接受到一组experience(𝑆, 𝐾𝑆, 𝑅)后，WaffleMaker会随机抽取一批的experience，根据其S和KS值，使用一个动作价值函数𝑄(𝑆, 𝐾𝑆) = R计算输出一个预期的R值，然后根据以下的一个损失函数（均方误差）来更新模型，随着模型的不断学习，WaffleMaker输出的KS趋向于带来一个更高的R值。
2.4 索引重构模块
当Waffle接受到一个新的旋钮设置时，Waffle会对索引进行重构，称为regrid。对于每一个对象，Waffle会将其从原始的网格索引中删除，然后插入新的网格索引中，所以在regrid过程中，会存在一新一旧两个网格索引，当旧的索引中所有的对象都被删除了，就意味着新的索引完全取代旧的索引，regrid完成了。
但这样的重构机制存在着一定问题，当Waffle正在regrid时，用户新提交的查询请求会被搁置，直到整个regrid完成，如果移动对象的数量很多的话，查询处理的延迟会明显增加，为了解决这个问题，Waffle使用一个两级锁协议来实现并行处理方案。每种查询操作在处理时会将扫描到的块进行锁定，防止其他查询操作的同时访问，插入和删除查询需要锁定单独的一个块，称为X-lock，空间范围和K-NN查询需要锁定一组块，称为S-lock。例如查询1锁定了chunk(0,1)，查询2需要访问chunk(0,1)，那么查询2只能等到查询1处理完毕解除锁定后才能进行，如果查询3不需要访问chunk(0,1)，那么查询3就能和查询1并行处理。
基于这样的锁定协议，Waffle将regrid划分成一系列的转移事务操作，每个事务操作包含一个删除查询和一个插入查询，这样一来就可以实现索引重构和用户查询请求的并行处理。
图2 实现并行处理方案前后Waffle工作流程的对比图
如图2所示，原先的Waffle在接受到空间范围查询的请求时因为regrid正在进行，不得不等到整个regrid完成后才能开始处理查询，这会产生很大的处理延迟，而在实现并行处理方案后，在第一个转移事务完成后，Waffle便可以开始处理查询，这明显提高了Waffle处理查询的性能，并且同时regrid依然在进行。值得注意的是，由于在regrid过程中会存在一新一旧两个网格索引，所以处理查询时需要考虑两个索引，锁定协议的实现可以保证一个对象只会出现在一个索引中，确保查询结果的准确性。
三．实验
论文进行的实验使用美国洛杉矶和纽约的两个路网数据集[2]，两个数据集的地理空间范围为
LA（洛杉矶）: ( [33.8449, 34.3243], [−118.766, −117.793])
New York（纽约）: ([40.2513, 41.0595], [−74.8782, −73.2227])
在实验中，基础的对象被随机地放置于道路上，额外的对象则是随着时间逐渐插入到地理空间中心附近的道路上，所有对象都沿着道路保持随机的移动，插入的额外对象会随着时间逐渐从空间中删除，基础对象和额外对象的数量都设置为106。
论文使用DDPG，一种广泛使用的深度强化学习算法[3]作为WaffleMaker的对照；使用u-Grid、u-R-tree、Quad tree和RSMI四种移动对象索引方法作为Waffle的对照。
3.1 WaffleMaker优化效果
图3 WaffleMaker和DDPG优化效果对比
如图3所示，随着学习模型的不断训练，两者输出的旋钮设置的预期reward的平均值逐渐提高最终趋于稳定，在整个过程中，WaffleMaker输出的reward平均值始终高于DDPG输出的值，可见WaffleMaker对旋钮设置的优化效果要优于DDPG。
3.2 Waffle性能
图4 Waffle与现有方法处理查询时间以及内存使用对比
图4比较了7种方法处理四种查询的时间以及内存使用，Waffle(fixed)使用一个固定的旋钮设置，不进行regrid，Waffle(WaffleMaker)和Waffle(DDPG)分别使用WaffleMaker (wtime=0.9, wmemory=0.1)和DDPG来优化旋钮设置，并进行regrid。实验测量了各种方法处理四种查询的平均时间，以及查询过程中索引使用内存的最大值和最小值。从a、b、c、d四张图可以看出，无论处理哪种查询，Waffle(WaffleMaker)总是表现得最好的那一个，并且相比其他方法，处理时间有着很大的提升。Waffle(WaffleMaker)和Waffle(fixed)之间的对比展现了优化旋钮配置的作用，一个固定的旋钮配置无法很好地应对时刻在变化的移动对象分布情况。Waffle(WaffleMaker)和Waffle(DDPG)的对比再次展现出WaffleMaker良好的优化效果，这也是Waffle性能提升的关键。而Waffle(fixed)和Waffle(DDPG)与另外四种索引方法相比，在大部分情况下的表现依然要更好，这展现了Waffle基于单元格和块概念的新型索引方法相比现有索引方法在处理查询上有着更好的表现，以及基于两级锁协议实现的并行处理方案对于查询处理性能的提升。在内存使用方面，Waffle(WaffleMaker)和Waffle(DDPG)表现得不好，内存使用的最大值和最小值都要高于其他方法，这是由于实验中Waffle以提升查询处理时间为主要目标来优化旋钮设置，并根据新的旋钮设置进行regrid，产生一新一旧两个索引，相比其他方法使用了更多的内存资源，这一点可以通过调整WaffleMaker中Wtime和Wmemory参数的值来改善，或者直接使用Waffle(fixed)，取消regrid机制，在内存使用较低的情况下依然有着不错的查询处理性能。
四．总结
本文介绍了Waffle，一个基于深度强化学习自动优化配置的新型内存网格索引系统，它使用基于单元格和块概念的索引方法来为移动对象建立索引并储存在主存中，支持处理插入、删除、空间范围以及k-NN四种查询。WaffleMaker是系统中一个自动优化配置旋钮的模块，它基于深度强化学习，根据现阶段移动对象的分布情况训练模型，输出一个优化后的旋钮设置。Waffle根据新的旋钮值进行索引重构，并且设计了一个两级锁协议来实现用户查询请求和索引重构的并行处理。实验结果表明，相比现有的索引方法以及深度强化学习算法，Waffle(WaffleMaker)对于移动对象的查询处理有着更优秀的性能，能够很好地管理移动对象产生的位置数据。
参考文献
[1].Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin A. Riedmiller. 2013. Playing Atari with Deep Reinforcement Learning. CoRR abs/1312.5602 (2013). arXiv:1312.5602 http://arxiv.org/abs/1312.5602
[2].Ahmed Eldawy and Mohamed F. Mokbel. 2019. Roads and streets around the world each represented as individual line segments. https://doi.org/10.6086/ N1H99379#mbr=9qwesvg4,9qxq6f81 Retrieved from UCR-STAR https://star.cs. ucr.edu/?OSM2015/road-network.
[3].Timothy P. Lillicrap, Jonathan J. Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. 2016. Continuous Control with Deep Reinforcement Learning. In 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings. http://arxiv.org/abs/1509.02971
-End-

本文作者

张梓健

重庆大学计算机科学与技术专业二年级在读学生，重庆大学START团队成员。主要研究方向：时空数据流式查询。
时空艺术团队（START，Spatio-Temporal Art）来自重庆大学时空实验室，旨在发挥企业和高校的优势，深入探索时空数据收集、存储、管理、挖掘、可视化相关技术，并积极推进学术成果在产业界的落地！年度有2~3名研究生名额，欢迎计算机、GIS等相关专业的学生报考！

waffle网格系统单元格索引
文章转载自时空实验室，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

评论