在了解方案前先了解一下几个理论理论CAPC consistency 一致性: 所有节点在同一时间访问时, 拿到的均为最新数据A availability 可用性: 向非故障节点发起请求后, 每一次请求都能在有限时间内获得合理的响应（而非错误或超时）P partition tolerate 分区容错性: 部分节点挂了, 依旧能正常对外提供服务在分布式系统下,P是前提,仅能实现CP/APCP 一致性 + 分区容错: 当网络分区发生时，为了保证数据一致，系统会拒绝服务或报错，牺牲可用性（A）。适用于银行转账、交易系统AP 可用性 + 分区容错: 当网络分区发生时，系统保证可用，但允许读取旧数据，牺牲强一致性（C），满足最终一致性。适用于大多数Web应用、社交媒体CA 一致性 + 可用性: 仅可在单机环境下成立,常用数据库如mysql oracle等BASEBASE是下面几个单词的缩写, 此理论是互联网实践而来,是对CAP理论的演变和权衡结果.Basically Available 基本可用: 在系统发生故障或高负载时, 必须保证系统核心功能可用, 非核心功能使用降级熔断等策略保证--基本可用Soft-state 软状态: 允许系统存在短暂、无锁、可过渡的中间状态，节点间数据暂时不一致, 但不影响整体可用性.​ 与硬状态(ACID事务, 实时锁定)相对Eventually Consistent 最终一致性: BASE理论强调最终一致性, 即在有限时间和有穷步后, 结果最终一致.一致性的三个状态一致性强调结果, 即数据最后能否一致强一致性: 系统写了什么, 读出来就是什么弱一致性: 不保证多久后读取数据是最新的, 甚至永远可能读不到最新值. 都不保证最终一致性: 现在不一定一致, 但在有限时间后一定一致幂等性同一个操作执行多次, 结果相同常见方案XA 标准化分布式事务这是对2PC 的标准化实现, 是X/Open 组织制定的、跨数据库/消息队列的分布式事务工业级标准协议. 流程参见2PC支持XA 的有MySQL、Oracle、PostgreSQL、SQL Server、RocketMQ、Kafka 等几乎所有主流中间件2PC 两阶段提交借用XA 的角色定义: AP 业务应用(Application Program), TM 事务管理器(Transaction Manager), RM 参与者(Resource Manager)AP 向TM 发起全局事务TM向RM A, B发送要执行的SQlRM A, B开启事务, 执行业务SQL, 两个执行成功/失败均向TM 返回TM 根据返回决定向RM 发送commit或rollback优点: 强一致, 开发简单. 适用于金融等系统缺点: 性能差, 协调者节点挂了会导致锁无法释放(可用心跳包等方法解决), 极端情况下会导致一部分commit, 一部分rollback3PC 三阶段提交CanCommit: 仅检查库存, 锁.PreCommit: 所有节点的Can 均返回成功时, 向所有节点发送PreCommit, 此步骤开启事务但不提交.DoCommit: 所有节点的PreCommit 均返回成功时,向所有节点发送DoCommit.3PC 为所有节点增加了超时决策逻辑, 在PreCommit 后超时可选自动Abort/DoCommit, 在CanCommit 超时自动Abort.极端情况下仍有可能导致协调者只给部分节点发送了DoCommit, 剩下节点可能Abort/DoCommit.生产几乎不用AT 自动事务模式 (Seata)官方链接: https://seata.apache.org/zh-cn/docs/overview/what-is-seata 你可以阅读官方文档获取更详细的说明三个角色TM（Transaction Manager）: 业务应用里的事务发起方TC（Transaction Coordinator）: Seata Server, 管理全局事务状态、协调各分支提交/回滚、维护全局锁RM（Resource Manager）: 由 Seata 代理数据源实现, 自动拦截 SQL、生成日志、执行回滚一阶段执行流程开启本地事务, 解析SQL 的操作(update等)、表（product），条件（where name = 'TXC'）等相关的信息查询前镜像：根据SQL定位到记录, 将记录保留一份执行业务 SQL, 将执行后的结果当做后镜像: 根据前镜像的结果，通过 主键 定位数据将前后镜像和业务SQL 组成一条回滚日志记录, 插入到UNDO_LOG 表中向TC 申请指定表的指定主键的记录的全局锁如果申请到全局锁, 本地事务提交(携带undo log一块). 如果拿锁失败则继续尝试, 超出尝试范围将放弃. 回滚本地事务, 释放本地锁将本地事务结果上报给TC二阶段执行流程回滚收到 TC 的分支回滚请求, 开启本地事务根据 XID(全局事务锁ID) 和 Branch ID(分支事务ID) 查找到 UNDO_LOG 表中对应记录那记录中的后镜像与当前数据比较, 如果不同, 则说明数据被当前全局事务之外的动作修改. 此时根据配置策略处理, 详见文档根据 UNDO_LOG 的前镜像和 SQL 语句生成对应回滚语句提交本地事务. 上报本地事务执行结果给 TC提交收到 TC 的分支提交请求, 将请求放入异步队列, 立刻响应处理成功结果给 TC异步队列删除 UNDO_LOG 表的记录更详细流程下方解释和图表来自对豆包的总结, 不保证正确.TC 是被动接收方, 通过 @GlobalTransactional 注解实现开启事务、提交、回滚、获取当前状态等方法. 根据context判断是rm还是tm, tc在一开始是不知道有多少rm的, 而是通过 tm 调用 rm, 然后 rm 主动携带 branchID xid 等向 tc 报道. 在完成后 tm 会根据执行向 tc 上报 commit/rollback步骤发起方协议 / 动作接收方作用1TMGlobalBeginRequestTC开启全局事务，获取 XID2TMRPC 调用 (含 XID)RM业务驱动 RM 干活3RM执行本地 SQL, 生成 UNDO LOGDB执行业务逻辑4RMBranchRegisterRequest (含 lockKey)TCRM 主动报到，TC 知道了 RM 的存在并分配全局锁5RMCommit Local TransactionDB提交本地事务，释放本地锁6TMGlobalCommit/RollbackRequestTC告诉 TC 是提交还是回滚7TCBranchCommit/RollbackRequestRMTC 主动推送命令，让 RM 执行二阶段操作8RM删除 UNDO_LOG / 执行回滚 SQLDB完成二阶段收尾TCC Try-Confirm-Cancel用户下单商品, 执行Try检查商品和预留字段的库存, 增加预留库存操作1 无问题执行Confirm, 实际扣减商品库存, 删除预留库存. 操作1 存在问题执行Cancel, 取消预留库存, 执行其他恢复代码优点: 性能好于2PC, 因为取消了事务导致的长锁(但可能需要短锁/乐观锁保证库存检查和预留)缺点: 开发量大, 每个业务均需编写三个接口: TrySell, ConfirmSell, CancelSell, 需修改数据库表结构衍生方案通用型 TCC 异步化try阶段不变, confirm/cancel 阶段基于 MQ 异步异步确保型 TCC借用 Seata 图片, 感觉类似于 RocketMQ 的半消息机制try阶段发消息给mq, 只做存储, 消费者无法读取到confirm/cancel 阶段消费者才可以读取补偿型 TCChttps://seata.apache.org/zh-cn/blog/tcc-mode-applicable-scenario-analysis/#%E5%9B%9B%E8%A1%A5%E5%81%BF%E5%9E%8B-tcc-%E8%A7%A3%E5%86%B3%E6%96%B9%E6%A1%88 seata官网文章补偿型 TCC 适用并发冲突少 / 外部业务, 只需要 Try 和 Cancel 两个接口即可实现我向A, B发送Do请求如果都成功则正常处理如果A / B 出现问题则发送 Compensate 请求补偿seata会自己解决原子性问题, 这里我懒得深入了解了基于本地消息的最终一致性方案拥有业务表A, 信息表B执行业务, 首先启动事务, 事务中执行业务, 同时将消息插入消息表中. commit/rollback 保证业务和消息100%不会丢失定时任务扫描信息表, 发送信息到MQ消费方读取消息处理优点: 实现简单, 不依赖外部消息中间件的事务, 本地消息绝对不会丢失缺点: 业务表和消息表耦合, 定时任务有延迟基于可靠消息的最终一致性方案即借用外部消息中间件的事务功能, RocketMQ叫半消息机制, Kafka叫生产者事务(0.11引入), RabbitMQ叫AMQP事务RocketMQ流程极端情况下, 业务代码在执行commit/rollback时可能会出现网络波动导致没有正确处理, 这时会有事务回查(补偿)机制, RocketMQ 会主动询问此事务是commit还是rollbackKafkakafka流程同上, 但没有回查机制, 依靠三种状态: committed, aborted, incomplete和事务协调器兜底.事务开启, 消息发送commit/abort没有送达根据transaction.timeout.ms 配置, 超时将事务标记为Aborted结束消费者默认仅读取committed 消息, 可通过isolation.level=read_committed 配置可以手写补偿机制完善.RabbitMQ基于AMQP协议的原生事务性能较差, 生产环境中几乎不用, 此事务流程同上更多使用发布确认机制(流程不同上):单个确认: 批量确认: 流程和单个确认相同, 是堆积到一定数量消息后, 将消息一次性发送过去等待整批响应. 缺点是无法确定批次中哪个消息出现问题异步确认(性能最优): 但需要手动完善机制才能实现RocketMQ效果最大努力通知方案优点: 实现简单, 最柔, 整体流程无锁缺点: 一致性最差Saga将长事务拆分为多个单步事务, 每个事务对应自己的补偿失误定义事务为T, 取消为C正常流程: T1->T2->T3->T4失败失败：T1->T2->T3失败->C3->C2->C1两种模式编排式(生产常用)由协调器调配: 先做1->再做2, 如果2失败协调器下令回滚1协作式服务直接靠消息/其他手段互相通知A 做完发消息, B 监听做, B 失败发消息, A 自己回滚结论优点: 支持长事务, 并发高, 整体流程无锁(即不会像2PC 那样所有T 均上锁)缺点: 补偿逻辑复杂, 中间状态会暴露给用户衍生方案嵌套 SagaSaga 只允许两个层次的嵌套, 即 父Saga-多个子Saga. 而嵌套 Saga 则是将一个/多个子事务合并成一个独立、完整的 Saga 事务.子 Saga 拥有自己完整的正向执行流和反向补偿流子 Saga 对外暴露原子化的事务接口, 父 Saga 将其视为普通事务节点, 不感知其内部实现, 也不能单独调用子 Saga 中的内部某个事务子 Saga 不能依赖父 Saga 的其他子 Saga 资源执行流程Root Saga 流程为 A → B → C，其中 B 是嵌套子 Saga（包含 B1→B2→B3）正向：A 成功 → 子 Saga B 全流程执行成功 → C 成功，全局事务完成异常：A 成功 → 子 Saga B 执行到 B2 失败 → 子 Saga B 先补偿 B2→补偿 B1，完成自回滚 → 向 Root Saga 返回失败 → Root Saga 补偿 A，全局回滚完成基于事件溯源（Event Sourcing, ES）的事务方案ES指: 不存储实体的当前状态，只存储所有导致状态变更的不可变事件. 比如update set a = 50 where id = 1; 这里我们不存储a=50这个结果, 而是存储 将 id 为 1 的记录, a 字段修改为 50 这个操作.ES + Outbox Pattern收到操作请求, 记录请求的操作到 Event Store 中,状态标记为 待发布.按顺序投递存储的操作到 MQ, 状态标记为 已发布下游监听 MQ, 执行本地事务并写入到自身 Event Store, 并且通过唯一 id 实现幂等性.ES + Saga订单服务接收请求, 在本地事务中生成订单创建事件写入 Event Store, 发布到事件总线Saga 编排器监听订单创建成功事件, 触发库存服务扣减库存, 库存服务完成后生成库存扣减成功事件写入自身 Event Store 并发布编排器依次监听和触发, 直到整个 saga 事务结束即使服务宕机也可以通过 ES 重放CQRS(读写分离) + ESCQRS: 命令查询职责分离, 将写操作和读操作完全拆分.写侧（命令端）：完全基于 ES 实现，只负责处理业务命令、生成不可变事件、写入 Event Store，保障写事务的原子性, 是整个系统唯一的事实源读侧（查询端）：通过监听写侧的事件流, 更新适配查询场景的读库（MySQL/ES/Redis 等），通过事件的可靠消费保障读写最终一致性跨服务分布式事务通过「命令→事件→命令」的事件驱动流转实现，全程无锁、无耦合。写侧处理：业务请求以 Command 形式提交到写服务，写服务验证命令合法性后，在本地事务中生成业务事件写入 Event Store，完成写侧事务，事件发布到事件总线跨服务事务流转：下游服务监听对应事件, 转化为自身的业务 Command, 执行本地写操作并生成新的事件写入 Event Store, 完成跨服务事务的原子性流转读侧同步：读侧的投影服务（Projection）监听事件总线，根据事件类型更新对应的读库（如订单列表写入 MySQL、热点数据写入 Redis）。一致性保障：通过事件唯一 ID 实现消费幂等，确保事件只被处理一次. 读侧更新失败会自动重试，直到成功；若读侧数据出现不一致，可直接重放 Event Store 的事件，重新生成全量读库数据，彻底修复一致性问题。事务回滚：跨服务事务失败时生成补偿事件，写侧 Event Store 持久化补偿事件，读侧投影服务同步更新读库，完成回滚后的全链路一致性。参考[]: https://seata.apache.org/zh-cn/docs/overview "Seata文档"[]: https://javaguide.cn/distributed-system/protocol/cap-and-base-theorem.html "CAP & BASE理论详解"[]: https://www.doubao.com/ "豆包"
基于物品的协同过滤Item base collaborative filtering,这个算法的核心逻辑是: 你喜欢物品A,根据其他喜欢A的用户喜欢的物品B来计算相似度,然后推荐.ItemCF核心算法1. 定义用户交互矩阵U = { "user1": { "item1": 1, "item2": 1, "item3": 0, }, "user2": { "item1": 1, "item2": 0, "item3": 1, }, "user3": { "item1": 1, "item2": 0, "item3": 1, } }2. 计算物品相似度实际时你应当只计算有相同交互物品的用户的其他物品相似度.使用下面的余弦相似度公式计算:$$ w_{ij} = \frac{C[i][j]}{\sqrt{|N(i)| \cdot |N(j)|}} $$C[i] [j]: 物品i物品j共同交互用户数量,遍历每个用户的物品,两两配对然后加一,这就是现实了共现矩阵(统计两个或多个元素在特定上下文内同时出现频率的二维矩阵)|N(i)|和物品i有交互的用户总数,|N(j)|一样.# 实现共现矩阵 collective_matrix = {} # 物品被操作计次 item_operate = {son_name: 0 for _,item in U.items() for son_name in item.keys()} for index, v in U.items(): for ci,item in enumerate(v.keys()): if ci == len(v.keys())-1: break collective_matrix[item] = {name: 0 for name in v.keys()} break for pk in U.keys(): for item in U[pk].keys(): if U[pk][item] != 0: item_operate[item] +=1 for name,v in U.items(): # 获取item长度 l = len(v) # 获取所有key all_keys = list(v.keys()) for i in range(l): # 如果用户没有交互此物品,跳过 if v[all_keys[i]] == 0: continue # user交互的物品总数减去已经遍历过的物品数 for j in range(l-i-1): if v[all_keys[i]] == v[all_keys[i+j+1]]: collective_matrix[all_keys[i]][all_keys[i+j+1]] += 1 # 输出 print(collective_matrix) print(item_operate) # 计算两个物品的相似度 similar_dict = {} for item_parent in collective_matrix.keys(): for son_key in (collective_matrix[item_parent]).keys(): # 默认没有C[i][i]这种情况 if son_key is item_parent: continue # 如果没有人交互i和j两个物品,跳过 if collective_matrix[item_parent][son_key] == 0: continue # 开始计算不同物品的相似度 if item_parent not in similar_dict: similar_dict[item_parent] = {} similar_dict[item_parent] |= { son_key: collective_matrix[item_parent][son_key]/math.sqrt(item_operate[item_parent] * item_operate[son_key]) } print(similar_dict) # 输出 {'item1': {'item1': 0, 'item2': 1, 'item3': 2}, 'item2': {'item1': 0, 'item2': 0, 'item3': 0}} {'item1': 3, 'item2': 1, 'item3': 2} {'item1': {'item2': 0.5773502691896258, 'item3': 0.8164965809277261}}用余弦相似度公式再次确认是否正确:$$ w_{ij} = \frac{1}{\sqrt{3 \cdot 1}} \approx 0.577 $$分子C[i] [j]取值为 1, 分母中 |N(i)| =3, |N(j)| =1. 算出item1和2的结果正确3. 候选物品推荐用户最近交互的物品是abc拿abc找出相似度最高的N个物品使用下面公司按照最后得分排序输出$$ p(u, i) = \sum_{j \in N(u)} w_{ij} \cdot r_{uj} $$sigma(Σ)是表示求和.N(u)代表用户交互过的所有物品.wij表示物品相似度.ruj为用户u对物品j的的兴趣强度或者权重,可以为0这里假设ruj为1, u为user1, 感兴趣物品(i)为item3,上面公式计算示例: p(user1,3) = w13 1 + w23 1 = 0.816这里只有item1和item3有共同交互用户,所以其实可以直接得出0.816皮尔逊相关系数算法余弦相似度适用于隐式反馈场景（如点击、浏览）,但在某些应用中我们还有显式评分数据（如5星评分、点赞数等）。对于这类数据，可以使用更精细的相似度计算方法。$$ w_{ij} = \frac{\sum_{u \in U_{ij}}(r_{ui} - \bar{r}_i)(r_{uj} - \bar{r}_j)}{\sqrt{\sum_{u \in U_{ij}}(r_{ui} - \bar{r}_i)^2}\sqrt{\sum_{u \in U_{ij}}(r_{uj} - \bar{r}_j)^2}} $$uij表示同时评分过i和j的用户集合rui表示用户u对i的评分-ri是物品i的平均评分基于皮尔逊系数可以预测未接触物品的评分$$ \hat{r}_{u,j} = \bar{r}_{j} + \frac{\sum_{k \in S_j} w_{jk}\,\left( r_{u,k} - \bar{r}_{k} \right)}{\sum_{k \in S_j} w_{jk}} $$
Anti-Entropy熵是物理学上的一个概念，代表杂乱无章，而反熵就是在杂乱无章中寻求一致。本质上，反熵是一种通过异步修复实现最终一致性的方法。--钝悟节点周期性随机选择节点,交换全量数据消除差异.周期不会结束.若运行时间较长会导致传递数据过大.状态Susceptible(易感): 节点还没接收到这条消息Infective(传染性的): 节点已经持有这条消息，并且会周期性地向其他节点传播全量消息过程1. 节点周期性触发节点 A 每隔固定时间 T (例如 5 秒) 执行 Anti-Entropy随机选择一个邻居节点 B (fan-out=1,此时只会选择一个邻居节点)2. 交换状态节点 A 将自己完整状态发送给 B节点 B 将自己完整状态发送给 A3. 计算差异A 接收到 B 的状态 → 找出 B 拥有但自己缺失的部分 → 更新自己B 接收到 A 的状态 → 找出 A 拥有但自己缺失的部分 → 更新自己4. 重复执行节点 A 等待下一个周期，再随机选择一个节点执行同样操作所有节点独立、周期性地执行这个流程优点最终一致性确定节点周期性全量或差异同步，理论上所有节点最终必然一致。容错能力强即使某轮传播失败，下轮周期仍会补救，适应网络不稳定。修复遗漏节点无论之前哪个节点没收到消息，周期性同步最终都会把缺失数据同步过去。适合大规模网络同步不依赖单轮成功，概率模型收敛分析简单可靠。缺点传播速度相对慢周期性触发可能导致新消息扩散比 Rumor-Mongering 慢。带宽消耗大全量或差异同步比单条消息增量传播消耗更多网络资源。实现稍复杂需要周期触发、状态摘要或差异计算(摘要和差异是现代实践,论文中没有)，以及节点间同步机制。Rumor-Mongering仅传播最新数据. 每次传播都随机选择节点进行传播, 如果节点已经持有消息(即传播失败), 或因网络超时传播失败, 计数器+1, 达到阈值后停止.由于是增量传播,数据包小,不会无限制传播.状态Susceptible(易感): 节点还没接收到这条消息Infective(传染性的): 节点已经持有这条消息，并且会周期性地向其他节点增量传播消息。Removed: 当收到被传播节点持有此消息,或传播次数超过阈值时,停止传播这条消息过程论文传播停止是因为全网络节点已感染有点难理解,这里用工程实践版的1. 收到消息节点 A 收到消息更新 infected 列表标记这个消息已知2. 选择目标节点 A 从自己的邻居列表中随机选择几个节点 (fan-out数量)3. 尝试发送消息对每个目标节点 B：如果 B 没有收到过消息 M:B 接收消息 M,并在下一轮也会对自己的邻居进行 rumor-mongering 传播节点 A 的计数器 不增加如果 B 已经持有消息 M:节点 A 的计数器 +1 (表示一次失败传播)如果 B 网络超时:节点节点 A 的计数器 +1 (表示一次失败传播)4. 检查停止条件节点 A 对消息 M 的传播计数器达到阈值 (例如 3):节点 A 停止传播消息 M节点 A 不再尝试发送 M 给其他节点5. 下一轮传播对于尚未停止的节点,重复 1-3节点每轮随机选择邻居,尝试传播消息,直到自己的计数器达到阈值优点快速传播新消息节点收到新消息就立即传播,消息扩散速度快低带宽开销（增量传播）只发送新消息,不发送全量状态实现简单逻辑只需随机选择邻居并推送消息,无需全局状态或复杂同步表概率性最终一致性随着轮次增加,高概率网络大部分节点最终会收到消息缺点潜在不一致问题节点 A 向节点 B 传播消息 M，但因为网络超时/丢包, B 没有收到 → 本轮传播失败A 后续随机选择节点传播时 可能没再次选择 BA 的失败计数器达到阈值 → 停止传播如果其他节点也因为随机选择没选择到 B,由于Rumor-mongering不会向Anti-Entropy主动周期性和邻居节点同步, 所以 B 在下次被传播前缺失了这条消息结果：网络中存在少数节点缺失该消息 → 高概率最终一致,但不是强一致性可靠性受网络不稳定影响大网络超时或节点离线可能导致消息传播失败,且节点不会自动重新尝试收敛不可预测消息最终传播到全网的时间依赖于随机性和阈值,不保证精确收敛不能保证强一致性适合快速扩散场景,但不能保证每个节点最终状态完全一致因此现代实践中先使用Rumor-mongering快速传播,再使用Anti-Entropy保证最终一致性通信模式Push节点A全量推送自己所有数据给B节点,B节点对比差异更新自己Pull节点A将自己的key,version推送给BB对比本地数据,增量推送(包含key,value,version)比A新的数据给AA对比更新自己Push-Pull节点A将自己的key,version推送给BB对比本地数据,增量推送(包含key,value,version)比A新的数据给AA对比更新自己,再增量推送(包含key,value,version)比B新的数据给BB对比更新自己注意: Anti-Entropy和Rumor-mongering可以随意选择Push,Pull,Push-Pull搭配,而不是固定的.Reference[]: https://dunwu.github.io/waterdrop/pages/88db2f5d "分布式算法 Gossip"[]: https://chatgpt.com/ "ChatGPT"
前置请先看完 http://www.kailing.pub/raft/index.html 后继续查看文章角色leaderfollowercandidate每个节点同时只扮演一个角色,允许切换Leader领导者,接收客户端请求,使用日志条目复制数据到Follower维护状态term: 当前任期号log[]: 日志条目数组,每个条目包含客户端指令和产生该条目的任期号commitIndex: 已被集群多数节点复制且可以提交的日志最大索引（所有≤该索引的日志均可应用到状态机）lastApplied: 已应用到状态机的日志最大索引（记录本地状态机执行到哪条日志）nextIndex[]: 对每个 follower 维护一个值，表示下一次向该 follower 发送日志的起始索引matchIndex[]: 对每个 follower 维护一个值，表示该 follower 已成功复制的最大日志索引Follower跟随者,被动接受Leader的日志复制请求和心跳包维护状态term: 当前任期号（与 leader 保持一致，或在发现更高任期时更新）log[]: 日志条目数组（与 leader 同步的日志副本）commitIndex: 已被集群多数节点复制且可以提交的日志最大索引（由 leader 通过心跳同步）lastApplied: 已应用到状态机的日志最大索引（记录本地状态机执行到哪条日志）votedFor: 当前任期内投票给的节点 ID（用于避免重复投票，保证每个任期仅投一票）超时计时器：用于检测 leader 是否失联（若超时未收到 leader 心跳，会转换为 candidate 发起选举）Candidate候选者,当Follower在一定时间没有接收到Leader心跳包后将从follower切换到candidate进行选举请求日志复制作用: 专门用于向 follower 同步新的日志条目内容: 包含 leader 的任期号（term）、前一条日志的索引和任期（用于 follower 校验匹配）、需要同步的日志条目（可能是一条或多条）、leader 当前的commitIndex（用于同步提交状态）心跳包作用：用于维持leader的地位,定时发送,防止follower因超时触发新的选举。内容：格式与日志复制请求基本一致，但不包含任何新的日志条目（可以理解为空日志的复制请求），同样会携带 leader 的term和commitIndex投票请求作用: 竞选leader内容: 等待150ms-300ms随机时间过期后为自身term+1,给自己投一票,然后向其他节点发送投票请求,多数派同意后变成leader成员变更请求作用: 动态增删节点,避免脑裂问题执行流程客户端向Leader发送请求Leader接受到请求,使用日志复制将数据同步到Follower多数派Follower处理完成响应给LeaderLeader收到多数派响应,修改自身CommitIndex,返回响应给客户端Leader等待下次心跳包进行同步提交信息如果在同步提交信息前挂掉了怎么办?此时Follower变成Candidate进行选举,注意,只有日志与多数派相同的Candidate才会被选举为Leader新的Leader当选,任期+1,立刻触发日志同步步骤如下向所有follower发送包含自身日志信息的同步请求（基于nextIndex初始化值）当follower返回响应时,NewLeader会通过matchIndex记录每个follower已复制的最大日志索引当NewLeader发现某条日志的matchIndex已满足多数派已复制（即超过半数 follower 的matchIndex≥该日志索引），就会直接将自己的commitIndex更新为该日志索引此时之前Leader未同步提交的信息将会被标记提交Reference[]: http://www.kailing.pub/raft/index.html "Raft 算法动画演示"[]: https://chatgpt.com/ "ChatGPT"[]: https://www.doubao.com/ "豆包"
介绍There is only one consensus protocol, and that’s “Paxos” — all other approaches are just broken versions of Paxos—— Mike Burrows角色proposal(提议者),发起提案acceptor(接受者),决策提案learner(学习者),当提案被通过,会被学习者学习,学习者不参与提案的发起和抉择[!IMPORTANT]一个agent允许扮演多个角色提案一次提案通过多轮决策最终决定一个唯一值.每个提案均会有instance_id,下面用i代替每个agent均会带有promised_rnd: 已承诺决策ID,下面用prnd代替accepted_rnd: 已接受决策ID,下面用arnd代替accepted_v: 已接受决策值,下面用av代替传递的rnd不仅会有round_id,还会携带proposal的唯一标识实现理想情况假设现有4个节点(agent),其中A为proposal,BCD为Acceptorproposal A向BCD发送信息: i=1,rnd=(1,A)收到多数派返回结果: i=1,prnd=(1,A),arnd=0,av=nilA发现prnd和自己的rnd相同,因此开始Phase2,发送: i=1,rnd=(1,A),v="G"接收到多数派节点返回信息: i=1,arnd=1,av="G",prnd=1理想情况下提案结束.并发写冲突X向多数派BC发送: i=1,rnd=(1,X)X收到多数派返回: i=1,prnd=(1,X),arnd=0,av=nilY向多数派CD发送: i=1,rnd=(1,Y)Y收到多数派返回: C: i=1,prnd=(1,X),arnd=0,av=nilD: i=1,prnd=(1,Y),arnd=0,av=nilY查询多数派返回的prnd != rnd,rnd+1继续发送请求 i=1,rnd=(2,Y) 给BCY收到多数派返回: i=1,prnd=(2,Y),arnd=0,av=nilX此时进行Phase2发送请求: i=1,rnd=(1,X),v="G"B节点返回: i=1,prnd=(1,X),arnd=1,av="G" B节点更新成功C节点判断prnd!=rnd返回: i=1,prnd=(2,Y),arnd=0,av=nil C节点更新失败Y进行Phase2发送请求: i=1,rnd=(2,Y),v="J"Y收到多数派返回: i=1,prnd=(2,Y),arnd=2,av="J"此时X重新进行Phase1,由于上面被拒绝,这次rnd增加为3,发送请求: i=1,rnd=(3,X)X收到多数派返回:B: i=1,prnd=(3,X),arnd=1,av="G"C: i=1,prnd=(3,X),arnd=2,av="J"X发现多数派响应中,有两个接受的值,av="G" av="J"因此,这次不能写入自己的值,而是进行修复.由于C节点的arnd最新,考虑到paxos算法的约定: 只接收rnd大于自己的请求,如果av="G"已经被多数派确认,那么av="J"一定不会被写入. 所以将av="J"确定为要修复值X向BC节点进行Phase2请求: i=1,rnd=(3,X),v="J"X接收到多数派响应: i=1,prnd=(3,X),arnd=3,av="J"提案结束最终值J被确定极端情况--rnd无限提升X向BC发送i=1,rnd=1X收到多数派成功返回Y向CD发送i=1,rnd=1失败(这里没画出来),提升rnd后发送i=1,rnd=2Y收到多数派成功返回X向BC发送i=1,rnd=1,v="X",B节点成功,C节点失败X提升rnd,向BC发送i=1,rnd=3,收到成功响应Y向CD发送i=1,rnd=2,v="Y",D节点成功,C节点失败Y提升rnd .....无限重试...Muti-Paxos将多个提案的Phase1合并到一个请求中发送Fast-Paxos逻辑一步到位直接发送Phase2请求,其中rnd=0,这样可以保证冲突时安全退回,因为classic-paxos的rnd一定>=1如果Fast-Paxos冲突,退化到Classic-Paxos处理为什么增加多数派数量引用xp大佬的图除X,Y外,中间五个节点从左到右命名为ABCDEX使用rnd=0占用了ABC.因为rnd同为0,Y只占据了DE.Y退化至classic-paxos.此时CDE的arnd都为0,Y无法判断哪个值被多数派接受,如果选择CDE则最终值为y0,但实际x0为多数派接受.此时应当修改多数派从n/2+1改为n*(3/4)+1,这样接受X的多数派数量为4个,Y不论如何去选都至少有两个节点av为x0,通过至少两个节点有相同的值Y可以确定被接受的值.Reference[]: https://blog.openacid.com/algo/paxos "可靠分布式系统-paxos的直观解释"[]: https://www.doubao.com/ "豆包"[]: https://github.com/Trekkiii/paxos_raft_protocol "paxos_raft_protocol"