X-Git-Url: https://git.saurik.com/redis.git/blobdiff_plain/ed9b544e10b84cd43348ddfab7068b610a5df1f7..39c8c0f22d21c80783b464f90fc8c8c8e6faaa2c:/client-libraries/ruby/lib/hash_ring.rb

diff --git a/client-libraries/ruby/lib/hash_ring.rb b/client-libraries/ruby/lib/hash_ring.rb
index 403f7cf5..bed86601 100644
--- a/client-libraries/ruby/lib/hash_ring.rb
+++ b/client-libraries/ruby/lib/hash_ring.rb
@@ -1,10 +1,15 @@
-require 'digest/md5'
+require 'zlib'
+
 class HashRing
+
+  POINTS_PER_SERVER = 160 # this is the default in libmemcached
+
   attr_reader :ring, :sorted_keys, :replicas, :nodes
+
   # nodes is a list of objects that have a proper to_s representation.
   # replicas indicates how many virtual points should be used pr. node,
   # replicas are required to improve the distribution.
-  def initialize(nodes=[], replicas=3)
+  def initialize(nodes=[], replicas=POINTS_PER_SERVER)
     @replicas = replicas
     @ring = {}
     @nodes = []
@@ -18,7 +23,7 @@ class HashRing
   def add_node(node)
     @nodes << node
     @replicas.times do |i|
-      key = gen_key("#{node}:#{i}")
+      key = Zlib.crc32("#{node}:#{i}")
       @ring[key] = node
       @sorted_keys << key
     end
@@ -27,7 +32,7 @@ class HashRing
   
   def remove_node(node)
     @replicas.times do |i|
-      key = gen_key("#{node}:#{count}")
+      key = Zlib.crc32("#{node}:#{count}")
       @ring.delete(key)
       @sorted_keys.reject! {|k| k == key}
     end
@@ -40,15 +45,9 @@ class HashRing
   
   def get_node_pos(key)
     return [nil,nil] if @ring.size == 0
-    key = gen_key(key)
-    nodes = @sorted_keys
-    nodes.size.times do |i|
-      node = nodes[i]
-      if key <= node
-        return [@ring[node], i]
-      end
-    end
-    [@ring[nodes[0]], 0]
+    crc = Zlib.crc32(key)
+    idx = HashRing.binary_search(@sorted_keys, crc)
+    return [@ring[@sorted_keys[idx]], idx]
   end
   
   def iter_nodes(key)
@@ -59,11 +58,66 @@ class HashRing
     end  
   end
   
-  def gen_key(key)
-    key = Digest::MD5.hexdigest(key)
-    ((key[3] << 24) | (key[2] << 16) | (key[1] << 8) | key[0])
+  class << self
+
+    # gem install RubyInline to use this code
+    # Native extension to perform the binary search within the hashring.
+    # There's a pure ruby version below so this is purely optional
+    # for performance.  In testing 20k gets and sets, the native
+    # binary search shaved about 12% off the runtime (9sec -> 8sec).
+    begin
+      require 'inline'
+      inline do |builder|
+        builder.c <<-EOM
+        int binary_search(VALUE ary, unsigned int r) {
+            int upper = RARRAY_LEN(ary) - 1;
+            int lower = 0;
+            int idx = 0;
+
+            while (lower <= upper) {
+                idx = (lower + upper) / 2;
+
+                VALUE continuumValue = RARRAY_PTR(ary)[idx];
+                unsigned int l = NUM2UINT(continuumValue);
+                if (l == r) {
+                    return idx;
+                }
+                else if (l > r) {
+                    upper = idx - 1;
+                }
+                else {
+                    lower = idx + 1;
+                }
+            }
+            return upper;
+        }
+        EOM
+      end
+    rescue Exception => e
+      # Find the closest index in HashRing with value <= the given value
+      def binary_search(ary, value, &block)
+        upper = ary.size - 1
+        lower = 0
+        idx = 0
+
+        while(lower <= upper) do
+          idx = (lower + upper) / 2
+          comp = ary[idx] <=> value
+
+          if comp == 0
+            return idx
+          elsif comp > 0
+            upper = idx - 1
+          else
+            lower = idx + 1
+          end
+        end
+        return upper
+      end
+
+    end
   end
-  
+
 end
 
 # ring = HashRing.new ['server1', 'server2', 'server3']