Part 5: 练习

1. HTTP 服务器

练习 1：HTTP 请求格式

题目：一个 OpenAI chat 请求的 HTTP 报文长什么样？写出完整的请求。

参考答案（先自己尝试，再展开查看）

POST /v1/chat/completions HTTP/1.1
Host: 127.0.0.1:8000
Content-Type: application/json
Content-Length: 95

{"model":"deepseek-v4-flash","messages":[{"role":"user","content":"Hello"}],"stream":true}

ds4_server 用 sscanf 解析第一行，用 Content-Length 确定请求体长度。

练习 2：SSE 格式

题目：写出两个 SSE 事件，分别发送 {"text":"Hi"} 和结束标记。

参考答案（先自己尝试，再展开查看）

data: {"text":"Hi"}

data: [DONE]

注意每行 data: 前缀，每条消息后有两个换行（一个在内容后，一个空行分隔）。

练习 3：为什么推理只用一个 worker 线程

题目：ds4_server 只有一个推理 worker。为什么不并行处理多个请求？

参考答案（先自己尝试，再展开查看）

1. GPU 独占：Metal GPU 一次只能执行一个计算图，多个请求无法同时使用 GPU
2. KV cache 独占：内存中只有一个 live session，多请求会互相覆盖
3. 内存限制：模型本身占 81GB，一个 KV cache 占数 GB，128GB 机器没有空间给多个 session
4. 串行化保证：按先来先服务的顺序处理，避免复杂的并发控制

如果未来支持 batching（多请求合并），可以同时处理多个短请求。

练习 4：poll() 事件追踪

题目：SSE 推理产生 3 个 token "Hi"、"!"、"EOS"。write_all 在发送第 2 个 SSE chunk 时，send() 返回 -1 且 errno=EAGAIN（TCP 发送缓冲区满）。追踪 poll() 调用的事件序列，标出每次 poll 的 events 和 revents 值。

参考答案（先自己尝试，再展开查看）

初始: TCP 发送缓冲区 = 65536 字节

步骤 1: sse_headers(fd)
  → send() 成功，写入 HTTP 响应头 ~120 字节
  → 缓冲区剩余 ~65416

步骤 2: sse_chunk(fd, "Hi")
  → send() 成功，写入 "data: {\"text\":\"Hi\"}\n\n" ~25 字节
  → 缓冲区剩余 ~65391

步骤 3: sse_chunk(fd, "!")
  → send() 尝试写入 ~25 字节
  → 缓冲区满（假设之前的响应数据还没被客户端读走）
  → send() 返回 -1, errno = EAGAIN (would block)

步骤 4: poll() 调用
  struct pollfd pfd = {fd, POLLOUT, 0};
  poll(&pfd, 1, -1);           // 无限等待，直到 fd 可写

  → 此时:
    pfd.events  = POLLOUT (= 0x0004)  // 关注可写事件
    pfd.revents = 0                    // 还没有事件

步骤 5: 客户端读走数据，TCP 缓冲区释放
  → poll() 返回
    pfd.revents = POLLOUT (= 0x0004)  // fd 现在可写了

步骤 6: 重新 send()
  → send() 成功，写入剩余的 SSE chunk 数据

步骤 7: sse_done(fd)
  → send() 成功，写入 "data: [DONE]\n\n"
  → 流结束

时序:
send(headers)  → OK
send(chunk_1)  → OK
send(chunk_2)  → EAGAIN ← 缓冲区满
poll(POLLOUT)  → 等待...
                ← 客户端读走数据
poll 返回       → POLLOUT
send(chunk_2)  → OK（重试成功）
send([DONE])   → OK

练习 5：job 队列交错追踪

题目：3 个客户端几乎同时发送请求（fd=5, fd=6, fd=7），1 个 worker 线程。追踪 enqueue/dequeue 的执行顺序，画出队列状态变化。

参考答案（先自己尝试，再展开查看）

初始状态: head=NULL, tail=NULL

步骤 1: client_main(fd=5) 调用 enqueue(job_5)
  lock(mu)
  head = job_5, tail = job_5
  signal(cv)      // 唤醒 worker
  unlock(mu)

步骤 2: client_main(fd=6) 调用 enqueue(job_6)
  lock(mu)
  tail->next = job_6  // job_5 → job_6
  tail = job_6
  signal(cv)
  unlock(mu)

