短网址系统设计

引言

短网址系统负责将某个长网址缩短为一个很短的网址，用户通过访问这个短网址可以重定向到原本的长网址。

现在的很多链接由于需要带上很多参数来提供业务所需的数据，所以往往非常冗长，而相应地转换成短网址后能带来很多益处：

1. 在分发和使用的时候更方便、清爽
2. 更好地适应微博、短信等有字数限制的场景
3. 降低生成二维码的复杂度，提升扫码识别率
4. 可以一定程度上隐藏部分参数，比如 aff 等
5. 能够实现链接跳转的跟踪和各维度数据统计
6. 原网址失效后可以不改变短网址，只修改跳转关系
7. 个性短网址更有利于品牌建设和营销

短网址系统的设计核心有三点：

1. 发号器如何设计，即如何生成不重复的短链接
2. 重定向过程
3. 存储系统设计

本文将围绕这三点依次展开论述。

发号器的设计

对于每一个长链接转短链地址时，都必须生成一个全局唯一的短链值，不然就会发生冲突。关于如何生成全局唯一短链通常有以下思路:

1. 利用雪花算法得到一个全局唯一ID，然后使用不可逆哈希算法对ID进行哈希，得到对应的字符串，将此字符串作为短链结果。

在这里插入图片描述

• 优点: 雪花算法生成的唯一ID，不依赖于数据库或者Redis，同时支持分布式，性能更好。
• 缺点: 由于哈希映射结果可能会发生冲突，所以对哈希算法要求比较高。

1. 还是基于雪花算法生成全局唯一ID，然后根据ID生成62进制（a-zA-Z0-9）的短码，为了避免生成的短码有规律，我们先反转ID，然后再转换成62进制。最终生成的短码是无规律的。避免被恶意识别。一个亿的数字转换后也就五六位（1亿 -> zAL6e），将短链接服务器域名，与这个字符串进行拼接，就能得到短链接的 URL，比如：t.cn/zAL6e 。
2. 自增ID，但是生成自增 ID 需要考虑性能影响和并发安全性，所以我们可以通过 Redis 的 incr 命令来做一个发号器，它是一个原子操作，因此我们不必担心数字的安全性。而 Redis 是内存操作，所以效率也挺高
3. 除了自增 ID 以外，我们还可以生成随机数再转 62 进制的方法来生成短链接。但是，由于随机数可能重复，因此我们需要用布隆过滤器来去重。
   • 布隆过滤器是一个巧妙设计的数据结构，它的原理是将一个值多次哈希，映射到不同的 bit 位上并记录下来。当新的值使用时，通过同样的哈希函数，比对各个 bit 位上是否有值：如果这些 bit 位上都没有值，说明这个数是唯一的；否则，就可能不是唯一的。
   • 当然，这可能会产生误判，布隆过滤器一定可以发现重复的值，但 也可能将不重复的值判断为重复值，误判率大概为 0.05%，是可以接受的范围，而且布隆过滤器的效率极高。
   • 因此，通过布隆过滤器，我们能判断生成的随机数是否重复：如果重复，就重新生成一个；如果不重复，就存入布隆过滤器和数据库，从而保证每次取到的随机数都是唯一的。

重定向过程

浏览器访问短链接服务时，根据短链地址取到原始 URL，然后进行网址重定向。我们通常有两种重定向方式：

• 一种是返回给浏览器 301 响应码永久重定向，让其后续直接访问真实的 URL 地址；
• 一种是 302 临时重定向，让浏览器当前这次访问真实 URL，但后续请求时还是根据短链地址访问。

虽然用 301 浏览器只需一次请求，后续可以直接从浏览器获取长链接，这种方法可以提升访问速度，但是它没法统计短链接的访问次数。

所以根据业务需要，我们一般选用 302 重定向。

• 301 永久重定向：浏览器会缓存映射关系，因此下次访问，浏览器会直接帮我们完成重定向，而不会再次访问我们的短链服务器了。
• 302 临时重定向: 浏览器不会缓存映射关系，因此下次访问，浏览器还是会将请求发送到我们的短链服务器，由我们的短链服务器告诉浏览器进行重定向操作。

存储系统设计

存储系统这块简单聊聊表结构的设计:

• 主键 id
• 短码 short_url
• 原始网址 original_url
• 原始网址MD5哈希值 url_hash
• 创建时间戳 create_time
• 过期时间戳 expire_time

针对该表主要有两个查询需求：

1. 根据原始网址生成短码，可以根据url_hash查询数据库，如果有存在的，更新过期时间，直接返回。
2. 用户点击短码，查询数据库，有记录，返回301重定向到实际的网址。

整体流程如下:

1. 指定的服务器调用 短网址服务 对普通网址生成一个短网址；
2. 根据普通网址进行MD5 Hash生成一个MD5码；
3. 根据MD5码（索引）和网址从数据库里面查询短网址记录；
4. 有记录就把更新过期时间，并直接返回；
5. 无记录则使用雪花算法生成一个分布式唯一ID，反转ID，并转换成62进制；
6. 完整映射记录写入数据库并返回

高并发优化

缓存

短网址系统的特点是：

1. 数据存储量很大，全国的网址每天至少都是百万个短链接地址需要生成；
2. 并发量也不小，遇到同时来访问系统，按一天 3600 秒来算，平均每秒至少上千个请求数；

因此目前的系统设计上，DB数据库会成为我们的性能瓶颈，为了提高并发性能，可以考虑引入缓存进行优化。

短链接和长链接的对应关系一般不会频繁修改，所以数据库和缓存的一致性通过简单的旁路缓存模式来保证：

• 读（Read）数据时，若缓存未命中，则先读 DB，从 DB 中取出数据，放入缓存，同时返回响应；
• 写（Write）数据时，先更新 DB，再删除缓存。

当用户需要生成短链接时，先到这个映射表中看一下有没有对应的短链接地址。有就直接返回，并将这个 key-value 的过期时间增加一小时；没有就重新生成，并且将对应关系存入这个映射表中。 缓存的淘汰策略可以选用：

• LRU：Least Recently Used，最近最少使用算法，最近经常被读写的短链地址作为热点数据可以一直存在于缓存，淘汰那些很久没有访问过的短链 key；
• LFU：Least Frequently Userd，最近最不频繁使用算法，最近访问频率高的短链地址作为热点数据，淘汰那些访问频率较低的短链 key。

但是，使用缓存也防止不了一些异常情况，比如“缓存穿透”。所谓缓存穿透，就是查询一个缓存和数据库中都不存在的短链接，如果并发量很大，就会导致所有在缓存中不存在的请求都打到 MySQL 服务器上，导致服务器处理不了这么多请求而阻塞，甚至崩溃。

所以，为了防止不法分子通过类似“缓存穿透”的方式来攻击服务器，我们可以采用两种方法来应对：

• 对不存在的短链地址加缓存，key 为短链接地址，value 值为空，过期时间可以设置得短一点；
• 采用布隆过滤器将已有的短链接多次哈希后存起来，当有短链接请求时，先通过布隆过滤器判断一下该地址是否存在数据库中；如果不在，则说明数据库中不存在该地址，就直接返回。

数据库和缓存高可用

数据库高可用:

• MySQL 数据库采用主从复制，进行读写分离。Master 节点进行写操作，Slave 节点用作读操作，并且可以用 Keepalived 来实现高可用。
• Keepalived 的原理是采用虚拟 IP，检测入口的多个节点，选用一台热备服务器作为主服务器，并分配给它一个虚拟 IP，外部请求都通过这个虚拟 IP 来访问数据库。
• 同时，Keepalived 会实时检测多个节点的可用状态，当发现一台服务器宕机或出现故障时，会从集群中将这台服务器踢除。如果这台服务器是主服务器，keepalived 会触发选举操作，从服务器集群中再选出一个服务器充当 master 并分配给它相同的虚拟 IP，以此完成故障转移。
• 并且，在 Keepalived 的支持下，这些操作都不需要人工参与，只需修复故障机器即可。

缓存高可用:

• 由于在大数据高并发的场景下，写请求全部落在 Redis 的 master 节点上，压力太大。如果一味地采用增加内存和 CPU 这种纵向扩容的方式，那么一台机器所面临的磁盘 IO，网络等压力逐渐增大，也会影响性能。
• 所以 Redis 采用集群模式，实现数据分片。并且，加入了哨兵机制来保证集群的高可用。它的基本原理是哨兵节点监控集群中所有的主从节点，当主节点宕机或者发生故障以后，哨兵节点会标记它为主观下线；当足够多的哨兵节点将 Redis 主节点标记为主观下线，就将其状态改为客观下线。
• 此时，哨兵节点们通过选举机制选出一个领头哨兵，对 Redis 主节点进行故障转移操作，以保障 Redis 集群的高可用，这整个流程都不需要人工干预。

系统容错

服务在上线之前，需要做好充分的业务量评估，以及性能测试。做好限流、熔断和服务降级的逻辑，比如：采用令牌桶算法实现限流，hystrix 框架来做熔断，并且将常用配置放到可以热更新的配置中心，方便对其实时更改。

当业务量过大时，将同步任务改为异步任务处理。通过这些服务治理方案，让系统更加稳定。