vLLM整体架构
看了一些整体架构的博客，以及源码，我的一些感想是，可以尝试从更加high level的角度考虑这个推理框架的设计，如果是你的话，你会怎么设计？现在已经有参考答案了，可以从结果推过程，这么做目的是什么？
一个推理框架，首先是一个暴露给用户的一个entrypoint，可以轻松通过这个调用模型推理任务，而不需要关注内部的具体细节。
其次是核心，LLM Engine，它有两个任务，调度和执行。调度需要考虑同一时刻来了很多request，应该用什么样的顺序去执行这些request，目前还有任务没推理结束，应该照顾到新来的任务还是现在的任务。执行需要考虑分布式推理，流水线并行、张量并行，每个device上如何加载模型，kv cache如何管理，如何推理，如何做all-reduce。
有两种llm engine，一种是同步的，一种是异步的，异步的就是request输入需要处理，模型需要执行，结果后处理，这些可以异步执行。同步的适用于离线批处理。再llm engine的一个step中，只有可能全部做prefill或者全部做deocde。
调度器(schedualer)，掌管sequence group的执行，sequece group的引入是同一个prompt可能会对应于多个output，例如beam search，self-consistency等，sequece group掌管自己的逻辑地址，那如何通过逻辑地址找到对应的物理地址？这就通过BlockManager来完成。
BlockManager需要维护一个block table完成地址的映射。推理的时候，可能一个batch中的某些sequence group结束了，就需要将这些内存释放掉，腾出空间来，给新的的sequenece group加进来。如果某一个时刻内存空间不足了，就需要释放掉一些内存空间或者将空间swap到主存，要的时候再重新加载。这样需要一些队列来维护当前sequece的状态，比如waiting、running还有swap队列。怎么知道推理的时候会不会内存空间不足呢？这就涉及到一个保守的策略。
如何分配物理块，两个阶段要分开考虑。prefill阶段和decode阶段。prefill阶段我们要为这个batch中的sequence分配足够的物理块，有些sequence group的prefix可能已经分配过了，可以复用，这可以通过前缀token hash来实现，每个物理块有一个hash。每个物理块有一个引用计数，表示当前有多少个sequence使用，如果sequence结束推理，则-1，如果归0，就将这个block打入冷宫。使用evictor管理物理块分配的细节，因为有些sequence已经结束了，但是还是不会去释放掉block（可能万一以后有用呢？），就用free table去管理这些没有被引用，但没被释放的空间。出现空间不足的时候，就会去释放这些物理块。如何决定这些物理块释放掉呢？利用LRU，最长时间没有使用的block，如果都一样的话，去找hash长度最长的block释放掉，如果都一样，那就随机了。
decode阶段的物理块会触发copy-on-write机制，如果不能复用，就会重新创建一个新的物理块，因此ref count 需要-1，这个时候也要重新计算物理块的hash值，decode阶段在一个block还没有满的时候，给它一个互相不重复的hash。当子序列完成物理块的所有slots的时候，再对这个物理块做hash计算，拿着这个new hash，去free tables（冷宫）和cache blocks（当前正在被使用的物理块表）。如果没有找到可以复用的物理块，就释放这个物理块，复用旧的物理块；没有的话，就要在cache blocks中释放掉旧的，用新的hash取代掉。所以decode阶段的prefix caching不是一种频繁地复用，而是一种累积到一定范围尽可能地长段复用，方便进行kv cache的管理。
kv cache空间是很重要的，在正式推理开始之前，我们能不能知道这个显卡上面可以分配多少kv cache呢？通过模拟实验的方式，决定到底分配多少个KV cache块。
用户提供的两个重要参数：
- max_num_seqs，在一个推理阶段中，最多能处理的seq数量，默认256
- max_num_batched_tokens：在一个推理阶段，最多能处理的的token数量，默认为2048
假设在模型推理中，平均一个seq要处理 max_num_batched_tokens // max_num_seqs 个token.
用假数据模拟一次前向推理
想知道在1次推理过程中，可以分配多少的显存给KV cache。我们可以使用如下公式计算：
分配给KV cache显存 = gpu总显存 - 不使用KV cache做1次推理时的显存占用（包括模型本身和推理过程中的中间数据，例如激活值缓存）。对于“不使用KV cache做1次推理时的显存占用”，我们就可以用杜撰出来的假数据模拟一次前向推理来计算得出。在前向推理之后，我们把gpu上的缓存清一次，让它不要影响后续模型的正常推理。（禁用kv cache进行一次前向推理）。
worker中又有CacheEngine（负责管理kv cache）和model runner（负责加载模型，推理）
关于调度器：
优先考虑从swapped队列中取出sequence group（肯定处于decode阶段），所以在推理中，要么都来自于running，要么都来自running + swapped，要么都来自于waiting，这是因为在vllm中，一个step只有可能都做decoding或者都做prefill
超过一定时间的时候，就需要从waiting队列中取出来做prefill，那就需要判断gpu上面是否有充足空间做prefill/decoding？
在离线批处理中，表面上是同步推理的（batch size）是固定的，但是LLMEngine在实际运行中，是可以动态变化的
一个prefill称为一个推理阶段，一个decode称为一个推理阶段，batch size可以根据显存中的实际使用而变动。比如给一个很大的batch，尽管vLLM利用了Page Attention这样的显存优化技术，依然没有办法同时处理很大的batch。
每一条batch数据，都会被放到一个waiting队列中
利用调度策略，从waiting队列中取出来，放到running中，然后有的sequence已经推理结束了，比如
将waiting队列中的数据继续append到running队列中，进行下一个阶段的推理
这就是动态batch的四线。
因此当一条请求发过来的时候，会先进入secheduler的waiting队列，由调度器决定哪些进入running队列进行推理。
在这个过程中，使用PageAttention的技术和先来先服务策略，gpu不够就swap到CPU上的调度策略。
step()：负责执行1次推理过程（1个prefill算1个次推理，每个decode各算1次推理）。在这个函数中，vLLM的调度器会决定要送那些数据去执行本次推理，并负责给这些数据分配好物理块id，真正的物理块分配是通过CacheEngine来做的。
将base model 加载到worker上
Squence类
SquenceGroup，为什么要这个类？有哪些状态
一个SquenceGroup中的每个squence由一个公共的prompt生成
swap和recomputation策略
如何schedule？就是在一个推理阶段，哪些数据需要送给模型做推理，同时负责给这些模型分配kv cache
get_max_num_running_seqs这个方法用于计算一个序列组(seq_group)在其剩余生命周期内可以并行运行的最大序列数量。
在vLLM中，每个seq都单独维护一份属于自己的逻辑块，不同的逻辑块可以指向同一个物理块
BlockTable用来干什么，每个seq有管理自己的逻辑地址，根据block table，可以根据逻辑地址的id找到seq的物理块，实现了逻辑块到物理块的映射。
BlockManager使用来管理和分配物理块的。
- waiting队列
- running队列
- swapped队列，存放被抢占的seq group
那么是根据什么规则调度的呢？
如果当前swapped队列为空，那就去检查是否能从waiting队列中调度seq_group，直到不满足调度条件为止（gpu空间不足，或waiting队列已为空等）。此时，1个推理阶段中，所有的seq_group都处在prefill阶段。（尽可能装满）
如果swapped队列非空，检查running队列中调度seq group
在一个推理阶段，要么所有seq group全部处于prefill阶段，要么全部处于decode阶段
如果说在若干个推理阶段后，gpu上面的资源不够了，需要调度器抢占下这个seq_group，因此需要swap策略，还是recomputation策略，对于seq比较少的seq group，重新计算kv cache的代价并不高。
如何计算seq的剩余生命周期？即并行running最大的seq数量，知道seq group中的所有seq都完成推理。
是否有充足空间给该seq group做decode / prefill，这是两个不同的判断
如果是decode，为每一个需要decode的seq都要预留一个block，否则就不能deode
一个物理块，一个逻辑块到底长什么样子？
对于物理块，我们需要记录设备是gpu还是cpu，物理块对应设备上的全局block idx，物理块的尺寸，这个hash值是通过多少个前置token计算出来的，这个物理块被多少逻辑块引用，物理块最后一次被使用的时间，物理块是否被计算过（prefix caching中使用），物理块 hash（prefix caching场景）
逻辑块的序号、size、逻辑块的token id，没有分配的话，就是-1，当前逻辑块已经被装下的token数量。一些方法：获取剩余槽位，是不是空的，是否已经被装满，将给定的一些token id放入当前的逻辑块中。
每个seq自己维护一个逻辑块的列表
prefill阶段如何分配物理块？如果还没有prefill的话，一定是在waiting队列，要先判断是否有充足空间，如果有的话，就用blockAllocator，根据是否需要prefix caching，分配不同的block allocator。
waiting队列->running队列
prefill阶段计算物理hash值的方法：需要注意hash值的计算非常重要，两个等待进行prefill的seq如果拥有相同的hash，说明有相同prompt，就可以复用已有的kv cache。计算hash，计算token num。
使用evictor（驱逐器）管理物理块分配的细节
为什么需要free table？因为当一个seq推理完成后，理论上不需要它的kv cache的物理块了，没有逻辑块引用，是可以释放掉。但是如果下一个来的seq正好用上了呢？因此设计一个free table存放现在还没有用，但是可能以后会用上的block
因此在prefill阶段，当我们想创建一个物理块的时候，需要下面几个步骤：
- 计算物理块的hash值，看是否有可以重复利用的物理块
- 没有，就先检查下这个设备剩余的空间是否足够我们创建一个新的物理块
- 如果没有空间，就从free table中驱逐掉一个块，为新的物理块腾出空间，利用LRU，如果多个相同最后一次使用，就优选去掉hash token最多的那个
decode阶段的时候，分配物理块的方法
物理块的copy-on-write机制，对于同一个prompt，如果生成两个不同的token，就需要在物理内存上面开辟一个新的空间，这个时候就不能复用一个物理block了，因此ref count 需要-1
这个时候也要重新计算物理块的hash值，decode阶段在一个block还没有满的时候，给它一个互相不重复的hash。当子序列完成物理块的所有slots的时候，再对这个物理块做hash计算，拿着这个new hash，去free tables（冷宫）和cache blocks（当前正在被使用的物理块表）。
如果没有找到可以复用的物理块，就释放这个物理块，复用旧的物理块
没有的话，就要在cache blocks中释放掉旧的，用新的hash取代掉。
所以decode阶段的prefix caching不是一种频繁地复用，而是一种累积到一定范围尽可能地长段复用，方便进行kv cache的管理。