知识卡片
Storm acker框架:用异或校验值追踪消息完整处理
流式系统要保证”一条消息进入系统后确实被完整处理完”,最直白的做法是给每条消息维护一棵完整的”衍生消息树”(一条消息可能衍生出多条新消息,新消息又可能继续衍生),跟踪树上每个节点是否都处理完了——但这样每条消息都要占用大量内存记录整棵树,代价很高。Storm的acker框架用了一个精巧得多的办法:不需要保存树的结构,只需要给每个Spout发出的原始Tuple维护一个初始值为0的64位校验值(ack-val),每当任意一个Bolt发射或接收一条Tuple,就把这条Tuple的64位唯一ID和当前校验值做一次异或运算。异或运算有一个关键数学性质——同一个值异或两次会互相抵消归零,这样只要每条派生消息在”被发射”和”被接收确认”两个环节都各参与一次异或,当整棵衍生树上的所有消息都被完整处理一遍后,所有ID的异或贡献会两两抵消,校验值必然精确变回0,从而不需要保存任何树形结构就能判断”这条原始消息的整条处理链是否已经走完”——每条消息平均只需要约20个字节就能完成追踪。如果等待一段时间校验值仍不为0,acker就认定消息丢失或处理不完整,通知Spout重新发送——由于重发可能导致同一条消息被处理多次,这决定了Storm实现的是”at least once”而非”exactly once”语义。可迁移启发:当需要追踪一组动态生成、结构不固定的关联事件是否”全部完成”时,如果每个事件都有全局唯一ID,用异或(或其他自反运算)折叠成一个定长校验值,往往比维护完整的关联结构树更省内存,代价是只能判断”整体是否完成”,无法追溯具体是哪个节点没完成。
结构图:
flowchart TB
A["Spout发射tuple1(ID=0011)<br/>acker记录ack-val=0011"]
A --> B["Bolt1收到tuple1,产生tuple2(ID=0100)<br/>发送(tuple1 XOR tuple2)给acker<br/>ack-val = 0011 XOR 0011 XOR 0100 = 0100"]
B --> C["Bolt2收到tuple2,处理结束(无新Tuple)<br/>发送tuple2 ID给acker<br/>ack-val = 0100 XOR 0100 = 0"]
C --> D["ack-val归零→tuple1被完整处理<br/>(超时未归零→acker通知Spout重发,实现at least once)"]
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
原书出处
参考来源
- 位置:《大数据技术体系详解:原理、架构与实践》第13章《流式实时计算引擎》之"13.2.3 Storm内部原理"(源文件:_epub-src/OEBPS/text00104.html)
- 结论依据:原文说明"Storm不需要为每个消息保存整棵消息树,单个消息只需要约20个字节进行追踪即可知道是否被完整处理完……为每个Spout Tuple保存一个64位校验值,初始值为0……每当Bolt发射或接收一个Tuple,该Tuple的ID……跟这个校验值进行异或操作……如果每个Tuple都成功处理完了,则校验值变为0……如果一条消息在一定时间内未处理完……则由acker通知Spout重新发送数据……因而Storm实现了'at least once'一致性语义", 直接支撑本卡关于acker框架异或校验机制的结构图。
- 原始内容:正是由于消息可能会被Spout发出多次,因而Storm实现了"at least once"一致性语义。