# 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的生成方法一览](http://calvin1978.blogcn.com/articles/uuid.html)

## 6.References

[Instagram 维护分布式全局id的方法](https://engineering.instagram.com/sharding-ids-at-instagram-1cf5a71e5a5c)

[Tiny Url系统设计总结](https://segmentfault.com/a/1190000006140476#articleHeader8)
