什么是hash算法

???? 對于普通的hash算法，計算增加一個節(jié)點對于數(shù)據(jù)遷移的比率以及計算時間

from?hashlib?import?md5
from?struct?import?unpack_from
from?time?import?time

begin=time()#記錄下當(dāng)前時間，方便計算計算消耗的時間
NODE_COUNT=100?#原有節(jié)點數(shù)目
NEW_NODE_COUNT=101#新的節(jié)點數(shù)目
DATA_ID_COUNT=10000000#數(shù)據(jù)量

move_ids=0#統(tǒng)計可能移動的數(shù)據(jù)的個數(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é)點計算MD5值，將二進(jìn)制轉(zhuǎn)換成我們理解的無符號型整數(shù)，因為unpack_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

實驗輸出

9900989?ids?moved,?99.01%
Total?time?46?second

這樣的輸出結(jié)果顯然不能是的我們滿意，現(xiàn)在嘗試做一個ring來進(jìn)行存儲

實驗原理：

????? 仍然有數(shù)據(jù)10000000，原有節(jié)點數(shù)目是100，增加了一個節(jié)點變成了101，

???? 我們將數(shù)據(jù)分成100分，

??? 第0個節(jié)點存放數(shù)據(jù) 10000000/100*0

??? 第1個節(jié)點存放數(shù)據(jù) 10000000/100*1

?? ...

??? 第99個節(jié)點存放數(shù)據(jù) 10000000/100*99

??? 那么改變節(jié)點數(shù)目之后就變成了101

??? 第0個節(jié)點存放數(shù)據(jù) 10000000/101*0

??? 第1個節(jié)點存放數(shù)據(jù) 10000000/101*1

?? ...

??? 第100個節(jié)點存放數(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是原來的數(shù)據(jù)進(jìn)行映射的點，new_node_id則是根據(jù)新的節(jié)點數(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

實驗結(jié)果

4901707?ids?moved,?49.02%
Total?time?69?second

現(xiàn)在加入虛節(jié)點之后進(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é)點的索引值
NEW_NODE_COUNT?=?NODE_COUNT?+?1??
vnodes_to_reassign?=?VNODE_COUNT?/?NEW_NODE_COUNT??#要進(jìn)行重新分配的虛節(jié)點的數(shù)目，一下是只需確定，移動節(jié)點的數(shù)目，先遍歷節(jié)點，確定節(jié)點索引值，
#然后遍歷虛節(jié)點,如果虛節(jié)點指向的實節(jié)點索引值與之前一致，那么該虛節(jié)點的數(shù)據(jù)，則應(yīng)該遷移到new_node_id節(jié)點上去，這里只改變虛節(jié)點和實節(jié)點的對應(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

實驗結(jié)果：

90423?ids?moved,?0.90%
Total?time?34?second