基于模型的相关维时间序列的可扩展管理_tsms异常处理

ModelarDB：基于模块化模型的时间序列使用Spark和Cassandra进行管理

摘要

工业系统，例如风力涡轮机，从可靠的高速传感器产生大量数据。由于存储和查询如此大量的数据是不可行的，所以目前只存储简单的聚合。然而，聚合消除了波动和异常值，这些波动和异常值会揭示潜在的问题并限制从历史数据中获得的知识。作为补救措施，我们提出了分布式时间序列管理系统(TSMS)模型数据库，它使用模型来存储传感器数据。因此，我们提出了一种在线自适应多模型压缩算法，该算法将数据值保持在用户定义的误差范围内(可能为零)。我们还提出了(1)将时间序列存储为模型的数据库模式，(2)利用该模式将谓词下推到键值存储的方法，(3)对模型执行聚合查询的优化方法，(4)通过静态代码生成优化投影执行的方法，以及(5)允许使用新模型而无需重新编译TSMS的动态可扩展性。此外，我们还展示了一个通用的模块化分布式TSMS体系结构及其实现——MoodardB，作为一个可移植的库，使用Apache Spark进行查询处理，使用Apache Cassandra进行存储。实验评估表明，与当前系统不同，ModelarDB找到了最佳位置，同时提供了快速接收、良好压缩和快速、可扩展的在线聚合查询处理。这是通过使用多个模型动态适应数据集来实现的。随着更多异常值的出现，系统会正常降级，并且实际误差远低于界限。

1 介绍

对于关键基础设施，如可再生能源，大量高质量的传感器通过有线电力和连接向监控系统提供数据。传感器定期采样，虽然可能会出现无效、缺失或无序的数据点，但这些数据点很少，除了缺失的数据点之外，所有数据点都可以通过既定的清洗程序进行纠正。虽然该领域的从业者需要高频率的历史数据来进行分析，但是目前不可能存储大量的数据点。作为一种变通方法，存储简单聚合的代价是移除时间序列中的异常值和波动。
我们将术语模型用于时间序列的任何表示，从该模型中可以在已知误差范围(可能为零)内重新创建原始时间序列。例如，线性函数y = ax+b可以表示增加、减少或恒定的时间序列，并将存储要求从每个数据点一个值减少到只有两个值:a和b。我们支持有损和无损压缩。我们的有损压缩保留了数据的结构和异常值，用户定义的错误界限允许在准确性和所需存储之间进行权衡。这与传统的传感器数据管理形成对比，传统的传感器数据管理使用模型来推断噪声较小的数据点[29]。
为了建立业界最先进的时间序列存储技术，我们评估了常用系统和大数据文件格式的存储需求。我们根据db引擎对[11]的排名、与能源行业公司的讨论以及我们的调查[28]来选择这些系统。两个关系数据库管理系统(rdbms)和一个TSMS由于其广泛的工业应用而被包括在内，尽管它们被优化用于比分布式解决方案更小的数据集。另一方面，大数据文件格式可以很好地处理大数据集，但不支持在线分析的流媒体摄取。我们使用来自一家能源生产公司的100ms采样间隔的传感器数据。第7节描述了模式和数据集(能量产生高频)。表1中的结果(包括我们的系统ModelarDB)显示了对时间序列使用TSMS或柱状存储的好处。然而，ModelarDB实现的存储减少更为显著，即使有0%的误差限制，也清楚地展示了基于模型的时间序列存储的优势。
由于传感器数据量巨大，需要分布式架构。(ii)流处理:对于监视，摄取的数据点必须在用户定义的小时间延迟之后才可查询。(iii)压缩:细粒度的历史值可以显示随时间的变化，例如性能下降。然而，在不压缩的情况下存储原始数据是不可行的，由于减少了磁盘I/O，这也有助于查询性能。(iv)有效检索:为了减少查询历史数据子集的处理时间，需要索引、分区和/或按时间顺序存储。(v)近似查询处理(AQP):在用户定义的错误范围内近似查询结果可以减少查询响应时间并支持有损压缩。(vi)可扩展性:领域专家应该能够在不改变TSMS的情况下添加特定领域的模型，并且系统应该自动使用最好的模型。
虽然存在使用多种模型之一压缩时间序列片段的方法[22,37,40]，但我们在[28]调查中没有发现使用多模型压缩的TSMS。另外，现有的方法没有提供上面列出的所有属性。它们要么不提供延迟保证[22,40]，要么需要在延迟和压缩[37]之间进行权衡，要么限制支持的模型类型[22,40]。相比之下，ModelarDB提供了所有这些特性，我们在基于模型的大数据系统存储和查询处理方面做出了以下贡献:

• 基于模块化模型的TSMS的通用架构，提供列出的重要属性。
• 一种有效的、自适应的在线多模型压缩时间序列在用户定义的误差范围内的算法。该算法与模型无关，可扩展，结合了有损和无损压缩，允许丢失数据点，同时提供低延迟和高压缩比。
• 基于模型的TSMS的方法和优化:

• 将多个时间序列存储为模型的数据库模式。
• 方法将谓词下推到用作基于模型的物理存储层的键-值存储。
• 直接在模型上执行优化的聚合函数而无需动态优化器的方法
• 使用静态代码生成来优化投影。
• 动态可扩展性使得在不更改或重新编译TSMS的情况下添加其他模型成为可能。

• 我们的体系结构实现为分布式TSMS ModelarDB，包括可移植的ModelarDB核心接口，用于查询处理的未修改版本Apache Spark和用于存储的Apache Cassandra。
• 使用来自能量域的时间序列对模型进行评估。评估显示了各个功能和贡献如何有效地协同工作，以动态适应使用多个模型的数据集，从而产生良好压缩、快速摄取和快速、可扩展的在线聚合查询处理的独特组合。实际误差比允许的范围低得多，当加入更多的异常值时，模型误差会适度下降。

论文组织如下。第2节给出了定义。第3节描述了我们的架构。第4节详细介绍了摄取和我们基于模型的压缩算法。第5节描述了查询处理，第6节描述了ModelarDB的分布式存储。第7节是评估，第8节是相关工作，第9节是结论和未来工作。

2 预备知识

我们现在提供将在整篇论文中使用的定义。我们也用一个运行的例子来举例说明。

