client-libraries/ruby/lib/hash_ring.rb

   1 require 'digest/md5'
   2 class HashRing
   3   attr_reader :ring, :sorted_keys, :replicas, :nodes
   4   # nodes is a list of objects that have a proper to_s representation.
   5   # replicas indicates how many virtual points should be used pr. node,
   6   # replicas are required to improve the distribution.
   7   def initialize(nodes=[], replicas=3)
   8     @replicas = replicas
   9     @ring = {}
  10     @nodes = []
  11     @sorted_keys = []
  12     nodes.each do |node|
  13       add_node(node)
  14     end
  15   end
  16
  17   # Adds a `node` to the hash ring (including a number of replicas).
  18   def add_node(node)
  19     @nodes << node
  20     @replicas.times do |i|
  21       key = gen_key("#{node}:#{i}")
  22       @ring[key] = node
  23       @sorted_keys << key
  24     end
  25     @sorted_keys.sort!
  26   end
  27
  28   def remove_node(node)
  29     @replicas.times do |i|
  30       key = gen_key("#{node}:#{count}")
  31       @ring.delete(key)
  32       @sorted_keys.reject! {|k| k == key}
  33     end
  34   end
  35
  36   # get the node in the hash ring for this key
  37   def get_node(key)
  38     get_node_pos(key)[0]
  39   end
  40
  41   def get_node_pos(key)
  42     return [nil,nil] if @ring.size == 0
  43     key = gen_key(key)
  44     nodes = @sorted_keys
  45     nodes.size.times do |i|
  46       node = nodes[i]
  47       if key <= node
  48         return [@ring[node], i]
  49       end
  50     end
  51     [@ring[nodes[0]], 0]
  52   end
  53
  54   def iter_nodes(key)
  55     return [nil,nil] if @ring.size == 0
  56     node, pos = get_node_pos(key)
  57     @sorted_keys[pos..-1].each do |k|
  58       yield @ring[k]
  59     end
  60   end
  61
  62   def gen_key(key)
  63     key = Digest::MD5.hexdigest(key)
  64     ((key[3] << 24) | (key[2] << 16) | (key[1] << 8) | key[0])
  65   end
  66
  67 end
  68
  69 # ring = HashRing.new ['server1', 'server2', 'server3']
  70 # p ring
  71 # #
  72 # p ring.get_node "kjhjkjlkjlkkh"
  73 #