How Least Recently Used (LRU) list is managed in PostgreSQL?

How Least Recently Used (LRU) list is managed in PostgreSQL?


In PostgreSQL, the least recently used (LRU) list is a mechanism used to manage the buffer cache. The buffer cache is a memory area used to store recently accessed data pages, so that they can be quickly retrieved without needing to read them from disk.

The LRU list is used to keep track of the pages in the buffer cache and to determine which pages should be evicted (removed) when the cache becomes full. When a new page is added to the buffer cache, it is added to the head of the LRU list. When a page is accessed, it is moved to the head of the LRU list. Pages that have not been accessed for a longer period of time are closer to the tail of the LRU list.

When the buffer cache becomes full, the PostgreSQL’s buffer manager will remove pages from the tail of the LRU list (the least recently used pages) to make room for new pages. The pages that are evicted are either written to disk if they have been modified, or discarded if they have not been modified.

The LRU list is implemented as a doubly-linked list, which allows for efficient insertion, removal and movement of pages. The buffer manager uses a clock algorithm to keep track of the pages in the buffer cache and to determine which pages should be evicted. The clock algorithm uses a clock hand to move through the pages in the buffer cache and marking pages as accessed or not accessed.

Additionally, PostgreSQL uses the clock-sweep algorithm to optimize the buffer cache management. This algorithm attempts to minimize the number of pages that need to be evicted by considering the state of pages before evicting them.

It’s important to note that the buffer cache management is a complex task, and the LRU list management is just one part of it. The buffer manager is constantly monitoring and adjusting the buffer cache to ensure that it is used as efficiently as possible and also it’s important to monitor the buffer cache usage and adjust the settings accordingly to make sure that it is performing efficiently.

About Shiv Iyer 219 Articles
Open Source Database Systems Engineer with a deep understanding of Optimizer Internals, Performance Engineering, Scalability and Data SRE. Shiv currently is the Founder, Investor, Board Member and CEO of multiple Database Systems Infrastructure Operations companies in the Transaction Processing Computing and ColumnStores ecosystem. He is also a frequent speaker in open source software conferences globally.