专栏首页灯塔大数据每周学点大数据 | No.60磁盘算法实践

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

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 的源代码。

小可:等等,老师,这里提到了一个概念Hash 表,这是什么呢?

文章作者:王宏志

文章编辑:秦革

本文分享自微信公众号 - 灯塔大数据(DTbigdata),作者:王宏志

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2017-11-03

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

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

    No.21期 磁盘算法概述 Mr. 王:现在我们谈谈磁盘算法的问题。根据你的了解,跟我说说计算机中都采用了哪些种类的存储器? 小可:这个我还是略知一二...

    灯塔大数据
  • 每周学点大数据 | No.23 外排序(二)

    No.23期 外排序(二) Mr. 王:接下来我们用一个例子对磁盘归并排序进行说明。先来约定讨论的参数:N=24,M=8,B=2。 小可:嗯,一共有2...

    灯塔大数据
  • 每周学点大数据 | No.28 表排序

    No.28期 表排序 Mr. 王:前面我们讨论了一些基础磁盘算法,现在我们来讨论一些关于磁盘中图算法的问题。 通过对基础磁盘算法的学习,我们可以很容易地想到...

    灯塔大数据
  • 视频流媒体平台EasyNVR直播出现卡顿及重复播放视频片段问题应该如何解决?

    我们之前为大家解答过不少关于流媒体服务器可能出现的问题,比如降低直播延迟、302重定向、播放中断等问题,都为大家提出了适合的解决办法。我们的流媒体服务器一次授权...

    EasyNVR
  • ASM 翻译系列第七弹:高级知识 How many partners?

    原作者:Bane Radulovic 译者: 庄培培 审核: 魏兴华 DBGeeK社群联合出品 ASM的数据冗余机制是通过将extent的镜像副本复...

    沃趣科技
  • 云计算RAID的六种应用场景

    1、客户要求高可靠性:客户的数据最终存储到了磁盘,如SATA、SAS、SSD介质,如果磁盘损坏,数据不能丢失,怎么办?

    希望的田野
  • 开发应该知道的Linux系统分析-IO篇

    小文件读写的性能瓶颈是磁盘的寻址(随机读写性能更差),评估的标准是tps。大文件读写的性能瓶颈是带宽,评估的标准是持续的读写速度。Linux可以利用空闲内存作文...

    只喝牛奶的杀手
  • 沃趣科技火线救援某公安系统核心业务数据

    求助电话 只剩下键盘敲打声的办公室,被一个突如其来的电话打破了宁静。电话那头,是某公安客户的紧急求助。 案发现场 其核心数据库,由于存储突然断电,导致数据库实例...

    沃趣科技
  • 每周学点大数据 | No.21磁盘算法概述

    No.21期 磁盘算法概述 Mr. 王:现在我们谈谈磁盘算法的问题。根据你的了解,跟我说说计算机中都采用了哪些种类的存储器? 小可:这个我还是略知一二...

    灯塔大数据
  • ASM 翻译系列第十一弹:高级知识 Offline or drop?

    原作者:Bane Radulovic 译者: 庄培培 审核: 魏兴华 DBGeeK社群联合出品 Offline or drop? 当一个ASM磁盘不...

    沃趣科技

扫码关注云+社区

领取腾讯云代金券