热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

java一致性哈希框架_浅尝一致性Hash原理

一、前言在解决分布式系统中负载均衡的问题时候可以使用Hash算法让固定的一部分请求落到同一台服务器上,这样每台服务器固定处理一部分请求(并维护这些请求的信息)

一、前言

在解决分布式系统中负载均衡的问题时候可以使用Hash算法让固定的一部分请求落到同一台服务器上,这样每台服务器固定处理一部分请求(并维护这些请求的信息),起到负载均衡的作用。

但是普通的余数hash(hash(比如用户id)%服务器机器数)算法伸缩性很差,当新增或者下线服务器机器时候,用户id与服务器的映射关系会大量失效。一致性hash则利用hash环对其进行了改进。

二、一致性Hash概述

为了能直观的理解一致性hash原理,这里结合一个简单的例子来讲解,假设有4台服务器,地址为ip1,ip2,ip3,ip4。

一致性hash是首先计算四个ip地址对应的hash值

hash(ip1),hash(ip2),hash(ip3),hash(ip3),计算出来的hash值是0~最大正整数直接的一个值,这四个值在一致性hash环上呈现如下图:

f29756b56ffe3c9827374c5a0829e84f.png

hash环上顺时针从整数0开始,一直到最大正整数,我们根据四个ip计算的hash值肯定会落到这个hash环上的某一个点,至此我们把服务器的四个ip映射到了一致性hash环

当用户在客户端进行请求时候,首先根据hash(用户id)计算路由规则(hash值),然后看hash值落到了hash环的那个地方,根据hash值在hash环上的位置顺时针找距离最近的ip作为路由ip.

a7f400a84d7e6ff70fde0d5861e4c808.png

如上图可知user1,user2的请求会落到服务器ip2进行处理,User3的请求会落到服务器ip3进行处理,user4的请求会落到服务器ip4进行处理,user5,user6的请求会落到服务器ip1进行处理。

下面考虑当ip2的服务器挂了的时候会出现什么情况?

当ip2的服务器挂了的时候,一致性hash环大致如下图:

217167fa3d9eda768ba7f73d0d1c5711.png

根据顺时针规则可知user1,user2的请求会被服务器ip3进行处理,而其它用户的请求对应的处理服务器不变,也就是只有之前被ip2处理的一部分用户的映射关系被破坏了,并且其负责处理的请求被顺时针下一个节点委托处理。

下面考虑当新增机器的时候会出现什么情况?

当新增一个ip5的服务器后,一致性hash环大致如下图:

05499503047c4baa6b264b6196405d1e.png

根据顺时针规则可知之前user1的请求应该被ip1服务器处理,现在被新增的ip5服务器处理,其他用户的请求处理服务器不变,也就是新增的服务器顺时针最近的服务器的一部分请求会被新增的服务器所替代。

三、一致性hash的特性

单调性(Monotonicity),单调性是指如果已经有一些请求通过哈希分派到了相应的服务器进行处理,又有新的服务器加入到系统中时候,应保证原有的请求可以被映射到原有的或者新的服务器中去,而不会被映射到原来的其它服务器上去。 这个通过上面新增服务器ip5可以证明,新增ip5后,原来被ip1处理的user6现在还是被ip1处理,原来被ip1处理的user5现在被新增的ip5处理。

分散性(Spread):分布式环境中,客户端请求时候可能不知道所有服务器的存在,可能只知道其中一部分服务器,在客户端看来他看到的部分服务器会形成一个完整的hash环。如果多个客户端都把部分服务器作为一个完整hash环,那么可能会导致,同一个用户的请求被路由到不同的服务器进行处理。这种情况显然是应该避免的,因为它不能保证同一个用户的请求落到同一个服务器。所谓分散性是指上述情况发生的严重程度。好的哈希算法应尽量避免尽量降低分散性。 一致性hash具有很低的分散性

平衡性(Balance):平衡性也就是说负载均衡,是指客户端hash后的请求应该能够分散到不同的服务器上去。一致性hash可以做到每个服务器都进行处理请求,但是不能保证每个服务器处理的请求的数量大致相同,如下图

7a13531147769c20df0c66e302adbb0e.png

