更新题目 getID：批量取号
题目 everpure-get-id · 修改（rev 12） · · 2026-10-27 12:09
body
@@ -59,4 +59,6 @@ | 用什么语言？ | 帖子都没说（2017 年的发帖人主用 Java，变体 C 是 C 签名）。本页用 Python：`get_block_id(count) -> list[int]`、`get_one_id() -> int`，语法见 [[p:kb/python-concurrency]] | C/C++ 把锁和条件变量换成 `std::mutex`、`std::condition_variable`，结构一样 | +> [!say] Before I write anything: is the block call expensive, and is the cost mostly per call rather than per id? Must the ids be unique across calls, and can I hand them out in any order? Will get_one_id be called from multiple threads, and can the block call itself run concurrently? And do unused ids matter if the process exits? + ## 面经里怎么考的 @@ -111,4 +113,6 @@ 所以 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 条让它自己调。 + +> [!say] Version one just calls get_block_id with count one every time. Every call pays the full cost. Version two fetches a batch and serves from a cache, which amortizes the cost, but whoever triggers the refill still pays all of it, and a larger batch wastes more ids on exit. ### 3. 多线程：不加锁会发重复的 id，加锁之后补货让所有人等 @@ -156,4 +160,6 @@ 加锁版的代价是，补货的那次 `get_block_id` 在锁里，耗时 T。这 T 秒里每一个来调 `get_one_id` 的线程都停在拿锁那一行。按变体 B 的数（T = 1 s，每秒 100 次调用），每批发完时会有将近 100 个调用者排队，最早到的那个等将近 1 s。 + +> [!say] With multiple callers the check, the refill and the take must sit in one critical section. Otherwise two threads read the same slot and return the same id. Even with the lock, the slow call happens inside it, so during a refill everyone waits. #### 把补货挪到锁外，等待还是消不掉 @@ -253,4 +259,6 @@ `daemon=True` 让进程退出时不必等这个线程。实际的服务里还要 `close()`：置关闭标志、叫醒两边、等线程退出，之后的 `get_one_id` 直接报错，不会永远等（测试用例「关闭」）。 +> [!say] So I make it producer-consumer: a background thread refills the buffer whenever it drops to the low-water mark, calling get_block_id outside the lock. I use two condition variables on one lock, one for "not empty" that callers wait on and one for "need refill" that the producer waits on, so I wake exactly the party that needs to run. Callers block only when the buffer is truly empty, and the buffer never holds more than the mark plus one batch. + ### 5. 提前多少取：低水位怎么定（变体 B 的 follow-up） @@ -270,4 +278,6 @@ - **供给的上限。** 一次取 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（测试用例「突发」）。 + +> [!say] The low-water mark has to cover the demand during one fetch: at a hundred calls per second and a one-second fetch, that's a hundred ids. Keep one batch in hand while the next is in flight and nobody waits on steady demand. A burst bigger than the buffer plus the batch in flight still waits, possibly for more than one fetch. ## 代码 @@ -435,4 +445,6 @@ 需求稳定在 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` 防止它无限涨，多取的那些放着慢慢发，不会丢。轨迹见测试用例「自适应批量」。 +> [!say] If the fetch can fail, the producer must retry with backoff rather than die, otherwise every caller blocks forever with no error. And if demand can change, I size the next batch from the measured consumption rate, a bit like TCP adjusting its window, except I can measure demand directly. + ### 3. 需求超过供给：并行取一批 @@ -447,16 +459,2 @@ 进程退出时缓冲区里没发出去的 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()` 里把剩的退回去，但这几篇面经里的接口都没有这个函数，不要替题目发明。可以作为一个问题问面试官。 - -## 英文讲法 - -> [!say] Before I write anything: is the block call expensive, and is the cost mostly per call rather than per id? Must the ids be unique across calls, and can I hand them out in any order? Will get_one_id be called from multiple threads, and can the block call itself run concurrently? And do unused ids matter if the process exits? - -> [!say] Version one just calls get_block_id with count one every time. Every call pays the full cost. Version two fetches a batch and serves from a cache, which amortizes the cost, but whoever triggers the refill still pays all of it, and a larger batch wastes more ids on exit. - -> [!say] With multiple callers the check, the refill and the take must sit in one critical section. Otherwise two threads read the same slot and return the same id. Even with the lock, the slow call happens inside it, so during a refill everyone waits. - -> [!say] So I make it producer-consumer: a background thread refills the buffer whenever it drops to the low-water mark, calling get_block_id outside the lock. I use two condition variables on one lock, one for "not empty" that callers wait on and one for "need refill" that the producer waits on, so I wake exactly the party that needs to run. Callers block only when the buffer is truly empty, and the buffer never holds more than the mark plus one batch. - -> [!say] The low-water mark has to cover the demand during one fetch: at a hundred calls per second and a one-second fetch, that's a hundred ids. Keep one batch in hand while the next is in flight and nobody waits on steady demand. A burst bigger than the buffer plus the batch in flight still waits, possibly for more than one fetch. - -> [!say] If the fetch can fail, the producer must retry with backoff rather than die, otherwise every caller blocks forever with no error. And if demand can change, I size the next batch from the measured consumption rate, a bit like TCP adjusting its window, except I can measure demand directly.