简介这份文档面向云计算方向的学生、研究人员与工程实践者系统梳理资源分配与调度算法的核心知识帮助读者理解如何在多用户、多任务场景下实现计算资源的公平高效利用。内容围绕静态与动态资源分配两条主线展开涵盖最大最小公平算法、分数算法、最优化算法、遗传算法等典型方法并延伸至云计算调度算法中的任务分配、负载均衡、能耗管理与任务迁移等关键问题同时介绍随机森林、神经网络、贪婪算法及无模型调度等常见方案还讨论了多元异构环境调度、强化学习融合与云原生调度等发展趋势。资源包共1个docx文件约21KB结构紧凑、主题集中适合作为算法选型与方案对比的参考笔记。目前已有389人学习可帮助读者快速建立资源分配与调度算法的知识框架理解不同算法的适用场景与权衡思路。1. 云计算资源分配算法从“资源抢不到”到“算力刚刚好”凌晨两点监控大盘上某业务集群的 CPU 利用率曲线像心电图一样剧烈抖动——白天峰值冲到 92%夜里跌到 8%。运维群里有人吐槽“扩容慢得像蜗牛”业务方抱怨“高峰期接口超时”财务那边又盯着账单问“为什么闲置这么多”。这不是某一家的问题而是所有把业务搬上云之后都会撞上的墙资源分配算法没调好钱花了体验还差。云计算资源分配算法说白了就是一套决定“哪台物理机、哪个虚拟机、哪个容器该拿多少 CPU、内存、带宽”的规则集合。它要同时回答三个问题新来的任务放哪、已有的任务要不要挪、挪的时候怎么不中断。适合谁看做后端、SRE、平台工程、容器调度的同学只要你手头有集群、有账单、有 SLA 压力这篇就能用。下面从选型到落地把能抄的配置和踩过的坑一次讲清。2. 先搞懂分配算法的三条主线装箱、调度、弹性资源分配不是单一算法而是一条流水线。很多团队一上来就调 Kubernetes 的调度器权重结果发现瓶颈根本不在调度而在装箱策略和弹性阈值。先把三条主线拆开后面动手才不会乱。2.1 装箱问题为什么“最佳适应”反而让碎片更严重装箱Bin Packing解决的是“把多个任务塞进有限节点”的问题。常见策略有三种首次适应First Fit、最佳适应Best Fit、最差适应Worst Fit。直觉上最佳适应最省空间但实际跑起来它会把大节点切得七零八落留下大量“塞不进大任务、又浪费小任务”的碎片。我一般会按业务形态选长尾小任务多用首次适应追求高利用率用最差适应只有任务规格高度统一时才考虑最佳适应。下面这段 Python 用一维装箱模拟三种策略的碎片率可以直接改参数跑。# 模拟三种装箱策略的碎片率 # bins: 节点容量列表items: 任务规格列表 def first_fit(bins, items): remain bins[:] # 剩余容量 for it in items: for i in range(len(remain)): if remain[i] it: remain[i] - it break return sum(remain) / sum(bins) # 碎片率 def best_fit(bins, items): remain bins[:] for it in items: idx, gap -1, float(inf) for i in range(len(remain)): if remain[i] it and remain[i] - it gap: gap, idx remain[i] - it, i if idx 0: remain[idx] - it return sum(remain) / sum(bins) def worst_fit(bins, items): remain bins[:] for it in items: idx, gap -1, -1 for i in range(len(remain)): if remain[i] it and remain[i] - it gap: gap, idx remain[i] - it, i if idx 0: remain[idx] - it return sum(remain) / sum(bins) bins [64] * 10 # 10 个 64 核节点 items [3, 5, 8, 13, 21] * 8 # 混合规格任务 print(first:, first_fit(bins, items)) print(best :, best_fit(bins, items)) print(worst:, worst_fit(bins, items))逻辑说明remain记录每个节点剩余容量遍历任务时按策略选节点。参数bins是节点容量items是任务规格改这两个就能模拟自己的集群。碎片率越低越好但别只看这个数——最佳适应碎片率低却可能让后续大任务无处可放这就是“局部最优、全局翻车”。2.2 调度器选型Kubernetes 默认打分够不够用Kubernetes 默认调度器有一套打分插件NodeResourcesFit、PodTopologySpread、InterPodAffinity 等。多数场景够用但有两个边界要注意一是默认的LeastAllocated倾向把 Pod 打散利用率上不去二是没有原生支持“任务优先级 抢占 回填”的组合。如果集群规模在 500 节点以内我建议先用默认调度器加自定义打分权重别急着换调度框架。改权重的方式是写一个 KubeSchedulerConfiguration把NodeResourcesFit的scoringStrategy从LeastAllocated改成MostAllocated再配requestedToCapacityRatio曲线。# scheduler-config.yaml apiVersion: kubescheduler.config.k8s.io/v1 kind: KubeSchedulerConfiguration profiles: - schedulerName: default-scheduler pluginConfig: - name: NodeResourcesFit args: scoringStrategy: type: RequestedToCapacityRatio requestedToCapacityRatio: shape: - utilization: 0 score: 0 - utilization: 70 score: 8 - utilization: 100 score: 10 resources: - name: cpu weight: 2 - name: memory weight: 1逻辑说明shape定义利用率与得分的映射70% 利用率给 8 分100% 给 10 分引导调度器把节点用满。weight表示 CPU 比内存更重要。参数怎么改如果业务对内存敏感把 memory 权重提到 2如果怕热点把 100% 对应的分数降到 6留出缓冲。改完用--config启动调度器观察kube-scheduler的schedule_attempts_total和pod_scheduling_duration_seconds两个指标。2.3 弹性伸缩HPA 的冷却时间和阈值怎么设才不抖弹性伸缩是资源分配的“动态修正”。HPA 默认 15 秒同步一次扩容冷却 3 分钟、缩容冷却 5 分钟。很多团队把阈值设成 CPU 80%结果业务一抖动就扩容扩完又缩账单像坐过山车。我的经验是扩容阈值看 P95 而不是均值缩容阈值比扩容低 20 个百分点冷却时间按业务启动时长设。比如 Java 应用启动要 90 秒缩容冷却至少 5 分钟否则刚缩完又得扩。下面是一个 HPA 配置示例。apiVersion: autoscaling/v2 kind: HorizontalPodAutoscaler metadata: name: web-hpa spec: scaleTargetRef: apiVersion: apps/v1 kind: Deployment name: web minReplicas: 3 maxReplicas: 30 behavior: scaleUp: stabilizationWindowSeconds: 60 # 扩容观察 60 秒 policies: - type: Percent value: 50 periodSeconds: 60 # 每分钟最多扩 50% scaleDown: stabilizationWindowSeconds: 300 # 缩容观察 5 分钟 policies: - type: Pods value: 2 periodSeconds: 60 # 每分钟最多缩 2 个 metrics: - type: Resource resource: name: cpu target: type: Utilization averageUtilization: 65逻辑说明stabilizationWindowSeconds是冷却窗口窗口内取最保守的推荐值避免抖动。policies限制每次伸缩的幅度。averageUtilization: 65是目标利用率留了 35% 的突发余量。参数调整时先看kube-state-metrics里的kube_horizontalpodautoscaler_status_current_replicas如果副本数频繁上下就把窗口拉长、幅度调小。3. 动手实现一个最小分配器从打分到绑定理解了三条主线接下来写一个能跑的最小分配器。不依赖任何调度框架纯 Python 模拟“节点打分 任务绑定 超卖控制”方便你改造成自己的策略。3.1 节点打分函数把 CPU、内存、磁盘 IO 归一化打分是分配算法的核心。不同资源量纲不同必须先归一化再加权。下面这个函数把 CPU、内存、磁盘 IO 三项归一化到 0~1再按权重求和。# 节点打分资源归一化 加权求和 def normalize(value, total): return value / total if total 0 else 0 def score_node(node, task, weights): # node: {cpu_free:.., cpu_total:.., mem_free:.., mem_total:.., io_free:.., io_total:..} # task: {cpu:.., mem:.., io:..} cpu_ratio normalize(node[cpu_free] - task[cpu], node[cpu_total]) mem_ratio normalize(node[mem_free] - task[mem], node[mem_total]) io_ratio normalize(node[io_free] - task[io], node[io_total]) # 剩余比例越高得分越高低于 0 直接淘汰 if min(cpu_ratio, mem_ratio, io_ratio) 0: return -1 return (cpu_ratio * weights[cpu] mem_ratio * weights[mem] io_ratio * weights[io]) nodes [ {cpu_free: 8, cpu_total: 16, mem_free: 12, mem_total: 32, io_free: 80, io_total: 100}, {cpu_free: 4, cpu_total: 16, mem_free: 28, mem_total: 32, io_free: 60, io_total: 100}, ] task {cpu: 2, mem: 4, io: 10} weights {cpu: 0.5, mem: 0.3, io: 0.2} for i, n in enumerate(nodes): print(fnode{i} score:, round(score_node(n, task, weights), 4))逻辑说明normalize把剩余量除以总量得到 0~1 的比例。score_node先算分配后的剩余比例任何一项为负就返回 -1 淘汰。weights是权重CPU 占 0.5 表示更看重算力。参数调整如果磁盘 IO 是瓶颈把 io 权重提到 0.4如果任务对内存敏感mem 权重提到 0.5。注意归一化用的是“分配后剩余”不是“当前剩余”这样能提前避开会被撑爆的节点。3.2 绑定与回填任务排队时怎么不浪费空闲槽位打分选出节点后还要处理“大任务排队、小任务先跑”的问题。回填Backfill策略允许小任务跳过排队的大任务只要不影响大任务的预计开始时间。下面是一个简化版回填逻辑。# 简化回填大任务预留资源小任务填缝隙 def backfill(nodes, queue, reserve): # reserve: 为大任务预留的节点索引集合 scheduled [] for task in queue: if task[size] large: # 大任务走正常打分 best, best_score -1, -1 for i, n in enumerate(nodes): if i in reserve: continue s score_node(n, task, {cpu: 0.5, mem: 0.3, io: 0.2}) if s best_score: best, best_score i, s if best 0: nodes[best][cpu_free] - task[cpu] nodes[best][mem_free] - task[mem] nodes[best][io_free] - task[io] scheduled.append((task[id], best)) else: # 小任务只填非预留节点 for i, n in enumerate(nodes): if i in reserve: continue if (n[cpu_free] task[cpu] and n[mem_free] task[mem] and n[io_free] task[io]): n[cpu_free] - task[cpu] n[mem_free] - task[mem] n[io_free] - task[io] scheduled.append((task[id], i)) break return scheduled逻辑说明reserve是给大任务预留的节点小任务不能碰。大任务走完整打分小任务只做容量检查。参数reserve怎么定按大任务的历史到达频率和规格预留 20%~30% 的节点。回填的代价是可能延迟大任务所以要用stabilizationWindow类似的机制监控大任务排队时长超过阈值就暂停回填。3.3 超卖比控制CPU 可超卖内存为什么不能超卖Overcommit是提高利用率的常用手段但 CPU 和内存的超卖逻辑完全不同。CPU 是可压缩资源超卖后最多变慢内存不可压缩超卖后可能 OOM。我的做法是 CPU 超卖比 1.5~2.0内存超卖比 1.0~1.1并且给关键业务打上GuaranteedQoS。# 资源配额与超卖配置 apiVersion: v1 kind: ResourceQuota metadata: name: team-quota spec: hard: requests.cpu: 100 requests.memory: 200Gi limits.cpu: 200 # CPU 超卖 2 倍 limits.memory: 220Gi # 内存超卖 1.1 倍逻辑说明requests是调度依据limits是运行上限。CPU 的 limits 可以远大于 requests因为内核会按权重分配时间片内存的 limits 接近 requests防止节点内存被击穿。参数调整如果业务是离线批处理CPU 超卖可以到 3 倍如果是在线交易内存超卖必须锁死 1.0。监控container_memory_working_set_bytes和container_oom_events_totalOOM 一多就降超卖比。4. 避坑与排查那些让集群半夜报警的配置分配算法调参最怕“白天看着正常半夜突然雪崩”。下面五条是我和同行踩过的真实坑按现象、原因、解决写清楚。4.1 现象扩容后新 Pod 一直 Pending节点却有空闲原因调度器打分时把MostAllocated权重调太高所有节点得分接近但新 Pod 的requests刚好超过每个节点的剩余可分配量。Kubernetes 调度看的是requests不是实际使用量节点“看起来空闲”但可分配量已耗尽。解决用kubectl describe node看Allocated resources对比Requests和Limits。把MostAllocated的 100% 得分从 10 降到 7留出缓冲或者给节点打标签把大规格 Pod 定向到高配节点。4.2 现象HPA 频繁扩缩副本数像呼吸一样原因扩容阈值和缩容阈值太接近或者冷却窗口太短。CPU 利用率在阈值附近波动时HPA 会反复触发。解决扩容阈值和缩容阈值至少差 15 个百分点比如扩 70%、缩 50%。stabilizationWindowSeconds扩容设 60 秒、缩容设 300 秒。如果还抖检查指标采集周期Prometheus 抓取间隔要小于 HPA 同步周期。4.3 现象内存超卖后节点 OOM关键业务被杀原因内存超卖比设成 1.5节点实际内存耗尽内核 OOM Killer 按oom_score杀进程关键业务因为占用内存大反而先被杀。解决关键业务设GuaranteedQoSrequests 等于 limits并给 Pod 加oom_score_adj: -999。内存超卖比降到 1.1 以内同时开启kubelet的eviction-hard阈值比如memory.available10%就驱逐低优先级 Pod。4.4 现象回填导致大任务排队超时原因小任务不断填缝隙大任务预留的节点被逐渐占用或者预留比例不够。解决给大任务设PriorityClass调度器开启preemption。回填时用PodDisruptionBudget保护大任务预留节点用taint标记小任务只能容忍特定 taint。监控scheduler_pending_pods指标大任务排队超过 5 分钟就暂停回填。4.5 现象跨可用区调度导致网络延迟飙升原因打分时只考虑资源没考虑拓扑。Pod 被调到跨可用区节点服务间调用走公网延迟从 1ms 涨到 20ms。解决用PodTopologySpread约束可用区分布或者给节点打topology.kubernetes.io/zone标签在打分插件里加NodeAffinity权重。跨区流量大的服务直接设requiredDuringSchedulingIgnoredDuringExecution强制同区。5. 进阶技巧用真实指标反推分配参数调参不能靠拍脑袋得用真实指标反推。我习惯每周跑一次“资源画像”把过去 7 天的 CPU、内存、IO 使用率按 P50、P95、P99 拉出来再对比requests和limits看偏差有多大。具体做法用 Prometheus 查container_cpu_usage_seconds_total和container_memory_working_set_bytes按 Pod 聚合后算分位数。如果 P95 只有 requests 的 40%说明 requests 虚高可以下调如果 P99 接近 limits说明 limits 太紧要上调或优化代码。-- 按 Pod 算 CPU 使用率分位数PromQL 风格 quantile_over_time(0.95, rate(container_cpu_usage_seconds_total{container!POD}[5m])[7d:5m] ) by (pod) / quantile_over_time(0.95, kube_pod_container_resource_requests{resourcecpu}[7d:5m] ) by (pod)逻辑说明分子是实际使用率的 P95分母是 requests 的 P95比值小于 0.5 就考虑下调 requests。参数[7d:5m]表示过去 7 天、每 5 分钟一个采样点。这个查询跑完你会得到一张“虚高排行榜”按比值从低到高排序优先调前 20% 的 Pod。另一个技巧是“压力测试反推”。用stress-ng在测试集群模拟峰值负载逐步加压直到 SLA 告警记录此时的资源使用量作为limits的下限。生产环境再留 20% 余量。这样调出来的参数比看监控拍脑袋靠谱得多。最后说个血泪教训别在业务高峰期改调度器配置。我有一次在晚高峰调MostAllocated权重结果调度器重启期间新 Pod 全部 Pending业务抖了 15 分钟。后来定了个规矩——所有调度相关变更必须在低峰期灰度先改一个节点池观察 30 分钟再全量。希望帮到你。本文还有配套的精品资源点击获取