Presto Router 调度算法详解：五种负载均衡策略的源码级解析与选型指南

大数据数据库后端【免费下载链接】prestoThe official home of the Presto distributed SQL query engine for big data项目地址https://gitcode.com/gh_mirrors/pre/presto点击查看免费下载Presto Router 是 Presto 分布式查询引擎中用于在多个 Presto 集群之间做负载均衡的独立路由模块。本篇文章以官方文档 Router Schedulers 为骨架结合presto-router模块的源码与测试系统讲解RANDOM_CHOICE、ROUND_ROBIN、USER_HASH、WEIGHTED_RANDOM_CHOICE、WEIGHTED_ROUND_ROBIN五种内置调度算法的原理、实现细节、配置方法与适用场景帮助读者在搭建多集群路由环境时做出正确的选型决策。一、为什么需要 Router 调度器在大型数据平台中单个 Presto 集群往往无法承载全部查询负载常见的做法是部署多套 Presto 集群并由 Presto Router 统一对外提供服务。Router 收到查询请求后会根据预定义的「选择器selectors」匹配到某个集群组group再由**调度器scheduler**从该组内的候选集群中选出一个目标集群将查询转发过去。Presto Router 为此提供了多种调度算法用于在不同场景下实现负载均衡。官方文档 Router Schedulers 中明确列出了五种内置算法而从源码看实际可配置的调度类型有六种多出的一种是CUSTOM_PLUGIN_SCHEDULER自定义插件调度器本文也会一并说明。所有调度器都实现自 Presto SPI 中定义的com.facebook.presto.spi.router.Scheduler接口通过getDestination(RouterRequestInfo)方法返回一个目标集群的 URI返回Optional.empty()表示本次无法调度。二、调度器类型枚举与工厂创建调度器类型的定义位于 SchedulerType.javapublic enum SchedulerType { RANDOM_CHOICE, ROUND_ROBIN, USER_HASH, WEIGHTED_RANDOM_CHOICE, WEIGHTED_ROUND_ROBIN, CUSTOM_PLUGIN_SCHEDULER }SchedulerFactory.java 负责根据枚举类型创建对应的调度器实例RANDOM_CHOICE→RandomChoiceSchedulerWEIGHTED_RANDOM_CHOICE→WeightedRandomChoiceSchedulerUSER_HASH→UserHashSchedulerROUND_ROBIN→RoundRobinSchedulerWEIGHTED_ROUND_ROBIN→WeightedRoundRobinSchedulerCUSTOM_PLUGIN_SCHEDULER→ 通过CustomSchedulerManager加载插件调度器若传入无法识别的类型工厂会抛出PrestoException(NOT_SUPPORTED, Unsupported router scheduler type ...)。值得注意的一点是scheduler配置项在 RouterSpec.java 中被定义为OptionalSchedulerType读取时通过schedulerType.orElse(RANDOM_CHOICE)返回默认值因此即使不配置scheduler字段Router 也会默认采用RANDOM_CHOICE策略。这一点与官方部署文档 deployment.rst 中「The default is RANDOM_CHOICE」的描述完全一致。三、五种内置调度算法逐一解析3.1 RANDOM_CHOICE随机选择算法原理从候选集群列表中随机选取一个。官方文档的描述是Randomly selecting a cluster from a list of candidates。源码实现RandomChoiceScheduler.javaprivate static final Random RANDOM new Random(); Override public OptionalURI getDestination(RouterRequestInfo routerRequestInfo) { try { return Optional.of(candidates.get(RANDOM.nextInt(candidates.size()))); } catch (IllegalArgumentException e) { log.warn(e, Error getting destination for user routerRequestInfo.getUser()); return Optional.empty(); } }实现非常直接通过Random.nextInt(candidates.size())生成一个[0, size)区间内的随机下标再从候选列表中取出对应 URI。特点与适用场景无状态不需要记录任何历史选择信息实现最简单从长期统计看各候选集群被选中的概率基本均等测试用例testRandomChoiceScheduler用 10,000 次采样验证了命中比例约为 1:1:1适合候选集群数量固定、性能接近的通用负载均衡场景由于它是默认调度器开箱即用无需任何额外配置。3.2 ROUND_ROBIN顺序轮询算法原理按顺序轮流从候选集群中选择第一轮到cluster1第二轮到cluster2……循环往复。官方文档特别强调因为该算法会维护「当前选中下标」这一状态所以只能在候选集群始终保持一致时使用。源码实现RoundRobinScheduler.javaGuardedBy(this) private final MapString, Integer candidateIndexByGroup new HashMap(); Override public OptionalURI getDestination(RouterRequestInfo routerRequestInfo) { try { return Optional.of(candidates.get(candidateIndexByGroup.compute(candidateGroupName, (key, oldValue) - { if (oldValue null || oldValue 1 candidates.size()) { return 0; } return oldValue 1; }))); } catch (IllegalArgumentException e) { log.warn(e, Error getting destination for user routerRequestInfo.getUser()); return Optional.empty(); } }实现要点使用candidateIndexByGroup以集群组名为 key记录每组当前轮到的下标compute方法在第一次调用时返回 0之后每次调用下标加 1到达列表末尾oldValue 1 candidates.size()时归零实现环形轮询调度结果与请求内容用户、来源无关纯粹按到达顺序分配测试用例testRoundRobinScheduler验证了连续四次调度的目标依次为192.168.0.1 → 192.168.0.2 → 192.168.0.3 → 192.168.0.1。特点与适用场景能够做到严格的「公平」轮流分配比随机选择更容易预期正因为依赖「下标 1」的推进逻辑若候选集群列表在运行期间发生增删例如某个集群失联被过滤下标与列表的对应关系就会错位可能出现跳过或重复选择适用于候选集群集合稳定、且希望流量严格均分的场景。若集群列表可能动态变化应换用无状态或支持重建的调度器。3.3 USER_HASH用户哈希算法原理对用户名做哈希根据哈希值取模选择目标集群从而保证同一用户的查询总是被路由到同一个集群。源码实现UserHashScheduler.javaOverride public OptionalURI getDestination(RouterRequestInfo routerRequestInfo) { try { return Optional.of(candidates.get(routerRequestInfo.getUser().hashCode() % candidates.size())); } catch (ArithmeticException e) { log.warn(e, Error getting destination for user routerRequestInfo.getUser()); return Optional.empty(); } }实现要点直接使用 Java 字符串的hashCode()对候选数量取模得到下标由于同一个用户的hashCode()恒定只要候选列表不变该用户的查询就会稳定落在同一集群上测试用例testUserHashScheduler对test、user、1234三个用户各连续调度三次断言三次结果完全一致。特点与适用场景实现了「用户级会话粘性session stickiness」非常适合需要复用连接、缓存、临时表或希望某个用户始终访问同一集群数据的场景从源码结构看它假设hashCode() % size的结果落在合法下标范围内对候选列表的稳定性同样有一定依赖候选变化会导致同一用户的映射发生漂移若用户数量足够多各集群的负载在统计上也能大致均衡但不保证精确均分。3.4 WEIGHTED_RANDOM_CHOICE加权随机算法原理按照预定义的权重随机选择集群权重越高的集群被选中的概率越大。官方文档表述为Clusters with higher weights have higher opportunity to be selected。源码实现WeightedRandomChoiceScheduler.javaListURI serverList weights.keySet().stream() .map(uri - nCopies(weights.get(uri), uri)) .flatMap(Collection::stream) .collect(toImmutableList()); // If server list is empty (servers got filtered out due to 0 weight) // select the first candidate from candidate list if (serverList.isEmpty() !candidates.isEmpty()) { return Optional.of(candidates.get(0)); } return Optional.of(serverList.get(RANDOM.nextInt(serverList.size())));实现要点采用「按权重复制展开」的思路把每个 URI 按权重值复制nCopies(weight, uri)份再拍平成一个大列表最后用Random.nextInt均匀随机取样例如三台集群权重为{A:1, B:3, C:9}展开后列表为[A, B, B, B, C×9]随机抽取时 C 被选中的概率就是 9/13处理了全零权重的边界情况若所有权重都为 0serverList 为空则回退选择候选列表的第一个集群。测试用例testWeightedRandomChoiceSchedulerZeroWeight专门验证了该行为进入调度前会执行checkArgument(candidates.size() weights.size())要求候选与权重的数量必须匹配。特点与适用场景支持按集群的物理能力CPU、内存、机器数差异分配不同流量比例例如大集群权重给 5、小集群权重给 1无状态候选或权重变化后下一次调度即可生效因为每次调用都重新展开列表测试用例testWeightedRandomChoiceScheduler以权重 1:3:9 采样 100,000 次断言命中比例约为 1:3:9误差 0.5 以内。3.5 WEIGHTED_ROUND_ROBIN加权轮询算法原理按预定义权重顺序轮询选择集群。与ROUND_ROBIN类似该算法同样维护选中下标状态因此候选集群与权重都必须保持一致。源码实现WeightedRoundRobinScheduler.javaif (serverList null || weights.values().stream().mapToInt(Integer::intValue).sum() ! serverList.size()) { this.generateServerList(); } if (!candidateIndexByGroup.containsKey(candidateGroupName)) { candidateIndexByGroup.put(candidateGroupName, 0); } else { serverIndex candidateIndexByGroup.get(candidateGroupName) 1; } if (serverIndex serverList.size()) { serverIndex 0; } candidateIndexByGroup.put(candidateGroupName, serverIndex); // If server list is empty (servers got filtered out due to 0 weight) // select the first candidate from candidate list if (serverList.isEmpty() !candidates.isEmpty()) { return Optional.of(candidates.get(0)); } return Optional.of(serverList.get(serverIndex));实现要点与加权随机相同先把权重展开为带重复项的serverList但只生成一次generateServerList()仅在serverList为空或权重总和变化时重建调度时在serverList上顺序推进下标因此权重为 3 的集群在每一轮循环中会被连续选中 3 次setWeights方法有特殊设计只保留第一次传入的权重源码注释 Only keeps the first givenweightsdue to maintaining the selected index for weighted round-robin这是为了保证下标状态与权重列表的一致性测试用例testWeightedRoundRobinScheduler通过多组权重如 1:10:100、1:5:10、10:20:30验证了「每台服务器被连续访问的次数恰好等于其权重值」。特点与适用场景在轮询的确定性基础上叠加权重能力既公平又可按集群能力分配比例由于依赖展开后的serverList和下标状态运行时修改候选或权重需要重建调度器对象才能生效否则可能出现下标越界或比例错乱适用于集群配置长期固定、需要精确控制流量比例的强管控场景。四、调度器在 Router 中的实际调用链路五种调度算法并不是独立运行的它们统一由 ClusterManager.java 的getDestination(RequestInfo)方法驱动。从源码看一次完整的调度流程如下匹配集群组通过matchGroup(requestInfo)依次执行选择器规则命中第一个匹配的targetGroup若没有任何规则命中返回Optional.empty()本次请求无法路由健康过滤从目标组中过滤出remoteClusterInfos标记为 healthy 的成员得到healthyClusterURIs若没有健康集群则回退使用组定义中的全部成员healthyClusterURIs groupSpec.getMembers()避免因健康检查波动导致流量完全中断注入候选调用config.getScheduler().setCandidates(healthyClusterURIs)将候选列表交给调度器按类型差异化处理加权类WEIGHTED_RANDOM_CHOICE/WEIGHTED_ROUND_ROBIN额外调用setWeights()注入该组对应的权重表轮询类ROUND_ROBIN/WEIGHTED_ROUND_ROBIN额外调用setCandidateGroupName()注入组名用于按组维护轮询下标自定义插件调度器CUSTOM_PLUGIN_SCHEDULER则注入健康的RemoteClusterInfo映射后直接调用其getDestination()执行调度调用getDestination(requestInfo.toRouterRequestInfo())得到最终目标集群 URI。这套流程揭示了两个实践要点其一调度器看到的「候选」始终是健康过滤后的子集因此轮询类算法要求候选稳定否则健康状态抖动会直接破坏其下标一致性其二权重只在加权算法中被注入普通算法配置了weights也不会生效。五、配置方式在 router-config.json 中指定调度器调度器类型通过 Router 的配置文件etc/router-config.json中的scheduler字段指定。以下完整示例取自官方部署文档 deployment.rst{ groups: [ { name: all, members: [http://127.0.0.1:61381, http://127.0.0.1:61382], weights: [1, 5] } ], selectors: [ { targetGroup: all } ], scheduler: RANDOM_CHOICE, predictor: http://127.0.0.1:8000/v1, user-credentials: username:passwordhash }各字段与调度器的关系说明如下字段说明与调度器的关系groups集群组定义。每个组必填name与members集群 URI 列表可选填weights成员权重列表weights仅对加权调度算法生效members即为调度器的候选集selectors选择器规则支持source、user、clientTags、targetGroup匹配决定请求落到哪个组进而决定使用哪个组的候选与权重scheduler调度器类型取值见上文的SchedulerType枚举核心配置项默认值为RANDOM_CHOICE由 RouterSpec.java 的orElse(RANDOM_CHOICE)保证predictor查询资源用量预测服务的 URI可选默认http://127.0.0.1:8000/v1供调度决策参考与内置五种算法无强耦合user-credentialsRouter 与 Presto coordinator 通信时使用的凭据可选与调度算法本身无关配置示例速查纯负载均衡、零配置直接省略scheduler字段使用默认的RANDOM_CHOICE严格轮流分配scheduler: ROUND_ROBIN需保证候选稳定用户级粘性scheduler: USER_HASH按集群能力分配流量scheduler: WEIGHTED_RANDOM_CHOICE或scheduler: WEIGHTED_ROUND_ROBIN并在groups中配置weights: [1, 5]这类比例。部署 Router 的完整步骤etc/node.properties、etc/jvm.config、etc/config.properties、etc/router-config.json的配置以及bin/launcher start/bin/launcher run的启动方式可参考同目录下的 Deploying Presto Router 文档本文不再展开。六、测试验证调度器行为如何被保障presto-router模块提供了针对全部五种调度器的单元测试位于 TestScheduler.java测试使用三台模拟集群192.168.0.1/2/3作为候选testRandomChoiceScheduler执行 10,000 次随机调度统计各集群命中次数断言任意两台之间的命中比接近 1误差 0.1 以内证明随机选择长期均衡testUserHashScheduler对同一用户连续调度三次断言目标完全一致验证用户哈希的粘性testWeightedRandomChoiceScheduler配置权重 1:3:9采样 100,000 次断言命中比例约为 1:3:9误差 0.5 以内验证权重确实影响概率testWeightedRandomChoiceSchedulerZeroWeight全部权重置 0断言回退到第一个候选验证边界保护逻辑testRoundRobinScheduler连续四次调度断言目标依次为 1、2、3、1验证轮询的环形推进testWeightedRoundRobinScheduler使用多组权重1:10:100、1:5:10、10:20:30验证每台集群被连续命中的次数精确等于其权重值。这些测试用例本身就是理解每种算法行为的最直观的「可执行文档」想确认某个调度器在极端输入如全零权重下的表现直接阅读对应测试即可。七、选型总结与使用建议调度器状态加权确定性核心特征推荐场景RANDOM_CHOICE无状态否否实现最简单长期统计均衡默认选项通用负载均衡、候选可动态变化ROUND_ROBIN有状态下标否是严格轮流候选必须稳定集群固定、流量严格均分USER_HASH无状态否是按用户同一用户固定到同一集群用户会话粘性、连接与缓存复用WEIGHTED_RANDOM_CHOICE无状态是否按权重展开后随机支持动态调整集群能力差异大、需要比例分流WEIGHTED_ROUND_ROBIN有状态下标serverList是是加权轮询候选与权重必须稳定集群固定且需要精确比例控制最后给出三点实践建议能无状态就不选有状态。ROUND_ROBIN与WEIGHTED_ROUND_ROBIN依赖内部下标状态一旦候选集群因健康检查波动而增减轮询节奏就会错乱如果集群规模会动态伸缩优先考虑RANDOM_CHOICE或WEIGHTED_RANDOM_CHOICE权重比例先想清楚再配置。加权算法的权重在groups.weights中按members的顺序一一对应务必保证数量一致源码中checkArgument(candidates.size() weights.size())会强制校验且建议使用互质或较小的整数比例便于观察实际分流效果粘性需求用USER_HASH但注意漂移。USER_HASH的稳定性建立在候选列表不变的前提下若集群发生扩缩容同一用户的映射会被重新打散这在需要长期会话的场景如 BI 工具长连接中需要提前评估。如果以上内置算法都无法满足需求Presto Router 还通过CUSTOM_PLUGIN_SCHEDULER提供了自定义调度器扩展点见 SchedulerType.java 与 SchedulerFactory.java 中的CustomSchedulerManager加载逻辑开发者可以实现自己的负载均衡策略并作为插件接入。赞分享大数据数据库后端【免费下载链接】prestoThe official home of the Presto distributed SQL query engine for big data项目地址https://gitcode.com/gh_mirrors/pre/presto点击查看免费下载相关推荐OBS Studio硬件编码器突然失效从QSV与NVENC消失到恢复的完整排查指南OBS Studio硬件编码器突然失效从QSV与NVENC消失到恢复的完整排查指南 OBS Studio的硬件编码器QSV、NVENC、AMF突然全部消失音视频直播屏幕录制桌面应用视频RELION 5.0 安装与配置完整指南掌握低温电镜3D重构核心技术RELION 5.0 安装与配置完整指南掌握低温电镜3D重构核心技术 RELIONREgularised LIkelihood OptimisatioN是BabyAI未来展望语言理解AI研究平台的发展路线图BabyAI未来展望语言理解AI研究平台的发展路线图 BabyAI平台作为一款专注于训练智能体理解和执行语言命令的测试平台正在引领AI语言理解领域的创新与发人工智能强化学习机器学习深度学习NLP创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考