最近在读 Alex Xu 的《System Design Interview》 这本书，系统学习一下系统设计面试的相关问题。读完觉得有必要记录一些笔记，帮助自己”学而时习之”，于是记录在这里，不断更新中~

为了准备英文面试，我读的是英文版，这本书的中文版已经出版，豆瓣 8.3 分，叫做 《搞定系统设计：面试敲开大厂的门》 有兴趣也可以阅读。

第五章：一致性哈希

第六章：KV存储(键值对存储)

  • KV 存储，又叫 KV 数据库
  • Key 各不相同，可以是 字符串，也可以是 哈希值
  • Value 透明的对象
  • 设计：没有完美的设计，需要权衡以下问题
    • 读，写，内存使用
    • 一致性，可用性
  • 需要考虑的功能特性
    • 键值对大小
    • 存储大数据的能力
    • 高可用
    • 高扩展
    • 自动扩展
    • tunable consistency(可调的一致性)
    • 低延时

单机 KV 存储

  • 用 哈希表 实现就行，数据都放内存里
  • 遇到空间问题可以：
    • 数据压缩
    • 内存只存放热数据，其他的存磁盘里
  • 缺点：
    • 即使有了优化，仍然很容易遇到单机的空间上限，数据多了一定要上大数据

分布式 KV 存储

  • distributed key-value store 也叫 distributed hash table (分布式哈希表)
  • CAP 理论：
    • Consistency 一致性：同一时间，所有客户端，都返回同样的数据
    • Availability 可用性：不论连接到哪个节点，都有数据返回
    • Partition Tolerance 分区容忍性：系统在网络分区（即网络中断导致通信失败）的情况下仍然能够继续运行
  • CAP三个里最多同时满足两个，至少要牺牲一个
    • CA：因为网络故障在真实世界里不可避免，所以选 CA 而放弃 P 的情况是不可能存在的
    • CP：选一致性，放弃可用性。比如银行，对账户余额要求高，如果遇到问题，可以直接报错，不能返回脏数据
    • AP：选可用性，放弃一致性。为了保证高可用，遇到网络故障，数据同步中断，可能返回脏节点的脏数据，等网络恢复后会同步成功

系统组件

  • Data Partition 数据分片
    • 设计目标：
      • 数据能分布存储
      • 加减节点的时候，数据移动少
    • 使用 第五章 介绍的 一致性哈希 可以解决这个问题，好处
      • 自动扩容
      • 均匀（容量越大的节点，配置越多的虚拟节点）
  • Data Replication 数据复制
    • 为了高可用，必须吧数据复制到不同的节点
    • 一般是 哈希环 上顺时针往后的 N 个节点，如果有虚拟节点，适当跳过，选择不同的物理节点
    • 一般同一个数据中心的机器会同时发生 电力/网络/自然灾难 等故障，最好放到不同的数据中心，数据中心之间用高速网络连接
  • Consistency 一致性
    • 强弱一致性定长
      • N = 副本总数
      • Q = 写操作至少需要确认的节点个数
      • R = 读操作至少需要确认的节点个数
      • 如果 W + R > N， 就满足强一致性， 一般 N = 3, W = R = 2
      • 如果 R = 1， W = N 就是为快速读取设计的
      • 如果 W = 1， R = N 就是为快速写入设计的
    • 一致性模型
      • 强一致性：任何读写操作，都是最近数据，没有脏数据（不够高可用）
      • 弱一致性：不能保证
      • 最终一致性：给足够的时间同步数据，最终数据都是一致的（高可用的服务，一般用这种，比如 Dynamo Cassandra）
  • Inconsistency resolution 不一致性恢复
  • Handling failures 错误处理
  • System architecture diagram 系统架构图
  • Write path 读路径
  • Read path 写路径

词汇表

  • tradeoff 权衡
  • opaque 不透明的
  • sacrificing availability 牺牲可用性
  • unavoidable 不可避免的
  • immutable 不可变的
  • replica 复制
  • high

ChangeLog

  • 24-07-01 新建文档，部分发布：第六章：KV存储

附录，中文版目录（来源于豆瓣页面）

