最新发布《数智时代的AI人才粮仓模型解读白皮书(2024版)》,立即领取! 了解详情
写点什么

流式计算优化指南:提高时效性

  • 2019-07-31
  • 本文字数:3323 字

    阅读完需:约 11 分钟

流式计算优化指南:提高时效性

什么是流式计算

在传统的数据处理流程中,总是先收集数据,然后将数据放到数据库中,当人们需要的时候通过查询对应的数据进行处理。这样看起来没什么大问题,但是当我们遇到以下场景的时候就有问题了。比如:金融风控,双十一抢购,推荐系统等,这类系统有一个共同的特点,就是对时效性要求非常高。


所谓“时光一逝不复返,往事只能回味“。我们举一个简单的例子,当前你的余额宝账户有 3000 块,你去商场消费了 2000。这时候触发支付宝结算,假设支付宝处理这笔数据需要 10 秒,而 10 秒之内,你接着又消费了 2000,这时候应该提示你余额不足了,但由于结算程序还在处理,实际上余额还有 3000,那么你这 2000 又结结实实可以消费了。10 秒后支付宝反应过来了,这时候钱已经扣了,找谁还钱去啊,这样引发了很大的金融风险。


其实还有一个简单的办法,支付宝在结账的时候(10 秒钟之内)禁止消费,又带来的问题是交易量下跌,这样的损失更加接受不了,所以这就对数据的实时处理要求非常高,这 1 秒的数据这 1 秒就要处理完,下一秒的数据可能又是其它的情况了。数据就像流水一样不断变化,我们需要实时的处理数据。


那么如何才能够提高流式计算的速度呢?

流式计算优化之拓扑排序

1. 流式计算

流式计算就是实时查询并且对数据进行计算,假设我们遇到了如下计算场景:


A = D + B;


B = C + E;


C = D + E。


我们需要计算得到 A 的值,如何才能最快的计算出结果呢?我们从以下几个方面来分析问题:

2. 单线程

如果是单线程的情况,我们只能线性的去执行任务,最开始计算 a = d + b,先计算 d,然后计算 b,而 b = c + e,只能再去计算 c,而 c = d + e。先计算出 d 和 e 相加得出 c,然后计算 c 加 e 得出 b,最后计算 d 加 b 得出 a。最后我们统计计算 a,一共做了多少次计算:


d 2 次


e 2 次


c 1 次


b 1 次


a 1 次


这里显而易见,我们做了 2 次重复计算。有 2 种方法去解决这个问题:一种是加缓存,一种是拓扑排序。

3. 缓存

增加缓存的方法如下,计算 a 的时候先计算 d 和 b,计算 d 之后把 d 先缓存,然后计算 b,由于 b=c+e,那么需要先计算 c,而 c=d+e,最后需要计算 d+e,而 d 已经缓存了直接从内存取出,再接着计算 e,放入缓存,这样计算 b=c+e 的时候只需要计算 c,e 直接从内存取出。缓存虽然可以解决上面的问题,但也有缺点,首先缓存需要占用内存空间,其次缓存都有淘汰机制,下面介绍一种更优的方法。

4. 拓扑排序

我们可以根据上述的关系,得到如下的依赖图:



Dependency Graph


实际上我们得到了一个 DAG 的图,可以看出如果要计算 a,我们需要先计算 d 和 b,而计算 b 需要计算 c 和 e,而计算 c 又需要计算 d 和 e,即一件事情依赖另外的一件。这样的例子在生活中有很多,比如早晨起来,你必须先穿袜子才能穿鞋子,而穿鞋子之前你必须得先穿上裤子。这些问题都可以用拓扑排序来解决,思路就是深度优先遍历,优先找出最底层的节点,然后找出次底层的,依次得出结果。最后我们会得到如下的顺序:d e c b a,即按照如下顺序计算,每个节点只需要计算一次,在不产生顺序冲突的同时,得出最短的计算时间。

5. 多线程

上面是单线程的情况,如果是多线程的情况,当然只要我们有足够的资源,多线程肯定是理论上计算时间最短的。但导致的一个问题就是重复计算,浪费计算资源,下面是多线程执行流程图:



即如果开启 6 个线程执行,那么最终执行的时间可能是 (这里假定 d 的执行时间比 e 长) d c b a,我们把 e 的计算时间给节省掉了,多线程的情况对缓存来说可以说是灾难性的后果,比如计算 a 开始的时候就开始计算 d 了,而计算 c 的时候 d 如果没有计算完,c 也取不到 d 的缓存,导致缓存可以说是没有太大用处。如果缓存可以取到,才可以节省计算资源。


如果我们按照如下思路,还可以进一步节省计算资源,在上面拓扑排序的基础上,加入层级的概念,比如:



加入层级之后,比如 d 和 e 的层数都是 4,那么 d 和 e 可以并行计算,而 c,b,a 的层级分别是 3,2,1,进行串行计算。这里很明显,如果层数相同的则进行并行计算,层数不同则串行计算,带来的好处一是节省计算资源,二是节省了计算时间,这才是最优解。

