项目简介

PathFinder 是一个面向人机物融合场景的轻量级融合调度系统。系统基于 Kubernetes 与 Knative Serving，在请求绑定到执行实例之前完成排序、等待、抢占和负载分发，用于缓解长短任务混布时的队头阻塞问题。PathFinder 的核心思路是在 Knative Activator 请求路径中引入有界等待队列、分布级执行时间预测和执行时间感知负载均衡，在不修改工作节点内核、不要求业务运行时支持抢占的前提下，使短任务能够在绑定阶段获得更高优先级，从而降低端到端尾延迟。

作者团队

北京大学计算机学院

队长

刘侯谦

---

PathFinder — 面向人机物融合场景的轻量级云原生调度系统

Bounded preemptive scheduling and execution-time-aware load balancing for Knative Serving, targeting long-tailed serverless workloads, function chains, edge intelligence, embodied intelligence and industrial IoT scenarios.

本项目围绕一个核心问题：在云原生服务平台中，长任务先进入执行队列时，后到达的短任务会被迫等待，导致 P99 尾延迟升高、请求超时和资源利用率下降；能否在不破坏 Knative 原有部署模型的前提下，通过调度器内有界抢占和负载感知分发降低队头阻塞？

主要贡献包括：

• 调度器内有界抢占：抢占发生在请求绑定到 Pod 之前，长任务只在 Activator 内等待一个有上界的时间窗口；等待期间到达的短任务可优先绑定执行实例，不中断已经运行的业务任务。
• 分布级执行时间预测：不要求精确预测单个请求耗时，而是基于短时间窗口内的执行时间分布、请求到达分布和历史统计信息计算等待策略。
• 执行时间感知负载均衡：将 Pod 负载从“在途任务数量”扩展为“预计剩余执行时间”，并结合 Power-of-Two 候选比较降低长任务造成的局部负载倾斜。
• 函数链与多阶段任务支持：支持真实风格函数链、边缘视觉链路和多阶段业务请求，将外部请求拆分为多个子任务并分别执行调度。
• 云原生兼容：核心改动集中在 Knative Serving Activator 请求路径中，复用 Kubernetes 的 Pod 管理、Knative 的 Revision/Autoscaler 机制和 Istio 的流量入口能力。
• 完整实验验证：在 ALU microbenchmark、real-world function chain 和 parking benchmark 上，对比 Late Binding、Early Binding、Early+ExecTime 和 PathFinder，验证 P99 延迟、抢占率、队列长度、吞吐和负载均衡效果。

系统架构图见 fig2-overview.pdf，P99 延迟实验结果见 p99lat.pdf。

---

1. 仓库结构

PathFinder/
├── modified-knative-file/       # Knative Serving Activator 相关修改文件
│   ├── handler.go               # 请求接入、任务标注与 HTTP Header 元数据处理
│   ├── queue.go                 # 有界等待队列与 SchedulingUnit 管理
│   ├── heap.go                  # 队列/统计辅助数据结构
│   ├── shared.go                # 全局状态、执行时间统计、Pod 负载状态
│   ├── real_world_support.go    # 函数链长度、调用间隔、CDF 等真实负载支持
│   ├── lb_policy.go             # round-robin、late binding、power-of-two 等策略
│   ├── throttler.go             # 请求节流、绑定与负载分发路径
│   ├── main.go                  # Activator 服务入口与完成反馈逻辑
│   ├── activator.yaml           # 修改后的 Activator 部署配置
│   └── activator-service.yaml   # 反馈服务与 NodePort 相关配置
├── slb-simplified/              # Serverless load balancing 简化实验负载
│   ├── alu/                     # ALU CPU 密集型 microbenchmark
│   │   ├── alu.py
│   │   ├── locustfile.py
│   │   ├── Dockerfile
│   │   └── alu-service.yaml
│   ├── real-world/              # 真实风格函数链 benchmark
│   │   ├── workgen.py
│   │   ├── function.c
│   │   ├── run.sh
│   │   ├── real-world-service.yaml
│   │   └── CDFs/                # Azure/真实函数链相关 CDF 数据
│   └── enable-node-port.sh      # 反馈服务 NodePort 辅助脚本
├── spright-parking/             # Parking benchmark 与 Spright 相关实验代码
│   └── spright/
│       ├── cfg/parking.cfg
│       ├── sigcomm-experiment/expt-3-parking/
│       └── ...
├── assets/                      # 项目相关静态资源
├── logs/                        # 实验或运行日志目录
├── 特性设计文档.md              # 系统设计、核心模块、接口与异常处理说明
├── 测试方案文档.md              # 测试目标、环境、benchmark、trace、指标和结果
└── README.md

