Technology Used

Tagging system to be added.

Raison D’etre

We aim to change PostgreSQL’s buffer replacement policy from its current clock-sweep algorithm (that uses LRU) to MRU. While MRU is often not used for a reason—the current algorithm used by Postgres is often more efficient in most cases—there sometimes exists cases where MRU is preferred (see sequential flooding and caching).

In the Weeds

To implement MRU in Postgres, we get rid of logic pertaining to the Clock Sweep algorithm and modify each buffer so that it keeps track of when it was last used with a timestamp (initialized in buf_init.c); we add this timestamp in buf_internals.h. In bufmgr.h, we keep a global variable of the timestamp value so that it does not reset with each buffer used; we also initialize the timestamp value for each new page in the buffer pool when the page is last used (based on the global timestamp value).

The timestamp simply increments with each successive use of a buffer page, meaning that the candidate buffer with the highest timestamp value is the most recently used and hence the page to be replaced. We use the same logic as provided in the original PSQL code to determine which buffers are candidate buffers in freelist.c. Then, we loop through those candidate buffers and find the buffer with the greatest timestamp value, returning it in the StrategyGetBuffer replacement function as the most recently used buffer page to be replaced.

Challenges

Global variables are usually not great!