TIME SERIES 时间序列：xxxxxxx
REGULAR TIME SERIES 规则的时间序列：xxxxxxx
SAMPLING INTERVAL 采样间隔：xxxxxxx
MODEL 模型：xxxxxxx
GAP 间隙：xxxxxxx
REGULAR TIME SERIES WITH GAPS 带间隙的规则时间序列：xxxxxxx
SEGMENT 带间隙的规则时间序列：xxxxxxx

七大定义弄懂

3 架构

ModelarDB的体系结构是模块化的，能够重用部署在集群中的现有软件，并被分成三组具有明确目的的组件:数据摄取、查询处理和段存储。模型数据库是围绕模型数据库核心设计的，这是一个可移植的库，具有基于模型的时间序列管理、元数据缓存和一组预定义模型的系统无关功能。对于分布式查询处理和存储模型，Core通过一组接口与现有系统集成，使可移植的核心易于与现有基础架构一起使用。该架构如图3所示。组件之间的数据流显示为箭头，而组件集由虚线分隔。
我们的架构实现将ModelarDB Core与Apache Spark的现有版本[8、17、45、46、47]集成在一起，以进行分布式查询处理，而Apache Cassandra [2、32]或JDBC兼容的RDBMS可以用于存储。由于分布式存储是ModelarDB的最重要属性，因此在本文的其余部分中，我们将重点介绍Cassandra。图3中的每个组件都带有在ModelarDB中提供该组件功能的系统或库注释。之所以使用Spark和Cassandra，是因为它们都是Hadoop生态系统的成熟组件，并且通过DataStax Spark Cassandra Connector进行了很好的集成。为了允许已经部署在集群中的未修改Spark和Cassandra实例与ModelarDB一起使用，它被实现为一个单独的JAR文件，该文件嵌入了ModelarDB Core，并且仅利用Spark和Cassandra提供的公共接口。结果，可以通过将JAR文件作为作业提交到未经修改的Spark版本来部署ModelarDB。此外，已经实现了单节点摄取器，以支持不使用Spark的数据点摄取。支持其他查询处理系统，例如通过实现新的引擎类，可以将Apache Flink [3，18]添加到ModelarDB中。支持其他存储系统，例如Apache HBase [4]或MongoDB [5]仅要求实现ModelarDB Core提供的存储接口。
摄取时，ModelarDB对时间序列进行分区，并将每个子集分配给集群中的核心。因此，并行地从子集中摄取数据点，并且对于无限的时间序列同时摄取每个子集中的时间序列。使用为时间序列的每个动态大小段自动选择的适当模型，将摄取的数据点转换为基于模型的表示形式。除了预定义的模型外，还可以动态添加用户定义的模型，而无需更改ModelarDB。由段生成器构造的段作为分布式内存缓存的一部分保存在内存中。随着新的段被发送到流中，一批旧段被刷新到段存储中。可以使用SQL查询高速缓存和存储中的两个段。通过将最新的段集保留在内存中，可以对最新数据执行有效的查询。由于必须从Cassandra中检索段并对其进行缓存，因此对历史数据的查询增加了查询处理时间。随后的查询将在缓存上执行。通过重用现有系统，可以重复使用容错功能，如[44]中所示。结果，ModelarDB可以提供成熟且经过测试的容错保证，并允许系统用户选择存储系统和具有适合给定用例的折衷的查询处理引擎。但是，由于ModelarDB的容错级别取决于查询引擎和数据存储，因此我们仅在体系结构级别讨论该实现。对于ModelarDB，数据丢失可能发生在三个阶段：正在摄取的数据点，分布式内存缓存中的段以及写入磁盘的段。通过使用可靠的数据源（例如Apache Kafka）或从多个节点的每个时间序列中提取数据点，可以保证容错性。通过使用分布式复制，可以确保内存和磁盘上的段的容错能力。在我们的实现中，可以通过对启用了Spark和Cassandra的复制的ModelarDB进行编译来防止段丢失。在本文的其余部分中，我们将不考虑复制，因为ModelarDB无需修改即可重用Spark和Cassandra中的复制。由于每个数据点由一个节点提取，因此，如果节点发生故障，数据点将丢失。但是，由于我们的主要用例是分析时间序列数据的趋势，因此可以接受一些数据丢失以显着提高摄取率[39]。除了容错能力之外，通过利用现有组件，可以将ModelarDB的实现保持在较小水平，从而减轻了确保正确性和添加新功能的负担。
ModelarDB用1675行Java代码（用于ModelarDB Core）和1429行Scala代码（用于命令行以及与现有系统的接口）实现。 ModelarDB Core是用Java实现的，以简化与其他JVM语言的接口，并在优化性能时使从源代码到字节码的转换尽可能简单。 由于模式匹配，类型推断和不可变数据结构提高了生产率，Scala用于其他组件。 源代码位于https://github.com/skejserjensen/ModelarDB

4 数据摄取

为了均匀地使用资源，将根据该任务可用的线程数和时间序列的采样率并行执行摄取。 时间序列集被划分为不相交的子集SS并分配给可用线程，因此每个子集的每秒数据点都尽可能接近相等。 为每个线程提供相同数量的数据点进行处理，确保在整个群集中统一利用资源以防止瓶颈。 ModelarDB使用的分区方法基于[31]，并最小化max(data_points_per_minutes(S1))-min(data_points_per_minutes(S2)) for S1,S2∈SS

4.1 与模型无关的压缩算法

