TSCache: An Efficient Flash-based Caching Scheme for Time-series Data Workloads
时间序列数据库正在成为当今数据中心不可或缺的组成部分。为了管理快速增长的时间序列数据，我们需要一个有效有效的系统解决方案来处理巨大的时间序列数据查询流量。有前途的解决方案是部署高速、大容量的缓存系统，以减轻后端时间序列数据库的负担，加快查询。然而，时间序列数据与其他传统数据有很大的不同，这不仅带来了挑战，也带来了机遇。在本文中，我们提出了基于闪存的时间序列数据缓存系统的设计TSCache。我们开发了一套基于平板电脑据管理、两层数据索引结构、自适应时间感知的缓存策略和低成本压缩过程等优化方案。我们实现了一个基础Twitter的Fatcache的原型。实验结果表明，TSCache能显著提高客户端查询性能，有效提高带宽6.延迟减少了84倍.2%。
1 INTRODUCTION
时间序列数据库正成为当今数据中心不可或缺的组成部分[33、34]。近年来，我们见证了时间序列数据在数据分析[2、49、67]、物联网部署[40、72]、互联网监控[57、65]、系统报警和诊断[33、34]、数据挖掘[48、51]、可视化[59]、许多其他应用[34、39、41、60]等各种应用中的广泛应用。
时间序列数据是一段时间内收集的数字数据点序列[31、32]，如股价、传感器读数、异常事件计数等。时间序列数据非常有趣，因为它为用户提供了跟踪时间变化的能力，这使得我们可以提取有价值的动态信息，通常无法通过单独检查每个单独的静态快照获得。然而，由于此类数据的性质，处理庞大而快速增长的时间序列数据集需要高效的系统设计。例如，Twitter的Observability堆栈通常收集1.每分钟测量7亿，每天查询[11]多达2亿。高速查询处理时间序列数据是理想的，但实现起来很有挑战性。一个简单的解决方案是把整个时间序列数据库放在内存中，比如谷歌s Monarch[34]。这种方法虽然有效，但会导致部署成本过高，尤其是考虑到时间序列数据量的不断增加。然而，
1.1 Challenges and Opportunities
时间序列数据是特殊的。一些独特的特点使其与传统闪存缓存系统中的数据处理完全不同[6、46、61、70]。在处理时间序列数据查询时，必须充分利用这些独特的优化机会，解决一系列关键挑战
特性#1:。收集时间序列数据，记录时间间隔特定度量的演变。换句话说，时间序列数据反映了过去一段时间发生的事实。这样的数据只是历史数据点的流动，本质上是不被修改的。因此，时间序列数据是不可变的，只能添加[32]。事实上，许多时间序列数据库，如BTrDB[41]为管理时间序列数据提供了一个特殊的抽象数据，只写一次。
属性#2:时间序列数据通常用于趋势预测或行为分析，集合的趋势预测或行为分析。单个数据点通常很无聊。因此，与传统数据库不同，范围查询通常是时间序列数据库中的主要操作[28、39、41、63]。
，有几个原因。。其次，常规缓存采用无缓存方法。缓存访问要么成功，要么失败。相反，时间序列缓存必须考虑一些成功（缓存查询的一些数据点）
行为分析、趋势预测、问题诊断和警报等大多数时间序列数据应用，3,39]。Facebook报告称，他们至少85%的查询集中在过去26小时收集的数据点[65]上，这意味着用户对时间序列数据的兴趣与数据创建时间密切相关。随着时间的推移，这种兴趣会迅速减弱。另一方面，我们应该注意到，一些旧的数据测量也会引起人们的兴趣。例如，Etsy的Kale在整个时间序列中，系统定期搜索历史数据，以找到具有类似模式的异常[12、39]。这两种模式可以混合使用，从而进一步增加了做出缓存决策的难度。
1.2 Flash-based Caching for Time-series Data
在本文中，我们提出了一个其目标是提供高效的缓存解决方案timeseries数据库的查询性能。据我们所知，这是第一个基于它的flash缓存时间序列数据。。与Memcached[25]类似，TSCache与后端时间序列数据库不直接交互意味着TSCache允许客户机和数据库服务器之间的中间层TSCache同时为各种时间序列数据库提供通用缓存服务。抽象作为时间序列缓存服务，TSCache它为用户提供了一个基于时间范围和类似键值的简单接口，方便用户在缓存中存储和检索数据。
在我们的设计中，。这极大地简化了我们的缓存设计，并允许我们开发一种类似于日志的机制来存储和管理大量的缓存数据，这是优化的I/O性能和管理成本降低。(3)时间序列工通过所有这些特殊的设计和优化，我们可以构建有效的时间序列数据缓存。
。例如，[43,45,52]。TSCache中的I/O操作并行化，使用flash SSD内部并行性[44，47]。TSCache内存过内存slab以大的形式刷新组织大的、有序的写作操作，在性能和耐久性方面受到闪存的青睐[38、45]。
为了评估tscache的性能。。我们使用五个现实世界的时间序列数据集来评估TSCache，包括车辆交通、比特币交易、空气污染测量、环境传感和出租车轨迹数据。实验结果表明，时间序列缓存设计显著提高了客户查询性能，带宽提高了6.延迟减少了84倍.2%。
3 DESIGN
在本文中，。tscache目标是为时序数据库客户端提供基于网络的独立缓存服务。
如图1所示，使用TSCache典型的工作流和Memcached类似。如果在缓存中找到数据，缓存服务器将检索数据并返回客户端；否则，客户端将收到NOT_FOUND，后端数据库需要直接查询，然后将接收到的时间序列数据发送给缓存服务器，以缓存和服务于未来的查询。数据点直接插入后端数据库，不涉及TSCache，这意味着TSCache不在关键路径中。这种设计给时间序列工作负载带来了两个重要优势。首先，它将缓存从任何特定的数据库中分离出来，允许我们为各种类型的时间序列数据库提供通用和共享的缓存服务。其次，它类似于流行的键值缓存服务，如Memcached[25]和Redis[27]许多开发人员和从业人员都熟悉这些服务，这使得它们在实践中得到轻松顺利的应用。
3.1 Architecture Overview
如图2所示，TSCache有五个主要组成部分接口：为客户机提供一个通用和简化的接口来存储和检索时间序列数据，通常是从时间序列数据库返回的数据点的集合。SCache采用了基于Slab连续数据点的序列是容纳大量块数据，一次写一次以上。(:基于时间段的搜索采用两层数据索引结构，快速过滤不相关数据点。为了识别最有价值的缓存数据，设计了一种自适应缓存替换方案，优化了时间序列工作负载下唯一的访问模式。在后台运行低成本压缩过程，去除重复数据点，优化缓存空间的利用。
.2 Time-range based Interface
传统的缓存系统是为单独缓存数据对象或块而设计的。，比如一个键、一个对象ID或一个块号等。，该时间范围是一个包含一系列数据点的逻辑数据集。然而，我例如，客户机可能需要放大/缩小并检查时间序列数据的子范围。
为了解决上述问题，前者定义一个特定的查询条件，后者定义一个连续的时间范围。通过这种方式，我们可以跟踪一个特定的查询，在我们的缓存服务器中有哪些时间范围的数据点可用。
界面设计。。具体来说，我们使用不包括时间范围部分的数据查询语句来计算160位的SHA-1哈希值[1]作为我们在libMemcached库中提供了一个API函数，作为帮助用户快速为给定的查询语句生成哈希键的工具。然后，该键被用作与缓存服务器交互的句柄。由于SHA-1哈希，查询可以用键唯一标识。这种方法有几个好处。。
API函数。该密钥是根据数据查询语句使用SHA-1加密哈希函数计算出的160位摘要。该值是一个JavaScript对象表示法(JSON)[23]文件，包含一组编码过的数据点，可以在不同的平台上共享。。。要从缓存服务器检索数据点，它需要满足两个条件:键应该匹配，并在此基础上，请求的时间范围应该被缓存的数据覆盖。返回给客户机的数据点被编码为JSON文件，以保证其完整性。
3.3 Handling Partial Hits
在传统缓存中，请求的数据对象要么在缓存中找到(命中)，要么没有找到(未命中)，与此不同的是，在时间序列缓存中可能会出现一种特殊情况，即部分命中。例如，
我们有两个可能的选择来处理部分命中的情况:(1)缓存将部分找到的数据返回给客户端，然后客户端向数据库提交另一个查询来检索缺失的部分，或者(2)缓存通知客户端INCOMPLETE，然后客户端提交完整的查询到数据库加载完整的数据。
Handling partial hits
为了理解上述两种选择对性能的影响，我们设计了一个实验来比较它们的I/O效率。为了模拟部分命中场景，我们将请求分为两个操作，首先从缓存读取，然后按顺序从后端数据库读取，并计算每个请求所引起的延迟的总和。关于系统设置的更多细节请参见第5节。
。对于小于512 KB的请求，花费在数据库服务器上的时间占据了查询延迟，这意味着分割一个相对较小的请求不会带来太多的性能好处。但是，对于较大的请求(超过512 KB)，从缓存服务器检索数据(即使是部分)也是有帮助的。对于4-MB的请求，从缓存读取一半的请求可以减少36.2%的平均延迟，而不是从数据库读取全部请求。这个结果表明，从缓存加载部分数据的好处取决于请求的大小。TSCache采用自适应方法处理局部命中。(1)如果请求的数据大小很小(在我们的原型中小于512 KB)，我们将部分命中简单地视为未命中，并快速响应客户端，而无需进一步搜索缓存，客户端需要向数据库服务器提交一个完整的请求。(2)对于较大的请求，我们将缓存服务器中找到的部分数据返回给客户端，客户端需要创建另一个部分请求来从数据库服务器加载剩余的数据。
这里值得注意的是，无论它们的创建时间(新或旧)，只要两个查询有部分重叠的数据，就会发生部分命中。TSCache只有在检索部分命中的数据具有成本效益时才有选择地返回缓存的数据，这可以避免前面讨论过的不必要的开销。
Request size estimation.
部分命中的自适应处理要求对请求的数据量进行估计。如果部分数据太小，我们希望快速响应客户端INCOMPLETE。但在现实中，缓存服务器很难做出准确的估计，因为对于给定的请求，所涉及的数据点的数量和每个数据点的大小都是未知的。我们可以简单地扫描缓存来查找相关的数据点，但是这种方法显然非常耗时，并且阻碍了快速响应客户机的工作。TSCache估计数据大小如下所示。数据写入缓存服务器,我们知道的时间范围푇和数据量푉,基于估计就可以计算数据密度。密度信息与时间范围相关联，并作为元数据的一部分存储在关键索引中(参见第3.5节)。在时间范围푡读请求,数据量估计。通过这种方式，我们可以快速估计查询中涉及到多少数据，并决定是否只通过访问键索引来处理部分命中。
3.4 Slab Management
时间序列数据只写一次，只追加。我们利用这个属性并使用类似日志的机制来管理大块数据。在TSCache中，数据管理的基本单元是一个平板，它按时间顺序存储一系列时间序列数据点。因此，每个板代表数据的一个时间范围。
如图5所示，每个slab是一个独立的、自包含的单元，它存储连续时间范围的一系列数据点和相关的元数据。平板由两部分组成，头和数据。头部分包含描述数据部分的元数据，并促进对查询的快速搜索;数据部分存储按时间顺序排序的数据点列表。
为了理解我们的板结构设计的基本原理，我们首先解释一个我们必须解决的关键挑战。在时间序列缓存中，缓存的数据点可以与多个查询关联，每个查询由一个查询键表示。简单地将键映射到由于查询结果可能重叠，单独的数据点集将导致严重的缓存数据冗余。或者，我们可以将多个键映射到每个共享数据点。然而，由于数据点数量庞大，构建多键对多数据点映射结构是不现实的。简单地记录每个查询的开始和停止位置也是不可行的，因为不同查询的数据点可能由于时间范围重叠而混合。我们使用基于标签的反向映射来解决这个问题。我们将每个数据点与一组称为位数组的标志位(128位)相关联。每个位对应于slab中的一个查询键。设置位表示数据点与查询关联。位数组本质上是以一种节省空间的方式标记数据点的键。为了完成反向数据点到键的映射，我们需要在slab头部中有另一个结构，如下所述。
3.5 Two-layered Data Indexing
高效的数据索引结构对查询性能至关重要。在TSCache中，我们使用一个两层的内存数据索引结构来满足这一需求。如图6所示，两个独立的索引结构，关键索引和平板索引，彼此独立，为不同的目的而设计。
key index ，无论是在缓存中找不到查询键，还是找到了请求的键但没有找到请求的时间范围。。第一级是由查询键索引的传统哈希表。每个键都与一个单独的时间范围序列相关联，该序列以跳跃列表结构组织[66]。在向缓存中添加新时间范围时，将合并任何重叠的时间范围，以确保键的时间范围不重叠。对于一个给定的键，如图7所示，它的时间范围被组织成一个4级的跳跃列表。每一项代表一个单独的时间范围[time_start, time_end]。每个关卡都是一个单独的链接列表。最底层(0级)是按照升序排序的所有时间范围项目的完整列表。每个较高的级别(级别1到级别3)都提供了所选项目的参考点列表。级别越高，列表越短。通过跳跃列表的结构，我们可以快速地跳过不相关的时间范围，并找到目标时间范围，从而加快了长列表的搜索速度。我们发现4个关卡的跳跃列表对于我们的工作负载来说已经足够了。关于skip list的更多细节可以在之前的工作中找到[66]。
Slab index.
slab索引跟踪缓存中的所有slab。对于每个slab，我们在内存中维护一个28字节的slab节点来管理它的元数据，包括一个4字节的slab ID (SID)、一个8字节的Bloom过滤器和两个8字节的时间戳，它们表示slab中数据点的物理时间范围。
与列存储数据库类似，。由于一个典型的时间序列度量只有4到10个字段，所以在大多数情况下，16个bucket的哈希表就足够了。
。我们将属于虚拟时间范围的slab节点连接起来，使用一个单链表，按升序排列。请注意，列表中的石板可能有重叠的物理时间范围。定期运行一个压缩过程来删除重复的数据(参见3.7节)。
。(1)在slab节点中，，我们简单地跳过它并检查下一个slab;否则，(2)我们将进一步将目标时间范围与slab的物理时间范围进行比较，后者记录了slab中的第一个和最后一个时间戳。如果请求的时间范围完全或部分在slab的物理时间范围内，我们然后从缓存读取slab;否则，我们就跳过这个slab，检查列表中的下一个。通过这种方式，我们可以快速地过滤掉不相关的slab，而不会引起不必要的I/ o(读取slab头)，提高缓存查找速度。
。对于具有键和指定时间范围的缓存查询，它的工作方式如下。如果时间范围被部分命中，我们运行请求大小估计器(参见第3.3节)来决定是否将部分数据返回给客户端。在命中或部分命中的情况下，我们进一步转向平板索引结构。对于每个请求的字段，我们首先定位所涉及的虚拟时间范围，然后定位所涉及的sl
Time-aware Caching Policy
Cache replacement policy
如图8所示，我们将缓存逻辑地划分为两个分区，使用不同的缓存策略分别对它们进行管理.The upper-level LRU partition维护一个slab列表，。。低层FIFO分区维护按时间顺序排列的板的列表，并使用简单的FIFO替换算法进行管理。分区大小会根据运行时的工作负载自适应地自动调整。
我们的缓存策略如下所示。当一个slab被添加到缓存中，它首先被插入到低层FIFO分区。由于大多数时间序列工作负载对最近的数据更感兴趣，我们将FIFO列表分成两个大小相等的部分(旧的和新的)。在重新访问一个slab，如果它是在FIFO列表的前半部分(更新的)，slab仍然在FIFO列表中的当前位置没有行动;否则，被提升到上层LRU分区。同时，LRU分区中最近最少使用的(LRU)板被降格到FIFO分区，并根据其时间插入到列表中。对于驱逐，我们总是选择FIFO列表尾部最老的slab作为驱逐的受害者slab。设计原理如下:我们使用FIFO分区以原始的时间顺序管理大多数板，这确保最近的板在缓存中停留的时间更长，旧的数据将首先被驱逐。然而，如果一个相对古老的slab被重新访问，这意味着这个slab可能覆盖一个热的时间范围。因此，我们将其提升到LRU区域，并给它第二次机会，使其在缓存中停留更长时间。如果一个slab在LRU列表冷却，它将降级到FIFO列表，并最终驱逐。
5 EVALUATION
Workloads.
我们使用时间序列基准YCSB-TS[7]为我们的实验生成具有不同时间范围的查询。每个查询在“最新分发”之后有一个时间范围[time_start, time_end]。每个查询的时间范围长度遵循在配置中定义的maxscanlength和minscanlength之间的Zipfian分布。除时间范围部分之外的所有查询都用作缓存键，遵循Zipfian分发。
我们配置一个Full工作负载，查询的时间范围从一分钟到一周不等，代表了实践中的一个典型用例。Traffic、BTC、Pollution、Sensor和Trajectory的平均请求大小分别为15.11 KB、13.68 KB、15.15 KB、10.12 KB和24.77 KB。对于每个数据集，我们按照YCSB-TS中定义的Zipfian分布，生成100,000个具有可变时间范围的查询。我们在总体比较和组件研究中使用这种工作量进行实验。
Overall Comparison
我们展示了使用一组时间序列数据工作负载加速查询的TSCache的总体性能。为了确保每个实验都以相同的状态开始，我们首先创建一个数据库并将数据点加载到数据库中，在每次运行中，我们都从加载的相同数据库开始
我们将TSCache与其他三种系统解决方案进行了比较。我们的基线案例是一个非缓存、仅运行数据库的系统，它运行一个。(2)。TSCache使用一个额外的缓存服务器。。对于这两个仅使用数据库的系统，我们还配置了一个基于ssd的设置，，以研究存储设备的效果。为了与通用缓存解决方案进行比较，我们基于Twitter的Fatcache[10]实现了一个简单的时间序列缓存(记作Fatcache)。时间序列数据流使用固定大小的时间单位划分为块，类似于之前的工作[71]。每个块作为一个单独的缓存单元存储在缓存中，并根据其查询和时间范围建立索引。
与两个仅使用数据库的系统相比，TSCache在所有5个工作负载中获得了最佳的整体性能。通过缓存10%的数据集，TSCache提高了2.7倍的带宽，比Single-DB减少了63.6% 84.2%的平均延迟。如果与双服务器配置的Dual-DB相比，TSCache的带宽增加了1.7倍3.4，延迟减少了42.3% 68.6%。
Performance vs. cache size
我们还在图11中测量了缓存大小对性能的影响。我们将缓存大小从工作负载数据集大小的4%配置到10%。随着缓存大小的增加，带宽和命中率也会增加，而延迟则会减少。特别是随着缓存大小的增大，TSCache的命中率提高了23.7 48 p.p.，从而导致带宽增加了1.6 2.4倍，时延降低了34.2% 57.6%，这充分说明了缓存系统的有效性