设某个节点 u 的缓存中有若干条完整 token 序列,请求序列为 r,则该节点与请求的匹配长度为:
LCP(u,r)=s∈cacheumaxcommonPrefixLen(s,r)每次请求到来时,需要选择:
实现一个多节点 LLM 推理集群的请求路由器。每个节点维护一个 KV Cache,缓存已处理请求的完整 token 序列(模拟 prefill 完成后 KV 被缓存)。新请求到来时,选择能复用最多 KV Cache 的节点以减少 prefill 计算量;命中长度相同时,选负载最轻的节点。
背景:在实际 LLM 推理系统中(如 vLLM、SGLang),若新请求的前缀与某节点已缓存的请求存在公共前缀,该部分的 prefill 计算可直接复用,显著降低 TTFT(Time To First Token)。
路由规则(按优先级):
选与当前请求拥有最长公共前缀(LCP)的节点
若多个节点 LCP 长度相同(含均为 0),选当前队列中待处理 token 总量最少的节点
状态更新(每条请求路由后立即执行,模拟 prefill 完成):
将请求的完整 token 序列加入所选节点的缓存
将请求的 token 数(len(request))累加到所选节点的负载上
解答要求
时间限制:C/C++ 1000ms,其他语言:2000ms
内存限制:C/C++ 512MB,其他语言:1024MB
Line 1: N M # N个节点,M个请求
Line 2: load[0..N−1] # 每个节点初始待处理 token 数
Line 3~N+2: K seq0 seq1 ... # 每个节点初始缓存:K条序列,各序列 token 逗号分隔。K=0 时该行只有 “0”
Line N+3~end: t0 t1 t2 ... # 每条请求的 token 序列,空格分隔,共 M 行
一行,M 个整数,assignment[i] 为第 i 条请求分配的节点编号(0-indexed)。
输入:
3 4
100 50 200
0
0
0
10 20 30 40 50
10 20 30 40 60
10 20 30 40 50 70
5 6 7 8
输出:
1 1 1 1
解释:逐步分析:
| 请求 | 最长LCP | 路由 | 原因 |
|---|---|---|---|
| 10,20,30,40,50 | 0(无缓存) | 节点1 | 负载最轻(50) |
| 10,20,30,40,60 | 节点1:4 | LCP 最长 | |
| 10,20,30,40,50,70 | 节点1:5(命中第1条) | ||
| 5,6,7,8 | 0(无命中) | 负载最轻(50+5+5+6=66,节点0=100,节点2=200) |
输入:
2 4
0 0
1 1,2,3,4,5
0
1 2 3 4 5 6 7
8 9 10 11
1 2 3 4 5 100 200
99 88 77
输出:
0 1 0 1
解释:逐步分析:
| 请求 | 最长LCP | 路由 | 原因 |
|---|---|---|---|
| 1,2,3,4,5,6,7 | 节点0(命中缓存 1,2,3,4,5) | 节点0 | LCP 更长 |
| 8,9,10,11 | 0 | 节点1 | LCP 相同,节点1负载(0) < 节点0(7) |
| 1,2,3,4,5,100,200 | 5 | 节点0 | LCP 更长 |
| 99,88,77 | 0 | 节点1 | LCP 相同,节点1负载(4) < 节点0(14) |