【算法技术专题】如何用Java实现一致性 hash 算法( consistent hashing )(上)

简介: 【算法技术专题】如何用Java实现一致性 hash 算法( consistent hashing )(上)

一致性hash的历史


【Consistent Hashing算法】早在 1997 年就在论文 Consistent hashing and random trees 中被提出,目前在 cache 系统中应用越来越广泛;



一致性hash的目的


一致性哈希算法是分布式系统中常用的算法,一致性哈希算法解决了普通余数Hash算法伸缩性差的问题,可以保证在上线、下线服务器的情况下尽量有多的请求命中原来路由到的服务器。



问题背景


业务开发中,我们常把数据持久化到数据库中,如果需要读取这些数据,除了直接从数据库中读取外,为了减轻数据库的访问压力以及提高访问速度,更多地引入缓存来对数据进行存取。



分布式缓存


分布式缓存,不同机器上存储不同对象的数据。为了实现这些缓存机器的负载均衡,一般就会存在两种Hash算法进行均匀分配数据节点存储:普通Hash算法



普通的Hash算法的


Hash取模做法的缺陷

一个Redis集群中,如果我们把一条数据经过Hash,然后再根据集群节点数取模得出应该放在哪个节点,这种做法的缺陷在于:扩容(增加一个节点)之后,有大量缓存失效。



普通Hash的案例分析


比如你有 N 个 cache 服务器(后面简称 cache ),那么如何将一个对象 object 映射到 N 个 cache 上呢,你很可能会采用类似下面的通用方法计算 object 的 hash 值,然后均匀的映射到到 N 个 cache ;

hash(object)%N 
复制代码


一切都运行正常,再考虑如下的两种情况;


  • 一个 cache 服务器 m down 掉了(在实际应用中必须要考虑这种情况),这样所有映射到 cache m 的对象都会失效,怎么办,需要把 cache m 从 cache 中移除,这时候 cache 是 N-1 台,映射公式变成了 hash(object)%(N-1) ;


  • 由于访问加重,需要添加 cache ,这时候 cache 是 N+1 台,映射公式变成了 hash(object)%(N+1) ;


  • 这意味着突然之间几乎所有的 cache 都失效了。对于服务器而言,这是一场灾难,洪水般的访问都会直接冲向后台服务器;(造成缓存雪崩机制)

image.png

一致性Hash算法


一致性hash算法正是为了解决此类问题的方法,它可以保证当机器增加或者减少时,对缓存访问命中的概率影响减至很小。下面我们来详细说一下一致性hash算法的具体过程。


  • 一致性hash算法通过一个叫作一致性hash环的数据结构实现。这个环的起点是0,终点是2^32 - 1,并且起点与终点连接,环的中间的整数按逆时针分布,故这个环的整数分布范围是[0, 2^32-1]
  • 整个哈希值空间组织成一个虚拟的圆环,将节点的IP地址或主机名作为关键字进行哈希计算,得出的结果作为节点在环上的位置。数据经过hash后按顺时针方向找到最近一个节点存放,如图data的hash位置,应该存放在node2。

image.png

  • 相比Hash取模,一致性Hash算法的优点就是扩容后影响的缓存数据较少,如果是n个节点扩容到n+1个的话,影响的缓存数是0~1/n,即最多让一个节点的缓存失效。


  • 他的缺点是,缓存在每个节点上分布不均,毕竟hash值随机,那节点在环上的位置也随机。





改良版一致性Hash算法


一致性Hash算法 + 虚拟节点


为了解决数据分布不均的问题,我们引入虚拟节点的概念。我们对每一个服务节点计算多个哈希,每个计算结果位置都放置一个此服务节点,称为虚拟节点。定位到虚拟节点的数据就存到该虚拟节点对应的真实节点上,这样数据分布就相对均匀了,虚拟节点数越多,分布越均匀。


引入“虚拟节点”后,映射关系就从 { 对象 -> 节点 } 转换到了 { 对象 -> 虚拟节点 } 。查询物体所在 cache 时的映射关系

image.png

一般虚拟节点数32个以上,dubbo是160个。

image.png

处理机器增减的情况