步骤 3: client_main(fd=7) 调用 enqueue(job_7)
  lock(mu)
  tail->next = job_7  // job_5 → job_6 → job_7
  tail = job_7
  signal(cv)
  unlock(mu)

步骤 4: worker_main 调用 dequeue()
  lock(mu)
  head = job_5 → 取出 job_5
  head = job_6
  unlock(mu)
  → generate_job(job_5)    // 处理 fd=5 的推理

步骤 5: worker 完成 job_5，再次 dequeue()
  lock(mu)
  head = job_6 → 取出 job_6
  head = job_7
  unlock(mu)
  → generate_job(job_6)

步骤 6: worker 完成 job_6，再次 dequeue()
  取出 job_7
  head = NULL, tail = NULL
  → generate_job(job_7)

队列状态变化:
enqueue(job_5): [job_5]
enqueue(job_6): [job_5, job_6]
enqueue(job_7): [job_5, job_6, job_7]
dequeue:        [job_6, job_7]        → 处理 job_5
dequeue:        [job_7]               → 处理 job_6
dequeue:        []                    → 处理 job_7

关键观察:
- enqueue 的顺序决定了处理顺序（FIFO）
- signal(cv) 可能合并（多个 signal 只唤醒一次）
- 但 while(!head) 确保不会丢失任务

今日学习检查清单

• 理解 socket/bind/listen/accept/recv/send 的流程
• 能描述 ds4_server 的线程架构
• 理解 poll() 处理慢客户端的原理
• 能手写 SSE 事件格式
• 理解 OpenAI 和 Anthropic API 的区别

---

延伸挑战

挑战 1（中级）：用 curl 测试 ds4-server

启动 ./ds4-server，用 curl 发送一个非流式请求和一个流式请求（"stream": true）。对比两次响应的格式差异。如何用 jq 解析非流式响应中的 assistant 回复？

挑战 2（高级）：实现 /v1/models 端点

ds4_server.c 目前没有实现 /v1/models 端点（很多客户端会调用它）。阅读 client_main 的路由逻辑，添加一个处理函数返回 {"data": [{"id": "deepseek-v4-flash", "object": "model"}]}。提示：找到处理 POST /v1/chat/completions 的地方，在前面加一个路径匹配。

2. KV Cache 持久化

练习 1：SHA1 缓存 key

题目：token IDs = [100, 200, 300]。计算 SHA1 的输入字节（不需要算完整 SHA1）。

参考答案（先自己尝试，再展开查看）

token 100: le_put32 → [0x64, 0x00, 0x00, 0x00]  (100 = 0x64)
token 200: le_put32 → [0xC8, 0x00, 0x00, 0x00]  (200 = 0xC8)
token 300: le_put32 → [0x2C, 0x01, 0x00, 0x00]  (300 = 0x012C)

SHA1 输入: 64 00 00 00 C8 00 00 00 2C 01 00 00 (12 字节)
SHA1 输出: 20 字节 → 40 字符 hex 文件名 + ".kv"

练习 2：原子写入

题目：为什么用 rename(tmp, final) 而不是直接 fwrite 到最终路径？

参考答案（先自己尝试，再展开查看）

1. 崩溃安全：如果写一半进程崩溃，临时文件不完整，最终文件完好
2. 原子性：rename 在 POSIX 上是原子的——要么成功（新文件替换旧文件），要么失败（旧文件不变）
3. 无半写状态：读取方要么看到完整的旧文件，要么看到完整的新文件，不会看到写了一半的数据

练习 3：前缀匹配效率

题目：缓存目录有 100 个文件，incoming prompt 有 5000 个 token。最坏情况下需要计算多少次 SHA1？

参考答案（先自己尝试，再展开查看）

最坏情况：每个缓存文件的 token 数都 <= 5000

对于每个缓存文件:
  计算该文件 token 数量的 prompt 前缀的 SHA1 → 1 次 SHA1

最多 100 次 SHA1 计算

优化：先按 token 数量排序，从最长开始匹配
→ 找到第一个匹配就停止

练习 4：二进制头部布局计算

题目：给定以下参数，手动构造 KV cache 文件的二进制头部：

• quant_bits = 4, reason = 2 (continued), ext_flags = 0
• tokens = 5000, hits = 3, ctx_size = 8192
• created_at = 1700000000, last_used = 1700000300
• 文本 "Hello, world!" 长度 13 字节

要求：

