短链接服务原理

三月 14, 2018 web后端

本文介绍短链接服务的实现原理。

很多人都用过短链接服务，简单来说就是把一个很长的URL转换成一个很短的URL。比如我们使用百度的短链接服务http://www.dwz.cn/，对https://nodejs.org/en/docs/guides/getting-started-guide/这个URL进行短链接处理，会得到http://www.dwz.cn/7A3VlG，可以看到URL缩短了很多。

需求

给定一个原始URL，将其转换为一个短链接（啊废话！），并且需要非常大短链接地址池（近乎无限）。
原始URL和其短链接要能双向转换。
短链接永久有效。
短链接服务要能够承受较大的并发量。
服务的可扩展性。

设计

原始URL->短链接

首先是将原始URL转换为短链接，先考虑一下短链接长什么样。假设我们有一个短链接域名t.me，这是我乱编的一个域名。很容易发现可以使用[0-9a-zA-Z]一共62个字符来构建短链接，也就是一个62进制的计数方式。比如短链接可以可以是这样样子：t.me/xyz、t.me/p6H，诸如此类。

可能有同学会说这里的转换可以用hash，计算原始URL的hash值，然后映射到一个范围内，比如[0, 2^64-1]，然后将映射值转换成62进制的形式就得到对应的短链接了。这种方式乍一看很合理，但实际上这种做法忽略了一个事实，hash存在冲突问题，当然我们可以用一些手段去解决hash冲突，但是这无疑增加了系统复杂性。

其实有更简单方便的方式来做这个转换，可以利用自然数递增这个天然特性。例如，设计一个发号策略，对第1个原始URL发号0，第2个原始URL发号1，第100个原始URL发号100，以此类推。由于自然数是无限的，因此我们能够发的号也是无限的。发号后，将这个自然数转换成62进制就得到我们的短链接了。比如第0个原始URL对应的短链接就是t.me/0，第1个原始URL对应t.me/1，第10个原始URL对应t.me/a，第36个原始URL对应t.me/A，第100个原始URL对应t.me/1C，以此类推。

另外，还需要在DB中存储原始URL和短链接的对应关系，例如使用MySQL。

原始URL和短链接的双向转换

从原始URL到短链接的转换机制已经设计好了，对于从短链接到原始URL的转换也很简单，只需要将原始URL和短链接的关系存储起来即可。比如可以在为原始URL创建短链接时，将对应关系写入K-V存储，比如Redis或者memcached，将短链接做key，原始URL做value。之后当用户使用短链接访问时，我们立刻可以查询到其对应的原始URL，然后将用户302重定向到这个原始URL。

短链接永久有效

短链接永久有效主要是用户体验问题，用户肯定不希望一个短链接只有很短的有效期。

在原始URL->短链接部分，我们最后将原始URL和短链接的对应关系持久化存储了，这可以保证我们一定能通过一个存在的短链接找到它对用的原始链接。

但是每次根据短链接查找原始URL都要查一次DB效率太低，尤其是并发量大的时候。刚才在原始URL和短链接的双向转换部分将短链接和原始URL的关系写入K-V存储，这个查询可以在内存中完成，效率很高。但是单实例的K-V存储的数据量是有限的，就算使用集群，相对于近乎无尽的原始URL，储存量也还是有限。所以在不影响用户使用的情况下K-V存储的原始URL和短链接对应关系需要一个淘汰机制。我们可以对一个原始URL和短地址的key-value设置过期时间，比如1小时。当key-value还未过期时，每次用户访问短地址都会将该key-value的过期时间再次更新为1小时。

如果某个key-value被淘汰之后又有用户使用该短链接查询，此时我们可以再去DB中查找对应关系，将用户重定向，同时将这个对应关系写一份缓存到K-V存储。

应对大并发量

之前提到发号器，可以使用Redis来做，设置一个key原始值为0，每过来一个原始URL就对其发放一个值，然后发号器的值自增1。这里就有一个单点问题，如果这个节点挂了，服务整体也就挂了，一个发号器发号大并发量扛不住。

可以设计N个发号器，比如100个。这100个发号器的初始值从0-99，每次发号后自增值为N。例如，0号发号器的初始值为0，每次自增100，发号序列就是0，100，200，300…，1号发号器的初始值为1，每次自增100，发号序列就是1，101，201，301…，99号发号器初始值为99，每次自增100，发号序列就是99，199，299，399…。

这样各个发号器都在一个固定的数值序列上发号，如果后期想继续扩展也简单，多设置发号器就好了。

可扩展性

如果整个系统的并发量和数据量都很大，或者可以预见未来增长很大。为了高可扩展性，K-V存储和持久化都需要使用集群做数据分片。然后使用一些路由策略将数据分布到每台具体实例上。具体的数据分片方法这里就先不描述了，数据分片这个话题本身都可以单独成文。