对于线上的业务,增加或者减少一台机器的部署是常有的事情。


例如,增加机器c4的部署并将机器c4加入到hash环的机器c3与c2之间。这时,只有机器c3与c4之间的对象需要重新分配新的机器。对于我们的例子,只有对象o4被重新分配到了c4,其他对象仍在原有机器上。



一致性Hash算法的实现原理


在业务开发中,我们常把数据持久化到数据库中。如果需要读取这些数据,除了直接从数据库中读取外,为了减轻数据库的访问压力以及提高访问速度,我们更多地引入缓存来对数据进行存取。读取数据的过程一般为:



Java代码实现Hash算法的实现


用一个TreeMap来作为环,key为虚拟节点下标,value为真实节点的hash。个人感觉可以加一个Map<T, Set>来维护真实节点-虚拟节点的关系。

/**
 * 一致性Hash算法
 * 算法详解:http://blog.csdn.net/sparkliang/article/details/5279393
 * 算法实现:https://weblogs.java.net/blog/2007/11/27/consistent-hashing
 * @author xiaoleilu
 *
 * @param <T>   节点类型
 */
public class ConsistentHash<T> implements Serializable{
    private static final long serialVersionUID = 1L;
    /** Hash计算对象,用于自定义hash算法 */
    Hash32<Object> hashFunc;
    /** 复制的节点个数 */
    private final int numberOfReplicas;
    /** 一致性Hash环 */
    private final SortedMap<Integer, T> circle = new TreeMap<>();
    /**
     * 构造,使用Java默认的Hash算法
     * @param numberOfReplicas 复制的节点个数,增加每个节点的复制节点有利于负载均衡
     * @param nodes 节点对象
     */
    public ConsistentHash(int numberOfReplicas, Collection<T> nodes) {
        this.numberOfReplicas = numberOfReplicas;
        this.hashFunc = key -> {
            //默认使用FNV1hash算法
            return HashUtil.fnvHash(key.toString());
        };
        //初始化节点
        for (T node : nodes) {
            add(node);
        }
    }
    /**
     * 构造
     * @param hashFunc hash算法对象
     * @param numberOfReplicas 复制的节点个数,增加每个节点的复制节点有利于负载均衡
     * @param nodes 节点对象
     */
    public ConsistentHash(Hash32<Object> hashFunc, int numberOfReplicas, Collection<T> nodes) {
        this.numberOfReplicas = numberOfReplicas;
        this.hashFunc = hashFunc;
        //初始化节点
        for (T node : nodes) {
            add(node);
        }
    }
    /**
     * 增加节点<br>
     * 每增加一个节点,就会在闭环上增加给定复制节点数<br>
     * 例如复制节点数是2,则每调用此方法一次,增加两个虚拟节点,这两个节点指向同一Node
     * 由于hash算法会调用node的toString方法,故按照toString去重
     * @param node 节点对象
     */
    public void add(T node) {
        for (int i = 0; i < numberOfReplicas; i++) {
            circle.put(hashFunc.hash32(node.toString() + i), node);
        }
    }
    /**
     * 移除节点的同时移除相应的虚拟节点
     * @param node 节点对象
     */
    public void remove(T node) {
        for (int i = 0; i < numberOfReplicas; i++) {
            circle.remove(hashFunc.hash32(node.toString() + i));
        }
    }
    /**
     * 获得一个最近的顺时针节点
     * @param key 为给定键取Hash,取得顺时针方向上最近的一个虚拟节点对应的实际节点
     * @return 节点对象
     */
    public T get(Object key) {
        if (circle.isEmpty()) {
            return null;
        }
        int hash = hashFunc.hash32(key);
        if (false == circle.containsKey(hash)) {
            SortedMap<Integer, T> tailMap = circle.tailMap(hash);   //返回此映射的部分视图,其键大于等于 hash
            hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
        }
        //正好命中
        return circle.get(hash);
    }
}





