PinkHello
做一个快乐的程序猿
短链接的思考与技术实现
短链接的思考与技术实现

前提


又到了一月一度的清理消息的时候了,开始清理短信,忽然见到一个幸福里的通知短信,那是在短信到达之前,本🐶打肿脸充胖子在幸福里小程序里面咨询上海的一套二手房的价格的,后来没关注, 这个短链接 https://m.xflapp.com/s/vdwecR 引起了本🐶的兴趣.

我发问:如何去实现一个短链接服务?

短链接example.png

短链接的原理


短链接的核心是什么?

构建的短链接和长链接(我们真实的访问地址)的唯一关联映射、也就是映射标识生成算法。

从这个定义也能得到短链接服务的几个特点:

  • 1⃣️具有高性能
  • 2⃣️是排列组合数量量要足够大
  • 3⃣️要具有不易破解、且破解难度极大

拆解短链接


👆的短链接 https://m.xflapp.com/s/vdwecR 我掏出了我的神器 Chrome 打开了一下,直接跳转到了http://m.haoduofangs.com/f100/activity/client/tt_im?app_id=13&customer_user_id=62800686641&realtor_id=3781951248937422. 好了仔细看一下请求和响应,响应的302,响应头中带了需要跳转的地址.

服务跳转HTTP响应方式

综上我示意图:

短链接访问方式

可以看出来,构建唯一映射关系是将原有的固定长链接生成一个或多个短链接,1:N关系。生成的短链接必须满足:

  • 不能轻易的被猜出来(破解),被恶意遍历。
  • [一定时间内]不能重复(一个短链接在一定时间内只能对应一个长链接、这个一定时间可以是永久)
  • 长度尽量短
    • 在短信运营商会限制短信的长度、如果太长、留给运营人员或者客户的的字符长度会有🚫,这不是给同事或客户挖坑么。
    • 链接变二维码,二维码的点位会非常密集,不利于客户端识别和传输
    • 长度太长,从个人情感里面也比较繁琐这样的长链接,不易记录和输入

回到这个唯一映射关系上来,就是需要对这个长链接做 Hash,和大多数哈希算法一致,生成算法需要就是要具备唯一性和较低的碰撞率的特点,而在短链接场景下,又决定了它还要具备短线精悍并且易于传输的特点。

短链接压缩生成算法特点:

  • 短小精悍、易于传输
  • 高度唯一性
  • 低碰撞率

短链接生成算法


短链接协议解析

从上图可以看出,协议域名均为不可变部分,能定制的只有压缩码(哈希码), 那么作为程序🐶能玩的也只有这部分了。

回到幸福里通知短信的短链接, 它抛掉协议域名两部分,还剩下s/vdwecR, 可以看出Path其实是两层,第一层是s,第二层是vdwecR, 可以抽象为{pathLevel1}/{pathLevel2},{pathLevel1}为了简短使用了单个字母(可以区分大小写)或者数字, {pathLevel2} 为了满足低碰撞率和唯一性,使用了6位区分大小写字母和数字的组合体。 那么像这个组合体的最大组合数量是多少呢?{pathLevel1} 假设只有一位, {pathLevel2} 有6位,从当前的例子来看,不考虑取值为数字的可能,那么它的组合数 每个取值都是(26个大写字母 + 26个小写字母) ,也就是 52 ^ 7 = 1,028,071,702,528 ,已达万亿级别数量级。

现在我做个假设,我们只实现有一个级别的path, 每个字符串的取值为(26个大写字母 + 26个小写字母 + 10 个数字),那么这个组合数就看位数N了: 62 ^ N 为组合数数量级

  • N=4 62^4 = 14,776,336 达到 147.76 万
  • N=5 62^5 = 916,132,832 达到 9.16 亿
  • N=6 62^6 = 56,800,235,584 达到 568 亿
  • N=7 62^7 = 3,521,614,606,208 达到 35216.14 亿

可以看出,组合数越小的数量级别越小,破解的难度越小,组合数越大,破解的难度越难。

从我的🦶机历史的短信上,看 4567 的短链接都有,大部分的还是6位,现在决定选型: 选择 6 位作为组合位的位数。现在我把这个6位的随机串叫做 压缩码

好了,下面开始设计了,只需要解决两个问题就设计完成:

  • 压缩码的生成
  • 长链接和短链接的映射

如何解决压缩码的生成?

在考虑如何生成压缩码的时候,我讨巧了一下,也是借助样例子做了个拓展,62进制的字符串刚好由 0-9, A-Z, a-z 组成,在这方面只需要做一件事, 直接生成一个唯一的十进制数,最后直接转换为 62进制数即可

10进制数的生成方式:

  • DB 自增
  • 雪花算法
  • 其他方式等

如何解决映射问题?

压缩码生成后如何生成短链接?这边采用最简单的方式,直接协议拼接生成,压缩码直接消耗掉(后面考虑回收压缩码的问题)。长链接和压缩码直接关联映射(1:N).N的数量看需求服务方要求。

拓展问题:

  • 压缩码共享(多个短链接域名)

综上下图是短链接映射实现图:

短链接映射实现图

短链接换长链接时序图:

短长链接时序图

短链接服务的技术实现

开源项目: corgi

wait coding


最后修改于 2021-09-05