Rethinking buffer pool page replacement
October 15, 2013 Leave a comment
Adam Storm – Senior Software Developer,IBM Toronto Lab.
Life as we know it is generally quite ordered. It’s common for drivers to take the same route to work every day, place their keys in the same spot when they arrive home, and then go to bed at the same time every night. These routines soon become habits, which free the mind to focus on more important, thought intensive work. In the field of computer science however, this determinism can sometimes create problems. For instance, elegant algorithms like Quicksort can perform poorly for certain input sets. When the algorithm is randomized however, it ironically becomes more predictable, and has better overall performance characteristics.
In the course of developing BLU Acceleration, we observed something interesting about our buffer pool victim selection algorithm (the algorithm which kicks-in when we want to find a page to evict from a full buffer pool) – it didn’t perform well on workloads which consisted primarily of large table (or in our case, column) scans.
Modern buffer pool victim selection algorithms usually utilize one or more of the following basic approaches:
- Least Recently Used (LRU) in which the least recently used page in the buffer pool is victimized.
- Most Recently Used (MRU) in which the most recently used page in the buffer pool is victimized.
- Least Frequently Used (LFU) in which the least frequently used page in the buffer pool is victimized.
Unfortunately, all of these approaches perform poorly in cases where a table (or column), which is larger than the buffer pool, is scanned repeatedly. Fortunately however, we noticed that by modifying the victim selection algorithm to take into account the size of the column relative to the size of the buffer pool, we could greatly improve the page reuse rates (aka, the buffer pool hit rates). Determining which pages to keep around was the tricky part. For that, we turned to randomness.
In the video below Chris Eaton and I discuss this new page replacement algorithm, which we call the Scan Friendly Victim Selection algorithm, in greater detail.
About the author:
In his 13 years at IBM Adam Storm has worked on many critical features in DB2, including the Self-Tuning Memory Manager, pureScale and BLU Acceleration. Adam is currently the architect for Insert, Update and Delete on column organized tables.