相关文章
|
1月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
69 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
11天前
|
JSON 前端开发 JavaScript
java-ajax技术详解!!!
本文介绍了Ajax技术及其工作原理,包括其核心XMLHttpRequest对象的属性和方法。Ajax通过异步通信技术,实现在不重新加载整个页面的情况下更新部分网页内容。文章还详细描述了使用原生JavaScript实现Ajax的基本步骤,以及利用jQuery简化Ajax操作的方法。最后,介绍了JSON作为轻量级数据交换格式在Ajax应用中的使用,包括Java中JSON与对象的相互转换。
25 1
|
19天前
|
SQL 监控 Java
技术前沿:Java连接池技术的最新发展与应用
本文探讨了Java连接池技术的最新发展与应用,包括高性能与低延迟、智能化管理和监控、扩展性与兼容性等方面。同时,结合最佳实践,介绍了如何选择合适的连接池库、合理配置参数、使用监控工具及优化数据库操作,为开发者提供了一份详尽的技术指南。
29 7
|
21天前
|
移动开发 前端开发 Java
过时的Java技术盘点:避免在这些领域浪费时间
【10月更文挑战第14天】 在快速发展的Java生态系统中,新技术层出不穷,而一些旧技术则逐渐被淘汰。对于Java开发者来说,了解哪些技术已经过时是至关重要的,这可以帮助他们避免在这些领域浪费时间,并将精力集中在更有前景的技术上。本文将盘点一些已经或即将被淘汰的Java技术,为开发者提供指导。
49 7
|
16天前
|
SQL Java 数据库连接
在Java应用中,数据库访问常成为性能瓶颈。连接池技术通过预建立并复用数据库连接,有效减少连接开销,提升访问效率
在Java应用中,数据库访问常成为性能瓶颈。连接池技术通过预建立并复用数据库连接,有效减少连接开销,提升访问效率。本文介绍了连接池的工作原理、优势及实现方法,并提供了HikariCP的示例代码。
31 3
|
17天前
|
SQL 监控 Java
Java连接池技术的最新发展,包括高性能与低延迟、智能化管理与监控、扩展性与兼容性等方面
本文探讨了Java连接池技术的最新发展,包括高性能与低延迟、智能化管理与监控、扩展性与兼容性等方面。同时,结合最佳实践,介绍了如何选择合适的连接池库、合理配置参数、使用监控工具及优化数据库操作,以实现高效稳定的数据库访问。示例代码展示了如何使用HikariCP连接池。
10 2
|
19天前
|
Java 数据库连接 数据库
优化之路:Java连接池技术助力数据库性能飞跃
在Java应用开发中,数据库操作常成为性能瓶颈。频繁的数据库连接建立和断开增加了系统开销,导致性能下降。本文通过问题解答形式,深入探讨Java连接池技术如何通过复用数据库连接,显著减少连接开销,提升系统性能。文章详细介绍了连接池的优势、选择标准、使用方法及优化策略,帮助开发者实现数据库性能的飞跃。
25 4
|
16天前
|
Java 数据库连接 数据库
深入探讨Java连接池技术如何通过复用数据库连接、减少连接建立和断开的开销,从而显著提升系统性能
在Java应用开发中,数据库操作常成为性能瓶颈。本文通过问题解答形式,深入探讨Java连接池技术如何通过复用数据库连接、减少连接建立和断开的开销,从而显著提升系统性能。文章介绍了连接池的优势、选择和使用方法,以及优化配置的技巧。
16 1
|
16天前
|
算法 Java 数据库连接
Java连接池技术,从基础概念出发,解析了连接池的工作原理及其重要性
本文详细介绍了Java连接池技术,从基础概念出发,解析了连接池的工作原理及其重要性。连接池通过复用数据库连接,显著提升了应用的性能和稳定性。文章还展示了使用HikariCP连接池的示例代码,帮助读者更好地理解和应用这一技术。
31 1
|
19天前
|
SQL Java 数据库连接
打破瓶颈:利用Java连接池技术提升数据库访问效率
在Java应用中,数据库访问常成为性能瓶颈。连接池技术通过预建立并复用数据库连接,避免了频繁的连接建立和断开,显著提升了数据库访问效率。常见的连接池库包括HikariCP、C3P0和DBCP,它们提供了丰富的配置选项和强大的功能,帮助优化应用性能。
38 2