同行分析优化

关注
发布于: 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.具备可延展性，可以轻松把逻辑延展到多维空间
以上就是本次优化从思考到实现的全过程啦，希望大家喜欢(≧▽≦)
﻿