侧边栏壁纸
博主头像
孤鸿

凡是过往,皆为序章

  • 累计撰写 38 篇文章
  • 累计创建 8 个标签
  • 累计收到 2 条评论

目 录CONTENT

文章目录

高性能短链接系统设计与实现

孤鸿
2022-06-24 / 0 评论 / 0 点赞 / 255 阅读 / 2,155 字 / 正在检测是否收录...

什么是短链接

短链接(短网址)指把一个长网址转化成一个相对较短的网址,并且访问这个较短的网址和访问较长的网址效果是一样的。

比如现在有个链接 https://www.bilibili.com/bangumi/media/md28223066,用新浪短链转化后为 https://t.hk.uy/aArZ,可以看到长度明显缩短了,但访问效果都是一样的。

为什么要用短链接

  1. url 看起来更简洁,对用户更友好
  2. 减少字符数量,比如微博等场景有字符限制
  3. 在某些业务场景可以显著节省成本(比如发短信的场景)
  4. 对提供出去的外部 url 统一管理,还可以做一些访问统计,用于数据分析

短链接的原理是什么

用户访问短链接时,短链系统把该 url 转化为真正的网址,并重定向到该地址

重定向用301还是302

  • 301 是永久重定向,响应是可缓存的
  • 302 是临时重定向,每次请求都会向原地址发出请求

一般推荐使用 301 来进行重定向,这样可以减轻短链接服务器的压力,但是如果有统计访问次数的需求,建议使用 302 重定向。

短链接的算法

自增序列

自增的方法实现很简单,我们可以直接使用 mysql 的自增 id 实现,也可以使用 redis 的 incr 函数。

通过自增得到了一个数字,需要将其转化成字符串,可以利用 0~9,a~z,A~Z,来设计一个 62 进制,如果最大用 6 位字符的话,则最大可以有 62^6 = 568 亿种,对于一般的系统都是够用了。

以下是一个简单的 62 进制转化算法

private static final String CHARS = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";

public static String convert(long num) {
    if (num < 0) {
      throw new IllegalArgumentException("num must gte zero:" + num);
    }
    StringBuilder sb = new StringBuilder();
    do {
      Long remainder = num % 62;
      sb.append(CHARS.charAt(remainder.intValue()));
      num = num / 62;
    } while (num > 0);
    // 如果需要固定长度,可以进行补位
    return sb.reverse().toString();
  }

需要注意的是,自增序列生成的短链接具备规律性,很容易被攻击,因此还是要根据自己的业务场景权衡是否使用这种方式。

自增序列的性能优化

如果我们用 redis 的 incr 函数来实现我们的自增序列,每次生成序列号都需要和 redis 交互有点略显浪费。

我们可以使用 incrby 函数为每次自增设置步长,批量获取序列号。

incrby key 1000

这样每次可以获取一批序列号,本地再结合 AtomicInteger 原子类使用这批序列号,使用完后再去 redis 里申请下一批。

哈希算法

哈希算法可以把任何大小的数据转化成一个固定长度的字符串,因此我们可以用 MD5, ShA-1 之类的算法对长链接算出一个哈希值,当然这个哈希值可能还有点长,使用的时候可以截取其中一部分。

但仔细思考一下,其实我们并不关心 hash 算法能否被反向解密,我们在此场景下对哈希算法的最大的要求是效率和随机性。因此 MurmurHash 算法可能更符合我们的使用场景,MurmurHash 算法与一般的哈希算法相比,对于规律性较强的 key,具备更好的随机性分布特征。

MurmurHash 算法可以生成 32 位 和 128 位两种哈希值,一般情况下 32 位就够了,再通过我们上面的 62 进制算法转化,可以使 url 看起来更短。

哈希冲突了怎么办

哈希算法必然存在哈希冲突的现象,或许概率很低,但做为一个健壮的系统,还是要对这种情况作出应对。

我们可以在数据库对短链接的列加上唯一索引,这样在存储的时候,如果重复就会抛出异常。

对于这种重复的,可以对原地址加上特定的值(可以是一个固定的UUID的值),然后再存储,如果还是重复,接着加特定的值(当然这种概率很小很小了)。

在访问短链接的时候,我们返回重定向的真实地址前,先判断地址是不是以特定的值结尾,如果是,先截取掉,再返回给用户。

其它优化

分表

如果短链接的使用量比较大,可以考虑使用 shardingsphere 之类的中间件进行分表存储,分表的算法一般按照短链接 code 哈希取模即可。

缓存

对于访问频率高的短链接,可以考虑放入缓存(比如 redis),来提高响应性能

  • 新生成的短链接,直接放入缓存,设置合理的过期时间(比如一天)
  • 设计一种策略统计最近访问频率较高的短链接,热点数据放入缓存
  • 缓存过期策略建议使用 LRU

过期数据清理

短链系统在设计的时候一般都会有个过期字段,因为很多短链接没必要永久生效。

可以跑一个定时任务,在业务低峰期对过期的短链记录进行清理,考虑到留底的作用,也可以把过期数据迁移到归档库。

总结

这篇文章我们主要讲了什么是短链接系统,以及短链接系统的实现。

对于自增序列和哈希算法两种,我们可以根据我们的业务场景去选择。

最后,又聊了一些可以优化的点,希望对你有所帮助。

参考资料

https://time.geekbang.org/column/article/80850

0

评论区