文档章节

一致性哈希

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
粉丝 10
博文 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
一致性(连续性)hash算法(Consistent hashing)

一致性(连续性)hash算法(Consistent hashing) Consistent hashing is a scheme that provides hash table functionality in a way that the addition or removal of one slot does not s......

程序员诗人
2017/08/22
0
0

没有更多内容

加载失败,请刷新页面

加载更多

w, vmstat, top, sar, nload命令查看系统状态信息

w/uptime 查看系统负载 cat /proc/cpuinfo 查看cpu核数 vmstat 监控系统状态,用法 vmstat 1,关键的几列: r, b, swpd, si, so, bi, bo, us, wa top 查看进程使用资源情况 top -c 显示详细的...

野雪球
今天
1
0
小白创建一个spring boot项目

进入 https://start.spring.io/

lilugirl
今天
2
0
Alibaba Java诊断利器Arthas实践--使用redefine排查应用奇怪的日志来源

背景 随着应用越来越复杂,依赖越来越多,日志系统越来越混乱,有时会出现一些奇怪的日志,比如: [] [] [] No credential found 那么怎样排查这些奇怪的日志从哪里打印出来的呢?因为搞不清...

hengyunabc
今天
2
0
home hosts

home hosts lwk@qwfys:~$ cat /etc/hosts127.0.0.1 localhost127.0.1.1 qwfys192.168.56.101vm600.qwfys.com39.108.212.91alpha1.ppy.com39.108.117.122alpha2.p......

qwfys
今天
3
0
大数据教程(6.1)hadoop生态圈介绍及就业前景

1. HADOOP背景介绍 1.1、什么是HADOOP 1.HADOOP是apache旗下的一套开源软件平台 2.HADOOP提供的功能:利用服务器集群,根据用户的自定义业务逻辑,对海量数据进行分布式处理 3.HADOOP的核心组...

em_aaron
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部