燕郊南城百度海量日志处理——任务调度实践与优化

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

业务场景 

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

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

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

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

问题分析 

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

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

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

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