每周学点大数据 | No.60磁盘算法实践

灯塔大数据

发布于 2018-04-04 12:01:43

7730

发布于 2018-04-04 12:01:43

文章被收录于专栏：灯塔大数据灯塔大数据

NO.60

磁盘算法实践

Mr. 王：前面讨论了很多理论方面的内容，从今天开始，我们研究如何从实践的角度去进行磁盘算法、并行算法和众包算法的设计。

小可：嗯，我也很想实际写几个程序去操作前面提过的算法。

Mr. 王：那么我们就从磁盘算法的实践开始吧。

小可：我们平时使用的计算机上的数据很多都是以文件形式进行存储的，那么是不是只要借助C 语言读写文件的函数就可以操作磁盘了呢？

Mr. 王：文件的确是存储在磁盘上的，读写文件的操作也的确会产生磁盘读写。不过这样做大量的操作都是操作系统帮助我们完成的，对磁盘读写的大量细节我们并没有看到，在这里我会通过一些基本的程序，展示一个磁盘算法读写磁盘时的很多细节操作。

小可：嗯，在很多底层的操作中，操作系统和高级语言中封装好的函数为我们完成了太多的工作。

Mr. 王：现在我们就来深度剖析读写磁盘的过程。

首先给出两个用C/C++ 语言读写磁盘的程序。

Mr. 王：上面两个函数分别是从磁盘读取字节数据和向磁盘写入字节数据的实现代码。我们来研究一下这段代码，暂时不关心其中一些函数的实现细节，先来看看这两个函数完成了什么工作。先说说写磁盘程序。首先要明确的一点是，并不是每当要进行磁盘读写时，都直接读写磁盘，这样做是非常不经济的。所以当要读写磁盘时，就需要在内存中开辟一块空间，称作Buffer（缓冲区）。在写磁盘程序的开始，我们先检测缓冲区的页上还有没有剩余的空间去容纳所要写入的内容。如果有，就直接把它们先存放在缓冲区中，并且将缓冲区的偏移量位置向前移动。

但如果页上剩余的空间不足以容纳所要写入内容的大小，那么就先将这个内存页剩余的部

分填满。

接下来，对当前操作的内存页执行Unpin 操作。

然后增加页的编号，并且将偏移量归零。

再对新到达的内存页执行Pin 操作。

将在前一个页上还没有装满的数据填满，并设置偏移量。

小可：等等，老师，其中涉及了两个概念Pin 和Unpin，这是什么意思呢？

Mr. 王：这是磁盘操作中十分关键的两个操作。之前我们也讨论过，在操作磁盘的过程中，我们并不会直接去操作磁盘，而是将磁盘块加载到内存中来，在内存中进行操作和处理。读写磁盘也是一样，我们会在内存中建立一个缓冲区，在缓冲区中存放要操作的磁盘块的数据镜像。此时当需要读取某一部分数据时，如果磁盘中已经存在这部分数据，就不必要再从磁盘中读取数据了，而是从内存中读取该数据。

小可：嗯，毕竟操作内存要比操作磁盘快得多。

Mr. 王：可是，由于我们在不停地对磁盘进行着读写操作，所以很多时候，缓冲区中的数据和磁盘中的数据并不是一致的，这就会带来很严重的问题——“脏数据”。下面举一个例子来说明这个问题，比如有一个进程正在修改一个磁盘块的内容，而另一个进程要读取该内容，此时磁盘块中的数据并没有修改完成，所读取的数据并不是正确的数据。为了避免发生这种读取不一致数据的问题，我们引入了基本操作——Pin 和Unpin。正像它们的名字一样，Pin 是用一个“针”把这个磁盘块给“钉住”，不允许其他进程来读取它的值，因为有一个进程正在写它，这时候读取的值是不正确的。Unpin 正相反，就是写这个磁盘块的过程已经结束，现在内存中的缓冲区和磁盘块中的内容已经一致，可以安全地读取其数据了，此时就不必再“钉住”它了。

小可：哦，我懂了，简单来说，就是防止其他进程在写的过程中读取了正在被写的数据。

Mr. 王：是的。类似的机制在很多两级存储器中有所体现，比如内存和高速缓存（Cache）之间也有相似的机制，以防止CPU 读到Cache 和内存中不一致的数据。

小可：可是Pin 和Unpin 又是如何实现的呢？

Mr. 王：接下来我们就来谈谈Pin 和Unpin 的实现。其实Pin 和Unpin 这两个操作的原理很简单，我们只需要维护一个查找表，这个查找表标记着各个磁盘块和其对应的内存缓冲区的状态。PinPage 函数完成了这样的功能：对id 为pid 的页执行Pin 操作，程序会将磁盘中非空且不在缓冲区中的对应页加载到内存中。程序在执行过程中，首先会在缓冲区中为新来的页寻找空间，如果没有足够的空间，程序会从缓冲区中寻找一个页替换出去，以提供空间给新的页；如果仍然找不到这样的页，就会报错。如果读入的页不是空的，则将正常执行操作，Pin 操作，并且在Hash 表中存储页号和帧号，以标记这是一个已加入缓冲区的被Pin 页。下面是PinPage 的源代码。