原文链接：The secret architecture behind “username already taken”

当你在 Instagram 等平台上注册并输入用户名时，系统几乎能立即告诉你该用户名是否可用。如果已被占用，它甚至会即时提供替代建议。

对于只有几千用户的小型初创公司来说，这项检查很简单——只需查询数据库即可。但对于像 Instagram、Google 或 X（前身为 Twitter）这样拥有数十亿用户的平台而言，这一挑战要艰巨得多。

它们不可能在每次有人注册时都扫描数十亿条记录。

那么，它们如何能在眨眼间完成这项工作的呢？

在本文中，我们将深入探讨这些系统的构建历程，从最基本的方法开始，逐步升级到大科技公司所使用的复杂架构。

第一层：直接查询数据库

检查用户名是否存在的最直接方法是查询数据库：

SELECT COUNT(1)
FROM users
WHERE username = "new_user";

如果计数大于零，则该用户名已被占用。如果为零，则该用户名可用。

对于拥有数千甚至几百万用户的小型系统来说，这种方法完全可行。一个索引良好的关系型数据库可以在几毫秒内返回结果。

但是，一旦扩展到数亿甚至数十亿用户，并且分布在多个服务器和数据中心时，情况就开始变得非常不同。

  • 索引变得庞大：即使使用 B 树或哈希索引等高效数据结构，扫描和维护它们也需要更长时间。
  • 数据库不堪重负：每次注册尝试都意味着另一次查询，给本已繁忙的系统带来沉重的读取流量。

简而言之：虽然直接查询精确且易于实现，但它们根本无法扩展到大型科技公司的需求。面对数十亿条记录，这种方法很快就会陷入停滞。

第二层：添加缓存

下一个自然的优化是缓存。

与其每次用户尝试新用户名时都查询数据库，不如将频繁检查的用户名临时保存在内存中（使用 Redis 或 Memcached 等工具）。

缓存架构

工作流程如下：

  1. 用户输入用户名：请求首先发送到应用服务器。
  2. 缓存检查（主要）：系统检查缓存中是否最近查询过该用户名。
    • 如果找到 → 立即返回结果（无需接触数据库）。
    • 如果未找到 → 继续查询数据库。
  3. 数据库检查（后备）：如果缓存未命中，应用查询数据库以获取权威结果。
  4. 更新缓存（未来优化）：数据库返回答案后，系统更新缓存，以便下次有人检查相同用户名时，可以立即从内存中提供。

这对于经常检查的用户名非常有效。例如，如果成千上万的人不断尝试像 john、alex 或 princess 这样的名称，缓存可以立即提供这些请求，而根本无需接触数据库。

但是，缓存也引入了新的权衡：

  • 内存有限：你不可能永远将数十亿用户名存储在内存中，成本太高。系统通常依赖 LRU（最近最少使用）等驱逐策略，只保留”热门”条目。
  • 数据过期：如果用户名变得可用（例如用户删除其账户），但缓存未及时更新，系统可能会错误地认为它仍被占用。这通常通过 TTL（生存时间）值来解决，以便缓存数据最终过期。
  • 缓存未命中：独特的用户名在首次查询时仍必须一直访问到数据库。

第三层：使用布隆过滤器

如果有一种方法可以快速排除大部分可用性检查，从而减少对缓存和数据库的调用，那会怎样？

与其每次都在内存中显式存储每个用户名或每次都查询数据库，不如存储一个紧凑的”指纹”，它可以告诉我们用户名是否可能存在？

这正是布隆过滤器（Bloom Filter）的设计目的。

什么是布隆过滤器？

布隆过滤器是一种概率数据结构，可以非常快速地回答这个问题：“这个用户名可能存在吗？”

  • 如果过滤器说不，你可以100% 确定该用户名不存在。
  • 如果过滤器说是，该用户名可能存在，你需要在缓存或数据库中进行二次检查。

布隆过滤器以微小的假阳性概率换取极高的速度和内存效率。

  • 空间高效：使用约 1.2 GB 内存，布隆过滤器可以表示约 10 亿个用户名，假阳性率仅为 1%。
  • 快速：检查内存中的几个比特比访问缓存或数据库快得多。

布隆过滤器的工作原理

初始化：布隆过滤器开始时是一个大型比特数组，全部设置为 0。

布隆过滤器初始化

添加用户名：

