01--是时候让我们谈谈一致性hash了-LMLPHP

---------------------

假如你有图中三个盒子,我们有代号为 1,4,5,12 这四样东西 那根据代号作为主键,将东西放到盒子了,该如何放置?

我们可以对代号取模 1 mod 3 = 1   4 mod 3 = 1    5 mod 3 = 2  12mod 3 = 0

这样的话 大家就可以分配好到对应到盒子里

  1 #!/usr/bin/env python
2
3 box0 = []
4 box1 = []
5 box2 = []
6 box_home = {
7 '0':[],
8 '1':[],
9 '2':[],
10 }
11 res = [1,4,5,12]
12
13 for i in res:
14 key = i % 3
15 if key == 0:
16 box_home[str(key)].append(i)
17 elif key == 1:
18 box_home[str(key)].append(i)
19 elif key == 2:
20 box_home[str(key)].append(i)
21
22 for k,v in box_home.items():
23 print k,v
~

  

代码如上

01--是时候让我们谈谈一致性hash了-LMLPHP

-------------------------------------------------------------

但是如果现在加一个盒子 。

就变成这样了

那么现在就要取模为4了 之前箱子里面的东西都要重新计算重新,重新摆放。

这在很多场景是不能够接受的,比如负载均衡,我不能因为重新加了一个节点,让所有用户的长链接都断开,重新链接。

或许这种还能接受,那么如果是分布式存储呢?

所以这个时候我们不能够这样做。这样子都服务就不是无状态都服务。

这个时候就是一致性hash派上用场的时候了。

我们可以在刚刚分配的时候预留很多空位置。

01--是时候让我们谈谈一致性hash了-LMLPHP

圆形就是是空,矩形就是有箱子的。我们可以在一开始就留很多空白多地方 ,如图上

我们一开始有三个节点,但是我们会分配5个位置,然后有数据就mod6,如果数据分配到到是没有节点到位置

那么我就就把这个数据放到下一个有节点到位置,比如图上我们要分配到是 数据8 那么8mod6 = 2 此时位置2上没有节点。那么将这个数据到下一个有节点到位置

也就是位置3。如果是mod到是最后一个那么就从头开始,也就是说,位置是环形的。

01--是时候让我们谈谈一致性hash了-LMLPHP

如有新的节点加入,那么直接放到空的位置上,然后将之前的分配在这个位置上的数据转移上去即可,这样子就能避免重新分配。

我们可以通过代码模拟分配情况

#!/usr/bin/env python
#coding:utf-8 class Node():
def __init__(self,data,next_node = None,node_type = 'body',is_online=0): self.data = data
self.next_node = next_node
self.is_online = is_online
self.node_type = node_type
self.self_data = []
self.other_data = [] def get_next_node(self):
return self.next_node def set_next_node(self,next_node):
self.next_node = next_node
return True def set_node_status(self,num):
self.is_onlie = num def get_data(self):
return self.data class boxs():
def __init__(self,head=None):
self.head_node = head
self.size = 0
self.ser_node = None def add_None(self,data,num):
if self.head_node == None:
self.head_node =Node(data,is_online=num)
self.scr_node = self.head_node
self.size +=1
else:
new_node = Node(data,is_online=num)
self.scr_node.set_next_node(new_node)
self.scr_node = new_node
self.size +=1 def print_list(self):
curr = self.head_node
while curr :
print '-----------------------'
print curr.data,'--->',curr.node_type,"---->",curr.is_online
print "data:",curr.self_data
print "other_data",curr.other_data if curr.node_type != 'body':
break
else:
curr = curr.get_next_node() def set_ass_node(self,data,num):
new_node = Node(data,node_type='tail',is_online=num)
new_node.type = 'tail'
self.scr_node.set_next_node(new_node)
new_node.set_next_node(self.head_node) def insert_data(self,key,dick_len):
curr = self.head_node
while curr:
if key % dick_len == curr.data:
if curr.is_online == 1:
curr.self_data.append(key)
else:
while 1:
curr = curr.get_next_node()
if curr.is_online == 1:
curr.other_data.append(key)
break break
else:
curr = curr.get_next_node() def set_node_allot(self,key_dict,dick_len):
for key in key_dict:
self.insert_data(key,dick_len) #设置节点种有盒子的节点
online_node = [1,3,5] #实例化链表
mylist = boxs() #添加节点,如果节点数属于online_node的节点 那么就设定他在线
for i in range(7): now_status = 0
if i in online_node:
now_status =1 if i <6:
mylist.add_None(i,now_status)
else: mylist.set_ass_node(6,now_status)
#模拟数据
key_dict = [2,3,5,6,12,22,23,33] #分配数据
mylist.set_node_allot(key_dict,len(key_dict)-1) #打印分配情况
mylist.print_list()

  

05-11 22:26
查看更多