同行分析优化

用户头像
誓约·追光者
关注
发布于: 2020 年 08 月 17 日

优化源于痛点(┬_┬)

有没有痛点取决于业务场景的需求;有多痛取决于当前方案对业务的契合度

让我们从业务场景①、当前方案②切入,联立①②来推导当前痛点③吧!

话不多说,开始分析



①业务场景:

1.同一时间段内出现在同一摄像头下的用户即为同行关系(不需要两个人同步出现在摄像头下,因为我司暂不支持在一张图片内一次性提取两个人,处理逻辑太麻烦了,还不如后面分析)

2.计算需要并行进行,每次计算一天的数据量,大约千万级



②当前方案:

将全部数据拉到内存,全局排序后按照时间段大小分块,然后通过滑动窗口进行计算,比如说时间段是10s,20.11.00到20.11.10为一个窗口,20.11.10到20.11.20为一个窗口,20.11.20到20.11.30为一个窗口,同一窗口直接判定同行,相邻窗口间需要计算确定是否同行,计算后还要每两个窗口之间去重



③当前痛点:

1.千万级数据拉到内存,会对内存造成一定压力,因为并不是只有这一个服务需要使用内存

2.计算过程大量重复,去重逻辑繁琐,浪费大量算力



那么问题来了,是否存在什么更合适的方案来解决这些痛点呢?

我想,是有的。

根据痛点③,反推我们的预期目标④;

根据目标④,尝试推导出优化思路⑤;

落地思路⑤,成为最终的优化方案⑥



④预期目标

1.不占内存

2.避免重复计算,一键去重



⑤优化思路

1.不把数据全拉到内存全局排序就不会造成内存压力,所以我们直接在sql里dd分好片就行了

2.从数学上逻辑推导来解决重复计算问题,参考裂项相消法的思路



⑥优化方案

test:原表,存储需要计算的数据

①假定取一天数据,划分时间段是10s,我们可以把一天分成8640个块,然后按块处理。这些块就是我们需要的分块,不需要做排序再切片什么的

with source as(
select
id,
floor(unix_timestamp(time)/10) as time_part,
unix_timestamp(time)as time
from test
)

②假定有四个块,1234,那么我们需要计算的其实是相邻的块之间的时间差,也就是1和2,2和3,3和4,其他的11,22,33,44都直接就是我们需要的结果,把这些返回结果加起来,就是我们需要的答案。我们把数据复制一份,第一份是原本的1234,第二份-1变成0123,然后按块join,就能得到11(原本的2,即12),22(原本的3,即23),33(原本的4,即34),第一份再和自己join,就能得到11,22,33,44,加起来就是11,22,33,44,12,23,34,即我们需要的所有结果(下图所示,把-1换成+1,效果是等效的。图画的有些潦草,请勿见怪)

不知道为什么上传到这里是倒着的,我不太会弄,麻烦大家倒过来看...不好意思啊



with source as (
select
id,
floor(unix_timestamp(time)/10) as time_part,
unix_timestamp(time)as time
from test
),
target as (
select
id,
alias.time_part,
time
from source
lateral view explode(split(concat(time_part-1,',',time_part),',')) alias
as time_part
)

上述操作其实是一步到位,把所有数据块平移了一个单位然后和原本的数据库union了,实现方式为explode,alisas是别名。通过这种方式我们能直接得到需要计算的所有数据

③配对,计算

with source as (
select
id,
floor(unix_timestamp(time)/10) as time_part,
unix_timestamp(time)as time
from test
),
target as (
select
id,
alias.time_part,
time
from source
lateral view explode(split(concat(time_part-1,',',time_part),',')) alias
as time_part
)
select id from
source join target
on source.time_part=target.time_part
where abs(source.time-target.time)<10

以上就是我的优化方案,所有sql均在spark.sql中执行,优点如下:

1.数据库内直接分好块,不占内存,来再多数据也没影响

2.完美解决边界点问题,没有任何遗漏计算也没有任何重复计算

3.具备可延展性,可以轻松把逻辑延展到多维空间

以上就是本次优化从思考到实现的全过程啦,希望大家喜欢(≧▽≦)



发布于: 2020 年 08 月 17 日 阅读数: 42
用户头像

誓约·追光者

关注

还未添加个人签名 2020.08.11 加入

还未添加个人简介

评论

发布
暂无评论
同行分析优化