可以做兼职的网站有哪些,网站的技术解决方案,wordpress 邮箱函数,论坛做视频网站有哪些背景
最近在阅读查询优化器的论文#xff0c;发现System R中对于Join操作的定义一般分为了两种#xff0c;即嵌套循环、排序-合并联接。在原文中#xff0c;更倾向使用排序-合并联接逻辑。
考虑到我的领域是在处理分库分表或者其他的分区模式#xff0c;这让我开始不由得…背景
最近在阅读查询优化器的论文发现System R中对于Join操作的定义一般分为了两种即嵌套循环、排序-合并联接。在原文中更倾向使用排序-合并联接逻辑。
考虑到我的领域是在处理分库分表或者其他的分区模式这让我开始不由得联想我们怎么在分布式场景应用这个Join逻辑对于两个不同库里面的不同表我们是没有办法直接进行Join操作的。查阅资料后发现原来早有定义即分布式联接算法。
分布式联接算法
跨界点处理数据即分布式联接算法常见的有四种模型Shuffle Join洗牌联接、Broadcast Join广播联接、MapReduce JoinMapReduce联接、Sort-Merge Join排序-合并联接。
接下来将进行逐一了解与分析以便后续开发的应用。
Shuffle Join洗牌联接
先上原理解释 Shuffle Join的核心思想是将来自不同节点的数据重新分发洗牌使得可以联接的数据行最终位于同一个节点上。 通常对于要联接的两个表会对联接键应用相同的哈希函数哈希函数的结果决定了数据行应该被发送到哪个节点。这样所有具有相同哈希值的行都会被送到同一个节点然后在该节点上执行联接操作。 可能解释完还是有点模糊举个例子有两张表分别以id字段进行分库操作且哈希算法相同为了简单这里只介绍分库场景分库分表同理。算法有很多种这里举例是hash算法那么这两张表的分片或许可以在同一个物理库中这样我们不需要做大表维度的处理我们可以直接下推Join操作到对应的物理库操作即可。
在ShardingSphere中这种场景类似于绑定表的定义如果两张表的算法相同可以直接配置绑定表的关系进行相同算法的连接查询避免复杂的笛卡尔积。
这样做的好处是可以尽量下推到数据库操作在中间件层面我们可以做并行处理适合大规模的数据操作。
但是这很理想有多少表会采用相同算法处理呢。
Broadcast Join广播联接
先上原理解释 当一个表的大小相对较小时可以将这个小表的全部数据广播到所有包含另一个表数据的节点上。 每个节点上都有小表的完整副本因此可以独立地与本地的大表数据进行联接操作而不需要跨节点通信。 举个例子有一张非常小的表A还有一张按照ID分片的表B我们可以在每一个物理库中复制一份表A这样我们的Join操作就可以直接下推到每一个数据库操作了。
这种情况比Shuffle Join甚至还有性能高效这种类似于ShardingSphere中的广播表的定义其存在类似于字典表在每一个数据库都同时存在一份每次写入会同步到多个节点。
这种操作的好处显而易见不仅支持并行操作而且性能极佳。
但是缺点也显而易见如果小表不够小数据冗余不说广播可能会消耗大量的网络带宽和资源。
MapReduce JoinMapReduce联接
先上原理解释 MapReduce是一种编程模型用于处理和生成大数据集其中的联接操作可以分为两个阶段Map阶段和Reduce阶段。 Map阶段每个节点读取其数据分片并对需要联接的键值对应用一个映射函数生成中间键值对。 Reduce阶段 中间键值对会根据键进行排序在某些实现中排序发生在Shuffle阶段和分组然后发送到Reduce节点。 在Reduce节点上具有相同键的所有值都会聚集在一起这时就可以执行联接操作。 MapReduce Join不直接应用于传统数据库逻辑而是适用于Hadoop这样的分布式处理系统中。但是为了方便理解还是用SQL语言来分析例如一条SQL
SELECT orders.order_id, orders.date, customers.name
FROM orders
JOIN customers ON orders.customer_id customers.customer_id;会被转换为两个SQL
SELECT customer_id, order_id, date FROM orders;
SELECT customer_id, name FROM customers;这个过程就是Map阶段即读取orders和customers表的数据并为每条记录输出键值对键是customer_id值是记录的其余部分。
下一个阶段可有可无即Shuffle阶段。如果不在这里排序可能会在Map阶段执行SQL时候排序/分组或者在接下来的Reduce阶段进行额外排序/分组。在这个阶段主要将收集到的数据按照customer_id排序分组以确保相同的customer_id的数据达到Reduce阶段。
Reduce阶段将每个对应的customer_id进行联接操作输出并返回最后的结果。
这种操作普遍应用于两个算法完全不相同的表单也是一种标准的处理模型在这个过程中我们以一张逻辑表的维度进行操作。这种算法可能会消耗大量内存甚至导致内存溢出并且在处理大数据量时会相当耗时因此不适合需要低延迟的场景。
额外补充
内存溢出场景普遍在如下场景
1.大键值对数量如果Map阶段产生了大量的键值对这些数据需要在内存中进行缓存以进行排序和传输这可能会消耗大量内存。
2.数据倾斜如果某个键非常常见而其他键则不那么常见那么处理这个键的Reducer可能会接收到大量的数据导致内存不足。这种现象称为数据倾斜。
3.大值列表在Reduce阶段如果某个键对应的值列表非常长处理这些值可能会需要很多内存。
4.不合理的并行度如果Reduce任务的数量设置得不合适太少或太多可能会导致单个任务处理不均匀从而导致内存问题。
我能想到的相应解决方案
•内存到磁盘的溢写当Map任务的输出缓冲区满了它会将数据溢写到磁盘。这有助于限制内存使用但会增加I/O开销。
•通过设置合适的Map和Reduce任务数量可以更有效地分配资源避免某些任务过载。具体操作可以将Map操作的分段比如1~100100200Reduce阶段开设较少的并发处理。
•优化数据分布比如使用范围分区range partitioning或哈希分区hash partitioning来减少数据倾斜。
Sort-Merge Join排序-合并联接
先上原理解释 在分布式环境中Sort-Merge Join首先在每个节点上对数据进行局部排序然后将排序后的数据合并起来最后在合并的数据上执行联接操作。 这通常涉及到多阶段处理包括局部排序、数据洗牌重新分发以及最终的排序和合并。 举个理解还是上面的SQL。
SELECT orders.order_id, orders.date, customers.name
FROM orders
JOIN customers ON orders.customer_id customers.customer_id;1.对orders表按customer_id进行排序。
2.对customers表按customer_id进行排序。
3.同时遍历两个已排序的表将具有相同customer_id的行配对。
这个就有点类似于原生的排序-合并联接了。也是数据库场景的标准处理办法。
对于已经排序的数据集或数据分布均匀的情况这种方法非常有效。如果数据未预先排序这种方法可能会非常慢因为它要求数据在联接之前进行排序。
当然这个算法也会造成内存溢出的场景解决方案如下
1.当数据集太大而无法一次性加载到内存中时可以使用外部排序算法。外部排序算法会将数据分割成多个批次每个批次单独排序然后将排序后的批次合并。这种方法通常涉及到磁盘I/O操作因此会比内存中操作慢。
2.对于合并步骤可以使用流式处理技术一次只处理数据的一小部分并持续将结果输出到下一个处理步骤或存储系统。这样可以避免一次性加载大量数据到内存中。
3.当内存不足以处理数据时可以使用磁盘空间作为临时存储。数据库管理系统通常有机制来处理内存溢出比如创建磁盘上的临时文件来存储过程中的数据。
4.在分布式系统中可以将数据分散到多个节点上进行处理这样每个节点只需要处理数据的一部分从而减少单个节点上的内存压力。
作者京东科技 张俊杰
来源京东云开发者社区 转载请注明来源
