9-19 记录

2026-09-19 · 随笔 · 43a908c205b5

# 2026 年 9 月 19 日｜从 KV Store 到 KV Cache：思路与疑问


> 根据今天两段录音（约 9 分 55 秒、3 分 48 秒），对照《公开面试题官网吗》聊天导出整理。下文是整理稿，不是逐字转写；题面、个人复盘和整理时的技术说明分开记录。
>
> 聊天来源：我的gpt对话: `ChatGPT-公开面试题官网吗-20260919-2141.md`。题目是聊天中给出的 Versioned Key-Value Store 练习，不能据此当作官方逐字原题。


## 前情提要


今天看了一些 OpenAI、Anthropic 面试题的讨论，觉得这类题可以拿来做自我训练，就让 ChatGPT 挑了一题给我试试。当时没有电脑，我先用口头方式推演。


以下保留当天 16:14:49 聊天中给出的练习题面，仅调整标题层级。


### 题目：Versioned Key-Value Store


实现一个内存中的 key-value store：


```python
class VersionedKVStore:
    def set(self, key: str, value: str, timestamp: int) -> None:
        ...


    def get(self, key: str, timestamp: int) -> str | None:
        ...
```


语义：


```python
store.set("a", "hello", 10)
store.set("a", "world", 20)


store.get("a", 5)    # None
store.get("a", 10)   # "hello"
store.get("a", 15)   # "hello"
store.get("a", 20)   # "world"
store.get("a", 100)  # "world"
```


`get(key, timestamp)` 应返回：


> 对这个 key，所有 `timestamp <= 查询 timestamp` 的记录中，**时间最新的一条 value**。


#### 额外条件


`set()` **不保证按照 timestamp 顺序到达**。


例如：


```python
store.set("a", "v3", 30)
store.set("a", "v1", 10)
store.set("a", "v2", 20)
```


仍然需要：


```python
store.get("a", 25)   # "v2"
```


如果同一个：


```text
key + timestamp
```


被 set 两次，**后一次覆盖前一次**。


例如：


```python
store.set("a", "cat", 10)
store.set("a", "dog", 10)


store.get("a", 10)   # "dog"
```


假设最多大约：


```text
100,000 次 set/get 操作
```


#### 我现在想看你做四件事


你可以直接用 Python 写。


1. 先讲一下你准备使用什么数据结构。
2. 实现 `set()` 和 `get()`。
3. 告诉我两者的时间复杂度。
4. 自己写几个你认为重要的 test case。


**不要考虑并发、磁盘、TTL 等问题，现在题目里都没有。**


第二段录音对应当天 16:53:01 聊天中的下列问题。题面原文保留，编号按本篇顺序调整。


### 第二题：Transformer KV Cache


假设有一个 decoder-only Transformer：


```text
输入：
[A, B, C, D]


模型生成：
E


然后再生成：
F
```


普通 attention 在生成 `E` 时，会计算：


```text
Q_A Q_B Q_C Q_D
K_A K_B K_C K_D
V_A V_B V_C V_D
```


生成完 `E` 后，下一步要生成 `F`。


我的问题只有一个：


> **为什么生成 F 时，不需要重新计算 A、B、C、D 的 K 和 V？**


你先不用管代码，也不用背公式。


就按你喜欢的“**拓扑 + 标准件 + 数据流**”方式想：


```text
token
 ↓
某些算子
 ↓
K / V
 ↓
attention
```


你告诉我：**哪些东西是过去已经确定、可以缓存的，哪些东西每生成一个新 token 必须重新算？**


你回答完，我再继续追问下一层。


## 第一段复盘：从需求想到标准件


我一开始想到的，还是用“数据结构加标准件”的方式来拼解法。


最直观的想法是用 list，把 timestamp 当成下标，并把某些没有记录的位置也填上对应的值。下标天然有顺序，看起来可以直接查询。但继续想就发现，数组究竟要开多长？如果 timestamp 很大、很稀疏，空间会浪费很多；遇到乱序写入，又该修改哪些位置？录音时，我没有把填充范围完整说清楚，这个方案还没有形成精确的规则。


我也想过把时间范围写成一条条 if/else，有点像自己构造一个状态机。它能表达不同时间区间对应不同的值，但每增加或修改一条历史记录，都可能要改动原来的判断规则。如果把这些规则存成字符串，存储和维护也会变得别扭。


后来，ChatGPT 给出的方向是把哈希表、有序列表和二分查找组合起来。外层通过 key 找到一份历史记录，内层保存按 timestamp 排序的记录。查询时，在这份历史里找到不超过查询时间的最大 timestamp，返回它对应的 value。


我真正想追问的是：为什么能想到这些组件？


回头看，我一开始喜欢 list，是因为下标似乎顺带提供了顺序。但直接把时间戳当下标，也把存储空间绑到了时间戳的取值范围上。其实可以把需求拆开：先找到某个 key 的历史；再让历史按时间排列；最后找到查询时间的前驱。对应起来，就是哈希表负责定位历史，有序列表负责保存顺序，二分查找负责定位边界。


今天值得记住的，是从操作需求反推组件的过程。我已经能复述这个组合的大致思路，但录音里对写入步骤、dict 和 list 的具体关系还有反复。接下来可以用几次乱序写入和查询，把每一步存下来的内容写出来，检查自己的理解是否完整。


