短网址 顾名思义，就是将长网址缩短到一个很短的网址，用户访问这个短网址可以重定向到原本的长网址（还原）。这样可以达到易于记忆、转换的目的，常用于有字数限制的微博、二维码等场景。
开篇先抛出几个问题，如果大家自己去实现会怎么实现这个看似很简单的服务呢？
是否有什么算法可以直接把一百个字符左右的长网址缩短到10位以内，并可以原样还原，即可逆。
10倍的压缩比在无损压缩算法领域谁介绍下？当然这个比例是基于多样数据而不是特定的文本，否则文本只有一个字符a，那压缩比想多少有多少。只实现字符压缩/hash，不需要做到可逆，然后存储到数据库中，恢复时只需要查询数据库。
从压缩的角度和第一条说明没有区别，不可能无损压缩，那就有可能出现hash碰撞。不同的长网址缩短成了同一个短网址，那也做不到还原了。接着第二条，出现碰撞了可以后面再加随机字符。
随机字符可以缓解碰撞问题，但是无法根治。另外，增加几位字符呢才可靠呢？这种概率事件无法通过测试来回答，通过运维监控不断的调整也是一件头疼和折磨人的事。预先在redis/db里异步生成一批短码，每次从列表里面取不就好了。
具体是在redis还是db里批量生成其实是截然不同的两种实现。 若是redis, 那么里面要放入全量的短码么？否则怎么知道这个短码到底是不是唯一的？如果全量，那对redis的可用性就要严格保证，否则它挂了，就必须全量的预热，这个过程要做好不是那么的容易； 若是db, 那么就要有大量的并发锁定，意味着大量读写，这个对数据库也是个考验。短网址的还原跳转用301还是302呢？
301是永久重定向，302是临时重定向。短地址一经生成就不会变化，所以用301是符合http语义的。同时浏览器会对301请求保存一个比较长期的缓存，这样就减轻对服务器的压力；而且301对于网址的SEO有一定的提升。但是很多情况下我们需要对接口点击或者用户行为进行一些业务监控处理的时候，301明显就不合适了（浏览器直接按照缓存数据跳转了）, 所以很多业务场景下还是采用302比较合适。
请结合上述问题后的描述思考5分钟，然后我们开始正文
首先声明本文设计思路也只是取自己业务场景可以容忍的情况，而有所取舍.
没有完美的系统只有适用的系统。
缩短网址的算法
# 初期选型算法
对于算法本人也算是踩了不少的坑，最开始采用的是网上流传甚广的微博短网址算法(原理类似16进制与62进制的转换)，加了些许改进：
- 将"原始链接（长链接）+ key(随机字符串,防止算法泄漏)"MD5后得到32位的一个字符串A
- 将上面的A字符串分为4段处理， 每段的长度为8 ， 比如四段分别为 M、N、O、P
- 将M字符串当作一个16进制格式的数字来处理， 将其转换为一个Long类型。 比如转换为L
- 此时L的二进制有效长度为32位， 需要将前面两位去掉，留下30位 ， 可以 & 0x3fffffff 进行位与运算得到想要的结果。（30位才能转换62进制，否则超出）
- 此时L的二进制有效长度为30位， 分为6段处理， 每段的长度为5位
- 依次取出L的每一段（5位），进行位操作 & 0x0000003D 得到一个 <= 61的数字，来当做index
- 根据index 去预定义的62进制字符表里面去取一个字符， 最后能取出6个字符，然后拼装这6个字符成为一个6位字符串，作为短链接码
- 拿出第②步剩余的三段，重复3-7 步
- 这样总共可以获得 4 个6位字符串，取里面的任意一个就可作为这个长链接的短网址
- 串码添加校验位checksum，用于简单校验。所以总共7位码
算法其实并不太复杂，大家自行解读。这个算法在服务量不大的情况下hash碰撞的概率尚可以接受，一定量的压测效果也还算理想。因为有4个hash可选项，即使碰撞到了还有其他3次机会去避免。但是如果作为基础服务，在使用方调用量级无法估量无法保证短链接绝对可用的情况下，这个算法还是有很大的隐患！
# 改进算法
只要有hash就有碰撞的可能，要一劳永逸就得抛弃hash算法。这里我们就用全局自增长的10进制序号 -> 62进制实现。这里继续抛出问题来了：
1. 字符超长问题
即使到了10亿(Billion)转换而成的62进制也无非是6位字符，所以长度基本不在考虑范围内，这个范围足够使用了。
2. 短码安全问题
按照算法从0-61都是1位字符，然后2位、3位...这样的话很容易被人发现规律并进行攻击，当然防御手段很多，请求签名之类的安全验证手段不在本文讨论范围内。
首先计数器可以从一个比较大的随机中间值开始，比如从10000开始计数，他的62进制是 2Bi 3位的字符串；
然后采用一些校验位算法(比如Luhn改进一下)，计算出1位校验位拼接起来，4位短码，这样可以排除一定的安全风险；
再加点安全料的话，可以在62进制的转换过程中把排序好的62个字母数字随机打乱，比如ABCD1234打乱成1BC43A2D, 转换的62进制也就更难hack了；
最后如果仍不放心，还可以在某些位置（比如1，3，5）插入随机数，让人无法看出规律来也可以达到良好的效果。
3. 同一长网址短码是否应该相同问题
这个问题按照码农的完美主义原则，基本上回答是Yes。做到也不麻烦，比如对长网址进行sha1生成的hash值存入hashtable或者redis，在缩短之前进行hash值比对，如果相同就查询出之前生成的短码即可。
但是缓存内预热多少sha1值让其比对，多少会穿透到数据库进行比对，就是你自己需要对热点数据如何预热和缓存命中的问题了，这里不展开。
4. 自增算法是否完美无缺
相比上面的hash分段算法，自增算法能已经基本可以保证码唯一、同址同码的目标了。但是它也有缺陷，那就是随着序号的自增，码越来越长，到了很大的数值后没有办法循环往复，让码重新变短！而hash分段就没有这个问题。
所以这两个算法其实各有优劣，如果业务所需的短网址有效期相对较短，通过批处理定期清洗掉，那第一种算法不失为一种可选方案；
而自增算法对于无差别的业务短网址，可以保证任何的请求量都不会出现冲突，权衡下来不失为最佳之选。码无非分为永久码或临时码，结合业务的话其实大部分的码都是临时码，只是或长或短而已，所以甚至可以设计永久的码序号区间是0-10000，0-5天的码10001-20000，5-30天的码20001-30000，30天+的码30001-无穷。这样就可以实现序号的重复使用了。当然如果你对自己设定的区间没有自信的话（溢出），请千万不要这么做。
Redis/DB 如何设计
# DB设计
只需要一张表，存放短码与原网址的映射关系，其他一些属性比如原网址的sha1码，过期时间等保存好即可。当然短码和sha1字段都要加上唯一索引，保证唯一性的同时提高查询效率。
# Redis设计
若想短链接服务达到低延迟高并发的目标，Redis在很多环节都可以起到关键作用。
1. 自增长序列
通过Redis的 incr 方法可以很容易的实现全局自增长序列，但前提是Redis的高可用，如果Redis挂了序列从哪里开始呢？当然是从DB中拿咯，怎么拿？
方式一：DB表中新增一个字段，存入最新的短码基于的序号值，然后Redis在此基础上+1即可。这部分代码务必做好同步； 方式二：直接从DB中获取最新的短码，然后逆向计算出序号值，+1后继续；
2. 长网址的Hash表
在Redis中存入热点网址的hash映射数据，注意，这里说的是热点网址而且不是全量网址，实现者需要有所取舍。或者没有命中的就产生新的短码（会导致同址不同码），或者没有命中就到数据库查询，保证强一致的同址同码。
3. 短码与长网址的映射表
同样，在Redis中存入热点网址的映射，在短网址还原的请求处理中可以快速的查询到原网址。所以这个点的缓存是必须的。
其他一些说明
- 原网址的Hash方法文中是sha1是选择之一，类似Murmur64等更快更优的hash算法，可以自行采纳
- 类似的服务已经有比较成熟的开源解决方案，比如YOURLS，不想重复造轮子的同学可以直接拿来用
- 如果要对短链接做一些监控，比如访问量，可以通过Redis自行实现。目前公司应用集成了点评开源CAT，所以访问量监控都不是问题
文终。
任何疏漏或者意见，欢迎讨论。
