第 1 章 性能的基础知识

第 1 章 性能的基础知识

1.1 学习性能所必需的知识

在最开始,我们先来介绍一下有关性能的基础理论。

性能变差的原因示例

曾经有客户过来咨询:“处理的数据条数变多时,数据库(DataBase, DB)的处理速度就会变得很慢,这让人很头疼。”听到这样的问题,一般就会马上想到“是不是 DB 的这个 SQL 语句不太好啊?是不是磁盘的 I/O 不太好啊”等,即从一个方面去判断问题的原因。由于当时笔者有一定的知识储备,立即就推断出 DB 进行单个处理的速度并没有变慢。但是据客户说,DB 单次处理的数据量分别为 1000 条和 100 万条时,花费的时间会有几十倍甚至几百倍的差别。由于找不到头绪,就从客户那里要来了应用程序的代码。看了一下源代码,就找出原因了。实际情况如下所示。

第 1 条数据的处理过程是:从文件中读取 1 条数据,并把它放在内存中,接着在 DB 中放入 1 条数据,完成。第 2 条数据的处理过程是:从文件中读取 1 条数据,放在刚才的内存位置的后面,接着在 DB 中放入 1 条数据,完成。第 3 条数据的处理过程是:同样从文件中读取 1 条数据,然后遍历内存,在其后面的位置放入 1 条数据,再在 DB 中放入 1 条数据,完成。

那么,知道这个处理的问题出在哪里了吗?没错,在已经放入 100 万条数据的时候,为了再放入 1 条数据,就需要遍历 100 万次内存(图 1.1)。

{%}

图 1.1 数据放得越多,处理速度变得越慢的例子

编写这个程序的客户可能觉得遍历内存这种处理一下子就能完成了。但是,要知道“积土成山”。本身 DB 的单次处理速度就不快,如果要遍历 100 万次内存的话,速度会更慢。在笔者指出以上问题后,客户显得很不好意思。要解决这个问题,只需增加 1 个变量,来标明内存的最后位置。只需如此,性能就有了几百倍的提升(图 1.2)。

{%}

图 1.2 放入很多数据后处理速度也不会变慢的例子

在这个例子中,应用程序的设计是导致性能变差的原因。但是,如果没有这方面的知识,就不会意识到这个原因。在本章中,我们就来说明一下有关性能的基础知识——“算法”。

1.2 算法的优缺点与学习方法

1.2.1 什么是算法

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

想象一下,从队列的一头依次打开箱子。假设有 1000 个箱子,平均打开 500 个就能找到需要的物品。也就是说,我们需要从一头开始依次打开 500 个箱子。那么有没有效率更高的方法呢?如果把箱子里的物品标上序号排好的话,会更方便查找(图 1.3 上)。比如说,我们要找标着数字“700”的物品。先打开最中间那个箱子,假设出来的是标着数字“500”的物品。因为要查找的数字比它更大,所以我们把目标转向这个箱子的右边部分。在右边的那一部分箱子之中,打开位于正中间的箱子,假设第 2 次找到的是标着“750”的物品。由于需要查找的数字比它更小,因此接下来就要查找这个箱子的左边。这样,通过有效地缩小查找范围,只需要很少的次数就能快速找到需要的数字(图 1.3 下)。

{%}

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

这样的策略或方法就称为“算法”。算法的好坏对性能有很大的影响。

此外,学习算法的好处,不仅仅局限于提升性能。熟练掌握 IT 技能的人也都熟知主要的算法,当新的技术出现的时候,他们可以马上想到“就是那个算法啊”,立刻就能理解。因为对每个算法的优缺点都了然于胸,所以很少会用错。如果只掌握了技术的表面而没有真正理解,或者是仅仅死记硬背了下来,那么或许会一些简单的使用方法,但在实际应用时会很辛苦。因此,掌握算法是 IT 工程师的基本功。

1.2.2 算法的基础

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

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

{%}

图 1.4 地址是算法的基础

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

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

{%}

图 1.5 按顺序排,还是不按顺序排

1.2.3 学习算法的窍门

掌握优点和缺点

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

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

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

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

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

通过在图上推演来思考

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

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

1.3 算法的应用实例及性能的差异

1.3.1 日常生活中算法的例子

为了让大家切身感受到算法,让我们结合系统处理的流程,来了解算法在日常生活中的广泛应用。

举一个“预约机票”的例子。假设我们要从东京去北海道,首先查找飞机航班。在进行这样的处理时,大部分系统都会使用“树”(用于查找的机制)。航班会按费用由低到高“排序”(排列的机制)显示。此外,处理待取消的预约时,应该会先登录“队列”(用于等待的机制),接着,把姓名和会员号等放入“数组”或“链表”(用于保存的机制)中保存(图 1.6)。我们的生活就是这样与 IT 的算法有着无法割舍的关系。

