`
xpenxpen
  • 浏览: 723177 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

一致性哈希

 
阅读更多
1. 简介
一致性哈希(consistent hashing) 是一种 hash 算法,在移除/添加一个节点时,它能够尽可能小的改变已存在 key 的映射关系。
最简单的哈希算法是模运算(%),slot = hashCode() % N (N为节点数)
但是当N增加或减少时,slot的值会和之前完全不一样,导致完全不命中。

2. java实现
import java.util.Collection;
import java.util.SortedMap;
import java.util.TreeMap;

public class ConsistentHash<T> {

 private final HashFunction hashFunction;
 private final int numberOfReplicas;
 private final SortedMap<Integer, T> circle = new TreeMap<Integer, T>();

 public ConsistentHash(HashFunction hashFunction, int numberOfReplicas,
     Collection<T> nodes) {
   this.hashFunction = hashFunction;
   this.numberOfReplicas = numberOfReplicas;

   for (T node : nodes) {
     add(node);
   }
 }

 public void add(T node) {
   for (int i = 0; i < numberOfReplicas; i++) {
     circle.put(hashFunction.hash(node.toString() + i), node);
   }
 }

 public void remove(T node) {
   for (int i = 0; i < numberOfReplicas; i++) {
     circle.remove(hashFunction.hash(node.toString() + i));
   }
 }

 public T get(Object key) {
   if (circle.isEmpty()) {
     return null;
   }
   int hash = hashFunction.hash(key);
   if (!circle.containsKey(hash)) {
     SortedMap<Integer, T> tailMap = circle.tailMap(hash);
     hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
   }
   return circle.get(hash);
 }

}

可以看到用java实现一个一致性哈希算法如此简单,核心就是调用SortedMap.tailMap和firstKey这两个方法。

3. 参考资料
Memcached分布式算法详解
Consistent Hashing
分享到:
评论

相关推荐

    一致性哈希算法(ketama hashing)

    一致性哈希算法(Consistent Hashing)是一种在分布式系统中实现负载均衡的算法,尤其在分布式缓存如Memcached和Redis等场景下广泛使用。它解决了传统哈希算法在节点增减时导致的大量数据迁移问题,提高了系统的可用...

    基于C# 实现的一致性哈希算法

    一致性哈希算法是一种分布式哈希(Distributed Hash Table, DHT)技术,它解决了在分布式环境中数据分片和负载均衡的问题。在传统的哈希算法中,如果增加或减少服务器节点,会导致大量数据重新分配,而一致性哈希...

    基于一致性哈希算法的分布式数据库高效扩展方法.pdf

    一致性哈希算法最初由麻省理工学院的K等人提出,并被广泛应用于分布式系统中,以解决节点动态变化时数据一致性问题。其核心思想是通过引入哈希环,将数据对象均匀分布在哈希环上的不同节点中,以此降低节点变更对...

    一致性哈希算法C版实现

    一致性哈希算法是一种在分布式系统中解决数据分片和负载均衡问题的算法,它主要解决了在动态添加或移除节点时,尽可能少地改变已经存在的数据分布。在云计算和大数据处理领域,一致性哈希被广泛应用,例如在分布式...

    带虚拟节点的一致性哈希

    一致性哈希(Consistent Hashing)是一种分布式哈希算法,主要应用于分布式缓存、负载均衡等领域,例如Memcached和Redis等系统。它解决了在分布式环境中数据分片与节点动态增减时,尽量减少数据迁移的问题。带虚拟...

    分布式存储系统中改进的一致性哈希算法.pdf

    一致性哈希算法通过将哈希值空间组织成一个虚拟的环状结构,使得每个存储节点仅负责环上的一段区域,从而有效减少了节点变化时的数据迁移量。然而,一致性哈希算法也存在一些问题,比如在节点数量较少时,节点间的...

    基于一致性哈希算法的分布式数据库高效扩展方法研究.pdf

    【摘要】中的“高效扩展”和“分布式数据库”是本文的核心话题,研究的是如何利用一致性哈希算法在大数据时代高效地扩展分布式数据库。一致性哈希算法最初由Karger等人提出,目的是解决分布式缓存的问题,它弥补了...

    一致性哈希与Chord1

    【一致性哈希与Chord1】是一篇关于分布式哈希算法的文章,主要讨论了一致性哈希和普通哈希的区别,以及如何通过引入虚拟节点来优化一致性哈希的分布问题。 1. **普通哈希算法**: - Java中的`HashMap`类是一个典型...

    一致性哈希算法演示.rar

    一致性哈希算法是一种分布式哈希表(DHT)中用于解决数据分片和负载均衡问题的算法。在大型分布式系统中,例如缓存系统、分布式数据库等,一致性哈希能够确保当节点加入或离开时,尽可能少的数据需要迁移,从而保持...

    一致性哈希算法源码 Ketama一致性hash算法源码

    一致性哈希算法是一种分布式哈希(Distributed Hash Table, DHT)技术,旨在解决在分布式环境中数据分布不均匀的问题。Ketama算法是基于一致性哈希的一种优化实现,由Last.fm公司的Simon Willison提出,其目标是在...

    深入探讨一致性哈希:分布式系统中的应用与优势

    一致性哈希(Consistent Hashing)是一种特殊的哈希算法,它在分布式缓存和负载均衡等场景中被广泛应用。它通过将数据和服务器节点映射到一个哈希环上,提供了一种在节点增减时能够最小化数据重新分配的机制。本文将...

    Mycat一致性哈希分片算法.zip

    《Mycat一致性哈希分片算法详解》 在分布式数据库系统中,数据分片是实现高可用性和可扩展性的重要手段。Mycat作为一款开源的分布式数据库中间件,其核心特性之一就是数据分片策略,而一致性哈希分片算法在其中扮演...

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

    一致性哈希算法是一种在分布式系统中用于解决数据分发和负载均衡问题的算法。随着互联网技术的快速发展,分布式系统已经成为支撑大规模服务的关键技术之一。在分布式系统中,多个节点通过网络协同工作,提供高可用性...

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

    ### 一致性哈希算法及其在分布式系统中的应用 #### 摘要 一致性哈希算法是一种用于解决分布式系统中节点动态变化导致的数据重新分布问题的关键技术。它通过将哈希空间映射到一个循环的空间中,实现了数据节点的高效...

    24一致性哈希:如何高效地均衡负载?1

    一致性哈希算法是一种在分布式系统中解决负载均衡和数据分布问题的有效方法。在传统的哈希算法中,当添加或移除服务器节点时,大部分数据需要重新映射,导致大规模的数据迁移。而一致性哈希算法通过特定的设计,能够...

    一致性哈希算法应用及优化(最简洁明了的教程)

    一致性哈希算法应用及优化是IT领域中分布式系统设计的核心技术之一,特别是在处理大规模数据分布与缓存系统中,其重要性不言而喻。本文将深入探讨一致性哈希算法的基本概念、工作原理以及在实际场景中的应用和优化...

    Mycat一致性哈希分片算法1

    Mycat 一致性哈希分片算法 Mycat是一款开源的数据库中间件,支持各种数据库管理系统,包括 MySQL、 PostgreSQL、Oracle 等。Mycat 的核心功能之一是分片(Sharding),它可以将大量数据分布式存储在多个数据库节点...

    一致性哈希(php版)

    一致性哈希算法的php版,希望能帮到phper了解一致性哈希

    分布式存储系统中一致性哈希算法的研究.pdf

    一致性哈希算法作为解决这一问题的重要手段之一,近些年来得到了广泛关注和应用。 一致性哈希算法由David Karger等人在1997年提出,它是一种特殊的哈希算法,主要用于分布式系统中实现负载均衡。与传统的哈希算法...

Global site tag (gtag.js) - Google Analytics