引言
短网址系统负责将某个长网址缩短为一个很短的网址，用户通过访问这个短网址可以重定向到原本的长网址。
现在的很多链接由于需要带上很多参数来提供业务所需的数据，所以往往非常冗长，而相应地转换成短网址后能带来很多益处：
- 在分发和使用的时候更方便、清爽
- 更好地适应微博、短信等有字数限制的场景
- 降低生成二维码的复杂度，提升扫码识别率
- 可以一定程度上隐藏部分参数，比如 aff 等
- 能够实现链接跳转的跟踪和各维度数据统计
- 原网址失效后可以不改变短网址，只修改跳转关系
- 个性短网址更有利于品牌建设和营销
短网址系统的设计核心有三点：
- 发号器如何设计，即如何生成不重复的短链接
- 重定向过程
- 存储系统设计
本文将围绕这三点依次展开论述。
发号器的设计
对于每一个长链接转短链地址时，都必须生成一个全局唯一的短链值，不然就会发生冲突。关于如何生成全局唯一短链通常有以下思路:
- 利用雪花算法得到一个全局唯一ID，然后使用不可逆哈希算法对ID进行哈希，得到对应的字符串，将此字符串作为短链结果。
- 优点: 雪花算法生成的唯一ID，不依赖于数据库或者Redis，同时支持分布式，性能更好。
- 缺点: 由于哈希映射结果可能会发生冲突，所以对哈希算法要求比较高。
- 还是基于雪花算法生成全局唯一ID，然后根据ID生成62进制（a-zA-Z0-9）的短码，为了避免生成的短码有规律，我们先反转ID，然后再转换成62进制。最终生成的短码是无规律的。避免被恶意识别。一个亿的数字转换后也就五六位（1亿 -> zAL6e），将短链接服务器域名，与这个字符串进行拼接，就能得到短链接的 URL，比如：t.cn/zAL6e 。
- 自增ID，但是生成自增 ID 需要考虑性能影响和并发安全性，所以我们可以通过 Redis 的 incr 命令来做一个发号器，它是一个原子操作，因此我们不必担心数字的安全性。而 Redis 是内存操作，所以效率也挺高
- 除了自增 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
针对该表主要有两个查询需求：
- 根据原始网址生成短码，可以根据url_hash查询数据库，如果有存在的，更新过期时间，直接返回。
- 用户点击短码，查询数据库，有记录，返回301重定向到实际的网址。
整体流程如下:
- 指定的服务器调用 短网址服务 对普通网址生成一个短网址；
- 根据普通网址进行MD5 Hash生成一个MD5码；
- 根据MD5码（索引）和网址从数据库里面查询短网址记录；
- 有记录就把更新过期时间，并直接返回；
- 无记录则使用雪花算法生成一个分布式唯一ID，反转ID，并转换成62进制；
- 完整映射记录写入数据库并返回
高并发优化
缓存
短网址系统的特点是：
- 数据存储量很大，全国的网址每天至少都是百万个短链接地址需要生成；
- 并发量也不小，遇到同时来访问系统，按一天 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 框架来做熔断，并且将常用配置放到可以热更新的配置中心，方便对其实时更改。
当业务量过大时，将同步任务改为异步任务处理。通过这些服务治理方案，让系统更加稳定。
