性能优化 | 必知定律篇

语言: CN / TW / HK

之前的几篇文章中,分别介绍了性能优化方法、工具...

性能优化|有条不紊的方法

性能优化|火焰图篇

性能调优|成都核酸系统篇

但是计算机系统是非常庞大的,包含了计算机体系结构、操作系统、网络、存储等,单单拎出任何一个方向都值得我们去研究很久,因此,我们在分析系统性能的时候,可能会碰到一些无法解释的问题或者现象, 程序员必须了解的性能延迟指标   我们可以借助一些理论去帮助我们去进一步推断和解决问题。


本文主要介绍阿姆达定律、古斯塔夫森定律、帕累托法则、利特尔法则。

Amdahl(阿姆达)定律

科学计算中用多处理器进行并行加速时,总体程序受限于程序所需的串行时间百分比。譬如说,一个程序 50% 是串行的,其他一半可以并行,那么,最大的加速比就是 2。无论用多少处理器并行,这个加速比不可能提高到大于 2。

加速比 = 优化前的系统耗时/优化后的系统耗时

对每一条曲线我们都可以看到,超过一定的并行度后,就很难进行进一步的速度提升了。由此可见,为了提高系统的性能,只提高CPU的数量不一定能起到有效的作用。需要从根本上修改系统的串行行为。提高系统内可优化模块的比重,在此基础上,合理增加处理器的数量,才能以最小的投入,得到最大的加速比。

听起来可能比较晦涩,我举个简单的例子:

你洗衣服加上晾晒衣服总共需要30分钟,但是洗衣机洗衣服15分钟时间是固定(串行)的,但是晾晒衣服可以通过多人并行操作,最后缩短为1分钟甚至更短,但是不可能小于15分钟。

这个定律看似陌生,其实在日常工作中经常遇到,有时在优化代码过程中发现有个递归算法,于是乎想到通过单层for循环,以为发现了新大陆,性能一定会大幅度提高,最后发现没有任何区别。

这个定律告诉我们从线性模型中抽离出来,继续细分整个处理流程,找出执行时间最长的程序热点,对这些代码段进行并行化从而将所有瓶颈逐个击破,这才是使通过并行化获得最大性能提升的最好办法。

同时它也可以用木桶定律解释,一个桶能够装多少水取决于最短的那块板子。

Gustafson(古斯塔夫森)定律

Gustafson 定律也试图说明处理器个数、串行化比例和加速比之间的关系,如图2-1所示,但是Gustafson 定律和Amdahl 定律的角度不同。同样,加速比都被定义为优化前的系统耗时除以优化后的系统耗时。

可以看到,由于切入角度的不同,Gustafson 定律的公式和 Amdahl 定律的公式截然不同。从Gustafson 定律中,我们可以更容易发现,如果串行化比例很小,并行化比例很大,那么加速比就是处理器的个数。只要不断地累加处理器,就能获得更快的速度。

帕累托法则

它也被称为 80/20 法则、关键少数法则。

这个法则是基于我们生活中的认识产生的,人们在生活中发现很多变量的分布是不均匀的——在很多场景下,大约20%的因素操控着80%的局面。也就是说,所有的变量中,比较重要的只有20%,是所谓的“关键少数”。剩下的多数,却没有那么重要。

一个程序完成后必然会去运行,如果我们统计代码的运行时间,往往会发现程序的80%的时间是在运行大约20%的代码。也就是说,只有少数代码非常频繁地被调用。

所以,如果我们想提高程序的性能,最好找出这些少数代码,并做重点优化,这样就可以用很少的改动大幅度地提升整个程序和系统的性能。

假设我们的性能优化投入永远是按照代码的优先级来投入的,也就是说,总是要先优化最值得优化的代码。那么我们看到,只要投入差不多20%的努力,就能产出80%的性能优化产出,获得最大的投入产出比。

假如先解决20%的最重要的问题,就可以达到总体效果的80%。以后再花费80%的努力,也只能解决剩下的20%的问题。

那么现在,我们就从性能优化的角度,来看看如何参照帕累托法则,来规划我们性能优化工作的投入和产出。我举个例子:

  • 第一步要耗时最长的流程

  • 第二 要考虑耗时最长的流程是否是核心流程,是否可以去掉或者用更快的算法替代

  • 第一步和第二步如此反复

利特尔法则

利特尔法则(英语:Little’s law),基于等候理论,由约翰·利特尔在1954年提出。利特尔法则可用于一个稳定的、非占先式的系统中。其内容为:

在一个稳定的系统中,长期的平均顾客人数(L),等于长期的有效抵达率(λ),乘以顾客在这个系统中平均的等待时间(W)

或者,我们可以用一个代数式来表达:

L=λW

此理论同样适用于计算机性能优化中的QPS及最佳线程数量的计算

最佳线程数量配置

需要的线程数 = qps * latency(单位秒)。依据是little’s law,类似的应用是tcp中的bandwidth-delay product。如果这个数目远大于核心数量,应该考虑用异步接口。

线程数量配置示例

单线程QPS运行

我们都知道 RT「响应时间」 是由两部分组成 CPU Time + Wait Time 。那如果系统里只有一个线程或者一个进程并且进程中只有一个线程的时候,那么最大的 QPS 是多少呢?假设 RT 是 199ms (CPU Time 为 19ms ,Wait Time 是 180ms ),那么 1000s以内系统可以接收的最大请求就是

1000ms/(19ms+180ms)≈5.025。

所以得出单线程的QPS公式:

单线程      =1000    /    单线程QPS=1000ms/RT

最佳线程数

还是上面的那个话题 (CPU Time 为 19ms ,Wait Time 是 180ms ),假设CPU的核数1。假设只有一个线程,这个线程在执行某个请求的时候,CPU真正花在该线程上的时间就是CPU Time,可以看做19ms,那么在整个RT的生命周期中,还有 180ms 的 Wait Time,CPU在做什么呢?抛开系统层面的问题(这里不考虑什么时间片轮循、上下文切换等等),可以认为CPU在这180ms里没做什么,至少对于当前的业务来说,确实没做什么。

  • 一核的情况

由于每个请求的接收,CPU只需要工作19ms,所以在180ms的时间内,可以认为系统还可以额外接收180ms/19ms≈9个的请求。由于在同步模型中,一个请求需要一个线程来处理,因此,我们需要额外的9个线程来处理这些请求。这样,总的线程数就是:

(180    +19    )/19    ≈10个(180ms+19ms)/19ms≈10个

多线程之后,CPU Time从19ms变成了20ms,这1ms的差值代表多线程之后上下文切换、GC带来的额外开销(对于我们java来说是jvm,其他语言另外计算),这里的1ms只是代表一个概述,你也可以把它看做n。

  • 两核的情况

一核的情况下可以有10个线程,那么两核呢?在理想的情况下,可以认为最佳线程数为: 2 x ( 180ms + 20ms )/20ms = 20个

CPU利用率

我们之前说的都是CPU满载下的情况,有时候由于某个瓶颈,导致CPU不得不有效利用,比如两核的CPU,因为某个资源,只能各自使用一半的能效,这样总的CPU利用率就变成了50%,在这样的情况下,最佳线程数应该是: 50% x 2 x( 180ms + 20ms )/20ms = 10个 这个等式转换成公式就是: 最佳线程数 = (RT/CPU Time) x CPU 核数 x CPU利用率 当然,这不是随便推测的,在收集到的很多的一些著作或者论坛的文档里都有这样的一些实验去论述这个公式或者这个说法是正确的

最大QPS公式推导

假设我们知道了最佳线程数,同时我们还知道每个线程的QPS,那么线程数乘以每个线程的QPS 即这台机器在最佳线程数下的QPS。所以我们可以得到下图的推算。

我们可以把分子和分母去约数,如下图。

于是简化后的公式如下图.

从公式可以看出,决定QPS的是CPU Time、CPU核数和CPU利用率。CPU核数是由硬件做决定的,很难操纵,但是CPU Time和CPU利用率与我们的代码息息相关。

虽然宏观上是正确的,但是推算的过程中还是有一点小小的不完美,因为多线程下的CPU Time(比如高并发下的GC次数增加消耗更多的CPU Time、线程上下文切换等等)和单线程的CPU Time是不一样的,所以会导致推算出来的结果有误差。

总结

性能调优的优先条件是性能分析,只有分析出系统的瓶颈,才能进行调优。否则就是瞎蒙。

参考

  1. http://plantegg.github.io/2018/08/24/%E6%80%A7%E8%83%BD%E4%BC%98%E5%8C%96%EF%BC%8C%E4%BB%8E%E8%80%81%E4%B8%AD%E5%8C%BB%E5%88%B0%E7%A7%91%E5%AD%A6%E7%90%86%E8%AE%BA%E6%8C%87%E5%AF%BC/

  2. http://cloud.tencent.com/developer/article/1675024

  3. http://blog.csdn.net/en_joker/article/details/80621082?utm_medium=distribute.pc_relevant.none-task-blog-2~default~baidujs_baidulandingword~default-0-80621082-blog-109124342.pc_relevant_multi_platform_whitelistv3&spm=1001.2101.3001.4242.1&utm_relevant_index=3

  4. http://www.inlighting.org/archives/amdahls-law-and-its-proof

  5. http://www.intel.com/content/dam/develop/external/us/en/documents/8-1-3-amdahl-e5-ae-9a-e5-be-8b-180203.pdf

随手关注或者”在看“,诚挚感谢!