专栏首页数据库架构之美为什么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 条评论
登录 后参与评论

相关文章

  • A Comprehensive Guide: PostgreSQL Shared Buffers(译)

    与MySQL设置innodb_buffer_pool_size = 80%左右的系统内存相比,也就是将操作系统大部分内存分配给Innodb的buffer poo...

    数据库架构之美
  • POSTGRESQL 吊打 ORACLE 的“傲娇”

    大早上的因为昨天的网络问题,MGR 的一台机器就unreachable, 按照流程将节点添加进原来的集群,失败failed, 搞了一上午,终于把集群 succe...

    AustinDatabases
  • 《逆袭进大厂》第六弹之操作系统汇总篇 | OS一次性更完

    算了吃啥午餐啊,我直接放大招,把我自己整理的所有操作系统八股文一次性放出来给大家好了!

    拓跋阿秀
  • 页面置换算法

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

    233333
  • Redis的批量操作是什么?怎么实现的延时队列?以及订阅模式、LRU。

    这次的内容是我自己为了总结Redis知识而扩充的,上一篇其实已经总结了几点知识了,但是Redis的强大,以及适用范围之广可不是单单一篇博文就能总结清的。所以这次...

    纪莫
  • 内存耗尽后Redis会发生什么

    作为一台服务器来说,内存并不是无限的,所以总会存在内存耗尽的情况,那么当 Redis 服务器的内存耗尽后,如果继续执行请求命令,Redis 会如何处理呢?

    肉眼品世界
  • 内存耗尽后,Redis 会发生什么?

    作为一台服务器来说,内存并不是无限的,所以总会存在内存耗尽的情况,那么当 Redis 服务器的内存耗尽后,如果继续执行请求命令,Redis 会如何处理呢?

    孙玄@奈学教育
  • 大数据技术之_21_Redis学习_02_解析 Redis 配置文件 redis.conf + Redis 的持久化 + Redis 的事务 + Redis 的复制(Master/Slave)+ Re

    1、配置大小单位,开头定义了一些基本的度量单位,只支持 bytes(字节),不支持 bit(位数)。 2、对大小写不敏感。

    黑泽君
  • BP-Wrapper:无锁竞争的缓存替换算法系统框架

    最近看了一个golang的高性能缓存ristretto,该缓存可以很好地实现如下功能:

    charlieroro
  • Apache Spark常见的三大误解

    最近几年关于Apache Spark框架的声音是越来越多,而且慢慢地成为大数据领域的主流系统。最近几年Apache Spark和Apache Hadoop的Go...

    Albert陈凯
  • 面试官:你懂LRU?那你知道InnoDB里的LRU怎么做的吗?

    Innodb为了解决磁盘上磁盘速度和CPU速度不一致的问题,在操作磁盘上的数据时,先将数据加载至内存中,在内存中对数据页进行操作。 Mysql在启动的时候,会向...

    帅地
  • --PostgreSQL 怎么正确的开始POSTGRESQL 调优的活动 1

    文字内容来自于 postgresqlopen 2019 Mistaken And Ignored Parameters While Optimizing A P...

    AustinDatabases
  • Redis哨兵,持久化,主从

    Redis采用的是基于内存的采用的是单进程单线程模型的 KV 数据库,由C语言编写,官方提供的数据是可以达到100000+的QPS(每秒内查询次数)。

    Vincent-yuan
  • Redis入坟(四)Redis内存回收知多少

    Reids 所有的数据都是存储在内存中的,在某些情况下需要对占用的内存空间进行回收。内存回收主要分为两类,一类是 key 过期,一类是内存使用达到上限(max_...

    源码之路
  • 《吊打面试官》系列-Redis哨兵、持久化、主从、手撕LRU

    Redis在互联网技术存储方面使用如此广泛,几乎所有的后端技术面试官都要在Redis的使用和原理方面对小伙伴们进行360°的刁难。作为一个在互联网公司面一次拿一...

    Java3y
  • PostgreSQL autovacuum 优化与调试 (1 触发 autovacuum 的条件)

    PostgreSQL 的数据库系统中是需要进行autovacuum 进行表级别的数据清理的。在开始autovacuum 进行调优之前实际上是需要理解为什么需要...

    AustinDatabases
  • MySQL中的InnoDB 体系结构(中)

    在开始这部分内容之前,我们需要理清buffer和cache的差别,因为在数据库层面会有大量的buffer和cache的术语,我们在学习的时候非常容易混淆。

    jeanron100
  • MySQL中的InnoDB 体系结构(中)

    在开始这部分内容之前,我们需要理清buffer和cache的差别,因为在数据库层面会有大量的buffer和cache的术语,我们在学习的时候非常容易混淆。

    jeanron100
  • 页面调度算法模拟

    模拟实现的算法:FIFO,Optimal(最佳置换),LRU,Clock,改进的Clock算法 一、先入先出(FIFO): 最简单的页面置换算法是先入先出(FI...

    欠扁的小篮子

扫码关注云+社区

领取腾讯云代金券