当前位置:首页 > 开发 > 编程语言 > 算法 > 正文

用clojure实现一致性哈希算法(consistent hashing)

发表于: 2014-05-16   作者:Aaron5   来源:转载   浏览次数:
摘要: 一、 依赖的jar包 [com.google.guava/guava 14.0.1] 二、具体实现 (defn vnodes "生成n个随机的vnode" [n] (vec (sort (repeatedly n #(rand-int 65536))))) (defn short-hash "产生一个0
一、 依赖的jar包
[com.google.guava/guava 14.0.1]


二、具体实现
(defn vnodes
  "生成n个随机的vnode"
  [n]
  (vec (sort (repeatedly n #(rand-int 65536)))))

(defn short-hash
  "产生一个0..2^16范围的hash值"
  [s]
  ;; SHA-1 used for uniform value distribution
  (bit-and (->> (.hashString (com.google.common.hash.Hashing/sha1) s) (.asInt)) 0xffff))

(defn closest-before
  "查找之前最近的一个vnode"
  [coll el]
  (let [idx (java.util.Collections/binarySearch coll el compare)]
    (cond
      (= -1 idx) -1 ;;
      (neg? idx) (coll (- -2 idx)) 
      :else      (coll idx))))

(defn responsible
  "超找某个数据hash之后应该属于哪个node。因为一个node包含一组vnode。所以多了个这个方法,不然用到closest-before其实就够了。"
  [hash ^List ring]
  (let [found (apply max-key #(closest-before % hash) ring)]
    (.lastIndexOf ring found)))


(closest-before [1 2 3 4 20 30 60 80 1020 34045] 50)
;;==>30
;;假设有node1:[100 200 300]。100,200,300是vnode。
;;假设有node2:[400 500 600]。
;;结果为1。可以把这连个node串成一个环(ring)来看。往前找最近的,就是node2了。所以返回index值为1。
(responsible 50 [[100 200 300] [400 500 600]] )
;;==> 1


用clojure实现一致性哈希算法(consistent hashing)

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
memcache虽然是分布式的应用服务,但分布的原则是由client端的api来决定的,api根据存储用的key以及
consistent hashing由来? 最初由Karger等人设计。在麻省理工学院用作分布式缓存,现在已经扩大到其
一致性哈希算法在1997年由麻省理工学院提出的一种分布式哈希(DHT)实现算法,设计目标是为了解决因
consistent hashing由来? 最初由Karger等人设计。在麻省理工学院用作分布式缓存,现在已经扩大到其
一、简单介绍一致性哈希算法 分布式存储中,常常涉及到负载均衡问题,由于有多个数据存储服务器。因
consistent hashing由来? 最初由Karger等人设计。在麻省理工学院用作分布式缓存,现在已经扩大到其
一致性哈希算法在1997年由麻省理工学院提出的一种分布式哈希(DHT)实现算法,设计目标是为了解决因
一致性哈希算法在1997年由麻省理工学院提出的一种分布式哈希(DHT)实现算法,设计目标是为了解决因
转载请说明出处:http://blog.csdn.net/cywosp/article/details/23397179 一致性哈希算法在1997年由
一个简单的consistent hashing的例子,很容易理解。 首先有一个设备类,定义了机器名和ip: [java]
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号