许昌做网站公司报价,网站建设实施流程,澄迈网站制作,网站提交百度了经常修改网站为什么要对 command 去重#xff1f;
在一个接收外部 command 的系统中#xff0c;通常一个 command 至少要执行一次#xff0c;我们称其为 at-least-once semantics。如果一个 command 执行失败#xff0c;系统内部经常会实现一套重试结构来尝试恢复这个问题#xff0c;…为什么要对 command 去重
在一个接收外部 command 的系统中通常一个 command 至少要执行一次我们称其为 at-least-once semantics。如果一个 command 执行失败系统内部经常会实现一套重试结构来尝试恢复这个问题这就会引出一个问题重复命令的提交可能会对系统的状态造成影响。
例如要实现 linearizable semantics (用户的每个操作外部看来是立即执行的、恰好执行一次、在它发起调用和返回之间的某一个时间点执行)我们就需要对 command 去重。在没有 command 去重的 Raft 实现中一个 command 可能会被执行多次leader 可能在 commit 之后返回给 client 期间崩溃client 如果向一个新的 leader 重试相同的 command 最后就会导致一个 command 被执行了两次。
解决这个问题可以有两种方案一种是类似 etcd 的方法区分出可以重试的命令和不可以重试的命令将不可以重试的命令的错误结果返回给用户并不提供任何保证即使这个命令可能已经被系统执行了。另一种方案是实现一套 command 的 track 机制检查系统中执行了的命令来实现 command 的去重当系统实现了这种去重机制可以实现 command 执行的 exactly-once semantics进而实现更高级别的一致性保证。
Etcd 中的 gRPC client interceptor重试的实现
// unaryClientInterceptor returns a new retrying unary client interceptor.
//
// The default configuration of the interceptor is to not retry *at all*. This behaviour can be
// changed through options (e.g. WithMax) on creation of the interceptor or on call (through grpc.CallOptions).
func (c *Client) unaryClientInterceptor(optFuncs ...retryOption) grpc.UnaryClientInterceptor {intOpts : reuseOrNewWithCallOptions(defaultOptions, optFuncs)return func(ctx context.Context, method string, req, reply interface{}, cc *grpc.ClientConn, invoker grpc.UnaryInvoker, opts ...grpc.CallOption) error {ctx withVersion(ctx)grpcOpts, retryOpts : filterCallOptions(opts)callOpts : reuseOrNewWithCallOptions(intOpts, retryOpts)...var lastErr errorfor attempt : uint(0); attempt callOpts.max; attempt {if err : waitRetryBackoff(ctx, attempt, callOpts); err ! nil {return err}...lastErr invoker(ctx, method, req, reply, cc, grpcOpts...)if lastErr nil {return nil}...// 在这里基于 callOpts 和 lastErr 判断是否可以重试if !isSafeRetry(c, lastErr, callOpts) {return lastErr}}return lastErr}
}去重在什么阶段完成
首先要清楚去重的目的是什么防止重复 command 对状态机造成影响。那么就会有两个阶段可以对 command 进行去重一是接收到 command 的阶段另一个是在应用到状态机时对 command 去重。
无论是哪个方法我们都需要一个数据结构来追踪已接收并执行的 command 的进度这样才可以对客户端发来的 command 去重处理。
在应用到状态机阶段时进行 command 的去重处理自然可以利用状态机的后端存储来获取到之前执行的 command 例如 Log::get_cmd_ids 可以获取 log 中所有的 command id利用这个 command id set 可以对即将应用到状态机的 command 进行去重处理。
在接收到 command 阶段进行去重处理就需要额外维护一套数据结构进行处理通常这套数据结构需要维护在内存中保证高效的读写速度所以要求这套数据结构不能占用非常大的空间可能要具备 GC 的机制。
对于第一种方案首要的问题是 log compaction 机制会让去重机制失效。在 raft 系统中大家都会实现 log compaction 来避免 log 占用过多内存如果一个 command log 已经被 compact那么下次接受到相同的 command 就无法去重了。其次的问题是重复的 command 会在发送到状态机之前还会进行 preparespeculative execute 处理消耗额外的 CPU最后的问题就是读状态机的操作是昂贵的这种去重手段的性能损耗会很大。
综上我们可以确定在接受到 command 的阶段就进行去重处理尽早地拒绝重复 command 的提交。 目前的 command 去重设计的缺陷
Xline curp 内的 command 是一个靠外部实现的 trait我们没有像 etcd 一样区别对待一些 command 的重试行为所以我们没有在 command trait 中定义是否具有重试的特征。
目前 curp client 中对所有的 command 都会有重试所以我们在 curp server 处实现了一套简单的去重机制
CommandBoard 中有一个 IndexSet用于记录之前已经执行过的 command 的 ID
/// Command board is a buffer to track cmd states and store notifiers for requests that need to wait for a cmd
#[derive(Debug)]
pub(super) struct CommandBoardC: Command {.../// The cmd has been received before, this is used for deduppub(super) sync: IndexSetProposeId,...
}于是我们可以在 O(1) 的开销下在 propose 阶段对命令进行去重
pub(super) fn handle_propose(self,cmd: ArcC,) - Result((OptionServerId, u64), Resultbool, ProposeError), CurpError {...if !self.ctx.cb.map_write(|mut cb_w| cb_w.sync.insert(id)) {return Ok((info, Err(ProposeError::Duplicated)));}...}为了保证 CURP 在发生 leadership transfer 时不会丢失当前正在的执行的 command 的 ID我们在恢复 Speculative Pool 中也会恢复这个结构
/// Recover from all voters spec poolsfn recover_from_spec_pools(self,st: mut State,log: mut LogC,spec_pools: HashMapServerId, VecPoolEntryC,) {...for cmd in recovered_cmds {let _ig_sync cb_w.sync.insert(cmd.id()); // may have been inserted before...}}最后为了避免这个 IndexSet占用过多内存之前在 Xline 源码解读文章中提到的 GC 机制会定时清理这个结构。
不过在极端的网络条件下client 在发起 command 和收到返回之间的间隔超过了 GC 的间隔IndexSet 中记录的 ProposeId 被 GC 清理了client 重试这个命令会导致这个命令的去重失效。
我们在 madsim 的测试中发现了这种极端情况由于 madsim 的时钟的流速比现实快很多最后触发了这种问题需要提出一个新的去重结构来解决问题。本文的后半部分将介绍 RIFL(Reusable Infrastructure for Linearizability) 的工作原理后续的文章中我们将详细介绍如何在 Xline 中实现 RIFL。 RIFL 介绍
RIFL (Reusable Infrastructure for Linearizability), 是一种在大规模集群中保证 RPC(command) exactly-once semantics 的一套基础设施。为了将 RIFL 的术语和 Xline 系统的术语的统一本篇章中 RPC 和 Command 具有相同的语义。
RIFL 简介
在 RIFL 中首先要给每一个 RPC 分配一个 unique identifier它由一个 64-bit 的 client_id 和在这个 client_id 下分配的 64-bit 的递增 sequence_number 组成。
client_id 需要由一个 system-wide 的结构生成在 RIFL 中使用了一个全局的 Lease Manager 模块实现Lease Manager 会为每个 client 分配一个 client_id并创建一个与之对应的 leaseclient 需要不断 keep alive 这个 leaseserver 则需要检查这个 lease 来判断 client 是否崩溃。
其次RIFL 需要一个 RPC 的完成记录和追踪信息持久化然后RIFL 在系统迁移时RPC 的完成记录也需要一并迁移这样可以保证 RIFL 在系统迁移过程中也能保证 RPC 不会重复执行重复执行的 RPC 将会直接取出之前的完成记录。
最后 RPC 的完成记录需要在 Client 确认下清除或者 Client 的奔溃后清除这样可以安全地清理掉一些不必要的存储。
RIFL 具体组件及功能
下面是 RIFL 中的一些主要组件以及对应的功能1. Request Tracker: 在 client 端追踪发送出去的命令 a. newSequenceNum(): 为一个 RPC 生成一个递增的序列号 b. firstIncomplete(): 获取当前最小的还未收到 RPC 回复的序列号 c. rpcComplete(sequenceNumber): 标记当前 sequenceNumber 为收到后续用于更新 firstIncomplete
2. Lease Manager: 一个统一的 Lease Manager 模块client 使用它为 client_id 续租, server 使用它检查 client_id 的租约是否到期 a. getClientId(): client 获取自己的 client_id如果不存在的话就询问 lease server 创建一个 b. checkAlive(clientId): server 检查这个 client_id 的租约是否到期来判断该 client 是否存活
3. Result Tracker: 在 server 端追踪接收到的命令以及 client 确认的进度 a. checkDuplicate(clientId, sequenceNumber): 根据完成记录来判断这个 RPC 是否重复 b. recordCompletion(clientId, sequenceNumber, completionRecord): 在返回给 client 之前标记这个 RPC 为已执行并存储 completionRecord c. processAck(clientId, firstIncomplete): 为这个 client 回收 firstIncomplete 之前的所有 RPC 的完成记录。 当 Server 收到一个 RPC(client_id, seq_num, first_incomplete) 时会根据 checkDuplicate 来检查这个 RPC 的状态1. NEW: 一个新的 RPC按照正常的逻辑处理请求2. COMPLETED: 一个已经执行完成的 RPC返回执行完成的记录3. IN_PROGRESS: 一个正在执行的 RPC返回 IN_PROGRESS 错误4. STALE: 一个已经被 client 确认回收的 RPC返回 STALE 错误
其次Server 会根据传来的 RPC 中 first_incomplete 字段来调用 proccessAck回收掉已经被确认的 RPC 的完成记录。最后当这个 RPC 执行完成返回给 Client 之前会调用 recordCompletion 来将完成记录持久化并标记这个 RPC 为 COMPLETED。
除此之外Server 会检查 client_id 的租约是否还有效来判断一个 client 是否还存活如果失效则回收掉这个 client_id 下的所有的完成记录。 RIFL 性能分析
在 RIFL 的结构中很容易发现一处开销来自于 client 和 server 与 Lease Manager 之间通信的开销RIFL paper 中提到了 server 可以缓存某个 client_id lease 的过期时间在即将过期时查询 Lease Manager这样可以省去一些的网络通信。
在上述的过程中 checkDuplicate 或者 proccessAck 中至少会有一个 O(n) 复杂度的操作按 sequenceNumber 顺序记录进行 checkDuplicate 或者无序记录 sequnceNumber 但需要遍历过滤小于 first_incomplete 进行 processAck和之前使用 IndexSet 方案的 O(1) 复杂度相比RIFL 会在这里会有一部分开销。我们可以将 processAck 单独作为一个 RPC 用于通知 server 回收完成记录来优化一些性能。
最后由于回收的第一种机制仅是检查 first_incomplete这可能会遇到某个耗时很长的 RPC 阻塞了回收后续 RPC 的完成记录最后可能导致 server 内存占用过多。RIFL paper 中提到了可以为某个 client 设置最大 inflight RPC 的数量过多的 RPC 将会被拒绝另外也可以考虑提前回收后续的 RPC 完成记录这样可能会使 RIFL 更加复杂。
小结
以上是 RIFL 为 unary RPC 维护 exactly-once semantics 的机制paper 中 §6 Implementing Transactions with RIFL 中描述了 RIFL 对多个对象的 transactions 维护 exactly-once semantics 的机制由于 Xline 系统的 transaction 会作为一个单一 command 发送给 server所以不需要单独处理感兴趣的读者可以看看这里就不展开赘述了。 Summary
本文前半部分从 command 去重机制的契机开始介绍了去重的必要性以及目前 Xline 的去重机制存在的一些问题。后半部分详细讲解了 RIFL(Reusable Infrastructure for Linearizability) 的工作原理并对其进行了一些性能分析。后续的文章中将继续介绍我们是如何将 RIFL 应用到我们的 Xline 当中以及对 RIFL 做了哪些必要的更改与优化。 Xline于2023年6月加入CNCF 沙箱计划是一个用于元数据管理的分布式KV存储。Xline项目以Rust语言写就。感谢每一位参与的社区伙伴对Xline的帮助和支持也欢迎更多使用者和开发者参与体验和使用Xline。
GitHub链接
https://github.com/xline-kv/Xline
Xline官网www.xline.cloud
Xline Discord:
https://discord.gg/XyFXGpSfvb
