Scenario

  • 根据 long URL 生成一个 short URL
  • 根据 short URL 还原 Long URL 并且跳转
  • Long URL 和 short URL 必须是一一对应吗
  • Short URL 长时间没人用是不是要释放？
  • 日活用户？假设 100M
  • QPS
    • 假设每个用户每天发 0.1 条带 URL 的微博
      • Write QPS: 100M * 0.1 / 86400 ~ 100
      • Peak QPS: 100 * 3 ~ 300
    • 假设每个用户每天点击一个 URL
      • Read QPS: 100M * 1 / 86400 ~ 1000
      • Peak QPS: 1000 * 3 ~ 3000
  • 每天产生的新的 URL 所占的存储
    • 100M * 0.1 ~ 10M 条
    • 每条 URL 长度 100，共 1G
    • 1T 硬盘可以用三年

Service

  • URL Service
  • 函数: UrlService.encode(url), UrlService.decode(url)
  • 端口: GET /, POST /shorten/ data: {url: 'example'}

使用什么算法

  • hash function - 不可行，容易出现冲突
  • 随机生成 short URL + 数据库去重: 会越来越慢
    • 随机生成一个，如果数据库中没有，就绑定
  • 禁止转换 Base62: 效率高，但是依赖全局的自增 ID
    • 把 6 位的 short URL 看作一个 62 进制的数字 (0-9, a-z, A-Z)
    • 每个 short URL 对应一个整数
    • 每个整数表示 table 中的 primary key

Storage

  • No transaction
  • 没有复杂的 query

因此可以使用 NoSQL

Scale

  • 可以利用 cache 提速，比如使用 Memcached 存储 short url 和 long url 的对应关系
  • 可以在多地架设服务器提高速度，比如中国和美国各架设一台服务器