modified-knative-file/ 中的文件不是独立运行的完整 Knative 仓库，而是用于合并到 Knative Serving 对应源码位置后重新构建 Activator 镜像的核心修改文件。

---

2. 系统设计

2.1 三层架构

PathFinder 采用三层结构：

层次	职责
任务接入层	接收来自设备、业务服务或函数链的请求，为请求附加任务类型、到达时间、预计执行时间分组和链路标识等元数据。
融合调度层	在 Knative Activator 中实现有界等待队列、时间分布预测、实例状态管理和负载感知调度。
资源执行层	由 Kubernetes 节点、Knative Revision Pod、服务网格转发链路以及可接入的边缘/云端资源组成，负责执行任务并反馈状态。

2.2 设计原则

原则	说明
轻量化集成	不替换 Kubernetes 调度器，不修改业务函数运行时，核心改动集中在 Knative Activator 请求路径中。
调度器内抢占	抢占发生在请求绑定 Pod 之前，是逻辑抢占，不中断已经运行的任务。
分布级预测	基于历史执行记录估计任务执行时间分布和请求到达分布，避免依赖单请求精确耗时预测。
执行时间感知负载均衡	以预计剩余工作量衡量实例负载，适配长短任务混布场景。

2.3 核心模块

模块	功能	主要文件
请求接入与任务标注模块	接收 HTTP 请求，记录到达时间，为请求生成任务长度、函数链起始时间等调度元数据。	modified-knative-file/handler.go
有界等待队列模块	将请求封装为调度单元，为每个任务维护计时器，并根据等待时间决定出队顺序。	modified-knative-file/queue.go
时间分布与历史统计模块	维护执行时间分组、平均执行时间、最大执行时间、上一次任务信息和全局统计量。	modified-knative-file/shared.go, modified-knative-file/heap.go
真实负载生成支持模块	读取函数链长度、调用间隔、变异系数和执行时间 CDF，用于构造真实风格任务流。	modified-knative-file/real_world_support.go, slb-simplified/real-world/CDFs/
实例状态管理模块	记录每个 Pod 上在途任务数量和预计剩余负载，任务完成后更新状态。	modified-knative-file/shared.go, modified-knative-file/main.go
负载均衡策略模块	实现 round-robin、late binding、power-of-two 和执行时间感知选择策略。	modified-knative-file/lb_policy.go, modified-knative-file/throttler.go
完成反馈模块	提供任务完成反馈接口，回收 Pod 负载状态并更新统计信息。	modified-knative-file/main.go, modified-knative-file/activator-service.yaml

2.4 调度流程

1. 请求到达 Knative Activator。
2. 请求接入模块读取服务标识，生成或读取任务执行时间分组，并记录到达时间。
3. 对于函数链任务，系统根据链路长度和调用间隔分布生成多个子任务。
4. 请求被封装为 SchedulingUnit，进入有界等待队列。
5. 等待队列根据任务时间分布、请求到达强度和历史统计计算等待时间。
6. 任务等待时间到期后进入绑定阶段；短任务可因等待时间更短而越过先到达的长任务。
7. 负载均衡模块从候选 Pod 中选择预计剩余负载较低的实例。
8. 请求通过 Knative 原有反向代理链路转发到目标 Pod。
9. 执行实例完成任务后，将执行结果和任务信息反馈给 Activator。
10. Activator 更新对应 Pod 的在途任务状态和全局统计信息。

---

3. 关键算法

3.1 有界等待队列

每个请求进入队列时都会关联一个等待上限。队列管理协程周期性检查任务计时器，当任务等待时间归零时，该任务被取出并进入绑定流程。与 FIFO 队列不同，出队顺序不完全由到达顺序决定，而由等待时间和调度收益共同决定。长任务仍具有等待上界，避免短任务持续到达导致永久饥饿。