为了扩展由ModelarDB Core提供的模型集，我们提出了一种用于分割和压缩带有间隙的规则时间序列的算法，其中可以使用使用有损或无损压缩的模型。 通过按照第1节中所述的用例针对带有间隙的常规时间序列优化算法，可以丢弃每个数据点的时间戳，因为可以使用为每个时间序列存储的采样间隔和存储的开始时间结束时间来重构它们 作为每个细分的一部分。 为了减轻现有多模型压缩算法所需的高压缩和低延迟之间的折衷，我们引入了两种分段类型，即临时分段（ST）和最终分段（SF）。该算法根据尚未定义到流中的数据点的用户定义的最大等待时间来发出ST，而当新的数据点不能由所使用的模型集表示时，则发出SF。我们算法的总体思路如图4所示，它使用了一系列模型，如[22]所建议的，一次可以激活一个模型。在此示例中，我们将最大等待时间设置为三个数据点，使用线性函数形式的单个模型，并提取第2节中的时间序列TS。在t1和t2处，将数据点添加到临时缓冲区，而将模型M逐步拟合到数据点。由于我们的方法与模型无关，因此每个模型都定义了如何将其拟合到数据点以及如何计算误差。这允许模型实现最合适的方法来拟合数据点，例如，设计用于流传输的模型一次可以拟合一个数据点，而必须为每个数据点重新计算的模型可以执行分块。在t3时，尚未发出三个数据点，请参见，并且模型已作为ST的一部分发出到主内存段缓存中。为了说明起见，我们用T标记作为ST的一部分发出的最后一个数据点，而用F标记作为SF的一部分发出的最后一个数据点。由于M可能表示更多的数据点，所以保留这些数据点在缓冲区中添加下一个数据点，并在t4处将其添加。在t5，添加一个数据点，该M点不能在用户定义的误差范围内表示。由于我们的示例仅包括一个模型，因此在将算法与下一个数据点重新开始之前，将SF发射到主内存段缓存，并从缓冲区中删除由SF表示的数据点（如虚线圆圈所示）。由于发射的SF表示在t4摄取的数据点，因此ye在t5不会递增，因此不会发射已经由SF表示的数据点作为ST的一部分。最后，在tn处，当高速缓存达到用户定义的批量写入大小时，会将段刷新到磁盘。我们的压缩算法显示在算法1中。第一个变量在第8-11行中初始化，这与图4中的t0对应。为确保可以从每个段中复制数据点，在第14-16行中，如果存在间隙，则所有数据 缓冲区中的点作为一个或多个SF发出。如果缓冲区中的数据点数量少于实例化任何提供的模型所需的数量（线性函数需要两个数据点），则会发出包含未压缩值的段。在第17-20行中，数据点被附加到缓冲区，而上一个被设置为当前数据点。数据点被追加到模型，从而允许模型更新其内部参数，并允许算法检查模型是否可以在用户定义的误差范围或长度限制内表示新的数据点。之后，不作为段发出的数据点的数量增加。图4中的状态t1至t4说明了这种增量过程。如果尚未发出等待时间数据点，则在第21-23行中会发出使用当前模型的ST。保留当前模型，因为它可能表示其他数据点。这对应于图4中的t3，因为由于等待时间= 3而发出了ST。如果无法使用缓冲区中的数据点实例化当前模型，则会发出包含未压缩值的ST。当模型不再能够代表所需误差范围内的数据点时，将选择模型列表中的下一个模型，并使用第25-27行中的缓冲数据点进行初始化。由于模型在初始化时表示来自缓冲区的尽可能多的数据点，并且拒绝任何后续数据点，因此无需显式检查模型是否可以表示缓冲区中的所有数据点。相反，当添加新数据点时，此检查将作为算法的下一次迭代的一部分进行。当模型列表变为空时，在第29行中将发送一个包含具有最高压缩率的模型的SF。为了允许使用无损压缩的模型，我们将压缩率计算为字节的减少量而不是要存储的值数：压缩比=（表示的数据点（模型）×（数据点）的大小）/（模型的大小）。由于模型选择基于压缩率，因此由发射最终段发出的段可能无法表示缓冲区中的所有数据点。在第30-32行中，将模型设置为列表中的第一个模型，并使用缓冲区中剩余的任何数据点进行初始化。如果不是由ST发出的数据点已作为SF的一部分发出，则已发出的数据会适当减少。发射SF的过程对应于图4的t5，其中最新数据点保留在缓冲区中，而SF首先发射一个数据点。在第35行中，由于已接收到所有数据点，因此将刷新缓冲区，以便将所有数据点作为SF发出。

4.2 有关数据摄取的注意事项

存在两种分割时间序列的方法：已连接和已断开。连接的网段从上一个网段的最后一个数据点开始，而断开的网段从前一个网段未表示的第一个数据点开始。我们的算法通过更改发射最终段是否保留段的最后数据点来支持两者。连接段的使用有两个好处。如果与支持插值的模型一起使用，则可以按任意采样间隔重建时间序列，因为可以对任意两个数据点之间的值进行插值。同样，可以仅使用单个时间戳存储连接的段，因为一个段的结束时间是下一个段的开始时间。但是，对于时间序列的多模型压缩[37，38]，如果存储每个段的开始和结束时间以供索引使用，则对于断开的段，压缩率会提高。减小的大小是由于在安装断开的段时增加了灵活性，因为不包括来自先前段的数据点[37，38]。由于时间序列可能会有间隔，因此必须存储段的开始时间和结束时间，以确保可以重新构造摄取的所有数据点。结果，本文的其余部分将只涉及断开的段。为了表示间隙，有两种方法：遇到间隙时刷新数据点流，或将间隙显式存储为一对时间戳G =（ts，te）。当我们评估两者时，我们发现压缩比没有显着差异。但是，显式存储间隙需要额外的计算，因为对段的任何操作都必须跳过间隙，这也使实现复杂化。明确地存储间隙需要将算法1第15行中的刷新缓冲区（缓冲区）替换为timestamp（上一个），并将timestamp（数据点）添加到间隙缓冲区中，并且修改发出段的函数以将间隙包括为该段的一部分。如算法1所示，ModelarDB刷新数据点流；但可以显式存储差距。

4.3 用户定义模型的实现

为了用户在ModelarDB Core中预定义的模型和段之外可选地添加新的模型和段，每个模型和段都必须实现表2中的接口。Tid是分配给每个时间序列的唯一id。通过拥有一个段类，模型对象可以在不增加其段大小的情况下，在摄取数据点的同时存储数据。因此，模型可以实现特定于模型的优化，如分块、延迟匹配或记忆。对于要直接在段上执行的聚合查询，必须实现可选方法。使用线性函数作为模型的段的sum实现如清单1所示。对于这个模型，可以通过将值的平均值与所表示的数据点的数量相乘来计算总和，而无需重新创建数据点。


