鲜阅

鲜阅

算法之于性能

作者/榑松谷仁等

日本Oracle株式会社技术顾问。曾在Emprix公司(美国本部)就职,为SIer和一般企业提供压力测试、性能管理等方面的咨询服务。之后就职于日本Oracle株式会社,还负责为使用Java、WebLogic、Exalogic等中间件产品的客户提供咨询服务。

从技术视角严格来说,性能是非常模糊的术语。当一个人说“这是个高性能的应用”时,其实我们无从判断他说的是什么。他是说应用消耗的内存少?应用节约了网络流量?还是说应用使用起来非常流畅?总而言之,高性能有着多重的含义和丰富的解释方式。

不过,我们可以确认几种影响性能的主要因素。其中,算法的效率对性能有很大的影响。

算法

请想象一下,有一排连成长队的箱子,这些箱子中放着物品。那么,从这些箱子中找出目标物品的时间长短就代表性能的优劣。如果时间很短,就可以说性能很好。相反,如果时间很长,就称性能很差。

如果从队列的一头依次打开箱子,有1000个箱子,平均打开500个才能找到需要的物品。也就是说,我们需要从一头开始依次打开500个箱子。有没有效率更高的方法呢?如果把箱子里的物品标上序号排好的话,会更方便查找(图1-1 上)。

比如说,我们要找标着数字“700”的物品。先打开最中间那个箱子,假设出来的是标着数字“500”的物品。因为要查找的数字比它更大,所以我们把目标转向这个箱子的右边部分。在右边的那一部分箱子之中,打开位于正中间的箱子,假设第2次找到的是标着“750”的物品。由于需要查找的数字比它更小,因此接下来就要查找这个箱子的左边。这样,通过有效地缩小查找范围,只需要很少的次数就能快速找到需要的数字(图1-1 下)。

{%}

图 1-1 通过改进使查找起来更容易

与现实世界不同的是,这些箱子上都写着地址,如果知道了地址,就能立即打开那个箱子。例如,如果想要看第100号箱子的内容,不管自己在哪个位置,都能立即打开第100号箱子看里面的内容。

还可以在箱子的里面放入地址。例如,如果将第100号箱子的地址放入第99号箱子中,那么“100”这个数字就放入到了第99号箱子里(图1-2)。

{%}

图 1-2

“1. 箱子连成一排”“2. 地址”“3. 可以在箱子里面放地址”“4. 知道地址的话就能立即访问”,这4点就是算法的基础,也是计算机结构的基础。对此有些了解的人可能会从“可以在箱子里面放地址”这个比喻联想到C语言的“指针”。另外,也可能会有人从“知道地址的话就能立即访问”这个比喻联想到CPU处理的“物理内存”。有些人可能对指针有恐惧心理,觉得很难,其实理解指针的窍门就是区分“值”和“地址”。如果感到头脑混乱,请想一下这个原则。

接下来,让我们来考虑一下往箱子里放物品。假如要把从1到100的数字放到1000个箱子中。这里简单起见,假设从1开始按顺序放入数字。也就是说,在第1个箱子里放入1,第2个箱子里放入2,第100个箱子里放入100。这样一来,从101号箱子开始,之后的箱子都是空的(图1-3 上)。接着,假设拿到了一个数字50.5,各位读者会怎么处理呢?这个问题其实没有正确答案。可以在101号箱子里放入50.5(图1-3 中),也可以把51号之后的箱子里面的数字依次后移(图1-3 下)。这里,我们把前者称为“方法 1”,后者称为“方法 2”。

{%}

图1-3

学习算法的窍门

● 掌握优点和缺点

学习算法的窍门之一就是掌握算法的优点和缺点。那么前面列举的方法 1 和方法 2 各自的优缺点是什么呢?

方法 1 的优点是可以立即将数字放到箱子里。缺点是数字不再按照顺序排列,在查找数字的时候需要把所有的箱子都打开。

