TinyURL

  • generate tinyURL: long -> short

  • click tinyURL: short -> long

Assumption: Weibo 100M DAU

Scenario

  • QPS (long -> short) = 100M * 0.1 / 100k = 100

  • Peak QPS = 100 * 2 = 200

  • QPS (short -> long) = 100M * 1 / 100k = 1k

  • Peak QPS = 1k * 2 = 2k

==> 2k QPS, 一台SSD支持 的MySQL完全可以搞定

Storage
  • 100M * 0.1 * 100 byte = 1000 MB = 1G / day

==> 1T SSD is enough for 3 years

Service

  • urlService

    • encode(long_url)
    • decode(short_url)

    • GET /<short_url>: return a Http redirect response

    • POST /data/shorten/: Return short url

Scale
  • cache

  • 利用地理位置信息提速

  • 优化服务器访问速度
    •不同的地区，使用不同的Web服务器
    •通过DNS解析不同地区的用户到不同的Web服务器

  • 优化数据访问速度
    •使用Centralized MySQL+Distributed Memcached
    •一个MySQL配多个Memcached，Memcached跨地区分布

  • add DB server

    • design sharding key

    • approach 1: 用Long URL做shard key
      •查询的时候，只能广播给N台数据库查询•并不解决降低每台机器QPS的问题

    • approach 2: 用ID做shard key
      •按照ID % N(N为数据服务器个数)，来分配存储

      • Short url to long url

      • 将short url转换为ID

      • 根据ID找到数据库

      • 在该数据库中查询到long url

      • Long url to short url

      • 先查询:广播给N台数据库，查询是否存在

      • 看起来有点耗，不过也是可行的，因为数据库服务器不会太多

      • 再插入:如果不存在的话，获得下一个自增ID的值，插入对应数据库

    • approach 3: shard key = hash(long_url) % 62

      • short_url = shard key + short key

      • 这样我们就可以同时通过short_url和long_url得到Sharding Key

      • 无需广播 无论是short2long还是long2short 都可以直接找到数据所在服务器

    • approach 4: 按照网站的地域信息进行Sharding

  • •提高Web服务器与数据服务器之间的访问效率: cache. 利用缓存提高读请求的效率
    •提高用户与服务器之间的访问效率: dedicated web server for each region. 解决了中国用户访问美国服务器慢的问题
    •提高QPS，将数据分配到多台服务器: sharding DB server. 解决流量继续增大一台数据库服务器无法满足的问题
    •提高中国的Web服务器与美国的数据库服务器通信较慢的问题: design sharding key. 按照网站地域信息进行Sharding

  • customize shorten

    • 新建一张表存储自定义URL: CustomURLTable

    • 查询长链接

      • 先查询CustomURLTable

      • 再查询URLTable

    • 根据长链接 创建普通短链接

      • 先查询CustomURLTable是否存在

      • 再在URLTable中查询和插入

    • 根据长链接 创新自定义短链接

      • 查询是否已经在URLTable中存在

      • 再在CustomURLTable中查询和插入

Algo
  • shortUrl = MD5 hash(longUrl)
    • x: hard to handle conflict
  • shortUrl = rand(), nextRand() if exist already
  • base62, (0-9, a-z, A-Z)
    • id <-> 6 digit short url, convert short url to database id
    • 5 digit = 62^5 = 1B
    • 6 digit = 62 ^ 6 = 57B

results matching ""

    No results matching ""