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     @nodes.reject!{|n| n.to_s == node.to_s}
  35     @replicas.times do |i|
  36       key = Zlib.crc32("#{node}:#{i}")
  37       @ring.delete(key)
  38       @sorted_keys.reject! {|k| k == key}
  39     end
  40   end
  41
  42   # get the node in the hash ring for this key
  43   def get_node(key)
  44     get_node_pos(key)[0]
  45   end
  46
  47   def get_node_pos(key)
  48     return [nil,nil] if @ring.size == 0
  49     crc = Zlib.crc32(key)
  50     idx = HashRing.binary_search(@sorted_keys, crc)
  51     return [@ring[@sorted_keys[idx]], idx]
  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   class << self
  63
  64     # gem install RubyInline to use this code
  65     # Native extension to perform the binary search within the hashring.
  66     # There's a pure ruby version below so this is purely optional
  67     # for performance.  In testing 20k gets and sets, the native
  68     # binary search shaved about 12% off the runtime (9sec -> 8sec).
  69     begin
  70       require 'inline'
  71       inline do |builder|
  72         builder.c <<-EOM
  73         int binary_search(VALUE ary, unsigned int r) {
  74             int upper = RARRAY_LEN(ary) - 1;
  75             int lower = 0;
  76             int idx = 0;
  77
  78             while (lower <= upper) {
  79                 idx = (lower + upper) / 2;
  80
  81                 VALUE continuumValue = RARRAY_PTR(ary)[idx];
  82                 unsigned int l = NUM2UINT(continuumValue);
  83                 if (l == r) {
  84                     return idx;
  85                 }
  86                 else if (l > r) {
  87                     upper = idx - 1;
  88                 }
  89                 else {
  90                     lower = idx + 1;
  91                 }
  92             }
  93             return upper;
  94         }
  95         EOM
  96       end
  97     rescue Exception => e
  98       # Find the closest index in HashRing with value <= the given value
  99       def binary_search(ary, value, &block)
 100         upper = ary.size - 1
 101         lower = 0
 102         idx = 0
 103
 104         while(lower <= upper) do
 105           idx = (lower + upper) / 2
 106           comp = ary[idx] <=> value
 107
 108           if comp == 0
 109             return idx
 110           elsif comp > 0
 111             upper = idx - 1
 112           else
 113             lower = idx + 1
 114           end
 115         end
 116         return upper
 117       end
 118
 119     end
 120   end
 121
 122 end
 123
 124 # ring = HashRing.new ['server1', 'server2', 'server3']
 125 # p ring
 126 # #
 127 # p ring.get_node "kjhjkjlkjlkkh"
 128 #