“AI 技术+人才”如何成为企业增长新引擎?戳此了解>>> 了解详情
写点什么

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

  • 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


公众号推荐:

2024 年 1 月,InfoQ 研究中心重磅发布《大语言模型综合能力测评报告 2024》,揭示了 10 个大模型在语义理解、文学创作、知识问答等领域的卓越表现。ChatGPT-4、文心一言等领先模型在编程、逻辑推理等方面展现出惊人的进步,预示着大模型将在 2024 年迎来更广泛的应用和创新。关注公众号「AI 前线」,回复「大模型报告」免费获取电子版研究报告。

AI 前线公众号
2019-07-31 08:002606

评论 3 条评论

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

通过 Amazon API Gateway 和 Amazon Lambda 实现基于 Restful API 的 CloudFront Distribution 复制/克隆功能

亚马逊云科技 (Amazon Web Services)

Lambda Gateway

python实现连接两个数据库

YUKI0506

设施资产管理系统解决方案

低代码小观

资产管理 CRM CRM系统 企业设备管理 设备巡检管理系统

架构实战营|模块1

KDA

#架构实战营

面试突击49:说一下 JUC 中的 Exchange 交换器?

王磊

Java java面试

私有化的IM即时通讯平台,企业首选的沟通工具

WorkPlus

互联网公司目标管理OKR实践落地与反思

laofo

互联网 OKR 研发效能 绩效管理 快手

互联网公司目标管理OKR和绩效考核误区

laofo

OKR 研发效能 互联网公司 快手 绩效考核 GRAD

Reactor百万连接的并发

C++后台开发

reactor 高并发 epoll Linux服务器开发 C++后台开发

无聊科技正经事周刊(第 7 期):跟村上春树学跑步,向古川武士学养成

潘大壮

程序员 周刊 行业趋势 科技周刊 技术周刊

活动报名:以「数」制「疫」,解密 Tapdata 在张家港市卫健委数字化防疫场景下的最佳实践

tapdata

数字化 数据孤岛 实时数据 疫情防控 活动报名

存储模组头部厂商嘉合劲威加入龙蜥社区

OpenAnolis小助手

开源 操作系统 芯片 龙蜥社区 嘉合劲威

程序员,做业务还是做技术更有前途?

张泽豪

程序员

融云首席科学家任杰:历练出人才,职场「经历>经验」

融云 RongCloud

微信业务架构,学生管理系统架构设计

泋清

#架构实战营

互联网研发效能专家怎么找?

laofo

Tapdata x 轻流,为用户打造实时接入轻流的数据高速通道

tapdata

SaaS 数据同步 实时数据 轻流

Python unicode三明治

AIWeker

Python 人工智能 5月月更

员工考勤打卡时,如何避免非本人代替打卡?

华为云开发者联盟

人脸识别 打卡 华为云FRS 华为云FunctionGraph 华为云APIG

互联网大厂研发效能团队的需求管理

laofo

互联网 DevOps cicd 研发效能 CI/CD

快速上手云原生安全平台 NeuVector

Rancher

Kubernetes k8s rancher NeuVector

微信小程序商城源代码

源字节1号

软件开发 小程序开发

软件的license是什么意思?作用是什么?

行云管家

软件 运维 许可证

零基础可以学云计算运维吗?怎样从才可以学好?

行云管家

云计算 运维 IT运维 云运维 服务器运维

css 学习笔记【二】-背景,渐变,链接文档的MIME类,id选择器和类选择器的区别

恒山其若陋兮

5月月更

Tapdata Cloud 2.1.5来啦:新增支持Amazon RDS数据库,错误日志查询更便捷,Agent部署细节再优化

tapdata

SaaS 数据同步 polarDB Amazon RDS

Tapdata 在数字化防疫场景的最佳实践

tapdata

数字化 防疫 主数据管理 实时数据 数据虚拟化

攻防演练 | 关于蓝队攻击研判的3大要点解读

青藤云安全

安全攻防 网络安全

基于GPU的并行集群系统在中国的发展状况

Finovy Cloud

gpu 云服务器 集群渲染 渲染服务

数据产品实战-toB产品实践心得

第519区

数字化转型 解决方案 数据产品 tob产品

学生管理系统架构设计图

Justin1024

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