服务器ip1,ip2,ip3经过hash后落到了一致性hash环上,从图中hash值分布可知ip1会负责处理大概80%的请求,而ip2和ip3则只会负责处理大概20%的请求,虽然三个机器都在处理请求,但是明显每个机器的负载不均衡,这样称为一致性hash的倾斜,虚拟节点的出现就是为了解决这个问题。

五、虚拟节点

当服务器节点比较少的时候会出现上节所说的一致性hash倾斜的问题,一个解决方法是多加机器,但是加机器是有成本的,那么就加虚拟节点,比如上面三个机器,每个机器引入1个虚拟节点后的一致性hash环的图如下:

6b3b8d35ccd31dd2e824511e69c9a75b.png

其中ip1-1是ip1的虚拟节点,ip2-1是ip2的虚拟节点,ip3-1是ip3的虚拟节点。

可知当物理机器数目为M,虚拟节点为N的时候,实际hash环上节点个数为M*N。比如当客户端计算的hash值处于ip2和ip3或者处于ip2-1和ip3-1之间时候使用ip3服务器进行处理。

六、均匀一致性hash

上节我们使用虚拟节点后的图看起来比较均衡,但是如果生成虚拟节点的算法不够好很可能会得到下面的环:

c3259d7b52a1add163598a6b6cb9807d.png可知每个服务节点引入1个虚拟节点后,情况相比没有引入前均衡性有所改善,但是并不均衡。

均衡的一致性hash应该是如下图:

0768405f46096d18670e488b9b1b866c.png

均匀一致性hash的目标是如果服务器有N台,客户端的hash值有M个,那么每个服务器应该处理大概M/N个用户的。也就是每台服务器负载尽量均衡

七、总结

在分布式系统中一致性hash起着不可忽略的地位,无论是分布式缓存,还是分布式Rpc框架的负载均衡策略都有所使用。

52d4a570191b85a93cc599539ce47cd0.png

d0c1501a6d8bb921cf36400dc89de69f.png



