设计一个系统将长链接地址转为短链接地址
背景
最近遇到一个面试题，问请你设计一个系统将长链接转为短链接。起初回答的不是很好，之后通过自己思考和查阅资料将这块的内容进行整理。
研究
定义
短地址（也叫 短网址：Short URL）就是为了让一个很长的网站链接缩短为一个短的链接，因为微博内有字数限制，所以短地址就是为了这个而产生的。大部分微博、手机短信提醒等地方已经有很多应用了。
优势
- 节省网址长度，便于社交化传播。
- 方便后台跟踪点击量、地域分布等用户统计。
- 规避关键词、域名屏蔽手段。
- 隐藏真实地址，适合做付费推广链接。
总之
1、链接变短，在对内容长度有限制的平台发文，可编辑的文字就变多了
最典型的就是微博，限定了只能发 140 个字，如果一串长链直接怼上去如连接后面是100个“has11nut06bab2y3”这样的字符的时候，其他可编辑的内容就所剩无几了，用短链的话，链接长度大大减少，自然可编辑的文字多了不少。再比如一般短信发文有长度限度，如果用长链，一条短信很可能要拆分成两三条发，本来一条一毛的短信费变成了两三毛。另外用短链在内容排版上也更美观。
2、我们经常需要将链接转成二维码的形式分享给他人，如果是长链的话二维码密集难识别，短链就不存在这个问题了。
跳转原理
我们可以认为他是整个交互的流程，具体的流程细节如下：
（1）用户访问短链接：https://dwz.date/fn4w；
（2）短链接服务器dwz.date收到请求，根据URL路径fn4w获取到原始的长链接（KV缓存数据库中去查找）：https://www.cnblogs.com/lingyejun/p/15894620.html；
（3）服务器返回302状态码，将响应头中的Location设置为：https://www.cnblogs.com/lingyejun/p/15894620.html；
（4）浏览器重新向https://www.cnblogs.com/lingyejun/p/15894620.html发送请求；
（5）返回响应；
具体方案
优化方案
算法优化
短链接标识一般是 [0-9, a-z, A-Z] 随机组合而成的字符串，字符一共有 62 个，因此短链接标识可以用 62 进制的字符串表示。
首先维护一个自增的 ID，当生成短链接时，将 10 进制的自增 ID 转换成 62 进制字符串，这个字符串就可以唯一标识一个长链接。由于 ID 是自增的，对应的 62 进制字符串是不同的，这样就不会出现一个短链接对应多个长链接的问题，62 个字符排列组合，可以保证短链接是用不完的，就算仅限于 6 位长度标识的短链接，也有 558 亿多种情况，这种算法在网上被称为自增序列算法。
1、62 进制的顺序并不一定严格按照 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ 的顺序来表示，这个顺序可以是打乱的，这样生成的短链接标识更随机不易被破解。
2、长链接与短链接是否需要一对多关系，同一个长链接使用自增主键 ID 算法生成的短链接是不同的，因为自增主键 ID 不同，生成的 62 进制字符串自然也不同。如果我们有一个长链接唯一对应一个短链接需求，可以将长链接进行 md5 加密，将加密后的 md5 值存储在 DB 中，每次生成短链接前都根据长链接 md5 值查询 DB，如果存在，则直接返回短链接，当然也可以使用其他方式维护这种关系。
短地址发号器优化方案
1、算法优化
采用以上算法，如果不加判断，那么即使对于同一个原始URL，每次生成的短链接也是不同的，这样就会浪费存储空间（因为需要存储多个短链接到同一个URL的映射），如果能将相同的URL映射成同一个短链接，这样就可以节省存储空间了。主要的思路有如下两个：
方案1：查表
每次生成短链接时，先在映射表中查找是否已有原始URL的映射关系，如果有，则直接返回结果。很明显，这种方式效率很低。
方案2：使用LRU本地缓存，空间换时间
使用固定大小的LRU缓存，存储最近N次的映射结果，这样，如果某一个链接生成的非常频繁，则可以在LRU缓存中找到结果直接返回，这是存储空间和性能方面的折中。
2、可伸缩和高可用
如果将短链接生成服务单机部署，缺点一是性能不足，不足以承受海量的并发访问，二是成为系统单点，如果这台机器宕机则整套服务不可 用，为了解决这个问题，可以将系统集群化，进行“分片”。
在以上描述的系统架构中，如果发号器用Redis实现，则Redis是系统的瓶颈与单点，因此，利用数据库分片的设计思想，可部署多个发号器实例，每个实例负责特定号段的发号，比如部署10台Redis，每台分别负责号段尾号为0-9的发号，注意此时发号器的步长则应该设置为10（实例个数）。
另外，也可将长链接与短链接映射关系的存储进行分片，由于没有一个中心化的存储位置，因此需要开发额外的服务，用于查找短链接对应的原始链接的存储节点，这样才能去正确的节点上找到映射关系。
参考文章：
https://blog.csdn.net/xlgen157387/article/details/80026452