译文 原文 有用的飞书文档 和其他的算法相比 Strong leader 日志只能从领导者发送到其他节点 Leader election 随机计时器选举领导，在心跳机制上加上一些额外的工作 Membership changes 角色变换 Replicated state machines # 复制状态机一般基于日志实现，通俗的理解只要所有的机器按照相同的顺序执行指令，那么每个节点的状态都是确定的，所以需要把指令日志复制到其他节点上去，这就是一致性算法的工作 如果只是要求最终所有的节点都执行一样顺序的指令，而不要求实时性，则可以限定 只有一个节点可以进行写操作，因为只有写操作才可以改变系统的状态 写节点同步指令到其他节点，最终所有节点指令顺序一致 一致性算法的共有特性 安全性 不会返回一个错误结果，只要是在非拜占庭错误情况下，包括网络延迟，乱序，丢包，分区，冗余等都可以保障正确性 可用性 集群只要大多数机器可以正常通信，就可以确保可用，失败节点可以忽略或者后续恢复状态，大多数指的是半数以上 不依赖时序保证一致性 时钟错误或者消息延迟只有在极端情况下才会导致可用性 慢节点不会影响消息的反馈，消息可以快速的响应 拜占庭将军问题 Paxos # 难以理解 没有公认的可以实现的基础架构，大部分系统从Paxos开始，在遇到问题的时候自行想办法解决，导致最后的系统实现只能是类似Paxos的算法 Raft # 管理复制状态机的一种算法，他会在集群中选举一个leader，之后会复制所有的日志到其他节点实现一致性 他可以分解为三个问题 领导选举 一个新的领导人需要被选举出来，当先存的领导人宕机的时候 日志复制 领导人必须从客户端接收日志然后复制到集群中的其他节点，并且强制要求其他节点的日志保持和自己相同 安全性 在 Raft 中安全性的关键是在图 3 中展示的状态机安全：如果有任何的服务器节点已经应用了一个确定的日志条目到它的状态机中，那么其他服务器节点不能在同一个日志索引位置应用一个不同的指令 可以在这个网站查看实例 节点有三种状态 Follower Candidate Leader 他们之间的转换关系如下图 任期在 Raft 算法中充当逻辑时钟的作用，这会允许服务器节点查明一些过期的信息比如陈旧的领导者。每一个节点存储一个当前任期号，这一编号在整个时期内单调的增长。当服务器之间通信的时候会交换当前任期号；如果一个服务器的当前任期号比其他人小，那么他会更新自己的编号到较大的编号值。如果一个候选人或者领导者发现自己的任期号过期了，那么他会立即恢复成跟随者状态。如果一个节点接收到一个包含过期的任期号的请求，那么他会直接拒绝这个请求。 下面是详细的细节参数 下面的参数要求在节点上持久存在 currentTerm 服务器最后一次知道的任期号，初始化为 0，持续递增 votedFor 当前获得选票的候选人的Id log[] 日志条目集；每一个条目包含一个用户状态机执行的指令，和收到时的任期号 下面的参数在节点上是随时变化的 commitIndex 已知的最大的已经被提交的日志条目的索引值 lastApplied 最后被应用到状态机的日志条目索引值，初始化为 0，持续递增 下面的参数需要在leader重新选举之后变化的 nextIndex[] 对于每一个服务器，需要发送给他的下一个日志条目的索引值，初始化为领导人最后索引值加一 matchIndex[] 对于每一个服务器，已经复制给他的日志的最高索引值 这篇图表示的是rpc的参数信息以及返回值，由领导人负责调用来复制日志指令；也会用作heartbeat 参数 term 领导人的任期号 leaderId 领导人的 Id，以便于跟随者重定向请求 prevLogIndex 新的日志条目紧随之前的索引值 prevLogTerm prevLogIndex 条目的任期号 entries[] 准备存储的日志条目，表示心跳时为空；一次性发送多个是为了提高效率 leaderCommit 领导人已经提交的日志的索引值 返回值 term 当前的任期号，用于领导人去更新自己 success 跟随者包含了匹配上 prevLogIndex 和 prevLogTerm 的日志时为真 如果 term < currentTerm 就返回 false 如果日志在 prevLogIndex 位置处的日志条目的任期号和 prevLogTerm 不匹配，则返回 false 如果已经已经存在的日志条目和新的产生冲突（相同偏移量但是任期号不同），删除这一条和之后所有的 附加任何在已有的日志中不存在的条目 如果 leaderCommit > commitIndex，令 commitIndex 等于 leaderCommit 和 新日志条目索引值中较小的一个 由候选人负责调用用来征集选票

