让你设计一个短链系统，怎么设计？
让你设计一个短链系统，怎么设计？
先说一下回答思路：
1）简单描述下短链原理
2）后端设计
3）补充跳转设计
一个小小短链其实融合了很多知识点，能较为全面的考察一个候选人的综合实力。
原理
在浏览器输入短链后，请求打到短链服务，短链服务会根据 url 找到对应的长链重定向到长链地址，此时浏览器就会跳转网页定位到真正的地址。
所以本质原理就是短链服务器根据 url 定位到真正地址，然后通过重定向实现跳转。
后端设计
后端的主要功能是存储短链和长链的对应关系，并且能快速通过短链找到长链。
首先需要先生成短链，假设短链的域名是 dl.x
1）可以通过数据库自增 id 作为短链，往数据库插入一条长链，对应就会得到一个 id
| id | url |
|---|---|
| 1 | https://www.code-nav.cn/course/1790274408835506178 |
| 2 | https://www.code-nav.cn/course/1789189862986850306 |
如果用户访问了 dl.x/1 ，解析得到 1，通过主键就能定位到数据库记录，得到长链 https://www.code-nav.cn/course/1790274408835506178 。
这个方式很简单，通过主键查询也很快。
如果面试官问这样的方式有什么缺点，你再说：一旦短链量变多，自增 id 会变成很大，比如 9999999999999999，这样短链也不短了，而且数字有规律性，容易被人遍历出来。
没问就不用说。
2）哈希算法
可以通过 hash 算法将长链进行 hash 计算，得到固定的长度，比如通过 md5 计算可以得到固定的 128bit 数据，还有别的哈希函数，比如 MurMurHash，它既可以生成 128 bit 也可以生成 32bit，不过 32 bit 相比 128 bit 生成速度更慢，且 hash 碰撞的概率更高。
这里再提一嘴 MurMurHash 128bit 版本的速度是 md5 的十倍。
还有 crc32 ，得到的就是 32 位的哈希值，运算速度和 md5 差不多。
因此我们可以将长链通过 hash 得到固定的位数，我找了个网上的 MurmurHash2 例子，我们来看下
可以看到这么长的一个 url，直接变成了 2278507744，因此短链就是 dl.x/2278507744
但是这好像比我们平时在短信中看到的短链还长了一些，还能再缩短吗？
当然是可以的，还可以利用进制转化进一步缩短长度！
比如我们取 62 位的，最终的短链就是 dl.x/2ucnWU，这样看着是不是感觉就对了？同理上面的自增 id 也可以通过进制转化进一步缩短。
最终的数据库表结构的设计如下：
字段：
- id：主键
- short_url：短链
- long_url：原始长 URL
- user_id：用户 ID（如果需要关联用户）
- created_at：创建时间
- updated_at：更新时间
短链字段需要建立索引，因为很常见的查询就是通过短链得到长链。
跳转设计
我们已经了解到通过短链得到长链的过程，那么浏览器具体是如何在输入短链后自动跳到长链地址的呢？
答案就是重定向。这里就需要涉及到 HTTP 的知识点，服务器返回 301 或者 302 状态码，然后在 location 上写上长链的地址，浏览器就会自动识别动作，进行跳转。
这两个状态码还是有区别的：
1）301 表示永久重定向，即浏览器会默认缓存这次跳转的信息，下次用户在浏览器访问这个短链，浏览器不需要请求短链服务，会自动跳转到长链地址。
2）302 表示临时重定向，即浏览器不会缓存这次跳转信息，用户每次访问这个短链，都需要请求短链服务得到长链。
区别就是 301 可以降低短链服务器压力，因为后续用户访问都不需要请求短链后端服务，而 302 则需要每次访问，但是这样一来可以统计短链访问次数，做一些分析。
扩展
如果数据量大了，一张表存储所有短链数据就会有性能问题，因此需要分库分表。
如果是利用自增 ID 转换得到短链信息，在分库分表场景就会出现重复 ID 的情况，因此可以引入全局发号器来实现全局唯一 ID 分配，比如唯一 ID 可以利用雪花算法生成。
然后通过全局 ID 转化的短链数据作为分表的键即可，因为查询肯定是通过短链来查的。
还有哈希方法可能会导致哈希冲突，即不同的长链可能会生成一样的短链，我们可以将 short_url 作为唯一索引，这样就能保证唯一性，如果插入报错，则可以简单在长链后面拼个随机数，重新进行 hash，这样就能避免重复了。
还可以引入缓存，比如我们双十一做了一个营销活动，给很多用户推送了短信，此时肯定会有很多用户访问这个短信内的短链，此时我们就可以将短链相关信息放在缓存中，不需要查数据库，利用缓存提高性能。
补充为什么需要短链
一般短链会用在短信场景，因为短信有字数限制，超过一定字数收费不一样，所以太长的连接不合适。
再比如一些社交媒体平台对字数也会有限制。
还有一些二维码，如果 url 太长，生成的码也会比较复杂，比较难扫。