而方法 2 的优点是,由于数字是按照顺序排列的,因此可以使用前面介绍的从中间开始查找的方法。缺点就是在存放的时候把数字依次后移会很麻烦。

如各位所见,算法本身都有各自的优点和缺点。“折中”是一个很重要的思维。系统中的很多意外情况都是因为没有注意到这种折中所导致的。例如,由于将数据按照到手的顺序来存放,导致数据量增加时查找会耗费惊人的时间,等等。

另外,这个折中的思维不仅体现在算法上,在架构上也是一样的。

● 通过在图上推演来思考

接着介绍另一个学习的窍门。要理解性能,在图上推演是很重要的。如果读了文字说明后还是不理解,可以试着看一下图。可以的话,推荐自己画图,然后向别人说明。如果能够做到画图说明,可以说理解了算法(或运算指令)。实际去做一下就会知道,在自己尝试着去说明的过程中,会发现那些在理解上模棱两可的地方。

此外,不建议一上来就去掌握和说明一些异常操作,应该先从基本操作开始。之后,作为补充,再去掌握和说明更加详细的操作或异常操作等,这样就足够了。想要一下子理解细枝末节,只会事倍功半。笔者曾在某大型IT公司做了5年的培训老师,有很强的陈述和说明能力,不过还是强烈建议各位读者画图说明,以及在一开始先抛开细枝末节来理解。

对性能的影响程度

理解了算法的重要性后,接着我们来切身感受一下由于算法不同而导致的性能差别。我把Mega(M)作为标准单位来使用。Mega是表示100万的单位,然后把算法的好坏放在处理100万个数据的情况下来考虑,会更容易理解。

首先,我们考虑一下从100万个数据中找出某一个特定数据的情况。假设检查1个数据需要花费1毫秒。使用从一头开始逐个检查所有数据的算法的话,因为从概率论来说要检查一半数据后才能找到要找的数据,所以可以计算出需要花费50万次×1毫秒,也就是500秒。

接着,我们来考虑一下对于已经排好序的数据,一半一半地来查找的算法。首先,检查100万个数据的正中间的数据,假设数值是“50万”。如果要查找的数据比50万小,就查找左半部分;如果比50万大,就查找右半部分的数据集,以此类推。这样,每检查1次就可以把查找范围缩小一半。虽然一开始有100万个查找对象,但检查1次后,查找对象就变成了50万个,接着变成25万个,再接着变成12.5万个。那么,什么时候查找对象会变为1个呢?通过计算我们可以知道大概是在第20次的时候(图1-4)。检查1个数据花费1毫秒的话,总共就是20毫秒,与500秒相比就是一瞬间的事。读者可能会想:“当然不会使用从头开始依次检查这样没有效率的方法了!”但是计算机经常会被迫进行这样没有效率的处理,只是使用的人没有意识到而已。

{%}

图 1-4

不过,一些一线程序员可能会想:“从头开始依次查找的方法和对半查找的方法相比,查找1个数据的时间应该是有差别的。从头开始查找的方法程序写起来比较简单。”的确,使用从头开始查找的方法,程序的编写比较轻松,处理也很简单,因此要查找1个数据花费的时间也很短。而使用对半查找的方法,需要记录自己检查到了哪个位置,还要计算下一步把哪部分数据对半,这是相对费事的。但其花费的时间是第一个方法的1.5倍?还是2倍?还是3倍?这里希望大家能有一种感觉,那就是这里所花费的时间从整体来看是很微小的,完全可以忽略。即使是2倍,那所花费的时间也只是40毫秒,3倍的话也只是60毫秒。与从头开始查找所要花费的500秒比起来,差别依旧是很大的。

基于以上原因,在比较算法优劣的时候,会忽略掉一些微小的系统开销。我们应该关注的是随着数据个数的变化,所花费的时间会以怎样的曲线发生变化。因为有一些算法,在数据只有一两个的时候性能很好,但是当数据个数达到几千到几万的时候,性能会急剧下降。