推荐阅读
  • Java Socket 关键参数详解与优化建议
    Java Socket 的 API 虽然被广泛使用,但其关键参数的用途却鲜为人知。本文详细解析了 Java Socket 中的重要参数,如 backlog 参数,它用于控制服务器等待连接请求的队列长度。此外,还探讨了其他参数如 SO_TIMEOUT、SO_REUSEADDR 等的配置方法及其对性能的影响,并提供了优化建议,帮助开发者提升网络通信的稳定性和效率。 ... [详细]
  • Web开发框架概览:Java与JavaScript技术及框架综述
    Web开发涉及服务器端和客户端的协同工作。在服务器端,Java是一种优秀的编程语言,适用于构建各种功能模块,如通过Servlet实现特定服务。客户端则主要依赖HTML进行内容展示,同时借助JavaScript增强交互性和动态效果。此外,现代Web开发还广泛使用各种框架和库,如Spring Boot、React和Vue.js,以提高开发效率和应用性能。 ... [详细]
  • 本文深入探讨了 Git 与 SVN 的高效使用技巧,旨在帮助开发者轻松应对版本控制中的各种挑战。通过详细解析两种工具的核心功能与最佳实践,读者将能够更好地掌握版本管理的精髓,提高开发效率。 ... [详细]
  • 阿里巴巴终面技术挑战:如何利用 UDP 实现 TCP 功能?
    在阿里巴巴的技术面试中,技术总监曾提出一道关于如何利用 UDP 实现 TCP 功能的问题。当时回答得不够理想,因此事后进行了详细总结。通过与总监的进一步交流,了解到这是一道常见的阿里面试题。面试官的主要目的是考察应聘者对 UDP 和 TCP 在原理上的差异的理解,以及如何通过 UDP 实现类似 TCP 的可靠传输机制。 ... [详细]
  • Hyperledger Fabric 1.4 节点 SDK 快速入门指南
    本文将详细介绍如何利用 Hyperledger Fabric 1.4 的 Node.js SDK 开发应用程序。通过最新版本的 Fabric Node.js SDK,开发者可以更高效地构建和部署基于区块链的应用,实现数据的安全共享和交易处理。文章将涵盖环境配置、SDK 安装、示例代码以及常见问题的解决方法,帮助读者快速上手并掌握核心功能。 ... [详细]
  • 在《Linux高性能服务器编程》一书中,第3.2节深入探讨了TCP报头的结构与功能。TCP报头是每个TCP数据段中不可或缺的部分,它不仅包含了源端口和目的端口的信息,还负责管理TCP连接的状态和控制。本节内容详尽地解析了TCP报头的各项字段及其作用,为读者提供了深入理解TCP协议的基础。 ... [详细]
  • 该大学网站采用PHP和MySQL技术,在校内可免费访问某些外部收费资料数据库。为了方便学生校外访问,建议通过学校账号登录实现免费访问。具体方案可包括利用学校服务器作为代理,结合身份验证机制,确保合法用户在校外也能享受免费资源。 ... [详细]
  • REST与RPC:选择哪种API架构风格?
    在探讨REST与RPC这两种API架构风格的选择时,本文首先介绍了RPC(远程过程调用)的概念。RPC允许客户端通过网络调用远程服务器上的函数或方法,从而实现分布式系统的功能调用。相比之下,REST(Representational State Transfer)则基于资源的交互模型,通过HTTP协议进行数据传输和操作。本文将详细分析两种架构风格的特点、适用场景及其优缺点,帮助开发者根据具体需求做出合适的选择。 ... [详细]
  • 美团优选推荐系统架构师 L7/L8:算法与工程深度融合 ... [详细]
  • Python 实战:异步爬虫(协程技术)与分布式爬虫(多进程应用)深入解析
    本文将深入探讨 Python 异步爬虫和分布式爬虫的技术细节,重点介绍协程技术和多进程应用在爬虫开发中的实际应用。通过对比多进程和协程的工作原理,帮助读者理解两者在性能和资源利用上的差异,从而在实际项目中做出更合适的选择。文章还将结合具体案例,展示如何高效地实现异步和分布式爬虫,以提升数据抓取的效率和稳定性。 ... [详细]
  • 2016-2017学年《网络安全实战》第三次作业
    2016-2017学年《网络安全实战》第三次作业总结了教材中关于网络信息收集技术的内容。本章主要探讨了网络踩点、网络扫描和网络查点三个关键步骤。其中,网络踩点旨在通过公开渠道收集目标信息,为后续的安全测试奠定基础,而不涉及实际的入侵行为。 ... [详细]
  • 分布式开源任务调度框架 TBSchedule 深度解析与应用实践
    本文深入解析了分布式开源任务调度框架 TBSchedule 的核心原理与应用场景,并通过实际案例详细介绍了其部署与使用方法。首先,从源码下载开始,详细阐述了 TBSchedule 的安装步骤和配置要点。接着,探讨了该框架在大规模分布式环境中的性能优化策略,以及如何通过灵活的任务调度机制提升系统效率。最后,结合具体实例,展示了 TBSchedule 在实际项目中的应用效果,为开发者提供了宝贵的实践经验。 ... [详细]
  • 对于希望在未越狱的iOS设备上修改Hosts文件的苹果用户来说,了解文件的具体位置和操作步骤至关重要。本文将详细介绍如何通过安装最新版本的iTunes来实现这一目标,并提供实用的操作指南,帮助用户轻松完成Hosts文件的编辑。 ... [详细]
  • 本文详细介绍了在Linux系统上编译安装MySQL 5.5源码的步骤。首先,通过Yum安装必要的依赖软件包,如GCC、GCC-C++等,确保编译环境的完备。接着,下载并解压MySQL 5.5的源码包,配置编译选项,进行编译和安装。最后,完成安装后,进行基本的配置和启动测试,确保MySQL服务正常运行。 ... [详细]
  • 近年来,BPM(业务流程管理)系统在国内市场逐渐普及,多家厂商在这一领域崭露头角。本文将对当前主要的BPM厂商进行概述,并分析其各自的优势。目前,市场上较为成熟的BPM产品主要分为两类:一类是综合型厂商,如IBM和SAP,这些企业在整体解决方案方面具有明显优势;另一类则是专注于BPM领域的专业厂商,它们在特定行业或应用场景中表现出色。通过对比分析,本文旨在为企业选择合适的BPM系统提供参考。 ... [详细]
author-avatar
392399224_619416
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有