为了演示，我们使用第2节中的片段，起始时间为100，结束时间为400，采样间隔为100，线性函数为0.0024ti+29.5作为模型。对于一个更现实的例子，我们将结束时间增加到7300。首先计算线段代表的数据点数量((7300 - 100)/100)+1 = 73，然后计算第一个数据点的值0.0024 × 100 + 29.5 = 29.26，最后一个数据点的值0.0024 × 7300 + 29.5 = 11.98。线段代表的数据点的平均值为(29.26 + 11.98)/2 = 20.62，代表值之和为20.62 × 73 = 1505.26。我们的例子清楚地显示了使用模型进行查询的好处，因为计算总和从73个算术运算减少到10个，或者就复杂性而言，从线性到恒定时间复杂性。所有模型都必须表现出以下行为。尚未添加足够的数据点来实例化模型的模型必须返回一个无效的压缩率n an，这样它就不会被选为段的一部分。第二，如果模型拒绝一个数据点，则必须拒绝所有随后的数据点，直到模型被重新初始化。最后，作为使用可扩展模型集的结果，计算模型近似误差的方法必须由模型定义。用户定义的模型和模型选择算法的结合提供了一个足以表达现有时间序列压缩方法的框架。对于使用一种压缩方法将时间序列压缩为静态大小的子序列的时间序列管理系统，如Facebook的Gorilla [39]，可以使用基于极限参数拒绝数据点的单一模型。对于在预定义序列中使用多个有损模型的方法，如[22]，相同的模型可以在任何集成了ModelarDB Core的系统中实现和重用，额外的好处是模型的排序不像[22]中那样作为算法的一部分进行硬编码，而只是一个参数。为了评估，我们从文献中实现了一组通用模型。我们选择模型的依据是[27]，除了现有的主要选择常数和线性模型的多模型方法之外，[22，38]我们还证明了支持动态大小数据段的模型的压缩率大幅提高，以及一些常数和线性模型的高压缩率。我们还选择可以增量拟合的模型，以便在线有效地拟合数据点。为了确保每个数据点的用户提供误差界限得到保证，仅考虑基于统一误差范数提供误差界限的模型[34]。最后，我们选择具有无损和有损压缩的模型，允许ModelarDB为每个子序列选择最合适的方法。因此，我们实现了以下模型:常数PMC-磁流变模型[33]，线性摇摆模型[23]，两者都进行了修改，因此误差范围可以表示为实值和近似值之间的百分比差异，以及Facebook [39]提出的浮点值无损压缩算法，该算法被修改为使用浮点。当没有其他模型适用时，存储原始值的模型由ModelarDB使用。

5 查询处理

5.1 通用查询接口

由段生成器发出的段放在主内存缓存中，可以与存储中的段一起查询。ModelarDB使用两个视图为内存和存储中的段提供了统一的查询接口。第一个视图直接表示段，而第二个视图将段表示为数据点。这个段视图使用模式(Tid int、StartTime timestamp、EndTime timestamp、SI int、Mid int、Parameters blob)，并允许在段上执行聚合查询，而无需重新构造数据点。属性Tid是唯一的时间序列id, SI是采样间隔，中间是用于分段的模型id，参数是用于模型的参数。数据视图使用模式(Tid int、TS时间戳、值float)来允许在从段重新构建的数据点上执行查询。在这两个抽象级别上实现视图允许查询处理引擎直接与ModelarDB Core使用的数据类型进行接口。高效聚合可以在段视图上实现为用户定义的聚合函数(UDAFs)，谓词下推可以实现到查询处理引擎支持的程度。虽然只有数据视图可以提供一个更简单的查询接口，但是与ModelarDB Core连接一个新的查询处理引擎将会更加复杂，因为对数据视图的聚合查询需要重写以使用片段视图[21,29,43]。

5.2 Apache Spark中的查询接口

通过Spark SQL, ModelarDB提供了SQL作为其查询语言。由于Spark SQL只将所需的列和WHERE子句的谓词推入数据源，因此聚合在段视图上被实现为UDAFs。虽然没有执行完整的查询重写，但是data point视图通过将WHERE子句的谓词推到段存储的段视图检索段。因此，段存储只需要从段视图支持谓词下推，而不需要同时支持两个视图。我们当前的实现支持COUNT、MIN、MAX、SUM和AVG。如果可用，UDAFs使用表2所示的段接口中的可选方法，否则查询将在数据点上执行。由于Spark SQL中的UDAFs不能重载，因此实现了两组UDAFs。第一个集合将段作为行进行操作，并具有后缀s。第二个集合将段作为struct进行操作，并具有后缀SS。因此，对于在段视图上执行的查询与在数据视图上执行的查询具有相同的粒度，可以提供函数来限制段的开始时间(start)、结束时间(end)或同时限制段的开始时间(INTERVAL)。虽然ModelarDB目前仅通过片段视图支持有限数量的内置聚合函数，但为了演示使用模型计算聚合的好处，Spark SQL提供的任何聚合函数都可以通过data point视图使用。此外，现有的以时间序列作为数据点进行操作的软件，如用于时间序列相似度搜索，可以利用数据观点。最后，使用Spark SQL提供的api，可以将任何分布或代数聚合函数添加到数据点视图和段视图中。

5.3 执行视图查询

对视图的查询示例如清单2所示。第1-2行显示了计算Tid = 3的时间序列摄取的所有值之和的两个查询。第一个查询从片段重新构建的数据点计算结果，而第二个查询直接从片段计算结果。第4-5行上的查询计算时间戳在2012-01-03 12:30之后的数据点值的平均值。WHERE子句在段级别过滤结果，并忽略比所提供的时间戳更早的数据。最后，在第7-8行中，在data point视图上执行查询，就好像数据点已经存储了一样。

为了降低查询延迟，主内存段缓存(参见图3)存储每个时间序列最近发出的或查询的SFs和最后发出的ST。然后，为了确保查询不会返回重复的数据点，当发出具有相同Tid的SF时，将更新ST的开始时间，这样时间间隔不会重叠。

在STs中，StartTime > EndTime被丢弃。最后，SF缓存在达到用户定义的批量写大小时刷新。ModelarDB中的查询处理主要关心从查询结果中过滤出片段和数据点。图5显示了一个查询片段的示例，其中查询来自于日期2012-01-03之后的传感器Tid = 77的数据点。假设只有sf3和st6同时满足这两个谓词，并且sf3不在缓存中。首先，WHERE子句谓词被推到段存储(参见RS1)，以检索相关的段。从磁盘检索的段被缓存，参见RS2，然后缓存与内存中的STs和SFs合并，如rs3和RS4，以生成集合RS5。rs5根据WHERE子句进行过滤，可能会删除由谓词计算不精确的段存储提供的段(例如，假阳性)，并从内存缓存中删除不相关的段。最终结果如RS6所示。通过片段视图检索相关片段来处理对数据视图的查询。然后根据WHERE子句重建和过滤数据点。

