设计一个short URL service

短网址系统
非常高频的系统设计面试题

功能上很简单 可浅可深

两个问题

1. Long URL 和short URL要一一对应吗？？ 可以是一对多，或者一对一
2. Short URL长时间没人用需要释放吗 ？？ 不需要

分析

日活用户一亿 100M * 0.1 / 86400 ~ 100
peak 200
Read 2k
100M * 0.1 ~ 10M

encode(long_url)
decode(short_url)

301永久跳转, 302临时跳转

Storage

Select Schema
不需要支持transaction, 不需要丰富的SQL Query
对Scaling要求有多高? SQL 可以搞定
SequentialID 自增ID， 每次插入需要加锁

办法

思路： 使用Hash很难没有冲突。
随机生成： 可能会慢。while true 不停的搞。
进制转换：需要搞一个Sequential ID. 先去一台机器取id.

加速

如果找一个long url有没有建过short key, 就需要对long URL做index
大多数No SQL不支持二级索引

Scale提高响应速度：
缓存里面需要存两类数据； (缓存一般是读多写少)
long to short （生成short url时需要)
short to long

再提速
利用地理位置提速

Sharding

如果需要sharding, 用什么东西做sharding key
如果不需要long to short 一对一，则直接用short url做为sharding key
如果需要long to short, 则可以把long url的hash 值放到short url里面 （比如 放第一位)
根据用户习惯sharding