分布式时空数据库去中心化负载均衡方法

胡 珂，李成名，沈建明

(1.中国测绘科学研究院，北京 100036; 2.江苏省地质测绘院，江苏 南京 211100)

近年来，云计算技术的兴起[1-3]，解决了大数据的存储及处理问题[4]，特别是对于结构化及半结构化[5]数据，分布式数据库成为一种有效、经济、安全的存储方式[6]，并且提供近乎实时的查询效率[7-8]，满足了线上系统的应用需要。但是分布式存储系统中的数据量非常庞大，节点存储的信息也很多[9-10]，当集群中的某些节点利用率不高时，就会影响存储系统的性能，浪费存储空间。另外，在多用户高并发访问节点时，用户不了解每个节点的负载情况会导致节点的负载分配不均[11]。以上问题严重影响了系统整体的性能和服务效率，因此提出一种负载均衡方法来解决上述问题显得尤为重要。

在分布式系统中，常用的负载均衡策略[12]分为中心化控制策略和去中心化控制策略。其中，中心化的控制策略采用单一负载均衡器来收集系统负载情况，但是对于海量时空数据，负载均衡器承载的任务量大，易出现宕机问题；去中心化控制策略则是由每个服务器都参与到收集负载信息和分配客户请求中，这种模式没有中心节点，自组织能力强，可扩展性高，更适合存储时空数据。因此去中心化的存储策略[13]成为存储时空数据的主流。

针对以上海量时空数据存储问题及高并发读写能力问题，本文首次使用在分布式时空数据库去中心化动态负载均衡下的环状模型作为解决方案。该方案采用一致性哈希算法建立环状模型，可以有效地保证集群的稳定性与可靠性，实现整体的负载均衡。

1 一致性哈希算法

1.1 算法简介

一致性哈希算法(consistent hash)由麻省理工学院David Karger等在1997年提出[17]，其设计初衷是应对互联网中的热点问题，解决了简单哈希算法在分布式哈希表(distributed hash table,DHT)中存在的动态伸缩等问题，对简单的哈希算法进行了修正。由于分布式环境是不断变化的，哈希算法相比于其他算法的优势在于平衡性、单调性和分散性上，具体如下：

(1) 平衡性：每个节点都等量分配了hash结果。

(2) 单调性：无论是增加还是删除节点，系统依旧可以继续运作。

(3) 分散性：分布式集群里每个节点都存储了数据的一部分(节点自身可备份)，而不需要冗余存储。

1.2 算法原理

一致性哈希算法[18]属于传统的哈希算法，特点是无论节点的增删,都能以最小的影响处理好已经存在的节点与增删节点的映射关系[19],尽可能满足单调性的需求。

一致性哈希算法首先将哈希空间进行映射,如同一个圆圈一般，哈希空间在0～232-1中取值。然后按顺时针方向排列。0和232-1在零点方向重合，如图1所示。

这种定制改装赋予了越野车一种硬朗的都市感，我们联系了当地的影像资料馆，资料馆建议把Dean Lane滑板公园作为外景地。那里充满涂鸦的环境十分完美，所以我们预订了两个小时的包场，在当地滑板运动爱好者到达之前的清晨进行拍摄。

图1 环形哈希空间

接着将服务器节点使用统一算法计算出对应的hash值,顺时针映射到hash环上,然后根据hash值的位置沿圆环顺时针方向映射到环上。每增加一台新的服务器时,只有新增服务器的逆时针方向上碰到的第一台服务器的数据受到影响，其他均不会受到影响。由于节点的增删带来的重定位数据很小，因此系统的运行效率和容错率会高很多。

1.3 DHT算法原理

DHT属于一种网络中很流行的分布式数据保存算法，其通过分布式哈希算法解决数据的相关存储问题。DHT的核心思想是把需要存储的资源相关属性通过哈希运算,得到相关键值(hash key),需要存储的资源信息根据键值进行存储。具体来讲,大致有以下步骤：

(1) 将需要存储的资源相关属性通过哈希运算,得到键值，即可将所有资源的信息归结在同一个数值区域内。

(2) 整个网络中每一个节点只管理某一个特定数值区域。如A节点管理键值2000～2999的资源，B节点管理3000～3999的资源。通过该方式,就有规律性地将所有资源存储到整个网络中每一个节点上面。

2 分布式时空数据去中心化的负载均衡方法

整体路线分为两个部分：服务器和负载均衡。其中，服务器部分经过多项比较选择了分布式集群架构PostgreSQL-XL。它包括了以下3个部分:全局事务管理器(GTM)控制全局事物分配，确保事务一致性；协调器(coordinator)管理用户会话，并与GTM和数据节点进行交互，将操作指令发送到各数据节点；数据节点(data node)负责实际存储。

