更新题目 getID：批量取号

题目 everpure-get-id · 修改（rev 11） · cc · 2026-10-27 00:33
body

@@ -1,10 +1,10 @@
 ## TL;DR
 
-- **题**：面试官给一个现成的 `get_block_id(count)`，一次返回 `count` 个 id。要你写 `get_one_id()`，每次发一个，要求「性能好」。整轮按三版推进：每次现取 → 一次取一批、缓存起来发 → 专门一个线程提前取。开写前先问题目一节表里的几件事。
-- **批量多大**（思路第 2 节）：取一批的固定开销 T 摊到每个 id 上是 T/B。B 至少要 r·T（r 是每秒的需求），否则供给 B/T 追不上需求。B 越大，退出时浪费、占的内存越多。批量只降平均延迟，触发补货的那次照样等满 T。
-- **多线程**（思路第 3 节）：检查「这批发完没有」、补货、发一个，三步必须在同一个临界区里，否则两个线程会发出同一个 id，或者同时补货、浪费整批。加锁以后补货的 T 秒里所有调用者都在等。
-- **第三版**（思路第 4 节）：生产者线程负责取，调用者只从缓冲区拿。缓冲区剩的不多于低水位 L 时生产者去取下一批，慢调用在锁外。两个条件变量共用一把锁，分别等「缓冲区非空」和「该补货」。缓冲区最多 L + B 个。
-- **提前多少取**（思路第 5 节）：L 至少等于 r·T，也就是取一批的时间里会被要走的个数。变体 B 里是 100，即手里留一整批、下一批同时在取。突发超过「缓冲区加路上那一批」时照样要等，而且可能不止一个 T。
-- **Follow-up**：取一批失败时生产者要退避重试、不能死，也要能被关闭。批量按实测的消费速度自动调。`get_block_id` 能并行调，供给才能超过每秒 B/T。
+- **题**（题目一节）：用一次给 `count` 个 id 的 `get_block_id(count)` 写出高性能的 `get_one_id()`，按每次现取 → 批量取、缓存着发 → 专门线程提前取三版推进，开写前先问表里那几件事。
+- **批量多大**（思路第 2 节）：固定开销 T 摊到每个 id 是 $T/B$，B 至少 $r \cdot T$（r 是每秒需求）供给 $B/T$ 才追得上，B 越大退出浪费和内存越多，且批量只降平均延迟，触发补货那次照样等满 T。
+- **多线程**（思路第 3 节）：检查发完没有、补货、发一个必须在同一个临界区里，否则会发重复 id 或同时补货浪费整批，代价是补货的 T 秒里所有调用者都在等。
+- **第三版**（思路第 4 节）：缓冲区剩的不多于低水位 L 时生产者线程到锁外取下一批，调用者只从缓冲区拿，两个条件变量共用一把锁分别等「非空」和「该补货」，缓冲区最多 $L + B$ 个。
+- **提前多少取**（思路第 5 节）：$L \ge r \cdot T$，变体 B 里是 100（手里留一整批、下一批同时在取），突发超过缓冲区加路上那一批时照样要等，可能不止一个 T。
+- **Follow-up**（Follow-up 一节）：取一批失败要退避重试、生产者不能死且能被关闭，批量按实测消费速度自动调，`get_block_id` 能并行调供给才能超过每秒 $B/T$。
 
 ## 题目
