首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >每周学点大数据 | No.21磁盘算法概述

每周学点大数据 | No.21磁盘算法概述

作者头像
灯塔大数据
发布2018-04-08 16:05:26
7110
发布2018-04-08 16:05:26
举报
文章被收录于专栏:灯塔大数据灯塔大数据

No.21期

磁盘算法概述

Mr. 王:现在我们谈谈磁盘算法的问题。根据你的了解,跟我说说计算机中都采用了哪些种类的存储器?

小可:这个我还是略知一二的。计算机中有很多用来存储数据的存储器,比如寄存器、缓存(Cache)、内存和硬盘等。

Mr. 王:这些存储结构都有什么特点呢?

小可:寄存器、缓存和内存都是需要依靠电来维持其所存储的数据的,而磁盘可以在断电的情况下保存数据。数据是存储在磁性介质上的。

Mr. 王:它们的速度、容量和价格又如何呢?

小可:它们的容量是依次变大的,但访问速度却是越来越慢的,而且越快的存储器相对也就越昂贵。

Mr. 王:是的,计算机中存储器的价格衡量标准是单位存储空间的价格。寄存器在计算机中的存储空间是比较小的,现代计算机中的寄存器一般都直接集成在CPU 内部,但寄存器的存取速度是最快的,往往可以用来存储CPU 运行的中间结果。

Cache 的价格比寄存器稍便宜,存储空间也比寄存器大,它的存取速度比寄存器稍慢一些,它往往处在内存和CPU 中间,用来缓存数据,使得当CPU 需要用到一些数据时,可以快速地找它们,而不是到内存中去寻找。

下一级别的存储器是内存,内存也叫主存,存储空间相对较大,它的存取速度比Cache 慢,但比各种外存设备快得多,一般用于在程序执行时存储程序和必要的数据,我们在运行程序时,也要将程序从磁盘加载到内存中。

价格最便宜而存取速度最慢的设备叫作辅存,计算机中最典型的辅存就是磁盘,当然常见的还有光盘等。它们适合存储大量的数据,而且这些数据存储在磁性介质或者光介质上,并不依赖于电力,在系统断电之后数据也不会消失。

从价格、存取速度和空间的角度来看,设置多级存储结构还是非常有必要的,这能够让我们在最节省钱的情况下,达到最好的存储和访问效果。

小可:我知道多数程序都是在内存中运行的,那我们为什么还需要磁盘算法呢?

Mr. 王:其实这个很显然啊,内存的容量是有限的,我们在处理很多问题时,需要比现有内存更大的空间来存储数据,自然也就需要磁盘这样的大容量存储介质来帮忙了。相对于内存来讲,像磁盘、磁带这样的存储介质一般称作外存,所以磁盘算法也叫外存算法。

小可:那么把数据存放在内存中和存放在磁盘中,我们在进行处理时有什么区别呢?

Mr. 王:我们知道,内存是可以进行随机访问的。也就是说,给出一个内存地址,我们就可以很快地把数据找出来。硬盘可就不一样了,它是由一层层的盘片组成的,磁盘上有一个读写头,通过读写头的旋转来找到盘片上的不同位置。

如果要在硬盘上找两个数据,在找到第一个数据之后去寻找第二个数据时,需要旋转读写头,如果这两个数据的距离比较远的话,读写头需要旋转的距离也就很远。这导致硬盘的读写速度是很慢的,其访问速度比内存要慢上106倍。

小可:那的确是够慢的了。

Mr. 王:想想看,这个问题可以怎么解决?

小可:访问开销比较大的原因就是磁盘读写头的旋转消耗了时间,如果需要连续读取的两个数据离得很近或者是相邻的,那么旋转读写头的时间就很短,可以很快速地把数据取出来,额外的开销也就会变得非常小,因此我们只要把数据都连起来存储就好了。

Mr. 王:不错,所以硬盘尽可能将连续读取的数据放在一起,用大规模连续的数据传输来平摊消耗。因此,硬盘的一个重要特点就是它以块为单位进行访问,一般这个块的大小是8 ~ 16KB,以保证高效地进行数据存取。

在以往的计算模型中,我们关注的只有CPU 和内存,程序和各种数据存储在内存中,CPU 调取这些数据进行处理,而当数据量比较大时,或者操作系统到硬盘中读取内容时,就不得不考虑磁盘输入输出(磁盘I/O)带来的额外开销了,这也是我们要来讨论磁盘算法的意义所在。上面的图说明了数据量和程序运行时间的关系。

不难看出,当数据量大到一定程度时,运行时间会产生一个阶跃。这个阶跃就出现在数据量突破了内存的容量时,我们不得不将数据存储在磁盘中,然后不断地将需要用到的数据加载进内存中,再进行进一步的处理。另外,当算法不够好时,虚拟内存会不断地访问磁盘,不停地产生掉页错误,最终导致算法的运行开销大大增加。

小可:看来设计好的磁盘算法还真的很有必要啊。请老师给我举几个磁盘算法的例子吧。

Mr. 王:先别着急,我们要先建立一个磁盘模型,因为之前的算法都是运行在内存中的。

我们用圆柱体来代表磁盘,矩形框就是内存。内存和磁盘之间的I/O(输入输出)交互是以块为单位进行的。

我们先来设几个基本项:

N= # 问题实例数据项个数

