Raft如何做到线性一致性

一、为什么需要请求去重考虑一次Append(name, A)1. 客户端发送 Append 请求 2. Leader 将请求提交到 Raft 日志 3. KV 状态机执行成功name 变成 A 4. 服务端返回响应 5. 但响应在网络中丢失 6. 客户端超时重新发送同一个请求如果服务端无法识别重试Append会再次执行第一次执行name A 第二次执行name AA客户端实际上只请求了一次状态机却执行了两次这会破坏客户端期望的语义。因此必须给每个逻辑请求一个唯一身份。二、ClientId和CommandId分别是什么图中每个客户端维护两个重要信息。ClientId表示客户端身份例如客户端AClientId C1001 客户端BClientId C2001项目中Clerk创建时会生成客户端 ID并将请求序号初始化为 0Clerk::Clerk() : m_clientId(Uuid()), m_requestId(0), m_recentLeaderId(0) {}CommandId在项目中叫RequestId表示该客户端发出的第几个逻辑请求(C1001, 1) - Put(x, A) (C1001, 2) - Append(x, B) (C1001, 3) - Get(x)每次产生一个新的逻辑请求时客户端将m_requestId加一m_requestId; auto requestId m_requestId;三、为什么必须是二元组唯一请求标识是(ClientId, RequestId)不能只使用ClientId因为一个客户端会发送很多请求。不能只使用RequestId因为不同客户端都可能存在RequestId 1(C1001, 1) (C2001, 1)这显然是两个不同请求。因此ClientId RequestId共同构成一个类似“幂等键”的东西。项目中的 Raft 命令Op包含这两个字段class Op { public: std::string Operation; std::string Key; std::string Value; std::string ClientId; int RequestId; };四、重试时 RequestId 不能增加这是图中非常关键的一点。新的逻辑请求才增加RequestId第一次业务操作RequestId 10 第二次业务操作RequestId 11同一个请求因为超时而重试时必须继续使用原来的 ID发送请求(C1001, 11) 超时重试(C1001, 11) 再次重试(C1001, 11)不能变成 12、13否则服务端会认为它们是三个不同请求。这个项目做得是对的requestId在进入重试循环之前保存循环中始终复用它m_requestId; auto requestId m_requestId; while (true) { args.set_requestid(requestId); // 向不同服务器重试 }五、服务端如何判断重复请求每个 KV Server 保存std::unordered_mapstd::string, int m_lastRequestId;含义是ClientId - 该客户端已经执行过的最大 RequestId例如C1001 - 15 C2001 - 8表示C1001的 1 到 15 号请求已经处理过。判断重复请求的逻辑是return RequestId m_lastRequestId[ClientId];假设m_lastRequestId[C1001] 15那么请求 16新请求可以执行 请求 15重复请求不能再次执行 请求 14旧请求也不能再次执行这就是图中“只执行递增的 CommandId”的具体含义。六、完整的丢包重试过程客户端 C7 发送 (C7, 12, Append(x, A)) Leader 写入 Raft 日志 ↓ 多数节点复制成功 ↓ 日志被提交 ↓ KV 状态机执行 Append ↓ lastRequestId[C7] 12 ↓ 响应丢失 ↓ 客户端重试同一个 (C7, 12) ↓ 服务端发现 12 lastRequestId[C7] ↓ 不再执行 Append直接返回成功项目在 Raft 提交命令后调用ifRequestDuplicate()只有非重复请求才操作 KV 数据if (!ifRequestDuplicate(op.ClientId, op.RequestId)) { if (op.Operation Put) { ExecutePutOpOnKVDB(op); } if (op.Operation Append) { ExecuteAppendOpOnKVDB(op); } }执行 KV 操作时还会更新m_lastRequestId[op.ClientId] op.RequestId;KV 状态和去重信息在同一把互斥锁保护下更新这一点很重要。七、它与线性一致性的关系线性一致性要求每个操作看起来都在某一个瞬间原子完成而且不能违反真实时间顺序。Raft主要解决所有节点按照相同的日志顺序执行命令请求去重解决客户端的一次逻辑操作即使多次重试也只产生一次状态变化二者缺一不可。例如没有去重时Raft可能完全正确地提交两条相同的Append日志。Raft不知道它们是同一次请求的重试因为对 Raft 来说它们只是两条合法命令。所以更准确地说Raft提供一致的提交顺序ClientId RequestId提供重试情况下的至多一次执行语义二者共同支撑线性一致的客户端体验。网络层无法真正保证消息“只发送一次”这里只能保证重复消息不会导致状态机重复生效。