增量计算目标
增量计算只重算新增数据和被影响的旧结果,复用未受影响的历史计算。它适合数据变化小而全量重建昂贵的任务,本质是在正确性前提下缩小计算波及范围。
主题对照
从全量重算转向增量维护:变化怎样传播、结果缓存与复用条件、物化视图的维护成本、Percolator 式快照与提交、观察通知与传播阈值,以及省计算为什么不等于省延迟。
增量计算只重算新增数据和被影响的旧结果,复用未受影响的历史计算。它适合数据变化小而全量重建昂贵的任务,本质是在正确性前提下缩小计算波及范围。
变化传播从新增数据出发,计算直接影响,再沿依赖关系继续扩散,直到影响收敛。Percolator 和 Kineograph 属于这一类,适合准实时更新和依赖图清晰的系统。
复用旧Map结果能省资源,但Shuffle、Reduce、调度与缓存读取仍可能主导关键路径。并行Map省去大量总工作也不一定同幅缩短作业完成时间,反之也不能据书中某组10%以内实验就断言所有增量MR都只能提升10%。收益依变化范围、可复用算子和瓶颈分布测量。
Percolator让局部变化较快影响索引,MapReduce仍适合全局统计。更新时效提升来自计算与依赖范围变化,不是通知机制自动改进搜索相关性,也不能由历史100倍更新周期直接推断所有任务都提速100倍。数据规模不大时还应比较普通数据库事务与作业方案的复杂度。
固定查询可先离线算出结果,再由在线存储低延迟返回;任意组合列、过滤和连接的查询则可能需要现场并行计算。预计算减少请求时开销,却要付出更新与维护成本。判断“实时”须区分返回速度和数据新鲜度:旧汇总读得很快,并不说明包含了最新事件。
可联系[[基线冗余与增量连接折衷]]理解条件与边界。
分区期间允许多个副本独立更新,就必须为恢复后的状态定义合并规则。单一总数可能不足以辨别共同历史,需保留能够正确合并的状态,例如只增计数的分量。
批处理重算能接替出错的临时视图,前提是原始输入仍完整、批处理逻辑及发布正确。它不能追回已经发生的外部副作用,也不能保证任何实时错误都会无条件自动消失。
结果缓存复用从“不变的旧结果”出发,把上一轮中间结果以指纹缓存起来。下一轮改写计算 DAG,命中缓存的节点直接复用,适合批处理平台上的周期性重复任务。
Hadoop增量框架可保留旧数据的Map中间结果,仅为新增数据重新执行Map,再把新旧结果送往Reduce。前提是旧记录的Map输出不受其他新记录影响,且Map代码、参数和外部依赖仍兼容;Map若读取变化的全局模型就不能盲目复用。删除与修改旧记录时也要撤销或替换旧贡献,不能只追加新贡献。
为提高增量复用率,先把新增或变化记录从可复用旧数据中分离,再按原分区规则保存与调度Map输出给对应Reduce。若输入块混有大量旧数据,块级变化会扩大重算。缓存中间文件后还要改造抓取位置和调度,不能仅跳过Map任务却让Reduce继续等待不存在的本地文件。
DryadInc用缓存服务器保存计算结果并以指纹定位,Rerun Logic识别可复用子图后改写DAG。安全复用还要求对应输入、程序和配置语义未变;指纹相等只是依据之一,不能用缓存存在代替依赖校验。原文80%~90%是特定工作负载结果,不作为任何DAG任务的固定提速承诺。
跨地域写入不必等待所有副本同步确认;复杂连接或聚集查询则不能简单丢到后台让用户反复轮询。PNUTS用异步维护的实例化视图预先重组/聚合数据,让用户请求以较低延迟读取可接受稍旧的结果。设计时要区分可异步传播的后台更新与必须立即响应的查询路径,而不是把“昂贵”一概等同于“异步”。
跨分区连接或全表聚集若放在用户请求中同步执行,会占用多台服务器并拖慢页面;若改成纯异步查询,又会迫使用户反复检查结果。对可预见的查询模板,可在后台异步维护实例化视图/索引,让请求同步读取预先组织的数据;前提是应用能容忍视图暂时过期,且维护成本不拖慢主读写。
预计算结构能加速读,但如果维护视图抢占主请求资源、增加同步读写延迟,或因资源不足长期积压而变得过期,就可能失去价值。评估物化视图时要同时量维护成本、读取收益和可接受陈旧度,并限制预连接等高开销更新。
应用注册关注列及观察者,Worker扫描变更提示并触发事务,事务写入其他列可继续触发后续观察者,形成依赖变化传播。该结构替代周期全量重算的部分局部工作,不自动决定业务依赖或避免循环。通知、事务状态与外部副作用的边界需分别定义,不能把每次函数调用都当完成提交。
Percolator原论文说明,一个受观察列的多次写入可合并为一次观察者执行;事务性ack列用于限制同一变更的重复提交,notify列只是扫描提示。它适合根据最新状态重新处理的任务,并非保证逐业务事件各执行一次的消息队列。若每条变更都有独立计费意义,必须另保事件事实,不能用可合并通知代替。
Kineograph接收节点把输入转成带序号的图更新事务,图节点维护图结构、应用数据和邻接关系;快照器按进度组织可计算版本,再触发增量图计算。更新维护与图挖掘分离,避免把正在变化的各节点内存随意拼成一个版本。流输入不表示每条到达立即形成全局计算快照。
Kineograph接收节点汇报已完成更新进度,Progress Table记录序列号向量供Snapshooter确定快照边界。向量表达分布式输入流的处理进度,不能简单取最大序号当所有来源已完成。快照是后续计算的版本基础,逻辑时钟不等于墙钟时间或“最新一条消息”的单一标量。
Kineograph比较新旧快照及邻居传来的变化,调用用户函数更新受影响节点;新值变化达到条件时再通知邻居。阈值能减少传播,却可能引入近似误差,依赖规则与收敛条件而非永远精确。对于变化会扩散到全图的任务,也不能仅因输入很少就保证重算范围小。
本书所说的实时计算侧重增量处理:数据持续到来,系统尽快处理新增部分,不等大量数据积累后再统一分析。它是一种应用方式,而非某个产品名称。发散:设计时要说明“尽快”对应的延迟目标和数据量;不能把这里的实时直接理解为严格的硬实时保证。参见 [[离线计算先存后分析]]。
历史数据达4 EB、每分钟新增5 TB时,周末全量扫描难以承担。把相关性检查放在新数据进入目录时,以持久上下文做增量判断,可避免反复重扫全部存量;案例强调处理时机与数据规模的关系。
Percolator在Bigtable单行事务与多版本数据上实现跨行跨表的快照隔离事务,再用观察/通知把列变化触发为后续事务,支持索引局部持续更新。快照隔离防写写冲突但不等于可串行化,通知也可以合并,不能据“ACID”推断任意业务不变量或每次列写都独立调用一次。
Percolator以start timestamp读取一致版本,并排除并发写同一Cell的写写冲突。它提供快照隔离而非可串行化,仍可能写偏;“ACID”不能替代对具体业务不变量的分析。原文把锁行后一概阻塞所有读写说得过满,旧快照读取和冲突锁等待必须按版本范围判断。
张三余额10元、李四2元,转7元应得到3元和9元,总额仍12元。若先扣张三再加李四却无跨行原子边界,扣款后崩溃会使后一步未执行,总额变为5元。根因是一个资金转移被拆成可独立对外成功的两次写入,单行事务无法保护跨账户守恒;不是加一个重试就自然修复。
相关方案:[[ch17-011-主记录提交保护转账原子性]]。
Percolator先在start_ts写两账户新值与锁,secondary指向primary;预写完成后在新commit_ts原子替换primary锁为write记录,这是提交决定点,再完成secondary写记录与解锁。读者通过write记录指向数据版本,遇残锁依据primary状态恢复,避免把半完成预写当已提交转账。它保护该事务两行原子性;余额非负、隔离异常和业务重试幂等仍须各自处理。
相关问题:[[ch17-010-两步转账中断会破坏总额]]。
Percolator的data列在开始时间戳保存新值,write列在提交时间戳保存指向data版本的记录,lock列保存未决写与primary位置。先写data不等于立即对其他事务可见,读取应根据已提交write定位版本。这三个逻辑角色把值、可见性和恢复决策分开,不能只看最大的data时间戳读取余额。
secondary锁带primary位置,是为了在故障后统一判断事务结果。primary尚未提交可在同步检查后回滚,primary已被提交记录替代则必须前滚secondary,不能一概清锁丢弃新值。提交与清理在primary行事务上竞争,避免把仍活跃的提交错误回滚。此恢复细节由原始论文补充,不能按书中“清除主锁”一句简化。
读事务以start_ts为可见边界,选择不晚于该边界的最新write,再取它指向的data版本;只有影响该快照的未决锁才需要等待或协助清理。读旧快照不必因同一行存在任意较新写锁就全部阻塞。这个规则依赖Percolator事务API,直接绕过协议读Bigtable原列不获得同样保证。
点击箭头逐层展开,点击卡片标题查看详情。路径上下文仅用于连接层级,不计入主题卡片数。
来源书籍
书籍类型:未标注
424 张卡片
来源书籍
分布式系统类
书籍类型:经典原理
类别清单尚未核对
173 张卡片
来源书籍
书籍类型:经典原理
331 张卡片
来源书籍
分布式系统类
书籍类型:工程实践
清单覆盖 2/6
97 张卡片
来源书籍
数据科学实践类。全书虽为多作者案例集,但整体围绕真实数据项目的定义、获取、清洗、分析、建模、呈现与治理,符合端到端数据科学实践的判定范围。逐项对照必答维度:
书籍类型:未标注
类别清单尚未核对
229 张卡片
与 1 张主题卡片存在结构化链接;来自相同书籍;属于相同分类
与 1 张主题卡片存在结构化链接;来自相同书籍;属于相同分类
与 1 张主题卡片存在结构化链接;来自相同书籍;属于相同分类
与 1 张主题卡片存在结构化链接;来自相同书籍;属于相同分类
与 1 张主题卡片存在结构化链接;来自相同书籍;属于相同分类
与 1 张主题卡片存在结构化链接;来自相同书籍;属于相同分类