hash算法分析
[導(dǎo)讀]???? 對(duì)于普通的hash算法，計(jì)算增加一個(gè)節(jié)點(diǎn)對(duì)于數(shù)據(jù)遷移的比率以及計(jì)算時(shí)間from?hashlib?import?md5
from?struct?import?unpack_from
from?
???? 對(duì)于普通的hash算法，計(jì)算增加一個(gè)節(jié)點(diǎn)對(duì)于數(shù)據(jù)遷移的比率以及計(jì)算時(shí)間
from?hashlib?import?md5
from?struct?import?unpack_from
from?time?import?time
begin=time()#記錄下當(dāng)前時(shí)間，方便計(jì)算計(jì)算消耗的時(shí)間
NODE_COUNT=100?#原有節(jié)點(diǎn)數(shù)目
NEW_NODE_COUNT=101#新的節(jié)點(diǎn)數(shù)目
DATA_ID_COUNT=10000000#數(shù)據(jù)量
move_ids=0#統(tǒng)計(jì)可能移動(dòng)的數(shù)據(jù)的個(gè)數(shù)
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]#根據(jù)數(shù)據(jù)節(jié)點(diǎn)計(jì)算MD5值，將二進(jìn)制轉(zhuǎn)換成我們理解的無(wú)符號(hào)型整數(shù)，因?yàn)閡npack_from返回的是數(shù)組，也即取[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實(shí)驗(yàn)輸出
9900989?ids?moved,?99.01% Total?time?46?second
這樣的輸出結(jié)果顯然不能是的我們滿(mǎn)意，現(xiàn)在嘗試做一個(gè)ring來(lái)進(jìn)行存儲(chǔ)
實(shí)驗(yàn)原理：
????? 仍然有數(shù)據(jù)10000000，原有節(jié)點(diǎn)數(shù)目是100，增加了一個(gè)節(jié)點(diǎn)變成了101，
???? 我們將數(shù)據(jù)分成100分，
??? 第0個(gè)節(jié)點(diǎn)存放數(shù)據(jù) 10000000/100*0
??? 第1個(gè)節(jié)點(diǎn)存放數(shù)據(jù) 10000000/100*1
?? ...
??? 第99個(gè)節(jié)點(diǎn)存放數(shù)據(jù) 10000000/100*99
??? 那么改變節(jié)點(diǎn)數(shù)目之后就變成了101
??? 第0個(gè)節(jié)點(diǎn)存放數(shù)據(jù) 10000000/101*0
??? 第1個(gè)節(jié)點(diǎn)存放數(shù)據(jù) 10000000/101*1
?? ...
??? 第100個(gè)節(jié)點(diǎn)存放數(shù)據(jù) 10000000/101*100
?? 其數(shù)據(jù)遷移量是：
?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是原來(lái)的數(shù)據(jù)進(jìn)行映射的點(diǎn)，new_node_id則是根據(jù)新的節(jié)點(diǎn)數(shù)目進(jìn)行映射，如果不一致，則進(jìn)行數(shù)據(jù)遷移
????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實(shí)驗(yàn)結(jié)果
4901707?ids?moved,?49.02% Total?time?69?second
現(xiàn)在加入虛節(jié)點(diǎn)之后進(jìn)行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就是新添加節(jié)點(diǎn)的索引值
NEW_NODE_COUNT?=?NODE_COUNT?+?1??
vnodes_to_reassign?=?VNODE_COUNT?/?NEW_NODE_COUNT??#要進(jìn)行重新分配的虛節(jié)點(diǎn)的數(shù)目，一下是只需確定，移動(dòng)節(jié)點(diǎn)的數(shù)目，先遍歷節(jié)點(diǎn)，確定節(jié)點(diǎn)索引值，
#然后遍歷虛節(jié)點(diǎn),如果虛節(jié)點(diǎn)指向的實(shí)節(jié)點(diǎn)索引值與之前一致，那么該虛節(jié)點(diǎn)的數(shù)據(jù)，則應(yīng)該遷移到new_node_id節(jié)點(diǎn)上去，這里只改變虛節(jié)點(diǎn)和實(shí)節(jié)點(diǎn)的對(duì)應(yīng)關(guān)系
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實(shí)驗(yàn)結(jié)果：
90423?ids?moved,?0.90% Total?time?34?second
下載文檔