{%}

图 1.6 我们身边的系统也在使用各种算法

1.3.2 对性能的影响程度

理解了算法的重要性后,接着我们来切身感受一下由于算法不同而导致的性能差别。本书的前半部分把 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.7)。检查 1 个数据花费 1 毫秒的话,总共就是 20 毫秒,与 500 秒相比就是一瞬间的事。读者可能会想:“当然不会使用从头开始依次检查这样没有效率的方法了!”但是计算机经常会被迫进行这样没有效率的处理,只是使用的人没有意识到而已。

{%}

图 1.7 优秀的算法处理速度快

可以忽略一些微小的系统开销

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

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

1.3.3 评价算法的指标

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

{%}

图 1.8 数据个数与所需时间的关系①

什么是复杂度

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

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

通过复杂度来评价算法

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

{%}

图 1.9 树结构

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

{%}

图 1.10 数据个数与所需时间的关系②

在本书的讨论范围中,大家只要掌握 O(1)、O(n) 和 O(logn) 就足够了。在数据量小的时候,O(n) 的性能有时可能会超过 O(1),但当数据量变大时,一定是 O(1) 胜出。在评价算法优劣的时候,首先要考虑到数据量很大的情况。

不过,这只是理想世界中的性能,当然还不能在实际中使用。从第 3 章开始,我会针对现实世界中的性能进行说明。

COLUMN 学习信息科学的重要性

这里我们从算法和复杂度的角度介绍了信息科学的一个方面。笔者(小田)在大学的时候学的是信息科学专业。说实话,当时也会怀疑它在实际工作中是否有用,但是现在笔者的想法已经不一样了。

现在笔者认为,信息科学是全部 IT 工程师在早期就应该掌握的内容。信息科学是计算机的核心。要想成为一名工作能力优秀的工程师,信息科学是必学的内容。

举例来说,有一个理论叫“香农信息论”,它教给我们“什么是信息”“数据可以压缩到什么程度”“数据应该如何在计算机内部存储”等一些计算机的核心概念,并引发我们思考。在图像数据的压缩、加密等方面,也都会涉及它。

大家也不妨试着学习一下信息科学。笔者站在指导者的立场上,觉得信息处理技术考试的“基本信息技术考试”1 就很有学习价值。没有在教育机构学习过计算机的读者不妨去试着考一下基本信息技术考试,一定能学到一些基础的东西。这些基础的东西会在将来学习实际应用的时候发挥很大的作用。

1类似于我国的计算机等级考试。“基本信息技术考试”是“信息技术考试”中等级最低的考试,上面还有“应用”及各个专项考试(系统架构、项目管理、网络、数据库等 9 种)。——译者注

1.4 响应与吞吐的区别

在考虑性能时还有两个重要概念,就是响应与吞吐。响应表示的是应答的快慢,而吞吐表示的是处理数量的多少。初学者可能经常会混淆这两个概念,我们来完整地学习一下它们。

打个比方,响应就像是几乎装载不了东西,但速度飞快的 F1 赛车。而吞吐则像是速度很慢,但能装载大量货物的自卸卡车。不论哪个都很有用。

有些时候,虽然响应较慢,但吞吐会比较高。这是怎么一回事呢?比如,同时处理的数据条数增加时就是这种情况。虽然每条的处理时间并没有变快,但是某一段时间内处理的条数增加了(图 1.11)。这也可以称为性能提升。

{%}

图 1.11 响应和吞吐的关系

如果这一点没弄清的话,就很容易在实际工作中犯下“明明优化了机器的配置,但性能并没有提高”这样常见的错误。实际上是响应有问题,却增加了 CPU 核心数,这样怎么能指望收到相应的效果呢?只是增加了空转的 CPU 核心而已。所以要养成习惯,先确认问题是出在响应上还是吞吐上。

在实际环境中,有的系统偏重于响应,有的系统偏重于吞吐。偏重于响应是一剂万能药。因为响应变快的话,一般来说吞吐也会变大。但是,就像 CPU 的时钟频率和磁盘的 I/O 速度会有一个极限一样,物理上的增速也是有限度的,硬件并不能无限地提速。这时候就需要偏重于吞吐的系统上场了。这种情况经常会在高并发用户的系统中看到。互联网上的热门网站,应该都被设计成即使访问很集中,响应也不会变慢。像这样擅长高并发处理的系统称为“偏重吞吐的系统”。