## 第二段复盘：知道 K/V 可以缓存，但还没弄懂为什么


这一部分根据第二段录音整理；原先只依据聊天写下的 KV Cache 补记，以这次更具体的自述为准。


第二个问题是 Transformer 的 KV Cache。输入 A、B、C、D，生成 E，再生成 F，哪些东西可以不用重新计算？我之前回答，过去的 K 和 V 不用再算。


但再回头想，我发现自己还没有真正弄明白原因。我知道“不用重算”这个结论，就顺着它想到：那应该是后面新加入的内容不会影响之前的 K 和 V。可为什么不会影响？这一步我其实没有讲清楚。


我开始往前追：key 和 value 到底是怎么来的？我记得似乎要对输入矩阵做线性运算，但再往下想，Q、K、V 各自怎么计算，我的记忆并不完整。录音中提到了矩阵和“旋转”之类的操作，也没有把它们准确对应到具体步骤。


更让我困惑的是：Q 和 K 的计算方式不是类似的吗？如果新增输入不会影响旧的 K，为什么之前的解释又把 Q 单独拿出来说？究竟是旧的 Q 会变，还是每个新位置需要算它自己的 Q？这里我还没有理顺。


另外，decoder-only 究竟指什么，我也没有弄懂。我知道 attention 这个模块，但这还不足以让我说明整个模型为什么能够这样缓存。


这一段先把没有想明白的地方记下来：Q、K、V 的来源；新输入对旧位置计算的影响；以及 decoder-only 与因果注意力的关系。这些问题还需要继续往计算过程里追。


## 整理补充：澄清原聊天中关于 Q 的表述


以下是整理时补充的解释，不代表录音中已经掌握。


原聊天把“旧的 K/V 可以复用”和“新位置的 Q 必须计算”并列，容易让人误以为旧位置的 Q 会被新增 token 改变。这两句话比较的其实不是同一个位置。


在标准因果 Transformer 的推理过程中，若参数、已有前缀和位置约定保持不变，新增 E 不会改变 A、B、C、D 在各层的已有计算结果。**旧位置的 Q、K、V 都不因此改变。**


处理 E、准备预测 F 时，需要计算每层 E 位置自己的 Q、K、V。新 Q 要与历史 K 匹配，再对历史 V 加权，所以历史 K/V 在这一步还有用途；旧 Q 不参与这个新位置的注意力计算，通常没有必要保存在 KV cache 中。


用单个注意力头的基本形式表示，省略偏置等实现细节：


```text
该层输入 H
  ├─ Q = H W_Q
  ├─ K = H W_K
  └─ V = H W_V


注意力权重 = softmax(Q Kᵀ / sqrt(d_k) + 因果掩码)
注意力输出 = 注意力权重 × V
```


因此，V 本身也是输入的线性投影；“注意力权重乘 V”得到的是注意力输出，不能把这两个步骤混在一起。录音中的“旋转”具体指什么尚不明确，整理时不擅自认定为转置或某种位置编码。


在这道题的语境下，decoder-only 指采用解码器堆叠、自回归预测下一个 token 的模型结构；因果注意力限制每个位置只读取自己和更早的位置。缓存成立的关键，需要落实到这种依赖关系上，不能只记一个模型名称。


## 第一题的技术校正


以下为整理时的校正与补充，不计作录音中已经独立讲清楚的内容。


1. **查询的是时间戳的前驱。** 开头说的“最小值”应改为“不超过查询时间的最大 timestamp”，再返回对应的 value。
2. **两层存储可以直接表达。** `key -> [(timestamp, value), ...]`，每个列表按 timestamp 排序即可。不必先建一份 timestamp 到 value 的哈希表，再把它转换成列表。有序列表是数据组织方式，二分查找是算法。
3. **写入时保持有序。** 先在该 key 的列表里二分定位 timestamp；若已存在，覆盖 value；否则在正确位置插入。无需每次追加后再全量排序。题面允许乱序写入，所以不能假设直接追加就能保持有序。
4. **定位和插入的成本不同。** 对普通数组实现的列表，查询是 O(log n)；覆盖已有时间戳需要 O(log n) 定位；插入新时间戳最坏为 O(n)，因为后面的元素需要移动。n 指这个 key 的历史记录数。十万次操作下，若大量写入集中在同一个 key 且频繁从中间插入，这个成本需要评估；有序数组是一个可解释的基础方案，不能仅凭二分查找就认为整体高效。
5. **区分题面条件和泛化思考。** 本题 timestamp 明确是整数。录音中“小数不能直接作下标”的想法可以用于拓展，但当前数组方案更直接的问题是时间戳范围、稀疏性和乱序写入时的维护。
6. **保持当前练习的范围。** 同时支持乱序、覆盖和空结果，是这次练习明确的要求。并发、TTL、持久化尚未进入当前阶段。


## 第一题下一次可以用来检验理解的小例子


这是整理时补充的练习，不代表已经实现或测试通过。


```text
set("a", "v3", 30)
set("a", "v1", 10)
set("a", "v2", 20)
get("a", 25)          → "v2"
set("a", "new", 20)
get("a", 25)          → "new"
get("a", 9)           → None
get("missing", 25)    → None
```


尝试不看答案，写出每次操作后的内部结构，再解释为什么查询始终能得到正确的历史版本。