@@ -81,5 +81,5 @@
 ```
 
-正确，但每一次调用都付一次完整的 T：要 n 个 id 就调 n 次 `get_block_id`，总耗时约 n·T（测试用例「批量大小」B = 1 那行）。这一版的意义是确认接口和「每个 id 只发一次」这条约定，面试官不会在这里停。
+正确，但每一次调用都付一次完整的 T：要 n 个 id 就调 n 次 `get_block_id`，总耗时约 $n \cdot T$（测试用例「批量大小」B = 1 那行）。这一版的意义是确认接口和「每个 id 只发一次」这条约定，面试官不会在这里停。
 
 ### 2. 第二版：批量取、缓存起来一个个发（单线程）
@@ -104,11 +104,11 @@
 #### 一批取多少合适
 
-一批的大小记作 B。每取一批花 T，这一批能发 B 次，所以摊到每个 id 上的开销是 T/B，要 n 个 id 的总耗时从 n·T 降到约 n·T/B。从测试用例「批量大小」那张表里看三件事：
+一批的大小记作 B。每取一批花 T，这一批能发 B 次，所以摊到每个 id 上的开销是 $T/B$，要 n 个 id 的总耗时从 $n \cdot T$ 降到约 $n \cdot T/B$。从测试用例「批量大小」那张表里看三件事：
 
 - **平均快了，最坏没变。** B 越大总耗时越短，但每一行的「单次调用最长」都约等于一个 T。批量只减少了付 T 的次数，没有减少单次要付的量：轮到谁触发补货，谁就等满一个 T，和 B 多大无关（前提是 T 不随 `count` 增长。随 `count` 增长的话 B 越大这一次越慢，见题目一节的表）。这是面试官问「批量有什么问题」时要答的第一条，也是第三版要解决的问题。
-- **退出时浪费。** 进程退出时缓存里没发出去的 id 就作废了，分配器那边留下一段空洞。退出的时刻落在一批里的哪个位置是随机的，平均剩半批，所以平均浪费 B/2 个。
+- **退出时浪费。** 进程退出时缓存里没发出去的 id 就作废了，分配器那边留下一段空洞。退出的时刻落在一批里的哪个位置是随机的，平均剩半批，所以平均浪费 $B/2$ 个。
 - **内存。** 缓存最多存 B 个 id。
 
-所以 B 不是越大越好。下限来自吞吐：设需求速度是 r（每秒要多少个），取一批花 T，这段时间里会要走 r·T 个。B 比 r·T 小，供给 B/T 就追不上 r，调用者越排越长。上限是取舍：B 每翻一倍，浪费和内存也翻一倍，换来的只是 T/B 再降一半。【推断】常见做法是取 r·T 到 2r·T，多一倍余量应付需求波动。不知道 r 时把 B 做成构造参数，或者用 Follow-up 第 2 条让它自己调。
+所以 B 不是越大越好。下限来自吞吐：设需求速度是 r（每秒要多少个），取一批花 T，这段时间里会要走 $r \cdot T$ 个。B 比 $r \cdot T$ 小，供给 $B/T$ 就追不上 r，调用者越排越长。上限是取舍：B 每翻一倍，浪费和内存也翻一倍，换来的只是 $T/B$ 再降一半。【推断】常见做法是取 $r \cdot T$ 到 $2r \cdot T$，多一倍余量应付需求波动。不知道 r 时把 B 做成构造参数，或者用 Follow-up 第 2 条让它自己调。
 
 ### 3. 多线程：不加锁会发重复的 id，加锁之后补货让所有人等
@@ -170,5 +170,5 @@
 - **生产者消费者（producer-consumer）**：一方不断生产东西放进一个共享的容器，另一方不断从里面取。这里生产者是取一批的那个后台线程，消费者是调 `get_one_id` 的线程，容器是 id 的缓冲区。两边速度不同步，所以需要一个办法让消费者在容器空时等、让生产者在容器满时等。
 - **有界缓冲区（bounded buffer）**：容器有上限，生产者不能无休止地往里放。没有上限的话，需求低的时候生产者会一直取、缓冲区无限长，囤的 id 全是浪费。
-- **低水位（low-water mark）**：一个阈值 L。缓冲区里剩的 id 数降到 L 或更少，就该去取下一批了。L = 0 就是「空了才取」。L 越大，取得越提前。它同时也定了缓冲区的上限：去取下一批的时候最多剩 L 个，所以到货后最多 L + B 个。
+- **低水位（low-water mark）**：一个阈值 L。缓冲区里剩的 id 数降到 L 或更少，就该去取下一批了。L = 0 就是「空了才取」。L 越大，取得越提前。它同时也定了缓冲区的上限：去取下一批的时候最多剩 L 个，所以到货后最多 $L + B$ 个。
 - **条件变量（condition variable）**：让线程「睡下去等某个条件成立」的工具，和一把锁绑在一起用。`wait()` 在一步之内放锁并睡下，被叫醒后重新拿到锁才返回。`notify()` 叫醒一个等的线程，`notify_all()` 叫醒全部。等待为什么写 `while` 不写 `if`、为什么先改条件再通知，见 [[p:kb/python-concurrency]]。
 
@@ -247,5 +247,5 @@
 2. **调用者在等的时候，一定有人在取。** 调用者等，说明缓冲区空，长度 0 不大于 L。而生产者只在长度大于 L 时才睡，所以它此刻要么正在取，要么刚被叫醒、马上会取。「刚被叫醒」有保证：把长度降到 L 或以下的那一次 `popleft` 紧接着就 `notify()` 了生产者，而 `_need_refill` 上只有生产者在等，叫醒的一定是它（上面五步表的问题在这里不会出现）。
 3. **不会丢失唤醒。** 两边改缓冲区长度都在锁里，通知在改完、还拿着锁时发，等的一方用 `while` 重查，所以不会出现「刚放锁还没睡着，通知就发过去了」。
-4. **缓冲区有上限。** 生产者只在长度不大于 L 时去取，所以到货后最多 L + B 个。需求低时会接近这个上限：L = B = 100 时，预热到货后长度是 100，不大于 L，生产者立刻去取第二批。需求低的话这批在路上时只被要走一小部分，到货后接近 200，之后生产者一直睡（测试用例「变体 B」最后一条）。
+4. **缓冲区有上限。** 生产者只在长度不大于 L 时去取，所以到货后最多 $L + B$ 个。需求低时会接近这个上限：L = B = 100 时，预热到货后长度是 100，不大于 L，生产者立刻去取第二批。需求低的话这批在路上时只被要走一小部分，到货后接近 200，之后生产者一直睡（测试用例「变体 B」最后一条）。
 5. **慢调用在锁外。** 生产者取一批的 T 秒里不拿锁，调用者照常从缓冲区拿，这正是第二版做不到的。
 6. **预热。** 构造函数等第一批到货才返回，否则第一次调用要等满 T。变体 B 要求任何一次调用都不等超过 1 秒，T = 1 s 时第一次就刚好压线。
@@ -259,14 +259,14 @@
 先看 L = 0，空了才取。缓冲区见底的那一刻生产者才开始取，这 T 秒里来的调用者全部要等，最早来的那个等将近 T，和第二版加锁的最坏情况一样。所以把取一批挪到另一个线程，等待一点没少，**让人少等的是提前取**。
 
-一般情况：生产者开始取下一批的时候，手里还剩 L 个。这批在路上的 T 秒里最多来 r·T 次调用。所以：
-
-- **L ≥ r·T**：路上的这段时间手里的够发，没有人等。
-- **L < r·T**：L 个在 L/r 秒内发完，之后来的人等到这批到货，最长等 T − L/r。变体 B 里 L = 50 时是 1 − 0.5 = 0.5 s。
-
-所以变体 B 的 follow-up「每次调用不等超过 1 秒」的答案是：**L = r·T = 100，也就是手里始终留着一整批、同时下一批已经在取**。这个做法叫双缓冲（double buffering）：一批在发，一批在取。缓冲区上限 L + B = 200。
+一般情况：生产者开始取下一批的时候，手里还剩 L 个。这批在路上的 T 秒里最多来 $r \cdot T$ 次调用。所以：
+
+- **$L \ge r \cdot T$**：路上的这段时间手里的够发，没有人等。
+- **$L < r \cdot T$**：L 个在 $L/r$ 秒内发完，之后来的人等到这批到货，最长等 $T - L/r$。变体 B 里 L = 50 时是 $1 - 0.5 = 0.5$ s。
+
+所以变体 B 的 follow-up「每次调用不等超过 1 秒」的答案是：**$L = r \cdot T = 100$，也就是手里始终留着一整批、同时下一批已经在取**。这个做法叫双缓冲（double buffering）：一批在发，一批在取。缓冲区上限 $L + B = 200$。
 
 还有两个边界要说出来：
 
-- **供给的上限。** 一次取 B 个、花 T 秒，而且 `get_block_id` 不能并行调（题目一节的表），所以供给最多每秒 B/T = 100 个，恰好等于需求上限。需求长期超过它，缓冲区一定见底，排队的人越积越多，哪种设计都救不了。要么让 `get_block_id` 并行调，要么一次多取（Follow-up 第 3 条）。
+- **供给的上限。** 一次取 B 个、花 T 秒，而且 `get_block_id` 不能并行调（题目一节的表），所以供给最多每秒 $B/T = 100$ 个，恰好等于需求上限。需求长期超过它，缓冲区一定见底，排队的人越积越多，哪种设计都救不了。要么让 `get_block_id` 并行调，要么一次多取（Follow-up 第 3 条）。
 - **突发。** 一下子来了一大批调用，按数量分三种情况：不超过缓冲区里剩的，没人等。超出的部分不超过路上那一批，超出的人等到这批到货，不超过 T。再多，生产者只有一个、一次只有一批在路上，每再多 B 个就要多等一个 T。例：L = B = 100，预热后手里 100 个、第二批在路上，同时来 300 个调用：前 100 个立刻拿到，接着 100 个等第二批，最后 100 个要等第二批到货后才开始取的第三批，约 2T（测试用例「突发」）。
 
@@ -294,12 +294,12 @@
 ```
 
