此笔记位置已失效,请从目录继续阅读。
全书导读
本书从大数据的处理难题出发,依次解释分布式数据放在哪里、节点如何达成与维护状态、如何组织存储和计算,以及如何在这些基础之上完成图分析和机器学习。它适合作为2014年前后系统架构与算法的整体地图:原理的价值在于问题、假设和权衡,产品状态、硬件数值及未来预测需保留原书时间坐标。
全书主线
第0章建立业务目标和技术全景;第1–5章讨论分片路由、复制一致性、常用算法与数据结构、资源管理及协调;第6–7章解释构件如何通信、日志与数据变化如何流动。第8–10章进入文件、内存KV及列式数据存储,第11–13章把批处理、流处理与交互查询作为不同执行需求;第14章展开图计算,第15–16章讨论机器学习架构和分布式算法,第17章收束到增量计算。
系统没有脱离条件的万能保证:复制数量不独立决定可用性,序列化不消除远程失败,日志传递不自动使两个数据库处于同一事务,图及数值算法也必须保持输入和终止条件。附录A提供硬件数量级估算,附录B解释经典工作的贡献并补充真实secondary出处;不把重复点评另造同义卡。
内容简介
内容简介将本书定位为2014年前后大数据系统架构和算法的技术梳理,贯穿数据分布、一致性、存储、计算与分析。应按问题及实现条件理解各方案,不能把当时的产品状态和市场评价当作当前事实。
前言
前言从数据规模增长和系统技术演进引出写作目标:用整体框架串联分布式系统及分析算法,再进入具体架构。它强调读者应理解各方案所解决的问题。推荐和感谢属于出版背景,既不能当作技术正确性的证明,也不为市场赞誉单独成卡。
第0章 大数据概述
大数据的困难与工具能力、处理时限及任务有关,体量之外还要看产生速度和数据形式。原文Velocity与Variety标签对调,单位与早期增长统计亦需限定。处理主线从收集清洗经过存储、分析到可视化,业务目标决定如何组织多源信息。伦敦眼、Netflix、Watson及金融情绪实验展示不同用途,案例的样本和历史条件限制了可推广结论。
大数据是相对于既有工具与资源难以在可接受时间内有效存储、管理和处理的数据集合,而不是跨过固定PB数就自动成立。同一体量在不同任务、时限与设备上可能有不同困难。先识别数据来源、结构、增长和处理目标,再判断应改变架构、算法还是资源。原书2010年代的数据规模用于说明背景,不作为当前平台统计。 见大数据取决于处理能力边界。
Volume描述体量,Velocity描述产生、到达和处理的速度,Variety描述结构与来源的多样性。原书把后两者英文标签对调,应按含义纠正;Value是关注价值的补充视角,不能据此认定所有机构都使用唯一四V定义。还应区分十进制kB与二进制KiB,原书1024逐级换算属于二进制习惯,不能混作统一SI单位。 见区分数据规模速度与形式。
异质原始资料经过收集、清洗、存储管理、分析挖掘和可视化,才成为用户可理解并使用的信息。存储解决保存与访问问题,不能替代领域分析;可视化也不能挽救错误样本或推断。图0-1是职责流程,具体系统可以流式、迭代或交错执行,并非必须按固定产品串接。 见数据流水线连接原始资料与知识。
技术体系既包括分布式存储和计算,也包括把作业与资源协调起来的调度、通信与协调服务,以及收集、监控和工作流等支撑能力。图0-2提供2014年生态的定位图,适合按职责理解依赖;不能从图中产品名称推出今天唯一正确的技术栈,也不能认为引入NoSQL就完成了分析平台。 见存储计算调度共同支撑分析。
关系型数据库与NoSQL在数据模型、访问路径、一致性、事务、扩展和运维上提供不同取舍。互联网业务同样可能要求严格正确性,NoSQL也不都放弃事务;不能按行业名称把一致性需求一刀切。原书关于并行数据库最多扩展百台的比较是当时背景下的泛化,不作为普遍上限。 见存储选型依据工作负载。
伦敦眼案例把与奥运有关的Twitter消息筛选出来,用SentiStrength等情绪分析将文本分类,再按类别比例驱动灯光展示。这是数据收集、模型输出与可视化相连的项目案例。颜色比例反映被采集并被分类的消息,不能直接当作全体英国民众的真实情绪;讽刺、样本偏差与分类误差都会影响解释。 见情绪展示取决于采样与分类。
Netflix案例把用户评分、观看及搜索等行为与内容信息结合,用于推荐和业务决策。它说明数据价值来自围绕明确目标组织信号与反馈,而非仅保存更多记录。原书给出的市场份额和商业效果保留2010年代案例坐标,不能单凭相关增长证明某一算法造成全部收益。 见推荐系统组合多源行为信号。
Watson问答案例先识别问题类型和焦点,分解复杂问题,再检索生成候选答案,用多种证据评分并综合排序。它展示检索、语言分析及统计判断的协作,海量知识库本身不等于正确回答。这里只描述2011年竞赛系统及书中机制,不把当时医疗商业化展望当作当前临床能力。 见Watson组合候选生成与评分。
情绪与股票方向预测的历史实验,必须分别看数据样本、预测对象、验证方法和最终交易结果。原书引用87.6%的方向准确率,不能据此推导基金利润、稳定套利或未来表现。已核原论文摘要的对象是特定实验中的DJIA每日涨跌方向;收益还受交易规则、成本、风险和样本外失效影响,本卡不提出投资行动。 见方向预测准确率不等于收益。
按需租赁存储和计算,可让早期业务用较少固定投入启动,并随负载扩张资源。资源供给灵活不等于应用能自动扩容:状态、分区、并发和成本边界仍需设计。原书云平台案例说明商业供给方式,不保证任何工作负载上云后都更便宜或更可靠。 见云资源弹性需要应用配合。
商业生态段以Dropbox的文件同步与共享、Zillabyte的企业分析工具和Decide.com的消费价格趋势分析说明,大数据价值最终要落到具体用户服务。这些例子只简介产品用途与当时增长,没有解释同步协议、预测算法或给出足以复现的效果证据;本轮将其保留为整书笔记中的应用背景,不凭市场赞誉造技术机制卡。
第1章 数据分片与路由
本章围绕数据分片与路由展开。先把数据归属和物理放置拆开,再比较取模、虚拟桶、环路由与有序范围;扩展和副本容错分别设计。
分片可以拆成key到逻辑分片、分片到机器两层映射:前者决定记录归属,后者决定物理放置。两层独立维护时,扩容可在记录归属不变的前提下迁移选定分片;仍需真实搬运数据并更新路由,不能只修改表项就完成在线迁移。 二级映射分片
虚拟桶把“数据分片”从“物理机器”中抽离出来,新增机器时只调整桶到机器的映射表。它牺牲一层路由查表,换来平滑扩容和负载再均衡,和[[二级映射分片]]是同一思想。 虚拟桶解耦。一致性哈希把节点和数据放在同一哈希环上,节点增删只影响相邻区间的数据迁移。它解决取模哈希扩容时全量重排的问题,但仍需虚拟节点或负载策略缓解分布不均。 一致哈希迁移。取模分片H(key)=hash(key) mod K把机器数直接写进归属函数。K变为K+1后,大量key会映射到其他机器,需要重分布;原文“所有数据”是整体重新计算的描述,并非每条记录一定换位置。书中称Round Robin,此处实际机制是哈希取模,不应与按请求轮转混同。 取模扩容改变归属。Chord为节点保存按2的幂距离寻找后继的Finger Table,查询时向环上最接近目标且未越过目标的已知节点转发,最终由目标哈希的后继节点负责。N14查27可经N25到N29;跨0边界应按环区间比较,不能照搬普通整数大小条件。路由表是加速索引,不是数据副本。 指表跳跃定位后继。新节点先设置已知后继,周期稳定检测再询问后继的前驱、修正后继并通知新的邻接关系。N8加入N5与N14之间后,N14先改前驱,再由N5改后继,相关区间数据迁往N8;Finger Table还需独立刷新。它说明逐步修复过程,不保证任意并发故障下仅跑四步就原子完成迁移。 稳定检测修复邻接。一个物理节点可在哈希环上占据多个位置,减少单次随机落点造成的不均衡,并让不同配置机器承担不同份额。虚拟节点增加的是逻辑分片数量,并不自动增加独立故障副本;仍需核对物理放置和热点key,不能把均匀哈希等同业务负载绝对均衡。 虚拟节点适配异构机器。正常离环可交接数据并更新邻接;异常离环可能连同本地数据一起失去,路由稳定检测只能寻找可用节点,不能凭空恢复内容。需预先在其他物理节点保存副本,并处理故障检测和接管;分片扩展与副本容错是不同职责。 故障离环依赖副本
范围分片按key的有序区间切分,利用边界映射定位分片,便于点查和跨区间顺序扫描。哈希分片通常打散原始key顺序,范围查询需额外扫描或索引;不能因此说所有点查业务都必然适合哈希。热点区间的分裂、迁移属于进一步工程处理,不是排序自动提供的保证。 范围分片取舍
第2章 数据复制与一致性
本章围绕数据复制与一致性展开。先明确业务不变量、可见性及故障条件,再选择更新与提交协议;共识的安全、进展和原子提交不能互相替代。
CAP 不是给系统贴 AP 或 CP 标签,而是在网络分区出现时识别分区、进入明确的限制模式、恢复后修补状态。工程上应把取舍落到子系统、数据类型和运行阶段,而非全局二选一。 CAP细粒度化。BASE强调基本可用、软状态和最终一致性,允许副本在一段时间内不一致。最终一致性描述在停止新增更新且传播修复持续进行等前提下最终收敛,本身不保证固定时限;原书“给定时间窗口”需结合系统额外承诺理解。选择时要明确冲突、失败和补偿语义,也可在局部保留ACID事务。 BASE的代价。ACID的一致性指事务前后维持定义的业务不变量,CAP的一致性通常指线性一致的单副本行为。二者不能直接画成包含关系,也不能推出网络分区后业务规则必然破坏:拒绝部分请求或使用适用的协调与约束仍可保持规则。日志和补偿只是可选恢复机制,不能自动修复所有不变量。 ACID与CAP的C。分布式调用可能“成功执行但响应丢失”,客户端会重试同一请求。幂等操作让多次执行与一次执行效果相同,把网络不确定性转化为可接受的重复消息,是可靠接口的基础。 幂等吸收重试。两副本断联时,一边完成更新,另一边若继续返回旧值,就无法保持线性一致;若等待或拒绝相关操作,则放弃该操作的CAP可用性。CAP讨论分区条件下的保证,并非平时只能任选两项,也不是性能百分比。单份数据亦不自动等于正确并发语义,原书的推演只突出可达性冲突。 分区取舍限定操作。转账分为A扣款和B入账,若扣款后失败而入账未发生,总额就减少,业务结果不再符合两账户金额守恒。问题来自一笔业务操作被拆成可独立成功的步骤,不能靠重试整笔转账就安全修复,重试还可能重复扣款。对应约束见[[转账使用原子事务]]。 转账半成功破坏守恒。在同一受支持的事务范围内,把A扣款、B入账以及相关不变量校验作为一个整体,成功则全部提交,失败则回到事务前状态。它回应[[转账半成功破坏守恒]];跨服务或外部支付不能仅加一个本地事务就获得同样保证,重试标识、隔离和结果查询仍需设计。本书提供的是原子性算例,并未给出真实支付实现。 转账使用原子事务
一致性模型约束观察顺序与可见性。线性一致让已完成写在后续读中可见;最终一致允许传播窗口,读己之写、单调读、单调写、因果一致则分别增加不同约束。原书图2-4是简化分类,不宜把所有会话保证严格视为最终一致的子集,也不能把“强一致”与所有文献中的严格一致性等同。 一致性谱系。读己之写保证本进程后续读能看到自己的更新;单调读防止已看到的版本倒退;单调写约束同一进程写入顺序。会话结束后某些保证可能不延续,要按客户端迁移规则理解。它们可组合,却不自动保证其他客户端看到相同最新值,也不代表物理时钟排序。 会话保证各有观察范围
把同一更新同时发给所有副本,并不能让并发更新自动按同一顺序执行。需先用协议确定命令顺序,或明确定义版本冲突与合并规则。协议带来通信成本;先定义要提供的读写语义,再选择副本更新方式,不能以“广播过了”证明一致。 副本更新先确定顺序。主副本可统一写入顺序,同步所有副本会受慢副本制约;先确认再异步传播可降低等待,但故障时可能丢失尚未复制的已确认更新。只读主副本可避免普通复制延迟的旧读,却仍需正确的选主与持久化规则。同步、异步、部分同步不能单凭名称推出线性一致。 主副本确认决定取舍。无固定写主时,不同客户端可同时由不同副本接收同一key的更新。通知其他副本只是传播,还需版本与合并策略处理并发冲突。Dynamo中的协调节点不等同长期主副本;原书把Dynamo等概括为主从故障切换的表述过粗,不能据此推断实现。 任意节点写须处理冲突
固定N副本集合中,成功写入W份、读取R份且R+W>N,保证读写集合相交。交集本身不能单独证明线性一致:还需版本选择、并发写、未完成写、读修复及成员变更规则。增加R或W会改变延迟和故障容忍度;Dynamo的sloppy quorum还可能用临时替代节点,不能把简单交集公式当其全部保证。 仲裁读写权衡。向量时钟给每个进程维护一个记录所有进程逻辑时钟的整数向量,通过发消息、收消息、内部事件时的更新规则,让系统能判断两个事件是因果相关还是并发无关,而非只有全序时间戳。 向量时钟判因果。2PC先收集所有参与者的准备票,再持久化并传播全局提交或中止决定。协调者等待投票可超时中止;已投赞成票的READY参与者却不能仅凭超时自行中止,因为其他参与者可能已提交。互询可获知既定结果,但若可达参与者都处于READY且协调者不可达,仍可能阻塞;等待消息不等于所有状态都具有相同的不可决风险。 2PC阻塞态脆弱。Paxos靠Prepare和Accept两阶段、多数派确认来在非拜占庭环境下选出唯一倡议值:倡议者拿到多数接受者对高编号Prepare的响应后,必须沿用其中编号最高的已接受值而非随意赋新值,从而保证安全性。 Paxos两阶段选值。Raft用递增任期区分领导者时期,拆分领导者选举、日志复制与安全规则。它采用强领导者组织日志复制,以减少状态空间并便于实现;Paxos也可采用领导者,不能把二者区别简单归为P2P对主从。安全性需完整的投票、日志匹配和提交规则,原书结尾笼统称其仍有安全漏洞不能作为Raft协议结论。 Raft用任期简化。2PC准备阶段让每位参与者确认能否提交;所有参与者及协调者同意才作出全局提交,否则全局中止。决定须可靠保存并被参与者恢复读取,准备成功不等于事务已经提交。它解决原子提交,不单独提供隔离或线性一致,也不能把Raft多数复制直接称为2PC。 准备票约束最终决定。参与者已投赞成票后,超时只说明不知道决定,不能证明应中止。可向其他参与者查询已提交或已中止的可靠状态;若大家仍为READY且协调者不可达,就没有足够信息擅自决策。恢复时应根据持久日志重建状态,单纯设置更短超时无法消除这个不确定窗口。 准备后超时不能自行回滚。3PC在准备与最终提交间加入预提交,试图让参与者依据所处阶段推断后续动作。其非阻塞结论依赖通信与故障模型,不能推广为任意网络分区下都安全且持续可用;增加阶段也增加消息和恢复复杂度。原书仅给状态图,不足以成为生产实现协议。 预提交不消除所有分区。每个进程记录各进程已知计数;本地事件递增自己的分量,发送附向量,接收逐项取最大并计入本次接收事件。比较两向量:各分量不大于且至少一项小于代表happened-before;两者互不支配就是并发。[2,4,3]与[3,3,3]不可比较,不能按分量和判断新旧。 向量比较识别并发。Dynamo读取到版本时,用向量时钟淘汰被因果覆盖的旧版本;D3与D4互不覆盖则保留为并发分支,由应用按业务语义合并。合并写需携带综合上下文,使新版本覆盖已解决的分支;不能随意丢掉其中一支再声称一致。裁剪时钟亦可能损失因果信息。 并发版本交给业务合并。状态机复制让各服务器按同样顺序执行同样的已提交命令,从而在确定性执行前提下得到相同状态。共识负责日志选择,应用仍需处理外部时间、随机值及副作用的确定性与重试。单Paxos解决一个槽位,多槽位日志需要协议组合和恢复,不能以复制文件相同替代提交规则。 复制日志驱动确定状态机。Paxos接受者接受某提议只是局部事实,获得符合规则的多数接受才选定。学习者需要收集足够确认,不能收到单个接受消息就宣称已决议。直接通知所有学习者消息较多,代表转发降低消息量但需冗余代表避免单点;角色可在同一进程兼任。 已接受不等于已选定。Paxos的提议编号、承诺和已接受值需要跨重启保持,才能避免忘记旧决定。多个提议者不断提高编号可互相打断而没有进展,选稳定提议者并最终能联系多数才有利于完成;不推进不等于选出冲突值。非拜占庭模型也不是靠校验和就能解决恶意行为。 安全与进展分别保证。Raft跟随者超时后递增任期、给自己投票并请求其他服务器;同任期每台至多投一票,多数才当选,随机超时减少反复分票。投票还要比较候选日志末项任期及索引,防止缺少已提交历史者当选。超时是怀疑领导者失效,不是它已死亡的证明。 随机选举还须日志够新。Raft领导者只能通过多数副本计数直接提交当前任期的条目;当前任期条目提交后,先前日志前缀随日志匹配性质间接提交。旧任期条目即使暂存多数也不能单凭此计数判定安全。复制、提交、应用是不同阶段,不能把本地追加成功当客户端操作已完成。 提交当前任期保护旧日志
原书依据 · 29 处
- 数据复制与一致性 · 查看原书依据
- 数据复制与一致性 · 查看原书依据
- 数据复制与一致性 · 查看原书依据
- 数据复制与一致性 · 查看原书依据
- 数据复制与一致性 · 查看原书依据
- 数据复制与一致性 · 查看原书依据
- 数据复制与一致性 · 查看原书依据
- 数据复制与一致性 · 查看原书依据
- 数据复制与一致性 · 查看原书依据
- 延伸阅读 · 查看原书依据
- 数据复制与一致性 · 查看原书依据
- 数据复制与一致性 · 查看原书依据
- 数据复制与一致性 · 查看原书依据
- 数据复制与一致性 · 查看原书依据
- 数据复制与一致性 · 查看原书依据
- 数据复制与一致性 · 查看原书依据
- 数据复制与一致性 · 查看原书依据
- 数据复制与一致性 · 查看原书依据
- 数据复制与一致性 · 查看原书依据
- 数据复制与一致性 · 查看原书依据
- 数据复制与一致性 · 查看原书依据
- 数据复制与一致性 · 查看原书依据
- 延伸阅读 · 查看原书依据
- 数据复制与一致性 · 查看原书依据
- 数据复制与一致性 · 查看原书依据
- 数据复制与一致性 · 查看原书依据
- 数据复制与一致性 · 查看原书依据
- 数据复制与一致性 · 查看原书依据
- 数据复制与一致性 · 查看原书依据
第3章 大数据常用的算法与数据结构
本章围绕大数据常用的算法与数据结构展开。按成员过滤、有序内存索引、顺序写与合并、差异定位、压缩和冲突安置六类用途理解数据结构,同时保留概率与恢复边界。
布隆过滤器用多个哈希函数和位数组判断成员是否可能存在。它允许误判存在但不误判不存在,适合在磁盘访问前快速过滤无效查询,用少量内存换掉大量随机 I/O。 布隆过滤器。位数组m、预计成员n和哈希数k共同影响误判。理想独立均匀哈希下,p约为(1-exp(-kn/m))^k,最优k约(m/n)ln2,反算m约-n ln(p)/(ln2)^2。先估成员上限和允许误判,再取整数k与足够位数;这是近似模型,超量插入和偏斜哈希会改变实际效果。 布隆参数按误判预算算。将位改成小计数器,插入递增、查询看是否均非零、删除递减,允许删除真正插入过的成员。不能仅凭一次可能误报的查询就减计数,否则可能给其他成员制造漏判;还需处理重复插入及计数溢出。空间代价是每个位置使用多位,三四位只是原书示例。 计数过滤删除须有依据。SSTable的布隆过滤器若判不存在,可在构建正确且无不当删除前提下跳过该文件;若判可能存在,仍要读取真实数据确认。误判在此主要多一次I/O,不会变成伪造记录。不能用相同的可能存在结果直接拒绝支付请求或当作交易已完成的事实。 预过滤后仍查真实记录
SkipList 用随机层级给有序链表增加远跳指针,平均查找、插入、删除复杂度接近 O(logN)。它不需要复杂旋转,适合内存有序表,Redis Sorted Set 和 LevelDB MemTable 都受益于这种简洁性。 SkipList随机索引。跳表从高层向低层寻找key,沿途记录每层最后一个小于目标的前驱。插入时随机选层数,再改这些前驱的forward;已有key则更新值。删除同样按前驱数组跳过目标,最高空层回缩。原伪码中level与lvl等记号不完全统一,应按新节点实际层数理解,不直接照抄编译。 跳表更新保存各层前驱
LSM 树把随机写先落到内存和顺序日志,再批量合并成磁盘有序文件。它用读路径变长、后台合并和写放大,换取高吞吐写入;Bloom Filter 和缓存常用于弥补读损失。 LSM写读取舍。LevelDB写前日志记录待恢复的更新,MemTable提供内存有序访问;MANIFEST描述哪些SSTable有效及其层级、key范围,CURRENT指向当前MANIFEST。恢复需要内容日志和文件集合元数据配合。原书称LevelDB等价于BigTable子表服务器只是存储思想类比,单机引擎不包含整个分布式服务职责。 日志与表元数据分工。LevelDB的L0由内存表刷出,各文件key范围可能重叠;更高层的同层文件范围互不重叠。合并L0某文件时需纳入同层重叠文件,再与下一层重叠范围多路归并。不能仅按文件数判所有层的触发规则,原书是简化流程,实际还受层容量和读压力等机制影响。 零层重叠扩大合并范围。LSM删除先写墓碑,使读路径知道旧值已无效;刷内存表时不能直接去掉墓碑,因为旧值可能仍在其他层。合并清理必须确认不会让更老值复活,并保留仍被快照需要的版本。原书以minor和major解释过程,不同系统的术语与回收条件需分别核对。 删除标记延后清理
Merkle 树把数据块哈希逐层汇总成根哈希。两个副本只需比较树节点,就能快速定位少量不同的数据范围,适合副本修复、反熵同步和内容完整性校验。 Merkle定位差异。Merkle分支可把交易哈希逐层合成某区块头的根,证明的是交易被该根承诺的数据集合包含。它不独立证明签名、余额、无双花或区块所在链可信;原文把Prev Hash说成时间戳也不准确,它是前一区块头的哈希。轻节点验证还依赖工作量链和安全假设,不应将“最长”解释成人数最多。 包含证明不等于合法交易
压缩的核心不是永远追求最高压缩率,而是在 CPU、磁盘、网络之间重新定价。Snappy 选择较快压缩解压速度,适合 MapReduce 中间结果这类受吞吐和流水线延迟约束的场景。 压缩换传输。LZ77从已处理窗口中匹配后续输入,用距离与长度等信息代替重复文本;解码器从已解码前缀恢复,双方无需事先共享完整词典。LZSS增加字面量与匹配选择,短匹配若不划算就直接输出。示例AABBCBBAABC中BB可编码为距离3长度2,格式和最短长度属于具体方案参数。 滑动词典引用重复片段。为窗口片段保存哈希位置,可先定位候选,再比较实际字节延长匹配,避免逐位置完整扫描。Snappy按短固定片段寻找匹配,强调吞吐而非最高压缩率;原书32KB块和每次滑动4字节是历史实现概括,不能当格式永久规则或每次操作的精确描述。书中速度值亦非当前硬件基准。 匹配索引换压缩速度
Cuckoo Hashing 为元素准备多个候选位置,冲突时把旧元素“踢出”并递归安置。它让查询保持常数时间,但插入可能触发连锁迁移,空间利用率和重建策略决定稳定性。 Cuckoo驱逐冲突。SILT将KV追加到Flash,在内存保留标签和偏移以压缩索引;部分主键Cuckoo设计还让被驱逐项能定位另一候选桶,减少搬迁时读Flash。标签是候选匹配,真实记录仍需核对完整key。图3-15显示h1桶存h2标签、h2桶存h1标签,原书相邻文字把位置与内容写混,不能照其字面实现。 短标签索引仍需核验主键
原书依据 · 17 处
- 大数据常用的算法与数据结构 · 查看原书依据
- 大数据常用的算法与数据结构 · 查看原书依据
- 大数据常用的算法与数据结构 · 查看原书依据
- 大数据常用的算法与数据结构 · 查看原书依据
- 大数据常用的算法与数据结构 · 查看原书依据
- 大数据常用的算法与数据结构 · 查看原书依据
- 大数据常用的算法与数据结构 · 查看原书依据
- 大数据常用的算法与数据结构 · 查看原书依据
- 大数据常用的算法与数据结构 · 查看原书依据
- 大数据常用的算法与数据结构 · 查看原书依据
- 大数据常用的算法与数据结构 · 查看原书依据
- 大数据常用的算法与数据结构 · 查看原书依据
- 大数据常用的算法与数据结构 · 查看原书依据
- 大数据常用的算法与数据结构 · 查看原书依据
- 大数据常用的算法与数据结构 · 查看原书依据
- 大数据常用的算法与数据结构 · 查看原书依据
- 大数据常用的算法与数据结构 · 查看原书依据
第4章 集群资源管理与调度
本章围绕集群资源管理与调度展开。资源池化需要结合异质性、局部性、保障、抢占与隔离;架构决定决策分工,具体策略决定分配结果。
把集群静态分给不同计算框架实现简单,却会让某些框架排队时另一些资源闲置。统一资源管理的价值在于把硬件池化,使批处理、流式、交互式任务能按需竞争共享资源。 静态切分浪费
调度概念分为资源组织、策略和任务组织:资源可分组或池化,任务按用户与队列管理,策略决定如何匹配。通用架构由节点管理器报告水位,资源收集器更新资源池,调度器为工作队列分配容器,再由节点执行与隔离。分配成功不自动说明节点状态仍新鲜或任务已完成。 资源队列连接任务队列
调度器不只是分配 CPU 和内存,还要同时处理资源异质性、负载异质性、数据局部性、抢占、分配粒度、饿死、死锁和隔离。好的策略本质是多目标折中。 调度约束集合。节点本地、同机架、跨机架代表不同数据搬运范围,调度可尽量把计算放到数据附近。实际还要比较可用CPU内存和排队时间,本地资源不足时迁移计算或远程读取可能更快;机架内一定更快并非现代网络通用保证。局部性是成本目标,不能脱离资源与拓扑绝对化。 局部性与等待联合取舍。资源不足时,抢占可回收低优先级任务的已分配资源,非抢占则等空闲或自然释放。前者帮助紧急任务,也可能丢掉已完成计算、引发重试;后者降低干扰但等待可能长。公平不等于必须非抢占,书中公平调度器反而以抢占纠正长期不公平,需按保障与回收规则判断。 抢占回收有执行成本。若两个作业各需全资源的2/3才能启动,却各占住1/2等待剩余,资源已尽而谁也不运行、不释放,就形成死锁。群体分配可以要求一次获得启动集合,增量运行则需部分资源就能推进;选择时要区分任务依赖。低优先级一直等不到机会是饿死,并不一定造成全局死锁。 资源储备可能形成死锁。调度决定分给谁多少资源,隔离限制任务实际使用以减轻相互干扰。书中容器与cgroups用于CPU、内存等资源控制,但不同资源的隔离强度和版本能力不同,共享内核与设备仍可能干扰。LXC、lmctfy、Warden是历史实现例子,不能据此断定当前YARN或Mesos均只用同一容器方案。 隔离不等于调度公平
集中式调度把策略集中在中央;两级调度让中央分配框架资源、框架再安置任务;共享状态调度让多个调度器在全局状态副本上制定计划,再通过事务冲突检测提交。乐观并发可能导致重试,并不意味着牺牲已提交资源分配的一致性;能否公平也取决于仲裁策略,不能仅按架构名称断定。 三类调度范型。Omega类共享状态调度在本地状态副本上计划,通过事务检查提交时的资源冲突;失败计划重新计算或重试,并不必然重跑已经执行的业务任务。提交检查维护资源分配正确性,乐观并发节省的是中央串行规划。冲突率、优先级和仲裁规则决定效率与公平,不能认定没有中央强调度就绝不可能公平。 共享状态冲突需重试
数据局部性会减少跨网络读数据,但严格等待本地资源会拖慢任务。延迟调度允许任务短暂等待本地资源,超过阈值再放宽条件,用少量排队时间换整体吞吐。 延迟调度价值。主资源公平调度把每个用户占比最高的资源作为公平指标,避免只按 CPU 或内存单维度分配造成偏斜。多资源集群里,公平必须考虑任务对资源的不同组合需求。 DRF公平尺度。FIFO按排队或优先级处理,简单但短作业可能长等;公平调度与能力调度都可对池或队列设最低保障和上限,再临时共享闲置资源。原书分别强调作业和用户公平,这是版本场景描述,不是永久互斥特性。配置时应明确层级、权重、抢占和队列内部策略,不能只选名称。 调度公平先选保障对象。DRF先以资源已分配量除各类总量,再取每个用户最大占比,优先为主分享量最小者尝试下一任务。9CPU/18GB例中A每任务1CPU/4GB,B为3CPU/1GB,A三任务与B两任务的主份额都为2/3。任务粒度、配额和不可行需求会影响最终结果,不能强求所有资源同时用满。 主分享量指导下一次分配
书中Mesos中央分配器决定给哪个框架多少资源,框架调度器决定用这些资源运行哪些任务,节点执行器负责执行。框架可拒绝不合适的offer并用过滤器减少重复交互;资源可见性和数据局部性因此与集中规划不同。此为历史Mesos架构,不以原书“不支持抢占”概括所有后续版本。 资源供应下放安置决策
YARN将全局资源分配交给ResourceManager,每个应用的ApplicationMaster管理该应用任务,NodeManager管理节点容器。客户端提交后先分配并启动AM,再由AM申请任务容器、联系节点启动和释放资源。AM不是整个集群的唯一调度器,拆开职责也不自动消除RM故障,需要单独高可用机制。 作业主控分离全局资源
原书依据 · 17 处
第5章 分布式协调系统
本章围绕分布式协调系统展开。协调服务承载控制元数据,客户端利用节点、会话、版本和通知组合更高层协议,真实故障下还需处理不确定结果和旧持有者。
分布式协调系统解决的是“大家对状态达成同一认识”的问题:选主、配置、锁、成员发现、存活检测和同步。它应小而可靠,承载元数据和控制面,而非大吞吐数据面。 协调系统定位
Chubby 面向长时间持有的粗粒度锁,强调可靠性、可理解语义和高可用,而不是高吞吐。领导者选举、主控元数据和服务发现适合放在这种低频但关键的协调层。 粗粒度锁服务。Chubby会话由KeepAlive续租,服务器在约定租期内维持会话承诺。ZooKeeper临时节点则随会话终止或过期删除,短暂断连不等于已经过期。协调服务释放权利也不自动阻止失联旧持有者继续访问外部资源;接管还需由被保护资源校验代际等机制,不能把故障检测当作进程确定死亡。 会话租约语义。Chubby允许客户端缓存协调数据,服务端记录谁缓存了什么。修改前先通知相关客户端失效并等确认,再继续更新,降低读通信而把协调代价放到写路径。失联客户端还需通过会话租约等机制处置,不能仅按“等所有确认”推导它永远不会阻塞,也不能缓存业务大对象当数据库用。 缓存失效先于数据修改。本地GFS依赖Chubby选主,若Chubby的恢复数据也只能从这套尚未启动的GFS取回,就可能互相等候。原书把快照放到其他数据中心GFS以切断这个启动环。恢复路径必须检查依赖图,异地保存只是该案例方法,仍需保证远端可访问和恢复权限。 恢复存储避免循环依赖
ZooKeeper 的 Watch 机制适合把元数据变化通知给客户端,但它不是可靠消息队列的完整替代。客户端收到通知后应重新读取状态,因为通知只提示“变了”,不承诺携带全部变化历史。 Watch通知边界。ZooKeeper由领导者对写入排序,普通读可由客户端所连服务器响应,从而扩展读吞吐,也允许不同客户端暂时看到不同状态。原书建议必要时sync后读,需等待同步操作完成并理解并发写边界,不能据此宣称所有读自动线性一致。多数可通信等前提也不能缩成只要多数机器进程还活着就始终可用。 就近读不等于全局新鲜。Znode可同时有数据与子节点,文件/目录只是类比;原书持久、临时与顺序属性决定生命周期和命名。临时节点随会话结束或过期删除,不能把每次断网都视为立刻删除,传统临时节点也不可有子节点。顺序编号服务于同父路径下的顺序协调,不是全系统永久不重复业务ID。 节点属性区分生命周期。书中API把create用于建立节点,getData/exists/getChildren用于读取并设置watch,setData和delete带expectedVersion用于条件修改或删除。先读取版本再带版本提交,可检测中途被别人修改;失败后应重新读并决定重试。接口列举是概念签名,实际语言绑定与异步回调需按库核对,不把伪码直接当可执行脚本。 版本条件保护节点更新。各候选者竞争创建同一临时leader节点,只有创建成功者当选;其他节点观察变化,过期删除后再竞争。读取不存在与创建之间存在竞争,应处理已存在与连接不确定错误,不能把任何读取失败都当没有主。旧主可能暂停后恢复,外部写入还需校验代际;原书Python片段只是示意。 临时选主仍需防旧主。配置管理把小配置放在Znode,客户端读取时注册传统一次性watch,收到提示后重新读取并重新注册。应以当前版本为准而非把每个通知当完整事件流;重连后也需重建状态。当前ZooKeeper另有持久watch能力,不能把历史一次性模式概括所有API。 配置监听循环重读。成员在群组父节点下创建临时子节点,管理者读子节点集合并监听变化,重读集合计算加入或离开。它表达协调服务所见的会话存活,不证明业务线程一定健康;需结合任务或服务探测。会话断开后可能继续存在到过期,不能把目录当实时无误故障检测器。 成员目录表达会话存活。示例用tasks目录记录新任务,管理进程向machines/m-i下建立分配节点,worker执行后删除两处记录。若执行成功后删除前崩溃,重试可能重复;若先清理再完成又可能丢任务。原书只是协调骨架,生产上还需持久任务状态、认领代际、幂等执行与结果确认,不能由目录删除顺序证明恰好一次。 任务目录不是恰好一次。竞争者创建临时顺序节点,若自己为最小序号即获锁,否则只监听当前紧邻前驱;前驱消失则重读候选集合判断,而不是同时监听持锁者造成羊群效应。最近前驱是现存排序中的前一项,不一定数值恰小1;注册watch前它若已消失也应重新检查。对外部资源仍需旧持有者隔离。 锁等待最近的前驱。写请求等所有比自己更早的请求离开;读请求只需等更早写请求,所以同一段读可并发。等待对象是最近的更早写节点,唤醒后重新检查条件,不能因一个通知就直接获锁。节点以read/write前缀区分类别,真正排序依据顺序号,而非字符串字典序。 读锁等待更早写者。进入时每个进程登记到达,达到约定人数后才开始;退出时删除自己的登记,等待本轮所有进程都准备离开。真实实现需稳定参与集合或轮次标识,并处理会话过期、重复进入和丢失通知;原书计数示意并不保证故障进程下总能结束,也不表示所有机器物理同一时刻执行。 双向路障需稳定轮次。模糊快照遍历时状态可继续改变,因此恢复要结合事务日志与标识重建已提交状态,不能只把快照当某个瞬时完整图像。系统内部重放按事务序列处理,不等于所有客户端create/delete请求天然幂等;任意重复发业务调用仍可能失败或产生新顺序节点。 快照回放依赖事务标识
原书依据 · 19 处
第6章 分布式通信
通信章节区分接口调用、消息队列及状态扩散。IDL与序列化减少跨语言交换的样板工作,但远程失败和语义兼容仍需处理;Protobuf、Thrift与Avro的职责不能以压缩率一概排序。Kafka通过分区日志、位置及复制管理消息,顺序与耐久保证有明确边界。Gossip用局部交换传播信息,反熵修复与停止传播在开销、覆盖之间作不同取舍。
RPC用接口和代理隐藏一部分编码、连接及消息交换过程,使远程服务更容易调用。远程执行仍会遇到超时、部分失败、重试和重复请求,不能按普通本地函数假设成功与失败完全可知。书中同步阻塞调用是一个模型,不代表所有RPC都必须阻塞;序列化效率也不等于网络可靠性。 见RPC隐藏调用细节不隐藏故障。
IDL描述双方共同使用的消息结构及服务接口,再为不同语言生成对应代码。跨语言建立在双方遵守同一协议、字段含义及兼容规则上,不表示Protobuf与Thrift的任意消息可直接互通。修改字段时仍要考虑编号、类型及版本兼容;生成代码消除重复样板,不消除业务语义分歧。 见IDL建立双方共同的数据契约。
目的:把一份Thrift接口描述用于指定语言的应用。先在MyProject.thrift中定义类型和服务,再按书中示例执行thrift --gen java MyProject.thrift生成Java代码,在调用方与服务方引入对应生成物并实现服务逻辑。生成成功不代表服务已部署或兼容性已验证;实际环境还需明确工具版本和依赖。本次仅整理书中操作,未执行编译或网络调用。 见Thrift从定义生成代码。
Protobuf把按Schema定义的结构化消息编码为可传输字节,并生成语言绑定;RPC传输可由其他框架配合。它不是通用压缩算法,不应以最高压缩率概括全部价值。原书语言支持数量和与RPC的合称属于当时语境;官方文档明确支持repeated,现代语法亦有map,因此不能照录“不支持List和Map”的绝对比较。 见Protobuf结构化编码。
原图的Person含name、id、可选email及重复phone字段;PhoneNumber含number和带默认值的PhoneType,AddressBook重复保存Person。图中消息嵌套及字段类型表达数据结构,不是业务对象继承;Thrift一侧phone为set,不能与Protobuf重复字段直接宣称语义完全一致。图中Repeated首字母大写属于示例拼写,真实关键字应为repeated。 见通讯录消息区分嵌套与重复字段。
Avro用Schema描述基本与复合数据类型,支持二进制和JSON等数据表达;读取仍需要相应Schema及兼容解析。原书将JSON Schema描述直接称作IDL过于笼统:官方还提供独立Avro IDL语言。Schema放在数据前也应区分对象容器文件和RPC交换,不能说每条消息都重复携带整份Schema。 见Avro配合模式与编码。
书中LongList记录有long类型value,以及可指向LongList或null的next;命名类型的递归引用表达链接,null提供终止条件。aliases中的LinkedLongs是类型别名而非额外链节点。此处是Schema关系示意,不能从它推导运行时共享指针、循环对象或持久化行为;示例注释也不应原样当作严格JSON输入。 见递归Schema表达可终止链表。
生产者将消息交给中间层后,消费者可按自身节奏处理,降低必须同时在线的时间依赖。队列没有消除消息格式、业务语义和容量约束;积压可能转化为延迟,持久化也要结合确认、复制和保留策略评估。消费者竞争同一份工作与订阅多个主题是不同分发语义,不能只凭Pub-Sub名称推定交付保证。 见异步队列分离时间依赖。
原书把ActiveMQ、RabbitMQ、ZeroMQ和Kafka放在消息通信背景下比较,适合了解不同产品侧重。ZeroMQ更接近通信库与套接字模式,不应无条件当作自带持久化Broker的队列。2014年单次1KB吞吐测试缺少统一硬件、确认和耐久配置,不能延伸成今天的产品性能排名;选型需对齐保证和场景。 见消息产品比较先分清职责。
Kafka在生产者、Broker和消费者之间提供分区化的持久日志,使同一数据可被按位置读取,用于日志、行为数据或其他消息通道。主题是逻辑分类,分区是分布与复制的重要单位。这里介绍2014年书中Kafka的设计动机与日志主线,不把当时ZooKeeper架构或旧消费者接口当作当前安装说明。 见Kafka用分区日志承载消息。
主题可切成多个分区分布在Broker上,使不同分区并行处理;记录在一个分区内按日志位置排序,不自然形成跨分区全局顺序。按键分区可让相关消息进入相同分区,但要保持相应路由条件。Round Robin是轮流分配而非随机分配,也不能因此承诺同一键始终落同一分区。 见分区提供局部顺序与并行。
分区日志拆为一组段文件,新消息追加到活动段;索引帮助从逻辑Offset找到相应位置,再顺序读取。Offset是分区中的位置,不是整个集群的统一消息ID,也不能对所有记录用固定长度乘法推算字节地址。消费者记录进度后可重读仍被保留的数据;已经因保留策略删除的数据不因重置Offset而恢复。 见Offset与分段索引支持定位。
原书通过消费者进度和ZooKeeper说明当时元数据管理的分工,不能从中推出Broker无状态:分区日志、复制进度和本地存储仍需管理。当前版本也不能直接照用旧客户端存Offset到ZooKeeper的架构;已核Kafka4.0固定版本文档,KRaft将元数据控制职责集成到控制器,角色变化不抹去数据存储状态。 见Broker仍维护日志状态。
ISR追踪与分区Leader保持足够同步的副本,健康切主与已提交记录的保留依赖相应复制条件。生产者是否等待复制确认,还由acks及min.insync.replicas等设置约束;不能把所有写请求一概说成等全部分配副本成功。原书f+1与多数派2f+1的比较是特定协议与故障条件下的耐久性讨论,不是相同可用性、故障恢复和丢盘条件下的无条件替代。 见ISR与确认决定耐久性。
日志追加把许多随机写转成连续写,并可通过批量请求减少每条记录固定开销;读取也可利用页缓存和顺序访问。收益取决于工作集、存储介质、批量大小与耐久配置,不是磁盘普遍快过内存。原书SATA速度与倍数是历史说明,不能当作当前设备基准。 见顺序追加与批量化减少随机开销。
sendfile可在内核中把文件数据送到输出描述符,减少先读到用户缓冲再写出的复制与系统调用开销,适合文件到套接字等路径。零拷贝是减少特定复制的工程术语,不表示物理上完全没有数据搬运;传输、加密及平台条件仍重要,调用亦可能只发送部分数据而需继续处理。 见sendfile减少用户态往返。
Gossip让节点通过与部分对端交换信息,使状态逐步传播,减少所有节点直接互通知的组织压力。它可用于成员信息、故障线索和副本同步等场景,但传播机制本身不等于共识或瞬时一致。直接通知全体、持续反熵和带停止条件的谣言传播具有不同成本及覆盖保证,应明确使用哪一种。 见Gossip以局部交换扩散状态。
反熵让节点周期性比较状态并修复差异;Push发送本地较新状态,Pull请求对端状态,Push-Pull结合两向交流。版本摘要可减少无用传输,但时间戳较大不自动证明因果上正确,也不能自行解决并发冲突。原书熵的比喻用于说明趋于同步,不能把信息论熵简单定义为有用信息多少。 见反熵交换需要识别版本差异。
当传播者发现对方早已知道更新,可逐渐增加停止传播的概率,从而减少网络上反复发送相同内容。停止条件换来了较低开销,也可能在某些节点尚未获知时终止。需要最终覆盖时,应有持续同步或修复机制;不能将快速扩散的经验理解为每次更新必达全部节点。 见谣言停止降低流量也留下遗漏风险。
书中Cassandra示例先发送节点及版本摘要,接收方返回自己更新的状态和所需版本,发起方再补齐对方缺失部分,形成一次Push-Pull交换。摘要帮助判断传哪些内容,而非第一步就传整个集群所有数据。种子节点帮助新成员发现集群,不是所有数据更新必须经过的主节点;具体周期及状态名保留书中版本范围。 见摘要握手减少状态同步数据量。
章末对Kestrel的简洁和完备性比较仍是2014年作者评价:代码量少与可靠性能力不是同一指标,不把当时缺高可用的描述当作当前产品事实。这一取舍并入消息产品比较先分清职责,不为简短评价重复建卡。
原书依据 · 24 处
- 分布式通信 · 查看原书依据
- 分布式通信 · 查看原书依据
- 分布式通信 · 查看原书依据
- 分布式通信 · 查看原书依据
- 分布式通信 · 查看原书依据
- 分布式通信 · 查看原书依据
- 分布式通信 · 查看原书依据
- 分布式通信 · 查看原书依据
- 分布式通信 · 查看原书依据
- 分布式通信 · 查看原书依据
- 分布式通信 · 查看原书依据
- 分布式通信 · 查看原书依据
- 分布式通信 · 查看原书依据
- 延伸阅读 · 查看原书依据
- 分布式通信 · 查看原书依据
- 分布式通信 · 查看原书依据
- 分布式通信 · 查看原书依据
- 分布式通信 · 查看原书依据
- 分布式通信 · 查看原书依据
- 分布式通信 · 查看原书依据
- 分布式通信 · 查看原书依据
- 分布式通信 · 查看原书依据
- 分布式通信 · 查看原书依据
- 分布式通信 · 查看原书依据
第7章 数据通道
数据通道面向三类需求:分散日志汇聚、已提交数据库变化通知、异构系统批量迁移。Chukwa和Scribe展示接入、缓冲与批处理的分工;Databus的近期Relay及Bootstrap共同支持快慢消费者;Wormhole把变化路由给下游,Sqoop负责批量搬迁。双写窗口、保留进度、重放与下游事务是不能靠系统名称抹去的一致性问题。
日志分散在许多节点,集中收集需要同时考虑产生到可分析的延迟、动态扩缩和故障期间的缓冲。分析允许的延迟由用途决定,不能把书中分钟或小时级容忍推广到告警、审计或在线风控。保证不丢还需说明持久化、确认、重放和容量耗尽策略,不能只因有收集器就成立。 见日志收集目标要匹配分析时效。
Chukwa在节点部署Agent,把日志送往Collector及存储,再经归档整理和Demux解析供分析。它区分高频小日志接入与批量计算,避免为每小批资料直接启动MapReduce任务的开销。此卡是2014年项目架构导读,书中对未来性能的判断属于当时评价,不当作当前部署建议。 见Chukwa分开收集与批处理。
当每次处理的数据很少,作业启动、中间结果及磁盘往返等固定成本会占据主要时间。收集层先连续接入并整理数据,分析层再按适当批量执行,可使两种负载分别优化。批量变大又会增加等待,因此应按吞吐和时效目标取舍,不能只用单次作业速度判断整条数据链路。 见小批数据不宜重复承担作业开销。
Scribe接收应用以Thrift发送的分类日志,经服务器队列转交文件存储或下一层Scribe。目标端不可用时,可将数据暂存在本地磁盘后再转发,形成分层收集路径。缓冲只是故障承受的一环,还受磁盘容量、节点故障和交付确认影响,不能据此承诺绝对无丢失;这是书中历史系统设计。 见Scribe分类汇聚日志。
数据总线把数据源已经发生的变更通知给关注它的缓存、索引或分析系统。近实时、按主题选择和从某位置回溯,是降低重复扫描并恢复下游的重要能力。通知通道并不天然保证下游数据库与源库同一事务提交,应分别说明保留位置、重复处理和业务一致性要求。 见数据总线传播变化而非重复全量。
业务分别写数据库与消息系统时,一步成功另一步失败,会出现已变更却无通知或有通知却无相应数据的窗口。不能只改变两步先后顺序就消除问题,也不能把Paxos共识直接当作任意两资源原子提交的完整方案。书中以此引出从已提交数据库日志捕获变化;消费者仍需处理重试与重复。 见独立双写存在中间失败窗口。
先提交源库变更,再从其事务日志提取相关更新,可避免应用独立双写通知的缺口,使通道以源库的提交记录为依据。日志格式、Schema演化、解析版本及保留期由此成为依赖。捕获源端提交不意味着外部消费者业务与偏移量天然原子,端到端正确性仍需额外设计。 见日志捕获从已提交变化建立通道。
Databus Relay把源库近期提交更新编码后放入环形内存缓冲,客户端以Pull方式按进度获取。环形结构限制了内存占用,也意味着落后过久的消费者所需更新可能被覆盖。拉取使消费速率可控,却不会凭空消除积压;需要配合保留窗口与Bootstrap追赶机制。 见Databus保留近期变化。
新消费者或落后消费者先通过Bootstrap取得适当快照及其后的增量,再追上Relay继续读取,可以减少每次都扫描主数据库的压力。快照边界与增量位置必须衔接,不能仅按随意墙上时钟时间拼接而保证无缺口。原书用时间点解释总体思想,未给出的事务边界算法不补造。 见快照加增量支持落后消费者追赶。
Bootstrap订阅Relay的更新,由Log Writer保存增量日志,再由Log Applier把更新应用到快照存储。两种表示分别服务按位置重放和快速获得状态,具有不同职责。不能把快照当作所有历史记录,也不能因保存了日志就省略更新应用的幂等、进度和错误处理问题。 见快照与增量日志分工。
Wormhole从数据库更新形成主题和分片,向缓存、搜索索引及数据仓库等订阅者分发,也服务跨数据中心的数据通道。书中描述至少一次交付与分片内顺序,这允许重传,不能直接推导消费者只执行一次或跨分片全局有序。消费者应按实际业务定义去重、进度与恢复边界。 见Wormhole路由提交变化。
Sqoop通过连接器及批量任务,把数据在关系库等系统与Hadoop存储之间导入或导出,适合区别于逐条变更订阅的搬迁需求。书中Sqoop1命令行到Sqoop2服务接口的比较保留历史版本范围,不视为当前安装推荐。选择迁移工具还要核对类型映射、一致性快照、失败恢复和目标负载。 见Sqoop解决异构系统批量迁移。
第8章 分布式文件系统
分布式文件系统先要回答工作负载是什么:GFS以大文件、追加和顺序吞吐为中心,用Master管理命名与Chunk映射,客户端拿到位置后直接访问数据节点。文件内容的复制顺序、管理元数据的日志以及失败后的恢复是不同层次;记录原子追加仍可能重试出重复,不能由原子性推导恰好一次。单Master让控制简单,也把命名空间容量与管理吞吐压在一台机器。Colossus的管理分片、HDFS HA和Federation分别从扩展与服务连续性处理这一矛盾。
HDFS检查点不是热备,Standby必须同时追赶命名编辑与块位置;自动切换还需健康判断、选主及旧主隔离。QJM的2F+1日志节点需要F+1多数确认,原书少写一个确认且过度宣称不再需要隔离,不能照搬。Federation让独立命名空间共享DataNode,但不替代每个命名空间的HA。Haystack把小图片打包进大卷,用紧凑内存索引减少一次元数据磁盘读取,缓存处理热点,存储层仍服务长尾;追加更新和墓碑把回收工作移到后台。
存储布局独立于分布式文件系统接口。行存便于整行读取,列存便于投影和同类型压缩,行组内列存折中扫描与重组。Dremel为嵌套叶列补充重复层和定义层,才能保存列表边界及缺失位置,RCFile、ORC、Parquet再把分组、索引和页式编码用于有效读取。Row Group是逻辑结构,不能保证同机器放置。
纠删码用校验减少冷数据冗余,但恢复会读多个幸存块。RS要在同一有限域上用真正满足MDS性质的生成矩阵编码与求解;单位阵任意拼普通Vandermonde不构成证明,作者教程已有勘误。原书GF(16)恢复图片中途换数据,本次按原输入重新核算,不把不同样本混用。LRC再用局部冗余减少单块恢复IO,代价是额外存储与特定容错边界;16块示例只保证任意4个擦除,并非有6个校验就保任意6损坏。
工作负载与GFS控制/数据流:定位元数据后直读块;元数据日志与位置重建;影子主控主要承担读取;先传数据再统一写序;原子追加仍可能重复;主控分片突破元数据上限;按负载设计FS。
HDFS恢复、QJM和命名空间分治:大块文件系统面向吞吐;检查点节点不是热备;热备同步两类管理信息;故障切换与状态同步分开;QJM需要多数日志节点;日志隔离不覆盖全部旧主;联盟按命名空间分治;主控元数据瓶颈。
Haystack卷、缓存和追加回收:逻辑卷映射多个物理卷;热图缓存与长尾回源分工;目录管理卷与写入负载;紧凑索引加速卷恢复;对象更新用追加与回收;Blob元数据进内存。
行列布局、嵌套级别与格式:列族聚合常用字段;嵌套文档的模式树;重复层标记列表边界;定义层区分缺失位置;按层级重建嵌套记录;行组内按列组织RCFile;条带索引跳过无关数据;Parquet分层定位列页;列式布局省IO;混合布局折中。
RS有限域、恢复与LRC:编码字长决定有限域;用对数表做有限域乘除;任意恢复依赖MDS矩阵;按幸存行求解丢失块;保持恢复示例输入一致;局部恢复用额外冗余换IO;LRC不能按校验数估容错;历史RAID后台编码与修复;纠删码冷数据。
进一步阅读:定位元数据后直读块;元数据日志与位置重建;影子主控主要承担读取;先传数据再统一写序;原子追加仍可能重复;主控分片突破元数据上限;大块文件系统面向吞吐;检查点节点不是热备;热备同步两类管理信息;故障切换与状态同步分开;QJM需要多数日志节点;日志隔离不覆盖全部旧主;联盟按命名空间分治;逻辑卷映射多个物理卷;热图缓存与长尾回源分工;目录管理卷与写入负载;紧凑索引加速卷恢复;对象更新用追加与回收;列族聚合常用字段;嵌套文档的模式树;重复层标记列表边界;定义层区分缺失位置;按层级重建嵌套记录;行组内按列组织RCFile;条带索引跳过无关数据;Parquet分层定位列页;编码字长决定有限域;用对数表做有限域乘除;任意恢复依赖MDS矩阵;按幸存行求解丢失块;保持恢复示例输入一致;局部恢复用额外冗余换IO;LRC不能按校验数估容错;历史RAID后台编码与修复;按负载设计FS;主控元数据瓶颈;Blob元数据进内存;列式布局省IO;混合布局折中;纠删码冷数据。
原书依据 · 44 处
- 分布式文件系统 · 查看原书依据
- 分布式文件系统 · 查看原书依据
- 分布式文件系统 · 查看原书依据
- 分布式文件系统 · 查看原书依据
- 分布式文件系统 · 查看原书依据
- 分布式文件系统 · 查看原书依据
- 分布式文件系统 · 查看原书依据
- 分布式文件系统 · 查看原书依据
- 分布式文件系统 · 查看原书依据
- 分布式文件系统 · 查看原书依据
- 分布式文件系统 · 查看原书依据
- 分布式文件系统 · 查看原书依据
- 分布式文件系统 · 查看原书依据
- 分布式文件系统 · 查看原书依据
- 分布式文件系统 · 查看原书依据
- 分布式文件系统 · 查看原书依据
- 分布式文件系统 · 查看原书依据
- 分布式文件系统 · 查看原书依据
- 分布式文件系统 · 查看原书依据
- 分布式文件系统 · 查看原书依据
- 分布式文件系统 · 查看原书依据
- 分布式文件系统 · 查看原书依据
- 分布式文件系统 · 查看原书依据
- 分布式文件系统 · 查看原书依据
- 分布式文件系统 · 查看原书依据
- 分布式文件系统 · 查看原书依据
- 分布式文件系统 · 查看原书依据
- 分布式文件系统 · 查看原书依据
- 分布式文件系统 · 查看原书依据
- 分布式文件系统 · 查看原书依据
- 分布式文件系统 · 查看原书依据
- 延伸阅读 · 查看原书依据
- 分布式文件系统 · 查看原书依据
- 分布式文件系统 · 查看原书依据
- 分布式文件系统 · 查看原书依据
- 延伸阅读 · 查看原书依据
- 分布式文件系统 · 查看原书依据
- 分布式文件系统 · 查看原书依据
- 延伸阅读 · 查看原书依据
- 分布式文件系统 · 查看原书依据
- 分布式文件系统 · 查看原书依据
- 分布式文件系统 · 查看原书依据
- 延伸阅读 · 查看原书依据
- 分布式文件系统 · 查看原书依据
第9章 内存KV数据库
内存KV把正常读写放在内存,但成本与恢复能力不会随磁盘退出热路径而消失。把副本也全部留内存,可缩短接管却放大内存费用;只把备份放磁盘,则必须解决故障后的并行重建。RAMCloud用哈希表定位对象、日志组织更新,分散备份日志段并由多个恢复节点共同重建。原文5–10纳秒应为原论文的微秒目标,约一秒恢复也依条件成立。日志结构不等于LSM树,磁盘恢复期间先应答请求是作者提议而非已验证能力。
Redis展示另一条路线:主节点处理写入,副本异步跟进,重连时依据复制历史与缓冲保留范围选择部分或全量恢复。VIP迁移只改变访问入口,不能保证副本最新或旧主被隔离,原文Cluster未发布等状态须放回出版语境。Membase以虚拟桶分片,集群节点对等而每个桶仍有主从;Couchbase写入是否等待复制与持久化需按具体版本和durability选项判断,不能把所有写入说成同步强一致。选择恢复方案应同时预算成本、RTO、可接受丢失和角色切换协议。
内存成本与RAMCloud恢复:路由缓存定位内存主数据;内存日志配合哈希索引;散布备份实现并行恢复;恢复期间磁盘服务是提议;内存库成本悖论;RAMCloud恢复。
Redis复制与接管:部分复制受保留窗口约束;VIP迁移不等于数据接管;Redis主从边界。
Membase虚拟桶与副本:节点对等与分片主从并存;副本同步语义必须显式选择。
进一步阅读:路由缓存定位内存主数据;内存日志配合哈希索引;散布备份实现并行恢复;恢复期间磁盘服务是提议;部分复制受保留窗口约束;VIP迁移不等于数据接管;节点对等与分片主从并存;副本同步语义必须显式选择;内存库成本悖论;RAMCloud恢复;Redis主从边界。
第10章 列式数据库
本章沿历史云存储谱系讨论Bigtable、PNUTS、Megastore和Spanner,题名中的列式不等于它们全是分析型列存。Bigtable用行键、列键与时间组织值,列族事先定义、列描述符可动态增加,范围Tablet提供分布式管理。Chubby与元数据表帮助定位,客户端直接访问Tablet Server;日志、MemTable、SSTable及后台合并共同构成写读与恢复路径。索引和布隆过滤减少无用读取,不能据过滤阳性推断真实存在。
PNUTS选择记录级时间轴:主记录组织同一记录的更新顺序,经消息系统异步传播;路由器缓存位置,控制器维护权威分配。有序表与哈希表服务不同访问需求,ReadAny、带版本条件的读取和最新读取在陈旧程度与等待代价间提供选择。相同更新顺序不等于所有区域此刻状态相同。Megastore以实体组把常见共同更新的数据放入局部强事务,跨组消息与跨组2PC应区别;过大的组会限制并发,过小的组会增加协调。
Spanner进一步结合复制组、锁管理、跨组提交与TrueTime。Directory组织共同放置与迁移,Paxos解决组内日志共识,2PC协调多组原子提交,谁都不能替代所有层次。TrueTime返回有界区间,GPS与原子钟约束误差但不制造零误差时钟。外部一致性还依赖正确选择提交时间戳并在对外提交前等待它肯定已过去;若T1先完成而T2后开始,时间戳顺序必须尊重这一真实先后。原卡把单纯时间戳比较当作充分条件,本次据官方协议窄修。
Bigtable数据模型与服务分工:宽列模型仍有模式约束;行键范围决定Tablet边界;主控重建分配状态;BigTable三维表;三级定位元数据。
Tablet写读合并与恢复:块索引定位SSTable数据;多级合并清理旧版本;日志恢复衔接已刷盘数据;Tablet写路径。
PNUTS路由与记录一致性:PNUTS可选范围或哈希表;路由缓存服从权威映射;记录主副本发布有序更新;按版本需求选择读取;PNUTS时间轴。
Megastore实体组与跨组操作:实体组聚合共同更新的数据;父子主键支持数据聚簇;共识副本也有读取协议;实体组事务。
Spanner复制事务和有界时间:区域层次与数据放置分工;复制事务与并发各有层次;目录是放置与迁移单元;用有界时间判断先后;异源时钟约束共同误差;TrueTime换顺序。
进一步阅读:宽列模型仍有模式约束;行键范围决定Tablet边界;主控重建分配状态;块索引定位SSTable数据;多级合并清理旧版本;日志恢复衔接已刷盘数据;PNUTS可选范围或哈希表;路由缓存服从权威映射;记录主副本发布有序更新;按版本需求选择读取;实体组聚合共同更新的数据;父子主键支持数据聚簇;共识副本也有读取协议;区域层次与数据放置分工;复制事务与并发各有层次;目录是放置与迁移单元;用有界时间判断先后;异源时钟约束共同误差;BigTable三维表;三级定位元数据;Tablet写路径;PNUTS时间轴;实体组事务;TrueTime换顺序。
原书依据 · 27 处
- 列式数据库 · 查看原书依据
- 列式数据库 · 查看原书依据
- 列式数据库 · 查看原书依据
- 列式数据库 · 查看原书依据
- 列式数据库 · 查看原书依据
- 列式数据库 · 查看原书依据
- 列式数据库 · 查看原书依据
- 列式数据库 · 查看原书依据
- 列式数据库 · 查看原书依据
- 列式数据库 · 查看原书依据
- 列式数据库 · 查看原书依据
- 列式数据库 · 查看原书依据
- 列式数据库 · 查看原书依据
- 延伸阅读 · 查看原书依据
- 列式数据库 · 查看原书依据
- 列式数据库 · 查看原书依据
- 列式数据库 · 查看原书依据
- 列式数据库 · 查看原书依据
- 列式数据库 · 查看原书依据
- 延伸阅读 · 查看原书依据
- 列式数据库 · 查看原书依据
- 列式数据库 · 查看原书依据
- 列式数据库 · 查看原书依据
- 列式数据库 · 查看原书依据
- 列式数据库 · 查看原书依据
- 列式数据库 · 查看原书依据
- 列式数据库 · 查看原书依据
第11章 大规模批处理系统
批处理框架把海量记录拆分到多个任务,优先吞吐、并行和可恢复性。MapReduce的关键接口不是两个函数名,而是中间键定义了必须一起归约的数据。Map本地分区文件、位置元数据、Shuffle与排序把相同键送至同一Reduce;抓取可与尚未完成的Map重叠,用户归约仍需相应输入齐备。中间文件故障可触发已完成Map重算,Combiner只有在任意局部合并不改变结果时才安全。
可复用模式必须落实到用途。数值统计要保存可合并信息;链接反转和倒排索引汇集关系;独立过滤可以省Reduce;TopK须建立在已确定的全局评分和一致比较规则上。分类分区负责组织输出,全局排序还需有序范围分区与有序读取各输出。Reduce侧连接按键汇聚两侧并处理多对多规模,Map侧连接则以每个Mapper能装下小表及版本一致为前提,用复制小表换掉大表Shuffle。
DAG放开两阶段形状,把表达、执行引擎与物理集群分层。Dryad的Job Manager组织图与调度,数据通道直接连接计算节点;点连、全连、克隆与融合决定通信方式。图节点依输入就绪调度,中间物化决定故障重算范围。FlumeJava和Tez让多步任务在更大图上优化,可减少重复启动和不必要落盘,并不承诺所有中间数据都不落盘或全部控制故障自动消失。
MapReduce计算与执行机制:按业务键形成聚合组;反转链接构建倒排关系;分区文件衔接归约;抓取可与Map执行重叠;Combiner须允许重复调用;本地中间结果丢失需重算;MapReduce边界;Shuffle是成本中心;DAG突破两阶段。
聚合、过滤、组织和连接用途:用可合并统计量求平均;纯过滤可省归约阶段;两阶段合并局部TopK;用分区输出重组数据;范围分区形成全局排序;Reduce侧按连接键汇合;小表驻内存做Map连接;Map连接的初始化与处理;模式复用MR。
DAG层次、Dryad和图优化:DAG执行层衔接表达与机器;Dryad控制面不搬运数据;图运算区分点连与全连接;输入就绪再调度图节点;DAG优化减少多作业落盘。
进一步阅读:按业务键形成聚合组;反转链接构建倒排关系;分区文件衔接归约;抓取可与Map执行重叠;Combiner须允许重复调用;本地中间结果丢失需重算;用可合并统计量求平均;纯过滤可省归约阶段;两阶段合并局部TopK;用分区输出重组数据;范围分区形成全局排序;Reduce侧按连接键汇合;小表驻内存做Map连接;Map连接的初始化与处理;DAG执行层衔接表达与机器;Dryad控制面不搬运数据;图运算区分点连与全连接;输入就绪再调度图节点;DAG优化减少多作业落盘;MapReduce边界;Shuffle是成本中心;模式复用MR;DAG突破两阶段。
原书依据 · 27 处
- 大规模批处理系统 · 查看原书依据
- 大规模批处理系统 · 查看原书依据
- 大规模批处理系统 · 查看原书依据
- 大规模批处理系统 · 查看原书依据
- 大规模批处理系统 · 查看原书依据
- 图数据库:架构与算法 · 查看原书依据
- 大规模批处理系统 · 查看原书依据
- 大规模批处理系统 · 查看原书依据
- 大规模批处理系统 · 查看原书依据
- 大规模批处理系统 · 查看原书依据
- 大规模批处理系统 · 查看原书依据
- 大规模批处理系统 · 查看原书依据
- 大规模批处理系统 · 查看原书依据
- 大规模批处理系统 · 查看原书依据
- 交互式数据分析 · 查看原书依据
- 大规模批处理系统 · 查看原书依据
- 延伸阅读 · 查看原书依据
- 大规模批处理系统 · 查看原书依据
- 大规模批处理系统 · 查看原书依据
- 大规模批处理系统 · 查看原书依据
- 大规模批处理系统 · 查看原书依据
- 大规模批处理系统 · 查看原书依据
- 延伸阅读 · 查看原书依据
- 大规模批处理系统 · 查看原书依据
- 大规模批处理系统 · 查看原书依据
- 大规模批处理系统 · 查看原书依据
- 大规模批处理系统 · 查看原书依据
第12章 流式计算
流式任务持续接收记录,低延迟目标必须与状态恢复、扩展和表达能力一起设计。连续SQL窗口与可编程数据流平台是不同抽象层,可以组合。Storm、S4和Samza把控制、执行、消息与资源管理组合为不同架构,管理进程的可恢复状态不等于业务内存状态。DAG节点用记录与定时回调处理数据,键决定相关状态落点,时间戳也不必等于到达墙钟。Shuffle、按字段分组和广播应依状态局部性选择,并为热键与放大流量负责。
送达语义不能只看传输次数。ACK与重放可保证至少一次,失败窗口仍可能使已完成的数据再执行。Storm把衍生消息锚定成树,用64位异或状态追踪完成,但来源需要可重放,未锚定输出不在保障范围;它不是持久去重数据库。点击计费中漏事件会少计收入,重复累加会多计广告费,因此稳定事件ID必须与计数状态原子持久化,确认要放在提交之后。MillWheel把输入ID、状态、计时与输出纳入原子检查点,再ACK与发送,描述的是受管状态的一次逻辑效果,外部扣款仍需幂等或事务衔接。
恢复设计还应对齐状态与可重放输入位置。冷备用只恢复进程,热备需确定性和单输出约束,检查点之后可以从保留日志重放而不必永久丢失。Trident把批次ID和状态一起提交,并对重放内容和提交顺序提出条件;有序提交仍可让计算流水执行。MillWheel弱持久模式把部分存储成本转移为下游确认依赖,Samza则结合本地状态与Kafka变更日志恢复。历史D-Stream微批限制属于出版时评价,不能无条件概括当前所有微批系统。
流处理目标与平台架构:窗口查询与数据流平台有别;控制状态恢复不等于业务状态;S4对等节点仍依赖协调;Samza分开消息与资源管理;流式常驻计算;微批模拟流式。
计算接口、数据语义和分组:计算回调与持久状态接口;键与时间是数据流语义;按状态访问选择分组;显式配置拓扑并行度;拓扑即数据流。
送达、计费与去重提交:点击计费怕漏算与重算;点击计数需原子去重;ACK与锚定追踪处理树;异或校验压缩待完成集合;提交成功后ACK丢失会重放;输入去重与输出须一起提交;布隆阳性仍需查持久记录;消息语义分层。
状态容错与重放边界:备用进程不自动恢复状态;双路热备需要确定性与去重;检查点须对齐可重放输入;批次ID与状态原子持久化;流水执行与有序提交可并存;弱持久方式保留确认链;本地状态配合变更日志恢复。
进一步阅读:窗口查询与数据流平台有别;控制状态恢复不等于业务状态;S4对等节点仍依赖协调;Samza分开消息与资源管理;计算回调与持久状态接口;键与时间是数据流语义;按状态访问选择分组;显式配置拓扑并行度;点击计费怕漏算与重算;点击计数需原子去重;ACK与锚定追踪处理树;异或校验压缩待完成集合;提交成功后ACK丢失会重放;输入去重与输出须一起提交;布隆阳性仍需查持久记录;备用进程不自动恢复状态;双路热备需要确定性与去重;检查点须对齐可重放输入;批次ID与状态原子持久化;流水执行与有序提交可并存;弱持久方式保留确认链;本地状态配合变更日志恢复;流式常驻计算;拓扑即数据流;消息语义分层;微批模拟流式。
原书依据 · 27 处
- 流式计算 · 查看原书依据
- 流式计算 · 查看原书依据
- 流式计算 · 查看原书依据
- 流式计算 · 查看原书依据
- 流式计算 · 查看原书依据
- 流式计算 · 查看原书依据
- 流式计算 · 查看原书依据
- 流式计算 · 查看原书依据
- 流式计算 · 查看原书依据
- 流式计算 · 查看原书依据
- 流式计算 · 查看原书依据
- 流式计算 · 查看原书依据
- 流式计算 · 查看原书依据
- 流式计算 · 查看原书依据
- 流式计算 · 查看原书依据
- 流式计算 · 查看原书依据
- 流式计算 · 查看原书依据
- 流式计算 · 查看原书依据
- 流式计算 · 查看原书依据
- 流式计算 · 查看原书依据
- 流式计算 · 查看原书依据
- 流式计算 · 查看原书依据
- 延伸阅读 · 查看原书依据
- 流式计算 · 查看原书依据
- 流式计算 · 查看原书依据
- 流式计算 · 查看原书依据
- 流式计算 · 查看原书依据
第13章 交互式数据分析
交互式分析的需求,是让分析人员通过声明式查询在可接受时间内探索大数据。本章以2014年前后系统为背景,比较Hive、Shark、Dremel及混合式数仓。分类方便理解路线,不是严格谱系:Impala与Presto也借鉴MPP数据库,不能简单归为Dremel复制品。当年市场预测和性能倍数不作为当前选型事实。PB是数据量单位,记录条数还取决于记录大小,不将原文括注当固定换算。
早期Hive给HDFS文件增加表结构,分区以目录裁剪范围,桶在分区内按键散列。Metastore保存结构和位置,SerDe解释外部格式。查询从语法树经类型与语义检查形成逻辑算子DAG,优化后再映射物理任务。列裁剪、分区裁剪和谓词下推减少不同维度的数据量;连接策略决定如何移动数据。广播适合可复制的小侧,Shuffle让相同连接键相遇,共同分片则在加载阶段预先支付布局成本。原文对Join重排的简化描述不推广为“大表统一落盘”的通用算法。
MR的Map输出与任务间结果持久化,给失败恢复提供阶段边界,却增加正常执行I/O;启动调度在短查询中的占比尤其明显。Stinger在布局、缓存、Tez、向量化和优化器多层改进,Shark复用Hive前端,把执行映射为Spark RDD。PDE利用运行统计选择后续连接和并行度,避免只靠静态规则;内存带来的速度也受工作集容量约束,不能把任意查询宣传倍数当稳态收益。
Dremel结合嵌套列存和多级服务树。叶节点扫描,中间层局部聚合,根合并;计数分解后必须对局部计数求和,平均等函数需适当中间状态。树深减轻根压力,也增加通信。槽位把多份子表分派给有限线程,推测执行处理少数拖尾任务,但要管理冗余计算。嵌套查询还要保留记录内的重复层级,不能展平后丢失语义。
PowerDrill面向固定交互数据集,以复合范围分片与双字典编码节省内存、跳过不相关Chunk。全局ID保持跨片身份,局部ID压缩片内表示;局部计数须转换为全局ID后合并。Impala将算子树分片并行,Statestore辅助成员健康发现,协调器汇总结果;直接数据读取仍需要元数据,不等于完全不接触NameNode。Presto以存储连接抽象支持多源查询,各源能力与一致性仍须分别理解。
HadoopDB把单机关系数据库放到各数据节点,借MR组织任务,再由SMS将可执行部分下推数据库。数据加载分布决定本地聚合是否已经是最终结果,不符合分组键布局时仍需全局合并。因此混合架构既利用本地优化器,也继承部分MR成本。对这些机制的评价应以查询类型、数据规模、资源和恢复目标为共同条件;后续产品已演进,本轮不运行系统、不声称复现实验。
相关知识:Hive以SQL换MR;内存DAG提速;Dremel树形聚合;MPP交互查询;模式元数据连接文件与表;分区裁剪减少扫描目录;分桶按键分散文件;序列化接口扩展数据格式;查询编译分逻辑与物理;过滤尽量靠近数据扫描;小表驻内存做Map连接;重分布连接对齐相同键;MR落盘换取恢复边界;短查询容易被启动开销主导;性能倍数必须附测试条件;Stinger从多层改进查询;向量执行分批摊薄开销;动态计划利用运行统计;并行度需要平衡粒度;共同分片提前支付布局成本;服务树层数平衡聚合与通信;计数先局部再求和;槽位让线程分批处理子表;推测执行处理少量拖尾任务;嵌套查询保留记录内层次;定制数据仓库优化交互;复合范围分片依赖查询知识;双字典编码缩小局部编号;局部计数按全局身份合并;Impala执行协调与工作分离;成员健康信息辅助调度;计划片段按交换边界并行;Presto用连接接口解耦存储;混合数仓复用两层能力;数据加载决定后续局部性;算子下推须保留全局语义;系统能力结论需标明年代。
原书依据 · 40 处
- 延伸阅读 · 查看原书依据
- 交互式数据分析 · 查看原书依据
- 交互式数据分析 · 查看原书依据
- 延伸阅读 · 查看原书依据
- 交互式数据分析 · 查看原书依据
- 交互式数据分析 · 查看原书依据
- 交互式数据分析 · 查看原书依据
- 交互式数据分析 · 查看原书依据
- 交互式数据分析 · 查看原书依据
- 交互式数据分析 · 查看原书依据
- 交互式数据分析 · 查看原书依据
- 交互式数据分析 · 查看原书依据
- 大规模批处理系统 · 查看原书依据
- 交互式数据分析 · 查看原书依据
- 交互式数据分析 · 查看原书依据
- 交互式数据分析 · 查看原书依据
- 交互式数据分析 · 查看原书依据
- 交互式数据分析 · 查看原书依据
- 交互式数据分析 · 查看原书依据
- 交互式数据分析 · 查看原书依据
- 交互式数据分析 · 查看原书依据
- 交互式数据分析 · 查看原书依据
- 交互式数据分析 · 查看原书依据
- 交互式数据分析 · 查看原书依据
- 交互式数据分析 · 查看原书依据
- 交互式数据分析 · 查看原书依据
- 交互式数据分析 · 查看原书依据
- 交互式数据分析 · 查看原书依据
- 交互式数据分析 · 查看原书依据
- 交互式数据分析 · 查看原书依据
- 交互式数据分析 · 查看原书依据
- 交互式数据分析 · 查看原书依据
- 交互式数据分析 · 查看原书依据
- 交互式数据分析 · 查看原书依据
- 交互式数据分析 · 查看原书依据
- 交互式数据分析 · 查看原书依据
- 交互式数据分析 · 查看原书依据
- 交互式数据分析 · 查看原书依据
- 交互式数据分析 · 查看原书依据
- 交互式数据分析 · 查看原书依据
第14章 图数据库:架构与算法
本章同时讨论在线图服务和离线图计算,二者共享图表示,却追求不同运行目标。邻接表便于按关系遍历,幂律图的高阶节点可能让负载与通信集中,但不能把所有现实图都视为同一分布。在线三层结构用API表达实体关系,中间层映射到持久化与路由,底层可复用数据库;有本地事务不等于跨图操作天然原子。
TAO的历史设计以区域副本和两级缓存换取读延迟与内存成本平衡。Follower处理客户端,Leader对接Shard,读未命中可用本地副本,写仍去主区域。异步复制意味着暂时陈旧;同步回填写变化可改善同一缓存tier的读己之写,原论文还限定故障条件并列出淘汰与复制延迟竞态。因此不沿用原书“缓存更新后一定读新值”的绝对说法,也不把2013年内部系统规模或当前产品排名当今天事实。
离线问题中,PageRank以随机跳转加邻居贡献迭代重要性,需要补充无出边处理;单源最短路径沿有向出边传播源点到各点的距离,原文若干“节点到源点”的措辞与算法方向不符。本轮统一按源到节点解释。匹配中最大要求最多边,极大只要求不能直接加边;Pregel随机握手案例原论文属于极大匹配,不能接受原书将它写成最优边数的结论。
切边在顶点均衡下减少跨区边,切点在边均衡下控制顶点副本数,两个目标都只是工作量代理。随机顶点独立均匀放p台机器时,非自环边切开期望1-1/p;随机边独立均匀分布时,度为D的点副本期望p×[1-(1-1/p)^D]。二维哈希可用行列约束副本分散范围。所有结论有模型前提,不能把期望当实测,也不能从一个指标推出所有图上切点必胜。更复杂分片还需把预处理成本算入总收益。
编程模型说明如何写一次局部更新,执行范型说明何时可见。GAS将Gather、Apply、Scatter拆开,适合分散邻边工作,但合并函数必须满足相应并行语义。同步超级步提供明确边界,异步较早使用变化却要求检查冲突、顺序等价与收敛。GraphLab的Scope及完整、边、顶点一致性限制不同读写集合;其顺序等价不保证所有调度唯一结果,也不等同数据库线性一致性。
MR可按目标ID聚集贡献,保留拓扑并重复迭代,Combiner可减少安全可合并消息;频繁落盘和重启动则是专用图引擎要避免的成本。Pregel保留顶点状态,通过消息串联超级步,VoteToHalt后仍可被消息唤醒,结束必须同时没有活跃顶点和在途消息。最大值只能沿可达路径传播,检查点要形成一致切面。主控恢复既需身份选举,也需管理状态,不能仅凭主从架构推断完整容错。书中代码有排版、常数与初始化简化,本轮只解释机制,未编译或宣称执行成功。
Giraph以长驻Map-Only承载多步运算,通过专用网络而非每轮Shuffle通信。GraphChi则按目标Interval存入边、源ID排序,用完整Shard和其他Shard连续窗口重建子图,将随机访问组织成顺序I/O;保守调度避免共享边写冲突。双版本与边界交换可模拟同步,异步默认让后区间使用前区间更新。最小标签传播求无向或弱连通分量,不能求有向强连通。
PowerGraph把高阶顶点切为Master和镜像,镜像并行Gather,Master统一Apply,再同步和Scatter。增量缓存减少完整收集,但删除或最小值增大可能无法靠增量恢复,需要失效重算。变化阈值影响精度与激活工作量,GAS微屏障可构造同步范型。可迁移的是数据布局、状态可见性和运算性质的协同选择,不是历史系统“最快”的产品结论。
相关知识:图数据强耦合;切边切点权衡;节点中心编程;BSP超级步;GAS拆开节点;同步异步取舍;邻接表适合遍历稀疏关系;在线查询与离线挖掘目标不同;图语义可映射到关系存储;实体关系建模保留方向与类型;区域副本平衡内存成本与延迟;两级缓存分担读取负载;本地读与主区域写分别优化;写穿缓存的保证有范围;PageRank累积邻居重要性;最短路沿有向边松弛;匹配约束区别最大与极大;图分片优化看全流程成本;切边优化同时约束负载;随机顶点分片的切边期望;切点以副本同步换边均衡;随机边分片的副本期望;二维哈希限制副本分散;图编程模型与执行范型分开;MR用按键聚集模拟图消息;Combiner须允许重复调用;迭代图计算避免重复搬运状态;异步作用域限定冲突范围;顺序等价依赖访问约束;停用顶点仍可被消息激活;主控调度与工作节点分工;检查点频率平衡正常与故障成本;示例算法不等于可运行实现;随机握手匹配只证到极大;主控接管还要恢复管理状态;长驻Map任务承载多轮图计算;图分片按目标切源点排序;滑动窗口把随机访问组织成顺序;共享边限制子图更新并行;双缓冲改变状态可见时点;连通分量传播最小标签;镜像收集主副本统一应用;增量缓存复用收集结果;变化阈值决定激活范围;微同步将GAS组合为超级步。
原书依据 · 48 处
- 图数据库:架构与算法 · 查看原书依据
- 图数据库:架构与算法 · 查看原书依据
- 图数据库:架构与算法 · 查看原书依据
- 延伸阅读 · 查看原书依据
- 图数据库:架构与算法 · 查看原书依据
- 图数据库:架构与算法 · 查看原书依据
- 图数据库:架构与算法 · 查看原书依据
- 图数据库:架构与算法 · 查看原书依据
- 图数据库:架构与算法 · 查看原书依据
- 图数据库:架构与算法 · 查看原书依据
- 图数据库:架构与算法 · 查看原书依据
- 图数据库:架构与算法 · 查看原书依据
- 图数据库:架构与算法 · 查看原书依据
- 图数据库:架构与算法 · 查看原书依据
- 图数据库:架构与算法 · 查看原书依据
- 图数据库:架构与算法 · 查看原书依据
- 图数据库:架构与算法 · 查看原书依据
- 图数据库:架构与算法 · 查看原书依据
- 图数据库:架构与算法 · 查看原书依据
- 图数据库:架构与算法 · 查看原书依据
- 图数据库:架构与算法 · 查看原书依据
- 图数据库:架构与算法 · 查看原书依据
- 图数据库:架构与算法 · 查看原书依据
- 图数据库:架构与算法 · 查看原书依据
- 图数据库:架构与算法 · 查看原书依据
- 图数据库:架构与算法 · 查看原书依据
- 大规模批处理系统 · 查看原书依据
- 图数据库:架构与算法 · 查看原书依据
- 图数据库:架构与算法 · 查看原书依据
- 图数据库:架构与算法 · 查看原书依据
- 图数据库:架构与算法 · 查看原书依据
- 图数据库:架构与算法 · 查看原书依据
- 图数据库:架构与算法 · 查看原书依据
- 图数据库:架构与算法 · 查看原书依据
- 图数据库:架构与算法 · 查看原书依据
- 图数据库:架构与算法 · 查看原书依据
- 图数据库:架构与算法 · 查看原书依据
- 图数据库:架构与算法 · 查看原书依据
- 图数据库:架构与算法 · 查看原书依据
- 图数据库:架构与算法 · 查看原书依据
- 图数据库:架构与算法 · 查看原书依据
- 图数据库:架构与算法 · 查看原书依据
- 图数据库:架构与算法 · 查看原书依据
- 图数据库:架构与算法 · 查看原书依据
- 图数据库:架构与算法 · 查看原书依据
- 图数据库:架构与算法 · 查看原书依据
- 延伸阅读 · 查看原书依据
- 图数据库:架构与算法 · 查看原书依据
第15章 机器学习:范型与架构
本章把分布式机器学习看作一个同时控制计算、通信、等待和收敛的系统问题。样本与模型规模分别推动数据并行和模型并行,两者可以组合;监督学习的损失、经验风险和正则化解释了优化目标,但训练目标降低不直接等于泛化变好。同步、异步和有界陈旧是不同执行约束,需结合具体优化算法讨论正确性。
MapReduce把一次局部计算与全局合并做成迭代作业,模型通过持久化在轮次间传递;BSP用计算、通信、屏障构成超级步,其代价由最慢计算和最大通信量限制。SSP进一步允许有限进度差,保证旧到某一时钟的全部更新可见,同时保留读己之写;这个视图可以混有更晚更新,不是单一时刻快照。
历史架构各自减少不同开销:Oryx把离线训练与在线预测分层;Twister和HaLoop改造缓存、数据放置与通信;Spark以不可变RDD、选择性持久化和血缘恢复支持迭代复用,窄依赖可流水执行,Shuffle划分阶段。书中RDD定义、惰性缓存和公式按原论文及同节文字校正,不把历史性能比较推广为现行产品保证。MLBase再把任务声明转换为学习计划和分布式执行。
参数服务器把共享模型变成网络参数表,通过缓存减少访问,因此必须规定更新何时可见。时钟界CAP与值界VAP控制不同陈旧维度;SSPTable将读行、增量更新和时钟推进分离,再以线程缓存、进程缓存、服务器逐级满足新鲜度。GPU与MPI在本章只旁提,相关年代容量上限与发展判断不作为当前结论;引诗不作技术材料,末尾论文作为进一步阅读入口。
相关知识:分布式ML瓶颈;三种同步范型;数据模型并行;参数服务器;RDD支撑迭代;监督学习要验证泛化;损失函数编码误差;正则化约束模型复杂度;聚类依赖相似性定义;异步消除逐轮屏障;MR迭代显式传递模型;并行聚类要按样本加权;训练服务可以分别部署;BSP超级步分三阶段;BSP代价取决于最慢者;超级步边界适合检查点;SSP规定更新可见下界;SSP以等待限制进度差;陈旧度界不自动保收敛;迭代缓存需稳定数据位置;Twister用消息网络传结果;RDD转换创建新数据集;Action触发延迟计算;缓存声明不等于立刻装载;血缘重算只恢复所需分区;窄依赖看父分区去向;Shuffle划分执行阶段;MLBase搜索学习执行计划;参数表缓存需一致性规则;SSP规定更新可见下界;值界VAP限制未传播增量;SSPTable分离增量与推进;参数读取逐层检查新鲜度;缓存让快慢线程区别访问。
原书依据 · 36 处
- 机器学习:范型与架构 · 查看原书依据
- 机器学习:范型与架构 · 查看原书依据
- 机器学习:范型与架构 · 查看原书依据
- 延伸阅读 · 查看原书依据
- 机器学习:范型与架构 · 查看原书依据
- 延伸阅读 · 查看原书依据
- 机器学习:范型与架构 · 查看原书依据
- 机器学习:范型与架构 · 查看原书依据
- 机器学习:范型与架构 · 查看原书依据
- 机器学习:范型与架构 · 查看原书依据
- 机器学习:范型与架构 · 查看原书依据
- 机器学习:范型与架构 · 查看原书依据
- 机器学习:范型与架构 · 查看原书依据
- 机器学习:范型与架构 · 查看原书依据
- 机器学习:范型与架构 · 查看原书依据
- 机器学习:范型与架构 · 查看原书依据
- 机器学习:范型与架构 · 查看原书依据
- 机器学习:范型与架构 · 查看原书依据
- 机器学习:范型与架构 · 查看原书依据
- 机器学习:范型与架构 · 查看原书依据
- 机器学习:范型与架构 · 查看原书依据
- 机器学习:范型与架构 · 查看原书依据
- 机器学习:范型与架构 · 查看原书依据
- 机器学习:范型与架构 · 查看原书依据
- 机器学习:范型与架构 · 查看原书依据
- 机器学习:范型与架构 · 查看原书依据
- 机器学习:范型与架构 · 查看原书依据
- 机器学习:范型与架构 · 查看原书依据
- 机器学习:范型与架构 · 查看原书依据
- 机器学习:范型与架构 · 查看原书依据
- 机器学习:范型与架构 · 查看原书依据
- 机器学习:范型与架构 · 查看原书依据
- 机器学习:范型与架构 · 查看原书依据
- 机器学习:范型与架构 · 查看原书依据
- 机器学习:范型与架构 · 查看原书依据
- 机器学习:范型与架构 · 查看原书依据
第16章 机器学习:分布式算法
本章围绕六类任务解释如何把算法本身拆成分布式执行。广告点击率预估先用共享特征训练逻辑回归,而不是给稀疏的每个查询广告组合单独估率;出价与CTR乘积可比较每次展示期望收入,eCPM按金额解释还须乘1000。LR训练涉及损失、正则和优化方向,L1在零处不可微,不能直接把后续光滑梯度公式当成整个L1目标的导数。并行SGD示例是完整数据上的独立轨迹求均值,二维批量LR则同时划分样本与特征,先沿样本行归并完整内积,再沿特征列归并梯度。
推荐任务用用户商品潜在因子内积拟合已观测评分。ALS交替固定一个因子矩阵,独立解另一侧的正则线性子问题,使同阶段更新可并行;加权惩罚依观测次数调整,缺失评分不等于零分。学习排序还须明确Pointwise、Pairwise与Listwise的训练单位,查询文档特征和相关性标签进入训练,线上通常对召回候选重排。LambdaRank把文档对梯度按交换排名的指标收益缩放,更新方向必须相反;LambdaMART逐轮用树拟合这些伪响应。候选树互评降低通信,却不能保留与集中式逐节点训练完全相同的结果。
文本相似性从文档对转向共词倒排,两个MR阶段分别构建词表和累加文档对贡献,省去大量零乘积。内积只有在相应归一化后才是余弦;高DF词会产生组合爆炸,剪枝虽省IO也会改变结果。社交图谱聚类把对称非负相似图转为拉普拉斯谱嵌入,再对节点行向量聚类。拉普拉斯的非负是特征值性质,不是逐元素非负;稀疏近邻图改变连通与谱,须处理对称和零度节点。MR构图、MPI求特征向量、并行K-means可按阶段混用,数据搬移成本也要计入。
深度学习部分是出版时的DBN预训练与DistBelief路线,不能把当年的GPU规模、浅层类比和预训练方式当当前必然规律。DistBelief同时支持数据与模型并行,Downpour通过副本和参数分片双重异步及不同拉推周期提高吞吐,Sandblaster则按一轮全量梯度推进批优化,由协调器分解向量运算并调度细粒度数据片。这些算法具体机制沿用前章并行与参数服务器基础,避免另造同义定义。
广告目标、概率与并行优化:eCPM排序须明确计量单位;逻辑回归把特征映为概率;L1目标不能直接套光滑梯度;优化方向与曲率成本有关;限量历史替代完整海森矩阵;按更新粒度选择训练方式;独立SGD副本末尾求均值;二维切分同时分样本与特征;先归并内积再分列梯度;CTR稀疏学习。
矩阵分解与交替最小二乘:低维因子拟合稀疏评分;评分次数加权正则惩罚;交替解用户与商品子问题;矩阵分解并行。
学习排序及候选树训练:排序训练单位有三种;召回候选后再学习重排;Lambda梯度需保留方向;提升树逐轮拟合排名梯度;学习排序并行。
文本倒排与候选规模:文档内积不自动等于余弦;两次MR累加共词贡献;高频词剪枝须评估精度;倒排算相似。
谱聚类与混合并行:社交图对称化决定相似关系;拉普拉斯半正定不等于逐项非负;特征向量嵌入后按行聚类;稀疏近邻图改变谱计算对象;按阶段混合MR与MPI。
历史预训练与DistBelief算法:无监督预训练是历史训练路线;分别控制拉参数与推梯度周期;全量梯度齐备后推进批优化;参数分片执行向量操作;细粒度数据调度减轻拖尾;副本计算与参数操作分工;深度模型并行。
进一步阅读:eCPM排序须明确计量单位;逻辑回归把特征映为概率;L1目标不能直接套光滑梯度;优化方向与曲率成本有关;限量历史替代完整海森矩阵;按更新粒度选择训练方式;独立SGD副本末尾求均值;二维切分同时分样本与特征;先归并内积再分列梯度;低维因子拟合稀疏评分;评分次数加权正则惩罚;交替解用户与商品子问题;排序训练单位有三种;召回候选后再学习重排;Lambda梯度需保留方向;提升树逐轮拟合排名梯度;文档内积不自动等于余弦;两次MR累加共词贡献;高频词剪枝须评估精度;社交图对称化决定相似关系;拉普拉斯半正定不等于逐项非负;特征向量嵌入后按行聚类;稀疏近邻图改变谱计算对象;按阶段混合MR与MPI;无监督预训练是历史训练路线;分别控制拉参数与推梯度周期;全量梯度齐备后推进批优化;参数分片执行向量操作;细粒度数据调度减轻拖尾;副本计算与参数操作分工;CTR稀疏学习;矩阵分解并行;倒排算相似;学习排序并行;深度模型并行。
原书依据 · 36 处
- 机器学习:分布式算法 · 查看原书依据
- 机器学习:分布式算法 · 查看原书依据
- 机器学习:分布式算法 · 查看原书依据
- 机器学习:分布式算法 · 查看原书依据
- 机器学习:分布式算法 · 查看原书依据
- 机器学习:分布式算法 · 查看原书依据
- 机器学习:分布式算法 · 查看原书依据
- 机器学习:分布式算法 · 查看原书依据
- 机器学习:分布式算法 · 查看原书依据
- 机器学习:分布式算法 · 查看原书依据
- 机器学习:分布式算法 · 查看原书依据
- 机器学习:分布式算法 · 查看原书依据
- 机器学习:分布式算法 · 查看原书依据
- 机器学习:分布式算法 · 查看原书依据
- 机器学习:分布式算法 · 查看原书依据
- 机器学习:分布式算法 · 查看原书依据
- 机器学习:分布式算法 · 查看原书依据
- 机器学习:分布式算法 · 查看原书依据
- 机器学习:分布式算法 · 查看原书依据
- 机器学习:分布式算法 · 查看原书依据
- 机器学习:分布式算法 · 查看原书依据
- 机器学习:分布式算法 · 查看原书依据
- 机器学习:分布式算法 · 查看原书依据
- 机器学习:分布式算法 · 查看原书依据
- 机器学习:分布式算法 · 查看原书依据
- 机器学习:分布式算法 · 查看原书依据
- 机器学习:分布式算法 · 查看原书依据
- 机器学习:分布式算法 · 查看原书依据
- 机器学习:分布式算法 · 查看原书依据
- 机器学习:分布式算法 · 查看原书依据
- 机器学习:分布式算法 · 查看原书依据
- 机器学习:分布式算法 · 查看原书依据
- 机器学习:分布式算法 · 查看原书依据
- 机器学习:分布式算法 · 查看原书依据
- 机器学习:分布式算法 · 查看原书依据
- 机器学习:分布式算法 · 查看原书依据
第17章 增量计算
增量计算要同时处理新增数据和被其影响的旧结果,输入变化少不代表影响范围一定小。变化传播沿依赖更新受影响状态,结果复用则从不变部分出发缓存已有工作。Hadoop增量框架常复用旧Map输出,但只在Map输入和逻辑及依赖稳定时安全;输入切分、旧贡献撤销和中间文件调度都影响正确性。节省工作量也不必同幅缩短延迟,书中10%等数字只是特定任务的测量。
Percolator把Bigtable单行事务扩展为多版本快照隔离事务,再用列观察/通知组织局部更新,和全局批统计互补。快照隔离防止并发同Cell写写冲突,却不保证可串行化。转账示例中张三10元、李四2元,划7元后应为3和9;两次独立写中断会破坏12元守恒。协议先写两行data与锁,secondary带primary位置,再以primary写记录作为提交决定点,最后完成secondary。数据开始版本与提交可见记录分离,读者按快照范围找版本;遇残锁时primary已提交则前滚,否则同步判断后可回滚,不能统一清锁。该原子边界仍不替代余额业务校验或请求幂等。
观察者由列变化触发事务并可引起后续变化,但通知可合并且函数执行不等于提交,不能替代逐计费事件日志。Kineograph把流式图维护与快照上的增量挖掘分离,用来源进度向量确定可计算边界,再让节点变化按规则沿邻边传播;阈值会带来近似与收敛条件。DryadInc在执行前识别可复用结果并改写DAG,用缓存替代重算,指纹定位仍须满足输入、程序和配置兼容,80%~90%提速不具普遍性。
增量目标与计算复用条件:Map复用依赖逻辑稳定;输入切分显式区分新旧数据;省计算不等于按比例缩短延迟;增量计算目标;变化传播模式;结果缓存复用。
Percolator事务、转账与通知:局部增量与全局批算互补;快照隔离只排除部分并发异常;两步转账中断会破坏总额;主记录提交保护转账原子性;版本值与提交记录分开存储;残锁清理先查询主提交状态;按快照查提交版本与冲突锁;观察通知驱动后续局部更新;多次列更新可能合并通知;Percolator机制。
Kineograph快照与变化传播:图更新与快照计算分离;进度向量给快照确定边界;变化阈值控制图上传播范围。
DryadInc缓存改图:结果指纹不替代复用条件。
进一步阅读:Map复用依赖逻辑稳定;输入切分显式区分新旧数据;省计算不等于按比例缩短延迟;局部增量与全局批算互补;快照隔离只排除部分并发异常;两步转账中断会破坏总额;主记录提交保护转账原子性;版本值与提交记录分开存储;残锁清理先查询主提交状态;按快照查提交版本与冲突锁;观察通知驱动后续局部更新;多次列更新可能合并通知;图更新与快照计算分离;进度向量给快照确定边界;变化阈值控制图上传播范围;结果指纹不替代复用条件;增量计算目标;变化传播模式;结果缓存复用;Percolator机制。
附录A 分布式系统常用硬件性能指标
硬件附录用拓扑、存储层次及访问延迟帮助架构估算。原图已逐张阅读,具体设备容量、带宽和延迟属于出版时的示意量级。分析需要统一指标与单位:单次访问延迟不等于聚合吞吐,跨机架路径也不自动意味着整个集群性能下降。
附录把单机、机架和集群连接关系作为数据访问路径的基础:本地访问、同机架访问与跨机架访问会经过不同设备和链路。它提示架构设计关注数据位置及链路瓶颈,而不是所有网络必然具有相同层级和超售比。图A-1的40~80台机架规模属于历史示意,不作为容量规范。 见拓扑层次影响数据访问成本。
缓存、内存、磁盘和远端存储在容量、访问延迟及带宽上呈不同取舍。比较时应区分单次访问延迟、单链路带宽与集群总吞吐;更大总容量可能伴随更长访问路径,却不能据此断言集群整体吞吐必定下降。图A-2的2014年容量与网络数值仅作层次示例,具体设计应测量目标设备与负载。 见比较存储层次先统一指标。
目的:在设计早期估算访问路径成本。图A-3给出历史量级,如内存访问约100ns、数据中心往返约500000ns、磁盘寻道约10000000ns;先统一单位(1ms=1000000ns),再按次数和路径估算是否值得批量化或减少远程访问。它不是当前硬件基准,也不包含所有排队、缓存命中和并发影响;本次未运行性能测试。 见历史延迟表用于数量级估算。
附录B 延伸阅读
延伸阅读附录逐一点评经典论文、系统和书籍。下列讲解严格限于本书作者所介绍的贡献与边界:多数机制已在正文章节有唯一primary,附录只补secondary及阅读路线;仅有名气或市场排名的条目登记参考。除实际核过的官方资料外,本轮不宣称已逐篇阅读这些原论文。
Paxos:该段强调Paxos影响和阅读优先级,未展开新的安全性推导;作为论文参考登记,不以名气追加知识卡。
Raft:Raft把可理解性和实现细节的确定性作为设计目标,提醒选型不只比较抽象功能,也要评估实施时能否清楚处理边界。 见Raft用任期简化。
Dynamo:Dynamo把一致性哈希、反熵、Merkle树、向量时钟及读写仲裁组合为实用KV系统。组成技术并非各自新发明,价值还在协同组织及对复杂P2P管理的取舍。 见并发版本交给业务合并。
MongoDB:此处以流行和适用范围推荐MongoDB,没有补充独立实现机制;市场地位限于原书时期,登记项目参考。
RAMCloud:RAMCloud用内存保存服务数据,并借助外存备份平衡成本与恢复能力;低延迟目标不能脱离网络、恢复及备份约束来解释。 见内存库成本悖论。
Redis:Redis推荐点评强调单机效率和灵活数据结构,分布式部分的不足是原书年代评价,不作为当前Sentinel或Cluster能力判断。 见Redis主从边界。
GFS:GFS围绕大量网页存储构建基础文件服务,并成为上层数据处理平台的基石;其意义在与负载匹配的设计,而不只是规模数字。 见按负载设计FS。
Haystack:Haystack针对海量图片对象的访问和管理成本设计存储,展示文件接口以外的对象工作负载取舍;并非任何对象存储都必然采用相同索引。 见Blob元数据进内存。
Reed-Solomon:纠删码用编码冗余减少完整副本所需空间,恢复却可能需要读取多个剩余块。成本评估应同时考虑存储和恢复路径。 见纠删码冷数据。
LRC:局部重建码关注恢复少量损坏块时的网络开销,以增加局部分组的冗余换取较少的数据搬运;不能仅比较总冗余比例。 见局部恢复用额外冗余换IO。
Bigtable:Bigtable把大规模结构化数据模型与下层文件、协调等服务组合,承接海量文件存储并向应用提供更合适的数据组织。 见BigTable三维表。
Cassandra:Cassandra把Bigtable风格模型与P2P、Dynamo相关机制结合,说明数据模型和底层复制分片架构是可分别取舍的设计维度。 见Cassandra融合多层设计。
Spanner:Spanner点评强调全球部署和事务能力。应将跨地域一致性放回复制仲裁、时间不确定性及故障条件,不能理解成任意数据中心同时失效仍无条件可用。 见区域层次与数据放置分工。
Databus:数据总线把源数据的已提交变化通知给关注它的下游,减轻各应用重复扫描源库的负担;重放与消费正确性仍有独立边界。 见数据总线传播变化而非重复全量。
Chubby:粗粒度锁服务承担命名、协调和少量控制信息等职责,帮助上层大系统协调,而不是承接所有高频业务读写。 见粗粒度锁服务。
ZooKeeper:选主、配置、组成员和锁是协调服务的典型用途。选择已有协调系统能够复用经过设计的机制,却不能省略客户端会话与失败处理。 见协调系统定位。
YARN:YARN把资源管理从MapReduce专用主控中分离,为多类计算框架提供资源平台;它不是MapReduce应用本身,生态预测也应保留原书时间坐标。 见作业主控分离全局资源。
Omega:共享状态调度让多个框架观察资源并独立制定策略,以乐观控制应对竞争冲突;更完整的分类帮助比较集中式、两级与共享状态调度。 见共享状态冲突需重试。
Kafka:Kafka从日志收集扩展为分区化消息通道,保留日志与消费位置支持多种用途。吞吐与低延迟必须连同确认、保留和复制条件讨论。 见Kafka用分区日志承载消息。
MapReduce:MapReduce以批量数据并行模型影响后续平台,评价它时应同时看编程约束、数据搬运和故障重执行,而不是把批处理当作所有任务的统一答案。 见MapReduce边界。
Dryad:Dryad用有向无环任务图表达分阶段数据并行,较单个MapReduce作业能表示更一般的依赖;图表达更广不代表每种任务都更快。 见DAG执行层衔接表达与机器。
Storm:低时延数据处理关注持续到达事件及其状态、失败和交付语义。Storm在此是原书的重要开源入口,产品名本身不构成端到端一次处理的保证。 见流式常驻计算。
MillWheel:MillWheel把低延迟、容错及计算表达能力放入持续流处理平台的整体设计,适合与其他流系统比较保证及代价,不能只比较吞吐数字。
Hive:Hive将SQL式数据分析映射到Hadoop执行,降低既有数据仓库用户迁移门槛;原书对其MapReduce执行成本的评价有版本背景。 见Hive以SQL换MR。
Dremel:Dremel结合交互分析需要组织列式数据及分布式查询,影响后续SQL-on-Hadoop系统。借鉴相似架构不等于开源项目就是其源码公开版本。 见Dremel树形聚合。
Impala:Impala是原书列举的交互式SQL系统。性能领先需要完整工作负载与环境证据,点评中最好排名只保留为历史评价,不作为当前选型结论。
Pregel:Pregel将图计算组织为BSP式顶点迭代和消息交换,适合表达图依赖计算;终止、组合器及具体算法正确性仍需独立条件。 见BSP超级步。
PowerGraph:PowerGraph点评明确补充它能组织同步与异步两种计算。结合第14章可区分GAS接口和同步策略;效率排名保留2014语境,不能由称赞推导所有图都更快。 见微同步将GAS组合为超级步。
Petuum:参数服务器为迭代收敛学习共享参数,需权衡陈旧读取、同步成本和算法收敛条件;海量参数数字本身不能证明通用性能。 见参数服务器。
Spark:RDD以可重建的数据抽象支持迭代计算,内存复用和容错依赖数据依赖关系,不是把全部数据永久放内存。 见RDD支撑迭代。
Scaling Up Machine Learning:这部文集把MPI、GPU、MapReduce、Dryad等并行范型下的学习算法放在一起,提供按算法与执行环境比较的阅读路线;本轮仅阅读本书推荐点评。 见并行机器学习文集提供比较路线。
原书依据 · 52 处
- 延伸阅读 · 查看原书依据
- 延伸阅读 · 查看原书依据
- 延伸阅读 · 查看原书依据
- 数据复制与一致性 · 查看原书依据
- 延伸阅读 · 查看原书依据
- 数据复制与一致性 · 查看原书依据
- 延伸阅读 · 查看原书依据
- 分布式协调系统 · 查看原书依据
- 延伸阅读 · 查看原书依据
- 分布式协调系统 · 查看原书依据
- 延伸阅读 · 查看原书依据
- 集群资源管理与调度 · 查看原书依据
- 延伸阅读 · 查看原书依据
- 集群资源管理与调度 · 查看原书依据
- 延伸阅读 · 查看原书依据
- 内存KV数据库 · 查看原书依据
- 延伸阅读 · 查看原书依据
- 内存KV数据库 · 查看原书依据
- 延伸阅读 · 查看原书依据
- 分布式文件系统 · 查看原书依据
- 延伸阅读 · 查看原书依据
- 分布式文件系统 · 查看原书依据
- 延伸阅读 · 查看原书依据
- 分布式文件系统 · 查看原书依据
- 延伸阅读 · 查看原书依据
- 分布式文件系统 · 查看原书依据
- 延伸阅读 · 查看原书依据
- 列式数据库 · 查看原书依据
- 延伸阅读 · 查看原书依据
- 列式数据库 · 查看原书依据
- 延伸阅读 · 查看原书依据
- 大规模批处理系统 · 查看原书依据
- 延伸阅读 · 查看原书依据
- 大规模批处理系统 · 查看原书依据
- 延伸阅读 · 查看原书依据
- 流式计算 · 查看原书依据
- 延伸阅读 · 查看原书依据
- 交互式数据分析 · 查看原书依据
- 延伸阅读 · 查看原书依据
- 交互式数据分析 · 查看原书依据
- 延伸阅读 · 查看原书依据
- 图数据库:架构与算法 · 查看原书依据
- 延伸阅读 · 查看原书依据
- 图数据库:架构与算法 · 查看原书依据
- 延伸阅读 · 查看原书依据
- 机器学习:范型与架构 · 查看原书依据
- 延伸阅读 · 查看原书依据
- 机器学习:范型与架构 · 查看原书依据
- 数据通道 · 查看原书依据
- 延伸阅读 · 查看原书依据
- 分布式通信 · 查看原书依据
- 延伸阅读 · 查看原书依据
跨章综合
同一条数据链路需要同时考虑放置、复制、协调、通信和消费。分区可以增加并行度,却把跨分区关系推向更明确的协调;副本改善某些故障下的访问能力,却增加版本、恢复与写确认的选择。计算模型则把数据依赖、状态和失败重执行组织成不同形式,不能只按吞吐或框架流行度选型。
比较方案时先对齐工作负载、故障模型、顺序范围、数据保留与业务正确性,再看延迟、存储和网络代价。原书案例及伪码中的已知简化已在各章写作时限定:共识不是通用跨资源原子提交的简称,CDC不是消费者事务的自动保证,数学演示要保持同一数据与有限域条件。实践仅形成计划和实际首轮材料,不宣称系统已部署或性能已测。
发散与实践
保留两个有真实成熟实现的具体候选:LSM链路与Bloom源码/测试,各回答独立问题。分布式训练、图处理和增量计算缺少真实部署与任务目标,避免另造平台或通用性能实验;其机制保留知识卡。
已核验LevelDB官方1.23标签、实际读取源码/测试段并填写两份首轮映射;完整源码深读与后续实验未执行,无测量结果。
读LevelDB的LSM写读路径(计划:ideas/idea-001-读LevelDB的LSM写读路径.md;材料:ideas/materials/leveldb-lsm-first-pass.md);布隆过滤器源码与实测计划(计划:ideas/idea-002-实测布隆过滤器误判率.md;材料:ideas/materials/bloom-source-test-first-pass.md)。