作者简介

运小军百度高级研发工程师

负责百度运维部大规模日志处理、海量事件数据存储相关设计研发工作，在分布式系统架构、大数据存储计算、高性能网络服务和即时通讯服务有广泛实践经验。

干货概览

本文主要介绍百度运维部监控架构团队在处理大规模日志计算任务时，为保证任务分配均匀性和稳定性，对原始一致性哈希算法进行改进。新算法在保持原始一致性哈希算法稳定性的同时，通过设置不均衡因子来控制分配的不均匀范围，达到负载分配均匀性与稳定性有效兼容。

一

业务场景

分布式系统中我们经常会面对如下业务场景：

计算系统每分钟有大量的定时任务需要及时调度并按时完成，单机在处理能力和时效性上都无法满足要求，需要将任务分配到大量Work节点上进行并行计算，我们如何均匀分配这些任务，并且在任务增减，Work节点退出/加入(伸缩能力)时保持任务分配的稳定性(不会引起大量任务迁移)。

分布式存储系统，海量数据被分片存储，那么如何让每个Data节点上分片更加均匀，并且在Data节点退出/加入时保持数据分片的稳定性。

高并发Web系统中，架构上几乎都是一个或多个反向代理服务器(如Nginx)来做七层负载均衡，后端使用应用服务器集群(如Tomcat)提供服务，这种架构具备水平伸缩能力，那么反向代理如何均匀分配请求，并且尽量保证请求Session粘性。

二

问题分析

上述问题可以抽象为对分配算法如下几个方面的要求：

公平性：即算法的结果要尽可能地公平，不能造成分配不均问题，这点在分布式系统中尤其重要，公平性就是要尽可能避免由于负载过重/过轻导致系统出现慢节点/饥饿节点影响系统整体性能和资源利用率。

稳定性：分布式系统中，集群节点维护、故障、宕机、重启、扩缩容是非常常见的，稳定性就是要保证计算任务、数据、请求在节点加入/退出时尽可能保持稳定，不引起大量计算任务重分配、数据迁移、请求转移，这对系统整体可靠性、稳定性、高性能至关重要。

可行性：算法在工程实践上一定是可行的，具体体现在这两个方面：时间复杂度、空间复杂度，时间复杂度要求一定要快，满足业务场景对响应时间的要求，空间复杂度要求占用资源少，满足业务在资源投入和收益上的平衡。

三

常见算法

面对这些问题我们有很多常见处理方法，例如轮询(Round-Robin)、取模哈希、一致性哈希、按ID范围分段、自定义分段策略，下面我们选择几种常见分配算法，分析它们在公平性，稳定性及可用性方面的能力：

从上面表格对比可知这几种常见算法都无法兼具三种特性，那么有没有一个算法，能同时具备公平性、稳定性以及可行性？接下来介绍的这个算法能在保持原始一致性哈希稳定性的同时还具备可控的均匀性，已经实际应用于我们的分布式近线计算系统中用于分配定时计算任务，目前来看效果还不错。

四

有界负载一致性哈希

有界负载一致性哈希( Bounded-Load Consistent Hash)算法是对原始一致性哈希算法的改进，相对于原始一致性哈希算法的不均匀问题，新算法能通过设置一个不均衡因子，来控制整个分配的不均衡范围。

算法描述

1. 假设计算节点数为n，任务数为m，则每个计算节点的平均任务数t=m/n(取上界是为了保证t*n >= m，保证所有任务都能被分配执行)；

2. 设置不均衡因子c(取值范围为1 < c < ∞)用于控制最大不均匀范围，则每个节点分配的最大任务数为c*t；

3. 使用一致性哈希算法为任务寻找计算节点，当所选节点已有任务数大于tc时，顺序寻找下一个已有任务数不大于tc的节点，直到找到并将任务分配给该节点；

4. 重复步骤3直到所有任务分配完成；

不均衡因子c越接近1整个分配越均衡(整个分配过程耗时会变长)，跟轮询算法效果一样了，c无穷大时跟原始一致性哈希效果一样了。

实现

下面通过Java伪代码对该算法进行实现：

1. public String getTargeNode ( String key ) {

2. // imbalanceFactor为不均衡因子，取值范围为1 < imbalanceFactor < ∞

3. // 单节点最大分配任务数

4. maxAssignedSize = ( totalOfSlice / totalOfNode )* imbalanceFactor ;

5. // nodes中key是依据node名字产生的hash值，value是node的名字

6. SortedMap tail = nodes . tailMap ( hash ( key ));

7. long indexKey ;

8. if ( tail . isEmpty ()) {

9. indexKey = nodes . firstKey ();

10. } else {

11. indexKey = tail . firstKey ();

12. }

13. String targetNode = nodes . get ( indexKey );

14. //getTask获取该节点已分配任务数

15. if ( getTask ( targetNode ) > maxAssignedSize ) {

16. // 该节点超过最大任务数，继续顺序寻找下一个节点.

17. do {

18. SortedMap tailMap = nodes . tailMap ( indexKey , false );

19. if ( tailMap . isEmpty ()) {

20. indexKey = nodes . firstKey ();

21. } else {

22. indexKey = tailMap . firstKey ();

23. }

24. targetNode = tailMap . get ( indexKey );

25. } while ( getTask ( targetNode ) > maxAssignedSize );

26. }

27. return targetNode ;

28. }

因为maxAssignedSize*totalOfNode>=totalOfSlice，所以上面的算法不会导致死循环，每次分配必然有一个计算节点能接受这个任务；最终结果就是每个节点分配的任务数都不会超过maxAssignedSize，不均匀问题通过imbalanceFactor参数来控制；当计算节点退出时，其上面的任务迁移也只限于跟它相邻的一个或多个节点，并不会导致大范围重分配。

效果

下面通过对比近线计算分配算法分别选择轮询、一致性哈希、有界负载一致性哈希时的业务指标，从分配均衡性，计算节点加入/退出的稳定性两个方面来衡量这三种算法的效果：

图1 单个计算节点分配任务数(轮询、一致性哈希、有界负载一致性哈希(c=1.1))

图2 节点加入/退出时迁移任务数(轮询、一致性哈希、有界负载一致性哈希(c=1.1))

很明显可以看到，轮询在任务分配上非常均匀，但是当计算节点变动时，导致大量任务重分配，而一致性哈希解决了任务大量重分配问题，但任务分配不均匀而且无法控制这种均匀性，而有界一致性哈希在 任务分配均匀性 和 重分配 都表现非常好，通过不均衡因子来限制不均匀范围，本身一致性哈希又有效避免了大量任务重分配。

总结

分布式近线计算系统的任务分配算法在业务需求驱动下，经历了从最初的均匀轮询(防止分配不均导致慢节点)，到使用一致性哈希(防止任务因为计算节点加入/退出导致重分配，为了达到尽可能均匀优化虚拟节点个数)，再到有界负载一致性哈希通过参数控制解决原始一致性哈希 分布不均匀问题 ，每次分配算法改进都极大提高了 系统整体稳定性 ；有界负载一致性哈希算法具有通用性，可以有效解决任务分配，数据分片，请求分发等业务场景中分配均匀性与稳定性问题。