百亿级短链接系统设计：如何用 Redis + MurmurHash 实现高性能的“短网址生成器”？-育师

🔗 前言：面试官最爱问的“简单题”

“请设计一个短链接系统，像t.cn/AbCdEf这种。”
这道题在字节、阿里、腾讯的面试中出现的概率高达 80%。

很多初学者会不假思索地回答：“用 Redis 的INCR自增 ID，然后转成 62 进制不就行了？”
错！大错特错！

安全隐患：自增 ID 是连续的，黑客写个脚本t.cn/1,t.cn/2… 就能遍历你的所有数据，窃取商业机密。
性能瓶颈：严重依赖 Redis 单点计数器，难以水平扩展。

今天，我们来聊聊大厂主流的**“摘要算法生成法”**，利用MurmurHash + Base62，打造一个安全、无碰撞、可扩展的百亿级短链接系统。

🧠 核心原理：为什么是 MurmurHash？

要将一个长长的 URL 压缩成短字符串，本质上是一个Hash（摘要）过程。

1. 为什么不用 MD5？

MD5 生成的结果是 128 位（32 个字符），太长了！如果我们截取前 6 位，哈希冲突（Collision）的概率会爆炸式增长。

2. MurmurHash 的优势

Google 出品的MurmurHash算法，是目前非加密型 Hash 算法中的王者。

速度快：比 MD5 快几十倍。
雪崩效应好：输入微小的变化，输出巨大的差异。
32 位输出：MurmurHash32 返回的是一个整数，非常适合后续处理。

3. Base62 编码 (压缩的核心)

我们需要把 MurmurHash 算出的整数（比如394820123）转换成更短的字符串。
使用Base62（a-z, A-Z, 0-9 共 62 个字符）：

626≈56862^6 \approx 568626≈568亿
627≈3.562^7 \approx 3.5627≈3.5万亿

结论：只需 6 到 7 位字符，就足够容纳全世界的网页！

⚔️ 核心难点：如何解决“哈希冲突”？

这是这道题的致命考点。
虽然 MurmurHash 优秀，但在百亿量级下，冲突是必然的（抽屉原理）。即：
Hash(URL_A) == Hash(URL_B)

工业级解决方案：加盐双重探测

计算h = MurmurHash(LongURL)。
将h转为 Base62 字符串，即ShortURL。
查库校验：
- 去 Redis/DB 查这个ShortURL是否已存在。
- 情况 A (不存在)：完美，直接存入。
- 情况 B (存在，且长链接一致)：幂等，直接返回原短链。
- 情况 C (存在，但长链接不一致)：冲突爆发！
解决冲突：
- 给 LongURL 后面加一个特殊的“盐”（比如DUPLICATE）。
- 重新执行第 1 步：Hash(LongURL + "DUPLICATE")。
- 直到找到一个不冲突的位置。

🏗️ 架构设计：读写分离与多级缓存

在海量数据下，数据库存不下，Redis 存太贵。我们需要合理的架构。

架构流程图：

关键设计点：

布隆过滤器 (Bloom Filter)：在写入 DB 前，先用布隆过滤器判断短链是否存在。这能拦截 99% 的数据库查询，极大提升写入性能。
301 vs 302：
- 301 (永久重定向)：浏览器会缓存，减轻服务器压力，但无法统计点击量。
- 302 (临时重定向)：每次都请求服务器，适合做数据分析（大家一般都选这个）。

🛠️ 代码实战：Java 实现核心逻辑

引入 Google Guava 库来使用 MurmurHash。

<dependency><groupId>com.google.guava</groupId><artifactId>guava</artifactId><version>31.1-jre</version></dependency>

核心工具类：

importcom.google.common.hash.Hashing;importjava.nio.charset.StandardCharsets;publicclassShortLinkGenerator{// Base62 字符集privatestaticfinalStringBASE62="0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";/** * 将 10 进制转 62 进制 */publicstaticStringtoBase62(longnum){StringBuildersb=newStringBuilder();while(num>0){inti=(int)(num%62);sb.append(BASE62.charAt(i));num/=62;}returnsb.reverse().toString();}/** * 生成短链接 */publicStringgenerate(StringlongUrl){// 1. 使用 MurmurHash32 生成 32 位整数// 注意：需处理负数，转为 32 位无符号长整型longhash32=Hashing.murmur3_32_fixed().hashString(longUrl,StandardCharsets.UTF_8).padToLong();// 2. 转 Base62StringshortCode=toBase62(hash32);// 3. 解决冲突逻辑 (模拟)while(isConflict(shortCode,longUrl)){// 加盐重算longUrl+="[SALT]";hash32=Hashing.murmur3_32_fixed().hashString(longUrl,StandardCharsets.UTF_8).padToLong();shortCode=toBase62(hash32);}returnshortCode;}// 模拟数据库查询privatebooleanisConflict(StringshortCode,StringlongUrl){// 实际逻辑：// String existUrl = redis.get(shortCode);// return existUrl != null && !existUrl.equals(longUrl);returnfalse;}}