架构师第一期作业（第 5 周）

require 'digest/md5'
require 'securerandom'
require 'descriptive_statistics'
class String
  def hash_id
    Digest::MD5.hexdigest(self).to_i(16) % (2 ** 32 - 1)
  end
end
class ConsistentHash
  def initialize vnode_num
    @num_of_vnodes = vnode_num
  end
  def add server
    @nodes ||= {}
    if @num_of_vnodes > 0
      @num_of_vnodes.times do |i|
        vnode = server + '_' + i.to_s
        vid = vnode.hash_id
        @nodes[vid] = vnode
      end
    else
      id = server.hash_id
      @nodes[id] = server
    end
    @keys = @nodes.keys.sort
  end
  def remove server
    @nodes ||= {}
    
    if @num_of_vnodes > 0
      @num_of_vnodes.times do |i|
        vnode = server + '_' + i.to_s
        @nodes.delete vnode.hash_id
      end
    else
      @nodes.delete server.hash_id
    end
    @keys = @nodes.keys.sort
  end
  def get_server cache_key
    id = cache_key.hash_id
    key = @keys.bsearch { |k| k >= id }
    key = @keys[0] if key.nil?
    @nodes[key].split('_')[0]
  end
end
class Test
  def initialize size, server_num, vnode_num
    @size = size
    @vnode_num = vnode_num
    @server_num = server_num
  end
  def init_server
    @hash = ConsistentHash.new(@vnode_num)
    @server_num.times do |i|
      @hash.add "10.0.0.#{i + 1}"
    end
  end
  def run
    init_server
    result = {}
    @size.times do |i|
      key = SecureRandom.hex
      server = @hash.get_server key
      result[server] ||= 0
      result[server] += 1
    end
    result.sort.each do |k, v|
      print "\n#{k} => #{v}"
    end
    deviation = result.values.standard_deviation
    print "\n#{@vnode_num} VNodes Standard deviation: #{deviation}\n"
  end
end
##### test
Test.new(1000000, 10, 0).run
Test.new(1000000, 10, 10).run 
Test.new(1000000, 10, 50).run
Test.new(1000000, 10, 100).run
Test.new(1000000, 10, 150).run
Test.new(1000000, 10, 200).run
Test.new(1000000, 10, 300).run
Test.new(1000000, 10, 500).run

0 VNodes Standard deviation: 57755.30893346515
10 VNodes Standard deviation: 29447.974419304293
50 VNodes Standard deviation: 14106.573205424484
100 VNodes Standard deviation: 8963.619614865414
150 VNodes Standard deviation: 6030.176133414347
200 VNodes Standard deviation: 5068.374275840331
300 VNodes Standard deviation: 5110.457181114034
500 VNodes Standard deviation: 4372.238534206477