基于 commit: 23b67b37b246fb7cecb3815c6873fa3d18c3c0e7
目前公司主要用 v0，v1 架构已经发生了较大变化，后续补充整理。
调度器结构
数据结构
调度器的关键数据结构主要包含三个双端队列，存储 sequence group：
- waiting 队列：存放等待 prefill 的请求和重计算请求。所有请求最初都被添加到这里。
- running 队列：存放之前的推理阶段被送去推理的所有请求，decode + chunked prefill。
- swapped 队列：所有之前被抢占的请求。
调度器每一个 step（一次调度） 会从这些队列中取出请求，送去推理。
调度器还维护三个重要的状态：
- self.prev_time：记录上一次调度的时间。
- self.prev_prompt：记录上一次调度时，是否从 waiting 队列中取了 seq_group。
- self.last_prompt_latency：当前调度时刻（Now） - 最后一次从 waiting 队列做调度的时刻。
前置概念
抢占
如果推理时，发现 GPU 资源不够了：
- 如果当前 seq_group 剩余生命周期中并行运行的最大 seq 数量 > 1，则将所有 kv block 都 swap 到 CPU 上。
- 如果 < 1，则走 recomputation 策略，释放掉所有物理块，并将它放回 waiting 队列最前端。
也可以通过 preemption_mode 手动执行。
预算 Budget
用于调度时判断资源是否够用，主要由 max_num_batched_tokens 和 max_num_seqs 这两个参数决定。
budget 区别于系统实际可用资源。budget 主要是用户自行指定的资源额度，调度时会先判断 budget 是否充足。如果 budget 充足，才会通过 block manager 判断系统实际资源是否满足要求。
序列组调度
序列组调度主要是整理调度器如何调用不同的 sequence group。
基本代码结构
- _schedule(self)：是调度的主入口，其中会决定使用 _schedule_default 还是 _schedule_chunked_prefill。目前只整理了非 chunked prefill 的情况。
- _schedule_default：默认情况下的调度器，协调下面几个子调度器对各个队列进行调度，拼装最终的调度结果。
- _schedule_prefill：对 waiting 队列进行调度。
- _schedule_priority_preemption：抢占相关的逻辑，仅在 prefill 队列未被调度（因为调度了prefill 的话，running 和 swapped 都不会被调度，也就没必要抢占了）、且配置了 priority 模式时生效。
- _schedule_running：对 running 队列中的 decode 和 (chunked) prefill 请求进行调度。
- _schedule_swapped：调度 swapped 队列，将之前被换出的搬回 GPU。
调度策略概括
- waiting 队列（存储prefill + 重计算的序列组）是第一优先级。
- 先尝试从 waiting 队列中取出 sequence group 送去推理，直到不满足调度条件（GPU 空间不足、当前队列已为空等）；
- 但如果已经存在被 swapped 的序列组，则证明当前系统已经超负荷工作，有请求被换出，就不能再继续添加 waiting 中的序列组去计算了。
- （在没有开启 chunked prefill 的情况下）如果调度了 waiting 队列，就不会再调度其他队列；如果没有调度 prefill，才会进行抢占判断、running调度、swapped调度。
因为 prefill 和 decode 请求的计算特征不同（计算瓶颈 vs 带宽瓶颈）？，放到一个 step 里调度可能会降低设备利用率（要么prefill 等 decode，要么decode 等 prefill）。
- 进行抢占调度。
如果 running 队列存在优先级低于 waiting 队列的序列组，且设备资源不足，则将其换出到 CPU 或者直接清空放回 waiting 队列。具体执行换出还是重计算，可以手动配置，也可以让 vLLM 自动判断（判断方式在”前置概念“的“抢占”中介绍）。
- running 队列（存储 decode + chunked prefill的序列组）是第二优先级。
如果没有调度任何 prefill 请求，则开始尝试调度 waiting 队列中的序列组。
- swapped 队列是最次优先级。
如果没有调度 waiting，且调度完 running 胡还有资源剩余，且该 step 没有进行过任何抢占，才会尝试去 swapped 队列进行调度。
_schedule_prefills
这个函数负责将 waiting 队列中的请求添加到待调度的列表中。
默认情况下，会优先调度 prefill 请求。
但是如果一直有新来的请求，则旧请求的 decode 阶段会一直受阻，此时可通过 delay_factor 参数来控制仅在 prefill 请求已经排队多长时间时，才优先调度 prefill 请求（通过 _passed_delay 函数来判断）。
主要的逻辑都在红框中的 while 循环里，而进入循环的条件是 waiting 队列不为空，且 _passed_delay 为 True（ waiting 队列存在等待时间超过 delay_factor*last_prompt_latency 的请求）。
while 循环每次从 waiting 队列最前端取出一个请求，判断当前是否剩余足够的 kv cache 块，是否还剩下足够的 tokne 和 seqs 配额。如果有则将其添加到 seq_groups 列表中。
最后将 seq_groups 列表返回给主调度器。
作用是判断当前是否需要抢占：在存在“优先级反转”时，把低优先级的请求换出（从running 队列移动到 waiting 队列），腾出资源。
详细逻辑：
如果存在等待中的请求，则弹出 waiting 队列最左侧的元素作为一个“探针”。如果存在“优先级反转”（即 running 队列中优先级最低的 seq_group，低于 running 队列中的高优先级请求），且当前系统资源不足以调度 waiting 队列的这个请求，则进入后续判断逻辑。否则直接跳出循环。
如果已经出现了优先级反转，且系统资源不足以调度 waiting 队列里的这个高优先级请求，则取出 running 队列的请求，释放对应的资源，放入 waiting 队列。
最后将“探针”放回 waiting 队列，对 waiting 队列进行排序。
_schedule_running
循环弹出 running 队列中的序列组，直到系统资源/预算不足。其中包含抢占逻辑：
- 如果资源充足，则不抢占，为序列附加 slot，送去推理；
- 如果资源不足，则释放运行队列中最低优先级（队列末尾）的序列组；如果没有其他请求，则释放自己并结束调度。
_schedule_swapped
按照先进先出的原则循环弹出 swapped 队列中的序列组：
- 先判断所需的空间是否分配得出来：如果稍后可能可以分配（没超过最大可分配空间），则放回队列，之后再调度；如果不可能分配出来，则直接丢弃。
- 一直调度，直到预算不足。
资源调度
资源调度主要是整理在完成序列组调度后，调度器如何调度配套的资源。
待整理。。。