把个人使用的 PC 和系统使用的服务器(特别是大型服务器)比较来看的话,可以发现 CPU 的时钟数并没有很大的差异,但是价格却相差了数十到数百倍。产生这样大的价格差的一个重要原因,是服务器为了能支持高并发而进行了优化。服务器往往配备了多个 CPU 来同时处理,并准备了大量的内存,还能使用被称为总线的数据通道来有效地并发执行多个处理,另外 I/O 的性能也很高,一般不会阻塞处理的执行。

在考虑性能时,请经常有意识地思考一下系统是偏重于响应,还是偏重于吞吐。

COLUMN 系统工程师学习编程的重要性

本章虽然是在讲算法,但想要真正掌握算法还是要靠编程。在这个意义上,我认为系统工程师最好也做一下编程。笔者曾经在大学时做过编程。那个时候的经验对于现在的系统工程师工作是非常有用的。笔者从一个教育者的角度来看,对于很多毫无经验的系统工程师新人来说,编程经验不足会成为瓶颈,阻碍个人的发展。没有编程经验,就无法进行整体的把握,不能举一反三,只能死记硬背。

应用开发工程师转为系统工程师的话,可能一开始会比较辛苦,但因为懂算法,所以从长远来看成长空间很大,日后肯定能大展身手。如果可能的话,请将应用开发工程师和系统工程师这两个职业都体验一下。

1.5 算法的具体例子

1.5.1 数组与循环处理

接着我们来介绍一下主要的算法及其优缺点。首先是“数组”与“循环处理”2。数组就是一定个数的箱子并列排在一起,指定了数组中第几个(称为“下标”)的话,就能立即访问那个位置。并且,如果数据是按顺序放入的,那么下标也可以用来记录数据已经插入到了哪个位置,或者处理进行到了哪个位置(图 1.12)。下一次处理的时候,就可以直接从被记录的箱子之后的位置开始,从而提高按顺序处理的效率。

2可能有人会说“数组是数据结构”。由于它有数据结构所赋予的算法的特性,因此请允许笔者在此进行说明。

{%}

图 1.12 数组的示意图

下面举一个循环结构和数组整合在一起的例子。使用文字描述整个流程,如图 1.13 所示。

{%}

图 1.13 使用数组进行循环处理

复杂度

该怎么表示复杂度呢?是 O(1) 呢?还是 O(n) 呢?还是 O(logn) 呢?当处理的数据个数是 n 的时候,需要 n 次循环处理,因此正确答案是 O(n)。让我们替换上具体数字来确认一下吧。假设需要对 100 万个数据进行处理,每个处理需要花费 1 纳秒,因为是 3 个处理的循环,所以就是将 3 纳秒循环 100 万次,计算可得结果为 3 秒。那么,1000 万个的话就是 30 秒。n 变为原来的 10 倍后,花费的时间也增加到 10 倍。的确,就是 O(n)。

优点

数组的一个优点就是适用于循环处理。在循环过程中一个个遍历数组元素,这样的处理方法也比较容易用代码实现。

此外,数组很简单,因此初学者一开始就会学习这个数据结构。数组也适用于按顺序存放数据、查找数据。计算机的内存本身就是按照方便数组创建的形式构成的。因此,在内存中临时进行处理时,数组是用得很多的数据结构。

缺点

数组的缺点是,如果事先不知道数组长度的话,就会占用过多的空间,或者在后面发现空间不够。另外,在数组中间插入数据也不方便。数组就像是紧紧连在一起的一排箱子,如果需要插入数据,就只能把数据一个个往后移。

因此,存放的数据会长期慢慢增多时,或者数据会频繁修改的情况下,使用数组就会比较麻烦。

改进与变种

有些时候也会使用“数组的数组”。例如,在 C 语言等中,使用数组的数组来存放字符串。在这种情况下,一部分存放的是地址(图 1.14)。

{%}

图 1.14 数组的数组的示意图

此外,可以另外准备一个变量来标明数据已经放入到哪个位置了,以便能立即添加数据。在本章开头部分介绍的笔者亲身经历的那个例子中,使用的就是这种处理方法。

1.5.2 链表与循环处理

链表在算法的世界中也称为“链表结构”,指的是像链条一样的结构。链表就像多个珠子串联在一起,可以像数组一样按顺序遍历。不同的是,数组结构中的箱子贴在一起不能分离,而在链表结构中,则像是用绳子一样的东西把箱子连接在一起(图 1.15)。

{%}

图 1.15 链表结构的示意图

复杂度