利用普通机器组成的大规模计算集群进行并行的,高容错,高性能的数据处理函数框架 原始论文点这里,论文翻译点这里，有时间的话，自行对比翻译和原文 最终实现的目标是–实现一个分布式系统，对程序员隐藏底层分布式细节，程序员只需要定义map和reduce 函数即可。 map reduce实现为简单的kv输出，其中map接受源数据，生成kv的中间结果，中间结果保存在worker节点上。 reduce负责处理map产生的中间结果的kv数据，只是简单的数据处理过程. 他最先是受到lisp中map和reduce原语的启发，再加上当时Google现实的处理大量数据的需求，从他们现有的系统抽象而来的。 在论文中，使用了一个单词统计的案例，此时实现map函数用来分割文本，切分出最基本的单词。然后再使用reduce进行聚合操作， // 输出单词以及出现的次数，map端输出1 map(String key,String value): // key: 文档名 // value: 文档内容 for each word w in value: EmitIntermediate(w,"1"); // 针对相同的key，次数+1 reduce(String key, Iterator values): // key: 一个单词 // value: 计数值列表 int result = 0; for each v in values: result += ParseInt(v); Emit(AsString(result)); 执行过程 文件划分 主节点划分任务 按照划分的任务启动worker，执行map任务 worker节点的数据生成为中间结果，保存在本节点 所有map任务执行完成之后，reduce得到对应中间节点的文件路径，通过rpc读取文件，进行reduce任务 reduce任务完成之后，最终结果写入目标文件 一个mr任务完成之后，回得到n(reduce)个结果文件，可以按照需求处理文件，可以直接使用，或者继续作为其他mr的输入，mr任务是可以嵌套的。 主节点 记录map和reduce任务的状态，例如是否开始，是否结束，执行时间等 协调工作节点，确定工作状态。确定任务是否需要重试，是否需要back up等 容错性 工作节点失败 主机点定时检测工作节点状态，如果无法链接，此时需要把此丢失的工作节点上的所有的任务重新安排到其他节点上执行。包括已完成的map任务，因为mr任务是需要等所有map任务结束之后才能执行reduce任务，其map任务的数据在保存在worker节点上的。所以需要重新执行map任务。至于reduce任务，由于他的输出之最终的数据结果，且需要记录到文件。所以为了避免重复的数据产生，已完成的reduce任务不重试，前提是输出数据已经保存到其他节点上。 主节点错误 一般是直接重试整个mr任务，因为mr的主节点应该是需要选择集群中比较可靠的节点，此时有理由怀疑其他节点也可能出现问题，所以此时选择整个重新执行，当然也可以恢复主节点，从记录的回复点重新执行 backup task mr中由于任务切分不一定均衡或者不同节点计算能力不同，有的任务执行格外慢，此时可以在其他空闲节点上执行相同的任务，此时集群中可能有多个相同的任务，最终哪一个任务先完成，主节点就会终止其他未完成的工作节点。 上面就是原始的mr描述，理所当然的可以想到一些提升的地方 平均的划分任务文件，尽量任务均衡 流式计算，在中间结果产生的时候，直接保存中间文件到reduce节点，避免最后集中处理中间结果时候的网络带宽消耗 本地计算mr，有的mr任务没必要在不同节点上执行，直接划分到一个节点或把的某些任务划分到一个节点上，实现本地计算。避免网络IO 提前进行reduce操作，可以使用reduce任务提前处理中间结果，减少中间结果的大小 记录计算节点的状态，多次执行任务的时候，可以记录某节点的处理速度，在下一个mr任务划分的时候，按照此信息划分任务 https://www.zhihu.com/question/303101438 map和reduce之间是完全串行的，如果有多个MR任务嵌套的话，由于每个mr必须实现map和reduce，会导致链路过长，实现和调试困难 性能无法达到要求 6.824 LAB # 先掌握go，重点为go的协程，管道，以及channel 代码框架已经给出来了，需要自己实现分布式的worker和master 可以先实现简单的无状态的mr，可以通过test-mr.sh中的前面的测试 worker # map和reduce的执行节点，需要从master获得任务，按照任务的类型，执行不同的job func Worker(mapf func(string, string) []KeyValue, reducef func(string, []string) string) { for { job := getJob() if job.