写点什么

架构师第一期作业(第 5 周)

用户头像
Cheer
关注
发布于: 2020 年 10 月 20 日



  1. 用你熟悉的编程语言实现一致性 hash 算法。

  2. 编写测试用例测试这个算法,测试 100 万 KV 数据,10 个服务器节点的情况下,计算这些 KV 数据在服务器上分布数量的标准差,以评估算法的存储负载不均衡性。



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




从测试结果来看,虚拟节点数越多分布标准差越小,也可以看出随着虚拟节点增加,标准差的下降也越来越小。业界平均使用150~200虚拟节点,应该是个不错的综合考虑选择。



发布于: 2020 年 10 月 20 日阅读数: 33
用户头像

Cheer

关注

还未添加个人签名 2018.11.25 加入

还未添加个人简介

评论

发布
暂无评论
架构师第一期作业(第5周)