那么链表的复杂度怎么计算呢?如果是 10 倍的数据量,那么需要遍历的次数就会变为 10 倍。因此,其复杂度是 O(n)。在实际的编程中,为了访问下一个箱子,需要检查箱子内部的值,来确认下一个箱子在哪里,这就增加了一个步骤。但是,这对整体是没有影响的。

优点

链表的好处在于它的灵活性。如果需要插入数据的话,只要在插入数据后把箱子连接起来就行了(图 1.16),不需要像数组那样把数据依次往后移。添加箱子也很容易。因此,链表经常被用来管理容易变化的东西。

{%}

图 1.16 链表结构的灵活性

缺点

如果只考虑其优点的话,似乎不管什么情况下,使用链表都比使用数组更方便。但是,事情并不这么简单。

并不是所有情况下都可以使用“知道地址的话就能立即访问”这样的优点。比如,假设想要访问后面第 4 个箱子的数据。这个时候,如果是数组的话,只需指定“后面第 4 个”就能立即访问,而链表的话则没办法这么做(图 1.17)。

{%}

图 1.17 链表结构与数组的差别

改进与变种

有一种既能往前遍历又能往后遍历的链表,称为“双向链表”。

1.5.3 树与查找

把一棵树倒过来的结构,就是称为“树”的数据结构。在很多情况下,性能所对应的主要处理内容就是“查找相应的数据”。可以说,树结构就是为了方便查找而创造出来的。即使数据量增加了,层级也不会随之增加,这就是它的特点。如图 1.18 所示,一个一个的连接点或端点称为节点(Node)。数据是按顺序排列的。

{%}

图 1.18 树结构的特性

我们来看一下 1000 个数据与 100 万个数据的情况下树的高度。“高度”指的就是层级,表示访问多少次后能找到目标数据。1000 个数据的话是 32 次。100 万个数据的话是 1000 次。虽然数据变为 1000 倍,但是高度只变为 30 倍。

复杂度

把数据分成两股后,可以处理的数据量也成倍增加,即 2 的 x 次方。复杂度的增加反而逐渐变弱,与 2 的 x 次方相反,表示为 x = log2n。这就是以前数学中学到的对数。

研究一下这个对数曲线图可以发现,随着数据量的增加,复杂度是缓缓增加的。这就是树的特性。随着数据量的增加,树结构可以比数组及链表的 O(n) 更快地进行处理(图 1.19)。

{%}

图 1.19 数组、链表与树的比较

让我们来比较一下分别用数组和树来查找 100 万个数据的情况。假设检查 1 个箱子的数据花费 1 毫秒,用数组查找 100 万个数据就需要 1000 秒。而使用树的话,1000 层花费 1 秒。大家可以看到这个效果有多明显了吧。

优点

树的优点是可以不用检查无关的数据。例如,选择查找树的右边的话,就可以不查找树的左边。并且,在查找的过程中,查找范围会逐渐缩小。假设需要查找 100 到 1000 这个范围的话,只需查找树的一部分就可以了。

缺点

首先,数据更新不方便。由于数据是按顺序排列的,如果要更新数据,需要先删除数据,然后再将其插入到正确的位置。而删除数据的位置,通常不会被填充,而是就这么空着。这样一来,空闲位置慢慢增多,会导致性能变差。

另外,如果总是放入相同的数据,会导致仅某一个特定位置的分支不断延伸,这样就不能发挥出它的性能优势(图 1.20 左)。而且当左右的平衡被破坏后,想要修复就需要很复杂的操作。如果左边数据过多,就需要把一些数据从左边移到右边(图 1.20 右)。我们经常听到“DB 的索引碎片化了,需要再整理一遍”,就是因为出现了这样的情况。

{%}

图 1.20 树结构的缺点

改进与变种

以上介绍的树称为“二叉树”。实际上,也存在 n 叉树。在 n 叉树中,树的高度会更低,查找也更有效率。例如,16 叉树的话,高度只有 5。16 的 5 次方是 1 048 576。如果在内存上能处理的话,二叉树就很简单实用了。而如果要调用存放在磁盘上的数据,为了减少调用次数,n 叉树则更合适。

产品中经常会使用“B 树”,这是尽量保持各分叉平衡的多叉树。“B+ 树”是“B 树”的变种,只在树的叶子节点处存放数据。

大家可能经常会见到“B* 树”这个名称,这是叶子节点连接成的链表结构(图 1.21)。B+ 树和 B* 树在 DB 和文件系统中都很常见,请好好掌握。

{%}

图 1.21 B+ 树与 B* 树

1.5.4 散列算法

