架构师训练营第二期 Week 5 作业

require 'digest'
require 'forwardable'
class ConsistentHashing
  CIRCLE_LENGTH = 2 ** 32
  def self.hash(string)
    Digest::MD5.hexdigest(string).to_i(16) % (CIRCLE_LENGTH)
  end
end
class Node
  extend Forwardable
  attr_reader :name
  def_delegator :data, :fetch
  def_delegator :data, :store
  def_delegator :data, :delete
  def initialize(name)
    @name = name
    @data = {}
  end
  def count
    data.keys.size
  end
  private
  attr_reader :data
end
class VirtualNode
  include Comparable
  extend Forwardable
  attr_reader :key, :name, :node
  def_delegator :node, :fetch
  def_delegator :node, :store
  def_delegator :node, :delete
  def initialize(name, node)
    @name = name
    @node = node
    @key = ConsistentHashing.hash(name)
  end
  def <=>(other)
    key <=> other.key
  end
end
class DistributedHash
  WEIGHT = 150
  attr_reader :nodes, :virtual_nodes, :weight
  def initialize(nodes = [], weight = WEIGHT)
    @virtual_nodes = []
    @nodes = []
    @weight = weight
    nodes.each { |node| add_node(node) }
  end
  def add_node(node)
    weight.times do |i|
      virtual_nodes << VirtualNode.new("N_#{node.name}_#{i}", node)
    end
    virtual_nodes.sort!
    nodes << node
  end
  def remove_node(node_name)
    virtual_nodes.reject! { |vn| vn.node.name == node_name }
    nodes.reject! { |n| n.name == node_name }
  end
  def store(key, value)
    vn = find_nearest_virtual_node(key)
    vn.store(key, value)
  end
  def fetch(key)
    vn = find_nearest_virtual_node(key)
    vn.fetch(key)
  end
  def delete(key)
    vn = find_nearest_virtual_node(key)
    vn.delete(key)
  end
  private
  def find_nearest_virtual_node(key)
    hashed_key = ConsistentHashing.hash(key)
    virtual_nodes.bsearch { |vn| vn.key >= hashed_key } || virtual_nodes[0]
  end
end
def variance(values)
  m = values.sum.to_f / values.size
  sum = 0.0
  values.each { |v| sum += (v-m) ** 2 }
  sum / values.size
end
def standard_deviation(values)
  Math.sqrt(variance(values))
end
ds = DistributedHash.new(
  [
    Node.new('s1'),
    Node.new('s2'),
    Node.new('s3'),
    Node.new('s4'),
    Node.new('s5'),
    Node.new('s6'),
    Node.new('s7'),
    Node.new('s8'),
    Node.new('s9'),
    Node.new('s10'),
  ]
)
1_000_000.times do |i|
  ds.store(i.to_s, i)
end
node_counts = ds.nodes.map(&:count)
puts "Standard deviation for 150 virtual nodes: #{standard_deviation(node_counts)}"
ds = DistributedHash.new(
  [
    Node.new('s1'),
    Node.new('s2'),
    Node.new('s3'),
    Node.new('s4'),
    Node.new('s5'),
    Node.new('s6'),
    Node.new('s7'),
    Node.new('s8'),
    Node.new('s9'),
    Node.new('s10'),
  ],
  200
)
1_000_000.times do |i|
  ds.store(i.to_s, i)
end
node_counts = ds.nodes.map(&:count)
puts "Standard deviation for 200 virtual nodes: #{standard_deviation(node_counts)}"

$ ruby consistent_hashing.rb
Standard deviation for 150 virtual nodes: 5911.8596228259685
Standard deviation for 200 virtual nodes: 3909.191476507642