consistenthash.rb

# ported from http://amix.dk/blog/viewEntry/19367

require 'digest/md5'

class ConsistentHash

    def initialize(nodes=nil, replicas=100)
        # Manages a hash ring.
        # `nodes` is a list of objects that have a proper string representation.
        # `replicas` indicates how many virtual points should be used per node,
        # `replicas are required to improve the distribution. the more replicas, the more time it'll take to get the hash position.
        @replicas = replicas
        @ring = {}
        @sorted_keys = []

        nodes.each { |node| add_node(node) } if nodes
    end

    def node_keys(node)
        for i in 0...@replicas
            key = gen_key("#{node}:#{i}")
            yield key
        end
    end

    def add_node(node)
        # Adds a `node` to the hash ring (including a number of replicas).
        node_keys(node) do |key|	
            @ring[key] = node
            @sorted_keys << key
        end
        @sorted_keys.sort!
    end

    def remove_node(node)
        # Removes `node` from the hash ring and its replicas.
        node_keys(node) do |key|
            @ring.delete(key)
            @sorted_keys.delete(key)
        end
    end

    def get_node(string_key)
        # Given a string key a corresponding node in the hash ring is returned.
        # If the hash ring is empty, `nil` is returned.
        get_node_pos(string_key)[0]
    end

    def get_node_pos(string_key)
        # Given a string key a corresponding node in the hash ring is returned
        # along with it's position in the ring.
        # If the hash ring is empty, [`nil`, `nil`] is returned.
        return [nil, nil] if @ring.empty?

        key = gen_key(string_key)

        nodes = @sorted_keys
        nodes.each_with_index { |node, i| return [@ring[node], i] if key <= node }

        return [@ring[nodes[0]], 0]
    end

    def gen_key(key)
        # Given a string key it returns a long value,
        # this long value represents a place on the hash ring.
        # md5 is currently used because it mixes well.
        Digest::MD5.hexdigest(key).to_i(16)
    end
end