假设用户注册了 new_user。

  1. 用户名通过几个不同的哈希函数（比如 3-10 个）运行。
  2. 每个哈希函数产生比特数组中的一个位置，这些位置被翻转为 1。

添加用户名到布隆过滤器

检查用户名：

当有人稍后尝试 new_user 时，应用相同的哈希函数。

系统检查相应的比特：

  • 如果任何比特是 0，则该用户名肯定从未见过 → 它可用。
  • 如果所有比特都是 1，则该用户名可能被占用。

检查用户名

为什么布隆过滤器如此强大

有时，新用户名的哈希位置可能与其他用户名设置的位置重叠。这意味着过滤器可能会说”可能被占用”，而实际上该用户名是免费的。

这就是为什么布隆过滤器总是会在假阳性时（约 1% 的请求）跟随缓存或数据库检查以进行确认。

将所有这些结合在一起

当你输入 my_cool_username 并按回车键时，在大型系统背后会发生以下情况：

完整架构

  1. 负载均衡器：你的请求首先到达负载均衡器，它将请求路由到最近或最空闲的服务器。

  2. 布隆过滤器检查：服务器首先检查内存中的布隆过滤器。

    • 如果布隆过滤器说”肯定未被占用”，服务器立即返回响应”可用！”
    • 大多数用户名都是唯一的，因此绝大多数请求到此为止，无需接触缓存或数据库。

  3. 缓存检查（如果布隆过滤器说”可能被占用”）：如果布隆过滤器说”可能被占用”，系统会查询分布式缓存（Redis/Memcached）。

    • 如果最近检查过该用户名，缓存会立即返回权威答案。

  4. 数据库检查（最后手段）：只有当缓存也未命中时，请求才会进入主数据库。

    • 这不是单一机器，而是分布在数千台服务器上的分布式系统（Cassandra、DynamoDB 或 Spanner）。
    • 在底层，像 B+ 树这样的索引结构保持高效的查找——即使在大规模下也是 O(log n)。

  5. 返回并缓存：

    • 数据库返回最终的 是/否。
    • 在返回的路上，结果被写入缓存，以便下次查找相同用户名时立即可用。

这种分层方法就像一个漏斗，每一步都过滤掉大量请求，确保只有一小部分需要”昂贵”地访问主数据库。

查找流程统计

第四层：超越基本查找

到目前为止，我们一直在谈论简单的是/否检查：这个用户名存在还是不存在？

但像 Instagram 这样的现实世界平台做得更多。如果你的首选被占用，它们还会建议替代用户名。

以用户名 daniel 为例。如果它已被占用，Instagram 可能会建议：

  • daniel_dev
  • daniel_123
  • daniel2025
  • dan_iel

这些功能需要比缓存或布隆过滤器更智能的东西。它们依赖于一种专门为基于前缀的查找而设计的数据结构：Trie（前缀树）。

什么是 Trie？

Trie 是一种树状结构，通过共享前缀组织字符串。Trie 不会将用户名存储为完整的单词，而是将它们逐个字符地分解，重用共享路径。

例如：

  • daniel 变成 d → a → n → i → e → l
  • danny 在分支到 n → y 之前共享路径 d → a → n

Trie 结构

Trie 解锁了数据库和缓存难以实现的功能：

  • 快速查找：检查用户名是否存在所需的时间仅与字符串长度成比例（O(M)），而不是用户名总数。
    • 对于 “daniel”，即使系统中有数十亿用户名，也只需 6 步。
  • 自动补全：通过跟随部分路径，Trie 可以立即列出以给定前缀开头的所有用户名（例如 “dan”）。
  • 建议：由于相似的用户名共享公共路径，生成像 daniel_dev 或 daniel2025 这样的替代方案变得简单高效。

Trie 也有权衡：

  • 内存消耗大：如果用户名没有共享太多前缀，Trie 分支可能会急剧增长，消耗大量内存。
  • 更新开销：在分布式环境中实时插入或删除用户名需要仔细同步。

为了减少内存使用，通常使用压缩 Trie（也称为基数树）。压缩 Trie 不是将每个字符存储为一个节点，而是将单子节点链折叠成一条边。这节省了空间和查找步骤，使结构在大规模下更加实用。

希望这篇文章对你有所帮助！

本文为学习目的的个人翻译，译文仅供参考。

原文链接：The secret architecture behind “username already taken”。

版权归原作者或原刊登方所有。本文为非官方译本；如有不妥，请联系删除。