短网址生成系统的作用主要就是把一个很长的网址转换成一个较短的。 比如，谷歌的 https://goo.gl、百度的 http://dwz.cn、腾讯的 http://url.cn 都是常见的短网址系统。 工作能力通常包括读、写两个方面。在查询方面，它应当接收一个短网址的 GET 请求，然后返回一个 301 或者 302 的响应， 跳转地址为对应的长网址。当然，它肯定同时支持接收某个长网址，返回一个生成的短网址，而且也只有生成过的短网址后续可以查询到。
系统用途
短网址相较于转换前的长网址有很多优势：
- 在分发和使用的时候更方便、清爽（如短信推广）
- 更好地适应知乎、短信等有字数限制的场景
- 降低生成二维码的复杂度（编码点阵复杂度与网址长度成正比）
- 可以一定程度上隐藏部分 url 参数
- 方便实现对链接的跟踪和数据统计
- 可以在原网址失效后不改变短网址，只修改跳转关系，实现重新定向
关键功能设计
短网址系统最核心的部分就是长短链之间的转换了。有效的长网址显然是无限多的，根据信息论的知识， 不可能存在可逆的压缩算法将其变成一个长度有限的短网址，因此必须借助存储系统来保存映射关系。
读流程直接查询存储系统返回就行了。
一般来说，我们希望一个长网址只对应一个短网址，所以写流程要先检查提供的长网址是否已经有映射了，如果已经存在了就直接返回已有的短网址， 否则生成一个新的短网址插入存储并返回，且这个短网址必须与已有的都不相同（即满足唯一性）。
存储
可以使用 MySQL 等关系型数据库存储映射关系，存储字段定为短网址、原网址（即长网址）、原网址的短哈希（比如 sha1）、创建时间等， 在短网址和原网址的短哈希上加索引。额外存储“原网址的短哈希”就是为了用它替代“原网址”做索引以降低索引开销。 读流程按短网址搜索记录：
SELECT * FROM url_map WHERE short_url = "xxx";
写流程预检查时按原网址及其短哈希搜索记录（短哈希放检索条件前面以先走它的索引）：
SELECT * FROM url_map WHERE original_url_hash = SHA1("yyyyy") AND original_url = "yyyyy";
写流程实际插入新记录时比较简单：
INSERT INTO url_map
(short_url, original_url, original_url_hash)
VALUES
("xxx", "yyyyy", SHA1("yyyyy"));
读缓存
一般，短网址系统是一个读多写少的系统，所以增加一个读缓存是很有必要的。 这个缓存的 Key 选为短网址，Value 选为原网址。因为任一个 Key 的 Value 都不会变化， 所以也不需要考虑缓存更新导致的一致性问题，只要做好过期淘汰就好了。 可以选用 Redis 等内存缓存系统，甚至可以考虑本地内存缓存（延迟更低）。
布隆过滤器
写流程每次预检查时都需要穿透到数据库进行查询，有可能会成为写流程的瓶颈。 一个直觉解是增加一个反向的 KV 缓存，但是毕竟系统是读多写少的，为了少数的请求增加一倍的存储空间多少有点划不来。 更合适的方案是使用一个布隆过滤器，只要 500M 左右的内存空间就能完成 20 亿左右 url 集合的判断。 生成新的短网址映射时同步把原网址插入布隆过滤器，而每次预检查时都先检查布隆过滤器： 如果它表示该网址不存在，那就是一定不存在，可以直接生成新的短网址；反之则是有概率存在，需要实际穿透到数据库进行查询。
发号方案
写流程生成新的短网址时需要确保其唯一性，所以需要考虑唯一 id 的生成方案。
同时这个 id 还要足够短：假设短网址为 7 位（不含域名）。（为了尽可能多的存信息，把英文大小写、数字都利用上，
最终有效网址有 (26*2 + 10)^7 = 62^7 < 2^42 个，基本也够用。）
UUID 类似方案可以保证唯一性，但是其长度过长（128 bit），不适宜直接用作短网址； 如果在此基础上截取或压缩长度，那唯一性又不能保证了。所以这种方案不可行。
自增 ID 可以保证唯一性。自增 ID 的生成可以利用数据库的自增主键、Redis 原子 incr 命令、雪花算法等， 细节可参考这篇文章。 这个方案的问题主要在于两点：其一，如果额外依赖发号数据库或 Redis 等，调用延迟会增加而可用性会下降； 其二，自增 ID 规律性太强，容易被恶意攻击者猜测到。
短网址也可以用原网址的哈希来做，比如 MurmurHash。MurmurHash 是一种非加密型哈希函数，由 Austin Appleby 在 2008 年发明， 与其它流行的哈希函数相比，对于规律性较强的 key，它的随机分布特征表现更良好。 但是，哈希方案必须解决哈希碰撞的问题，在这里表现为多个长网址映射成同一个短网址（即违反唯一性）。 检测哈希碰撞的可行解包括利用数据库唯一索引和查询读缓存（看新生成的短网址是不是已经映射给其他长网址了）。查缓存本身比数据库操作更快些，但是插入数据库是本来就要做的， 而查询读缓存是额外增加的，为了小概率发生的哈希碰撞每次都查一次缓存不大合理，所以最好只利用数据库唯一索引解决。 检测到哈希碰撞之后可以通过改变 MurmurHash 的 seed 等方法重新哈希。
补充
因为映射关系实际上都是整行增加、查询的，也没有用到表关联操作，所以实际上可以用 RocksDB 等持久化 KV 引擎替代关系型数据库来存储。 因为短网址、原网址都会被用于查询，所以一条记录必须存储双向的映射，这样一来，布隆过滤器也没有存在的必要了。
如果要支持链接有效期功能，就要在数据库和缓存中都加入“过期时刻”字段，过期的映射在查询时视为不存在。 另外还要考虑是否要删除过期的映射，若进行删除，则能节约存储空间，但会一定程度上失去归档能力， 且很小概率会出现一个短网址在不同时刻对应两个不同长网址的情况（第一个映射过期被删后，第二个映射的短网址恰好与前者的相同）。 如果要删除，可选的清理策略为定期删除（比如每天半夜流量较少时）、延迟删除（读到过期的记录就顺便删除）和两者相结合（推荐）。
短网址查询的重定向 HTTP 状态码可选 301 或 302。 前者为永久重定向，浏览器会进行缓存，后续请求直接跳转原网址而不重复请求短网址系统。 这会导致无法在短网址系统处准确统计到访问次数等信息，也会导致不能支持动态修改跳转关系（上述的设计暂未支持），但会显著减少服务端压力。
参考资料：
