一个人的工作量太大了【精品文档】

一个人的工作量太大了【精品文档】 1.dht 优点: 一个人的工作量太大了，按一定的把他的工作分配很多人一起做。 分配方法:就是dht的几种算法。 2.hash :查找速度更快! Hash表的构造:除余法:例如H(k)=k mod 10 会有冲突: 解决冲突的方法: 1(链地址法: 2(开放地址法:Hi(k),(H(k)，di)mod m (1)di=1,2,3,…(线性探测再散列) (2) di=1^2,(-1)^2,2^2,(-2)^2…(二次探测再散列) (3) di=伪随机序列(伪随机再散列) 例:keys为(32，13，49，55，22，38，21)，m为7 (1) 线型探测在散列: 32 MOD 7 = 4 存入地址空间4; 13 MOD 7 =6 存入地址空间6; 49 MOD 7 = 0 存入地址空间0; 55 MOD 7 = 6 发生冲突，处理冲突如下: 下一个存储地址为(6，1) MOD 7 = 0 仍然冲突 在下一个存储地址为(6，2) MOD 7 = 1 不冲突，存入地址空间1; 22 MOD 7 = 1 发生冲突，处理冲突如下: 下一个存储地址为(1，1)MOD 7 = 2 不冲突，存入地址空间2; 38 MOD 7 =3 存入地址空间 3; 21 MOD 7 = 0 冲突， (0，1)MOD 7 = 1,冲突 (0，2)MOD 7 =2 冲突 (0，3)MOD 7 =3 冲突 (0，4)MOD 7 =4 冲突 (0，5)MOD 7 =5 不冲突，存入地址空间5 已经建立HASH表，用关键字K来查询K的数据元素: 根据K值求它的哈希地址，即H(k)，然后根据H(k)找出哈希地址如果为空，则 查找失败，若不为空，将K与该单元的关键字相比较，若两者相等，则查找成功，若 不相等，则按照构造hash表的方法，继续在“下一个存储地址”中查找。 3.dht的一般算法:环内按着succesor来查找。缺点:跳数太多(N/2，其中N为在环内 节点的数量)如果节点失败，就不能往下走。 Key的加入: 找到Key(看作ID)的Successor算法(就是找到负责Key的节点): def findNode(start, key): current=start while distance(current.id, key) > \ distance(current.next.id, key): current=current.next , while完成的功能是:current与key 的差值最小。 return current def distance(a, b): if a==b: return 0 elif a distance(next.id, key): current=next next=findFinger(current, key),如此反复，直到找到负责key7 的节点为节点0 return current 在节点node的finger表中查找与key值最接近的节点 def findFinger(node, key): current=node for x in range(k):,从finger表中finger[1]到finger[k]查找。 If distance(current.id, key) > distance(node.finger[x].id, key): current=node.finger[x],如果找到与key值最接近的id的 节点(即key的succesor) return current (2)节点加入和退出:(值得注意的是节点的加入和退出与key的加入和退出是独立的) 加入算法: 节点X利用任意一个节点A加入环中: 1(X得到一个随机分配的ID; 2(通过A查找X中finger表中的finger[1].start到finger[k].start的successor 3(更新其他节点的finger表 退出算法: 假设退出节点X: 1( 找到X的predecessor，把负责的keys交给predecessor 找出predecessor的算法如下: def find_predessor(id,current) n=current; while(id!?(n ,n. successor ] )% 找到id 值落在n和它的successor之间的节点n. n = n .closest _ preceding _finger(id , n);%则节点n就是id的predecessor return n; def closet _ preceding _finger(id , node) for i =m downto 1 if(node < finger[i].node < id) return finger[i].node; return n; 2( Predecessor将它的successor设置为X的successor。 3( JOIN和LEAVE的代码类似于在一个普通链表上插入或删除元素，增加了在加入/离开节点及其邻居间 迁移数据。 (3)节点的更新算法: def update(node): for x in range(k):, 表中一行一行更新，从finger[1]从finger[k] oldEntry=node.finger[x] node.finger[x]=findNode(oldEntry,(node.id+(2**x)) % (2**k)) (4)CHARD缺点:Chord中的finger table link是单向的 改进:利用XOR来得到节点的距离(distance metric)，算法如下: def distance(a, b): return a^b # In Python, this means a XOR b, # not a to the power of b. XOR得到的distance metric是蛮好的，因为它具有对称性。即distance (A,B)==distance(B,A), 如果A在B的finger table中，B必然也在A的finger table中。这意味着节点可以通过记录 那些查询本节点的节点的地址来刷新自己的finger table，能大大降低用于节点刷新的流量。 5.pastry:把节点数减低(log2N) 节点加入操作的复杂度为O(log2bN) 下周的计划:充分理解pastry算法:写出相关的算法: