短网址 望文生义，即是将长网址缩短到一个很短的网址，用户拜访这个短网址能够重定向到原本的长网址（复原）。这么能够到达易于回忆、变换的目的，常用于有字数约束的微博、二维码等场景。
开篇先抛出几个疑问，假如咱们自个去完成会怎样完成这个看似很简略的效劳呢？

1. 是不是有啥算法能够直接把一百个字符左右的长网址缩短到10位以内，并能够原样复原，即可逆。
   10倍的紧缩比在无损紧缩算法范畴谁介绍下？当然这个比例是依据多样数据而不是特定的文本，不然文本只需一个字符a，那紧缩比想多少有多少。

2. 只完成字符紧缩/hash，不需求做到可逆，然后存储到数据库中，恢复时只需求查询数据库。
   从紧缩的视点和第一条阐明没有差异，不也许无损紧缩，那就有也许呈现hash磕碰。不一样的长网址缩短成了同一个短网址，那也做不到复原了。

3. 接着第二条，呈现磕碰了能够后边再加随机字符。
   随机字符能够缓解磕碰疑问，可是无法彻底治愈。别的，增加几位字符呢才牢靠呢？这种概率事件无法经过测验来答复，经过运维监控不断的调整也是一件头疼和折磨人的事。

4. 预先在redis/db里异步生成一批短码，每次从列表里边取不就好了。
   详细是在redis仍是db里批量生成本来是截然不一样的两种完成。 假如redis, 那么里边要放入全量的短码么？不然怎样知道这个短码究竟是不是仅有的？假如全量，那对redis的可用性就要严厉确保，不然它挂了，就必须全量的预热，这个进程要做好不是那么的简略； 假如db, 那么就要有许多的并发确定，意味着许多读写，这个对数据库也是个检测。

5. 短网址的复原跳转用301仍是302呢？
   301是持久重定向，302是暂时重定向。短地址一经生成就不会改变，所以用301是契合http语义的。一起浏览器会对301恳求保留一个对比长时刻的缓存，这么就减轻对效劳器的压力；并且301关于网址的SEO有必定的提高。可是许多状况下咱们需求对接口点击或许用户做法进行一些事务监控处理的时候，301显着就不适宜了（浏览器直接依照缓存数据跳转了）, 所以许多事务场景下仍是选用302对比适宜。

请结合上述疑问后的描绘思考5分钟，然后咱们开端正文

首要声明这篇文章规划思路也仅仅取自个事务场景能够容忍的状况，而有所取舍.
没有完美的体系只需适用的体系。

缩短网址的算法

# 初期选型算法

关于算法自个也算是踩了不少的坑，最开端选用的是网上撒播甚广的微博短网址算法(原理相似16进制与62进制的变换)，加了少许改善：

1. 将"原始连接（长连接）+ key(随机字符串,避免算法走漏)"MD5后得到32位的一个字符串A

2. 将上面的A字符串分为4段处理， 每段的长度为8 ， 比方四段分别为 M、N、O、P

3. 将M字符串当作一个16进制格局的数字来处理， 将其变换为一个Long类型。 比方变换为L

4. 此刻L的二进制有用长度为32位， 需求将前面两位去掉，留下30位 ， 能够 & 0x3fffffff 进行位与运算得到想要的成果。（30位才能变换62进制，不然超出）

5. 此刻L的二进制有用长度为30位， 分为6段处理， 每段的长度为5位

6. 顺次取出L的每一段（5位），进行位操作 & 0x0000003D 得到一个 <= 61的数字，来作为index

7. 依据index 去预界说的62进制字符表里边去取一个字符， 最终能取出6个字符，然后组装这6个字符变成一个6位字符串，作为短连接码

8. 拿出第②步剩下的三段，重复3-7 步

9. 这么一共能够获得 4 个6位字符串，取里边的恣意一个就可作为这个长连接的短网址

10. 串码增加校验位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，所以拜访量监控都不是疑问

文终。
任何遗漏或许定见，期待评论。