6.824
分布式系统学习
如何协调多台机器高效、可靠地完成统一目标
单机系统引发的问题：
- 存储问题：
PB级数据，单机根本无法存储全部数据
- 计算问题：
单机CPU和内存无法快速处理海量数据（如排序1TB数据单机需数小时）
- 可靠性问题：
通过多台机器协同工作，解决以下问题：
单机存储不足 -> 数据分片（Sharding）+ 多副本存储
单机算力不足 -> 并行计算（如MapReduce）
单点故障风险 -> 冗余设计 + 自动容错（如GFS多副本）
高并发请求处理 | 负载均衡 + 横向扩展（如BigTable分片）
什么是MapReduce
核心思想： 分而治之
统计全网网页中单词频率。
三阶段：
Map阶段：每台机器处理本地数据，输出<word, 1>。
Shuffle阶段：按单词分组，发送到Reduce节点。
Reduce阶段：合并相同单词的计数。
问题：
数据分布与存储问题
- 数据分片（Sharding）
如何将海量数据拆分到不同机器上？
- 数据复制（Replication）
如何保证数据冗余和高可用？
一致性与共识问题
- 一致性模型
多副本间如何保持数据一致？
- 共识算法
如何让多个节点对某个值达成一致？
容错与高可用问题
- 故障检测
如何快速发现节点故障？
- 恢复机制：
故障后如何恢复数据和服务？
通信与协同问题：
- 远程调用（RPC）
如何让跨节点调用像本地调用一样简单？
- 分布式锁（Distributed Lock）
如何避免多节点并发修改同一资源？
资源调度与负载均衡
- 任务调度（Scheduling）
如何将任务合理分配到多台机器？
- 负载均衡（Load Balancing）
如何均衡流量或计算负载？
事务与原子性
- 分布式事务（Distributed Transactions）
如何保证跨节点的操作原子性？
- 幂等性（Idempotency）
如何避免重复操作导致错误？
时间与顺序问题
- 时钟同步（Clock Synchronization）
如何保证多机器时钟一致？
- 事件顺序（Event Ordering）
如何确定跨节点事件的先后顺序？
安全与权限
- 认证与授权（AuthZ & AuthN）
如何控制节点间访问权限？
- 数据加密（Encryption）
如何保护传输和存储中的数据？
全文搜索
倒排索引：
为什么快？ 分析复杂度
N = 文档数量 L = 每个文档的平均长度（单词数） 遍历所有文档（N 个文档）。 在每个文档里查找 "Go"（要扫描这个文档的所有单词 → L）。
O(N × L)
而倒排索引：
首先需要构建索引，方便以后的查询 虽然 构建索引慢，但只做一次。
在构建中就已经搭建出：
Go → [ (doc1, [3]), // 第3个单词是 Go (doc2, [1]), // 第1个单词是 Go (doc3, [5]) // 第5个单词是 Go ]
用户输入关键词后，系统只需查倒排索引，不用再扫描文档全文，速度快