5.4 代码生成的预测

除了谓词下推之外，视图还执行投影，以便只提供查询中使用的列。但是，根据请求的列动态地构建行会造成很大的性能开销。由于每个视图的列都是静态的，因此可以在编译时生成优化的投影方法，而不需要额外的开销和动态代码生成的复杂性。
为数据点视图生成的方法如清单3所示。在第3行，请求的列列表被转换为列索引，并按照请求的顺序连接，以创建一个唯一的整数。
这适用于两种视图，因为每种视图都少于十列，并且允许使用开关检索投影方法，而不是比较数组的内容。在第4行，使用匹配语句检索投影方法，该语句被编译为高效的查找开关[15]。

6 段存储

图6显示了用于存储片段和ModelarDB所需的元数据的通用模式。它有三个表:用于存储关于时间序列的元数据的Time Series(当前实现只需要采样间隔)，用于存储每个段中包含的模型类型的Model，以及用于存储将模型参数作为blob的段的最后一个段。大部分数据存储在段表中。与其他工作相比[22,24,38]，同时包含一个Tid和时间序列表，使得对不同采样间隔的不同时间序列片段的查询可以由一个片段表提供。

6.1 Apache Cassandra中的段存储

压缩是ModelarDB在Cassandra中存储段的主要重点。由于Cassandra期望表中的每一列都是独立的，因此使用Tid，StartTime，EndTime作为主键仅向Cassandra指示每个分区都由StartTime完全排序。结果，将StartTime和EndTime添加到主键不允许直接查找段。但是，由于段是按Tid分区的，因此在每个分区内，由于StartTime被排序，EndTime将被排序。我们通过将每个表按各自的ID进行分区来将其用于ModelarDB，并将EndTime用作段表的聚类列，以便按EndTime在磁盘上对段进行升序排序。这允许存储段的大小而不是存储StartTime，以获得更高的压缩率，同时允许ModelarDB在执行查询时利用段表的分区和排序，因为Cassandra可以在EndTime上过滤段，而Spark加载段直到需要到达启动时间。如第4.2节所述，由于存在间隙，不能忽略StartTime列。为了支持适合于特定存储系统的索引方法，例如在[24]中，二级索引可以在ModelarDB中实现，作为存储接口的一部分，如图3所示。

6.2 谓词下推

在我们的实现中支持谓词下推的列如图7所示。表中的每个单元格显示了特定列上的谓词在推入段视图或存储之前是如何重写的。用Spark takeWhile标记的列StartTime的单元格表示Spark分批从Cassandra读取行，直到单元格表示的谓词对于一个段为false为止。如上所述，这允许用存储段中数据点数量的列大小替换StartTime。这在不牺牲精度的前提下减少了启动时间所需的存储空间。当加载一个段时，可以将段的开始时间重新计算为StartTime = EndTime - (Size*SI)，从而允许Spark加载段，直到单元所表示的谓词对于一个段为false为止。Tid上的不相等性查询被重写，因为Cassandra只支持分区键上的相等性查询。

7 评价

我们将ModelarDB与业界使用的最先进的大数据系统和文件格式进行了比较:存储在HDFS的Apache ORC [6，26]文件[42]，存储在HDFS的Apache Parquet [7]文件，InfluxDB [13]，以及Apache Cassandra [32]。由于开源版本不支持分发，InfluxDB在单个节点上运行。用于每个实验的节点数量显示在相关的图中。时间序列的多模型压缩也在[22，37，38]中进行了评估。我们首先介绍评估中使用的集群、数据集和查询，然后描述每个实验。

7.1 评估环境

该集群由一个主节点和六个通过1 Gbit以太网连接的工作节点组成。所有节点均具有2.70 GHz Intel Core i7-2620M，1333 MHz DDR3内存的8 GiB和7200 RPM硬盘驱动器。每个节点都在EXT4之上运行Ubuntu 16.04 LTS，InfluxDB 1.4.2，InfluxDB-Python 2.12，Pandas 0.17.1，来自Hadoop 2.8.0的HDFS，Spark 2.1.0，Cassandra 3.9和DataStax Spark Cassandra Connector 2.0.2。主节点是主HDFS NameNode，辅助HDFS NameNode和Spark Master。每个工作程序都充当HDFS数据节点，Spark从站和Cassandra节点。 Cassandra不需要主节点。仅实验所需的软件将保持运行状态，并且所有系统都将禁用复制。使用du查找磁盘空间利用率。时间序列使用与数据点视图相同的模式存储：Tid作为int，TS使用每种存储方法的本机时间戳类型，而Value作为浮点型。 InfluxDB是一个例外，因为它仅支持double。所有存储方法的摄取都使用float进行。对于Parquet和ORC，将使用Spark在每个时间序列中创建一个文件，并将其存储在HDFS中，并为每个数据集和文件格式对创建一个文件夹，对于InfluxDB时间序列，将其作为一个测量值（以Tid作为标记）存储，对于Cassandra我们在Tid上进行分区，并对TS和Value上的每个分区进行排序，以获得最佳压缩效果。
一般来说，每个系统的配置都保留其默认值。然而，Spark和Cassandra或HDFS可用的内存都是静态分配的，以防止崩溃。为了在查询处理和数据存储之间划分内存，我们限制了Spark可以为每个节点分配的内存数量，因此Cassandra/HDFS和Ubuntu可以使用其余的内存。通过Spark限制内存分配，以确保所有实验的一致性。通过将每个系统上的内存的一半分配给Spark，然后减少为Spark分配的内存，直到所有实验都可以成功运行，从而为Spark找到合适的内存量。对于Parquet和ORC，我们启用谓词下推。所使用的参数如表3所示，ModelarDB的特定参数在左上角的表中，对Spark的默认参数的更改在右上角的表中，ModelarDB Core中实现的模型在底部的表中。参数值被发现与数据集和硬件配置工作得很好。如果没有明确说明，则误差范围为10%。

7.2 数据集和查询

