By

前言

Github：https://github.com/HealerJean

博客：http://blog.healerjean.com

1、短链接介绍

短码一般是由 [a - z, A - Z, 0 - 9] 这62 个字母或数字组成，短码的长度也可以自定义，但一般不超过8位。比较常用的都是6位，6位的短码已经能有568亿种的组合：(26+26+10 ) ^ 6 = 56800235584，已满足绝大多数的使用场景。

目前比较流行的生成短码方法有：自增id、摘要算法、普通随机数。

2、短连接生成方案

2.1、自增id

该方法是一种无碰撞的方法，原理是，每新增一个短码，就在上次添加的短码id基础上加1，然后将这个10进制的id值，转化成一个62 进制的字符串。

生成方法：数据库自增主键、Redis 的 INCR、分布式ID（雪花算法）

2.1.2、缺点

1、短码 id 是从一位长度开始递增，短码的长度不固定

2、生成的短码是有序的，可能会有安全的问题

2.2、普通随机数

从 62 个字符串中随机取出一个 6位短码的组合，然后去数据库中查询该短码是否已存在。如果已存在，就继续循环该方法重新获取短码，否则就直接返回。

2.2.1、优缺点

优点：该方法是最简单的一种实现

缺点：

1、不过由于Math.round()方法生成的随机数属于伪随机数，碰撞的可能性也不小。

2、在数据比较多的情况下，可能会循环很多次，才能生成一个不冲突的短码。

2.2、单项散列函数

步揍：通常的设计方案是

1、将长 URL 利用 MD5 或者 SHA256 等单项散列算法，进行 Hash 计算，得到 128bit 或者 256bit 的 Hash 值。

2、然后对该 Hash 值进行 Base64 编码，得到 22个或者 43 个 Base64 字符，再截取前面的 6 个字符，就得到短 URL 了

问题：这样得到的短 URL，可能会发生 Hash 冲突，即不同的长 URL，计算得到的短 URL 是相同的（MD5 或者 SHA256 计算得到的 Hash 值几乎不会冲突，但是 Base64 编码后再截断的 6 个字符有可能会冲突）。

解决：在生成的时候，需要先校验该短 URL 是否已经映射为其他的长 URL，如果是，那么需要重新计算（换单向散列算法，或者换 Base64 编码截断位置）。重新计算得到的短 URL 依然可能冲突，需要再重新计算。

2.2.1、优缺点

优点：链接的长度始终不变，同一长链接多次生成短链接，结果不变

缺点：哈希算法可能会产生冲突，虽然几率很小，但是该方法依然存在碰撞的可能性，解决冲突会比较麻烦。

2.3、预生成压缩码

建议采用预生成压缩码 的方案：即预先生成一批没有冲突的短 URL 字符串，当外部请求输入长 URL 需要生成短 URL的时候，直接从预生成成好的短 URL 字符串池中获取一个即可。

预生成短 URL 的算法可以采用随机数来实现，6 个字符，每个字符都用随机数产生（用 0~63 的随机数产生一个 Base64 编码字符）。为了避免随机数产生的短 URL 冲突，需要在预生成的时候检查该 URL 是否已经存在（用布隆过滤器检查），这些操作都是在生产短链接之前就完成的，所以不会影响生成短链接的性能。

3、实现方案

选择：摘要算法。

3.1、数据库存储

1、域名和后缀存储设计：短网址基础数据采用域名和后缀分开存储的形式。另外域名需要区分 HTTP 和 HTTPS，hash方案针对整个链接进行hash 而不是除了域名外的链接。域名单独保存可以用于分析当前域名下链接的使用情况。

2、链接有效期设计：增加当前链接有效期字段，一般有短链需求的可能是相关活动或者热点事件，这种短链在一段时间内会很活跃，过了一定时间热潮会持续衰退。所以没有必要将这种链接永久保存增加每次查询的负担。

字段 说明
base_url 域名
suffix_url 链接除了域名外的后缀
full_url 完整链接
shot_code 当前 suffix_url 链接的短码
expiration_date 失效日期
total_click_count 当前链接总点击次数
base_url suffix_url shot_code total_click_count full_url expiration_date
http://www.aichacha.com /search/12345 edfg3s   http://www.aichacha.com//search/12345  
http://www.aichacha.com /aiCheck/getResult/123 Fe9dq   http://www.aichacha.com//aiCheck/getResult/123  

3.2、缓存设计

如果短连接非常多，对于几百个G的数据量都放在缓存肯定不行，因此考虑缓存时间限制：缓存时间3个月，命中缓存，就不用走库。查不到的时候再走库更新缓存。

4、短链接跳转

例如访问http://code.cn/a5dw98

1、DNS进行解析，得到code.cn域名对应的IP地址

2、向得到的IP地址发送GET请求，查询短码a5dw98

3、服务器通过短码查询数据库得到对应的长URL

4、请求通过HTTP 301状态码，将请求重定向到长URL

⬤ 301：永久重定向、搜索引擎在抓取新的内容的同时也将旧的网址替换为了重定向之后的网址，使用301无法统计短链接被点击的次数，无法收集用户的Cookie等信息。

⬤ 302：临时重定向、搜索引擎会抓取新的内容而保留旧的地址，搜索搜索引擎认为新的网址是暂时的，302跳转每次会去访问短链接服务器，从而获取长链接再去访问，效率低而且会给短链接服务器负载压力。

ContactAuthor