本文作者：钟荣荣 Presto TSC member/Commiter

将Alluxio与Presto联合运行在社区中越来越风行，应用固态硬盘或内存来缓存热数据集，可能实现近Presto worker的数据本地行，从而防止了近程读取数据导致的高提早。Presto反对基于哈希的软亲和调度（soft affinity scheduling），这样整个集群中雷同数据只缓存一、两个正本，更多的热数据能被缓存到本地，进步缓存效率。现有哈希算法在集群规模发生变化时成果并不现实。针对这一问题，本文介绍了一种可用于软亲和调度的新哈希算法——一致性哈希（consistent hashing）。

软亲和调度

Presto应用一种叫做软亲和调度（soft affinity scheduling）的调度策略，将一个分片（split, 最小的数据处理单位）调度到同一个Presto worker（首选节点）上。分片和Presto worker之间的映射关系是由分片上的哈希函数计算出来的，确保同一个分片总是被散列到同一个worker上。

在第一次解决分片时，数据将被缓存在首选worker节点上。当后续的查询处理同一分片时，这些申请将再次被调度到同一个worker节点上。此时，因为数据曾经缓存在本地，不须要再近程读取数据。

为了进步负载平衡，更好地解决worker节点响应不稳固的问题，会抉择两个首选节点。如果第一个节点忙碌或没有响应，则会应用第二个节点。数据可能会被物理缓存到两个worker节点上。

对于软亲和调度的更多信息，请查看“通过 Alluxio 数据缓存升高Presto提早”（https://prestodb.io/blog/2020...）

哈希算法

软亲和调度依附哈希算法来计算分片和worker节点之间的映射关系。原先应用的是取模函数：

该哈希策略很简略，而且在集群稳固、worker节点没有变动的状况下成果很好。然而，如果某个worker节点临时不可用或者掉线，worker节点的数量可能会发生变化，分片到worker节点的映射将全副须要重新分配，导致缓存命中率大幅降落。如果呈现问题的worker稍后从新上线，则须要再次重新分配。

针对这个问题，Presto在通过取模计算出哪个worker调配给特定分片时，会对worker总数取模，而不是正在运行的worker数量。然而，这只能缓解worker节点长期掉线造成的重新分配问题。有时候因为工作负载的稳定，减少/删除worker是正当操作。在这些状况下，是否可能放弃正当的缓存命中率而无需进行大规模的重新分配？

咱们的解决方案是一致性哈希算法。

一致性哈希

一致性哈希由David Karger在1997年第一次提出，是一种将网络拜访申请散发到一组数量时常发生变化的网络服务器的调配算法。该技术被宽泛用于负载平衡、分布式哈希表等。

一致性哈希的工作原理

比方，将哈希输入范畴[0, MAX_VALUE]映射到一个圆环上（将MAX_VALUE连贯到0）。为了阐明一致性哈希的工作原理，咱们假如一个Presto集群由3个Presto worker节点组成，其中有10个分片被重复查问。

首先，worker节点被散列到哈希环上。每个分片都被调配给哈希环上与该分片的哈希值相邻的worker（注：这里“相邻”定义为从分片哈希值所在位置，按顺时针方向找到的第一个worker节点）。

上述情况下，分片的调配如下：

删除一个worker

当初，如果worker2因为某种原因下线，那么依据算法，分片0、5和7将被调度到对应下一个哈希值的worker，也就是worker1上。

只有被调配到到已下线worker（在这里是worker2）的分片须要从新确定调配到哪个worker。其余数据不受影响。如果 worker32 稍后上线，分片 0、5 和 7 将会被重新分配到 worker2，不会影响其余worker的命中率。

减少一个worker

如果工作负载减少，须要在集群中减少另一个worker节点——worker4, worker4的哈希值在哈希环上的地位状况如下图所示：

在这种状况下，分片8将落入worker4的区间，所有其余分片的调配不受影响，因而这些分片的缓存命中率不会受到影响。重新分配的后果如下：

虚构节点

从下面能够看出，一致性哈希能够保障在节点变动的状况下，均匀只有

的分片须要被重新分配。然而，因为worker散布不足随机性，分片可能不会平均地散布在所有worker节点上。针对这一问题，咱们引入了“虚构节点 ”的概念。虚构节点可能在某个节点断开连接时将它的负载重新分配给多个节点，从而缩小因集群不稳固而造成的负载稳定。

将每个物理worker节点映射成多个虚构节点。这样虚构节点便代替原先的物理节点，位于哈希环上。随后，每个分片将首先被调配到相邻（顺时针方向最邻近）的虚构节点，再路由到虚构节点映射的物理节点。下图的示例是一种可能呈现的状况，即每个物理worker节点都对应3个虚构节点。

随着哈希环上节点数量的减少，哈希空间将被宰割地更平均。

在一个物理节点宕机的状况下，与该物理节点绝对应的所有虚构节点都将被从新散列。这里不是所有的分片都被重新分配到同一个节点上，而是会调配到多个虚构节点，从而映射到多个物理节点上，以达到更好的负载平衡。

如下图所示，当删除worker3时，分片2和3将被从新散列到worker2，而分片8被从新散列到worker1。

如何在Presto中应用一致性哈希？

这是咱们最近奉献给Presto的一个试验性功能。如果有动向进行测试或单干，请分割咱们。

应用该性能前，请先依据指南（https://prestodb.io/docs/curr...）或教程（https://docs.alluxio.io/os/us...）启用Presto的缓存。确保你抉择SOFT_AFFINITY作为调度策略的配置项。在/catalog/hive.properties文件中，增加hive.node-selection-strategy=SOFT_AFFINITY。

须要通过在config.properties中增加node-scheduler.node-selection-hash-strategy=CONSISTENT_HASHING来启用一致性哈希。

论断

如上所述，当减少或删除节点时，一致性哈希能够使工作负载重新分配所产生的的影响降到最低。当集群的worker节点发生变化时，基于一致性哈希算法进行工作负载在worker节点间的调配，能够尽量升高对现有节点上缓存命中率的影响。因而，在Presto集群规模依照工作负载的须要扩缩容的场景下，或者部署环境中的硬件设施不齐全受控而导致worker节点可能随时被重新分配和调整的场景下，一致性哈希策略都会成为一种更好的抉择。

在Alluxio社区，咱们始终在不断改进Alluxio和各类计算引擎（例如文中的Presto）在功能性和可用性方面的集成。随着在Presto调度中引入一致性哈希，Alluxio能够利用Presto的软亲和个性，实现更好的数据本地性和缓存效率，最终进步解决性能并降低成本。咱们将继续致对整个数据生态圈进行奉献，不断改进和优化咱们的产品。