我们用于评估的数据集是规则的时间序列，其中的间隙并不常见。每个数据集都存储为CSV文件，每个文件有一个时间序列，每行有一个数据点。
Energy Production High Frequency该数据集被称为EH，由能源生产的时间序列组成。数据是由我们从OPC数据访问服务器收集的，使用连接到能源生产者的Windows服务器。该数据的近似采样间隔为100ms。在预处理过程中，由于舍入的原因，我们四舍五入时间戳并使用等效时间戳删除数据点。由于收集过程的限制，此预处理步骤是必需的，在生产设置中不存在。数据集的大小是582.68 GiB。
REDD公共参考能源分解数据集(REDD) [30]是在两个月内收集的六所房屋的能源消耗数据集。我们使用的文件包含了每户每秒的能源使用量。十二个文件中的三个已经被排序，以纠正一些无序的数据点，六号房的文件由于不规则的采样间隔而被删除。由于REDD适合单个节点上的内存，我们通过将每个文件的所有值乘以[0.001，1.001]范围内的随机数，并将每个值四舍五入到两位小数来扩展它，以确保我们的结果不会受到相同文件的影响。2，500是根据我们群集中的存储量选择的。数据集大小为487.52千兆字节，被称为扩展降排(ER)。我们使用这个公共数据集来实现再现性。
Energy Production该数据集被称为EP，主要由能源生产的时间序列组成，由一家能源贸易公司提供。数据收集时间超过508天，采样间隔为60秒，大小为339千兆字节。数据集还包含实体特定的测量值，例如风力涡轮机的风速和太阳能电池板的水平辐照度。
Queries 第一组查询(S-AGG)由小聚合查询和分组查询组成，代表一个或几个时间序列上的在线分析，例如相关传感器，因为分析查询是预期的模型数据库用例。Tid使用WHERE子句限制这两种类型的查询，GROUP BY查询对每个时间序列运行五次，GROUP on Tid。第二个集合(L-AGG)由大型聚合和分组查询组成，它们聚合整个数据集和Tid上的每个分组查询组。L-AGG旨在评估系统在执行预期用例时的可伸缩性。第三个集合(P/R)包含时间点和范围查询，这些查询由带有TS或Tid和TS的WHERE子句限制。P/R表示用户从时间序列中提取一个子序列，这不是预期的ModelarDB用例，但为了完整性而包含在内。我们不评估SQL JOIN查询，因为它们不常用于时间序列，并且相似性搜索尚未内置于ModelarDB中。

7.3 实验

Ingestion Rate（摄入率）为了消除可能的瓶颈网络，主要在工作节点上本地评估摄取率。 对于每种系统/格式，我们从本地磁盘上的gzip压缩CSV文件（14.67 GiB）提取ER的一号房中的一个通道。 除了InfluxDB之外，均通过Spark-shell及其默认参数使用Spark的本地实例执行摄取。 由于InfluxDB尚不具备我们所了解的成熟的Spark连接器，因此我们使用InfluxDB-Python客户端库[14]。使用Pandas解析输入文件，并且InfluxDB-Python的批量大小配置为50,000。 对于Cassandra，我们将以kb为单位的参数批处理大小失败阈值提高到50 MiB，以允许更大的批处理。 为了确定ModelarDB的可扩展性，我们还在两种不同的情况下评估其在集群上的摄取率：无查询的大容量加载（BL）和使用细分视图在随机时间序列上连续执行的带有聚合查询的在线分析（OA）。 当使用单个工作程序时，ModelarDB使用单节点摄取器，而在分发时，每个节点每个节点只有一个接收器，五秒钟的微批处理间隔以及零延迟将Spark串流，因此每个数据点都是 仅细分一次。

结果如图8所示。不出所料，InfluxDB和Cassandra的摄入率最低，因为它们是在摄入时被查询的。ModelarDB还支持在摄入过程中执行查询，但摄入速度仍分别比InfluxDB和Cassandra快11倍和4.89倍。Parquet和ORC分别比ModelarDB增加了1.52倍和1.39倍。然而，在查询Parquet和ORC之前，必须写入整个文件，由于这种方法固有的延迟，使得它们不适合在线分析。ModelarDB不需要这种折衷，因为可以在数据被接收时对其执行查询。当在六节点集群上进行大容量加载时，ModelarDB的摄取率增加了5.39倍，接近线性加速。当并行进行在线分析时，摄入几乎不受影响，增加了5.36倍。总之，ModelarDB实现了高摄取率，同时允许在线分析，这与替代产品不同。
Effect of Error Bound and Outliers（误差界限和异常值的影响）使用所有三个数据集评估存储效率和错误界限之间的权衡。 当存储在ModelarDB中且错误绑定设置为0％到10％的值时，可以找到使用的模型和每个数据集的大小。 我们将ModelarDB的存储效率与行业中使用的系统进行了比较。 此外，我们通过向每个数据集添加越来越多的异常值来评估存在异常值时ModelarDB的自适应压缩方法的性能。 随机创建异常值，以使两个连续异常值之间的平均距离为N，每个异常值的值设置为（要替换的数据点的值+ 1）* 2。
用于EH的存储如图9所示。在现有的系统中，InfluxDB表现最好，但即使误差范围为0%，ModelarDB缩小EH的大小是InfluxDB的1.52倍。这是预期的，因为PMC-MR模型可以用于执行运行长度编码，而使用Facebook模型使用delta压缩来管理值的更改。将误差范围增加到10%可以进一步减少1.18倍，而平均实际误差仅为0.005%。ER的结果如图10所示。与InfluxDB相比，ModelarDB提供了更好的压缩:2.40倍的1%，7.02倍的5%，9.31倍的误差范围10%。对于ER来说，ORC是现有系统中最好的，但ModelarDB在1%、5%和10%误差范围下分别降低了2.13倍、6.24倍和8.27倍。此外，ER的平均实际误差只有0.22%，5%和10%的平均实际误差分别为1.25%和2.50%。即使是0%的范围，ModelarDB也只比ORC多使用1.17倍的存储空间。EP结果如图11所示。在这里，ModelarDB提供了最好的压缩，即使在0%的误差范围内，但是，差异小于EH和ER。这是可以预见的，因为EH和ER采样间隔分别低了600倍和60倍，由于时间接近，产生了更多具有相似值的数据点。ModelarDB还设法将EP的平均实际误差保持在低水平，仅为0.08%(1%)、0.48%(5%)和0.73%(10%)范围。
每个数据集使用的模型如图12-14所示。 总体而言，PMC-MR和Facebook是使用最多的模型，除了EP误差为5％和10％之外，很少使用Swing。 注意，Swing还用于ER和EP，误差范围为0％，因为在数据集中确实存在值的完美线性增加和减少。 最后，除了EH，广泛使用多种模型。 这些结果清楚地表明了多模型压缩的好处和适应性，因为可以使用模型的不同组合有效地处理数据集和误差范围的每种组合。
离群值的影响如图15所示。正如预期的那样，所使用的存储量随离群值的数量而增加，但其增加取决于数据集和错误范围。对于所有数据集，随着将其他异常值添加到数据集，ModelarDB会正常降级。当N的值减小到250以下时，相对大小会更快地增加，因为大量异常值严重限制了ModelarDB可以构造的段的长度。结果还表明，当使用0％错误范围时，ModelarDB对异常值的鲁棒性更高。误差范围为10％时，EH和EP的相对增大比误差范围为0％时高，而在N = 25的极端情况下，误差范围为10％的ER的相对尺寸增大为9.06，而误差范围为0％时仅为1.12。这是可以预期的，因为ER具有较高的压缩率和10％的误差范围，并且异常值的数量过多，导致ModelarDB无法构建长段。结果表明，尽管为离群值很少的时间序列而设计，但随着离群值的增加，ModelarDB会适当降低。
总之，当使用0%的错误边界时，ModelarDB提供了与现有格式一样好的压缩，并且通过根据数据和错误边界组合不同的模型，即使是很小的错误边界，也提供了更好的压缩。
Scale-out（扩展）为了评估ModelarDB的可伸缩性，当使用测试集群在ER上执行L-AGG时，我们首先将它与现有系统进行比较。然后，为了确定ModelarDB在大型集群上的可扩展性，我们使用1 - 32标准D8 v3在Microsoft Azure上执行L-AGG，节点类型是根据Spark、Casandra和Azure的文档选择的[1,9,10]。使用测试集群中的配置，但Spark和Cassandra都可以访问每个节点的50%内存，因为在这个初始配置中没有观察到崩溃。对于每个实验，REDD都被复制，使用上面描述的方法，并被摄入，这样每个节点存储的压缩数据相当于节点的内存。这使得Spark和Cassandra无法在内存中缓存数据集。基于现有的分布式系统评估方法[19]，对节点数量和数据规模进行并行缩放。查询是使用每个系统最合适的方法执行的:InfluxDB的命令行界面(CLI)、ModelarDB的段视图(SV)和数据点视图(DPV)，以及Cassandra、Parquet和ORC的Spark SQL数据框架(DF)。我们使用DF和缓存数据帧(DFC)评估查询性能，如图25所示。然而，由于dfc增加了运行时间，由于数据低效地溢出到磁盘，我们只对其他查询使用DFs。

