热门标签 | HotTags
当前位置:  开发笔记 > 人工智能 > 正文

Java语言ConsistentHash算法学习笔记(代码示例)

这篇文章主要介绍了Java语言ConsistentHash算法学习笔记(代码示例),分享了相关代码示例,小编觉得还是挺不错的,具有一定借鉴价值,需要的朋友可以参考下

本文研究的主要是ConsistentHashing算法代码。

一致性哈希(Consistent Hash)

协议简介

一致性哈希算法在1997年由麻省理工学院提出(参见0),设计目标是为了解决因特网中的热点(Hot pot)问题,初衷和CARP十分类似。一致性哈希修正了CARP使用的简单哈希算法带来的问题,使得DHT可以在P2P环境中真正得到应用。

哈希算法

一致性哈希提出了在动态变化的Cache环境中,哈希算法应该满足的4个适应条件:

平衡性(Balance)

平衡性是指哈希的结果能够尽可能分布到所有的缓存中去,这样可以使得所有的缓存空间都得到利用。很多哈希算法都能够满足这一条件。

单调性(Monotonicity)

单调性是指如果已经有一些内容通过哈希分派到了相应的缓存中,又有新的缓存加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到新的缓存中去,而不会被映射到旧的缓存集合中的其他缓冲区。

简单的哈希算法往往不能满足单调性的要求,如最简单的线性哈希:

x → ax + b mod (P)

在上式中,P表示全部缓存的大小。不难看出,当缓存大小发生变化时(从P1到P2),原来所有的哈希结果均会发生变化,从而不满足单调性的要求。

哈希结果的变化意味着当缓存空间发生变化时,所有的映射关系需要在系统内全部更新。而在P2P系统内,缓存的变化等价于Peer加入或退出系统,这一情况在P2P系统中会频繁发生,因此会带来极大计算和传输负荷。单调性就是要求哈希算法能够避免这一情况的发生。

分散性(Spread)

在分布式环境中,终端有可能看不到所有的缓存,而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓存上时,由于不同终端所见的缓存范围有可能不同,从而导致哈希的结果不一致,最终的结果是相同的内容被不同的终端映射到不同的缓存区中。这种情况显然是应该避免的,因为它导致相同内容被存储到不同缓冲中去,降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生,也就是尽量降低分散性。

负载(Load)

负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中,那么对于一个特定的缓冲区而言,也可能被不同的用户映射为不同的内容。与分散性一样,这种情况也是应当避免的,因此好的哈希算法应能够尽量降低缓冲的负荷。

从表面上看,一致性哈希针对的是分布式缓冲的问题,但是如果将缓冲看作P2P系统中的Peer,将映射的内容看作各种共享的资源(数据,文件,媒体流等),就会发现两者实际上是在描述同一问题。

路由算法

在一致性哈希算法中,每个节点(对应P2P系统中的Peer)都有随机分配的ID。在将内容映射到节点时,使用内容的关键字和节点的ID进行一致性哈希运算并获得键值。一致性哈希要求键值和节点ID处于同一值域。最简单的键值和ID可以是一维的,比如从0000到9999的整数集合。

根据键值存储内容时,内容将被存储到具有与其键值最接近的ID的节点上。例如键值为1001的内容,系统中有ID为1000,1010,1100的节点,该内容将被映射到1000节点。

为了构建查询所需的路由,一致性哈希要求每个节点存储其上行节点(ID值大于自身的节点中最小的)和下行节点(ID值小于自身的节点中最大的)的位置信息(IP地址)。当节点需要查找内容时,就可以根据内容的键值决定向上行或下行节点发起查询请求。收到查询请求的节点如果发现自己拥有被请求的目标,可以直接向发起查询请求的节点返回确认;如果发现不属于自身的范围,可以转发请求到自己的上行/下行节点。

为了维护上述路由信息,在节点加入/退出系统时,相邻的节点必须及时更新路由信息。这就要求节点不仅存储直接相连的下行节点位置信息,还要知道一定深度(n跳)的间接下行节点信息,并且动态地维护节点列表。当节点退出系统时,它的上行节点将尝试直接连接到最近的下行节点,连接成功后,从新的下行节点获得下行节点列表并更新自身的节点列表。同样的,当新的节点加入到系统中时,首先根据自身的ID找到下行节点并获得下行节点列表,然后要求上行节点修改其下行节点列表,这样就恢复了路由关系。

讨论

一致性哈希基本解决了在P2P环境中最为关键的问题——如何在动态的网络拓扑中分布存储和路由。每个节点仅需维护少量相邻节点的信息,并且在节点加入/退出系统时,仅有相关的少量节点参与到拓扑的维护中。所有这一切使得一致性哈希成为第一个实用的DHT算法。

但是一致性哈希的路由算法尚有不足之处。在查询过程中,查询消息要经过O(N)步(O(N)表示与N成正比关系,N代表系统内的节点总数)才能到达被查询的节点。不难想象,当系统规模非常大时,节点数量可能超过百万,这样的查询效率显然难以满足使用的需要。换个角度来看,即使用户能够忍受漫长的时延,查询过程中产生的大量消息也会给网络带来不必要的负荷。

源代码:

