client-libraries/ruby/lib/hash_ring.rb

   1 require 'zlib'
   2
   3 class HashRing
   4
   5   POINTS_PER_SERVER = 160 # this is the default in libmemcached
   6
   7   attr_reader :ring, :sorted_keys, :replicas, :nodes
   8
   9   # nodes is a list of objects that have a proper to_s representation.
  10   # replicas indicates how many virtual points should be used pr. node,
  11   # replicas are required to improve the distribution.
  12   def initialize(nodes=[], replicas=POINTS_PER_SERVER)
  13     @replicas = replicas
  14     @ring = {}
  15     @nodes = []
  16     @sorted_keys = []
  17     nodes.each do |node|
  18       add_node(node)
  19     end
  20   end
  21
  22   # Adds a `node` to the hash ring (including a number of replicas).
  23   def add_node(node)
  24     @nodes << node
  25     @replicas.times do |i|
  26       key = Zlib.crc32("#{node}:#{i}")
  27       @ring[key] = node
  28       @sorted_keys << key
  29     end
  30     @sorted_keys.sort!
  31   end
  32
  33   def remove_node(node)
  34     @replicas.times do |i|
  35       key = Zlib.crc32("#{node}:#{count}")
  36       @ring.delete(key)
  37       @sorted_keys.reject! {|k| k == key}
  38     end
  39   end
  40
  41   # get the node in the hash ring for this key
  42   def get_node(key)
  43     get_node_pos(key)[0]
  44   end
  45
  46   def get_node_pos(key)
  47     return [nil,nil] if @ring.size == 0
  48     crc = Zlib.crc32(key)
  49     idx = HashRing.binary_search(@sorted_keys, crc)
  50     return [@ring[@sorted_keys[idx]], idx]
  51   end
  52
  53   def iter_nodes(key)
  54     return [nil,nil] if @ring.size == 0
  55     node, pos = get_node_pos(key)
  56     @sorted_keys[pos..-1].each do |k|
  57       yield @ring[k]
  58     end
  59   end
  60
  61   class << self
  62
  63     # gem install RubyInline to use this code
  64     # Native extension to perform the binary search within the hashring.
  65     # There's a pure ruby version below so this is purely optional
  66     # for performance.  In testing 20k gets and sets, the native
  67     # binary search shaved about 12% off the runtime (9sec -> 8sec).
  68     begin
  69       require 'inline'
  70       inline do |builder|
  71         builder.c <<-EOM
  72         int binary_search(VALUE ary, unsigned int r) {
  73             int upper = RARRAY_LEN(ary) - 1;
  74             int lower = 0;
  75             int idx = 0;
  76
  77             while (lower <= upper) {
  78                 idx = (lower + upper) / 2;
  79
  80                 VALUE continuumValue = RARRAY_PTR(ary)[idx];
  81                 unsigned int l = NUM2UINT(continuumValue);
  82                 if (l == r) {
  83                     return idx;
  84                 }
  85                 else if (l > r) {
  86                     upper = idx - 1;
  87                 }
  88                 else {
  89                     lower = idx + 1;
  90                 }
  91             }
  92             return upper;
  93         }
  94         EOM
  95       end
  96     rescue Exception => e
  97       # Find the closest index in HashRing with value <= the given value
  98       def binary_search(ary, value, &block)
  99         upper = ary.size - 1
 100         lower = 0
 101         idx = 0
 102
 103         while(lower <= upper) do
 104           idx = (lower + upper) / 2
 105           comp = ary[idx] <=> value
 106
 107           if comp == 0
 108             return idx
 109           elsif comp > 0
 110             upper = idx - 1
 111           else
 112             lower = idx + 1
 113           end
 114         end
 115         return upper
 116       end
 117
 118     end
 119   end
 120
 121 end
 122
 123 # ring = HashRing.new ['server1', 'server2', 'server3']
 124 # p ring
 125 # #
 126 # p ring.get_node "kjhjkjlkjlkkh"
 127 #