笔者在大学的时候首次接触到该算法,使用该算法几乎只需要一次计算就能找出数据,这令笔者颇为震惊。还记得当时曾感慨“我是绝对想不到这种方法的”。首先,准备好与数据量相同或更大的数组。接着,对各个数据进行名为“散列”的运算,确定存放数据的位置(数组的下标)(图 1.22)。

{%}

图 1.22 散列计算的机制

最容易理解的散列计算就是取余(余数)的计算。假设有 8 个数据(1、5、9、13、16、27、38、102)。首先,准备好有 10 个箱子的数组。接着,对这些数据进行取余计算,把结果当作下标来使用。例如,1 除以 10 的余数是 1,13 除以 10 的余数是 3。通过这样计算,就能确定从 0 到 9 的下标。这些下标标明的就是数据存放的位置。接着,我们来试着找一下 102。没有必要从数组的开头依次查找,而是进行取余计算,得到余数 2。然后,利用“知道地址的话就能立即访问”这一计算机的特性,马上就能访问到 102。

复杂度

假设数据都已经放到箱子里了,那么散列算法的复杂度如何呢?由于只需要计算散列值,因此复杂度与数据的个数没有关系。也就是说,复杂度是 O(1)。不管数据怎么增加,几乎一瞬间都能获得结果。大家不觉得这个算法相当神奇吗?

优点

不必多说,散列算法的优点就是不论数据量怎么增加,都可以在一定时间内完成查找处理。并且,散列函数有消除不平衡性的效果。就上面的例子来说,数据大多是一位数或 10 到 20 之间的数字。102 前后空空荡荡。使用散列函数计算后,就不会产生这种空荡荡的情况。

缺点

虽然前面写了“消除不平衡性”,但是对于相同的数据,该算法是无能为力的,因为它们的散列值是相同的。此外,也存在不同的数据凑巧有相同的散列值的情况。例如,18 和 28 被 10 除,余数都是 8。我们把获得相同散列值的现象称为“碰撞”。这个时候应该怎么办呢?一个方法就是用链表结构连接起来(图 1.23)。另一个方法叫作“重散列”(ReHash),即再一次计算散列值,将其放在另外一个位置。

{%}

图 1.23 碰撞的处理

要注意由数据引起的不平衡情况。曾经在一个测试中,散列算法的效果没有表现出来,出现了不平衡,于是笔者就想这是为什么,调查一下原因才发现,因为数据是 11、21、31、41 这样有规则的,导致了余数相同。测试数据很难与生产环境的数据一致,一不小心就会拿到这种有规则的数据,请注意这种情况。

散列算法的一个隐形缺点是,用散列进行计算,并将其放入数组中,整个工作会花费很长时间(是 O(n))。因为进行查找前的这个工作很费时,所以虽然看起来散列算法是万能的,但其实要视实际情况而定。

改进与变种

可能读者会发出这样的疑问:应该如何计算字符串的散列值呢?字母也可以转化为数字。例如,由于在计算机中使用“字符编码”这样的数字来表示字符,因此可以考虑把字符串的字符编码的数字全部加起来,再计算余数。

1.5.5 队列

队列的大致流程就像是往管道中一个一个地放入小球,然后小球从管道前头一个个出来(图 1.24)。队列适用于按顺序处理的工作。超市里收银台前排起的队、银行里排起的队都是队列。和大家的直观感受是一样的。

{%}

图 1.24 队列的示意图

很难注意到的是,在系统中到处都存在着队列。比如,用《图解 OS、存储、网络:DB 的内部机制》3 这本书中的图来作一下说明,在图中的这些地方都存在着队列(图 1.25)。

3原书名为『絵で見てわかる OS/ ストレージ / ネットワーク〜 DB はこう使っている』。截至目前(2016 年 7 月),尚无中文版。——译者注

{%}

图 1.25 队列无处不在

我们把先放入的先处理这种形式称为 FIFO(First In First Out)。

复杂度

各个处理的复杂度一般都是 O(1)。只要记录了开头的数据在哪个位置,就可以立即进行处理。

另外,当队列出现性能问题的时候,通常是由于对队列进行了扫描(全部检查)。在清除队列的时候,或者不按放入顺序取出数据的时候,就会发生这样的操作。这个时候,复杂度就会变成 O(n),很容易出现性能问题。

优点

当有大量处理涌入时,可以先将其放入队列中,使其按到达顺序等待。访问高人气网站时,有时需要稍等片刻才会显示出画面。这种情况就是处理被放入到了某一个队列中,等前面的处理结束后才会进行。

此外,把队列用于多个系统之间的连接点,还可以将其作为缓冲。笔者也将其称为“分割事务”(图 1.26)。对于不稳定的系统或互联网来说,这是一个有效的手段。

