DHT在分布式数据库技术中的性能优越

2023-10-28 理论教育版权反馈

【摘要】：DHT虽简单，但性能优越。DHT无需中心服务器，分布式系统中所有的DHT节点是平等的。同时，DHT继承了哈希表的主要特性，如高效定位和搜索元素。这允许DHT灵活扩展到拥有很多节点。DHT由以下两部分组成。这个基本性质使得DHT在节点加入或离开网络时的重组需求变得最小。节点按照DHT的连接策略选择邻居。DHT必须具有以下三个特性。因为DHT具备这三个特性，所以它在一些领域大受青睐。

DHT在分布计算及其应用中扮演着重要角色，特别是在大规模分布式环境里。如前所述，在客户端/服务器（C/S）模式中，服务器负责大多数资源的开发，它们也往往成为瓶颈或系统的弱点。而在分布式系统，尤其是P2P模式中，资源分布在系统的所有节点上，因此，健壮性和性能更优。那么，如何有效管理分布式环境中的资源呢？这样，DHT应运而生。

DHT是一种分布式存储方法。在不需要服务器的情况下，每个客户端负责小范围的路由，并负责存储一小部分数据，从而实现整个DHT网络的寻址和存储功能。例如，比特彗星（BitComet）^[1]允许同时连接DHT网络和Tracker，也就是说，在完全没连上Tracker服务器（也称种子服务器）的情况下，也可以很好地下载，因为它可以在DHT网络中寻找下载同一文件的其他用户。

DHT虽简单，但性能优越。它提供类似哈希表的功能来处理分布式数据。DHT无需中心服务器，分布式系统中所有的DHT节点是平等的。同时，DHT继承了哈希表的主要特性，如高效定位和搜索元素。DHT提供一个全局的、抽象的键空间（一般称为DHT空间），其中所有资源（如数据和DHT节点）都有其唯一的标识（ID）。与哈希表一样，DHT里的任何数据都可表示为一个二元组（K，V），其中，K是数据经哈希函数映射后的键值，V是原始数据。DHT空间里的每个节点也有一个键，称为节点ID。这样，分布式系统里的所有数据和节点都可以一直地映射到DHT空间。可以将DHT空间分割成若干个槽（slot），将DHT中的每个节点维护映射到自己节点槽里。DHT有两个基本操作：put（）函数将数据放入DHT空间，键值为K；get（）函数通过给定的键值K获取原始数据。

DHT网络由一个逻辑标识符哈希键空间组成，负责从端点到资源的映射。每个端点会维护邻居状态，通过基于标识空间的覆盖网络记录每个可用应用级的消息路由。这里，插入网络和从网络检索的算法是确定的，即给定一个键，这个键的资源就驻留在确定的端点上。

本质上，DHT提供类似哈希表的查表服务，即在DHT里存储“名字”（name）和对应的“值”（value）偶对，如果用户给定名字（name）的键，就可以检索到先前存储的值。通常，DHT里的键通过使用哈希算法生成，这类哈希算法如安全散列算法（SHA）。

DHT方法的优点是：节点可以通过树状结构来组织，其搜索算法的复杂性是O（log N）。这允许DHT灵活扩展到拥有很多节点。DHT方法的缺点是：用户需要确切知道名字的键（name key），以便检索所需的值，直接靠关键词查询是不行的，但可以通过在DHT技术上构建应用来满足语义搜索的需求；另外，实现覆盖（网络）^[2]一般比非结构化要付出更多的努力，以保证断接或离开时能维护节点间的一致性。

DHT由以下两部分组成。

●一种键空间分割模式，负责在参与节点间划分键空间。

●连接节点的覆盖网络，以此允许节点在键空间对任意给定键定位其“所有者”（owner），让花费的跳数目（hops）尽可能小。这个覆盖网络也负责在网络里注入冗余，使得在定位给定键时有多条路径可用。这样，当节点出现故障时仍可定位。

DHT在键分割模式里会使用某个一致哈希的变形（variant of consistent hashing）技术。这种技术使用一个距离函数，能测量从一个键到另一个键的抽象距离，与任何物理参数（如地理距离或网络延时）无关。典型情况是，为每个节点指定一个标识符哈希键（基于某些端点性质的哈希值，如网络地址、时刻等）。在一致哈希算法中，节点的移出和加入会改变相邻节点（由邻居ID）“拥有”的键集（合）。这个基本性质使得DHT在节点加入或离开网络时的重组需求变得最小。(www.chuimin.cn)

覆盖网络使用这些性质，在邻居节点路由表里维护通达邻居节点的链接的集合。节点按照DHT的连接策略选择邻居。但对任何键来说，一个节点或者拥有这个键，或者指针指向离这个键近的节点。因此，可以使用贪心算法检索键，通过将请求传递给ID最接近于所请求的键的邻居来实现。如果不能再进一步找到这类邻居，那么目前节点就是最接近的节点。

为了维护覆盖网络，需对算法进行调节，于是DHT定义了两个键参数。一个参数是可以定义任意路由的跳转数目（路由路径最小或跳数最少）；另一个参数是任何节点的最大邻居数，即最大的节点度，用于减少覆盖网络的维护开销。通常二者会产生矛盾，即路由最短需要节点度大，因此往往选择折中。通常节点度选为O（log N），路由长度也为O（log N）。

DHT可以有效组织分布式资源，让节点可以有效地获得资源，定位资源的时间复杂度为O（1）。与传统的哈希表相比，DHT处理系统的分布性和动态性强得多，因为DHT可以灵活定制槽的数目和槽的域范围。

DHT必须具有以下三个特性。

●高效：DHT继承哈希表的优秀特性，如高效定位数据在DHT空间的存储位置，无需知悉全局信息。

●分散（decentralization）：DHT是分散部署的，可以避免热点问题和实现好的负载均衡。

●可伸缩性（scalability）：DHT可以应用于分布式系统，规模大小可变，从成百上千到几百万的节点。

DHT在分布式数据库技术中的性能优越

相关推荐