3.2 分布感知等待时间计算

PathFinder 根据历史任务执行时间分布、请求到达强度和序列级尾延迟期望计算等待时间。等待时间过短时，短任务尚未到达，长任务仍可能造成队头阻塞；等待时间过长时，长任务自身延迟会增加。该策略用于在减少短任务阻塞和控制长任务额外等待之间取得平衡。

3.3 执行时间感知 Power-of-Two 负载均衡

PathFinder 从当前可用 Pod 中随机选择两个候选，比较两个候选 Pod 的预计剩余执行时间，并选择负载更低的 Pod。该策略调度开销低，同时比纯随机、轮询或只看请求数量的策略更适合长短任务混布。

3.4 函数链和多阶段任务

PathFinder 支持将一个外部请求拆分为多个子任务，并为每个子任务独立执行有界等待和负载分发。典型链路包括：

场景	示例阶段
边缘视觉链路	图像采集、目标检测、属性检索、结果持久化、告警或计费。
具身智能链路	感知、语义理解、动作候选生成、规划评估、状态更新。
工业物联网链路	事件清洗、异常检测、规则匹配、工单生成、云端归档。

当前实现以顺序函数链为主；如需支持并行分支，可在任务接入层增加 DAG 拆分器，将依赖关系转换为多个带依赖状态的调度单元。

---

4. 接口与配置

4.1 请求元数据 Header

PathFinder 使用 HTTP Header 传递轻量调度元数据：

Header	含义
X-Rate	任务长度或预计执行时间分组，用于等待时间计算和负载估计。
X-Arrive-Timestamp	请求到达 Activator 的时间戳，单位为毫秒。
X-Last-Rate	前序任务长度或实验统计字段。
X-Seq-Start-Time	函数链起始时间，用于计算链路端到端延迟。

X-Rate 可以由任务类型映射表、历史统计分布、设备侧 hint 或调度器在线估计结果生成。

4.2 任务完成反馈接口

Activator 提供 POST /store 接口接收任务完成反馈。执行实例在任务结束后返回任务长度、响应时间、总延迟和 Pod IP 等信息，用于更新在途任务表和执行时间统计。

字段	含义
pod_ip	实际执行任务的 Pod IP。
rate	任务长度或预计执行时间分组。
response_time	从任务到达 Activator 到开始执行的时间。
latency	从任务到达 Activator 到执行完成的总延迟。
sequence_latency	函数链端到端延迟。

4.3 策略配置示例

策略参数可通过 ConfigMap 或服务 annotation 暴露：

pathfinder.dev/scheduling-policy: bounded-preemptive
pathfinder.dev/history-window: 10m
pathfinder.dev/max-wait-ms: "100"
pathfinder.dev/load-metric: expected-runtime

---

5. 测试与核心结果

5.1 测试目标

测试目标是验证 PathFinder 在长短任务混布、函数链调用和动态负载场景下的调度效果，重点关注：

• 端到端 P99 尾延迟。
• 任务到达 Activator 到开始执行之间的响应时间。
• 有界抢占机制对短任务队头阻塞的缓解效果。
• 执行时间感知负载均衡对 Pod 间负载分布的改善效果。
• 不同执行时间分布和请求到达强度下的稳定性。
• 调度器额外等待和队列长度带来的控制面开销。

5.2 测试环境

实验环境采用 9 节点 Kubernetes 集群，基于 KinD 部署在单台高性能服务器上。1 个节点作为 Kubernetes control plane，其余 8 个节点作为 worker 节点。

类别	配置
操作系统	Ubuntu 22.04 LTS
Linux Kernel	5.15
CPU	双路 AMD EPYC 7742，单路 128 logical cores，主频 2.25GHz
内存	512GB
容器运行环境	Docker
Kubernetes 集群	KinD，9 节点，其中 8 个 worker
服务平台	Knative Serving
网络入口	Istio ingress gateway
单实例资源配置	每个 serverless function Pod 配置 1 个 logical core

复现实验软件版本：

组件	版本
Ubuntu	22.04 server
Kernel	5.15.0-113-generic
Docker	24.0.7
Go	go1.22.5 linux/amd64
KinD	v0.23.0
Kubernetes Client	v1.30.3
Kubernetes Server	v1.30.0
Knative Serving	v1.15.2
kn CLI	v1.14.0
Istio	v1.15.1
Python runtime	python 3.8 slim

