原则与底线：不说废话、不凑字数、不标题党。
背景
什么是短链
一个长的网址链接，转换为一个短的网址链接。
比如我发微博内容带有 https://blog.hanyu.cool/about/ 链接时，链接会自动转换成 https://t.cn/A6NlWmYi 这样的短网址。
微博的短网址域名为：t.cn，腾讯的短网址域名为 url.cn，阅读本文后，就可以自己实现一个高性能短链服务。
短链的作用
- 缩减无意义的地址长度，多出空间给实际内容（当前微博限制5000个字）
- 对URL进行流控、点击统计，来源识别等，方便进行数据分析
- 防止直接暴露参数等信息，防止某些平台对参数中的关键词屏蔽
- 方便对URL进行封禁，相同URL通过生成转换之后，最终地址是相同的
原理与实现
核心原理
- 生成&转换
- 存储
- 映射
实现过程
- 用户先访问短网址，短网址将自动请求至短链服务器
- 短链服务器收到请求后，在映射中通过短网址查找原始长链
- 服务端将原始长链以302或301状态码返回给用户
- 用户浏览器收到后重定向到原始长链
生成短链主要有两种方式，哈希和ID生成器。
哈希
哈希算法
哈希算法可以将一个不管多长的字符串，转化成一个长度固定的哈希值，所以可以利用哈希算法，来生成短网址。
常用的哈希算法如MD5、SHA、MurMurHash、CRC32等。
短链不需要考虑反向解密难度，只需要考虑计算速度快、冲突概率小即可。
目前应用比较广泛非加密算法是2008 年被发明的MurmurHash，据资料显示，现在已经广泛应用到 Redis、MemCache、Cassandra、HBase、Lucene等软件中，MurmurHash算法具体实现可自行去了解，此处不展开（因为我懂得不多）。
MurmurHash 计算可选长度128位、32位等，位数多碰撞的概率就小，如果短链系统用的人不多，可以选择32位，这样生成的短链更短。
短链服务端接收到生成的请求后，可以把长链做 MurmurHash 计算，可以得到的一个哈希值，将哈希值与短链域名拼接，即可得到完整短链，如： t.cn/111111111
进制转换
如上所示，MurmurHash计算后得到的结果并不算短，我们可以优化一下，常用的方式是将10进制转换成62进制。
10进制转换62进制的逻辑就是，一直循环用62取余然后倒序：
最终 t.cn/111111111 用62进制表示的短链就是 t.cn/7WD4h 。
假设生成6位字符的短链：
10进制 最大只能生成 10 ^ 6 - 1 = 999999个
16进制 最大只能生成 16 ^ 6 - 1 = 16777215个
62进制 最大竟能生成 62 ^ 6 - 1 = 56800235583个
A-Z a-z 0-9 刚好等于62位。
如果使用128进制，网址会更短，但之所以不使用128进制，是因为可能会出现大量的不常用字符比如 #%& 等，不利于记忆和传播。
哈希冲突
即使概率非常小，但哈希算法也可能会发生哈希冲突，也就是两个不同的原始长网址哈希后得到了相同的短网址，短链服务将无法判断当前的短网址对应的原始网址是哪个。
通常我们都会使用数据库如配合缓存来存储长短网址的映射关系，过程如下：
- 通过哈希算法将接收到的原始长网址进行转换，得到短串
- 使用短串去数据库或缓存中查找
- 如果不存在，则说明长短网址之间没有冲突，则将短网址返回给用户，同时将长短网址的映射关系入库
- 如果存在，则说明有冲突，但未必是哈希冲突，我们先将这个冲突的短网址对应的长网址从数据库中取出，和本次请求的长网址进行对比。
- 如果两个原始长网址相同，直接将短链返回给用户即可；
- 如果两个原始长网址不同，则说明发生了哈希冲突，我们可以将本次请求的原始长网址后面拼接随机串，再次进行哈希即可。
ID生成器
除了通过哈希的方式，我们还可以通过各类ID生成器来进行短链生成。
ID生成
包括但不限于：
- 数据库自增
- 程序计数器自增
- 中间件如Redis自增、MongoDB主键生成等
- snowflake、UUID、GUID
例如通过数据库自增ID拿到一个新的ID，然后将ID进行62进制转换，形成短链，将短链和原始网址映射关系存入库中，当然，如果不怕暴露信息的情况下，ID也可以不进行哈希。
二义性
使用ID生成器生成可能会存在二义性，也就是说一个原始长网址，经过两次生成得到的短网址不一样，解决思路如下:
- 第一种解决方式是[不处理]，因为使用短链的人，只关心短链是否能正确跳转至原始网址，所以原始长网址生成的短链不一致可以不进行处理
- 第二种解决方式是拿原始长网址去数据库中查找，如果存在，取出对应的短链返回给用户即可，但要注意数据库中的长短网址都需要加索引，给原始长网址加索引也会导致插入性能下降，占用空间更多。
高并发优化
为了应对高并发的生成和访问，我们需要对之前的短链系统做一定的优化。
数据库索引
以生成的短链作为数据库唯一索引，这样在生成短链后准备存入映射关系时，不必从数据库先进行查找判重，而是直接进行数据库的插入，如果捕获了唯一索引异常，说明有冲突，再进行二次哈希即可。
这样在生成短链时，减少了一次SQL查询操作，同时也能利用到索引高效访问。
布隆过滤器
布隆过滤器的原理是使用位图和多次哈希计算判断数据是否存在。不存储数据本身，而是只标识某数据的“存在性”。
场景1：对于之前我们使用哈希的方式进行短链生成，可以把已经生成的短网址，构建成布隆过滤器，长度是 10 亿的布隆过滤器，也只需要 125MB 左右的内存空间。
有新的短链要生成的时候，我们使用该短链去布隆过滤器里查找，如果不存在，那就一定不存在，我们直接将新生成的长短网址映射关系存储即可。
场景2：对于使用ID生成器的二义性问题，我们也可以通过布隆过滤器解决。
我们将接之前都已经存储好的长链构建成布隆过滤器，后续接收到生成短链的请求时，先拿原始网址去布隆过滤器里查找
- 如果不存在，那就一定不存在，我们就可以使用这个原始长地址进行短链转换并存储。
- 如果存在，可能会误判，我们还要用长地址去数据库中查找判重，再进行后续处理。
多级缓存
我们可以将长短网址的映射关系存入本地缓存如Guava作为一级缓存，同时存入Redis作为二级缓存。
同时还可以采用LRU缓存过期淘汰，减少无畏的内存消耗。
无论是生成时还是访问时，都可以先从一二级缓存中进行查找，大大提高效率。
并且，Guava和Redis都有布隆过滤器(Bloom Filter)的实现，如果使用布隆过滤器，没有特殊必要的话不必自己造轮子。
前置发号器
我们可以采用类似大禹治水的分治、分流思想。
将ID生成器服务上层放置多个发号器（服务+队列），生成器在启动时，批量预生成一批短链给各个发号器，比如给每个发号器预生成3000个短链，当发号器内数量少于200时，主动向生成器取一批号。
这样就提高了发号的并发能力，同时生成器也的大量计算操作也不受高并发请求线程的影响。
注：布隆过滤器
布隆过滤器是一种概率型数据结构，它的特点是高效的插入和查询，能确定某个字符串一定存在或者可能存在。布隆过滤器不存储具体数据，所以占用空间小，查询结果存在误差，但误差可控，同时不支持删除操作。布隆过滤器为了节约内存，是使用的位图。
（1）一个巨大的数据文件，需要知道是否存在某个key，如果把整个文件读取进行查找，这个效率就比较低。那么可以添加一个布隆过滤器，插入数据时对key做标识，查询key是否存在时直接查询布隆过滤器。
（2）一个数据库查询，想要查询数据库中是否存在key，可以添加一个布隆过滤器，查询key时直接查询布隆过滤器，不需要IO操作，大大提升查询效率。一个元素加入位图时，通过k个hash函数将元素映射到位图的k个点，并把它们置1；当检索时，再通过k个hash函数运算检查位图的k个点是否都为1；如果有不为1的点，那么认为该key不存在；如果全部为1，则可能存在。
只要有一个槽位为0，则key一定不存在；如果key映射的所有槽位都为1，不能说明一定存在，只能说明可能存在。
常见使用场景： 爬虫去重、解决缓存穿透、反垃圾邮件等。
注：snowflake
Twitter开源的分布式ID生成算法，保证大规模生成唯一的 ID 号。
优点是：高性能，低延迟；独立的应用；按时间有序。
缺点是：需要独立的开发和部署。要求机器时钟同步（到秒级即可），需要解决时钟回拨问题，如果某台机器的系统时钟回拨，有可能造成 ID 冲突，或 ID 乱序。
41 位的时间序列（精确到毫秒，41 位的长度可以使用 69 年）；
10 位的机器标识（10 位的长度最多支持部署 1024 个节点）；
12 位的计数顺序号（12 位的计数顺序号支持每个节点每毫秒产生 4096 个 ID 序号）最高位是符号位，始终为 0。
注：301和302状态码
301重定向（301 Move Permanently），指页面永久性转移，表示为资源或页面永久性地转移到了另一个位置。301是HTTP协议中的一种状态码，当用户或搜索引擎向服务器发出浏览请求时，服务器返回的HTTP数据流中头信息（header）中包含状态码 301 ，表示该资源已经永久改变了位置。
301重定向是一种非常重要的"自动转向“技术，网址重定向最为可行的一种方法。
301重定向是页面永久性转移，搜索引擎在抓取新内容的同时也将旧的网址替换成重定向之后的网址；
302重定向是页面暂时性转移，搜索引擎会抓取新的内容而保存旧的网址并认为新的网址只是暂时的。