A simple example to show how Rendezvous Hashing maintains minimal disruption even when targets change

rendezvous-hashing-demo.rb

#!/usr/bin/env ruby

#
# Demonstrate a simple Rendezvous Hash, which is a form of distributed hash 
# which allows clients to consistently map resources to a set of "sites",
# and remap them if a site is removed, without having to change the mapping
# for any resources on other sites.
#
# Example output:
#
# Initializing PRNG seed 333
#
# Assigning 1000 objects to 5 sites
#   {"a"=>185, "c"=>227, "e"=>185, "d"=>210, "b"=>193}
#
# Assigning 1000 objects to 4 sites
#   185/1000 changed sites
#   {"b"=>239, "c"=>266, "e"=>242, "d"=>253}

require 'digest'

SEED = 333
NUM_OBJECTS = 1000

# For a given object, compute the score for all sites and return highest
# scoring (NOTE: The "score" in this case is a byte string, but we can
# still use comparison methods on it)
def destination(object, all_sites = [])
  best_site = nil
  best_score = ""
  all_sites.each do |site|
    score = Digest::SHA1.digest(object.to_s + site.to_s)
    if score > best_score
      best_site = site
      best_score = score
    end
  end
  best_site
end

#
# Create some test objects
#
puts "Initializing PRNG seed #{SEED}"
$prng = Random.new(SEED)
puts

def random_string(length = 8)
  (0...length).map { (65 + $prng.rand(26)).chr }.join
end

@object_destinations = {}

NUM_OBJECTS.times do
  object = random_string()
  @object_destinations[object] = nil
end

#
# Assign all the objects against all sites
#
@available_sites = ('a'..'e').to_a
puts "Assigning #{NUM_OBJECTS} objects to #{@available_sites.length} sites"

count_by_site = Hash.new(0)
@object_destinations.keys.each do |object|
  site = destination(object, @available_sites)
  #puts "\t#{object} => #{site}"
  count_by_site[site] += 1
  @object_destinations[object] = site
end

puts "\t" + count_by_site.inspect
puts

#
# Do it again, but with one site missing
#
@available_sites = @available_sites[1..-1]

puts "Assigning #{NUM_OBJECTS} objects to #{@available_sites.length} sites"
count_by_site = Hash.new(0)
changed = 0
@object_destinations.keys.each do |object|
  site = destination(object, @available_sites)
  if site != @object_destinations[object]
    #puts "\tCHANGED #{object} => #{site}"
    changed += 1
  end
  count_by_site[site] += 1
end

puts "\t" + "#{changed}/#{@object_destinations.keys.length} changed sites"
puts "\t" + count_by_site.inspect
puts