DHT
云计算课程补充
P2P
- p2p是解决单点故障的方式，一台机器挂掉了，风险被分散了
- p2p集群看成哈希表
三种拓扑结构P2P
集中式拓扑
- 一个中央服务器担任目录管理员，会存在单点故障的问题
分布式非结构化拓扑模式
- 每个服务器连接到一些节点，都可以作为服务提供商，没有规则的在网络上搜索，设定一个阈值，几跳后就找不到
分布式结构化拓扑模式 DHT
- 一种结构化的方式对于p2p的节点进行管理
- 每个节点存储特定信息或者特定信息的索引，节点获得要查询的信息后，进行一个有目的搜索
- 通过任意一台设备能访问到我想要访问的信息
DHT原理简介
不同资源不同映射，均匀的分布在不同节点上
一致性Hash
一致性 Hash 算法也是使用取模的思想，只是，刚才描述的取模法是对节点数量进行取模，而一致性Hash算法是对 2^32 取模
简介
- 将Cache和资源视为同等概念，都需要Hash，Hash和Cache数量无关
- 单调性：尽可能小的改变已经存在的key映射关系，如果增加或者减少了节点的个数，只是相关区间之内的数据记录需要重新hash，而不是全局的数据
- 平衡性：Hash的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用
实现
- 一致性Hash将整个空间组织成一个虚拟的圆环，哈希函数的值空间就分布在0-2的32次方-1上
- 每次将节点进行一次Hash，按照一定的规则，比如按照ip地址的hash，让节点落在哈希环上面
- 通过数据key的hash值如果命中了机器节点就直接落在这个机器上，否则顺时针直到碰到第一个机器
数据倾斜问题
- 服务节点太少的时候，容易产生因为节点在圆环上分布不均匀而导致的大部分数据集中分布在某一台服务器上的问题
- 一致性hash算法引入了虚拟节点的机制，每个机器节点或进行多次hash，那么每个机器节点在hash环上面会存在多个虚拟节点的存在，数据定位算法不变，只是多了一步从虚拟节点到实际节点的映射
Chord
一致性哈希
提出
- 沿用一致性hash的hash环
- 但是一个环上使用的是SHA-1作为hash函数，总共会有0-2^160-1次方个位置可以给服务器节点存放，node就会很稀疏的分布在环上面
- 任何查找只要沿着chord环一圈结果肯定可以找到（每个节点知道了自己下一个节点的NID信息，查询信息的时候，不断比较key计算出来的KID信息，然后进行转发），这样的时间复杂度是O(N)， 但是对于一个上百万节点并且经常有节点加入退出 的p2p网络来说，是不能忍受的，所以选用了chord
- 用空间换时间
算法流程
- 每个节点维护一个表，长度是m，m就是位数，chord中是160，该表的第i项就存放节点n的第(n+2) mod 2个successor(1<=i<=m)，之所以要mod是为了形成环结构，让更大的节点的后继节点为前面的节点。
- 给定一个key，计算出KID，对于节点n，在看看他的直接后继节点有没有这个资源（NID<KID<NIDsuccessor）
- 如果没有就从finger表的最远处开始查找，然后往回找，直到找到距离KID最近的那个NID，并且满足NID小于KID，然后把转发请求发送到这个服务器上
冗余性
- 如果finger表中的项所代表的successor不存在，那么就会距离这个successor指向最近的那个存在的节点
节点加入
通过在每个节点的后台周期性的进行stabilize询问后继节点的前序节点是不是自己来更新后继节点以及路由表中的项
- join( n 0) ： n 加入一个Chord环，已知其中有一个节点n0.，新加入一个节点p会通知自己的successor把他的predecessor设置成p
- stabilize(): n 查询其后继节点的前序节点P来决定P是否应该是 n 的后续节点，也就是说当P不是n本身时，说明P是新加入的，此时将 n 的后继节点设置为P。
- notify( n0): n 通知 n0它的存在，若此时 n0没有前序节点或， n 比 n0现有的前序节点更加靠近 n0，则 n0将 n设置为前序节点
- fix_fingers(): 修改路由表。
节点退出
- 最重要的是当节点N失效时，所有指针表中包括N节点的都必须把N节点换成N的后继 节点
- 每一个Chord节点都维护一个长度为T的最近后继节点列表，当N节点发现其直接后继 节点失效了，立即使用下一个正常的最近后继节点替换已经失效的后继节点
Pastry
没咋听懂
大致流程
32个十六进制的数字的字符串
我的是x12345678…..
- 行数越大，距离我越近
- 每i行的节点（i，j）的第i+1的位需要和列号j相同，最左边的i位需要与N的左边i位相同
- 第0行表示 跟我的ID没有一位重合的节点的信息
- 第1行表示 跟我的前一个位置i相同的节点 第一位是1的节点
- 第2行表示 跟我的前二个位置i相同的节点 第二位以及之前需要是1 2
参考资料
https://www.jianshu.com/p/735a3d4789fc
https://blog.csdn.net/chen77716/article/details/6059575