5.3 对比策略

策略	说明
Late Binding	请求进入等待队列，直到存在空闲 Pod 后再绑定。
Early Binding	请求到达后立即选择 Pod 绑定，减少调度等待，但容易造成负载倾斜。
Early+ExecTime	请求到达后立即绑定，但实例选择时使用执行时间感知负载均衡。
PathFinder	使用有界等待队列进行调度器内抢占，并结合执行时间感知负载均衡选择实例。

5.4 Benchmark 与 Trace

Benchmark	说明
ALU Microbenchmark	CPU 密集型计算服务，请求中携带任务执行单元数，用于评估纯计算型长短任务混布。
Real-world Function Chain Benchmark	基于函数链长度分布、执行时间分布和函数间调用间隔生成任务序列，用于模拟多阶段端云协同与智能边缘链路。
Parking Benchmark	图像检测与计费链路，包含车牌检测、查询、索引更新、计费和元数据持久化等阶段。

测试使用三类执行时间分布：

分布	说明
Azure Trace	基于公开云函数调用数据构造，体现真实 serverless 任务长尾执行时间。
Zipf 分布	可控长尾任务长度，参数 a = 1.294789、m = 1571585。
Power-law 分布	补充长尾任务模型，参数 a = 0.416、scale 54.37。

请求到达采用泊松过程，覆盖 lambda = 10、12.5、15、17.5、20 requests/s。

5.5 指标

指标	含义
P99 latency	请求端到端 P99 延迟，主要评价指标。
Average latency	请求平均端到端延迟。
Response time	请求到达 Activator 到开始执行之间的时间。
Execution time	任务实际执行耗时。
Preemption rate	发生调度器内抢占的任务比例。
Queue length	调度器等待队列长度，衡量控制面空间开销。
Timeout count	请求超时数量。
Throughput	单位时间成功完成请求数。
Pod load balance	Pod 间预计剩余执行时间分布。

5.6 实验结果

在 ALU microbenchmark、real-world function chain 和 parking benchmark 上，PathFinder 在 Azure、Zipf 和 Power-law 三类 trace 下均取得最低 P99 延迟。随着请求到达强度升高，所有策略的尾延迟都会上升，但 PathFinder 的上升幅度更低。

相对于 Early Binding，PathFinder 的 P99 延迟降低约 1.49x - 2.75x；相对于 Late Binding，PathFinder 的 P99 延迟降低约 2.10x - 4.10x。整体 P99 结果见 p99lat.pdf。

核心结论：

• 有界等待机制使短任务可以在绑定阶段越过长任务，减少队头阻塞。
• 执行时间感知负载均衡避免长任务集中到少数 Pod 上，降低局部排队时间。
• 在函数链场景中，PathFinder 对每个子任务独立排序和绑定，能够降低链路级尾延迟放大。
• PathFinder 的抢占率随请求密度增大而提高，并与理论最优抢占率趋势一致。
• 调度器引入了额外队列长度和等待开销，但等待时间有界，整体控制面开销处于可控范围。

---

6. 部署与复现实验

6.1 环境准备

建议在 Ubuntu 22.04 LTS 上准备以下组件：

# 基础环境
Docker 24.0.7
Go 1.22.5
KinD v0.23.0
kubectl v1.30.x
kn CLI v1.14.0
Istio v1.15.1
Knative Serving v1.15.2
Python 3.8 slim runtime

6.2 集成 PathFinder Activator

部署时需要将 modified-knative-file/ 中的相关文件合并到 Knative Serving 对应源码位置，重新构建并部署 Activator 镜像。核心步骤如下：

1. 准备 Kubernetes、Istio 和 Knative Serving 环境。
2. 将 modified-knative-file/handler.go、queue.go、shared.go、real_world_support.go、lb_policy.go、throttler.go、main.go 等文件合入 Knative Serving Activator 对应位置。
3. 使用 modified-knative-file/activator.yaml 和 modified-knative-file/activator-service.yaml 部署修改后的 Activator 与反馈服务。
4. 通过 slb-simplified/enable-node-port.sh 暴露任务完成反馈入口。
5. 部署 ALU、real-world function chain 或 parking benchmark 服务。

