大家好，我是树哥。相信很多朋友都用过短链服务，但是如果让你实现一个短链服务，你知道怎么实现吗？其实实现短链服务并不难。最重要的是要知道一些设计思路和一些基础技术知识，比如：hash算法，全局数生成器等。短链服务的设计场景题也是国内很多公司的面试题，很多朋友在采访中被问到。今天就一起来学习如何设计一个短链服务吧！我们都知道短链URL的价值。对于一个很长的字符串，我们往往会在其后面加很多参数，方便数据统计。以下是微信文章的地址公众号。看得出来很长，估计有将近几百字。https://mp.weixin.qq.com/s?__biz=MzA4MjIyNTY0MQ==&mid=2647743787&idx=1&sn=1caec8eb1b81d6ee5dd7ba7fa05ac0f1&chksm=87ad0dadb0da84bb7beb5e4373a14e89fba1130c1bd2a51f4baa8021ec0abe496ce94603b6b4&token=894028224&lang=zh_CN#rd我们可以用百度的短网址功能，把上面的网址缩短成只有差不多有10串长，如下图。http://dwz.cn/iijg使用短链代替长链，有以下共同的好处：更简洁。一个大约10个字符的字符串肯定比一长串无意义的问题更简洁。使用方便。首先，有些平台对内容长度有限制（微博只能发140字），可以通过缩短网址的方式输入更多内容。其次，当我们将链接转换为二维码时，短链接生成的二维码更容易识别。第三，有些平台不能识别特殊的长链参数，切换到短链就没有这个问题。削减开支。当我们需要发送短信时，短信是按长度收费的，短网址可以节省费用。短链的原理短链可以给我们带来这么多的好处，但是它是如何工作的呢？当我们进入短链时，实际上访问的是短链服务器的地址。短链服务器获取对应的长链地址后，返回302HTTP响应，其中包含长链地址。浏览器收到响应后，转而请求长链接地址。整个接入短链的过程如下图所示：短链接入原理-来自网络从上面的过程我们可以知道，短链涉及到两个主要的技术原理，即：HTTP重定向和短链连锁服务设计。对于HTTP重定向，301和302都是重定向，那么您应该使用哪一个呢？301代表永久重定向。意思是在第一次获取到长链接后，如果浏览器下次请求短链接，就不会再次请求短链接服务器，而是直接从浏览器的缓存中获取。302代表临时重定向。意思是每次请求短链都会请求短链服务器，不会从浏览器缓存中获取。如果我们要统计短链接的点击次数来分析活动的效果。那么我们就需要用到一个302重定向码，这样我们才能拿到每一次请求的数据。一般来说，我们需要获取请求的数据，所以对于短链服务，会使用302临时重定向。实现思路让大家设计这样一个系统，大家有什么想法呢？我们可以先分析一下整个系统的处理流程：用户访问短链生成页面，输入一个长链字符串，短链服务返回生成的短链。当用户访问短链接时，短链接服务返回302响应，用户浏览器跳转到长链接地址。如果我们要实现上面的系统流程，我们一般的做法是生成一条短链。生成短链时，短链服务获取长链，然后生成短链，保存短链和长链的映射关系，最后将短链返回给用户。找到长链。访问短链时，短链服务获取短链，根据短链获取长链，返回302响应。根据以上分析，我们可以知道，短链系统的设计主要要解决以下两个问题：如何在长链的基础上生成独一无二的短链？如何保存短链和长链的映射关系？对于第2点，保存短链和长链的映射关系。考虑到持久化的问题，我们肯定是需要保存的，那么可以使用MySQL表来保存。如果需要，可以在MySQL前面做一层缓存。所以第2点相对简单。对于第一点，我们有2种生成唯一短链的思路，即：使用哈希算法生成唯一值和使用分布式唯一ID生成作为练习ID。我们来详细分析一下这两个方案。哈希算法生成短链要生成短链，我们可以对原来的长链进行一次哈希，然后得到一个哈希值，如下图。https://mp.weixin.qq.com/s?__biz=MzA4MjIyNTY0MQ==&mid=2647743787&idx=1&sn=1caec8eb1b81d6ee5dd7ba7fa05ac0f1&chksm=87ad0dadb0da84bb7beb5e4373a14e89fba1130c1bd2a51f4baa8021ec0abe496ce94603b6b4&token=894028224&lang=zh_CN#rd↓29541341303115543223957290326355那么我们遇到的第一个问题：使用什么哈希算法？我们都知道散列算法是一种摘要算法，其作用是对任意一组输入数据进行计算，得到固定长度的输出摘要。我们常用的哈希算法有：MD5、SHA-1、SHA-256、SHA-512等算法。但是我们最好还是使用另一种哈希算法，叫做MurmurHash。为什么？因为MD5和SHA哈希算法都是加密的哈希算法，也就是说我们不能从哈希值反推出原文，从而保证了原文的机密性。但是对于我们的场景，我们不关心安全性，我们关心的是计算速度和哈希冲突。MurmurHash算法是一种非加密哈希算法，因此速度较快。这时候我们就会遇到第二个问题：Hashcollision学过HashMap的同学都知道，hash碰撞是hash算法不可避免的问题。解决hash冲突的方法有两种，即：链表法和rehashing法。HashMap使用的是链表方式，而我们这里使用的是rehashing方式。所谓rehashing方法就是当发生hash冲突时，我们在原来的长链后面加上固定的特殊字符，等到后面取出长链的时候再把它去掉，如下图。原长链：https://mp.weixin.qq.com/s1caec8eb1b81d6ee5dd7b↓↓发生hash冲突↓↓添加特殊字符：https://mp.weixin.qq.com/s1caec8eb1b81d6ee5dd7b[SPECIAL-CHARACTER]↓↓Hashing再这样，我们就可以解决hash冲突的问题了。如果再次发生，则再次哈希，直到没有冲突为止。通常，哈希冲突的可能性很小。那么，现在我们通过哈希算法得到一个哈希值：29541341303115543223957290326355，就变成了这个：http://dwz.com/29541341303115543223957290326355。原本很长的网址变短了，但整体看起来还是有点长。有什么办法可以缩短URL吗？我们知道，在网站URL中，常用的合法字符是0~9、a~z、A~Z等62个字符。如果我们取哈希值的模数和62，那么余数一定在0-61之间。这62个数字正好对应62个合法的URL字符。接下来，我们将除以62得到的值再次对62取模，直到第0位。通过这样的处理，我们可以得到一个62个字符的字符串，长度很短。上面说的有点晦涩，举个例子吧。假设我们得到的哈希值是181338494，那么上面的处理流程就是：181338494除以62，结果是2924814，余数是26，此时余数26对应的字符就是q。2924814除以62，结果为47174，余数为26，余数26对应的字符为q。47174除以62，结果为760，余数为54，余数54对应的字符为S。省略剩余步骤，整个处理流程如下图所示：转十六进制数示意图——从极客时间可以看出，我们已经将十进制数181338494转换为由合法的URL字符组成的“62位十六进制数”——cgSqq。至此，我们不仅生成了一条短链，而且大大缩短了短链的长度。这就是使用哈希算法生成唯一练习题的全部内容。总结一下：首先，使用MurmurHash生成哈希值，使用rehashing解决哈希冲突问题。然后将十进制的hash值转换为base62的合法URL字符，从而缩短URL的长度。分布式ID生成短链使用哈希算法生成唯一短链的方法比较形象。但其实我们也可以使用分布式ID来完成唯一短链的生成。比如对于第一次请求的长链，我们为其生成一个唯一ID，并将长链与唯一ID关联起来。对于第二个请求，我们为其生成一个唯一ID，并再次将长链与唯一ID关联起来，如下图。第一次请求：https://mp.weixin.qq.com/s1caec8eb1b81d6ee5dd7b↓↓生成短链接：https://dwz.com/1021000001第一次请求：https://mp.weixin.qq.com/s1caec8eb1b81d6ee5ff7b↓↓生成短链接：https://dwz.com/1021000002因为生成的uniqueID也可能很长，所以我们可以用上面同样的方法将十进制的uniqueID转换为base62字符的合法URL，从而缩短字符长度。那么接下来的问题就变成了：如何设计一个全球唯一的IDissuer。如何设计一个全局唯一的ID生成器是另外一个话题，这里不再赘述。性能优化看到这里，我们基本有了一个完整的思路：得到长链地址后，可以通过哈希算法或者唯一ID分号获取唯一字符串，从而建立长链和短链的映射关系.为了缩短短链的长度，我们也可以用十六进制表示，整个短链的生成过程如下图所示。短链生成示意图短链已经生成并存入数据库，接下来就可以使用了。通常的做法是根据请求的短链串从数据库中查找数据，然后返回HTTP重定向原地址。在不断使用的过程中，还有一些可能会发现的优化点，这里简单说一下。索引优化如果使用关系型数据库，需要为短链字段创建唯一索引，以加快查询速度。当增加缓存并发量小的时候，我们都是直接访问数据库。但是当并发量再次增加时，就需要增加缓存来抵抗热数据的访问。读写分离短链服务肯定是读远远多于写，所以对于短链服务，可以做读写分离。如果分库分表是商业化的短链服务，数据量上亿也是正常的，更何况是多年积累的量。这时候可以一开始就做好分库分表的操作，避免后期再打架。分库分表，最关键的是，以哪个字段作为分库分表的依据。对于短链服务，当然是用转换后的62位数字作为分表的依据，因为它是唯一的。至于如何分库分表，涉及到分库分表的知识，以及系统容量的预估，这里不再赘述。如果有机会，我们会找个时间来深入谈谈这方面的事情。为了防止对公网开放的服务进行恶意攻击，任何事情都有可能发生。其中一个可能点就是被恶意攻击，不断循环调用。一开始我们可以做一个简单的限流操作。例如，未经授权的用户每分钟最多只能根据IP发出10次请求。对于未经授权的用户，所有用户每分钟最多只能请求4000次，以防止通过更改IP地址进行攻击。简单的说，就是要不断提高攻击的成本，让系统在最坏的情况下仍然可以正常提供服务。总结本文首先讲了短链的三个价值：简单、易用、节约成本。然后解释了短链的原理就是HTTP重定向。最后重点介绍了短链服务的设计思路。在短链服务设计思路上，最重要的是解决两个问题：基于长链生成短链，基于短链寻找长链。关于基于长链生成短链的思路，我们讲了两种实现思路，分别是：哈希算法生成短链，分布式全局ID生成短链，其中哈希算法涉及到哈希算法的选择和哈希冲突的处理。最后，我们也列出了短链服务后续可能的一些优化点，包括：如何缩短URL，索引优化，增加热点数据，读写分离，分库分表，防止恶意攻击，等短链服务如何设计？参考系统设计系列：如何设计一个短链服务_架构_看山_InfoQ写的社区很好！贵宾！实践经验！高性能短链接设计-掘金【原创】这可能是东半球最接地气的短链接系统设计-孤烟-博客园不错，这个很全面！贵宾！面试官：如何设计短链接系统——小黑说56|算法实战（五）：如何利用所学的数据结构和算法实现短网址系统？把它当作甜点吃。短网址系统是如何设计的？-iammutex的回答-哈希算法知乎-廖雪峰官网
