物联网传感器和全球定位系统（GPS）智能设备的海量数据流正涌入数据库系统进行进一步的处理和分析。新数据和历史数据的实时检索能力已被证明是利用这些数据流实现智能制造和智能城市实际应用的关键。在本文中，我们提出了一个简单有效的分布式解决方案来实现每秒数百万个单元插入和毫秒级的临时范围查询处理。为此，我们提出了一种新的数据划分方案，该方案充分利用了工作负载的特点，避免了代价高昂的全局数据合并。另外，为了解决吞吐量瓶颈，我们使用基于模板的索引方法，在相对稳定的传入元组分布上跳过不必要的索引结构调整。为了实现数据的并行插入和查询处理，我们提出了一种快捷的调度机制和有效的负载均衡策略，充分利用计算资源的工作负载感知方式。在集成工作负载和实际工作负载方面，我们的解决方案始终优于进的开源系统至少一个数量级。
随着物联网[21]传感器和位置信息[25]智能设备产生的高速数据的爆炸性增长，人们对高吞吐量数据接收和实时数据检索的需求迅速上升。它也是支持智能制造和智能城市应用的关键的数据处理功能之一，使系统用户能够根据需要快速检索历史数据和新数据。在图1中，我们给出了一个实时索引和查询处理的示例应用程序，其中分析系统尝试实时分析网络流量，并以非常高的速率在电信公司的骨干网络上采集样本。对流数据的典型查询从指定的IP范围和给定的时间间隔检索所有示例数据包，以识别网络攻击的潜在风险和识别网络故障。因此，系统必须支持低响应延迟的时间和范围查询，同时保证洪水样本到达后立即可见。
上述所有应用程序都要求系统支持极高的元组插入吞吐量和对指定域上的时间范围查询的实时响应。表1回顾了我们的目标应用程序的新系统性能保证。键值存储，如HBase[17]和leveldb[24]，将数据元组组织成排序映射，并支持快捷的键值范围查询。然而，非关键属性（如时态查询）的范围查询不是一等公民，因此无法有效执行。此外，虽然这些系统使用LSM树[33]代替传统的B+树来降低更新成本，但更新仍然需要与历史数据相结合，这导致了大量的数据整合成本，限制了插入吞吐量。时间序列数据库，如Druid[47]、gorilla[36]和btrdb[2]，是为实间序列数据摄取和具有时间限制的低延迟查询而设计的。但是，由于缺少辅助范围索引，它们无法对非时间属性提供有效的范围查询。
本文提出了一种简单有效的分布式解决方案waterwheel，它支持每秒100万元组以上的实时索引和具有键和时间范围约束的低延迟查询。据我们所知，这是个同时支持快捷时间和范围查询以及极高吞吐量数据插入的框架。waterwheel面临的主要挑战是在时间域和关键域中快捷地索引数据元组，同时在查询到达时保持新传输元组可见。我们利用实际工作负载的特点来解决这个问题，即到达几乎是有序的，分布演化缓慢。首先，流元组到达系统的顺序与生成它们的顺序几乎相同。例如，在图1中的动机示例中，样本包的收集几乎遵循样本包时间戳上的顺序。其次，传入元组的分布通常不会随时间发生显著变化。考虑到各种数据源，如图1中由智能设备、监控摄像机和智能建筑生成的网络数据包，在IP地址域中样本数据包的分布通常是缓慢和平缓的。
基于以上观察和直觉，我们重新设计了海量数据流的实时索引和查询处理架构。水车背后的关键思想是利用实际工作负载的特点，通过物理分区，将输入的数据作为独立的数据块，在不同的时间和关键范围内进行维护。在每个数据块中，建立模板B+树索引结构，支持有效的元组插入和数据检索。通过模板的使用，B+树不需要调整内部节点的结构，节省了索引维护成本，获得了较高的性能。这种简单的两层数据索引方案使系统能够根据不同的工作负载轻松地重新扩展。为了提高系统的性能和鲁棒性，设计了模板更新方法和动态密钥分配机制，使系统适应动态工作负载。为了充分利用查询处理中的计算资源，提出了一种同时保持负载平衡和数据局部性的查询调度算法。总的来说，与现有的开源解决方案相比，waterwheel的性能有了显著的提高。
1） 我们提出了一个通用的两层索引架构，它可以每秒插入数百万个单元，并以毫秒为单位查询密钥范围。
2） 设计了一种增强的基于模板的B+树，大大降低了索引维护开销，实现了高并发性。
3） 为了充分利用集群中的计算资源，设计了分布式查询调度算法和负载均衡机制。
4） 与文献中进的解决方案相比，我们使用合成和实际工作负载来评估原型系统，并显示出显著的性能改进。
