文档章节

一致性哈希

laichendong
 laichendong
发布于 2014/06/25 09:27
字数 594
阅读 16
收藏 1
点赞 0
评论 0
一致性哈希已经是被写烂了的题目了,所以我这也不想再赘述他的原理。这个随便一搜一大把。下面给出一个我的简单实现,需要用到的时候改改就能用了。需要注意的地方以及思路都在代码里了。
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 ⋅ 6

百度海量日志处理——任务调度实践与优化

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

g2v13ah ⋅ 2017/11/02 ⋅ 0

5分钟带你理解一致性Hash算法。

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

架构之路 ⋅ 2017/12/03 ⋅ 0

Cassandra的一致性哈希(Consistent Hashing)和虚拟节点(Virtual Nodes)的关系

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

bluishglc ⋅ 2016/10/18 ⋅ 0

一致性哈希算法及其在分布式系统中的应用

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

abing_hu ⋅ 2013/09/01 ⋅ 0

聊聊jump consistent hash

序 本文主要简介一下jump Consistent hash。 jump consistent hash jump consistent hash是一致性哈希的一种实现,论文见A Fast, Minimal Memory, Consistent Hash Algorithm 经典的一致性哈...

xixicat ⋅ 2017/11/11 ⋅ 0

一致性哈希及其 Python 实现

声明:本文仅限于简书发布,其他第三方网站均为盗版,原文地址: 一致性哈希及其 Python 实现 记得之前看一些集群数据库或者和集群相关的文章和书籍的时候,总是会有人提到一致性哈希这个东西...

yetship ⋅ 2017/09/27 ⋅ 0

Consistent Hashing算法

前几天看了一下Memcached,看到Memcached的分布式算法时,知道了一种Consistent Hashing的哈希算法,上网搜了一下,大致了解了一下这个算法,做下记录。 数据均衡分布技术在分布式存储系统中...

xumaojun ⋅ 04/08 ⋅ 0

理解 Consistent Hashing

原文出处:koala bear 简介 为了解决分布式 web 中的热点问题,David Karger 于 1997 年提出 一致性哈希(Consistent Hashing),论文请见 Consistent Hashing and Random Trees: Distributed...

koala bear ⋅ 01/29 ⋅ 0

【策略】一致性Hash算法

转载请说明出处:http://blog.csdn.net/cywosp/article/details/23397179 一致性哈希算法在1997年由麻省理工学院提出的一种分布式哈希(DHT)实现算法,设计目标是为了解决因特网中的热点(Ho...

无信不立 ⋅ 2017/05/17 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Spring Boot整合模板引擎thymeleaf

项目结构 引入依赖pom.xml <!-- 引入 thymeleaf 模板依赖 --><dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-thymeleaf</artifactId......

yysue ⋅ 14分钟前 ⋅ 0

ConstraintLayout使用解析

AndroidStudio3.0创建Project默认的布局就是ConstraintLayout。 AndroidStudio3.0前的可以自己修改,使用ConstraintLayout。 为了要使用ConstraintLayout,我们需要在app/build.gradle文件中...

_OUTMAN_ ⋅ 25分钟前 ⋅ 0

OSChina 周三乱弹 —— 这样的女人私生活太混乱了

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @ 胖达panda :你经历过体验到人生的大起大落吗?我一朋友在10秒内体验了,哈哈。@小小编辑 请点一首《almost lover》送给他。 《almost love...

小小编辑 ⋅ 59分钟前 ⋅ 9

自己动手写一个单链表

文章有不当之处,欢迎指正,如果喜欢微信阅读,你也可以关注我的微信公众号:好好学java,获取优质学习资源。 一、概述 单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对...

公众号_好好学java ⋅ 今天 ⋅ 0

Centos7重置Mysql 8.0.1 root 密码

问题产生背景: 安装完 最新版的 mysql8.0.1后忘记了密码,向重置root密码;找了网上好多资料都不尽相同,根据自己的问题总结如下: 第一步:修改配置文件免密码登录mysql vim /etc/my.cnf 1...

豆花饭烧土豆 ⋅ 今天 ⋅ 0

熊掌号收录比例对于网站原创数据排名的影响[图]

从去年下半年开始,我在写博客了,因为我觉得业余写写博客也还是很不错的,但是从2017年下半年开始,百度已经推出了原创保护功能和熊掌号平台,为此,我也提交了不少以前的老数据,而这些历史...

原创小博客 ⋅ 今天 ⋅ 0

LVM讲解、磁盘故障小案例

LVM LVM就是动态卷管理,可以将多个硬盘和硬盘分区做成一个逻辑卷,并把这个逻辑卷作为一个整体来统一管理,动态对分区进行扩缩空间大小,安全快捷方便管理。 1.新建分区,更改类型为8e 即L...

蛋黄Yolks ⋅ 今天 ⋅ 0

Hadoop Yarn调度器的选择和使用

一、引言 Yarn在Hadoop的生态系统中担任了资源管理和任务调度的角色。在讨论其构造器之前先简单了解一下Yarn的架构。 上图是Yarn的基本架构,其中ResourceManager是整个架构的核心组件,它负...

p柯西 ⋅ 今天 ⋅ 0

uWSGI + Django @ Ubuntu

创建 Django App Project 创建后, 可以看到路径下有一个wsgi.py的问题 uWSGI运行 直接命令行运行 利用如下命令, 可直接访问 uwsgi --http :8080 --wsgi-file dj/wsgi.py 配置文件 & 运行 [u...

袁祾 ⋅ 今天 ⋅ 0

JVM堆的理解

在JVM中,我们经常提到的就是堆了,堆确实很重要,其实,除了堆之外,还有几个重要的模块,看下图: 大 多数情况下,我们并不需要关心JVM的底层,但是如果了解它的话,对于我们系统调优是非常...

不羁之后 ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部