排序与内存聚合
统计最受欢迎的 URL,可以用 Unix 管道排序计数,也可以用脚本在内存哈希表中计数,策略截然不同。哈希表方案取决于工作集:不同 URL 能装进内存就很快,超出内存就失效。排序方案能高效利用磁盘:数据块在内存中排好后写成段文件,再把有序段合并,这与[[SSTable的排序收益]]原理相同。GNU sort 能自动溢写到磁盘并利用多核并行,简陋的命令链因此能处理远超内存的数据集。
主题对照
同一批数据要算成什么:分组与归约怎样切、连接在 Map 侧还是 Reduce 侧做、排序与抽样怎样只走一遍、作业图怎样抽象成可复用的片段(管道图、宏、组合聚合),以及这些写法的代价与边界。
统计最受欢迎的 URL,可以用 Unix 管道排序计数,也可以用脚本在内存哈希表中计数,策略截然不同。哈希表方案取决于工作集:不同 URL 能装进内存就很快,超出内存就失效。排序方案能高效利用磁盘:数据块在内存中排好后写成段文件,再把有序段合并,这与[[SSTable的排序收益]]原理相同。GNU sort 能自动溢写到磁盘并利用多核并行,简陋的命令链因此能处理远超内存的数据集。
Map把输入记录转换成中间键值,框架按中间键分组后交给Reduce。单词统计用单词作键,页面PV用URL作键;分组键定义“哪些数据必须一起计算”,输入记录ID未必是正确聚合键。选错键即使每个函数都运行成功,也会得到语义错误的统计结果。
链接反转时Map遍历每个网页的出链,输出目标URL到来源URL,再由Reduce汇集来源列表。倒排索引同理把文档中的不同词映射到文档ID。需要集合语义时先处理同一文档内重复词,避免把文档频率误算为词出现次数;这类模式聚合的是记录关系,而不是数值求和。
关系代数的集合投影先选出列,再合并相同元组。映射到MapReduce时,可用整个投影结果作为键,让Reduce对每个键只输出一次。这个步骤实现的是去重语义;普通SQL查询通常保留重复行,只有要求DISTINCT等去重行为时才能直接采用,不能因“只选几列”就删掉重复结果。
可联系[[子查询改写须保留重复语义]]理解条件与边界。
按A分组求B之和时,Map输出(A,B),Reduce为每个A累计B。若执行端用哈希表维护各组状态,Shuffle只需保证同键到同一任务,无须先把所有键排成顺序。少排序不改变同键汇合的要求;需要有序输出时仍须另加排序,也不能直接平均各分区的平均值。
可联系[[局部聚合须保留合并状态]]理解条件与边界。
Combiner是可选的局部合并,框架可能不执行或执行多次,因此结果必须不依赖调用次数和分组方式。求和、最值等适用,平均值应传(sum,count)后合并,不能简单平均各分区均值;中位数也不能以局部中位数直接替代。它减少Shuffle,但不能改变计算语义。
Map按对象键输出统计量,Reduce合并同键结果;计数与求和可局部预聚合,平均值保存累计和与样本数,最终再相除。分母为零和数值范围要有定义。中间格式应包含足够信息,不能只保留已舍入均值,否则分区大小不同会使结果偏离整体平均。
若每条记录只需独立判断谓词并输出满足条件的原记录,可以把过滤全部放在Map,不配置无用Reduce。用于清洗日志或提取目标用户记录时,过滤条件本身必须明确;一旦涉及跨记录去重、分组或全局排名,就不能再按独立过滤处理。
在记录分数已经确定且排序规则一致时,各Map保留局部TopK,最终Reduce从候选并集中取全局TopK。并列时应统一比较和保留规则。若分数是需要跨分片累加的词频,必须先得到正确的全局计数,不能先按局部词频截断就声称保留全局热门词。
按日期或类别选分区键,可以把海量记录分组输出成后续易消费的数据集合。分类键和输出位置需与Reducer分区规则对应,关注热点类别与过多小文件;哈希分区分散键,不保证不同键的业务类别自动对应独立文件,更不自动提供全局顺序。
分布式词频统计可把不同文件交给工人,各工人先按词生成局部次数表,工头再把同一词的次数相加。局部先聚合,减少了需要集中处理的原始文本量。示例在单机给多个工人同一个文件只是演示调用;真实总数要求各工人的输入片段不重复、也不遗漏。发散:并行化前先写清输入划分与合并规则,才能验证结果正确。
书中的影响力分数先为每个回应者找出他回应次数最多的人,再统计某人被多少人选为首要影响者。两步分别按回应者和影响者分组,不能把所有回应次数简单相加当作同一指标。这一例子说明:分析问题的业务定义决定分组键及计算阶段,框架负责并行化,不能替你选择正确指标。
与[[MapReduce抽象]]的联系:影响力业务定义决定两次按不同键分组,框架只负责执行。
全局计数若把每条记录都送到一台机器,分布式输入最终仍被单点归约限制。可合并聚合器先在各节点求局部计数,再把少量局部值相加得到总数。关键条件是部分结果能够正确组合;计数和求和满足,其他聚合须分别判断,不能认为所有计算都能不改变语义地提前归约。
与[[MapReduce抽象]]的联系:局部可合并结果减少全局归约节点需要接收的记录。
JCascalog聚合依据查询中仍需保留的输出变量来分组。输出person与count表示逐人计数,输出gender与count则表示按性别计数;中途使用过但不再输出的字段不自然成为分组维度。输出声明既决定结果形状,也决定统计粒度,修改字段可能改变业务含义,而不只是少显示一列。
与[[粒度决定弹性]]的联系:输出字段决定聚合分组,具体落实粒度选择。
函数处理一条输入时可以输出零条、一条或多条记录。零输出可过滤解析失败的字符串,一输出可增加转换后的字段,多输出可将句子展开成多个单词,并为每个输出保留原输入的副本。输入输出基数影响后续计数,不能把“转换函数”一律理解为不增不减行数。
与[[管道元组字段保持不可变]]的联系:字段不可变变换仍可改变输出记录数量。
普通聚合器逐条接收组内记录并维护状态,可与其他聚合器组合;缓冲器拿到整组迭代器,写法直接,但书中接口限制其与其他聚合器组合。并行聚合器则先把输入变成局部结果,再合并局部结果,减少网络传输。若与普通聚合器混用而不能在map侧预聚合,仍可得到正确输出,却失去这部分性能收益。
与[[部分聚合缩小全局瓶颈]]的联系:聚合器与缓冲接口影响是否能够局部预聚合。
浏览量可把互不重叠时间段的事件数相加;独立访客数却不能,因为同一个人可能在多个时间桶出现。跨桶统计须处理访客集合的并集,而不只是把各桶人数相加。若保存完整集合太贵,可以用可合并的近似摘要,但必须让业务接受估计误差。
与[[去重是语义问题]]的联系:跨桶去重不能直接相加已经汇总的人数。
只做映射的分解作业可能让每个mapper都为多种记录类型创建文件,输出文件数量随mapper数与类型数相乘。书中故意增加归约阶段,用可配置的reducer数控制输出写入端,再合并小文件。多一个阶段虽然增加数据重排,却可能减少元数据及文件句柄压力;少阶段不必然代表整体更快。
与[[小文件重复调度开销]]的联系:受控归约减少mapper乘类型导致的输出小文件膨胀。
计算全局前三词时,若把全部更新后的词计数发给一个节点,会形成随输入增长的瓶颈。各分区先选自己的前三,再把这些候选交给全局节点合并,可把每批跨节点汇总量限制到分区数乘K。在书中每词由唯一任务维护、计数只增的条件下,未入局部前三的词不会超过该分区三个更大候选;计数下降或任意删除则需要重新评估维护方法。
与[[部分聚合缩小全局瓶颈]]的联系:分区先选局部前K再合并缩小全局排名汇总流量。
枚举长度为 M、每位有 n 个取值的序列时,可按首位把搜索树切为 n 个互不重叠的子树,分给 n 个工人;按前两位可切为 n² 个子树。每个工人只遍历剩余后缀,工头合并计数。拆分降低单个任务的递归深度,不改变总结果数;工人数量、调度和输出开销仍约束收益。
用交错级数近似 π 时,每一项只由自己的序号决定,无需等待前一项的计算结果。可把项的索引范围切为互不重叠的区间,让工人各算部分和,再由工头汇总。关键是覆盖全部索引且不重复;并行化缩短求和时间的可能性来自项之间的独立性。
两侧记录在Map抽取连接键并附来源标记,Shuffle让同键记录抵达同一Reduce,再按来源构建集合并匹配。重复连接键可能产生多对多的乘积输出,需评估内存与结果规模。分区和标签正确只保证数据相遇,外连接、重复处理等业务语义仍须由用户逻辑实现。
一侧数据足够小且可完整装入每个Mapper内存时,先载入并按连接键建哈希表,再逐条扫描大表匹配,避免大表Shuffle。小表大小需考虑并发Mapper的总内存和版本一致性,多值键要保留全部匹配;超出内存或频繁变化的小表不宜直接照搬这一模式。
原图Mapper先在initialize中加载小表R到哈希结构H,再在map(join_key k,tuple l)中查出同键记录并输出连接结果。初始化准备可复用查找结构,逐记录函数只做探测与组合。方法图仅表达原图真实名字和参数,原图未给出返回类型,不能擅自补上接口契约。
结构图:
classDiagram
class Mapper {
initialize()
map(join_key k, tuple l)
}
Mapper ..> H : 小表哈希索引
note for Mapper "原图未标返回类型;不推断框架版本签名"
跨节点连接先解决同键记录在哪里相遇:大表双方可按连接键重新分区;较小一方的分区可在内存建哈希表,再扫描另一方匹配。有索引时也可逐条远程查找;整张小表可缓存到工作进程,供多个任务复用。选择时比较内存、网络与查询次数。重复连接键应输出两侧匹配行的全部组合,不能只配成一一对应。
可联系[[连接算法按相同键配对]]理解条件与边界。
批处理中关联活动日志与用户档案,不能逐条查询远程数据库:吞吐量会被网络往返拖垮,远程数据随时变化还会让结果不确定。更好的做法是把两侧数据都放进分布式文件系统,Mapper 各自提取连接键,框架按键分区排序后,相同键的记录自然相邻,进入同一次 Reducer 调用,称为排序合并连接。这把从正确机器取数据的网络问题,与拿到数据后的处理逻辑分开,Reducer 可以是简单的单线程代码。
[[排序合并连接]]要求同一键的记录进同一 Reducer,但名人账号这类热键数据量远超其他键,处理它的 Reducer 会拖慢整个作业。解法是打破这一约束:Pig 的偏斜连接先抽样找出热键,再把热键记录随机分发给多个 Reducer,另一侧对应记录则复制到所有这些 Reducer;Hive 要求在表元数据中标注热键并单独存放。分组聚合可分两阶段:先随机分发做局部聚合,再由第二个作业合并出最终结果。
与[[排序合并连接]]不同,若能对输入做假设,Map 侧连接可省去排序与 Reducer。广播散列连接:小数据集能装进内存,每个 Mapper 启动时把它载入哈希表。分区散列连接:两侧按相同的键、哈希函数和分区数分区,每个 Mapper 只读两侧对应分区。Map 侧合并连接:两侧不仅分区相同,还各自按键排好序,Mapper 可直接归并扫描。代价是对输入大小、分区与排序做了更强假设,这些假设往往由前一个作业保证。
分布式连接:把逻辑连接拆成在集群各节点上运行的较小节点连接,MapReduce、BigQuery、Snowflake、Spark 都适用。
ETL → ELT:传统 ETL 依赖外部系统拉取、转换、清洗数据,再加载到数仓——这是由源(RDBMS 限制拉取速度)和目标(存储、CPU 受限)的限制驱动的。随着数仓性能和容量增长,ELT 变得普遍:抽取原始数据、最小转换后导入数仓,再在仓内清洗转换。
数据湖版 ELT 的陷阱:加载时完全不转换,甚至没有使用计划,假设将来某个时候再转换——这是数据沼泽的重要成因。Inmon 说他见过太多组织“先把数据放进去以后再转换”,结果六个月后数据从没被碰过。
作者认为 ETL 和 ELT 只应在微观层面(单个转换管道内)使用,而不是在宏观上为全组织标准化;应按具体情况选择适当技术。
连接依据公共键把不同记录的字段组合到一条输出中:内连接要求各相关输入有匹配,外连接可保留缺少某侧记录的键并用空值补齐。集合合并则把兼容形状的多组记录拼成一组,不是按键横向配对。操作名字相近,但决定了结果的行数、字段和缺失信息语义,不能互相替代。
与[[管道图思维]]的联系:连接和集合合并是管道中语义不同的数据组合操作。
点击箭头逐层展开,点击卡片标题查看详情。路径上下文仅用于连接层级,不计入主题卡片数。
来源书籍
分布式系统类
书籍类型:工程实践
清单覆盖 3/6
125 张卡片
来源书籍
书籍类型:未标注
424 张卡片
来源书籍
分布式系统类
书籍类型:经典原理
类别清单尚未核对
173 张卡片
来源书籍
书籍类型:经典原理
331 张卡片
来源书籍
分布式系统类
书籍类型:工程实践
清单覆盖 2/6
97 张卡片
来源书籍
书籍类型:工程实践
33 张卡片
来源书籍
分布式系统类
书籍类型:经典原理
类别清单尚未核对
194 张卡片
来源书籍
数据工程与数据架构方法类
书籍类型:工程实践
类别清单尚未核对
145 张卡片
主题索引
比较批处理、流式、交互式查询、图计算、分布式机器学习与增量计算的计算模型与取舍。
与 4 张主题卡片存在结构化链接;共享 1 个其他主题;来自相同书籍;属于相同分类
与 3 张主题卡片存在结构化链接;共享 1 个其他主题;来自相同书籍;属于相同分类
与 2 张主题卡片存在结构化链接;共享 1 个其他主题;来自相同书籍;属于相同分类
与 2 张主题卡片存在结构化链接;共享 1 个其他主题;来自相同书籍;属于相同分类
与 2 张主题卡片存在结构化链接;来自相同书籍;属于相同分类
与 2 张主题卡片存在结构化链接;来自相同书籍;属于相同分类