以前看到过几次短网址的实现的文章，没有多留意。突然有个项目需要用到短网址，因为量不大，所以我就买了商业服务。不过还是在网上学习了一下短网址的实现。在这里记录备份一下。
短网址的好处
- 节省网址长度，便于社交化传播，一个是让URL更短小，传播更方便，尤其是URL中有中文和特殊字符，短网址解决很长的URL难以记忆不利于传播的问题；
- 短网址在我们项目里可以很好的对开放以及对URL进行管理。有一部分网址可以会涵盖性、暴力、广告等信息，这样我们可以通过用户的举报，完全管理这个连接将不出现在我们的应用中，对同样的URL通过加密算法之后，得到的地址是一样的；
- 方便后台跟踪点击量、地域分布等用户统计。我们可以对一系列的网址进行流量，点击等统计，挖掘出大多数用户的关注点，这样有利于我们对项目的后续工作更好的作出决策；
- 规避关键词、域名屏蔽手段、隐藏真实地址，适合做付费推广链接；
- 当你看到一个淘宝的宝贝连接后面是200个“e7x8bv7c8bisdj”这样的字符的时候，你还会觉得舒服吗。更何况微博字数只有140字，微博或短信里，字数不够，你用条短网址就能帮你腾出很多空间来；(短信里的字数和钱有关)
短链服务总的来说，就做两件事：
- 将长网址变为短网址，当然是越短越好
- 用户点击短网址的时候，实现自动跳转到原来的长网址
下面我们来分别看这两个问题
长网址转短网址
在网址 URL 中，常用的合法字符有 0～9、a～z、A～Z 这样 62 个字符，所以短链的长度决定了短链可以存储的长链数量.( 6 位的话，总共会有 62^6 ~= 568亿种组合，基本上够用了)
ID生成器
维护一个 ID 生成器。它可以生成 1、2、3…这样自增的整数 ID（与分布式ID的实现基本相同，需要规避单点）。当短网址服务接收到一个原始网址转化成短网址的请求之后，它先从 ID 生成器中取一个号码，然后将其转化成 62 进制表示法。
如果采用这种方式相同的原始网址可能会对应不同的短网址。这种问题有两种处理思路：
第一种处理思路是不做处理。实际上，相同的原始网址对应不同的短网址，这个用户是可以接受的。因为在大部分短网址的应用场景里，用户只关心短网址能否正确地跳转到原始网址。至于短网址长什么样子，他其实根本就不关心。所以，即便是同一个原始网址，两次生成的短网址不一样，也并不会影响到用户的使用。
第二种处理思路：当要给一个原始网址生成短网址的时候，我们要先拿原始网址在数据库中查找（原始网址要做缓存），看数据库中是否已经存在相同的原始网址了。如果数据库中存在，那我们就取出对应的短网址，直接返回给用户。但这种方式会带来两个问题：
- 两个索引占用了更多的存储空间
- 两个索引对插入、删除的性能有一定影响
MD5进制算法
网上看到的一种算法，据说是微博的算法
1、将长网址通过
md5运算，生成 32 字符的 hex string，分为 4 段，每段 8 个字符；2、对这四段循环处理，取 8 个字节，将其看成 16 进制串，并与 0x3fffffff(30位1) 与操作，即超过 30 位的忽略处理；
3、这 30 位分成 6 段，每 5 位的数字作为字母表的索引取得特定字符，依次进行获得 6 位字符串。
4、总的
md5串可以获得 4 个 6 位串，取里面的任意一个就可作为这个长网址的短网址 url 地址。
这种算法存在碰撞的可能性，所以在生成之前要进行防碰撞检测
哈希算法
哈希算法除了 MD5、SHA1 这一类加密哈希算法（cryptographic hash）。在生成短网址这个问题上，毕竟，我们不需要考虑反向解密的难度，所以我们只需要关心哈希算法的计算速度和冲突概率。
MurmurHash 算法最初由 Austin Appleby 于 2008 年发明，是一种非加密型哈希函数，适用于一般的哈希检索操作，即使输入的key是有规律的，所产生的hashcode仍然有很好的随机分布性，而且速度也很快。目前的版本是MurmurHash3,可以产生32位或者128位的哈希值。Redis、Memcached、Cassandra、HBase，Lucene、Hadoop、libstdc++、nginx、libmemcached都使用到了这种算法。
Murmur哈希算法最大的特点是：
- 碰撞率低
- 计算速度快
网上找了很久都只有这点介绍，没有具体算法，guava提供了这个算法，可以直接使用
为了让最终生成的短网址尽可能短，我们可以选择 32位的哈希值，对于原网站得到10进制的哈希值后，可以将 10 进制的哈希值转化成 62 进制
hash冲突
MD5进制算法和哈希算法都存在碰撞的可能性。尽管 MurmurHash 算法，冲突的概率非常低。但是，一旦冲突，就会导致两个原始网址被转化成同一个短网址。当用户访问短网址的时候，我们就无从判断，用户想要访问的是哪一个原始网址了。这个问题该如何解决呢？
当有一个新的原始网址需要生成短网址的时候，我们先利用 MurmurHash 算法，生成短网址。然后，我们拿这个新生成的短网址，在数据库中查找。如果没有找到相同的短网址，直接使用这个短网址，将短网址和长网址之间的关系存储到数据库中。
如果我们在数据库中，找到了相同的短网址，那也并不一定说明就冲突了。如果数据库中的原始网址，跟我们现在正在处理的原始网址是一样的，这就说明已经有人请求过这个原始网址的短网址了。我们就可以拿这个短网址直接用。如果数据库中记录的原始网址，跟我们正在处理的原始网址不一样，那就说明哈希算法发生了冲突。
不同的原始网址，经过计算，得到的短网址重复了。这个时候，我们该怎么办呢？我们可以给原始网址拼接一串特殊字符，比如“[DUPLICATED]”，然后跟再重新计算哈希值，两次哈希计算都冲突的概率，显然是非常低的。假设出现非常极端的情况，又发生冲突了，我们可以再换一个拼接字符串，比如“[OHMYGOD]”，再计算哈希值。然后把计算得到的哈希值，跟原始网址拼接了特殊字符串之后的文本，一并存储在数据库中。
短网址转长网址
了解了长网址转短网址之后，这一步就很简单了这一步非常简单，当用户访问短网址的时候，短网址服务先通过短网址，在数据库中查找到对应的原始网址。如果原始网址有拼接特殊字符（这个很容易通过字符串匹配算法找到），我们就先将特殊字符去掉，然后再将不包含特殊字符的原始网址做一个302跳转。
为什么要使用302跳转，而不是301跳转呢？
301 是永久重定向，302 是临时重定向。短地址一经生成通常就不会变化，301 是符合 http 语义的，同时对服务器压力也会有一定减少。
301 redirect:：301代表永久性转移(Permanently Moved)，301重定向是网页更改地址后对搜索引擎最友好的方法，只要不是暂时搬移的情况，都建议使用301来做转址。对于 GET 请求, 301 跳转会默认被浏览器 cache。也就是说，用户第一次访问某个短链接后，如果服务器返回 301 状态码，则这个用户在后续多次访问同一短链接地址，浏览器会直接请求跳转地址，而不会再去短链接系统上取！
302 redirect:：302代表暂时性转移(Temporarily Moved )，而302重定向很容易被搜索引擎误认为是利用多个域名指向同一网站，那么你的网站就会被封掉，罪名是“利用重复的内容来干扰Google搜索结果的网站排名”。对于 GET 请求, 302 跳转默认不会被浏览器缓存，除非在 HTTP 响应中通过 Cache-Control 或 Expires 暗示浏览器缓存。因此，用户每次访问同一短链接地址，浏览器都会去短链接系统上取
从网址A做一个302重定向到网址B时，主机服务器的隐含意思是网址A随时有可能改主意，重新显示本身的内容或转向其他的地方。大部分的搜索引擎在大部分情况下，当收到302重定向时，一般只要去抓取目标网址就可以了，也就是说网址B。如果搜索引擎在遇到302转向时，百分之百的都抓取目标网址B的话，就不用担心网址URL劫持了。问题就在于，有的时候搜索引擎，尤其是Google，并不能总是抓取目标网址。比如说，有的时候A网址很短，但是它做了一个302重定向到B网址，而B网址是一个很长的乱七八糟的URL网址，甚至还有可能包含一些问号之类的参数。很自然的，A网址更加用户友好，而B网址既难看，又不能用户友好。这时Google很有可能会仍然显示网址A。由于搜索引擎排名算法只是程序而不是人，在遇到302重定向的时候，并不能像人一样的去准确判定哪一个网址更适当，这就造成了网址URL劫持的可能性。也就是说，一个不道德的人在他自己的网址A做一个302重定向到你的网址B，出于某种原因，Google搜索结果所显示的仍然是网址A，但是所用的网页内容却是你的网址B上的内容，这种情况就叫做网址URL劫持。你辛辛苦苦所写的内容就这样被别人偷走了。302重定向所造成的网址URL 劫持现象，已经存在一段时间了。不过到目前为止，似乎也没有什么更好的解决方法。在谷歌曾进行的Big Daddy数据中心转换中，302重定向问题也是要被解决的目标之一。从一些搜索结果来看，网址劫持现象有所改善，但是并没有完全解决 ——摘自百度百科
但是如果使用了 301，我们就无法统计到短地址被点击的次数了。而这个点击次数是一个非常有意思的大数据分析数据源。能够分析出的东西非常非常多。所以选择302虽然会增加服务器压力，但是有时候是一个更好的选择。
细节优化
生成的优化
在短网址生成的过程中，我们会跟数据库打两次交道，也就是会执行两条 SQL 语句。
- 通过短网址查询短网址与原始网址的对应关系
- 将新生成的短网址和原始网址之间的对应关系存储到数据库
我们可以给数据库中的短网址字段，添加一个唯一索引。当有新的原始网址需要生成短网址的时候，我们并不会先拿生成的短网址，在数据库中查找判重，而是直接将生成的短网址与对应的原始网址，尝试存储到数据库中。
如果数据库能够将数据正常写入，那说明并没有违反唯一索引，也就是说，这个新生成的短网址并没有冲突。
如果数据库反馈违反唯一性索引异常，我们在执行“查询-写入”的过程，虽然这样会增加一次数据库交互。但是，在大部分情况下，我们把新生成的短网址和对应的原始网址，插入到数据库的时候，并不会出现冲突。所以，大部分情况下，我们只需要执行一条写入的 SQL 语句就可以了。所以，从整体上看，总的 SQL 语句执行次数会大大减少。
我们也可以通过布隆过滤器来判断短网址是否存在
加入随机码
62 进制用更短的字符串能表示更大的数，使得我们可以使用更少的字符，同时不会让用户直接知道我们的 id 大小，但是稍微懂一点技术的，很容易就能将 62 进制转换为 10 进制，在行家眼里，和直接使用 id 没什么区别。
我们得到 id 以后，先在其二进制表示的固定位置插入随机位。例如从低位开始，每 5 位后面插入一个随机位，直到高位都是 0 就不再插入。
前面提到高位为 0 就不再插入，那是为了不至于一开始就往高位插入了 1 导致我们刚开始的值就特别大，转换出来需要更长的字符串。
参考资料
https://time.geekbang.org/column/article/80850
https://javadoop.com/post/url-shortener
