Facebook Presto是一个以SQL语言作为接口的分布式实时查问引擎，能够对PB级的数据进行疾速的交互式查问。它反对规范的ANSI SQL.蕴含查问、聚合、JOIN以及窗口函数等。

Alluxio将其在数据层的翻新作为Presto和各种剖析应用程序和用例的要害反对技术。它创立了一个虚构数据层，能够聚合来自任何文件或对象存储的数据，提供跨存储系统的对立命名空间，并容许应用程序持续应用原有的行业标准接口来拜访数据，同时可能为Presto提供内存级别的速度和响应工夫。

为了进步申请的响应速度，Presto正在摸索缓存容量与缓存命中率对于性能的影响。Presto须要通过Alluxio晓得某些对于缓存的信息，从而判断当一个集群被缓存大小所限度时，扩充缓存容量是否可能帮忙集群进步缓存命中率以及申请的响应速度。同时这些信息也可能对摸索缓存算法潜在的优化策略提供肯定的帮忙。在此基础上，为了更好的负载平衡和效率，Presto想要通过这些信息优化缓存扩容的路由算法。于是如何更好的对Alluxio缓存数据进行追踪治理，就成了presto优化决策的要害。

针对下面Presto提出的需要，咱们提出两个关键问题：

运行的应用程序须要多大的缓存？

缓存的命中率晋升的极限在哪里？
咱们提出Shadow cache：用于追踪工作集大小和缓存命中率的轻量级Alluxio组件。首先为解决第一个问题，Shadow cache会告知管理者在过来24小时之内缓存一共承受到了多少互不反复的bytes，依此能够预计出将来缓存的需求量。此外为解决另一个问题，Shadow cache将会告知管理者在缓存可能将过来24h的所有申请全副保留的状况下申请命中缓存的数量，也就是说，未命中的都是从未呈现过的数据，而这就意味着失去了缓存最大命中率。

这个轻量级的Alluxio组件Shadow cache可能提供相当于有限缓存空间下，缓存工作集大小以及缓存命中率的趋势。因而，咱们定义以下要害指标，心愿这些指标可能为咱们察看集群缓存状态提供帮忙：

C1: 在一段时间内的真正的缓存占用空间大小

C2：Shadow cache在一个工夫窗口中的工作集

H1：实在缓存命中率

H2：Shadow cache的缓存命中率

想要为Alluxio的缓存提供上述指标是十分困难的，在实际尝试的过程中咱们也遇到了方方面面的问题，咱们将Shadow cache面临的挑战归类为以下三个方面：

低开销：作为一个跟踪缓存工作集大小的轻量级组件，留给Shadow cache的内存很小，利用无限的内存去追踪“有限”的工作集是相当艰难的。另外，因为Shadow cache是在每次利用查问缓存时对本次查问的数据进行解决，Shadow cache也必须要做到低CPU开销，否则将会导致用户的申请被长时间梗塞。

高精准：Shadow cache也必须要有精度上的保障，在Presto中，Shadow cache被用于评估集群的缓存情况，如果预计的极限缓存命中率过小，可能会使Presto谬误的判断此作业是缓存不敌对的；相同的，如果预计的极限缓存命中率过大，可能导致Presto认为此时集群扩充缓存可能极大地晋升整体性能。

实时性：Presto以及其余大多数利用在现在都只关怀可能反映以后或将来趋势的最新项。因而，实时地将过期的项抛弃对于Shadow cache也是相当重要的。否则，很有可能对决策带来乐音烦扰。【滑动窗口】便是记录最新项的驰名技术之一，然而为滑动窗口模型设计数据结构也不是一件简略的事件。每当窗口滑动时，都须要咱们实时地删去那些刚刚被移出窗口的项。如何找到须要被删的项以及尽量快的删去它成为了一个重要的问题。


既然提到了高精准与低开销两个需要，那么咱们首先就想到了在各类分布式数据库中大放异彩的布隆过滤器，基于布隆过滤器，Shadow cache便实现了对工作集大小和极限命中率的预计。上面咱们来对布隆过滤器做一个简略的介绍：

布隆过滤器是一个以bit为单位的初始化全0的数组，它将每个项映射为几个bits，极大的节俭了空间上的开销，并可能以极高的效率进行查问。布隆过滤器可能判断项是否存在，若布隆过滤器返回该项不存在，则项肯定不存在。反之，则该项不肯定存在。

布隆过滤器领有k个hash函数，在插入一个项时，会对此项别离进行k次hash运算，并失去k个地位，将在过滤器中对应地位的bit将被置为1。而须要查问时，则依然对项进行k次hash运算，若失去的k个地位上所有bit都为1，那么判断此项存在，否则判断此项不存在。具体过程如上图所示。


既然布隆过滤器可能同时满足开销小和精度高的两种需要，那么咱们可能间接将布隆过滤器利用于Shadow cache中吗？

首先咱们遇到的问题就是布隆过滤器不反对删除，咱们不关怀比拟长远的工作集负载状况，而只关怀用户的应用程序在过来的一段时间中的工作集大小，这就要求Shadow cache必须做到可能将过期的项删去，为了做到这一点，Shadow Cache将多个过滤器连贯到一起，组成了布隆过滤器链。上面咱们来看看如何通过布隆过滤器链，实时地对工作集负载大小进行更新。

查问：如上图所示，Shadow cache是由多个布隆过滤器所组成的链，如果咱们须要跟踪的是用户过来24h的工作集大小，那么能够将24h分为4个时间段，对应每个时间段Shadow cache有一个布隆过滤器，每个布隆过滤器都跟踪一个时间段。对于一个项的查问，Shadow cache会将所有布隆过滤器相“或“失去新的布隆过滤器，再对新的布隆过滤器进行此项的查问，如下图所示：

