[Markdown阅读][1]

今天上班的时候收到一个需要短链接的需求，之前的做法都是使用了新浪的短链接API（https://api.weibo.com/2/short_url/shorten.json）。但一是外网访问，二可能是新浪有所限制（毕竟是免费的），性能肯定不是太好。于是就想能不能自己实现一个，这样内网访问肯定快不少。

下班在班车上想了下，初步有些思路，记录一下，有什么说错的，欢迎指正。关于短链接的问题，我首先想到是两个问题：

 1. 持久化的问题，是否有必要保证短链接永久有效？

 2. 碰撞的问题，如何保证所有长链接对应的短链接是唯一的？

第一个问题我想如果能有一个算法直接对`url`本身进行计算然后得到一个短链接，而且是可逆那么这个问题就不存在了，但稍微一想就知道这个不大现实，比如类似md5这样的摘要算法，一是不可逆，必然还是需要存储一个映射关系的，二为了“短”，第2个问题肯定会更加突出。

此路不通，我想肯定还是得引入`DB`的，因为平时项目中使用`Redis`比较多，直觉它比较合适。对于存储这种映射关系，`NoSQL`最合适不过了。而且`Redis`数据结构灵活，API简单明了，性能也很不错。开启`EOF`后，持久化问题也能得到保证，另外`Redis`支持过期，可以满足一些特殊的需求。

再来看性能问题（初衷就是想提高性能的）。个人觉得要提高性能，如何解决第2个问题是关键。我有一个思路相信也是大家都能想到的：“提前计算”和“缓存”，说就是`先计算好一批短链接缓存起来，请求过来直接取就可以了`。这里大概还有以下几个问题：

 1. 怎么保证缓存起来的短链接都是各不相同的？

 2. 怎么保证缓存起来的跟历史生成的不相同？

 3. 怎么保证供大于求？

第1个问题，应该比较简单，编码应该是能解决的。第2个问题我考虑两个方面：

1）短链接的基数必须足够大。

参考新浪短链接http://t.cn/RhCtEye，6位字符，取值范围在[a-zA-Z0-9]，那么基数就是`56,800,235,584`，56亿多应该说是足够大的了。那么就要看`随机算法`，只要足够随机，那么两次重复的概率就很小了。

2）以防万一，每次都去做一次check，按照上面的想法，生成的短链接映射关系都是存储在`Redis`中的，只要一次`get`就可以了。`get`的时间复杂度为[O(1)][1]，只要保证数据都在内存里是非常快的（加上内网访问）。

第2）点在非常高的并发下还是有问题的，可能存在`get`的时候一个相同的key刚好还没`set`的进来，但结合第1）点这种可能性应该说是非常非常小了，而且我们实际的并发也不是特别大，所以忽略不计。

第3个问题更多是设计上的考虑。我的想法是用一个阻塞队列来实现，综合前面的问题，那应该就是一个去重的阻塞队列。至于如何保证“供大于求”，那就得根据前端的压力来调整队列的大小了。

这里还有一个问题，就是相同的url生成短链接的问题，如果要保证相同的url只对应一个短链接，那就得每次生成之前要去`Redis`找回一下（批量可以`mget`[O(N)][2]），增加了性能损耗，但是当这种情况很多的时候，比如恶意请求，那么反而会更好。可以作为可选配置。

上面说的都是短链接生成的问题，短链接重定向也就是还原到原始链接相对简单，一个`get`操作就可以搞定了，如果为了提高性能，减少不必要的`Redis`访问，可以在应用层增加一层Cache，比如`LRU Cache`。

最后说下存在的瓶颈：

 1. 短链接的随机生成算法，`java.util.Random`貌似不是非常靠谱；

 2. 去重的阻塞队列，这个应该是最大的瓶颈，如果一个队列，并发性能就很容易受限于此，如果搞多个，那么碰撞的问题就比较棘手；

 3. Redis的性能。其实这里Redis可以换成任何其他类似的`NoSQL`产品。

好了，把脑子里想的写完了，感觉实际应该够用了。有问题欢迎拍砖。

  [1]: https://www.zybuluo.com/zhanjindong/note/34734

  [2]: http://redis.readthedocs.org/en/latest/string/get.html

  [3]: http://redis.readthedocs.org/en/latest/string/mget.html