{%}

图 1.26 通过堆积使处理分阶段进行

这样一来,用户的等待时间就会变短。另外,就算一下子来了很多处理,也不容易超出服务器的负荷。这就是把处理先堆积起来的好处。不过需要注意的是,这种方式并不适用于那些需要实时响应的处理。另外,为了确认处理结果,需要之后再重新访问一次。

缺点

队列并不是没有极限的,它也会溢出。在这种情况下,请求发起者不能分辨请求是已经完成了还是失败了。请求者会看到“响应有延迟,请稍后再试”这样的提示,而这个提示在队列溢出时也会出现。

此外,并不是把请求存放在队列里就万事大吉了。一旦过了时效,请求也就失效了。有时候比起把失效的请求暂存起来,直接将其判定为错误会让系统整体更健全(图 1.27)。这个问题会在第 4 章详细说明。

{%}

图 1.27 堆积太多也不好

改进与变种

除了使用链表结构之外,通过数组组成环形结构(到了最后面就再从头开始)来实现队列也是很常见的(图 1.28)。

{%}

图 1.28 队列的实现(环形结构)

有时候也会把队列的数据存放到 DB 或文件中(特别是如果数据丢失会很麻烦的情况下,通常会将其放在 DB 里),甚至有时候服务器和系统自身从整体来看也变成了一个队列。例如,在证券市场等场合中,从证券公司接受请求,然后基于一定的规则,按请求顺序来进行处理。从这个意义上来说,证券市场也可以被称为是一个庞大的队列系统。

使用数组和链表来实现队列的时候,随着数据的增加,从队列中查找数据的时间也会相应增加。因此,有时候为了能更方便地从队列中查找数据,也会特意使用树结构来实现队列。

1.5.6 栈

如果把队列描述为向管道中放入小球,那么“栈”就可以被描述为把文件和书等从下往上不断堆积。并且,栈的处理顺序是从上往下的。换句话说,就是新来的优先处理。比如,在写程序的时候,会碰到函数 A 要调用函数 B,函数 B 要调用函数 C 这样连续的处理。这个时候,在函数 A 的上面是函数 B,函数 B 的上面是函数 C(图 1.29)。

{%}

图 1.29 栈的示意图

像这样,先放入的东西反而后处理的方式叫作 FILO(First In Last Out)。

复杂度

单次处理的复杂度通常是 O(1)。

优点

栈的优点是:只占用必要的空间,不会让空间产生碎片。只要处理一完成,那部分空间就会被腾出来,形成连续的闲置空间,这样就可以在那里放置下一个请求(图 1.30)。

{%}

图 1.30 栈不会形成碎片

OS 在执行程序的时候,也使用这样的机制。因此,系统就不会白白浪费内存空间,可以运行尽可能多的函数。这个特性是队列很难实现的。

缺点

FILO 适用的情况很少。另外,硬要说的话,那就是最先放进去的数据会被一直放置到最后。但是,由于这个算法就是以此为前提的,因此在使用这个算法的系统中,大部分情况下都不会出现问题。

改进与变种

在 OS 上见到的进程的栈轨迹(Stack Trace)、Java VM 的 Thread Dump 的栈轨迹就是遍历栈后所获得的信息。换句话说,它以栈的形式展现了哪个函数调用了哪个函数。

1.5.7 排序(快速排序)

“排序”就是将数据按顺序排列。比较容易理解的是插入排序(Insert Sort),即把数据一个个取出来,插入到链表中的相应位置(图 1.31)。

{%}

图 1.31 插入排序的示意图

这里介绍一下在排序中性能不错的快速排序(Quick Sort)。假设数组中有 1 到 20 的数据,我们选择一个中间位置的数字 10,把比 10 小的数字移到数组左边,比 10 大的数字移到右边。接着,将左边的数字按照同样的方法进行划分,这样左边的数据就被很整齐地排好了。右边也同理。像这样,快速排序就像是从上往下生成树结构一样。

{%}

图 1.32 快速排序的示意图

复杂度

快速排序的复杂度平均来说是 O(n logn)4

4如果考虑到异常情况等,复杂度则是 O(n2)。因篇幅有限,本书中不再说明复杂度的计算方法以及异常情况。

优点

排序整体的优点就是可以使查找数据的速度变快。并且,通过排序,可以了解数据的重复情况。

缺点

排序的缺点就是排序本身会花费一定的时间。和进行 1 次查找比起来,排序更花时间。如果后面会频繁查找数据的话,排序就是一个有价值的工作,如果只会查找 1 次,那排序所带来的好处就很少了。

另外,费时也常常意味着成本上升。

改进与变种

