Design Tiny URL

Scenario - 分析功能，需求，QPS, 存储容量

  1. DAU 100M
  2. 产生Tiny URL QPS = 100M * 0.1 (每天发0.1) / 86400 ~ 100, Peak 200
  3. 点击Tiny URL QPS = 100M * 1 / 86400 ~ 1k, Peak 2k
  4. 新的URL需要的存储
    • 100M * 0.1 ~ 10M条
    • 一条长度100，约1G，所以1T的硬盘可以用3年

Service - 画图找可行解

  • URL sercie
    • encode
    • decode

Storage - 画图找可行解

  • SQL vs NoSQL
    • 是否需要支持transaction，（两个操作同时成功或者失败）
    • 是否需要丰富的sql query或者secondary index
    • 兼容性
    • 是否需要sequential id （SQL是increment的，NoSQL则是随机的）
    • QPS的要求
    • Scalability的要求有多高

算法

  1. Hashing Function （不可行，难以确保不冲突）
  2. 随机生成ShortURL+ 数据库去重 （常见，confirmation code）
    • 实现简单
    • 生成短网址的速度随着shortURL越来越多变得越来越慢
  3. 进制转换Base62
    • 将6位的short url看做一个62进制数，这样每个short url对应一个整数，该整数对应数据库表的primary key —— sequential id
    • 效率高，但是依赖于全局自增的id,这样shortKey不一定需要存在表单里，可以通过id推算出来
    • confirmation就不适用，因为自增的规律可以猜到
    • 记得对shortKey和longUrl都要建立index

Scale - 研究可能遇到的问题，优化系统

  • reduce response time (read or write)

    • Cache，保存两类数据
      • long to short
      • short to long
    • 利用地理位置信息提速
      • 优化服务器访问速度。不同地区，用不同的web server，利用DNS解析不同的地区用户到对应的服务器
      • 优化数据访问速度。实用Centralized MySQL + Distributed Memcached. 即一个MySQL配多个Memcached跨地区分部。

  • How to Scale if the data is too much

    • Horizontal Sharding
    • Sharding Key?
      • Long Url, how to query id? 查询shortkey的时候，必须广播，所以无法解决降低QPS的问题
      • id, how to query Long URL?
        • 按照ID % N,来分配存储，确保分配均匀
        • query long的时候，仍然需要广播，但是由于分配均匀了，效果并不会太差。如果不存在的话，获得下一个自增的id，存入对应的数据库。同时，query long是写请求，一般比读少的多
      • 在shortkey前面增加一个前置位，作为sharding key（仅仅作为sharding key，不增加位数）。对于long url取hash(long) % 62
      • 还有一个办法，用前面random的办法，但是不用填检查是否已经在db中了。因为可以允许long url对应多个不同的short url。这个时候，只需利用cache来尽量减少重复
    • Multi Region进一步优化
      • 根据用户的习惯，中国用户访问时候，一般都是访问中国网站，所以可以按照网站的地域信息进行sharding。只需要用一张表记录常用的中国网站即可。
  • How to support custom tiny url
    • 不能直接加一个col，因为这个col可能经常为空
    • 另外创建一个table，每次查询时，优先查找customtable

results matching ""

    No results matching ""