文档章节

一致性哈希

laichendong
 laichendong
发布于 2014/06/25 09:27
字数 594
阅读 16
收藏 1
一致性哈希已经是被写烂了的题目了,所以我这也不想再赘述他的原理。这个随便一搜一大把。下面给出一个我的简单实现,需要用到的时候改改就能用了。需要注意的地方以及思路都在代码里了。
package me.elf.consistent.hashing;

import org.apache.commons.codec.digest.DigestUtils;

import java.util.*;

/**
 * 一致性hash路由算法
 *
 * @author laichendong
 * @since 14-6-10
 */
public class ConsistentHashing<T> {

    /**
     * 节点集合
     */
    private Set<T> nodes = new HashSet<T>();

    /**
     * 节点环,用treeMap模拟实现
     */
    private TreeMap<Integer, T> ring = new TreeMap<Integer, T>();

    public ConsistentHashing() {
    }

    public ConsistentHashing(Set<T> nodes) {
        if (nodes == null) {
            throw new NullPointerException("nodes must not be null");
        }
        this.nodes = nodes;
        for (T node : nodes) {
            ring.put(hash(node), node);
        }
    }

    /**
     * 添加节点
     *
     * @param node 节点
     * @return 节点添加是否成功
     */
    public boolean addNode(T node) {
        ring.put(hash(node), node);
        return nodes.add(node);
    }

    /**
     * 移除节点
     *
     * @param node 节点
     * @return 节点移除是否成功
     */
    public boolean removeNode(T node) {
        ring.remove(hash(node));
        return nodes.remove(node);
    }

    /**
     * 计算路由
     *
     * @param key 需要计算路由的key
     * @return key落到的节点上
     */
    public T route(Object key) {
        int h = hash(key);
        // 找到离key最近的节点
        Map.Entry<Integer, T> entry = ring.floorEntry(h);
        if (entry == null) {
            // 如果没有找到,可能时到最前面了,返回最后一个节点,形成环
            entry = ring.lastEntry();
        }
        if (entry == null) {
            return null;
        } else {
            return entry.getValue();
        }
    }

    /**
     * 采用的hash算法
     * 这个可以根据需要进行修改
     *
     * @param key hash key
     * @return hash 值
     */
    public static int hash(Object key) {
        // 这个md5挺重要的,可以将相似的key的hash值打散,使节点在环上散布开来,当然,也可以使用其他方法
        int h = DigestUtils.md5Hex(key.toString()).hashCode();
        // 然后再copy了以下HashMap的hash算法~~
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

    /**
     * 测试
     */
    public static void main(String[] args) {
        // 初始化
        ConsistentHashing<String> consistentHashing = new ConsistentHashing<String>();
        consistentHashing.addNode("node0");
        consistentHashing.addNode("node1");
        consistentHashing.addNode("node2");
        consistentHashing.addNode("node3");

        // 对每一个key进行路由计算 看看分布情况
        String[] keys = {"key0", "key1", "key2", "key3", "key4", "key5", "key6", "key7"};
        for (String key : keys) {
            System.out.println(key + " -> " + consistentHashing.route(key));
        }
        System.out.println("=================");
        // 减掉一个节点,再对每一个key进行路由计算   看漂移结果
        consistentHashing.removeNode("node3");
        for (String key : keys) {
            System.out.println(key + " -> " + consistentHashing.route(key));
        }

    }

}
输出是这样的:
key0 -> node1
key1 -> node1
key2 -> node3
key3 -> node1
key4 -> node2
key5 -> node1
key6 -> node1
key7 -> node3
=================
key0 -> node1
key1 -> node1
key2 -> node2
key3 -> node1
key4 -> node2
key5 -> node1
key6 -> node1
key7 -> node2
可以看到,在移除了节点3之后,原来落到节点3上的key都落到了节点2。而原来落到其他节点的key都还在原地。满足了“一致性”的要求。

© 著作权归作者所有

共有 人打赏支持
laichendong
粉丝 8
博文 85
码字总数 71483
作品 0
朝阳
程序员
使用虚拟节点改进的一致性哈希算法

分布式存储中的应用 ---在分布式存储系统中,将数据分布至多个节点的方式之一是使用哈希算法。假设初始节点数为 N,则传统的对 N 取模的映射方式存在一个问题在于:当节点增删,即 N 值变化时...

lionets
2014/07/07
0
6
百度海量日志处理——任务调度实践与优化

作者简介 运小军 百度高级研发工程师 负责百度运维部大规模日志处理、海量事件数据存储相关设计研发工作,在分布式系统架构、大数据存储计算、高性能网络服务和即时通讯服务有广泛实践经验。...

g2v13ah
2017/11/02
0
0
5分钟带你理解一致性Hash算法。

QQ用得起来越少了,现在就加入300+技术微信群,公众号回复"微信群"即可加入。 一致性Hash算法背景 一致性哈希算法在1997年由麻省理工学院的Karger等人在解决分布式Cache中提出的,设计目标是...

架构之路
2017/12/03
0
0
一致性哈希算法及其在分布式系统中的应用

摘要 本文将会从实际应用场景出发,介绍一致性哈希算法(Consistent Hashing)及其在分布式系统中的应用。首先本文会描述一个在日常开发中经常会遇到的问题场景,借此介绍一致性哈希算法以及...

abing_hu
2013/09/01
0
0
Cassandra的一致性哈希(Consistent Hashing)和虚拟节点(Virtual Nodes)的关系

本文原文出处: http://blog.csdn.net/bluishglc/article/details/52847591 严禁任何形式的转载,否则将委托CSDN官方维护权益! 一致性哈希所要解决的问题 一般的哈希算法存在的问题是:当“模...

bluishglc
2016/10/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

java并发备忘

不安全的“先检查后执行”,代码形式如下: if(条件满足){ //这里容易出现线程安全问题//doSomething}else{//doOther} 读取-修改-写入 原子操作:使用CAS技术,即首先从V中读取...

Funcy1122
今天
0
0
SpringBoot2.0 停机

最近新建了个SpringBoot2.0的项目,因为原来一直使用的是传统的Tomcat部署war包的形式,所以这次SpringBoot内置Tomcat部署jar包的时候遇到了很多问题。其中一个就是因为没有外置的Tomcat容器...

Canaan_
昨天
0
1
Confluence 6 外部参考

一个外部参考的意思是任何站点链接到你 Confluence 的实例。任何时候当 Confluence 的用户单击这个外部链接的时候,Confluence 可以记录这次单击为参考。 在默认的情况下,外部链接的参考链接...

honeymose
昨天
0
0
Android中的设计模式之抽象工厂模式

参考 《设计模式解析》 第十一章 Abstract Factory模式 《设计模式:可复用面向对象软件的基础 》3.1 Abstract Factory 抽象工厂 对象创建型模式 《Android源码设计模式解析与实战》第6章 创...

newtrek
昨天
0
0
Redis | 地理空间(GEO)的一个坑

Redis的地理空间(Geo)是个好东西,轻轻松松的就可以把地图描点的问题处理了, 最近却遇到一个坑...Redis采用的Msater-Slave模式, 运用GEORADIUS在salve读取对应的数据,新增了从节点但是从不返...

云迹
昨天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部