短网址系统设计

引言

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

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

  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 框架来做熔断,并且将常用配置放到可以热更新的配置中心,方便对其实时更改。

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