参考资料链接:系统设计题精选
书籍豆瓣链接:
开始学习时间:
预计完成时间:
实际完成时间:
1. 分布式ID生成器
分布式ID生成三大核心需求:
- 全局唯一:ID往往会作为数据库主键,需要保证全局唯一
- 按照时间粗略有序:查询的时候往往有按时间分页或者排序需求,普通索引访问比聚簇索引慢,如果能让ID按时间粗略有序,可以省去时间字段
- 尽可能短:存储性能
1.1 基于数据库实现
1.1.1 MySQL自增ID
- innodb_autoinc_lock_mode=0
传统的auto_increment设置中,每次访问auto-increment计数器的时候, INNODB都会加上一个名为AUTO-INC锁直到该语句结束(注意锁只持有到语句结束,不是事务结束).AUTO-INC锁是一个特殊的表级别的锁。这种模式下所有针对auto_increment列的插入操作都会加AUTO-INC锁,分配的值也是一个个分配,是连续的,正常情况下也不会有间隙(当然如果事务rollback了这个auto_increment值就会浪费掉,从而造成间隙)
- innodb_autoinc_lock_mode=1
bulk insert才会使用AUTO-INC缩,simple insert使用轻量级互斥锁
- innodb_autoinc_lock_mode=2
任何类型的insert都不使用AUTO-INC锁
1.1.2 多台MySQL协同
假设用8台MySQL服务器协同工作,第一台MySQL初始值是1,每次自增8,第二台MySQL初始值是2,每次自增8,依次类推。前面用一个 round-robin load balancer 挡着,每来一个请求,由 round-robin balancer 随机地将请求发给8台MySQL中的任意一个,然后返回一个ID
这个方法跟单台数据库比,缺点是ID是不是严格递增的,只是粗略递增的
1.2 基于分布式集群协调器生成
一般的,主流协调器有两类:
- 以强一致性为目标的:ZooKeeper为代表
- 以最终一致性为目标的:Consul为代表
1.3 划分命名空间
1.3.1 MongoDB ObjectId
用过MongoDB的人会知道,MongoDB会自动给每一条数据赋予一个唯一的ObjectId,保证不会重复,这是怎么做到的呢?实际上它用的是一种UUID算法,生成的ObjectId占12个字节
- 4个字节表示的Unix timestamp
- 3个字节表示的机器的ID
- 2个字节表示的进程ID
- 3个字节表示的计数器
UUID是一类算法的统称,UUID的优点是每台机器可以独立产生ID,理论上保证不会重复,所以天然是分布式的,缺点是生成的ID太长,不仅占用内存,而且索引查询效率低
1.3.2 Twitter Snowflake
雪花算法生成64位的二进制正整数,然后转换成10进制的数。64位二进制数由如下部分组成
- 41位时间戳:41位时间戳不是存储当前时间的时间戳,而是存储时间截的差值
- 10位机器标识码:可以部署在1024个节点,这10位可以由 5位机房ID + 5位机器ID 组成
- 12位序列:毫秒内的计数,12位的计数顺序号支持每个节点每毫秒(同一机器,同一时间截)产生4096个ID序号
2. 短网址系统(TinyURL)
2.1 短链设计
当前互联网网页总数介于32位和64位,短网址采用09AZa~z等62个字符进行编码
长网址携带状态信息生成短网址,所以一个长网址对应多个短网址
使用1中的分布式ID生成器生成,使用分布式kv数据库存储
2.2 短链跳转的基本原理
通过浏览器请求抓包之后可以看到,短链接的请求返回状态码 302 与 Location 字段,这个 Location 的值就是对应的长链接。
1 | 301 Moved Permanently 永久移动,响应默认会被浏览器缓存。当下次再请求的时候,浏览器不会向服务器发送请求,而是直接从缓存中获取需要重定向的新地址 |
所以为了统计短链的点击次数,使用302而不是301
2.3 预防攻击
别有用心的黑客,短时间内向TinyURL服务器发送大量的请求,会迅速耗光ID
用一台Redis作为缓存服务器,存储的不是 ID->长网址,而是 长网址->ID,仅存储一天以内的数据,用LRU机制进行淘汰。如果黑客大量发同一个长网址过来,直接从缓存服务器里返回短网址即可,他就无法耗光我们的ID了
3. 信息流
4. 定时任务调度器
见「Linux高性能服务器编程」
4.1 时间堆
使用最小堆,将堆顶的超时值作为心博间隔
4.2 时间轮
一个滴答的时间称为时间轮的槽间隔,新任务根据时间间隔被路由到对应的槽中
5. API限速
给定一个公共API,限制每个用户每秒只能调用1000次,如何实现?
- 滑动窗口:
- 令牌桶:按照固定的速率往桶里新增令牌,流入请求速度固定
- 漏斗:流出请求采用固定速率,从而平滑突发流入速率
简单限流
使用redis的zset结构作为滑动窗口,value是时间戳,移除时间窗口前的记录,并计算当前时间窗口的记录
缺点是需要记录窗口内所有的行为记录
漏斗限流
redis-cell
6. 线程安全的HashMap
开放地址法解决冲突,锁分离按bucket加锁解决全局锁的性能问题,CAS替代锁优化性能,链表太长采用红黑树优化查询性能
7. 最近1h访问频率最高的10个IP
内存中创建3600个HashMap,每个HashMap对应10w个pair,小于2的12次方乘以2的17次方乘以2的3次方=4G
维护一个大跟堆,存放频率最大的10个IP,每插入一个新请求都要遍历3600个HashMap,统计次数并更新
需要一个后台常驻线程,每过1s,清楚旧的HashMap
8. 负载均衡
9. key-value存储引擎
内存随机写甚至比硬盘的顺序读还要慢,因此好的KV存储引擎,都在尽量避免更新操作,把更新和删除操作转化为顺序写操作。LevelDB采用了一种SSTable的数据结构来达到这个目的
请求技术器
维护大量的长链接
10. 网络爬虫
11. PageRank
12. 搜索引擎
13. 大数据
13.1. 数据流采样
13.2. 频率估价
PV计数:redis incrby
13.3. 基数估计
UV计数:即基数估计
13.3.1 bitmap
redis支持