结果如图16-17所示。 对于这两种视图，ModelarDB都接近线性扩展。 这是可以预期的，因为时间序列的所有段都位于同一位置，因此无需进行随机操作即可回答查询。 但是，使用SV可以大大减少查询处理时间，因为SV不重建数据点，从而减少了CPU和内存的使用。 在一个节点上，SV比DPV快2.27倍，对于六个节点，SV快2.16倍。 对于ER上的L-AGG，ModelarDB比所有现有系统都快。 与InfluxDB相比，在一个节点上，ModelarDB的SV和DPV分别快2.95倍和1.30倍。 使用六个节点，ModelarDB分别比Parquet和ORC快1.52倍和1.67倍。 总之，ModelarDB几乎可以线性扩展，同时提供比竞争对手更好的性能。
Effect of Optimizations（优化的效果）为了评估代码生成和谓词下推优化，我们对带有或不带有优化的ER执行L-AGG和P / R。 为了与静态代码生成进行比较，我们使用scala.tools.reflect.ToolBox和Spark的mapPartitions转换实现了一个简单的动态代码生成器。 默认情况下，ModelarDB对投影使用静态代码生成，对Tid，Timestamp和takeWhile使用谓词下推。 图18中的投影结果表明，与动态构造每一行相比，生成用于投影的优化代码最多可将运行时间减少1.60倍。 但是，与静态代码生成相比，使用动态代码生成的实现会增加运行时间。谓词下推的结果如图19所示。谓词下推对L-AGG的查询处理时间几乎没有影响，但P / R的减少更为明显，我们看到减少了7.03倍。 这是可以预期的，因为L-AGG中的所有查询都必须从磁盘读取整个数据集，而P / R中的所有查询只能使用一小部分子集来回答。

Further Query Processing Performance（进一步的查询处理性能）为了进一步评估ModelarDB的查询性能，我们使用为向外扩展描述的查询接口对所有数据集执行S-AGG和P/R。S-AGG的结果如图20-22所示。同样，使用SV可以减少运行时间。虽然在ER和EP上，InfluxDB在S-AGG上的表现略好于ModelarDB，但它在可扩展性和摄取率方面有局限性，如上所示，ModelarDB在ER上执行L-AGG的速度比InfluxDB快2.95倍。与分布式系统相比，ModelarDB几乎在所有情况下都提供了同样好的或更好的查询处理时间。在EH上，ModelarDB比ORC快1.4倍，比Cassandra快152.62倍。对于EH来说，Parquet更快，但对于所有其他数据集，ModelarDB更快，使用更少的存储空间。对于核心用例场景ER来说，ModelarDB比Cassandra、Parquet和ORC分别减少了34.57倍、286.03倍和45.99倍的查询处理时间。最后，对于EP, Cassandra和ModelarDB提供了最低的查询处理时间，ModelarDB快11.33倍。因此，在我们的实验中，ModelarDB与其他分布式系统相比，在核心情况下大大提高了查询处理时间，而在小规模聚合查询方面，ModelarDB与优化的单节点系统相比仍具有竞争力。

