本文作者：钟荣荣 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推迟”（prestodb.io/blog/2020/0…）
哈希算法
软亲和调度依托哈希算法来核算分片和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的一个试验性功用。假如有意向进行测验或合作，请联系咱们。
运用该功用前，请先根据攻略（prestodb.io/docs/curren…）或教程（docs.alluxio.io/os/user/sta…）启用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的软亲和特性，完成更好的数据本地性和缓存效率，最终提高处理功能并下降成本。咱们将继续致对整个数据生态圈进行奉献，不断改进和优化咱们的产品。
