参考资料链接：系统设计题精选
书籍豆瓣链接：
开始学习时间：
预计完成时间：
实际完成时间：
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支持