package heritrix;
import java.util.Collection;
import java.util.SortedMap;
import java.util.TreeMap;
public class ConsistentHash {
	//哈希算法
	private final HashFunction hashFunction;
	//虚拟节点数目
	private final int numberOfReplicas;
	private final SortedMap circle = new TreeMap();
	public ConsistentHash(HashFunction hashFunction, int numberOfReplicas, Collection nodes){
		this.hashFunction = hashFunction;
		this.numberOfReplicas = numberOfReplicas;
		for (T node : nodes){
			add(node);
		}
	}
	public void add(T node){
		for (int i = 0; i  tailMap = circle.tailMap(hash);
			hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
		}
		return circle.get(hash);
	}
}

总结

以上就是本文关于Java语言Consistent Hash算法学习笔记(代码示例)的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题,如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!


推荐阅读
  • SpringBoot整合SpringSecurity+JWT实现单点登录
    SpringBoot整合SpringSecurity+JWT实现单点登录,Go语言社区,Golang程序员人脉社 ... [详细]
  • 2021最新总结网易/腾讯/CVTE/字节面经分享(附答案解析)
    本文分享作者在2021年面试网易、腾讯、CVTE和字节等大型互联网企业的经历和问题,包括稳定性设计、数据库优化、分布式锁的设计等内容。同时提供了大厂最新面试真题笔记,并附带答案解析。 ... [详细]
  • 在Android开发中,使用Picasso库可以实现对网络图片的等比例缩放。本文介绍了使用Picasso库进行图片缩放的方法,并提供了具体的代码实现。通过获取图片的宽高,计算目标宽度和高度,并创建新图实现等比例缩放。 ... [详细]
  • 在当前金融科技 ... [详细]
  • 本文介绍了OpenStack的逻辑概念以及其构成简介,包括了软件开源项目、基础设施资源管理平台、三大核心组件等内容。同时还介绍了Horizon(UI模块)等相关信息。 ... [详细]
  • Python开源库和第三方包的常用框架及库
    本文介绍了Python开源库和第三方包中常用的框架和库,包括Django、CubicWeb等。同时还整理了GitHub中最受欢迎的15个Python开源框架,涵盖了事件I/O、OLAP、Web开发、高性能网络通信、测试和爬虫等领域。 ... [详细]
  • Java和JavaScript是什么关系?java跟javaScript都是编程语言,只是java跟javaScript没有什么太大关系,一个是脚本语言(前端语言),一个是面向对象 ... [详细]
  • Centos下安装memcached+memcached教程
    本文介绍了在Centos下安装memcached和使用memcached的教程,详细解释了memcached的工作原理,包括缓存数据和对象、减少数据库读取次数、提高网站速度等。同时,还对memcached的快速和高效率进行了解释,与传统的文件型数据库相比,memcached作为一个内存型数据库,具有更高的读取速度。 ... [详细]
  • 解决Sharepoint 2013运行状况分析出现的“一个或多个服务器未响应”问题的方法
    本文介绍了解决Sharepoint 2013运行状况分析中出现的“一个或多个服务器未响应”问题的方法。对于有高要求的客户来说,系统检测问题的存在是不可接受的。文章详细描述了解决该问题的步骤,包括删除服务器、处理分布式缓存留下的记录以及使用代码等方法。同时还提供了相关关键词和错误提示信息,以帮助读者更好地理解和解决该问题。 ... [详细]
  • Sleuth+zipkin链路追踪SpringCloud微服务的解决方案
    在庞大的微服务群中,随着业务扩展,微服务个数增多,系统调用链路复杂化。Sleuth+zipkin是解决SpringCloud微服务定位和追踪的方案。通过TraceId将不同服务调用的日志串联起来,实现请求链路跟踪。通过Feign调用和Request传递TraceId,将整个调用链路的服务日志归组合并,提供定位和追踪的功能。 ... [详细]
  • ElasticSerach初探第一篇认识ES+环境搭建+简单MySQL数据同步+SpringBoot整合ES
    一、认识ElasticSearch是一个基于Lucene的开源搜索引擎,通过简单的RESTfulAPI来隐藏Lucene的复杂性。全文搜索,分析系统&# ... [详细]
  • 分布式系统一致性专题:3PC协议的优化和问题
    本文介绍了分布式系统一致性专题中的3PC协议,该协议是对2PC协议的优化和改进。文章详细解释了3PC协议的三个阶段:CanCommit、PreCommit和DoCommit,并分析了每个阶段可能出现的情况和处理方式。同时,文章也指出了3PC协议存在的问题,如参与者超时机制可能导致数据不一致等。总体来说,3PC协议在优化和改进方面取得了一定效果,但仍需继续努力解决数据不一致问题。 ... [详细]
  • 本文总结了初学者在使用dubbo设计架构过程中遇到的问题,并提供了相应的解决方法。问题包括传输字节流限制、分布式事务、序列化、多点部署、zk端口冲突、服务失败请求3次机制以及启动时检查。通过解决这些问题,初学者能够更好地理解和应用dubbo设计架构。 ... [详细]
  • 本文讨论了在使用Git进行版本控制时,如何提供类似CVS中自动增加版本号的功能。作者介绍了Git中的其他版本表示方式,如git describe命令,并提供了使用这些表示方式来确定文件更新情况的示例。此外,文章还介绍了启用$Id:$功能的方法,并讨论了一些开发者在使用Git时的需求和使用场景。 ... [详细]
  • 云原生应用最佳开发实践之十二原则(12factor)
    目录简介一、基准代码二、依赖三、配置四、后端配置五、构建、发布、运行六、进程七、端口绑定八、并发九、易处理十、开发与线上环境等价十一、日志十二、进程管理当 ... [详细]
author-avatar
mobiledu2502880317
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有