123456789_123456789_123456789_123456789_123456789_

Class: Redis::HashRing

Relationships & Source Files
Inherits: Object
Defined in: lib/redis/hash_ring.rb

Constant Summary

Class Method Summary

Instance Attribute Summary

Instance Method Summary

Constructor Details

.new(nodes = [], replicas = POINTS_PER_SERVER) ⇒ HashRing

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.

[ GitHub ] 

  


# File 'lib/redis/hash_ring.rb', line 15



def initialize(nodes = [], replicas = POINTS_PER_SERVER)
  @replicas = replicas
  @ring = {}
  @nodes = []
  @sorted_keys = []
  nodes.each do |node|
    add_node(node)
  end
end


  







Instance Attribute Details



  

    #nodes   (readonly)
  

  [ GitHub ]


  

  


# File 'lib/redis/hash_ring.rb', line 10



attr_reader :ring, :sorted_keys, :replicas, :nodes


  








  

    #replicas   (readonly)
  

  [ GitHub ]


  

  


# File 'lib/redis/hash_ring.rb', line 10



attr_reader :ring, :sorted_keys, :replicas, :nodes


  








  

    #ring   (readonly)
  

  [ GitHub ]


  

  


# File 'lib/redis/hash_ring.rb', line 10



attr_reader :ring, :sorted_keys, :replicas, :nodes


  








  

    #sorted_keys   (readonly)
  

  [ GitHub ]


  

  


# File 'lib/redis/hash_ring.rb', line 10



attr_reader :ring, :sorted_keys, :replicas, :nodes


  







Instance Method Details



  

    #add_node(node)  
  



  

    
Adds a node to the hash ring (including a number of replicas).


  



  [ GitHub ]


  

  


# File 'lib/redis/hash_ring.rb', line 26



def add_node(node)
  @nodes << node
  @replicas.times do |i|
    key = server_hash_for("#{node.id}:#{i}")
    @ring[key] = node
    @sorted_keys << key
  end
  @sorted_keys.sort!
end


  








  

    #binary_search(ary, value)   (private)
  



  

    
Find the closest index in HashRing with value <= the given value


  



  [ GitHub ]


  

  


# File 'lib/redis/hash_ring.rb', line 73



def binary_search(ary, value)
  upper = ary.size
  lower = 0

  while lower < upper
    mid = (lower + upper) / 2
    if ary[mid] > value
      upper = mid
    else
      lower = mid + 1
    end
  end

  upper - 1
end


  








  

    #get_node(key)  
  



  

    
get the node in the hash ring for this key


  



  [ GitHub ]


  

  


# File 'lib/redis/hash_ring.rb', line 46



def get_node(key)
  hash = hash_for(key)
  idx = binary_search(@sorted_keys, hash)
  @ring[@sorted_keys[idx]]
end


  








  

    #hash_for(key)   (private)
  

  [ GitHub ]


  

  


# File 'lib/redis/hash_ring.rb', line 64



def hash_for(key)
  Zlib.crc32(key)
end


  








  

    #iter_nodes(key)  
  

  [ GitHub ]


  

  


# File 'lib/redis/hash_ring.rb', line 52



def iter_nodes(key)
  return [nil, nil] if @ring.empty?

  crc = hash_for(key)
  pos = binary_search(@sorted_keys, crc)
  @ring.size.times do |n|
    yield @ring[@sorted_keys[(pos + n) % @ring.size]]
  end
end


  








  

    #remove_node(node)  
  

  [ GitHub ]


  

  


# File 'lib/redis/hash_ring.rb', line 36



def remove_node(node)
  @nodes.reject! { |n| n.id == node.id }
  @replicas.times do |i|
    key = server_hash_for("#{node.id}:#{i}")
    @ring.delete(key)
    @sorted_keys.reject! { |k| k == key }
  end
end


  








  

    #server_hash_for(key)   (private)
  

  [ GitHub ]


  

  


# File 'lib/redis/hash_ring.rb', line 68



def server_hash_for(key)
  Digest::MD5.digest(key).unpack1("L>")
end