Instagram 十亿级“用户名已被占用”背后的架构设计

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

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

每次用户注册时，他们根本不可能逐条扫描数十亿条记录。

那么，他们是如何在眨眼间完成这一切的呢？

本文将逐步介绍这些系统的构建过程，从最基本的方法开始，逐步升级到大型科技公司采用的复杂架构。

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

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

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

很简单，对吧？

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

但一旦用户规模扩大到数亿甚至数十亿，并分布在多个服务器和数据中心，情况就会变得截然不同。

• 索引变得非常庞大：即使采用像B树或哈希索引这样高效的数据结构，扫描和维护这些索引也需要耗费很长的时间。

• 数据库过载：每次注册尝试都会触发一次查询，这会给本已繁忙的系统带来沉重的读取负担。

简而言之，虽然直接查询精确且易于实现，但它根本无法满足大型科技公司的需求。当数据量达到数十亿条记录时，这种处理方式很快就会陷入停滞。

下一个顺理成章的优化方向是缓存。

用户每次尝试新用户名时，我们不会每次都去数据库查询，而是将常用用户名的临时副本存储在内存中（使用Redis或Memcached等工具）。

典型流程如下：

1）用户输入用户名：请求首先发送到应用服务器。

2）缓存检查（主要）：系统检查缓存，查看该用户名最近是否被查询过。

• 如果找到→ 立即返回结果（无需访问数据库）。

• 如果未找到→ 继续在数据库中查找。

3）数据库检查（备用方案）：如果缓存未命中，应用程序将查询数据库以获取权威结果。

4）更新缓存（未来优化）：一旦数据库返回答案，系统就会更新缓存，以便下次有人检查相同的用户名时，可以立即从内存中获取该用户名。

对于经常被验证的用户名，这种方法非常有效。例如，如果成千上万的人不断尝试类似 john、alex或princess这样的用户名时，缓存系统可以立即响应这些请求，无需访问数据库。

但缓存带来了新的权衡取舍：

• 内存有限。你不可能永远把数十亿个用户名存储在内存里，成本太高。系统通常依赖于诸如最近Least Recently Used（LRU）之类的淘汰策略，只保留“活跃”条目。

• 数据过期。如果某个用户名重新可用（例如用户注销账户），但缓存没有及时更新，系统可能会错误地认为该用户名仍然被占用。这种情况下，通常使用time-to-live (TTL)值来解决这个问题，以便缓存的数据最终过期。

• 缓存未命中。即使是唯一的用户名，在首次查询时也需要从数据库获取。

现在事情变得有趣起来了。

与其每次都将每个用户名显式地存储在内存中或查询数据库，不如存储一个紧凑的“指纹”，用以判断某个用户名是否存在。

这正是布隆过滤器的设计用途。

布隆过滤器是一种概率数据结构，能快速判断用户名是否存在系统中。

• 如果筛选结果为“否”，则可以100%确定该用户名不存在。

• 如果显示“是” ，则该用户名可能存在，需要在缓存或数据库中再次核查。

布隆过滤器以极小的误报概率为代价，换取了极高的速度和内存效率。

• 节省空间：布隆过滤器只需约1.2 GB的内存即可存储约10亿个用户名，误报率仅为1% 。

• 速度快：读取内存中的少量数据，远比访问缓存或数据库要快得多。

它的运作方式如下：

1）初始化：布隆过滤器初始状态为一个全为0的大规模位数组。

2）添加用户名

• 假设用户注册了“new_user”。

• 用户名会经过几个不同的哈希函数（例如 3-10 个）进行运算。

• 每个哈希函数生成一个位数组中的位置，这些位置会被翻转1。

3）检查用户名

• 当其他人后续尝试时“new_user”，系统会采用相同的哈希函数。

• 系统会检查相应的位：

• 如果任何一位为 0 ，则该用户名肯定从未被见过 → 可用。

• 如果所有位均为 1 ，则该用户名可能已被占用。

4）陷阱：误报

• 有时，新用户名的哈希值可能与其他用户名的重叠。这意味着，即使用户名实际上是空闲的，过滤器也可能显示“可能已被占用”。

• 这就是为什么布隆过滤器之后总是会进行缓存或数据库检查以确认，以防出现误报（约占请求的1%）。

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

1）负载均衡器：你的请求首先会到达负载均衡器，负载均衡器会将请求路由到最近或最不繁忙的服务器。

2）布隆过滤器（初筛）

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

• 如果布隆过滤器显示“绝对未被占用”，服务器会立即返回响应“可用！”

• 大多数用户名都是唯一的，因此绝大多数请求都会在此处结束，无需访问缓存或数据库。

3）缓存检查（辅助检查）

• 如果布隆过滤器显示“可能已被占用” ，则系统会查询分布式缓存（Redis/Memcached）。

• 如果用户名最近被验证过，缓存系统会立即返回最终结果。

4）数据库检查（最终检查）

• 只有当缓存也未命中时，请求才会发送到主数据库。

• 这不是一台单机，而是一个分布在数千台服务器上的分布式系统（Cassandra、DynamoDB 或 Spanner）；

• 从底层来看，像B+树这样的索引结构能保持高效的查询性能：即使在大规模的情况下，O(log n)也是如此。

5）回复和更新

• 数据库返回最终的“是/否”结果。

• 返回过程中，结果会被写入缓存，因此下次查找同一用户名时会立即生效。

这种分层方法就像一个漏斗，每一层都会过滤掉大量的请求，确保只有极少一部分请求需要进行耗时耗力的主数据库访问。

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

但像Instagram这样的现实平台会做得更多：如果你的首选用户名已被占用，它们还会推荐其他用户名。

以用户名daniel为例，如果该用户名已被使用，Instagram 可能会建议：

• daniel_123

• daniel_dev

• daniel2025

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

什么是前缀树？

它是一种树状结构，根据字符串的共同前缀对其进行组织。它不会将用户名存储为完整的单词，而是逐个字符地分解，并重用共同的路径。

例如：

• daniel变成d → a → n → i → e → l。

• dannyd → a → n在分支到 . 之前共享路径n → y。

Tries尝试解锁数据库和缓存难以实现的一系列功能：

• 快速查找：检查用户名是否存在所需的时间仅与字符串的长度成正比（O(M)），而不是与用户名的总数成正比。

• 以用户名“daniel”为例，即便系统中存有数十亿个用户名，查询它也仅需 6 步。

• 自动补全：通过跟踪部分路径，trie可以立即列出所有以给定前缀开头的用户名（例如，“dan”）。

• 建议：由于相似的用户名共享共同路径，因此生成类似daniel_dev或的替代名称daniel2025变得容易且高效。

尝试也伴随着权衡：

• 内存消耗大：如果用户名没有很多共同的前缀，则 trie 分支可能会呈爆炸式增长，消耗大量内存。

• 更新开销：在分布式环境中实时插入或删除用户名需要谨慎同步。

为了降低内存使用，通常采用压缩字典树（也称为基数树）。

压缩尝试不是将每个字符都存储为一个节点，而是将单子节点链合并成一条边。

这种方法既节省空间，又减少查找步骤，使结构在规模化应用时更具实用性。