LRU-K algorithm – Quick look

Dear Friends,

To start with; we can use a data or index page only when they exist in memory. For improved performance it is very important to keep alive the supply of buffer page for immediate use failing which would result in searching out many memory pages to locate a free buffer to be used as a workspace. SQL Server maintains a linked list of free page addresses and if any; worker needing a buffer uses the first available page in the list.

A single mechanism is responsible for both writing changed pages to disk and for making free those pages that are not referenced for some time in SQL Server 2008. Every buffer in data cache is having header that contains information when the page was referenced last two times and status information and if the page is dirty i.e. if changed since it was read into the disk. This reference information is used to implement the page replacement policy for data cache pages that uses LRU-K algorithm. You can read more on this algorithm here.

This algorithm takes a step ahead of Lest Recently Used (LRU) policy which had no knowledge of how recently the page was accessed or used as you call it. There is an improvement over Least Frequently Used (LFU) method by adding reference counters as it requires fewer adjustments by the engine. An LRU-K algorithm keeps track of the last K times a page was referenced and able to differentiate between data, index pages and level of frequency. SQL Server 2008 uses K value of 2 as such keeps track of the two most recent accesses of each page in buffer.

Data cache is scanned periodically from start to end. As buffer cache all in memory so these scans are very quick and there is no IO overhead.  Each buffer is assigned a value based on its usage history and when the value gets low enough, dirty page indicator is checked. If the page found to be dirty, a write is scheduled to write the modifications to disk. SQL Server use WAL so write of the dirty page is blocked while the log page recording the modification to disk first. Once modified page is flushed to disk or if the page is not dirty to start with, it is freed. The link between buffer page and data cache page that it contains is removed by deleting information about the buffer from hash table, and then buffer is put into free list.

I hope this explains the topic.

Regards

Kanchan Bhattacharyya

Like us on FaceBook Follow us on Twitter | Join the fastest growing SQL Server group on FaceBook

Follow me on TwitterFollow me on FaceBook

Avatar

About Kanchan Bhattacharyya

Kanchan is an astute IT professional, a seasoned SQL Database Administrator with 13+ years of industry experience. A calculated risk taker with deep technical knowledge and has gained proficiency in database consulting and solutions across different environments. Kanchan holds MBA degree in IT and an International Executive MBA in Project Management. He is very passionate about SQL Server and holds MCSE (Data Platform), MCSA – SQL 2012, MCITP – SQL 2008 certifications. Currently he is focusing on cloud and latest releases of SQL Server. When not working, Kanchan likes to spend his time reading on new technical developments specifically on SQL Server and other related technologies.

View all posts by Kanchan Bhattacharyya →

Leave a Reply

Your email address will not be published. Required fields are marked *