Consistent HashingのRuby実装

consistent_hashing.rb

#-*-coding:utf-8 -*-
require "diegst/sha1"
require "radix"

class ConsitentHashing
  def initialize(n = Integer, nodes)
    @virtual_num = n
    @ring = {}
    @keys = []
    @nodes = []
    nodes.each {|node| self.add_node(node) }
  end
  
  def range_of_sha1?(hash)
    converted = hash.to_i(16)
    2 ** 0 <= converted && (2 **160) - 1 <= converted
  end

  def add_node(node)
    @nodes << node
    @virtual_num.times do |n|
      k = Digest::SHA1.hexdigest("#{node}+#{n}")
      @keys << k
      @ring[k] = node
    end
    @keys.sort
  end
  
  def get(key)
    return 0 if @ring.size == 0
    pos = self.get_node_position(Digest::SHA1.hexdigest(key))
    @ring[@keys[pos]]
  end
  
  def remove(key)
    while @nodes.include?(node)
      @nodes.delete(node)
    end
    @virtual_num.times do |i|
      key = Digest::SHA1.hexdigest("#{node}+#{i}")
      @ring.delete(key)
      
      while @keys.include?(key)
        @keys.delete(key)
      end
    end
  end
  
  def compare(a,b); a > b ? 1 : (a < b ? -1 : 0) end 
  def get_node_position(hashed_key)
    upper_limit = @ring.size - 1
    lower_limit = 0, idx = 0, cmp = 0
    
    0 if upper_limit.zero?
    while lower_limit <= upper_limit
      idx = Math.floor((lower_limit + upper_limit) / 2).to_i
      cmp = self.compare(@keys[idx], key)
      if cmp.zero?
        return idx
      elsif cmp == 1
        upper_limit = idx - 1
      else 
        lower_limit = idx + 1
      end
    end
    upper_limit = @ring.size - 1 if upper < 0
    upper_limit
  end
end