1. 根据 code-walkthrough 中的布局表，写出头部各字段的十六进制字节值
2. 计算文本段的起始偏移（固定头部 = 48 字节）
3. 写出 text_len 前缀的字节值（4 字节 LE）
4. 计算整个文件的前两部分（header + text）共多少字节

参考答案（先自己尝试，再展开查看）

1. 头部字节值 (48 字节):

偏移  字节值                   字段
0-2   44 53 34                magic "DS4"
3     01                      version = 1
4     04                      quant_bits = 4
5     02                      reason = 2 (continued)
6     00                      ext_flags = 0
7-10  88 13 00 00             tokens = 5000 (0x1388) LE
11-14 03 00 00 00             hits = 3 LE
15-18 00 20 00 00             ctx_size = 8192 (0x2000) LE
19-26 00 F1 53 65 00 00 00 00 created_at = 1700000000 LE
27-34 2C F2 53 65 00 00 00 00 last_used = 1700000300 LE
35-42 00 00 00 00 00 00 00 00 payload_bytes = 0 (先算文件大小再填)
43-47 00 00 00 00 00          预留/对齐填充到 48 字节

2. 文本段起始偏移: 48

3. text_len 前缀: 0D 00 00 00 (13 = 0x0D, 4 字节 LE)

4. 文件前两部分:
   固定头部: 48 字节
   text_len 前缀: 4 字节
   文本内容: 13 字节
   合计: 48 + 4 + 13 = 65 字节

注: payload_bytes = 文件总大小 - 48 (header) - 4 (text_len) - 13 (text)
   = session 序列化数据的大小

练习 5：前缀匹配追踪

题目：磁盘缓存中有 4 个条目：

文件	text	tokens	quant_bits
a1...	"You are a helpful"	4	4
b2...	"You are a helpful assistant"	5	4
c3...	"Write a poem"	3	4
d4...	"You are"	2	4

新请求: prompt_text = "You are a helpful assistant. Tell me about AI"，quant_bits=4, ctx_size=8192, min_tokens=2

追踪 kv_cache_find_text_prefix 的执行过程，记录每个条目的匹配结果。

参考答案（先自己尝试，再展开查看）

扫描每个条目:

条目 a1 "You are a helpful" (4 tokens, quant=4):
  - tokens >= min_tokens? 4 >= 2 ✓
  - quant_bits match? 4 == 4 ✓
  - strncmp("You are a helpful assistant. Tell me about AI",
            "You are a helpful", 18) == 0 ✓
  - 匹配长度 = 18
  - best_len = 18, best_path = "a1..."

条目 b2 "You are a helpful assistant" (5 tokens, quant=4):
  - tokens >= min_tokens? 5 >= 2 ✓
  - quant_bits match? 4 == 4 ✓
  - strncmp("You are a helpful assistant. Tell me about AI",
            "You are a helpful assistant", 27) == 0 ✓
  - 匹配长度 = 27 > best_len=18 → 更新
  - best_len = 27, best_path = "b2..."

条目 c3 "Write a poem" (3 tokens, quant=4):
  - tokens >= min_tokens? 3 >= 2 ✓
  - quant_bits match? 4 == 4 ✓
  - strncmp("You are a helpful assistant. Tell me about AI",
            "Write a poem", 12) ≠ 0 → 不匹配

条目 d4 "You are" (2 tokens, quant=4):
  - tokens >= min_tokens? 2 >= 2 ✓
  - quant_bits match? 4 == 4 ✓
  - strncmp("You are a helpful assistant. Tell me about AI",
            "You are", 7) == 0 ✓
  - 匹配长度 = 7 < best_len=27 → 不更新

最终结果:
  best_len = 27
  匹配缓存: b2... ("You are a helpful assistant")
  effective_prompt = ". Tell me about AI"

加载效果:
  - 跳过 5 个 token 的 prefill（直接从磁盘恢复 KV cache）
  - 只需要增量推理 ". Tell me about AI" 部分

今日学习检查清单

• 理解原子写入模式（tmp + rename）
• 能解释为什么用 token IDs 而不是文本做缓存 key
• 能画出 KV cache 文件的格式布局
• 理解四种保存触发时机（cold/continued/evict/shutdown）
• 理解前缀匹配的工作方式
• 理解冷启动时修剪尾部 token 的原因

---

延伸挑战

挑战 1（中级）：KV Cache 文件逆向分析

运行 ./ds4-server 进行多轮对话，然后在 .cache/ds4/ 目录找到生成的 KVC 文件。用 xxd 查看头部，对照代码中的 KVC_MAGIC 和文件格式，解析出：token 数量、前缀长度、session payload 大小。

