文档章节

一致性哈希

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
朝阳
程序员
私信 提问
查找--深入理解一致性哈希算法

注:本篇博客只是讲述了一致性哈希的思想,我们会在之后讲述分布式哈希表以及一致性哈希的一种实现(Chord算法)。 什么是一致性哈希算法? 引用自维基百科: 一致性哈希是一种特殊的哈希算法...

珩翊
06/26
0
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
一致性(连续性)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

没有更多内容

加载失败,请刷新页面

加载更多

js垃圾回收机制和引起内存泄漏的操作

JS的垃圾回收机制了解吗? Js具有自动垃圾回收机制。垃圾收集器会按照固定的时间间隔周期性的执行。 JS中最常见的垃圾回收方式是标记清除。 工作原理:是当变量进入环境时,将这个变量标记为“...

Jack088
昨天
17
0
大数据教程(10.1)倒排索引建立

前面博主介绍了sql中join功能的大数据实现,本节将继续为小伙伴们分享倒排索引的建立。 一、需求 在很多项目中,我们需要对我们的文档建立索引(如:论坛帖子);我们需要记录某个词在各个文...

em_aaron
昨天
25
0
"errcode": 41001, "errmsg": "access_token missing hint: [w.ILza05728877!]"

Postman获取微信小程序码的时候报错, errcode: 41001, errmsg: access_token missing hint 查看小程序开发api指南,原来access_token是直接当作parameter的(写在url之后),scene参数一定要...

两广总督bogang
昨天
31
0
MYSQL索引

索引的作用 索引类似书籍目录,查找数据,先查找目录,定位页码 性能影响 索引能大大减少查询数据时需要扫描的数据量,提高查询速度, 避免排序和使用临时表 将随机I/O变顺序I/O 降低写速度,占用磁...

关元
昨天
13
0
撬动世界的支点——《引爆点》读书笔记2900字优秀范文

撬动世界的支点——《引爆点》读书笔记2900字优秀范文: 作者:挽弓如月。因为加入火种协会的读书活动,最近我连续阅读了两本论述流行的大作,格拉德威尔的《引爆点》和乔纳伯杰的《疯传》。...

原创小博客
昨天
35
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部