-`low_water` 取 r·T（第 5 节），`batch` 至少 r·T（第 2 节）。不知道 r 就按 Follow-up 第 2 条让它自己调。
+`low_water` 取 $r \cdot T$（第 5 节），`batch` 至少 $r \cdot T$（第 2 节）。不知道 r 就按 Follow-up 第 2 条让它自己调。
 
 ## 复杂度
 
-- `get_one_id`：锁里只做 O(1) 的事（读长度、`popleft`、可能一次 `notify`），不等待时就是 O(1)。等待时间：需求不超过 r 且 L ≥ r·T 时为 0。突发时按第 5 节「突发」分情况，每超出 B 个多等一个 T。
-- `get_block_id` 的调用次数：每 B 个 id 一次，摊到每个 id 上的开销 T/B。
-- 内存：缓冲区最多 L + B 个 id。
-- 持锁时间：生产者在锁里只做 `extend`（O(B)）和 `notify_all`，取一批的 T 秒完全在锁外。
+- `get_one_id`：锁里只做 $O(1)$ 的事（读长度、`popleft`、可能一次 `notify`），不等待时就是 $O(1)$。等待时间：需求不超过 r 且 $L \ge r \cdot T$ 时为 0。突发时按第 5 节「突发」分情况，每超出 B 个多等一个 T。
+- `get_block_id` 的调用次数：每 B 个 id 一次，摊到每个 id 上的开销 $T/B$。
+- 内存：缓冲区最多 $L + B$ 个 id。
+- 持锁时间：生产者在锁里只做 `extend`（$O(B)$）和 `notify_all`，取一批的 T 秒完全在锁外。
 
 ## 易错点
