背景
分享到微博或者推特都有 140 字的限制,所以最近产品提出一个分享 URL 要做成短链接的需求,便在网上查询了一下资料,综合下来,总结了几种算法.
算法
总的来说就是把长的 URL 通过一个算法得出一个 6 位左右的短链,再把这个映射关系保存起来,下次有用户访问短链的时候我们能找到他对应的长链.并通过301 或者 302 重定向到原来的 URL 上.
1. 自增 id 转 62 进制
从数据库或者 redis 里取一个自增数据,然后十进制转化成 62 进制,这样短链就永远不会重复,适合于原始 URL 1 对多的情况,也就是一个长链接每次分享都生成不一样的短链接.
就算是一亿对应的 62 进制数也就是 6LAze,短短的 5 位.
最小的 7 位 62 进制数对应的十进制数是 56800235584,五百六十八亿多,远超当前的所有URL 总和.所以 6 位数的 62 进制是肯定够用的.
为什么是 62 进制?
因为用 0-9 a-z A-Z刚好是 62 位,如果用 64 位就可能会产生/或者+,这在 URL 解析的时候可能会发生问题,所以使用 62 进制更加安全
2. 哈希值截取
这个方法比较简单,直接对 URL 进行哈希计算,然后取其中的 6 位.这种算法可能会出现重复,所以算出来后需要对数据库进行一次碰撞,如果重复一次.直到数据库里没有,即为短连接.这种方法有点在于快捷而且算法很简单.适合数据量比较小的服务.
存储
长链到锻炼映射关系需要存储起来.
短链到长链的映射肯定是需要用 redis 这样的高速缓存来做,因为页面的访问频率肯定会比较高,如果全部存在数据库里,当用户量比较大时,大量数据库连接会让数据库变得非常慢,甚至挂掉.如果需要做到持久化,也就是这个短链永久有效的话,那还是需要存一份数据库,当redis 找不到时,再去查数据库.
为什么要用 301 跳转而不是 302？
301 是永久重定向，302 是临时重定向。短地址一经生成就不会变化，所以用 301 是符合 http 语义的。同时对服务器压力也会有一定减少。
但是如果使用了 301，我们就无法统计到短地址被点击的次数了。而这个点击次数是一个非常有意思的大数据分析数据源。能够分析出的东西非常非常多。所以选择302虽然会增加服务器压力，但是我想是一个更好的选择。
安全问题
如果是长链一对多的情况,那黑客进行大量的请求,很可能会快速消耗短链个数,那可以结合一对多和一对一的策略,在生成锻炼的逻辑中,存储长链到短链的 redis 记录,并设置一个比较短的过期时间,比如 10 分钟,用LRU机制进行淘汰.在生成之前先查询一次redis,如果存在则直接返回短链,并刷新过期时间,如果不存在再去生成.