挑战 2（高级）：前缀匹配的最长公共前缀算法

KV Cache 查找需要计算新旧 token 序列的最长公共前缀。ds4.c 用简单的逐 token 比对。分析其时间复杂度，并提出优化方案：如果缓存了几百个 session，如何快速找到 LCP 最长的那个？提示：考虑 Trie 或哈希。

3. API 兼容层

练习 1：JSON 解析追踪

题目：追踪 json_skip_value 对以下 JSON 的解析过程：

{"name":"test","value":42}

从 { 开始，描述如何跳过整个对象。

参考答案（先自己尝试，再展开查看）

'{': 进入对象模式
  "name": 字符串 → json_string → 跳过
  ':': 跳过
  "test": 字符串 → json_string → 跳过
  ',': 跳过
  "value": 字符串 → json_string → 跳过
  ':': 跳过
  42: 数字 → json_number → 跳过
'}': 对象结束

指针停在 '}' 之后

追问：如果 JSON 是 [[[[...256 层...]]]] 会怎样？

json_skip_value_depth 在第 256 层递归时检测到 depth >= JSON_MAX_NESTING，返回 false，请求被拒绝。这防止了恶意深层嵌套 JSON 耗尽 C 调用栈的 DoS 攻击。

练习 2：API 格式对比

题目：同一个请求，写出 OpenAI 和 Anthropic 两种格式的 JSON body。

请求：系统提示 "Be brief"，用户消息 "What is 2+2?"，temperature=0，流式。

参考答案（先自己尝试，再展开查看）

OpenAI:

{
  "model": "deepseek-v4-flash",
  "messages": [
    {"role": "system", "content": "Be brief"},
    {"role": "user", "content": "What is 2+2?"}
  ],
  "temperature": 0,
  "stream": true
}

Anthropic:

{
  "model": "deepseek-v4-flash",
  "system": "Be brief",
  "messages": [
    {"role": "user", "content": "What is 2+2?"}
  ],
  "temperature": 0,
  "stream": true
}

主要区别：system 在 OpenAI 中是 messages 的一项，在 Anthropic 中是顶层字段。

练习 3：为什么手写 JSON 解析器

题目：列出 ds4_server 手写 JSON 解析器而非使用第三方库的三个理由。

参考答案（先自己尝试，再展开查看）

1. 零依赖：整个项目（ds4 + ds4-server）不需要安装任何库，make 就能编译
2. 精确控制：只需要解析请求中的特定字段，json_skip_value 可以高效跳过不关心的字段
3. 二进制大小：手写解析器编译后很小，不会引入整个 JSON 库的代码
4. 学习价值：展示了递归下降解析器的设计模式
5. 安全性：自己控制的代码比第三方库的攻击面小

今日学习检查清单

• 能解释递归下降 JSON 解析器的工作方式
• 理解 json_skip_value 的作用
• 能对比 OpenAI 和 Anthropic API 的格式差异
• 理解 Tool Calling 的完整流程（DSML ↔ OpenAI/Anthropic）
• 理解工具调用文本记忆（rax 基数树精确回放）
• 理解 DSML 参数文本和工具结果文本的转义规则（各自只保护关闭标签）
• 理解 KV cache 命中率衰减驱逐策略（6 小时半衰期）
• 理解 API 响应中 KV cache 用量报告（cached_tokens / cache_read_input_tokens）
• 理解工具 schema 前置到 system prompt 的原因（KV cache 边界裁剪保护）
• 理解检查点恢复机制（session rewrite API）
• 理解 Thinking 模式的三种级别
• 理解 SSE 流式输出的格式
• 理解 JSON 解析的嵌套深度限制（防止栈溢出 DoS）

---

延伸挑战

挑战 1（中级）：用 Claude Code 调用 ds4-server

配置 Claude Code 使用本地 ds4-server 作为后端（设置 OPENAI_API_BASE）。尝试一个多轮对话和一次 tool calling。观察 ds4-server 的日志输出，追踪请求格式是否与 API 兼容层学到的 JSON 解析路径一致。

挑战 2（高级）：扩展 JSON 解析器

ds4.c 的 JSON 解析器只支持 ds4-server 需要的字段。如果需要支持 logprobs: true 参数（返回每个 token 的 top log probabilities），需要修改哪些解析函数？画出从 HTTP 请求到 logprobs 输出的数据流图。