System requirements

Functional:

1. 输入一个长url输出一个短url
2. 输入一个短url转到长url页面

Non-Functional:

1. 系统的可伸缩性，弹性要好， 可以支持后续更多的日活
2. 系统的可靠性要高

Capacity estimation

1. DAU: 5000
2. 生成短链 tps: 5000*5 / 10^5 = 0.25 /s ，
3. 访问短链的qps: 5000*20 / 10^5 = 1/s。
4. 存储空间占用， 假设长链最大200个字符， 短链最大20个字符吧。

API design

1. 创建短链
2. api: POST /shorten
3. data: {long: "http://xxxx/longurl" }
4. resp: {code: ok, message: "", data：{short: "http://xxx/short"}}
5. 访问短链
6. api: GET /long?shorten="http://xxxx/short"
7. response: http状态码返回304， location 填写对应的长链

Database design

数据库表设计如下

High-level design

从上到下分别是以下组件

1. 客户端
2. 反向代理
3. 负载均衡
4. shorten服务
5. id service: 作用是用于生成递增的唯一id
6. 缓存
7. 数据库

Request flows

1. 创建短链
2. 客户端发送post /shorten请求
3. 请求通过反向代理和负载均衡到达 short servcie服务
4. short servcie 先判断短链是否存在，若存在则直接返回。
5. 如果不存在，则通过id service获取一个唯一的自增id
6. 通过hash算法将id转换为短链
7. 存储短链和长链的映射到数据库
8. 访问短链
9. 客户端发送Get /long请求
10. 请求通过反向代理和负载均衡到达short service服务
11. short service服务先访问缓存，缓存有则直接返回
12. 缓存没有访问数据库， 并更新缓存

Detailed component design

1. hash算法：hash算法的目的是将一个长链映射成一个短链， 假设我们限制短链最大长度为10个字符， 每个字符可以是0-9 a-z A 用这些字符可以表达64进制。 10个字符一共可以支持62^10个短链，完全够用。 这样hash函数的作用就是将id 转换成64进制的数。

Trade offs/Tech choices

1. 在高级设计视图中，有连个数据库， 其中id使用的数据库我们可以选用mysql， 主要是为了使用mysql的自增id，同时id service没有状态可以随意扩容，提高了可用性和可靠性，为了提高可靠性myql 我们用主从的方式。 short service使用的数据库我们选用mongodb, 一是因为数据之间关联性不强所以选用nosql, 另一个是mongo天然支持分布式，扩容比较方便
2. 缓存选用redis， 为了提高可靠性，redis部署为哨兵模式。

Failure scenarios/bottlenecks

1. 生成id的mysql随着流量的增大有可能成为瓶颈， 为了生成自增的id, myql必须是单点，至多是主从，不论是单点还是主从，写tps有限

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?