评价算法的指标

将数据的个数用变量 n 来表示,让我们来比较一下直线 y = n 和曲线 y = n2。可以发现 y = n2 的值会急剧变大(图 1-5)。即使是用 y = 2n 这条直线来与曲线 y = n2 作比较,差别也依然很大。在这里,2n 的“2”对整体是不产生影响的,这就属于前面提到的“可以忽略的系统开销”。

{%}

图 1-5 数据个数与所需时间的关系

计算机原则上是处理大量数据的东西,所以我们只关心当数据量变大时决定性能优劣的关键(Key)。这个关键就是“复杂度”(Order)。在前面列举的 y = n 或 y = 2n 中,其复杂度标记为 O(n)。而 O(1) 则表示不会受到数据量增加的影响。作为算法来说,这就非常好了。

打个比方,查找最小值的情况下,如果要从分散的数据的一端开始搜索,就需要查看所有的数据。换句话说,复杂度是 O(n)。但若数据是按顺序排列的,那第1个数据就是最小值,所以只要查看1次就完成了,复杂度就是 O(1)。若数据个数是5个或10个这样的小数字,两者花费的时间差距可能只有几毫秒。但是若数据量达到了100万个会怎么样呢?这就会产生大约1000秒的差距。

接下来,我们就针对“查找数据”这种对计算机来说非常基础的操作,来通过复杂度判断一下算法的优劣。刚才已经介绍了将所有数据从头到尾查找一遍的方法。此外,还有一个非常有名的能提高数据查找效率的方法叫作“树”(图1-6)。

{%}

图 1-6 树结构

在树的根节点放置1个数据,接着将比它大的数据放在右边,比它小的数据放在左边,以此方式进行分类。对分类到左右两边的数据,以同样的方法进行分类。这样就会生成一个像“树”一样的结构。从树的根节点开始查找,直到找到目标数据为止,这一过程就是把数据对半分的操作。这种操作的复杂度标记为 O(logn)。logn指的是把n除以2多少次后会变为1。大体来说,它的复杂度处于 O(1) 和 O(n) 之间,用图来表示的话,可以看到即便数据变大,O(logn) 曲线也只是缓缓地上升(图1-7)。

{%}

图 1-7 数据个数与所需时间的关系

在数据量小的时候,O(n) 的性能有时可能会超过 O(1),但当数据量变大时,一定是 O(1) 胜出。在评价算法优劣的时候,首先要考虑到数据量很大的情况。

 

{%}

《图解性能优化》列举了丰富的实例,并结合直观的插图,向读者传授了有用的实战技巧。另外,因为系统性能和系统架构密切相关,所以读者在学习系统性能的过程中还能有效地学到系统架构的相关知识。

 

 

强迫性调优障碍

作者/Christian Antognini

资深数据库专家,从1995年就开始致力于探究Oracle数据库引擎的工作机制。长期关注逻辑与物理数据库的设计、数据库与Java应用程序的集成、查询优化器以及与性能管理和优化相关的各个方面。目前任瑞士苏黎世Trivadis公司首席顾问和性能教练,是OakTable网站核心成员。

如果你曾仔细地定义过性能需求,那么很容易就可以确定应用程序是否正在遭遇性能问题。如果没有仔细定义过性能需求,那么答案很大程度上会取决于回答者的主观判断。

有趣的是,实际上导致应用程序性能被质疑的大部分情形都可以归纳为下面的少数几类。

  • 用户不满意应用程序当前的性能表现。
  • 系统监控工具警告某个基础组件正遭遇超时或不寻常的负载。
  • 响应时间监控工具通知你某个服务级别协议没有得到满足。

第二点和第三点的区别尤为重要。基于此,接下来的内容将简要描述这些监控方案。之后,再来看一下某些看似有必要、实则没必要进行优化的情况。

系统监控

系统监控工具基于一般系统统计信息进行健康检查。其目的是识别出不寻常的负载模式以及故障。虽然这些工具可以同时监控整个基础设施,但这里需要强调的是,它们只监控单独的组件(例如主机、应用服务器、数据库或存储子系统),而不考虑组件间的作用关系。因此,对于拥有复杂基础设施的环境,在支撑基础结构的单个组件出现异常时,很难或者几乎不可能评估异常对系统响应时间的影响。其中一个例子就是高频度地使用某一资源。换句话说,系统监控工具发出警报只是说明应用程序或者基础设施中的某些组件可能出现了问题,而用户根本没有察觉到任何性能问题(称作误报);反之,也可能出现用户正在遭遇性能问题,而系统监控工具并没有发现问题(称作漏报)。最常见、也是最简单的关于误报和漏报的例子,是监控一个拥有许多CPU的对称多处理系统的CPU负载情况。假设你有一个装有四颗四核CPU的系统。当看到使用率在75%左右时,你可能觉得这太高了,系统受到了CPU的限制。但是,如果执行任务的数量远大于处理核心数量,那么这样的负载就是很正常的。这便是一个误报。反之,当你看到CPU使用率大约为8%时,你可能觉得一切正常。但是如果系统正在执行一个没有并行的单任务,那对于这个任务来说可能瓶颈就是CPU。实际上,100%的1/16只有6.25%,因此单个任务的CPU使用率不能超过6.25%。这便是一个漏报。

响应时间监控

响应时间监控工具(也称为应用程序监控工具)基于由机器人产生的假想事务或者由终端用户产生的真实事务进行监控。这些工具测量应用程序处理关键事务的时间,如果时间超出预期阈值,它们就会发出警告。换句话说,它们和用户一样利用基础设施,也会像用户那样“抱怨”糟糕的性能。因为它们从用户的角度监控应用程序,所以这些工具不仅能检查单个组件,更重要的是,它们还能检查整个应用程序的基础设施。因此它们专门用于监控服务级别协议。

强迫性调优障碍

曾经有一段时间,大部分数据库管理员都患上一种叫作“强迫性调优障碍”1的病症。其症状是过多地检查性能相关的统计信息(大部分都是基于比率的),从而无法集中精力关注真正重要的事情。他们简单地以为应用某些“简单”规则,就能优化所管理的数据库。历史告诉我们,结果并不总是尽如人意。为什么会出现这样的情况?所有用来检查某个给定比率(或值)的规则都是独立于用户体验而制定的。也就是说,误报和漏报都是规则而非意外。更糟糕的是,大量的时间消耗在这些任务上。

1这个绝妙的名词是由Gaya Krishna Vaidyanatha发明的。你可以在Oracle Insights: Tales of the Oak Table( Apress,2004)一书中找到它的相关讨论。

举例来说,时不时会有数据库管理员向我提出这样的问题:“我注意到我们的一个数据库在某个闩(latch)上有大量的等待。怎么做才能减少或者最好能消除这些等待?”一般我会回答:“你的用户因为这个闩锁抱怨过么?肯定没有,所以不用担心。反倒应该问问他们认为应用程序的问题有哪些。然后分析这些问题,你就会知道这个闩锁上的等待到底有没有影响到用户。”

虽然我从未做过数据库管理员,但是必须承认我也患过“强迫性调优障碍”。现在我和其他大多数人一样,克服了这个病症。只不过与其他恶疾一样,彻底治愈“强迫性调优障碍”需要花很长时间。有些人根本没有意识到患了这种病症;有些人意识到了,但是因为多年的沉溺,总是很难去认识这样一个大错误并改掉陋习。

 

{%}

《Oracle性能诊断艺术(第2版)》Oracle数据库优化的里程碑式著作,帮你系统地发现并解决Oracle数据库性能问题。