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生成方法
6.References
Last updated
Was this helpful?