DHT算法
2017-2019年计算机视觉顶会文章收录 AAAI2017-2019 CVPR2017-2019 ECCV2018 ICCV2017-2019 ICLR2017-2019 NIPS2017-2019
DHT 算法：
在不需要服务器的情况下，每个客户端负责一个小范围的路由，并负责存储一小部分数据，从而实现整个DHT网络的寻址和存储。（百度百科）
结构式拓扑：
1.无中央服务器，各结点的功能和地位都是相同。
2.结点间的逻辑拓扑关系是按照某种决定性的算法严格控制的。资源的放置按照该算法决定性地放置在特定的结点上。资源定位信息与P2P拓扑是紧耦合的。资源的查询也是按照决定性的算法进行。
3.适于对可用性要求高、需服务质量保证的系统，如分布式存储系统Oceanstore，CFS，PAST。典型例子：分布哈希表（Distributed Hash Table,DHT）方法。
分布哈希表DHT的特点：
数据(key)由大量分布自组织的结点来协作存储，两个基本操作： Insert(key, value)，Lookup (key)，功能上非常像一个hash表：Hash（key）－>node。引入哈希函数以将要搜索的对象映射到唯一标识符：例如，hash（“Hey Jude”）→8045
在网络中的所有节点之间分配散列函数的范围，每个节点都包含标识符空间的一部分，每个节点必须“了解”每个对象的至少一个副本，该对象在其范围内（当存在时）。
分布哈希表(DHT)方法：
1.以分布式存储为背景解释DHT方法：海量数据文件由大量peer结点来协作存储，peer结点通过DHT方法来组织。
2.每个Peer都有唯一逻辑地址PeerID：结点间根据PeerID，按照DHT拓扑构造算法形成P2P网络拓扑；每个结点上都有一个“路由表”，保存了一些邻居结点的信息。
3.每个Peer负责存储一部分文件：各数据文件（根据其关键字key）有唯一的逻辑地址GUID；根据资源属性值ID，按照一定的映射关系将其放置到特定的结点上；Peer加入或退出时，相关Peer重新划分所负责的文件
4.文件的发布与定位：文件发布和查找过程都类似于IP路由过程；根据peer结点的“路由表”转发数据的定位消息。
DHT的数据发布：两种选择
1.节点可以缓存其范围内哈希值的每个（现有）对象
2.基于指针：(间接级别)节点缓存指向对象位置的指针。
DHT 数据查询/路由：
1.对于每个对象，其范围覆盖该对象的节点必须通过“短”路径到达。可以通过查询器节点（假设可以任意选择）。可以通过由具有对象副本的节点（当使用基于指针的方法时）。
2.不同的方法（CAN，Chord，Pastry，Tapestry）仅在路由方法上有根本的不同：任何“好”的随机散列函数就足够了。
DHT overlay的基本功能：构建拓扑、拓扑维护：节点动态加入退出、资源查询：分布式查询
DHT overlay的评价指标：节点度数，路由路径/网络直径，负载均衡，稳定性….
DHT 方法的挑战：
1.每个节点的邻居应该随覆盖参与的增长而扩展，例如，时间复杂度不应该是O(N)
2.DHT机制应该是完全分布式的（没有集中点可以阻塞吞吐量，或者可以作为单点故障）
3.DHT机制应该优雅地处理加入/离开叠加层的节点。a.需要在现有节点上重新划分范围空间b.需要重新组织邻居集c.需要引导机制将新节点连接到现有的DHT基础架构.
从下列角度(包括上面说的挑战)考虑为什么DHT算法实现起来很困难：DHT采取权力下放机制：没有中央权威服务器。可扩展：低网络流量开销。高效：快速查找项目（延迟）。动态：节点发生故障，新节点加入。通用：灵活命名
设计DHT算法要考虑的问题：
1.高性能DHT Overlay拓扑：拓扑构建、拓扑维护；结点度数与P2P网络直径的折衷：给定结点度数，如何最小化查询开销。
2.DHT逻辑拓扑与物理IP网络拓扑的匹配，P2P overlay网络中相邻两点，在物理网络中可能相距甚远。
3.DHT网络的稳定性负载平衡，各Peer间存储负载、链路负载的均衡。
3.丰富的搜索能力等，DHT方法通常只支持基于关键字的精确匹配，如何支持模糊匹配、区间匹配等。