B= # 每个磁盘块中的数据项个数

M= # 内存能容纳的数据项个数

T= # 输出数据项个数

I/O= # 内存和磁盘之间移动的块数

简单解释一下这几个量。

N 就是我们在分析算法中使用的n,用它来表示算法需要处理的数据规模。

B 是每个磁盘块可以容纳的数据项个数,前面我们提到,数据在磁盘上是以块为单位存储的,而对于每个问题而言,一个数据的大小也是不同的,所以用B 来表示一个磁盘块可以容纳多少单位数据。

M 表示内存中可以容纳的数据项个数,也就是我们为这个程序存储分配的内存空间可以容纳多少个数据。

T 是输出数据项的个数,在我们的分析里很少涉及这个概念。我们把内存和外存交换一个磁盘块定义为一次I/O,这个I/O 量表示的就是内存和磁盘之间进行了多少次磁盘块交换。

另外,在这里要给出一个非常重要的假设:M>B2。这就是说,内存的大小要比磁盘块大小的平方大。如果没有这个假设的话,很多磁盘算法的设计与分析会变得异常复杂,而且这个条件在现代的计算机系统中是非常容易满足的。所以我们就基于这个假设,来展开对磁盘算法的研究。

这里还要介绍一个内容,就是根据计算复杂性理论,我们要知道在内存和外存中各种基本算法的时间下限。

小可:为什么内存算法和磁盘算法会产生这么大的区别呢?而且为什么硬盘算法的界限反而变小了呢?

Mr. 王:我们就拿浏览来解释一下吧。如果有N 个数据,在内存中只要一个个地读取就可以了。而对于磁盘中的数据,我们要先将数据从磁盘读入内存中,而且每次只能读一个磁盘块,所以当一个磁盘块包含B 个数据项时,就需要进行次I/O。

注意,我们在讨论磁盘算法的时间界限时,研究的是以I/O 为单位进行运算的,而不是以对数据进行一次操作为单位的。简单来说,我们关注的仅仅包括访问磁盘的次数,时间界限和复杂度计算衡量的也就是访问磁盘的I/O 量。这是由于相比访问磁盘的开销,访问内存的开销已经可以忽略不计了。我们只要能够很好地控制I/O 的次数,就可以很好地降低磁盘算法的运行复杂度。

小可:原来是这样啊。

Mr. 王:此时,我们对一些概念的定义也就发生了变化,比如在磁盘算法中,线性算法指的是o()的算法。

小可:嗯,就以浏览为例,内存算法中的线性算法O(N) 对应的就是磁盘算法中的o()。

Mr. 王:另外,磁盘块的大小B 是一个非常重要的量,它对I/O 复杂度的影响是非常大的。一般来说<≪N。。另外,我们不能用搜索树对排序进行优化,因为不能保证搜索树在磁盘中是连续存储的,如果不是连续存储的,那么开销依然是很大的,达不到优化的目的。

Mr. 王:在前面的式子中,≪N这一点是非常重要的,这里先举一个最简单的例子来说明这个问题。就以遍历链表(链表排序)为例,数组大小N = 10 个(元素),磁盘块大小B= 2 个(元素),内存大小M = 4 个(元素)。

小可:这就是说,内存中能装下两个磁盘块。

Mr. 王:是的,看一下这两个图:

我们注意到,在两个图中,数据都是按照数字编号的逻辑次序进行访问的,但它们存放在磁盘中的物理顺序却是不一样的。在左图中,我们首先访问数据1,需要从磁盘中加载[1][5]

这个磁盘块进入内存,然后访问数据2,加载[2][6] 这个磁盘块进入内存。访问数据3 时,内存不足,加载[3][8] 这个磁盘块,并换出[1][5],依此类推。不难发现,在这种磁盘存储的情况下,我们每访问一个数据节点,就需要换入换出一个磁盘块,进行的数据访问次数和N 的数量级相同,本例中共进行了10 次磁盘I/O。

而在右图中,数据节点存储的连续性相对较好,访问数据1 时,加载[1][2] 块,访问数据2 时,不需要加载新的磁盘块,直接访问内存中的[2] 即可。[3][4] 也在一个磁盘块中,同样只需要进行1 次磁盘I/O 就可以访问3 和4 两个数据节点。此时,我们是以磁盘块为单位进行磁盘I/O 的,只需要N/B 的数量级,本例中共进行了5 次磁盘I/O。

小可:单单这么少的数据,N 和就差了一半啊。

Mr. 王:在实际情况中,这两个数字的差距更为惊人。

例如:在某个磁盘中,N=256×,B=8000,如果访问磁盘的时间为1ms的话,N次I/O需要256×s=4266min=71hr,而N/B次I/O只需要256/8s=32s。

小可吃惊地说:71hr 和32s,竟然可以相差如此之多。

Mr. 王点点头,说:这说明o() 和O(N) 不是一个数量级的量,在学习磁盘算法的过程中一定要非常注意,O(N) 对于磁盘来说不是线性算法,O(N) 的算法在实际运行的过程中会产生大量的磁盘I/O,效率是非常低的。

内容来源:灯塔大数据

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2017-01-06,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 灯塔大数据 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
相关产品与服务
对象存储
对象存储(Cloud Object Storage,COS)是由腾讯云推出的无目录层次结构、无数据格式限制,可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限,无需分区管理,适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档