1 从0到100万用户的扩展 1
1.1 单服务器配置 1
1.2 数据库 3
1.2.1 使用何种数据库 4
1.3 纵向扩展 vs. 横向扩展 5
1.4 负载均衡器 5
1.5 数据库复制 7
1.6 缓存 10
1.6.1 缓存层 10
1.6.2 使用缓存时的注意事项 11
1.7 内容分发网络 12
1.7.1 使用CDN时的注意事项 14
1.8 无状态网络层 15
1.8.1 有状态架构 15
1.8.2 无状态架构 16
1.9 数据中心 18
1.10 消息队列 20
1.11 记录日志、收集指标与自动化 21
1.11.1 添加消息队列和各种工具 21
1.12 数据库扩展 23
1.12.1 纵向扩展 23
1.12.2 横向扩展 23
1.13 用户量达到甚至超过了100万 27
2 封底估算 28
2.1 2的幂 28
2.2 每个程序员都应该知道的操作耗时 29
2.3 可用性相关的数字 31
2.4 案例：估算推特的QPS和存储需求 31
2.5 小技巧 32
3 系统设计面试的框架 33
3.1 有效的系统设计面试的四个步骤 34
3.1.1 第一步：理解问题并确定设计的边界 34
3.1.2 第二步：提议高层级的设计并获得认同 36
3.1.3 第三步：设计继续深入 38
3.1.4 第四步：总结 41
3.2 面试中每一步的时间分配 43
4 设计限流器 44
4.1 第一步：理解问题并确定设计的边界 45
4.2 第二步：提议高层级的设计并获得认同 46
4.2.1 在哪里实现限流器 46
4.2.2 流量限制算法 48
4.2.3 高层级架构 56
4.3 第三步：设计继续深入 57
4.3.1 流量限制规则 57
4.3.2 超过流量的限制 58
4.3.3 详细设计 58
4.3.4 分布式系统中的限流器 59
4.3.5 性能优化 61
4.3.6 监控 62
4.4 第四步：总结 63
5 设计一致性哈希系统 64
5.1 重新哈希的问题 64
5.2 一致性哈希 66
5.2.1 哈希空间和哈希环 66
5.2.2 哈希服务器 67
5.2.3 哈希键 68
5.2.4 查找服务器 68
5.2.5 添加服务器 69
5.2.6 移除服务器 70
5.2.7 两个问题 71
5.2.8 虚拟节点 73
5.2.9 找到受影响的键 74
5.3 总结 76
6 设计键值存储系统 77
6.1 理解问题并确定设计的边界 78
6.2 单服务器的键值存储 78
6.3 分布式键值存储 79
6.3.1 CAP理论 79
6.3.2 系统组件 81
6.3.3 数据分区 82
6.3.4 数据复制 83
6.3.5 一致性 84
6.3.6 不一致性的解决方案：版本控制 86
6.3.7 处理故障 89
6.3.8 系统架构图 94
6.3.9 写路径 96
6.3.10 读路径 97
6.4 总结 98
7 设计分布式系统中的唯一ID生成器 100
7.1 第一步：理解问题并确定设计的边界 101
7.2 第二步：提议高层级的设计并获得认同 101
7.2.1 多主复制 102
7.2.2 UUID 102
7.2.3 工单服务器 103
7.2.4 推特的雪花系统 104
7.3 第三步：设计继续深入 105
7.4 第四步：总结 106
8 设计URL缩短器 108
8.1 第一步：理解问题并确定设计的边界 108
8.1.1 封底估算 109
8.2 第二步：提出高层级的设计并获得认同 109
8.2.1 API端点 109
8.2.2 URL重定向 110
8.2.3 缩短URL 112
8.3 第三步：设计继续深入 112
8.3.1 数据模型 112
8.3.2 哈希函数 113
8.3.3 深入探讨URL缩短流程 116
8.3.4 深入探讨URL重定向流程 117
8.4 第四步：总结 118
9 设计网络爬虫 119
9.1 第一步：理解问题并确定设计的边界 121
9.2 第二步：提议高层级的设计并获得认同 122
9.3 第三步：设计继续深入 127
9.3.1 DFS vs. BFS 128
9.3.2 URL前线 129
9.3.3 HTML下载器 134
9.3.4 健壮性 135
9.3.5 可扩展性 136
9.3.6 检测和避免有问题的内容 137
9.4 第四步：总结 137
10 设计通知系统 139
10.1 第一步：理解问题并确定设计的边界 140
10.2 第二步：提议高层级的设计并获得认同 140
10.2.1 不同类型的通知 141
10.2.2 联系信息的收集流程 143
10.2.3 通知的发送与接收流程 144
10.3 第三步：设计继续深入 148
10.3.1 可靠性 148
10.3.2 其他组件和要考虑的因素 149
10.3.3 更新后的设计 151
10.4 第四步：总结 152
11 设计news feed系统 153
11.1 第一步：理解问题并确定设计的边界 154
11.2 第二步：提议高层级的设计并获得认同 154
11.2.1 news feed API 155
11.2.2 feed的发布 155
11.2.3 news feed的构建 156
11.3 第三步：设计继续深入 157
11.3.1 深入探讨feed的发布流程 158
11.3.2 深入探讨news feed的获取流程 161
11.3.3 缓存架构 162
11.4 第四步：总结 163
12 设计聊天系统 165
12.1 第一步：理解问题并确定设计的边界 165
12.2 第二步：提议高层级的设计并获得认同 167
12.2.1 轮询 168
12.2.2 长轮询 169
12.2.3 WebSocket 170
12.2.4 高层级设计 171
12.2.5 数据模型 175
12.3 第三步：设计继续深入 177
12.3.1 服务发现 177
12.3.2 消息流 178
12.3.3 显示在线状态 182
12.4 第四步：总结 185
13 设计搜索自动补全系统 187
13.1 第一步：理解问题并确定设计的边界 188
13.1.1 封底估算 189
13.2 第二步：提议高层级的设计并获得认同 189
13.2.1 数据收集服务 190
13.2.2 查询服务 190
13.3 第三步：设计继续深入 191
13.3.1 字典树数据结构 192
13.3.2 数据收集服务 197
13.3.3 查询服务 200
13.3.4 字典树操作 202
13.3.5 扩展存储 204
13.4 第四步：总结 205
14 设计视频分享系统 207
14.1 第一步：理解问题并确定设计的边界 208
14.1.1 封底估算 209
14.2 第二步：提议高层级的设计并获得认同 210
14.2.1 视频上传流程 211
14.2.2 视频流式传输流程 216
14.3 第三步：设计继续深入 217
14.3.1 视频转码 217
14.3.2 有向无环图模型 217
14.3.3 视频转码架构 219
14.3.4 系统优化 225
14.3.5 错误处理 230
14.4 第四步：总结 231
15 设计云盘 232
15.1 第一步：理解问题并确定设计的边界 233
15.1.1 封底估算 235
15.2 第二步：提议高层级的设计并获得认同 235
15.2.1 API 236
15.2.2 跳出单服务器设计 237
15.2.3 同步冲突 240
15.2.4 高层级设计 241
15.3 第三步：设计继续深入 243
15.3.1 块服务器 243
15.3.2 高一致性需求 245
15.3.3 元数据数据库 245
15.3.4 上传流程 246
15.3.5 下载流程 247
15.3.6 通知服务 249
15.3.7 节约存储空间 249
15.3.8 故障处理 250
15.4 第四步：总结 251
16 设计支付系统 253
16.1 第一步：理解问题并确定设计的边界 254
16.2 第二步：提议高层级的设计并获得认同 256
16.2.1 收款流程 256
16.2.2 复式记账系统（Double-Entry System） 258
16.2.3 托管支付页面 259
16.2.4 付款流程 265
16.2.5 实时卖家仪表板 265
16.3 第三步：设计继续深入 266
16.3.1 重试和幂等 267
16.3.2 同步支付 vs. 异步支付 271
16.3.3 一致性 276
16.3.4 处理支付失败 282
16.3.5 支付安全 284
16.4 第四步：总结 285
17 设计指标监控和告警系统 287
17.1 第一步：理解问题并确定设计的边界 287
17.1.1 高层级需求 288
17.2 第二步：提议高层级的设计并获得认同 289
17.2.1 基本原理 290
17.2.2 数据模型 290
17.2.3 高层级设计 293
17.3 第三步：设计继续深入 294
17.3.1 指标数据的收集 295
17.3.2 扩展系统 300
17.3.3 查询服务 303
17.3.4 存储层 304
17.3.5 告警系统 307
17.3.6 可视化系统 309
17.4 第四步：总结 310
18 继续学习 311
后记 313