豆博客 - 算法
type: channel
link: https://www.douboke.cn/category/%E7%AE%97%E6%B3%95/
items: 分布式事务几种方案
items: 推荐算法--基于物品的协同过滤
items: gossip协议
items: Raft算法
items: Paxos算法

分布式事务几种方案
type: item
date: 2026-02-16T01:26:00+08:00
description: 在了解方案前先了解一下几个理论理论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一块). 如果拿锁失败则继续尝试, 超出尝试范…

推荐算法--基于物品的协同过滤
type: item
date: 2026-01-18T18:47:00+08:00
description: 基于物品的协同过滤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]…

gossip协议
type: item
date: 2025-08-31T22:01:00+08:00
description: 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对比本地数据,增量推送(包含k…

Raft算法
type: item
date: 2025-08-24T21:07:00+08:00
description: 前置请先看完 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/ "豆包"

Paxos算法
type: item
date: 2025-08-24T18:56:00+08:00
description: 介绍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…