6.3 Benchmark 入口

目标	入口
ALU microbenchmark	slb-simplified/alu/alu.py, slb-simplified/alu/locustfile.py, slb-simplified/alu/alu-service.yaml
Real-world function chain	slb-simplified/real-world/workgen.py, slb-simplified/real-world/run.sh, slb-simplified/real-world/real-world-service.yaml
真实函数链 CDF 数据	slb-simplified/real-world/CDFs/
Parking benchmark	spright-parking/spright/cfg/parking.cfg, spright-parking/spright/sigcomm-experiment/expt-3-parking/

6.4 测试流程

1. 部署 Kubernetes、Istio 和 Knative Serving。
2. 构建包含 PathFinder 调度组件的 Activator。
3. 部署 PathFinder Activator、NodePort 反馈服务和被测 Knative Service。
4. 分别部署 ALU、real-world function chain 和 parking benchmark。
5. 为每个 benchmark 配置 Azure、Zipf、Power-law 三类执行时间分布。
6. 对每个分布分别设置 5 个请求到达强度。
7. 依次运行 Late Binding、Early Binding、Early+ExecTime 和 PathFinder。
8. 记录请求日志、任务完成反馈、P99 延迟、抢占率、队列长度和超时数量。
9. 对比不同策略在相同 benchmark、trace 和负载强度下的结果。

---

7. 异常处理与兼容性

7.1 异常处理

场景	处理方式
队列过载	队列容量由 MaxQueueize 控制；达到上限时可拒绝新请求或降级为直接绑定策略。
任务等待超时	每个任务等待时间均有上界，到期后进入绑定阶段，避免长任务永久饥饿。
执行超时	请求外层设置超时保护，由 Knative 和 PathFinder 请求处理逻辑共同返回错误。
反馈丢失	可为在途任务设置最大生命周期，结合 Knative/queue-proxy 指标校正状态，必要时降级为保守负载均衡。
预测偏差	分布突变时可缩短统计窗口、降低等待时间或回退到 early/late binding。
Pod 变化	基于 Activator endpoint 视图维护可用实例，Pod 新增时初始化状态，删除时清理状态。

7.2 兼容性

• Kubernetes/Knative 兼容：保留 Knative Service、Revision、Activator、Autoscaler 和网关调用方式。
• 业务函数兼容：业务函数无需集成专用 SDK；若需要完整反馈，则读取请求头元数据并在结束后调用 /store。
• 多类任务兼容：可接入端云协同、智能边缘、具身智能、工业物联网和安全增强等任务形态。

---

8. 已知局限

1. 当前实现以顺序函数链为主；并行 DAG 任务需要在任务接入层增加依赖拆分与状态管理。
2. 调度收益依赖任务执行时间分布的长尾程度；当任务耗时接近或负载很低时，有界等待收益会下降。
3. 完整负载状态依赖执行实例及时调用 /store 反馈接口；反馈丢失会导致 Pod 预计剩余负载短期滞后。
4. 历史窗口对预测稳定性有影响；窗口过短样本不足，窗口过长会引入过期负载阶段信息。
5. PathFinder 引入等待队列和统计维护逻辑，虽然开销有界，但仍需要结合队列容量、超时和降级策略控制控制面压力。

---

9. 文档索引

文档	内容
特性设计文档.md	系统总体设计、设计原则、核心模块、调度流程、关键算法、接口、异常处理和兼容性说明。
测试方案文档.md	测试目标、环境、对比策略、benchmark、trace、指标采集、测试流程和实验结论。
fig2-overview.pdf	PathFinder 系统架构图。
p99lat.pdf	三类 benchmark 与三类 trace 下的 P99 延迟对比结果。

---

10. License & 致谢

• 本项目基于 Kubernetes、Knative Serving、Istio 与 KinD 等云原生组件构建，请遵循相关开源项目许可证。
• Parking benchmark 相关代码位于 spright-parking/，请遵循其目录内许可证与使用说明。
• ALU 与 real-world function chain benchmark 位于 slb-simplified/，用于复现长短任务混布、真实风格函数链与多阶段调度实验。