更新：而为了保证数据的实时性，当工夫窗口进行滑动时，咱们须要Shadow cache抛弃曾经过期的数据。也就是说须要随着工夫t不断更新布隆过滤器中的数值，将布隆过滤器中曾经处于工夫窗口外的项删掉。如下图所示，因为咱们是将多个布隆过滤器组合在了一起，因而，很容易判断过期的项的地位，它们就处于最末端的布隆过滤器中。于是每当一个新的时间段到来，咱们就从链中删去最老的过滤器，并新增一个全空的过滤器来记录最新数据。

工作集大小：布隆过滤器将一个项映射为多个 bits，若将工作集大小直接判断为bit为1的数量将会带来不可承受的误差，因为某一bit可能代表多个项，而某一项也被扩散为了多个bits，于是在这里咱们应用了Swamidass & Baldi (2007) 所推导出的以下公式对工作集大小进行估算，并获得了良好的成果：

其中是被插入进过滤器中所有元素的估计值，m是过滤器的长度（大小），k是hash函数的个数，X是所有被置为1的地位的个数。

极限命中率：在提供了工作集大小这一指标后，Shadow cache还须要提供极限命中率这一指标。因为布隆过滤器可能以极小的内存使用量跟踪巨量的数据，咱们能够将布隆过滤器视作一个空间大小为有限的缓存，因而，“用户申请“命中布隆过滤器的数量就相当于命中一个有限大小的缓存的数量，咱们将此数量记为hit，而“用户申请”的总数量记为queryNum，于是极限命中率就等于hit/queryNum。

在实现布隆过滤器链之后，咱们就能够轻松得悉之前定义的指标H1、H2、C1、C2，之后Presto能够通过比拟它们之间的大小关系来判断集群的缓存状态，如下图所示：

当H2比拟低时，表明就算领有有限的缓存空间，也不能使得缓存命中率达到现实的数值，因而阐明该集群中运行的利用是缓存不敌对的。当H2高H1低且C2>C1时，阐明集群的缓存空间调配有余，如果扩充缓存容量，命中率可能进一步提高；而当H2高H1高且C2>C1时，证实集群状态良好，无需对缓存进行缩放。

Shadow cache的布隆过滤器实现是基于Guava库的，并且反对依据用户自定义的空间开销，窗口大小等参数抉择过滤器的具体配置。目前Shadow cache反对统计的工作集单位包含pages和bytes，别离代表工作集蕴含多少页以及工作集蕴含多少具体bytes。而对于命中率的计算，Shadow cache 能够以byte为单位记为一次命中，同样的也能够用一个对象为单位来记为一次命中。

配置项如下图示：


咱们对Shadow cache进行了试验评估，发现仅需125MB的空间，Shadow cache就能追踪27TB的工作集，并且错误率仅有3%。并且错误率还能够通过HyperLogLog算法进一步缩小，但如果应用HyperLogLog就将不反对极限命中率的预计。


在利用Shadow cache得悉集群的具体状态后，如果集群状态不良，Presto须要一些伎俩来及时的调整集群，以此进步集群的响应速度。咱们接下来先介绍目前presto的路由算法，而后给出几种在退出Shadow cache之后可选的路由优化计划。

Presto将不同的表存储在不同的集群中，以表名在各个集群之间分享缓存。因而，当一个对于某表申请到来时，该申请总会被发往雷同的集群。如果不这样做的话集群的缓存就容易被各种芜杂不一的表充斥，不能施展缓存的成果。上面咱们通过一张图来阐明路由逻辑：

如上图所示，table 1到table4有着不同的表名，因而被调配到不同的集群中 。当申请table1中的数据时，路由逻辑将会把此申请发往cluster1，而申请table3中的数据时，路由逻辑将把申请发往cluster3。

判断一个集群是否失常的一个简略计划就是看一个指向某个集群的申请的响应工夫，若该集群迟迟没有回应或回应的工夫过长，咱们就认为该集群呈现了问题。在有了Shadow cache之后，就像上文所提到的，联合H1、H2、C1、C2，咱们能够疾速判断一个集群是否是因为缓存有压力而呈现的性能降落。

对于这样一个体现不佳的集群，Presto提出以下三种路由优化计划：

计划一：当次要集群正忙时，咱们有一个指定的也领有该缓存的第二集群会被启用来为申请进行服务。但这种办法会在每个集群中占用额定的缓存空间。

计划二：两个集群都被视为主集群对申请进行服务，并且在这两个集群中进行负载平衡，然而这种计划将会使得缓存磁盘空间占用倍增。

计划三：基于申请的模式来替换各集群中的表，进而让CPU占用的散布更加平均。同样的，这种计划也有问题：会使得缓存散布不平均从而须要额定的缓存空间。

对用户缓存中的工作集大小进行追踪估算是一项重要而又富裕挑战性的工作，为此咱们基于布隆过滤器设计了一个轻量化的Alluxio组件Shadow cache。因为咱们只关怀用户工作集大小的最新状况，因而须要应用工夫窗口模型来淘汰过期项，为此Shaodow cache将工夫窗口拆分为4段，每段用不同的布隆过滤器进行跟踪，每次淘汰时只需删除最早创立的布隆过滤器，再创立一个新的布隆过滤器追踪最新数据。最初，须要提供工作集大小时，咱们用到了Swamidass & Baldi (2007) 提出的基数预计公式。

总体来看，Shadow cache为Presto提供了四种不便的指标：H1、H2、C1、C2，其中H1、C1别离代表实在缓存命中率和容量，而H2、C2则代表着缓存的极限命中率以及一段时间内用户的工作集大小。基于以上的四种指标，Presto可能轻松的判断缓存容量与利用性能之间的关系 ，并进一步摸索路由算法的优化策略。