排序的变种有很多,比较常见的有归并排序(Merge Sort)等。所谓归并排序,就是把排序完成的同类数据合并到一起,生成更大的排序数据的方法。

1.5.8 缓存①(回写)

虽然不能把缓存称为算法,但在考虑性能时它是一个非常重要的技术,所以在此介绍一下。缓存指的是“偷偷存放”的意思。在计算机中,缓存指的是为了提高性能而保存的东西。因为是为了提高性能,所以它比实际存放的场所距离更近,速度也更快。例如,CPU 也带有缓存。由于从主存储器和磁盘读取数据比较花时间,因此把经常使用的数据放在临近的位置有很多好处(图 1.33)。

{%}

图 1.33 缓存的优点

回写(Write Back)这种缓存方式指的是之后更新数据的方式,即在更新数据的时候,不更新数据实际存放的地方的数据,只更新缓存内的数据,之后再更新数据实际存放的地方(图 1.34)。

{%}

图 1.34 回写的动作

优点

数据实际存放的地方一般离得很远,所以处理速度很慢。回写则可以不用等待写入数据实际存放的地方,所以速度很快。

当然,如果读取也能通过缓存来进行,速度也很快。

缺点

如果缓存中的数据丢失,那么数据实际存放的地方的数据就一直是老数据,可能会导致数据不一致。如果一定要在数据实际存放的地方保存,就要使用后面提到的直写(Write Through)的方法。

改进与变种

有一些缓存是不会丢失数据的。如果缓存标有“非易失性”(Non-volatile)或“电池备份”(Battery Backup)等词语,那么即使突然停电或死机,数据应该也不会丢失。当然,进行了这样改进的缓存一般价格也很高。

1.5.9 缓存②(直写)

有时数据实际存放的地方也必须更新,这种情况下就要使用直写的方法。直写虽然会花费一些时间,但能确切地进行数据更新。例如“数据保存”等,因为数据丢失了会很麻烦,所以就需要确保写入磁盘。

优点

如果在缓存中有数据的话,读取会非常快速,并且也能确保数据写入。

缺点

完全写入数据实际存放的地方会花费时间,导致响应速度变慢。

改进与变种

在 OS 上写入东西的时候,并不是都是直写的方式,有时也会先暂时写入缓存,稍后再写入 OS。这就是 OS 必须要有关机这一步骤的一个原因。在关机的过程中,系统会将还未写入的数据同步到磁盘中。

当然,重要的写入一般都会指定“实时写入”。例如,DBMS 的日志数据如果丢失的话会很麻烦,所以通常都是“实时写入”。这就是即使机器死机了,DBMS 的数据还能恢复的原因。

COLUMN DMBS 是数据结构与算法的宝库

短期或长期保存数据,并且极致追求性能,这就是DBMS。因此,DBMS 中使用了各种数据结构和算法。学习了 DBMS 的内部结构后,自然而然地就对算法有详细的了解了。

例如,在索引中经常会使用树结构,有的 DBMS 在表的连接中使用散列。在 SQL 的处理中会出现排序,在生成索引时也需要排序。

笔者经常跟周围的人说“如果一个人在考虑算法的时候把 DBMS 也考虑进去,并以此来进行整体优化的话,那他就能独当一面了”。这是因为在工作中,很多人在进行优化时只考虑应用程序的算法(例如,应用程序根据需要只对 DBMS 进行必要的访问,如图 A 左边的例子),或者只考虑 DBMS(如图 A 右边的例子所示,认为 DBMS 的访问速度很快,应该没什么问题)。

{%}

图 A 常见的低效率情形

我们不应该这样片面地考虑,而应该把应用程序的算法和 DBMS 的算法放在一起来考虑,设计出整体来说最快的方法(图 B)。特别是在进行批处理时,这种方式是很重要的。

{%}

图 B 养成从整体来考虑的习惯

如果想要成为 DBMS 的专家,就学一下算法吧,一定会更擅长性能调优。

1.5.10 锁与性能

笔者在阅读介绍性能的图书时,经常会感到对于“锁”的说明还远远不够。在现实生活的性能问题中,和锁相关的问题是最多的。说到锁,会很容易想到 DB 的“行锁”“表锁”“Java 的锁”(synchronized)等,但除此之外,还有“CPU 的命令级别的锁”“OS 内部的锁”“DB 内部的锁”等,各种各样的锁无处不在。关于锁的实际操作我们会在第 4 章介绍,这里先介绍一下锁的相关知识。

锁的本质

