专栏首页数据库架构之美为什么PostgreSQL抛弃了LRU算法而使用时钟扫描?

为什么PostgreSQL抛弃了LRU算法而使用时钟扫描?

我们知道LRU(Least Recently Used)最近最少使用算法被广泛运用于操作系统及数据库的内存淘汰机制上,比如mysql的缓冲区页面置换算法就是使用LRU。当然还有lfu(最不经常使用算法)和fifo(先进先出算法)。下面先来看看lru算法。

LRU算法

通过下面的图来说明一下置换过程:

我们可以使用双向链表来将页面串联起来,使用双向链表而不是单向链表的原因是双向链表在进行页面淘汰后可以反向更改页面指针,指向相邻页面。

再看看上面的过程,页面4,7,0被相继读入缓冲区,第四步页面需要访问页面7,然后就会去遍历该链表,发现找到了7号页面,而且此时页面没有全部用满,那么将页面7提到表头(通过更改双向链表的指针指向实现),然后页面1被读到缓冲区,然后读取页面0,遍历链表找到了页面0并将页面0提到表头,其他步骤类似,再看看置换,比如最后一步,读取页面6,遍历链表后发现页面6没有找到,此时缓冲区已满,这时需要从缓冲区中置换掉链表最尾部(最近最少使用)的页面4进行淘汰,并且把页面6放在表头。

Clock算法

下面先来说说clock算法的过程。Clock算法为每页设置一位访问标识usage_tag,内存中的所有页面以链表的形式组成一个环形队列。当某页被访问时,其访问标识u就被置1。

Clock在需要进行页面淘汰时会循环地扫描环形队列的页面,如果发现页面访问位u=0,就选择该页换出;若u=1,则重新将它置0,这样该页面本次就不会被换出,有了第二次驻留内存的机会,再继续检查下一个页面。当检查到队列中的最后一个页面时,若其访问位仍为1,则再返回到队首去检查第一个页面,本轮检查就一定有u=0的页面了,然后会将第一个u=0的页面换出。

Clock算法实现起来更简单,性能也接近LRU,在clock的基础上又有改进的clock算法。

改进的clock算法

改进的clock算法是在clock算法的基础上再增加一个一个修改位modify_tag,标识该页面是否被修改。为什么增加修改位m呢,因为被修改的页面(也称为脏页)如果被替换出去必须要先强制刷盘,所以我们的原则是尽量优先替换未被修改过的页面。所以改进的clock算法页面替换原则顺序如下:

①先替换最近未被访问,也未被修改的页(u=0, m=0)。

②再替换最近被访问,但未被修改的页(u=1, m=0)。

③再替换最近未被访问,但被修改的页(u=0, m=1)。

④最后替换最近被访问,被修改的页(u=1, m=1)。

PostgreSQL中的clock算法

PG作为学术派数据库在改进的时钟扫描算法上又做了进一步创新,将usage_tag从一个布尔值的标识位改为usage_count的数值位,u代表了该页面被使用的次数,而不再是是否被使用。通过下面这个图看看PG的时钟扫描算法过程。当然pg缓冲区的三层结构不再介绍了,毕竟不是研发人员,了解下原理就行。

①受害者指针指向第一个描述符(buffer_id=1),发现它的状态是pinned(被钉住m=1,可以理解为modify_tag=1),故跳过该描述符。 ②受害者指针指向第二个描述符(buffer_id=2),发现此描述符的状态是unpinned(未被钉住m=0)但其usage_count为2,此时将usage_count减1,受害者指针继续前进。 ③受害者指针指向第三个描述符(buffer_id=3),状态描述符为unpinned(m=0),而且usage_count=0,所以该描述符被选为本轮的受害者进行替换。

从上面的过程可以看出,每当循环扫描缓冲区时,如果存在未被修改的页面,该页面的usage_count就会减少1。所以,如果缓冲池中存在未被修改的页面时,此算法始终可以通过若干次扫描找到usage_count=0的页面。

PG中的时钟扫描算法相比两标识位的时钟扫描更加精细,相当于为每个最近被使用的页面增加了权重,使用越频繁越不容易被替换出去,更加符合真实的场景。

本文分享自微信公众号 - 数据库架构之美(databasekernel),作者:dbaer

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

原始发表时间:2020-02-11

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 全面讲解分布式数据库架构设计特点

    随着全球经济下行压力增大,中美贸易摩擦愈演愈烈,美国一系列的经济制裁和技术封锁使得我们有种被扼住咽喉的感觉,数据库作为基础软件中的重要一环有着很深的技术含量,在...

    数据库架构之美
  • 为什么说GTM是所有PGXC架构分布式数据库无法逾越的性能瓶颈?

    熟悉pg的人对pgxc都不陌生,pgxc最初由stromdb公司开发,应用于商业,后来被TransLattice收购并将其开源,也就是现在的pgxl。Pgxc是...

    数据库架构之美
  • 商业银行如何进行分布式数据库选型思考

    在传统数据大集中的环境下,银行核心系统很容易发生故障,而且一旦发生故障,影响面将特别广,带来很大的舆论压力和监管压力,历史上大型商业银行核心系统故障的例子不在少...

    数据库架构之美
  • 页面置换算法

    操作系统将内存按照页的进行管理,在需要的时候才把进程相应的部分调入内存。当产生缺页中断时,需要选择一个页面写入。如果要换出的页面在内存中被修改过,变成了“脏”页...

    233333
  • 2019年,网上商城链接优化的几个小技巧!

    如果你在电子商务领域从业多年,并且正在运营一个网上商城,我们知道电子商务SEO是每个营销人员的必修课,而电商网站最大的特点就是,链接结构复杂,URL数目众多,为...

    蝙蝠侠IT
  • 啥是佩奇排名算法

    佩奇排名是根据页面之间的链接结构计算页面的值的一种算法。下面我们通过动画来理解进行计算的具体流程。

    五分钟学算法
  • 你知道“啥是佩奇”,却不一定了解佩奇排名算法

    佩奇排名是根据页面之间的链接结构计算页面的值的一种算法。下面我们通过动画来理解进行计算的具体流程。

    AI科技大本营
  • SEO常见疑问整理总结(一)

    黄伟SEO
  • 数字广告基本术语

    Rich Media:(富媒体),这种应用采取了所有适合的最先进技术,以最好的传达广告主的信息,甚至与用户进行互动!如视频、flash广告等 植入式广告:在...

    城市中的游牧民族
  • H5与App的通讯方式

    现在不管是桌面客户端还是移动客户端,都会夹杂着一部分H5页面,这种混合式的应用也是我们常说的Hybrid App。为什么会出现Hybrid App呢,早期是因为...

    JowayYoung

扫码关注云+社区

领取腾讯云代金券