[系统设计] TinyUrl

2018-03-22 本文已影响0人虫虫怪

系统设计SNAKE原则

Scenario: case/interface 情景，case，functional
Necessary：constrain/hypothesis 条件限制，非功能性的，性能要求，scalability, performance
Application: service/algorithm, 具体实现，算法，架构，逻辑
Kilobit: data
Evolve：simple version(单机版), 多用户—>cluster

Scenario 应用场景

应用场景有两个：将长的URL变短并存储；查找短的URL还原。抽象一下就是两个接口：
1.短到长 long_url lookup(short_url)
2.长到短 short_url insert(long_url)

Necessary

RPS Required?
读写的RPS一般要分开来计算
给出一些假设（assumption）
Requirement：日活用户数DAU：1M
Insert操作：

1,000,000 * 1% (function usage) * 10 (function frequency) = 100,000
RPS：100,000 / 86400 = 1.2
Lookup操作：
1,000,000 * 100% (function usage) * 3 (function frequency) = 100,000
RPS：3,000,000 / 86400 = 35
峰值估算（Peak estimation）
假设峰值为平均的5倍
插入峰值RPS = 6
查找峰值RPS = 175

Application - Architecture

HashTable/HashMap 传统hash

如果使用CRC32哈希算法，最多能支持的 URL数量为：2^32 = 4,294,967,296 约为4 billion
但实际上存到77,000的时候就有50%的概率遇到哈希冲突; 到110,000个时，冲突的概率为75%（birthday paradox）
解决哈希冲突，可以用 url + timestamp 作哈希，冲突的话再继续重试（改变timestamp）

使用自增ID

考虑到存入数据库并且多机器，则容量不限
不会出现collision
Url的长度：如果用十进制（Base10）,则长度 = log10(Url的数量)；用Base62，长度为log62(Url的数量),每一位用a-z, A-Z, 0-9表示

RPS per machine?
一般一台机器处理1000RPS

Kilobyte

Storage Required?
Decision process:
How many simultaneous users to support?

存储对于这种系统不是问题，netflix这种才有存储上的问题
第一步：select 选存储结构 -> 内存 or 文件系统 or 数据库 -> SQL or NoSQL?
第二步：schema 细化数据表

选存储结构 SQL vs NoSQL?

1.是否需要支持Transaction?
NoSQL不支持Transaction.
2.是否需要丰富的SQL Query?
NoSQL的SQL Query丰富度不如SQL，不过目前差距正在缩小.
3.是否追求效率(想偷懒)?
大多数Web Framework与SQL数据库兼容得很好(自带ORM)，意味着可以少些很多代码.
4.是否需要AUTO_INCREMENT ID?
NoSQL做不到1,2,3,4,5...NoSQL只能做到一个全局unique的Object_id.
5.对QPS要求高不高？
NoSQL性能高，比如Memcached的qps可以到million级别，MondoDB可以到10k级别，MySQL只能在K这个级别.
6.对Scalability的要求有多高？
SQL需要程序员自己写代码来scale; NoSQL这些都是自带的(sharding,replica).
综上：
1.transaction? 不需要 -> nosql
2.sql query? 不需要 -> nosql
3.是否追求效率？本来也没多少代码 -> nosql
4.对qps要求高？读2k，写200，真心不高 -> sql
5.对scalability要求高？存储和QPS要求都不高，单机就可以了 -> sql
6.要auto_increment_id? 我们的算法要！ -> sql

Envolve

如何优化响应时间？
如何将请求分发到不同的机器？
如何存储数据？Replication？Sharding？
如何保证数据一致性？

如何提高相应速度

提高web server和数据库之间的响应速度
读:利用Memcached提高响应速度,get的时候先去cache找，没有就从数据库里找；可以把90%的读请求都引流到cache上

提高web server和用户浏览器之间的响应速度（利用地理位置信息提速）
不同地区，使用不同的Web服务器和缓存服务器，所有地区share一个db，用于缓存没hit的情况
通过动态DNS解析可以把不同地区的用户match到最近的Web服务器

假如一台MySQL 存不下/忙不过来怎么办？

面临问题：
Cache资源不够
写操作越来越多
越来越多的cache miss率
怎么做：

拆数据库

拆数据库有两种，一种是把不同的表放到不同的机器(vertical sharding)，另一种是把数据散列到不同的机器(horizontal)。 最好用的是horizontal sharding。
当前的表结构是:(id, long_url)，既需要用id查long_url，也需要用long_url查id，如何分，把哪列作为sharding key呢？
一个简单可行的办法是，按id取模sharding，因为读(短到长)的需求是主要的；写的时候就广播给所有机器，由于机器不会太多，也是可行的。

ID设计

此时一个新的问题来了，n台机器如何共享一个全局自增id?
两个办法：开一台新的机器专门维护这个全局自增id，或者用zookeeper。都不好。所以我们不用全局自增id。

业内的做法是，把sharding key作为第一位直接放到short_url里。这样就不需要全局自增id,每台机器自增就好了。
用consistent hashing将环分为62份(这个无所谓，因为预估机器不会超过这个数目，也可以设成360或者别的数，每次新加一个机器可以把区间最大的分一半)每个机器在环上负责一段区间。

具体做法：

新来一个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减半 -> 把一半放到新增机器上

思考

1.Mysql的scale如何实现？

参考文章：

这篇写的很详细：
https://segmentfault.com/a/1190000006140476

扩展资料

Hash 方法比较
sharding key设计？
zookeeper介绍？全局自增id
一致性哈希：如何扩容