写点什么

在 Presto 中利用一致性哈希算法增强动态集群的数据缓存本地性

作者:钟荣荣,Alluxio 软件工程师 & Presto TSC member/Committer

  • 2022-05-11
  • 本文字数:2486 字

    阅读完需:约 8 分钟

在Presto中利用一致性哈希算法增强动态集群的数据缓存本地性

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 节点)。



上述情况下,分片的分配如下:

 

Worker1

Split1, Split4, Split6, Split8

Worker2

Split0, Split5, Split7

Worker3

Split2, Split3, Split9

 

删除一个 worker

 

现在,如果 worker2 由于某种原因下线,那么根据算法,分片 0、5 和 7 将被调度到对应下一个哈希值的 worker,也就是 worker1 上。

Worker1

Split0, Split1, Split4, Split5, Split6, Split7, Split8

Worker3

Split2, Split3, Split9

 

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

增加一个 worker

 

如果工作负载增加,需要在集群中增加另一个 worker 节点——worker4, worker4 的哈希值在哈希环上的位置情况如下图所示:



在这种情况下,分片 8 将落入 worker4 的区间,所有其他分片的分配不受影响,因此这些分片的缓存命中率不会受到影响。重新分配的结果如下:

Worker1

Split1, Split4, Split6

Worker2

Split0, Split5, Split7

Worker3

Split2, Split3, Split9

Worker4

Split8

虚拟节点

 

从上面可以看出,一致性哈希可以保证在节点变化的情况下,平均只有



的分片需要被重新分配。然而,由于 worker 分布缺乏随机性,分片可能不会均匀地分布在所有 worker 节点上。针对这一问题,我们引入了“虚拟节点 ”的概念。虚拟节点能够在某个节点断开连接时将它的负载重新分配给多个节点,从而减少因集群不稳定而造成的负载波动。

 

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

 


Worker1

Worker1_v1

Split6

Worker1_v2

Split0

Worker1_v3

Split1

Worker2

Worker2_v1

Split5, Split7

Worker2_v2

Split4

Worker2_v3

Split9

Worker3

Worker3_v1

Split2, Split3

Worker3_v2

 

Woker3_v3

Split8

 

随着哈希环上节点数量的增加,哈希空间将被分割地更均匀。

 

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

 

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

 


Worker1

Worker1_v1

Split6

Worker1_v2

Split4, Split8

Worker1_v3

Split1

Worker2

Worker2_v1

Split5, Split7

Worker2_v2

Split0, Split2, Split3

Worker2_v3

Split9

 

如何在 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 的软亲和特性,实现更好的数据本地性和缓存效率,最终提高处理性能并降低成本。我们将持续致对整个数据生态圈进行贡献,不断改进和优化我们的产品。

2022-05-11 11:183897

评论

发布
暂无评论
发现更多内容

探索科研项目计划管理系统的10大软件

易成管理学

项目管理 科研项目

2024年工作任务系统:9款必备工具

易成管理学

任务管理 任务管理工具

项目管理系统:如何根据需求挑选?

易成管理学

项目管理

一步迈入数智化,华为坤灵助力中小企业轻松飞跃

脑极体

AI 数智化 分销

实现-最佳实践-善于分享V3

南山

个人成长

实现-最佳实践-要事第一V3

南山

个人成长

从“群聊”到“一单到底”,天润融通工单系统助力品牌服务升级

天润融通

crm、scrm、ocrm、acrm、ccrm等等分别是什么?有什么区别?

百度搜索:蓝易云

PHP表单token验证防CSRF攻击

百度搜索:蓝易云

实现-最佳实践-难事开头V3

南山

个人成长

实现-最佳实践-适应高度刺激V3

南山

个人成长

如何选择适合的采购管理软件

易成管理学

采购管理

精通Java并发锁机制:24种锁技巧+业务锁匹配方案(第一部分)

肖哥弹架构

Java 高并发

文心快码Baidu Comate荣获2024北京信息通信行业网络安全产品优秀应用案例

百度安全

实现-最佳实践-睡前复盘V3

南山

AM Green收购Chempolis下一代2G生物燃料技术;投资10亿美元生产SAF

财见

实现-最佳实践-蒜蓉扇贝V3

南山

个人成长

实现-最佳实践-人生规划V3

南山

个人成长

实现-最佳实践-学做一道菜V3

南山

个人成长

九款装修进度管理软件全面评测

易成管理学

装修进度管理软件

一个示例了解什么是 API 集成

幂简集成

API API集成

百度副总裁陈洋:大模型让软件开发更高效、更安全

百度安全

云服务器建网站教程

百度搜索:蓝易云

实现-最佳实践-资料查找V3

南山

个人成长

Groovy 是一门 DSL 语言

FunTester

腾讯云AI代码助手:智能AI代码助手 ,新一代的高效代码开发辅助工具

鸽芷咕

腾讯云 科技 代码自动生成

科研项目计划管理系统的10款必备工具

易成管理学

项目管理 科研项目

实用采购工具,助你优化费用管理

易成管理学

采购管理 采购费用管理

2024网安周 | 百度安全深度参与,探索人工智能与数字安全的融合发展之路

百度安全

实现-最佳实践-权益维护抉择V3

南山

个人成长

深入剖析酷睿i7-14700KF与锐龙7 7800X3D:谁才是优秀多面手处理器

E科讯

在Presto中利用一致性哈希算法增强动态集群的数据缓存本地性_语言 & 开发_InfoQ精选文章