dht 分布式hash 一致性hash区别

先有一致性hash ：一致性哈希，似乎最早提出是在分布式缓存里面的，让节点震荡的时候，影响最小。不过现在已经应用在分布式存储和p2p系统里面。

dht 是p2p领域的概念，内有三大概念是由keyspace（key 空间）、keyspace partition（key 空间划分）、overlay network（覆盖网）组成。keyspace 很好理解，是所有定长字符串的空间。keyspace partition 方案将keyspace 上不同区域划分到不同的参与节点上。overlay network（覆盖网）将节点连接起来，使得网络中节点通过这个网络可以找到保存指定key 的节点。consistent hashing 对比DHT 的区别是，一致性哈希只覆盖了前两个概念，提供了一种keyspace 的划分方法

DHT只是一个概念，提出了这样一种网络模型。并且说明它是对分布式存储很有好处的。但具体怎么实现，并不是DHT的范畴。

分布式哈希表DHT 是一种去中心化的分布式系统，提供一种类似于哈希表的查询功能。

DHT 的研究最初是因为P2P 系统的兴起，如Napster，Gnutella 和Freenet。

Napster 是最早的P2P 服务的代表作，有一个中心index server 保存资源的index（key），当有节点加入、退出和查询时，与index server 进行交互，获取资源信息，存在单点故障，在遇到法律纠纷时，这个index server 很容就被关闭了。

Gnutella 去中心化得松散布局，当节点发起查询时，通过洪泛（flooding）的方式查询：每个收到查询命令的节点向其所有其他邻居节点发送类似请求。并通过TTL 控制洪泛的区域。

Freenet 首先采用了DHT，每个对象（文件）都关联一个key，具有相似的key 的文件保存在相似的节点上，并通过一个基于key 的启发式的路由进行查询。

DHT 可以认为是由keyspace（key 空间）、keyspace partition（key 空间划分）、overlay network（覆盖网）组成。keyspace 很好理解，是所有定长字符串的空间。keyspace partition 方案将keyspace 上不同区域划分到不同的参与节点上。overlay network（覆盖网）将节点连接起来，使得网络中节点通过这个网络可以找到保存指定key 的节点。consistent hashing 对比DHT 更多的是提供了一种keyspace 的划分方法，各种consistent

hashing 的也用在了DHT 中进行空间划分。为了更好的理解overlay network 的组成，有这么一段话：

Each node maintains a set of links to other nodes, these links forms the overlay network.

【译】每个节点维持到其他节点的链接，这些链接形成了覆盖网。

可以看出overlay network 已经从物理层的网络抽象成逻辑层上链接各个节点、各个节点保存的路由信息以及路由协议的集合。在overlay network 有两个重要参数：邻居节点数/度数（Degree）和跳数/路由长度（Route length）。度数衡量每个节点保存邻居节点信息的多少，度数越大每个节点邻居越多，保存和维持的信息就更多，需要的路由长度就越短。跳数指的是从该节点到保存特定key 的对象的节点的平均路由长度

chord算是最为经典的实现。cassandra中的DHT，基本是chord的简化版。