java面试场景题:QPS 短链系统怎么设计

以下是对文章的润色版本：

---

这道场景设计题，初看似乎业务简单，实则覆盖的知识点极为丰富：

• 高并发与高性能分布式 ID 生成机制；
• Redis Bloom Filter——高并发、低内存损耗的过滤组件知识；
• 分库、分表海量数据存储架构；
• 多级缓存策略；
• HTTP 传输原理；
• 二进制、十六进制、六十二进制知识。

总体而言，高并发、高性能系统的核心领域几乎都涵盖其中。经过深入分析，可以得出结论：这是一个极具价值的问题。

在互联网传播和引用中，短网址常被用来替代长 URL。例如 QQ 微博的 url.cn、新浪的 sinaurl.cn 等。在 QQ、微博等平台上发布网址时，系统会自动识别并将其转换为短网址，如 url.cn/2hytQx。这种做法的原因主要有以下几点：

1. 缩短地址长度，为有意义内容留出更多空间：原始 URL 往往较长，占用大量有效屏幕空间，尤其是对于微博这类字数受限的平台（如微博单条限制 140 字），过长的链接会占据内容篇幅的一半甚至更多，严重影响信息展示。短网址的出现，使得在有长度限制的平台上发布内容时，可编辑的文字数量得以增加。
2. 有效管控原始 URL 内容：部分网址可能包含不良信息，如暴力、广告等。通过用户的举报，我们可以对这些 URL 进行管理，使其不再出现在应用中。因为相同的 URL 经过加密算法处理后，得到的短网址是相同的，便于统一管控。
3. 便于对原始 URL 进行行为分析：通过对一系列网址的流量、点击等数据进行统计分析，可以挖掘出大多数用户关注的焦点，从而为项目的后续决策提供有力支持。

此外，短网址还具有以下优势：
4. 间接提高带宽利用率，节约成本；
5. 在某些平台上，过长的链接无法自动识别为超链接；
6. 短链接更加简洁、美观且安全，不暴露访问参数，还能规避关键词、域名屏蔽等手段。

短 URL 系统的核心在于将长 URL 转化为短 URL。客户端访问系统时，短 URL 的工作流程如下：

1. 客户端使用短地址 A 访问短链 Java 服务；
2. 短链 Java 服务进行地址转换和映射，将短 URL 映射到对应的长地址 URL；
3. 短链 Java 服务返回 302 重定向给客户端；
4. 客户端再重定向到原始服务。

那么，原始 URL 是如何变短的呢？简单来说，可以使用编号替代原始地址，而编号可以通过使用更大的进制来表示，从而进一步缩短长度。

1. 短 URL 系统的背景

2. 短 URL 系统的原理

六十二进制表示法：顾名思义，短网址是非常短的网址，如 xxx.cn/EYyCO9T，其中核心部分 EYyCO9T 只有 7 位长度。这 7 位长度是使用 62 进制表示的，即常用的 0-9、a-z、A-Z，共 10 个数字 + 26 个小写 + 26 个大写 = 62 位。

那么，7 位长度的 62 进制可以表示多大的范围呢？短网址的长度可以根据需要调整，如果需要更多范围，可以增加位数。即使 6 位长度的 62^6 也能达到 568 亿的范围。只要算法得当，可以覆盖很大的数据范围。

在编码过程中，可以根据需求调整 62 进制各位的含义。例如，在编码过程中，如果不想让人明确知道转换前的内容，可以进行弱加密。

• 62^7 = 3,521,614,606,208（合计 3.5 万亿）
• 10 进制最多只能生成 10^6 - 1 = 999,999 个
• 16 进制最多只能生成 16^6 - 1 = 16,777,215 个
• 16 进制中已经包含了 A、B、C、D、E、F 这几个字母
• 62 进制最多能生成 62^6 - 1 = 568,002,355,833 个，基本足够使用

A-Z、a-z、0-9 正好等于 62 位。

注意：

• int（4 个字节），存储范围是 -21 亿到 21 亿；
• long（8 个字节），存储范围是 -900 万万亿到 900 万万亿。

例如，A 站点将字母 c 表示为 32，B 站点将字母 c 表示为 60，这就相当于一种“密码本”。标准 ASCII 码也叫基础 ASCII 码，使用 7 位二进制数（剩下的 1 位二进制为 0），包含 128 个字符。看到这里，你或许会问，如果使用 128 进制（如果有的话），网址岂不是更短？确实如此。

7 位二进制数（剩下的 1 位二进制为 0）可以表示所有的大写和小写字母、数字 0 到 9、标点符号，以及在美式英语中使用的特殊控制字符。假设短地址长度为 8 位，62 的 8 次方足够一般系统使用。

3. 短 URL 系统的功能分析

系统核心实现包含三大功能模块：发号与存储模块、映射模块。

发号与存储模块：

• 发号：使用发号器为每个长地址分配一个号码 ID，并防止地址歧义，即防止同一个长地址多次请求得到的短地址不一样。
• 存储：将号码与长地址存放在数据库中，将号码转化为 62 进制，用于表示最终的短地址，并返回给用户。

映射模块：

• 用户使用 62 进制的短地址请求服务。
• 转换：将 62 进制的数转化为 10 进制，因为系统内部使用的是 long 类型的 10 进制数字 ID。
• 映射：在数据库中寻找对应的长地址。
• 通过 302 重定向，将用户请求重定向到对应的地址上。

回顾一下发号器的功能：为每个长地址分配一个号码 ID，并防止地址歧义。

以下是对目前流行的分布式 ID 方案的简单介绍：

方案 1：使用地址的 hash 编码作为 ID

• MD5 算法：MD5 消息摘要算法（MD5 Message-Digest Algorithm）是一种被广泛应用的密码散列函数，可以产生一个 128 位（16 字节）的散列值（hash value）。MD5 算法将数据（如一段文字）运算变为另一个固定长度值，这是散列算法的基础原理。该算法由美国密码学家 Ronald Linn Rivest 设计，于 1992 年公开，并在 RFC 1321 中被加以规范。
• CRC 算法：循环冗余校验（Cyclic Redundancy Check）是一种根据网络数据包或电脑文件等数据，产生简短固定位数校验码的散列函数，由 W. Wesley Peterson 于 1961 年发表。生成的数字在传输或存储之前计算出来并附加到数据后面，然后接收方进行检验以确定数据是否发生变化。由于该函数易于用二进制的电脑硬件使用、容易进行数学分析，并且尤其善于检测传输通道干扰引起的错误，因此获得广泛应用。
• MurmurHash：MurmurHash 是一种非加密型哈希函数，适用于一般的哈希检索操作。由 Austin Appleby 于 2008 年发明，并出现了多个变种。与其他流行的哈希函数相比，对于规律性较强的键，MurmurHash 的随机分布特征表现更良好。该算法已被许多开源项目使用，如 libstdc++（4.6 版）、Perl、nginx（不早于 1.0.1 版）、Rubinius、libmemcached、maatkit、Hadoop、Redis、Memcached、Cassandra、HBase、Lucene 等。MurmurHash 计算可以是 128 位、64 位、32 位，位数越多，碰撞概率越少。因此，可以对长链进行 MurmurHash 计算，得到一个整数哈希