流式计算优化之 IO 合并

流式计算还有一种优化是对内存操作和 IO 操作做区分,并进行优化,比如上述情况,如果 d 和 e 开启并行计算,c,b,a 线性计算,从计算的角度来看待,确实是最优的计算方式。但是考虑到计算分为内存计算和 IO 计算,而且 IO 计算的延时比内存计算高几倍到十几倍,因此我们主要的策略就是对 IO 计算做优化,一个比较好的优化思路就是对 IO 做合并,或者对 IO 计算做缓存,下面主要讲述对 IO 计算合并。


还是用下面的例子,我们需要计算如下情况:


A = D + B;


B = C + E;


C = D + E。


根据依赖关系,我们可以得出如下 DAG 的节点图:



即 d,e,c,b,a,我们计算的顺序可以按照如下方式进行,我们先从简单点的情况,然后扩展到复杂的情况。

1. IO 合并

首先我们假设 d 和 e 都是 IO 计算,如果按照之前介绍的拓扑排序然后再并发的思路,那么我们会同时启动 2 个线程,分别计算 d 和 e。虽然多线程不会增加时间,但是多了一次 IO 操作,带来的影响就是 IO 是有瓶颈的,如果系统的 IO 操作变多,会导致系统抖动和延时,假如我们可以把 d 和 e 做 IO 合并,即一次就可以把 d 和 e 都读取出来,那么系统 IO 的容量就可以提高 1 倍(实际不到 1 倍的提升)。

2. IO 不能合并

有 2 种情况:


  1. 如果 d 和 e 是访问的不同的数据库,那么我们的 IO 不能做合并,我们就只能读取 2 次。

  2. 接着我们增加下 IO 合并的复杂程度,比如现在有 d,e,c 这 3 个节点是 IO 计算,d 和 e 可以做 IO 合并,而 c 需要等待 d 和 e 做 join 操作之后,才能确定读取哪些 IO,这样我们做 IO 合并的时候只能先把 d 和 e 做合并,而不能把 c 做合并,因为在 d 和 e 做 join 操作之后,我们才知道 c 要去查什么数据,因此也做不了合并。


不过上述问题也是可以优化的,这一部分的优化可以通过分支预测和预取操作来解决。


2 个数据做 join 操作就是找到 2 个数据集的合集部分,比如一个数据集是数学成绩,一个数据集是地理成绩,下面我们需要找出数学成绩大于 60 分,而且地理成绩大于 90 的学生,那么我们就是找到 2 个数据集的交集部分,即 2 个数据集做 join 操作。

流式计算优化之分支预测

1. 假设我们有如下计算场景:

if ( isWeekend) { readIO(A);} else { readIO(B);}
复制代码


可以看到,如果今天是周末,则读取 A,如果今天不是周末,则读取 B。由于 A 和 B 都是 IO 操作,比较耗时,如果 A 和 B 能够合并读取,那么我们当然很开心,我们只需要读取一次就可以了。假如 A 和 B 不能够做 IO 合并,那么遇到的问题是,我们需要先判断是否是周末才能够明白到底去读取哪个 IO,假如我们引入分支预测机制。

2. 分支预测

上述条件,假设进入 A 条件的概率是 80%,而进入 B 条件的概率是 20%,如果采用分支预测,我们会直接跳过判断,直接去读取 A,然后再去计算判断条件,如果条件判断错误,再回过头去读取 B,这样带来的好处是如果判断正确,那么节省了大量的判断时间,如果判断错误,那么就会重新读取 B,时间反而变长了。前提是预测的足够准确,会提高计算的效率。

3. 预取缓存

对应的计算还有预取操作。还是上面的例子,要计算上面的语句,可以根据统计学来判断,哪些数据有很大的概率需要去取的,优先把这些数据放进缓存,下次计算直接去内存取数据,而不需要从 IO 取数据,这一部分就是热点数据,很多时候会把这部分热点数据保存在分布式的缓存中,能够很大的提高效率。当然预取的机制,缓存的一致性和缓存淘汰的机制对数据命中的效率影响非常大,另外在机器重新启动后,缓存没有建立起来之前,系统面临着没有缓存的情况,导致在启动阶段会有大量延时的情况,这些都是需要考虑的问题。

参考资料

  1. Dependency Resolving Algorithm


https://www.electricmonk.nl/docs/dependency_resolving_algorithm/dependency_resolving_algorithm.html


  1. Topological sorting


https://en.wikipedia.org/wiki/Topological_sorting


作者介绍


王方浩,前蚂蚁金服高级软件工程师。一直从事软件相关工作,是操作系统、大数据、自动驾驶相关技术的爱好者。


本文来自 DataFun 社区


原文链接


https://mp.weixin.qq.com/s/Jcz4XWDjMmbhmAiI_zBQXQ


公众号推荐:

