共计 4559 个字符，预计需要花费 12 分钟才能阅读完成。
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 可能轻松的判断缓存容量与利用性能之间的关系，并进一步摸索路由算法的优化策略。