@@ -308,5 +308,5 @@
 - **以为 GIL 能代替锁**（第 3 节）：GIL 只保证一条字节码不被打断，读和加一之间照样会切线程。
 - **慢调用放在调用路径上**（第 3 节末尾）：放在锁里，补货的 T 秒里所有调用者一起等。挪到锁外提前取，触发的那个调用者还是要等 T。要换第三版。
-- **空了才取**（第 5 节）：后台线程取一批本身不减少等待，提前取才减少。L 要不小于 r·T。
+- **空了才取**（第 5 节）：后台线程取一批本身不减少等待，提前取才减少。L 要不小于 $r \cdot T$。
 - **以为提前取了就不会等**（第 5 节「突发」）：突发超过缓冲区加路上那一批时，最后的人要等不止一个 T。
 - **生产者不睡**（第 4 节）：没有「缓冲区够就睡」这一条，需求低时缓冲区无限长。
@@ -341,5 +341,5 @@
 | 第三版 L = 100 | 0.00 s | 0.000 s | 0 | 100 | 5 |
 
-L = 50 的最长等待和第 5 节算出的 T − L/r = 0.5 s 一致。L = 100 时缓冲区最多 100，低于上限 200：需求等于供给，一批在路上时正好被要走 r·T = 100 个（Follow-up 第 4 条）。另把需求降到每秒 20 次、持续 3 s：缓冲区最多 179 个，`get_block_id` 只调 2 次（预热一次，预热到货后长度 100 不大于 L，又取一次），之后生产者一直睡。
+L = 50 的最长等待和第 5 节算出的 $T - L/r = 0.5$ s 一致。L = 100 时缓冲区最多 100，低于上限 200：需求等于供给，一批在路上时正好被要走 $r \cdot T = 100$ 个（Follow-up 第 4 条）。另把需求降到每秒 20 次、持续 3 s：缓冲区最多 179 个，`get_block_id` 只调 2 次（预热一次，预热到货后长度 100 不大于 L，又取一次），之后生产者一直睡。
 - **突发**（第 5 节）：T = 0.2 s，B = L = 100，预热后 300 个线程用 `Barrier` 同时调用。最快的 100 个不等。接着 100 个最长等 0.17 s。最后 100 个最长等 0.37 s，约 2T。比 0.2 s、0.4 s 略短，是因为第二批在创建 300 个线程的时候已经开始取了。
 - **第三版多线程正确性**：8 个线程各要 500 个，B = 50，L = 25，T = 1 ms：4000 个全部不同，`get_block_id` 81 次。