P/R的结果如图23-25所示。在P/R方面，InfluxDB和Cassandra表现最好，与我们的扩展实验中表现最差形成对比。显然，这些系统针对数据集的一个小子集的查询进行了优化，而Parquet、ORC和ModelarDB则针对大型数据集的聚合进行了优化。虽然P/R查询不是核心用例，但ModelarDB在大多数情况下为P/R查询提供了相当的性能，只是对于EH来说明显慢一些。与ORC和Parquet相比，ModelarDB通常更快，而且在最好的情况下，ER提供了1.63倍快的查询处理时间。在单个实例中，对于EH来说，ORC比ModelarDB快33.59倍，因为ORC禁用谓词下推将运行时间从47.64秒增加到1小时40分钟。然而，与Parquet和ORC不同的是，ModelarDB摄入的时间序列可以在网上查询。一个有趣的结果是DFCs增加了查询处理时间，特别是对于第一次查询。这表明，由于在初始查询期间内存不足，数据集被从磁盘读取并溢出到磁盘，随后的查询使用Spark的磁盘上格式执行。
对于我们的实验，其他系统需要权衡，因为它们要么擅长大聚合查询，要么擅长点/范围和小聚合查询，并支持在线分析，但不能同时支持两者。ModelarDB击中了一个最佳点，通过为大型聚合查询提供快速消化、更好的压缩和可伸缩性，提高了在线分析的最先进水平，同时在小型聚合和点范围查询方面保持了与其他系统的竞争力。任何竞争对手都没有提供这种功能组合。

8 相关工作

随着数据量的增加，使用模型管理传感器数据已经受到了很大的关注。我们提供了最相关的相关方法和系统的讨论。关于基于模型的传感器数据管理的调查，请参见[41]，而关于TSMSs的调查可参见[28]。
已经提出了以最小误差在线构建近似的方法[25]，或以最大片段长度进行更好的压缩的方法[34]。由于最优模型会随着时间的推移而变化，因此开发了使用多个数学模型的方法。在[37]中，时间序列中的每个数据点由集合中的所有模型近似表示。如果模型不能表示误差范围内的数据点，则从集合中移除该模型。当模型集为空时，存储压缩比最高的模型，并重新开始该过程。在[38]中讨论了段的关系模式。自适应近似算法[40]使用函数作为模型，采用可扩展的方法计算系数。AA算法逼近时间序列中的每个数据点，直到模型超过误差界限，并且为该模型创建了局部段，并且模型被重置。在所有模型都构造了一个局部线段之后，使用最少数量参数的线段被存储。文献[22]提出了一种基于回归的算法。它用单个多项式模型逼近数据点，然后随着误差界变得不可满足而增加系数的数量。当达到用户定义的最大系数数时，具有最高压缩比的模型被存储，并且时间序列被倒回到存储段的最后一个数据点。在本文中，我们提出了一种时间序列的多模型压缩算法，该算法改进了现有技术，因为它支持用户定义的模型，支持有损和无损模型，并消除了现有方法固有的压缩和延迟之间的权衡。
除了将时间序列表示为模型的技术之外，还提出了支持模型的关系数据库管理系统。MauveDB [21]支持使用模型进行数据清理，而无需将数据导出到另一个应用程序。模型是从一个包含原始数据的表中显式构建的，然后由关系数据库管理系统维护。以静态采样间隔创建的基于模型的视图充当模型的查询接口。FunctionDB [43]本身支持多项式函数作为模型。RDBMS的查询处理器在可能的情况下直接在这些模型上评估查询，并将查询结果作为离散值提供。模型拟合是通过将特定模型拟合到表中来手动执行的。已构建模型的维护不在本文讨论范围之内。柏拉图[29]允许用户定义模型。如果实现了必要的函数，则在模型上执行查询，如果没有实现，则执行离散值。为查询实例化模型的粒度可以用网格运算符指定，也可以留给柏拉图。将模型拟合到数据集是手动完成的，因为自动模型选择是留给将来的工作。Tristan [36]基于MiSTRAL架构[35]，使用字典压缩将时间序列近似为固定长度的时间序列模式序列。在摄取之前，必须根据历史数据离线训练字典。在摄取过程中，在应用压缩之前，会缓冲固定数量的数据点，并在必要时用新模式更新字典。对于近似查询处理，使用为时间序列存储的模式子集。[24]提出了一种基于模型的分布式时间序列存储方法，该方法使用基于内存树的索引、键值存储和MapReduce [20]。使用分段常数近似进行分割[41]。每个段都存储和索引两次，一次是按时间，一次是按值。查询处理是通过使用索引定位数据段，使用映射器从存储中检索数据段，最后使用缩减器实例化每个模型来执行的。ModelarDB找到了最佳位置，并在现有系统中没有的单一可扩展TSMS中提供了功能:在用户定义的误差范围内对时间序列进行存储和查询处理[21，29，43]，支持固定和动态大小的用户定义模型，这些模型可以在线拟合，而不需要任何类型的离线训练[36]，以及为时间序列的每个部分自动选择最合适的模型，同时每个片段只存储一次[24]。

9 结论和未来的工作

由于需要存储和分析来自可靠传感器的大量数据，我们提出了基于模块化模型的TSMS的通用体系结构以及使用该体系的具体系统ModelarDB。 我们提出了一种与模型无关的可扩展和自适应多模型压缩算法，该算法在用户定义的误差范围内支持无损和有损压缩。 我们还介绍了可在基于模型的TSMS中使用的常规方法和优化方法：（i）一种数据库模式，用于将多个不同的时间序列存储为（可能是用户定义的）模型，（ii）将谓词下推至键值的方法 利用所提供的模式的存储区；（iii）直接在模型上执行优化的聚合函数而无需动态优化器的方法；（iv）静态代码生成以优化投影的执行；（v）动态扩展性，允许用户定义的模型 无需重新编译TSMS即可添加和使用。该架构被实现为一个可移植的库，它与Apache Spark接口用于查询处理，与Apache Cassandra接口用于存储。我们的评估表明，与当前系统不同，ModelarDB在同一个系统中找到了最佳位置，实现了快速接收、良好压缩、几乎线性的横向扩展和快速聚合查询处理，同时还支持在线查询。该评估进一步展示了这些贡献如何有效地协同工作，以适应使用多个模型的数据集，实际误差远低于界限，以及ModelarDB如何随着离群值的增加而适度下降。
在未来的工作中，我们计划在多个方向上扩展ModelArdb:(1)通过开发新技术来索引由用户定义的模型表示的段，直接在用户定义的模型上执行相似性搜索，以及利用时间序列表示为模型来执行动态优化，从而提高查询性能。㈡通过将相关的传感器数据流表示为单个段流，减少大量传感器数据所需的存储。㈢通过删除或自动推断参数，进一步简化模型数据库的使用。