设计一个短网址系统(将 长网址 转换成 短网址,方便用户使用url)

4S分析法

  1. 提问:分析场景,功能,QPS,存储空间 -- Scenario
  2. 画图:根据分析结果设计“可行解” -- Service + Storage
  3. 进化:研究可能遇到的问题,优化系统 -- Scale

场景分析

  1. 把长网址 转换为 短网址
  2. 把短网址 还原为 长网址(给用户,用户通过短网址),并跳转

# 场景分析

  1. 询问日活用户量

    微博约100M

  2. 推算产生一条Tiny Url的QPS

    假定每个用户每天发0.1条带Url的微博

    Average Write QPS = 100 M * 0.1 / 86400 -> 115 QPS 峰值Peak Wirte QPS = 125 * (2 ~ 5) -> 200 ~ 500(考虑到明星结婚之类的新闻,峰值可能更高)

  3. 推算点击一条Tiny Url的QPS

    假设平均每个用户每天点击1个Tiny Url Avearge Read QPS = 100 M * 1 / 86400 ~= 1K Peak Read QPS ~= 2K ~ 5K

  4. 推算存储空间

    每天产生的url数量 100 M * 0.1 ~= 10M条 每一条url假设100bytes, 100 bytes * 10M条 = 1000 M bytes = 1 G 1T的硬盘可以用3年

# 服务分析

服务比较简单,只需要设计一个UrlService Application

函数设计

  • UrlService.encode(long_url)
  • UrlService.decode(short_url)

API设计

GET /${short_url}

if (not existed) return 404
return a Http redirect response

POST /data/shorten/

Data = {url: http://xxxxlonglong..}
return shorten url

# 算法设计

encode和decode

算法1:使用哈希函数(不可行)

比如取Long Url的MD5的后6位 优点:快 缺点:很难设计一个没有冲突的哈希算法

算法2:随机生成+数据库比较去重

随机生成一个6位的short url,如果没有被用过,就绑定到Long Url

优点: 实现简单 缺点:生成短网址的速度会随着短网址越来越多变得越来越慢

算法3:进制转换

short url的组成字符包括0-9,a-z, A-Z,共62个,把短网址字符串看做一个62进制的数字 每次发起生成请求,进制数+1

优点:效率高 缺点:依赖于全局自增的ID

# 存储

是否需要支持Transaction? 不需要 nosql +1

是否需要丰富的SQLQuery? 不需要 nosql +1

代码量,是否想偷懒?

大多数Web Framework和SQL数据库兼容得很好 用sql比用NOSQL少写很多代码(nodejs配合nosql代码量也很少)

对QPS的要求有多高? NOSQL的QPS更高

对Scalability的要求多高?

SQL 需要码农自己写代码来Scale

TODO DB如何做Sharding, Replica

NOSQL自动Sharding, Replica

是否需要Sequential ID?自增ID ? -- 取决于算法是什么

# Scale 扩展&优化

如何加快响应速度?

优化服务器访问速度:不同地区使用不同的web服务器,通过DNS解析不同地区的用户到不同的服务器 优化数据访问速度:中心化的Mysql+Distributed Membcached;不同地区做缓存,共享同一个数据库

数据是否需要长久保存short Url?比如一年以上没有访问的,是否可以记录最近访问时间,定期删除

数据库扩展:写操作忙不过来,比如有的人用脚本写

表结构足够简单;不能垂直扩展,只能水平扩展;比如三台db; 读操作可以用short mod 3 得到在哪台机器,直接去读 写操作 long -> short 可以是一对多的关系,每请求一次写,生成一条数据;

# 一致性哈希算法(Consistent Hashing)

水平扩展(Horizontal Sharding)的终极武器

  • 水平切分(Horizontal Sharding):同一张表,比如交易等,划分在不同的机器上
  • 垂直切分(vertical sharding): 不同的表放在不同的机器上

不一致性哈希的缺点:

当取模的底数发生改变时,大部分数据 会发生迁移

简单的一致性哈希算法:

  • 取模的底数取一个很大的数,比如360
  • 将360分配给n台机器,每台机器负责一段区间
  • 区间分配信息记录在一张表,存在web server上
  • 每次增删改查数据,先查询区间分配表,再操作
  • 新增机器时,查询区间和最大的两台机器,分成三台

缺陷:

  1. 数据分布不均匀;
  2. 迁移压力大;新机器的数据只能从两台老机器上获取,导致两台老机器负载压力大

更实用的一致性哈希

  • 将整个hash区间看做环,环的大小为2^64-1
  • 将机器和数据都看做环上的点
  • 引入虚节点的概念