hash算法分析
时间：2019-03-29 15:20:01
手机看文章
扫描二维码
随时随地手机看文章
[导读] 对于普通的hash算法，计算增加一个节点对于数据迁移的比率以及计算时间from hashlib import md5
from struct import unpack_from
from
对于普通的hash算法，计算增加一个节点对于数据迁移的比率以及计算时间
from hashlib import md5
from struct import unpack_from
from time import time
begin=time()#记录下当前时间，方便计算计算消耗的时间
NODE_COUNT=100 #原有节点数目
NEW_NODE_COUNT=101#新的节点数目
DATA_ID_COUNT=10000000#数据量
move_ids=0#统计可能移动的数据的个数
for data_id in xrange(DATA_ID_COUNT):
index=data_id
data_id=str(data_id)
hsh=unpack_from('>I',md5(str(data_id)).digest())[0]#根据数据节点计算MD5值，将二进制转换成我们理解的无符号型整数，因为unpack_from返回的是数组，也即取[0]
node_id=hsh%NODE_COUNT
new_node_id=hsh%NEW_NODE_COUNT
if node_id!=new_node_id:
move_ids+=1
percent_moved=100.0*move_ids/DATA_ID_COUNT
print '%d ids moved, %0.2f%%' % (move_ids,percent_moved)
duration=time()-begin
print 'Total time %d seconds' % duration实验输出
9900989 ids moved, 99.01% Total time 46 second
这样的输出结果显然不能是的我们满意，现在尝试做一个ring来进行存储
实验原理：
仍然有数据10000000，原有节点数目是100，增加了一个节点变成了101，
我们将数据分成100分，
第0个节点存放数据 10000000/100*0
第1个节点存放数据 10000000/100*1
...
第99个节点存放数据 10000000/100*99
那么改变节点数目之后就变成了101
第0个节点存放数据 10000000/101*0
第1个节点存放数据 10000000/101*1
...
第100个节点存放数据 10000000/101*100
其数据迁移量是：
from bisect import bisect_left
from hashlib import md5
from struct import unpack_from
from time import time
begin = time()
NODE_COUNT = 100
NEW_NODE_COUNT = 101
DATA_ID_COUNT = 10000000
node_range_starts = []
for node_id in xrange(NODE_COUNT):
node_range_starts.append(DATA_ID_COUNT / NODE_COUNT * node_id)
new_node_range_starts = []
for new_node_id in xrange(NEW_NODE_COUNT):
new_node_range_starts.append(DATA_ID_COUNT / NEW_NODE_COUNT * new_node_id)
moved_ids = 0
for data_id in xrange(DATA_ID_COUNT):
data_id = str(data_id)
hsh = unpack_from('>I', md5(str(data_id)).digest())[0]
node_id = bisect_left(node_range_starts, hsh % DATA_ID_COUNT) % NODE_COUNT
#node_id是原来的数据进行映射的点，new_node_id则是根据新的节点数目进行映射，如果不一致，则进行数据迁移
new_node_id = bisect_left(new_node_range_starts,
hsh % DATA_ID_COUNT) % NEW_NODE_COUNT
if node_id != new_node_id:
moved_ids += 1
percent_moved = 100.0 * moved_ids / DATA_ID_COUNT
print '%d ids moved, %.02f%%' % (moved_ids, percent_moved)
duration = time() - begin
print 'Total time %d second' % duration实验结果
4901707 ids moved, 49.02% Total time 69 second
现在加入虚节点之后进行hash的一致性讨论
from bisect import bisect_left
from hashlib import md5
from struct import unpack_from
from time import time
begin = time()
NODE_COUNT = 100
DATA_ID_COUNT = 10000000
VNODE_COUNT = 1000
vnode_range_starts = []
vnode2node = []
for vnode_id in xrange(VNODE_COUNT):
vnode_range_starts.append(DATA_ID_COUNT / VNODE_COUNT * vnode_id)
vnode2node.append(vnode_id % NODE_COUNT)
new_vnode2node = list(vnode2node)
new_node_id = NODE_COUNT #new_node_id就是新添加节点的索引值
NEW_NODE_COUNT = NODE_COUNT + 1
vnodes_to_reassign = VNODE_COUNT / NEW_NODE_COUNT #要进行重新分配的虚节点的数目，一下是只需确定，移动节点的数目，先遍历节点，确定节点索引值，
#然后遍历虚节点,如果虚节点指向的实节点索引值与之前一致，那么该虚节点的数据，则应该迁移到new_node_id节点上去，这里只改变虚节点和实节点的对应关系
while vnodes_to_reassign > 0:
for node_to_take_from in xrange(NODE_COUNT):
for vnode_id, node_id in enumerate(new_vnode2node):
if node_id == node_to_take_from:
new_vnode2node[vnode_id] = new_node_id
vnodes_to_reassign -= 1
break
if vnodes_to_reassign <= 0:
break
moved_ids = 0
for data_id in xrange(DATA_ID_COUNT):
data_id = str(data_id)
hsh = unpack_from('>I', md5(str(data_id)).digest())[0]
vnode_id = bisect_left(vnode_range_starts,
hsh % DATA_ID_COUNT) % VNODE_COUNT
node_id = vnode2node[vnode_id]
new_node_id = new_vnode2node[vnode_id]
if node_id != new_node_id:
moved_ids += 1
percent_moved = 100.0 * moved_ids / DATA_ID_COUNT
print '%d ids moved, %.02f%%' % (moved_ids, percent_moved)
duration = time() - begin
print 'Total time %d second' % duration实验结果：
90423 ids moved, 0.90% Total time 34 second
下载文档