跳进 AI 的奇妙世界,一起探索未来工作的新风貌!想要深入了解 AI 如何成为产业创新的新引擎?好奇哪些城市正成为 AI 人才的新磁场?《中国生成式 AI 开发者洞察 2024》由 InfoQ 研究中心精心打造,为你深度解锁生成式 AI 领域的最新开发者动态。无论你是资深研发者,还是对生成式 AI 充满好奇的新手,这份报告都是你不可错过的知识宝典。欢迎大家扫码关注「AI前线」公众号,回复「开发者洞察」领取。

2019-07-31 08:002622

评论 3 条评论

发布
用户头像
标记一下
2021-12-09 00:12
回复
用户头像
这文章看得让人走火入魔
2019-07-31 08:47
回复
上头~~
2019-07-31 10:13
回复
没有更多了
发现更多内容

​孟子轻量化技术迈上新台阶:登顶 ZeroCLUE 和 FewCLUE 榜单,已开源并提供 SDK

澜舟孟子开源社区

人工智能 自然语言处理 后端 大规模预训练模型

看了深入Java虚拟机:JVMG1GC的算法与实现文档,我悟了

程序知音

Java JVM 垃圾回收 java架构 后端技术

盘点:专业OKR管理工具有哪些?

PingCode

视频会议,WebRTC及RingCentral解决之道

RingCentral铃盛

WebRTC 视频会议 企业号九月金秋榜

阿里云对边缘计算的探索和实践

阿里云视频云

边缘计算

数据赋能智慧重庆,巴适得很!

浪潮云

云计算

基于预训练模型的金融事件分析及应用

澜舟孟子开源社区

人工智能 自然语言处理 金融科技 大规模预训练模型

主流定时任务解决方案全横评

阿里巴巴中间件

阿里云 云原生 定时任务

【8.26-9.2】写作社区精彩技术博文回顾

InfoQ写作社区官方

优质创作周报

到底什么样的数字化才是企业需要的?用2个数字化案例告诉你

优秀

数字化转型

重拾面向对象软件设计

阿里巴巴中间件

阿里云 技术 中间件 技术代码

Nacos 企业版如何提升读写性能和可观测性

阿里巴巴中间件

阿里云 微服务 云原生 中间件 可观测

MobPush 安卓推送消息数据解析推荐实现

MobTech袤博科技

android 移动推送

【计算讲谈社】第十一讲|商用车智能驾驶商业化实践:“科技+保险”模式探索

大咖说

智能驾驶 商用车

06_Linux基础-NGINX和浏览器、网页的关系-云服务器ssh登陆-安装NGINX-上传网页-压缩命令-xz-gzip-bzip2-zip-tar-配置NGINX服务器支持下载功能-备份脚本

mycpen

Linux

百余位顶级投资人齐聚无锡,DEMO CHINA创新中国峰会即将揭幕

创业邦

预训练模型在金融 NLP场景下的应用

澜舟孟子开源社区

人工智能 自然语言处理 大规模预训练模型

落地好OKR的8大关键步骤及常用辅助工具

PingCode

OKR

设计模式的艺术 第二十一章备忘录设计模式练习(设计一款RPG网游,为了给玩家提供更多方便,在游戏过程中可以设置一个恢复点,用于保存当前的游戏场景。如果在后续游戏过程中玩家角色“不幸牺牲”,可以返回到先前保存的场景,从所设恢复点开始重新游戏)

代廉洁

设计模式的艺术

图文实录|多模态自然语言处理最新进展

澜舟孟子开源社区

人工智能 自然语言处理 算法 后端

超越所有人的成就,牛顿的光芒也无法掩盖的天才数学巨人

图灵教育

数学 微积分 数学家

三面阿里,offer到手定级P7,过程很艰辛结果很满意

程序知音

程序员 阿里 java面试 后端技术 Java八股文

了解数字机器人最新发展动向,不要错过华为数字机器人秋季发布会​

王吉伟频道

RPA 机器人流程自动化 智慧政务 机器人开发 华为数字机器人

Java编程之语法结构

魏铁锤

卡塔尔世界杯足球赛dapp系统智能合约开发

开发微hkkf5566

05_Linux基础-NGINX编译安装^判断是否启动^修改端口^启动停止重启^相关路径^中文乱码-Windows、Linux文件传输

mycpen

Linux

极狐GitLab Helm Chart 已上线,玩转云原生极狐GitLab!

极狐GitLab

DevOps gitlab 云原生 Helm Kubernetes, 云原生, eBPF

当你的老板站在你背后,看你处理故障......

嘉为蓝鲸

运维 IT 故障 上班

数字藏品系统开发,NFT数字藏品开发说明

开源直播系统源码

软件开发 NFT 数字藏品 数字藏品软件开发 数字藏品系统

超越所有人的成就,牛顿的光芒也无法掩盖的天才数学巨人

图灵社区

数学 微积分 数学家

测评:腾讯Coding平台好不好用?

PingCode

流式计算优化指南:提高时效性_数据库_DataFunTalk_InfoQ精选文章