System Design
  • Introduction
  • Design Twitter
  • Design Tiny Url
  • Design Instagram
  • Consistent Hashing
  • NOSQL
    • Dynamo
    • Big Table
  • 在浏览器输入URL
  • RESTful API Design
  • 索引
    • Hash Indexes --- Bitcask
    • B-tree
    • LSM
  • Design Instagram
  • Design KV Store
  • Design Message System
  • Design Localization System
  • Design RSS Reader
  • Design Ticket Master
Powered by GitBook
On this page
  • Design Tiny Url
  • 1.Scenario
  • 2.Service
  • 3.Storage
  • 4.Scale
  • 5. Others
  • 6.References

Was this helpful?

Design Tiny Url

Design Tiny Url

1.Scenario

(1) 确认QPS

a. 首先确定DAU(Daily Active User), 假设有100M

b.估算产生一条Tiny Url的QPS

  • 假设每个客户每天发一条tiny url

  • 平均write QPS为 100M * 0.1 / (60 * 60 * 24) 约等于100

  • 峰期write QPS为 2 * 100

c.估算读一天Tiny Url的QPS

  • 假设每个客户每天点一条tiny url

  • 平均read QPS为 100M * 1 / (60 * 60 * 24)约等于 1k

  • 峰期read QPS为 2k

(2) 确认storage

假设每天url大小为100 byte，每天产生的URL的大小为100M * 0.1 * 100 = 1GB. 1TB可以存3年 （3年大概有1000天）

2.Service

(1) 只有一个Urlservice:

a. Long url to short url

b. short url to long url

(2) 算法

a. 利用hash function, 但这种方法很难设计一个没有Collision的hash function

b. 随机生成Short Url并利用数据库去重。这种方法实现简单，但生成短网址的速度会随着短网址越来越多而变慢

c. Base62 进制转换

  • 一般tiny url的长度为5-7位，而每位都有【a-zA-Z0-9】62种可能性，对于长度为6的url, 可以生成62^6 = 570亿

  • 这个方法效率很高，但缺点是依赖于Global ID, 而在分布式的环境下，生成Unique Global ID也是个难题

3.Storage

a. 由于我们利用Global ID来作为每条Tiny Url， Sql自带的auto-increment sequential非常适合

b. schema

只需要一个table，table包含两列，一列是自增id作为key，另一列是long url. 同时对long url建立索引，这样通过long url也可以查找到id

4.Scale

(1) 提高响应速度

a. 提高服务器和数据库之间的响应速度

  • 根据之前的分析，tiny url是个读多写少的应用，所以可以在server和数据库之间增加cache，提高读的速度

b. 提高服务器和用户浏览器之间的响应速度

  • 不同地区会用不同的服务器

  • 通过DNS解析不同地区的用户到不同的服务器

(2) Sharding

a. 面临的问题

  • 写的操作越来越多

  • 越来越多的写请求无法通过cache满足，cache miss rate越来越多

b. 解决方法

  • 还数据库的方法主要就两种，一种是Vertical Sharding, 即将多个表方法多个不同机器，另一种是Horizontal Sharding, 将数据散列到不同的机器上。Tiny Url适合用Horizontal Sharding.

  • Horizontal Sharding的具体做法是：以ID作为sharding key, 按照ID % N (N为机器的个数)作Sharding， 读的时候(short url to long)就将short url变成ID，然后根据ID到相应的机器找long url。写的时候 (long url to short)就广播给N台机器，查询是否存在对应的short url，如果没有则写入数据库里

(3) 全局自增ID

a. 问题：如何让n台机器共享全局ID

b. 一种做法是利用一台机器专门做自增ID服务，但容易有Single Point Failure, 可能需要多台机器避免这个问题，另一种方法是用zookeeper, 但不管哪种方法，用全局自增ID并不是一个好的解决方法

c. 一个更好的办法是，在short key前置一位，比如对于6位的short key “abcdef”，变为"0abcdef"，这样就不需要依赖全局自增ID，只需要机器内部自增就好，用consistent hashing将环分为62份(这个无所谓，因为预估机器不会超过这个数目，也可以设成360或者别的数，每次新加一个机器可以把区间最大的分一半)每个机器在环上负责一段区间。

d. 具体过程：

  • 新来一个long_url ->hash(long_url)%62 ->把long_url放到hash value对应的机器里 ->在这台机器上生成short_url ->返回short_url

  • 来一个short_url请求 ->提取short_url的第一位得到sharding key ->到sharding key对应的机器里找 ->返回long_url

  • 新增一台机器 ->找原来机器里负责range(0-61)最大的机器 ->将其range减半 ->把一半放到新增机器上

(4) Multi-region进一步优化

中国的db放到中国，美国的db放到美国。

用地域信息作为sharding key，比如中国网站都放到0开头的，美国网站都放在1开头的。

5. Others

(1) 自定义的短链接

单独建一张表CustomUrl Table，存custom_url <-->long_url 当查询时，先从custom表里查，再从url表里查。注意，千万不要在url表里插一列custom，这样这列大部分的值为空。

(2) 分布式Unique ID生成方法

服务化框架－分布式Unique ID的生成方法一览

6.References

Instagram 维护分布式全局id的方法

Tiny Url系统设计总结

PreviousDesign TwitterNextDesign Instagram

Last updated 5 years ago

Was this helpful?