文章搜索

布隆过滤器说用户名存在,就不能注册了吗?

一次误判如何变成业务误拦截?从数据库唯一约束、事务 Outbox 到过滤器补偿,梳理注册链路的正确性边界。

布隆过滤器说用户名存在,就不能注册了吗?

题目与条件

注册时,布隆过滤器把尚未注册的用户名判断为“已经存在”,如何避免错误拦截?如果注册后更新过滤器失败,而且多次重试仍不成功,应该怎样处理?

这里补充一个解题假设:用户主数据存储在关系型数据库,Redis 中的布隆过滤器用于加速存在性判断。我们讨论的是唯一用户名注册,不把缓存当作最终裁决者。

先给出面试回答

布隆过滤器返回“可能存在”不能直接拒绝注册,必须回到数据库确认,最终用用户名唯一索引解决并发注册冲突。即使过滤器返回不存在,也不能绕过数据库的唯一约束。

用户记录写入与待同步事件应放在同一数据库事务中;后台根据 Outbox 事件更新过滤器,成功后标记事件完成。失败时有限重试、退避、告警与补偿;超出重试次数仍保留失败事件,不能当作同步成功。

过滤器失步期间,其“不存在”判断也不能用作数据库一定没有该用户名的证据。此时降级到数据库查询或直接尝试受唯一约束保护的插入,待重建与追平增量后再恢复信任。

先理解“可能存在”

标准布隆过滤器用多个哈希函数将元素映射到一组位。只要其中任意一位没有置位,就说明这个元素没有被加入当前过滤器;全部位都被置位,则可能是该元素,也可能是其他元素碰巧覆盖了这些位置。

这解释了为什么它会出现误判。但“理论上没有假阴性”依赖于目标集合中的元素已经成功加入、过滤器未损坏且使用方式正确。数据库已经提交、过滤器尚未同步时,二者代表的集合不同,不能把数据同步问题当成概率结构的保证。

注册链路应该如何走

存在性提示与最终写入裁决
查看流程图源码
flowchart TD
    A[规范化用户名] --> B{过滤器是否可信}
    B -->|可信| C{可能存在}
    B -->|失步或不可用| D[数据库确认 / 尝试插入]
    C -->|是| D
    C -->|否| E[尝试插入]
    D --> E
    E --> F{唯一约束是否通过}
    F -->|否| G[用户名已被占用]
    F -->|是| H[同一事务写用户与 Outbox]
    H --> I[提交并返回注册成功]
    I --> J[后台更新过滤器]
存在性提示与最终写入裁决 · 可放大查看

图中的数据库确认可用于提前给出友好提示,但“先查不存在,再插入”依旧存在竞争窗口;两个请求可能同时查到不存在。最终裁决始终是数据库唯一约束,不能用一次普通查询替代它。

核心数据结构与事务

以下是示意 SQL。实际项目要先统一用户名的大小写、Unicode 规范化和长度规则,使业务规范化与数据库唯一比较语义一致。

CREATE TABLE users (
  id BIGINT PRIMARY KEY,
  normalized_username VARCHAR(64) NOT NULL,
  UNIQUE KEY uk_username (normalized_username)
);

CREATE TABLE registration_outbox (
  event_id VARCHAR(64) PRIMARY KEY,
  normalized_username VARCHAR(64) NOT NULL,
  status VARCHAR(16) NOT NULL,
  attempts INT NOT NULL DEFAULT 0,
  next_retry_at DATETIME NOT NULL
);

START TRANSACTION;
INSERT INTO users (id, normalized_username)
VALUES (?, ?);
INSERT INTO registration_outbox
  (event_id, normalized_username, status, next_retry_at)
VALUES (?, ?, 'pending', NOW());
COMMIT;

如果用户插入因唯一键冲突失败,事务回滚,不再创建同步事件。若插入用户成功,但写事件失败,也要回滚整个事务。这样不会出现用户已经持久化、补偿任务却从未存在的断点。

Outbox 不是“数据库和 Redis 一起原子提交”。它保证的是业务提交后,有一条可持久重试的同步记录;数据库与过滤器之间依旧是最终同步,需要明确同步延迟和降级规则。

更新失败,为什么不能只说“重试三次”

后台工作者取出待处理事件,执行 BF.ADD,成功后将事件标记为完成。向同一个过滤器重复添加相同元素,不应被误认为创建了第二个用户;但若过滤器被替换,必须确认重放目标是当前正确版本。

存在一个常见故障窗口:Redis 实际更新成功,工作者还没标记 Outbox 已完成就崩溃。恢复后事件会再次执行,因此同步操作必须允许重复;不要依靠“工作者应该只跑一次”保证一致性。

故障对用户的处理对后台的处理
用户事务失败返回明确失败或可重试错误不发布同步成功事件
数据库成功,Redis 更新失败注册成功;数据库已是事实保留事件、退避重试,标记过滤器可能失步
多次重试失败后续查询降级到数据库告警、人工排障或重建,不丢弃事件
重建中继续使用可信旧版本或走数据库全量构建、追增量、原子切换版本

如果请求超时但数据库结果未知,应查询该次注册操作的状态,或用幂等请求键恢复结果;不能仅凭超时认定注册失败并无条件重复创建其他业务资源。

一个具体的误判例子

用户名 alice 尚不存在,但它映射的位已经被其他用户名全部置位。过滤器返回“可能存在”,服务查询数据库确认不存在,再执行插入。插入成功后,记录同步事件并返回成功。

若此时另一个请求也注册 alice,数据库唯一约束只允许其中一个事务插入成功。过滤器既不负责决定“谁赢”,也不应充当分布式锁。

反过来,如果数据库中已有 bob,但上次同步失败导致过滤器说“不存在”,最终插入仍会被唯一约束拒绝。注册唯一性没有被破坏,但如果登录查询或其他接口直接相信负结果,就可能产生错误,因此降级范围应覆盖所有依赖该过滤器的业务路径。

工程取舍与追问

  • 为什么不先写过滤器? 先加进过滤器、数据库又失败,会增加“可能存在”的误判;也不能解决两个系统不能原子提交的问题。
  • 能不能删除错误加入的用户名? 标准布隆过滤器不能随意清除位,否则可能影响其他元素。需要删除语义时,应评估计数布隆过滤器或其他结构,并独立核对并发与计数溢出问题。
  • 一定要上布隆过滤器吗? 不一定。普通注册接口可能直接受数据库写入吞吐与唯一检查约束;先测量查询成本、重复请求比例与负载,确认收益大于同步复杂度。
  • 如何测试? 人工构造误判,确认未注册用户仍可注册;同名并发注册只成功一次;注入 Redis 故障后用户记录与 Outbox 一致,恢复重放不会创建重复用户。

延伸阅读

本文为独立整理的参考方案。唯一约束、幂等和同步补偿分别解决不同问题,不应互相替代。