Netflix 同步 KV Store：细粒度锁与原子读改写

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练 API 为 get/put/delete/update(key,fn)，同一 key 的操作要求线性化；不同 key 可以并行。题目未明确这些具体函数名。
• key 可哈希，value 的更新函数在锁内同步执行且不得再次调用同一 store；异常时不提交新值。None 代表不存在，若业务要存 None 应用 sentinel 区分。
• 用固定 64 条锁按 `hash(key)%64` 映射，可能出现不同 key 共享锁的假冲突；这不是分布式 KV。

解题路线

1. 所有操作先按 key 定位同一把条带锁，再读/写底层 dict；复合 `get+put` 必须通过一次锁内 update 完成，单独调用两次不原子。
2. update 在锁中读取旧值、计算新值并写回，异常时不写；示例 `lambda old:(old or 0)+1` 在并发线程中不会丢增量。每 key 线性化点是持锁时的赋值或读取。
3. 测试同 key 千次并发递增、不同 key 并发、update 抛错、delete 与 put 竞态。生产系统还要评估热点 key、锁竞争、持久化、跨进程分片与重试；若需要多 key 原子事务，要按全局锁顺序或事务协议处理，不可声称此实现已有。

手动走一遍

训练例 counter=0，1000 个线程各执行 `update(counter, +1)`，最终为 1000。若线程各自 `get` 后再 `put`，可能同时读 0 后都写 1。两个不同 key 恰好落同一 stripe 会串行但仍正确，影响吞吐而非语义。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

from threading import Lock


class SynchronizedKV:
    """Per-key linearizable operations via striped locks; no cross-key transaction."""

    def __init__(self, stripes=64):
        if stripes <= 0:
            raise ValueError("stripes must be positive")
        self._values = {}
        self._locks = [Lock() for _ in range(stripes)]

    def _lock_for(self, key):
        return self._locks[hash(key) % len(self._locks)]

    def get(self, key):
        with self._lock_for(key):
            return self._values.get(key)

    def put(self, key, value):
        with self._lock_for(key):
            self._values[key] = value

    def delete(self, key):
        with self._lock_for(key):
            return self._values.pop(key, None)

    def update(self, key, function):
        with self._lock_for(key):
            new_value = function(self._values.get(key))
            self._values[key] = new_value
            return new_value

复杂度

单次操作在无严重争用时预期 O(1)，空间 O(K+S)，K 为 key 数、S 为固定条带锁数。热点 key 必然串行，吞吐上界由该 key 临界区耗时决定；多个 key hash 到同条带会额外争用。

易错点与追问

容易失分的边界

• 使用线程安全 map 后把两次操作误当原子读改写。
• 按 key 动态创建锁但无原子注册步骤，两个线程可能为同一 key 创建不同锁。
• 在锁内运行任意外部回调，发生阻塞或重入死锁；生产要限定回调。
• 把线程级同步扩展成跨进程/跨区域一致性保证。
• 未规定 None 是否是合法 value。

继续深挖

• key 热点很高时如何分解或改 API？
• 多 key transfer 如何加锁而避免死锁？
• 读多写少时 RWLock 是否一定更快？
• 持久化 ACK 后的状态如何恢复？