Amazon LFU：O(1) 频率桶与分布式数据流追问

题意与假设

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

• 训练容量≥0，get命中与put已有key都频次+1，新key freq1；同频按LRU淘汰。
• 示例get miss为None，训练值不使用None；需要任意值应另返回found标记。无TTL，不隐式加入expiry。
• 代码复用已有Salesforce LFU标准训练实现，Amazon来源单列；分布式讨论是额外设计，不宣称代码本身跨机器。

解题路线

1. 状态values/frequency两个map，freq→OrderedDict桶，minimum_frequency。桶内从最旧到最新，get/更新把key从f桶移f+1桶末尾。
2. 如果旧最小f桶因touch变空，新的最低freq可置f+1，因为这个被移动key立即在f+1桶，其他未动key原freq≥f。不能简单对任何删除/TTL也这样推。
3. 新key满容量时从最小频桶pop最旧，然后新key freq1、minfreq=1；capacity0直接忽略put。不要全表扫描求min，否则不是O(1)基线。
4. 全局锁可使get频次更新与put淘汰原子。很多读并不是只读，因为命中也写频率/LRU；读写锁若把get当纯读会坏状态。
5. 按key分片可以本地LFU、消息按key路由及去重，容量每shard明确。但全局最低频key需要协调，不能把每片最低当精确全局最低；选择近似/局部淘汰时报告语义变化。
6. 长数据流历史频次会让旧热门长期受保护，可加衰减、epoch或近似计数但定义改变，需评估命中率与新热点切换成本。重试请求是否算访问要由业务合同核对。

手动走一遍

训练capacity2：put a、put b各freq1；get a使freq2；put c淘汰freq1的b。a/c后来同freq时淘汰桶里最久未触及者，不按字母或最早创建固定淘汰。

Python 参考实现

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

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

from collections import OrderedDict, defaultdict


class LFUCache:
    """Least frequency first, LRU among keys with equal frequency."""

    def __init__(self, capacity: int):
        if capacity < 0:
            raise ValueError("capacity must be nonnegative")
        self.capacity = capacity
        self.values = {}
        self.frequency = {}
        self.buckets = defaultdict(OrderedDict)
        self.minimum_frequency = 0

    def _touch(self, key) -> None:
        old_frequency = self.frequency[key]
        del self.buckets[old_frequency][key]
        if not self.buckets[old_frequency]:
            del self.buckets[old_frequency]
            if self.minimum_frequency == old_frequency:
                self.minimum_frequency += 1
        new_frequency = old_frequency + 1
        self.frequency[key] = new_frequency
        self.buckets[new_frequency][key] = None

    def get(self, key):
        if key not in self.values:
            return None
        self._touch(key)
        return self.values[key]

    def put(self, key, value) -> None:
        if self.capacity == 0:
            return
        if key in self.values:
            self.values[key] = value
            self._touch(key)
            return
        if len(self.values) == self.capacity:
            oldest_key, _ = self.buckets[self.minimum_frequency].popitem(last=False)
            del self.values[oldest_key]
            del self.frequency[oldest_key]
            if not self.buckets[self.minimum_frequency]:
                del self.buckets[self.minimum_frequency]
        self.values[key] = value
        self.frequency[key] = 1
        self.buckets[1][key] = None
        self.minimum_frequency = 1

复杂度

单机get/put期望O(1)，O(capacity)key与桶状态；频次数字位宽可随总访问增长。分布式成本含路由与协调，单机O(1)并不能推出跨网络端到端O(1)时间。

易错点与追问

容易失分的边界

• get命中不更新频次。
• 每次全表找最小。
• 任意删最小桶都min+1忽略频率空洞。
• 每片LFU声称精确全局LFU。

继续深挖

• 加TTL怎样维护minfreq而不扫全表？
• 历史频率衰减如何更新桶？
• 热门key集中一shard如何分流？