2022 OceanBase 年度发布会,点击了解详情 了解详情
写点什么

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

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

  • 2022 年 5 月 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 年 5 月 11 日 11:182542

评论

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

ARTS打卡 第6周

引花眠

ARTS 打卡计划

架构训练营第五周 - 总结

无心水

极客大学架构师训练营

重学 Java 设计模式:实战策略模式「模拟多种营销类型优惠券,折扣金额计算策略场景」

小傅哥

Java 设计模式 小傅哥 重构 代码优化

Week3:作业二

车小勺的男神

week5.课后作业

个人练习生niki👍

谈谈Spring xml配置文件中的命名空间,以及一些例外情况

xiaoxi666

spring 命名空间

三十张图助你看清红黑树的前世今生

淡蓝色

Java 程序员 数据结构 算法

面试官:为什么需要happens-before规则和什么是指令重排序

无予且行

Java 编程 程序员 面试 happens-before

Week3:作业一

车小勺的男神

它们为什么这么快:从多进程到多线程再到I/O复用

Ya

多线程 进程 并发

针对GPU单指令多数据流的编译优化算法

GPU

gpu 编译器 程序语言 if-conversion

操作系统概览

引花眠

计算机基础

架构师训练营 第5课学习总结

Glowry

极客大学架构师训练营

架构训练营第五周 - 作业

无心水

极客大学架构师训练营

[1.3万字] 玩转前端二进制

阿宝哥

Java 大前端 base64 Blob

GeekPwn 2020少年黑客马拉松大赛即将开启 谁将CARRY全场?

Geek_116789

读《看见》

YoungZY

架构师训练营学习总结

John

极客大学架构师训练营

刚去面试现场聊了一个多小时的Redis ,悄悄分享给大家!

Java小咖秀

nosql redis 面试

从Servlet到Spring Boot

废材姑娘

Java Spring Boot

视读——沟通的艺术,看入人里,看出人外(开篇)

废材姑娘

读书笔记 视觉笔记

PHP实现一致性Hash算法

Arthur.Li

php 极客大学架构师训练营 一致性hash

iOS sonar实践

余志斐

ios sonar

分布式缓存架构与负载均衡架构

负载均衡 极客大学架构师训练营 消息队列 分布式缓存 第五周

依赖倒置原则

John

极客大学架构师训练营

ARTS打卡-05

Geek_yansheng25

第五周-作业2-学习总结

seng man

架构师训练营第五周作业

CATTY

一致性Hash算法

架构师训练营第五章作业

饶军

架构师训练营 第5课作业

Glowry

极客大学架构师训练营

区块链系列教程之:比特币的问题

程序那些事

比特币 区块链 智能合约 以太坊

2022 阿里云飞天技术峰会 - 主论坛

2022 阿里云飞天技术峰会 - 主论坛

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