@@ -386,5 +386,5 @@
 第 2 节和第 5 节里 B 和 L 都要先知道需求速度 r。真实系统里 r 会变，固定的 B 要么在高峰时不够（调用者等），要么在低谷时囤太多（浪费）。2016 年的面试官把这个 follow-up 比作 TCP 的拥塞控制：TCP 不知道网络能承受多大的发送量，就从小量开始发、顺利就加大、丢包就减小。这里借的是同一个想法，不预先假设需求、按观测来调。区别是 TCP 只能靠丢包间接试探，这里能直接数出消费速度，所以直接套第 5 节的公式算。
 
-每批到货时算三样：最近一个周期（上一批到货到这一批到货）里每秒发出去多少，记作 rate。这一次取一批花了多久，记作 fetch_time。于是「取一批的时间里会要走多少」demand = rate × fetch_time，向上取整，再加上此刻还在排队的调用者数（他们是没被满足的需求）。然后下一批 B = 2 × demand（夹在最小和最大值之间），低水位 L = demand。这和第 5 节的 L = r·T、B 取 r·T 到 2r·T 是同一回事，只是 r 换成了实测值。
+每批到货时算三样：最近一个周期（上一批到货到这一批到货）里每秒发出去多少，记作 rate。这一次取一批花了多久，记作 fetch_time。于是「取一批的时间里会要走多少」$\mathit{demand} = \mathit{rate} \times \mathit{fetch\_time}$，向上取整，再加上此刻还在排队的调用者数（他们是没被满足的需求）。然后下一批 $B = 2 \times \mathit{demand}$（夹在最小和最大值之间），低水位 $L = \mathit{demand}$。这和第 5 节的 $L = r \cdot T$、B 取 $r \cdot T$ 到 $2r \cdot T$ 是同一回事，只是 r 换成了实测值。
 
 ```python
@@ -433,12 +433,12 @@
 起步时 B 会成倍往上长。缓冲区一直见底的时候，一个周期里发出去的正好是上一批那么多，周期也约等于一次取一批的时间，所以 demand 约等于「上一批 + 排队的人」，下一批是它的两倍。这和 TCP 的慢启动（slow start：连接刚建立时发送窗口很小，每一轮往返翻一倍）是一个样子，代价也一样：前几个周期调用者要等。知道大致需求的话，把 `min_batch` 设高一点就好。
 
-需求稳定在 r 时，demand = ⌈r × fetch_time⌉。fetch_time 总比 T 多一点（sleep 和线程调度的开销），r·T 恰好是整数时向上取整就多出 1：r = 500、T = 100 ms 时 demand = 51，B 稳定在 102。r = 100 时 demand = 11，B 稳定在 22。需求跳上去的那几个周期，排队的人把 demand 推得比稳定值大，B 会冲过头再落回来。`max_batch` 防止它无限涨，多取的那些放着慢慢发，不会丢。轨迹见测试用例「自适应批量」。
+需求稳定在 r 时，$\mathit{demand} = \lceil r \times \mathit{fetch\_time} \rceil$。fetch_time 总比 T 多一点（sleep 和线程调度的开销），$r \cdot T$ 恰好是整数时向上取整就多出 1：r = 500、T = 100 ms 时 demand = 51，B 稳定在 102。r = 100 时 demand = 11，B 稳定在 22。需求跳上去的那几个周期，排队的人把 demand 推得比稳定值大，B 会冲过头再落回来。`max_batch` 防止它无限涨，多取的那些放着慢慢发，不会丢。轨迹见测试用例「自适应批量」。
 
 ### 3. 需求超过供给：并行取一批
 
-第 5 节说过，`get_block_id` 一次只能被一个线程调时，供给上限是每秒 B/T 个。需求长期超过它，缓冲区必然见底，任何单线程生产者都救不了，只能从两处下手：
+第 5 节说过，`get_block_id` 一次只能被一个线程调时，供给上限是每秒 $B/T$ 个。需求长期超过它，缓冲区必然见底，任何单线程生产者都救不了，只能从两处下手：
 
 - **一次多取**：主版本的 `get_block_id(count)` 和变体 C 的 `get_ids(num_of_id, buf)` 都能指定数量，每次调用还是 T，那就加大 B，供给随 B 线性增长。代价是第 2 节说的浪费和内存。变体 B 固定 100 个，没有这条路。
-- **并行取**：如果分配器允许几个线程同时调（这要先问，题目一节的表），就开 k 个生产者线程，供给变成每秒 k·B/T。缓冲区和两个条件变量不用改：每个生产者各自判断「长度不大于 L 才取」，所以会有几个线程同时在取，到货后缓冲区最多 L + k·B 个。但 `close()` 要改两处：`_need_refill.notify()` 换成 `notify_all()`，并且 join 每一个生产者线程。不改的话只有一个生产者被叫醒退出，其余的一直睡在 `_need_refill.wait()` 里。被叫醒的要是恰好不是 `close()` 去 join 的那个，`close()` 自己也卡住（测试用例「多个生产者」）。要保序的话不能并行，两批谁先回来不确定。
+- **并行取**：如果分配器允许几个线程同时调（这要先问，题目一节的表），就开 k 个生产者线程，供给变成每秒 $k \cdot B/T$。缓冲区和两个条件变量不用改：每个生产者各自判断「长度不大于 L 才取」，所以会有几个线程同时在取，到货后缓冲区最多 $L + k \cdot B$ 个。但 `close()` 要改两处：`_need_refill.notify()` 换成 `notify_all()`，并且 join 每一个生产者线程。不改的话只有一个生产者被叫醒退出，其余的一直睡在 `_need_refill.wait()` 里。被叫醒的要是恰好不是 `close()` 去 join 的那个，`close()` 自己也卡住（测试用例「多个生产者」）。要保序的话不能并行，两批谁先回来不确定。
 
 两样都不允许，就如实告诉面试官：这是分配器的上限。
@@ -446,5 +446,5 @@
 ### 4. 退出时缓存里的 id 怎么办
 
-进程退出时缓冲区里没发出去的 id 就浪费了，最多 L + B 个，平均多少看需求。需求很低时，缓冲区从 L + B 慢慢降到 L 再补，平均约 L + B/2。需求稳定在 r、L ≥ r·T 时，一批在路上的 T 秒里会被要走 r·T 个，所以到货前剩 L − r·T 个、到货后多 B 个，平均约 L − r·T + B/2。取第 5 节的 L = r·T 就是 B/2。减少浪费的办法只有把 B 和 L 定小一点（第 2 节），或者用 Follow-up 第 2 条让它在需求低时自己缩小。如果分配器提供「退回」接口，可以在 `close()` 里把剩的退回去，但这几篇面经里的接口都没有这个函数，不要替题目发明。可以作为一个问题问面试官。
+进程退出时缓冲区里没发出去的 id 就浪费了，最多 $L + B$ 个，平均多少看需求。需求很低时，缓冲区从 $L + B$ 慢慢降到 L 再补，平均约 $L + B/2$。需求稳定在 r、$L \ge r \cdot T$ 时，一批在路上的 T 秒里会被要走 $r \cdot T$ 个，所以到货前剩 $L - r \cdot T$ 个、到货后多 B 个，平均约 $L - r \cdot T + B/2$。取第 5 节的 $L = r \cdot T$ 就是 $B/2$。减少浪费的办法只有把 B 和 L 定小一点（第 2 节），或者用 Follow-up 第 2 条让它在需求低时自己缩小。如果分配器提供「退回」接口，可以在 `close()` 里把剩的退回去，但这几篇面经里的接口都没有这个函数，不要替题目发明。可以作为一个问题问面试官。
 
 ## 英文讲法
更新题目 getID：批量取号

body

meta
