【每日一击】(20.5.25)- 高性能短链设计

[XJIANBIN]

短链的好处

• 1 链接变短，对于在内容长度有限制的平台，可编辑的文字就变多了（如微博140）
• 2 当把链接转成二维码分享给别人，长链可能会造成二维码密集难识别

短链跳转的原理

请求短链后，返回了状态码 302（重定向）与 location 值为长链的响应，然后浏览器会再请求这个长链以得到最终的响应。

• 301：永久重定向，也就是当浏览器第一次拿到长链接之后，下次不再请求短网址服务，而是直接在浏览器缓存里拿，这样会造成sever 层面无法统计到真实的短网址点击数
• 302 ：临时重定向，也就是每次都会去请求短网址服务器，这样就便于server统计点击数

短链生成的方法

格式：由固定短链域名 + 长链映射成的一串字母组成，如：https://gk.link/a/10asdf

1哈希算法：

因为对于短链这种服务，我们不用关心解密的难度，更关心的是哈希的运算速度和冲突概率，所以md5, SHA等算法并不太适用。满足这种场景的有google 出品的MurmmurHash 算法，是一种非加密型哈希函数，适用于一般的哈希检索操作。与其他的哈希函数相比，对于规律性比较强的key, 它的随机分布特征表现更良好。MurmurHash 提供了两种长度的哈希值，32 bit，128 bit，32 bit 能表示的最大值近 43 亿。

2 如何再缩短

http://gk.link/a/3002604296，比如3002604296 得到的这个哈希值是十进制的，那我们把它转为 62 进制可缩短它的长度，于是我们有 (3002604296)10 = (3hcCxy)10，一下从 10 位缩短到了 6 位！于是现在得到了我们的短链为 http://gk.link/a/3hcCxy

3 如何解决hash 冲突

我们访问短链能跳转到长链，需要我们保存这两者之间的映射关系。可以使用redis 或者mysql 存储。

• 1 将长链（lurl）经过 MurmurHash 后得到短链。
• 2再根据短链去 short_url_map 表中查找看是否存在相关记录，如果不存在，将长链与短链对应关系插入数据库中，存储。
  • 如果存在，说明已经有相关记录了，此时在长串上拼接一个自定义好的字段，比如「DUPLICATE」，然后再对接接的字段串「lurl + DUPLICATE」做第一步操作，如果最后还是重复呢，再拼一个字段串啊，只要到时根据短链取出长链的时候把这些自定义好的字符串移除即是原来的长链。

以上步骤显然是要优化的，插入一条记录居然要经过两次 sql 查询（根据短链查记录，将长短链对应关系插入数据库中），如果在高并发下，显然会成为瓶颈。一般数据库和应用服务（只做计算不做存储）会部署在两台不同的 server 上，执行两条 sql 就需要两次网络通信，这两次网络通信与两次 sql 执行是整个短链系统的性能瓶颈所在！

优化:

• 首先我们需要给短链字段 surl 加上唯一索引
• 当长链经过 MurmurHash 得到短链后，直接将长短链对应关系插入 db 中，如果 db 里不含有此短链的记录，则插入，如果包含了，说明违反了唯一性索引，此时只要给长链再加上我们上文说的自定义字段「DUPLICATE」,重新 hash 再插入即可，看起来在违反唯一性索引的情况下是多执行了步骤，但我们要知道 MurmurHash 发生冲突的概率是非常低的，基本上不太可能发生，所以这种方案是可以接受的。

当然如果在数据量很大的情况下，冲突的概率会增大，此时我们可以加布隆过滤器来进行优化。
用所有生成的短网址构建布隆过滤器，当一个新的长链生成短链后，先将此短链在布隆过滤器中进行查找，如果不存在，说明 db 里不存在此短网址，可以插入！

2 自增序列算法

我们可以维护一个 ID 自增生成器，比如 1，2，3 这样的整数递增 ID，当收到一个长链转短链的请求时，ID 生成器为其分配一个 ID，再将其转化为 62 进制，拼接到短链域名后面就得到了最终的短网址

主要有以下四种获取 id 的方法

• 类UUID

简单地说就是用 UUID uuid = UUID.randomUUID(); 这种方式生成的 UUID，UUID(Universally Unique Identifier)全局唯一标识符, 是指在一台机器上生成的数字，它保证对在同一时空中的所有机器都是唯一的，但这种方式生成的 id 比较长，且无序，在插入 db 时可能会频繁导致页分裂，影响插入性能。

• Redis

用 Redis 是个不错的选择，性能好，单机可支撑 10 w+ 请求，足以应付大部分的业务场景，并且可以设置多台机器。不过用 Redis 这种方案，需要考虑持久化（短链 ID 总不能一样吧），灾备，成本有点高。

• Snowflake

用 Snowflake 也是个不错的选择，不过 Snowflake 依赖于系统时钟的一致性。如果某台机器的系统时钟回拨，有可能造成 ID 冲突，或者 ID 乱序。

• Mysql 自增主键

巨人的肩膀

高性能短链设计