短域名服务设计

Jul 1, 2021

参考这里

因为短信、微博、二维码等场景无法存储太长的网址，要求设计一个类似新浪微博那种输入完全 URL 可以转换为短 URL 的短域名服务，可以为全国网址服务，该如何设计？

不可行方案

  1. 没有算法可以将长域名转换为短域名，再将短域名还原回长域名（单纯算法转换不可行）
  2. 没有算法可以将长域名转换为短域名并且不碰撞（MD5、Hash）（算法转换 + 数据库查询不可行）

结论：算法方案都不可行

ps：其实第二点是可以解决的，就是方案比较复杂，比如：

  1. 使用 Google 出品的 MurmurHash 算法，该算法性能高、哈希冲突概率低
  2. 算出短域名后在布隆过滤器中进行查找，如果不存在则可用，如果存在则到数据库进行判断是否确实存在
  3. 如果确认短域名存在且长域名不同，则在长域名后拼接一个自定义串，再重新Hash，即返回第一步
  4. 根据短域名取长域名时需要判断是否有自定义串，如果有，则需要移除

ps：布隆过滤器是一种非常省内存的数据结构，长度为 10 亿的布隆过滤器，只需要 125 M 的内存空间

可行方案

给每一个长域名一个自增ID，然后存入数据库即可，自增ID即短域名
自增ID在使用时转换为62进制（数字 + 小写字母 + 大写字母）以减少长度
6 位 62 进制数可表示 568 亿的数，应付长链转换绰绰有余（568 0023 5583）

比如：ID自增至10000，转换为62进制为：2Bi

其他问题

  1. 高并发下如何保证自增

    可以用多个节点自增，然后用节点数做步长。
    比如可以实现1000个逻辑发号器，分别发尾号为0到999的号。每发一个号，每个发号器加1000，而不是加1

  2. 跳转用301还是302

    301是永久重定向，302是临时重定向
    短域名一经生成就不会变化，所以用301是符合http语义的，同时减少对服务器的压力。但使用301就无法统计到短域名被点击的次数了。
    如果点击次数对业务的大数据分析很重要就选择302。

  3. 如何实现同一个长域名多次转换还是同一个短域名

    自增方案可以实现长域名、短域名一一对应，但是需要每次去查询数据库（性能较差）或者缓存全部的长域名、短域名（比较浪费空间）
    可以使用折中方案：用K-V存储最近一段时间，比如一个小时，的长短域名对应关系，然后采用LRU算法进行淘汰。
    这样整个流程为：先在最近的K-V存储中查询长域名是否有对应的短域名，有则直接返回并将过期时间延长；无则生成短域名、存入K-V存储并设置过期时间。
    如果一个长域名被频繁使用，那么它会一直在这个K-V存储中，总能返回当初生成的那个短域名，不会出现重复的问题。如果长域名使用并不频繁，那么LRU机制会淘汰掉它。
    当然，折中方案不能保证同一个长域名一定能转出同一个短域名，但是影响不大