负载均衡部分通过Chord算法来维护和管理网络结构，通过Gossip协议(一种在P2P网络分布式环境中广播自己信息及获取其他节点信息的协议)来广播节点的负载信息到全局。Chord是一致性哈希的一种实现，是构建结构化P2P的分布式哈希表系统中比较重要的一个算法。一致性哈希保证了整体架构，将服务器的节点通过hash之后平均分布到整个哈希环上，并且使得节点与关键字均生成了m位的标识符。节点的后继节点successor(k)来保存每个关键字，其中后继节点是指从k节点沿顺时针方向最近的一个节点。

另外，每个节点都维护了一张最多m个表项的Finger-Table表，该表提供了所有节点对整个网络的“全局视图”，由于本身是用来做类二分的节点查找的，因此可以把它当作一个路由表，用户通过访问一个节点就能迅速找到自己落在环上的位置，同时Gossip通信也通过路由表来传递各节点信息。负载均衡指标作为各个节点的信息广播到全局，经过比较筛选负载低的节点进行存储。最后，通过不断地比较负载指标从而实现负载均衡。

增加新的节点n时分为以下3步：

(1) 初始化节点n的Finger-Table表，同时将已知的某节点为它查找Finger-Table表中各个表项。

(2) 更新原有其他节点的Finger-Table表，其他节点使用更新函数来更新自身的Finger-Table表。

(3) 从后继节点把关键字传递到节点n。

如果节点n发生故障，根据Chord环的特性，由n的后继节点n+1替换故障的n节点，并将指针指向n+1。同时为了不影响系统查询，每个节点都维护一张r个最近后继节点的路由表，这样使得集群稳定性大大提高。设计路线如图2所示。

图2 集群设计方案

3 对比试验

本文在PostgreSQL-XL分布式集群环境下，利用上述方法搭建了基于Chord算法的负载均衡方法，网络带宽环境是100 MB的局域网。整个分布式时空数据系统采用4层结构，包括客户端、通信层、协调器层、分布式时空数据库层，如图3所示。

集群搭建在5台相同配置的服务器(CPU 8核2.4 GHz、16 GB内存、100 MB以太网卡)下进行测试，使用1台Windows 7计算机(CPU 8核3.6 GHz、4 GB内存、100 MB以太网卡)远程搭建PostgreSQL-XL服务器集群。其中，1台服务器作为GTM(global transaction monitor)来确保集群范围内的事务一致性，另外4台服务器配置协调器(coordinator)和数据节点(data node)。Chord算法及负载指标所在的通信层通过Java实现。

图3 系统结构

由于集群系统节点的异构性，服务器的不同硬件参数对性能的影响程度也有不同[20]。因此，参考文献[20]，本文采用了5种硬件参数加权求和来评价节点的性能C(Ti)，分别为服务器的网络带宽使用率C(Bi)、存储空间的使用率C(Si)、磁盘I/O的访问率C(IOi)、CPU利用率C(Ci)和内存利用率C(Mi)

(1)

启动负载均衡服务以后，通过Jmeter工具进行性能测试。测试数据是20世纪70年代1∶100万栅格世界地图数据集，在PostGIS数据库中以blob字段进行分块存储。在客户端用Jmeter向PostgreSQL-XL集群发送地图服务请求，然后从最初的250个虚拟并发用户依次增加到3000用户数并且设置用户的迭代次数为5次，总共进行两次测试。第一次使用中心化负载均衡模型(以HaProxy为例)与环状模型进行测试，在2000并发用户数时删除一个节点继续测试，结果如图4所示。

图4 系统响应时间对比

如图4所示，虚拟的并发用户越多，两个模型的响应时间也越长。任务数量较少时时间相当，但是随着并发用户数越来越多，环状模型的性能更好，与HaProxy相比提升了6.2%；在2000用户数关闭一个节点时，HaProxy停止运行，环状模型重新计算导致响应时间较长，之后又稳定下来，保证了集群的稳定性与有效性。

第二次在链状模型、网状模型、链网模型及本文环状模型4种状态下分别进行测试，所获得的系统性能对比情况如图5所示。

图5 系统响应时间对比

从图5可以看出，虚拟的并发用户个数不多的情况下4种方式的相应时间相差不多，但是用户个数超过1000之后差距开始逐渐显现出来，节点的负载加重对集群性能的影响也越来越大。通过对4种负载均衡方式的比较，链状模型与网状模型的响应时间变长，链网模型与环状模型系统性能较为稳定，环状模型比链状模型性能提升了20%，比网状模型提升了17%，比链网模型提升了3%，算法的负载均衡效果较为显著。由于环状模型的灵活性更强，在后期的效果略好于链网模型。

4 结 语

与传统的去中心化动态负载均衡算法相比，在多用户高并发的情况下存储时空大数据，环状模型的性能有明显的提升，在任务数增大的情况下尤为显著。将这种负载均衡方法应用在存储时空数据上具有一定的参考价值。但是本文没有考虑到路由效率问题，这是进一步研究中需要解决的问题。