4. 去重数据结构实战

行情去重模块的核心矛盾在于：既要“记得住”已经见过的消息，又要“记得快、占得少”。单靠一种数据结构很难同时满足这三个要求，因此实际工程中通常是把多种结构组合成一个分层去重模块。本节围绕一个可落地的内存去重模块展开，先明确每种结构在行情场景中的职责边界，再给出组合实现与性能权衡的判断依据。

四种结构在行情去重中的定位

哈希表提供精确判重，是正确性的底线。行情消息通常带有唯一标识，例如交易所代码加序号（如 SH:20240612:000873421），或快照的 symbol + exchange_ts + seq 组合键。哈希表以该键为索引，能在 O(1) 平均时间内回答“这条消息是否已处理”。它的代价是内存随消息量线性增长，且需要处理哈希冲突与扩容抖动。

布隆过滤器用极低的内存给出“可能存在/一定不存在”的判断。它适合挡在哈希表前面的第一道闸门：对绝大多数重复消息直接返回“可能存在”，再交给哈希表精确确认；对确定没见过的消息则快速放行。需要注意，布隆过滤器只能插入不能删除，误判率随插入量上升，因此必须按时间窗口定期重建。

LRU 缓存解决的是“只记最近一段时间的键”。行情去重往往只关心秒级到分钟级的重复，太久以前的键保留价值低。LRU 以容量为界，淘汰最久未访问的键，天然把内存控制在固定上限，同时保留高命中率的近期热点。

滑动窗口针对的是“按序号连续性判重”的场景。很多行情通道的序号是单调递增的，重复往往表现为序号回退或落在已处理区间内。维护一个记录“已见序号区间”的滑动窗口，可以用很小的状态判断乱序与重复，尤其适合逐笔成交和增量快照。

组合模块的判重路径

一条消息进入模块后，推荐按“先廉价后昂贵”的顺序判断。第一步查布隆过滤器：若返回“一定不存在”，说明该键从未插入，直接放行并同步写入布隆过滤器与哈希表；若返回“可能存在”，则进入第二步查哈希表做精确确认，命中即判定为重复并丢弃，未命中则放行。第三步由 LRU 缓存承担内存上限控制：哈希表本身不设淘汰，但可以把“最近访问的键”同步进 LRU，当 LRU 达到容量时淘汰的键同时从哈希表中移除，从而让精确判重集合始终收敛在近期窗口内。滑动窗口则作为并行的序号校验通道，专门识别序号回退、区间内重复和缺口。

这里有一个容易踩的坑：布隆过滤器与哈希表的写入必须保持“先哈希后布隆”还是“先布隆后哈希”的一致性。若先写布隆再写哈希，中间发生异常会导致布隆认为“可能存在”而哈希查不到，消息被误放行一次；若先写哈希再写布隆，异常时哈希已存在而布隆未标记，消息会被哈希精确拦截，结果更安全。因此工程上应选择先写哈希表、再写布隆过滤器，把误判方向控制在“多拦一次”而非“漏放一次”。

关键实现片段

下面给出一个简化的 Python 结构示意，重点体现组合关系与写入顺序，参数为示例值，实际需按消息速率调整。

class DedupModule:
    def __init__(self, lru_capacity=500_000, window_size=4096):
        self.exact = {}                      # 哈希表：key -> 首次见到的时间
        self.bloom = BloomFilter(bits=1 << 24, hashes=4)
        self.lru = OrderedDict()             # 近似 LRU，记录访问顺序
        self.lru_capacity = lru_capacity
        self.window = SeqWindow(window_size) # 滑动窗口，按 symbol 维护

    def check(self, symbol, seq, key):
        # 1. 布隆快速否定
        if not self.bloom.might_contain(key):
            self._accept(symbol, seq, key)
            return "PASS"
        # 2. 哈希精确确认
        if key in self.exact:
            self._touch(key)
            return "DUP"
        self._accept(symbol, seq, key)
        return "PASS"

    def _accept(self, symbol, seq, key):
        self.exact[key] = time.time()   # 先写哈希
        self.bloom.add(key)             # 再写布隆
        self._touch(key)
        self.window.observe(symbol, seq)

    def _touch(self, key):
        self.lru[key] = True
        self.lru.move_to_end(key)
        if len(self.lru) > self.lru_capacity:
            old, _ = self.lru.popitem(last=False)
            self.exact.pop(old, None)   # LRU 淘汰同步清理哈希表

滑动窗口的 observe 需要处理三种情况：序号等于 high+1 时推进窗口；序号落在 [low, high] 内则查位图判断是否重复；序号大于 high+1 说明出现缺口，记录缺口区间并触发补拉，同时把窗口整体前移。窗口大小 4096 意味着只保留最近 4096 个序号的状态，超出部分视为过期，这与行情“重复主要发生在短时间窗口内”的假设一致。

性能权衡与选型判断

选型的核心判断依据是消息速率与可接受的内存上限。假设单条键约 40 字节，每秒 5 万条消息、需要覆盖 3 分钟窗口，则哈希表约需 900 万条、约 360 MB，明显偏大；此时用 LRU 把精确集合压到 50 万条（约 20 MB），再叠加 2 MB 的布隆过滤器，就能在保持高命中率的同时把内存降一个数量级。反过来，如果消息速率很低、内存充裕，直接使用哈希表加滑动窗口即可，引入布隆过滤器反而增加重建与误判处理的复杂度。

最后给出一个可执行的验收思路：构造一段包含 10% 重复、5% 乱序、1% 缺口的模拟消息流，分别统计放行数、丢弃数、缺口告警数，与理论值比对；同时记录模块的常驻内存与 P99 判重耗时。若丢弃数明显低于理论重复数，优先检查布隆写入顺序与 LRU 淘汰逻辑；若缺口告警虚高，则检查滑动窗口的推进条件是否把正常乱序误判为缺口。通过这三项指标，就能判断当前参数组合是否达到“不漏放、少误拦、内存可控”的目标。