将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延迟”

哈希算法

软亲和调度依靠哈希算法来计算分片和 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 的一个实验性功能。如果有意向进行测试或合作，请联系我们。

使用该功能前，请先根据指南或教程启用 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 的软亲和特性，实现更好的数据本地性和缓存效率，最终提高处理性能并降低成本。我们将持续致对整个数据生态圈进行贡献，不断改进和优化我们的产品。