锁是在并行处理的情况下所必需的机制。例如,在链表结构下,某个程序想要在 1 和 4 之间插入数据 2。几乎在同一时间,另一个程序想要在 1 和 4 之间插入数据 3。这时会出现什么情况呢?链表的结构就会被破坏掉(图 1.35)。

{%}

图 1.35 必须使用锁的原因

为了防止出现这样的情况,在更新链表的时候就需要让别的程序等待。锁说到底就是在某个处理进行期间起到保护作用的机制,是为了防止别的处理侵入。

前面介绍过的算法事实上很多都不允许时间上的偏差。除了数组的更新之外,链表结构、队列、栈以及树的更新也是如此。可能你也注意到了,基本上数据的更新操作都要用锁来进行保护。不过,如果已经知道只有自己会进行操作,那么不使用锁也没关系。之所以在学校里几乎不写使用锁的程序,就是这个原因。多人使用的实际系统中隐藏了大量的锁。

另外,读取有时也需要加锁。例如读取一个值后,一边处理这个值一边进行更新的情况。如果这个值在处理过程中发生了变化的话就会很麻烦,所以在读取的时候也要用到锁。

锁等待的时候发生了什么事

只有一个处理在进行的时候,不会发生锁等待。因此,在开发的时候一般都不会注意到。但是,在性能测试和在生产环境中运行的时候,就会有多个请求同时涌入,这样等待锁被释放的处理的数量也就增加了。等待锁释放就像是在银行柜台或超市收银台前排起的一个等待队列(图 1.36)。其特征是等待时间会以指数级别增长。性能测试不充分,就像是在超市开业之前收银台方面只演练了只有一名顾客时的情况,但是在开业后,突然有几十人同时到来,导致现场极度混乱。另外,性能测试的技巧会在第 5 章介绍。

{%}

图 1.36 由于锁等待而产生的等待队列

解决锁等待的方法

从锁的机制来考虑,怎么才能解决这个问题呢?在锁进行保护的过程中,只要处理没有完成,就不能释放锁,也就解决不了问题。因此,基本的解决方法就是“让正受保护的处理尽快完成”。如果是对 DB 的表加锁,并执行 SQL 语句,那么让那个 SQL 处理尽快完成,就能减少占有锁的时间。

另外,还有一种分割锁的方法。不对 DB 的表加锁,而是对行加锁执行 SQL 语句,这样就能并行执行了。像这样,通过细化分割锁的方法,也能减少等待时间。

COLUMN 【高级篇】锁的机制是如何实现的

锁的算法其实相当复杂。你可能会想“检查一下是否被加了锁,如果没有被加锁,那就设置一个标志(Flag)加上锁就好了”。很可惜,这个想法是错误的。例如,“看一下程序 A 是否加了锁……”“看一下程序B 是否加了锁……”这两个操作几乎同时发生的话,会怎么样呢?如果 CPU 的时钟稍微有差别,A 和 B 都被执行了,那二者都会误认为自己获得了锁(图 A)。

{%}

图 A 加锁的一瞬间

为了避免发生这样的时间错位,通常会使用硬件(CPU 等)的指令。而且,硬件的指令在执行时会确保“检查是否已被加锁”“如果没有被加锁的话就加锁”这样的指令不会插入进来。这称为“原子性”(Atomic),即处理只有成功或失败一种结果。使用这样的 CPU 指令后,就可以让锁不会出错。一般程序员不会直接使用这样的 CPU 指令,而是使用 OS 中的 mutex、Java 中的 synchronized 等已经实现了锁的函数。

如果读者有兴趣,可以查一下“Test and Set”“Compare and Swap”等术语。

 

COLUMN 【高级篇】性能优劣不能只看正常情况

事实上,性能最难的部分不是正常情况,而是异常情况。发生故障时进行切换或者突然有大流量涌来等非正常运行的时候,问题就在于如何更好地使用从第1 章到第4 章介绍的东西。在编写应用程序的时候,异常情况的处理更考验能力,而在性能方面,异常情况也是展示能力的地方。另外,有时也会出现起因于各种产品的组合的问题,即使是经验丰富的专家,也能从中发现新的东西。

现实中比较棘手的有系统维护时的性能、服务器刚搭建好时的性能(因为缓存等还没生效)、集群切换时的性能(资源迁移)、网络设备故障时的性能、恢复时候的性能等。

非要提出建议的话,大概也就是以下几点,即“在维护的时候,针对队列不一定要走索引处理,也可以走全扫描”“(为方便维护或切换)尽量不要携带过多资源。资源越多,越费时间”“(为方便维护或切换)尽量减少脏数据”“(为方便切换)设置好合适的超时时间”“在故障测试的时候施加负载,把性能也一起确认一下”。

目录