P2P系统,一致性哈希和DHT
数据网格产品经常会使用P2P进行通信，借此机会系统地学习一下P2P网络和其资源搜索策略。
1 P2P网络架构
谈到P2P就涉及到一个概念：Overlay Network(覆盖网络)。所谓覆盖网络是应用层网络，几乎不考虑网络层和物理层，它具体指的就是建立在另一个网络上的网络。例如P2P网络就是覆盖网络，因为它运行在互联网之前，但允许对未知IP主机的访问。通过DHT等算法，可以在事先不知道IP地址的情况下，访问到存储某个文件的结点。
常见的P2P系统主要有Unstructured Network和Structured Network两种架构。
1.1 Unstructured Network
非结构化的P2P网络并不给覆盖网络强加某种特定架构，而是结点间随机形成链接。最流行的P2P网络，像Bittorrent、eMule、Gnutella、Kazaa等都是非结构化的P2P协议。因为缺少结构，所以网络面对频繁的动态添加和删除结点时，依然能够健壮地运行。但也正因为缺少结构，所以当某个结点想要搜索某些数据或文件时，查询必须flood整个网络(详见1.3搜索策略)。
1.2 Structured Network
结构化P2P网络将覆盖网络组织成某种特定的拓扑结构，并且它的协议能够保证：）根据集群和数据规模，散列冲突可能会比较严重(只能通过替换更好的哈希算法来平衡)；2）扩容添加结点或故障删除结点时(k->k±1)，所有数据都要重新映射到新的结点上(通过后面介绍的两种分布式哈希可以解决)。
3 一致性哈希
3.1 构造
将结点和数据映射到同一个线性地址空间，结点负责保存前一结点到本结点之间的数据。
3.2 Lookup过程
首先，位的id)和取模：
Ø Node-id = SHA1(IP/mac)
Ø Key-id = SHA1(key)
Ø id-space mod
4.2 Lookup过程
对于Chord版的DHT实现来说，这种Lookup过程是通过一张叫做Finger表的路由表来完成的，它根据计算数据id指数级增长时对应的各个结点，形成表中的信息：
在没有finger表的情况下，需要不断访问后继结点继续lookup，即O(n)跳才能找到目标结点：
有了finger表，就可以实现O(logN)的高效lookup：
5 算法复杂度对比
除了搜索/路由外，其他几项都是DHT占优：
参考资料
1 Princeton - P2P Systems and Distributed Hash Tables
2 Overlay Network：http://en.wikipedia.org/wiki/Overlay_network
3 Peer-to-Peer：http://en.wikipedia.org/wiki/Peer-to-peer
4 Structured Homogenous P2P Overlay Networks
5 memcached全面剖析--4. memcached的分布式算法
最新文章
- “基础提供程序在Open上失败”
- 利用iis虚拟目录实现文件服务器功能（分布式存储）
- Linux 发行版本及其基于
- 【整理】动态加载Web Services
- 如何将php的错误输出到nginx的error_log中去
- IOS项目集成ShareSDK实现第三方登录、分享、关注等功能。
- JSONP跨域原理和jQuery.getJSON用法
- QTP之对测试用例的自动化过程的分解
- win7禁止自动使用浏览器打开FTP而是用资源管理器
- 【机房系统知识小结点系列】之遍历窗体中的控件，判断Text是否为空？
- 用Verilog实现IIC通讯
- ECMAScript6之let与const关键字
- Java 泛型 泛型的约束与局限性
- ProgressBar、ProgessDialog用法解析
- RxSwift 介绍
- flask 第五章 WebSocket GeventWebsocket 单聊群聊 握手 解密 加密
- DFI LP DK P45 T2RS PLUS BIOS SETTING
- java 字符与ASCII码互转
- P1160 队列安排 luogu洛谷
- mysql Packet for query is too large (2036 > 1024). You can change this value on the server by setting the max_allowed_packet' variable.