共计 2938 个字符，预计需要花费 8 分钟才能阅读完成。
本文作者：钟荣荣 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 的软亲和个性，实现更好的数据本地性和缓存效率，最终进步解决性能并降低成本。咱们将继续致对整个数据生态圈进行奉献，不断改进和优化咱们的产品。
