0

I am reading a book on databases and a chapter in it talks about buffer manager and it's replacement strategies.

The two popular replacement startegies mentioned are least recently used - LRU and clock replacement. I am interested in details about LRU. LRU is implemented via queue. When a pin count is set to 0, page in memory is added to queue. When a replecement is needed, memory page from the start of the queue is used.

The book does not describe how pin count (and dirty bit) for a page is stored. Is it stored inside the queue entries? Is it stored as part of the header in buffer pool frames?

Moreover, what happens if a page is accessed while being in the queue? Is it deleted from the queue immediately?

2 Answers 2

0

(I have not heard of a pin count; does "pin" stand for something?)

A cache of things needs some subset of the following for each entry:

  • A timestamp or sequence number of when it was last used. Or this may be implemented via a linked list. (This may be the LRU queue you are referring to.)
  • An expiration date (rare).
  • A "dirty" flag, indicating that it has been changed. More specifically, that it disagrees with disk, so it must be written out before being freed.
  • Reference count -- This indicates how many threads (or whatever) have latched onto this item. (Not always present.)
  • A lock -- either on the item or on the entire table. This is used to avoid modifying data, links, flags, etc, versus freeing up the item. You must not allow one thread to free up an item while another thread is using the item. (This sort of addresses your last question.)
  • Forward and backward links to other items. (Especially useful if items are variable length.)
  • The item may be completely self-contained (eg when using RAM), or it may involve two blocks of info when using disk -- Keep the links, dirty bit, etc in RAM. That way you don't have to do an expensive I/O for following links or checking/setting the dirty bit. (So, the location of the dirty bit "depends".)

My rambling answer points out that there are many ways to implement a LRU cache. Your questions indicate that you are beginning to understand the complexity of this basic construct.

2
  • Thanks. pin count == reference count . The book I am reading suggests implementation using queue. And it uses 10 sentences to describe it :)
    – sanjihan
    Aug 8, 2019 at 19:30
  • @sanjihan - Geez, 10 sentences? A "reference count" is usually just a number.
    – Rick James
    Aug 8, 2019 at 22:38
0

Since you tagged this question with , in the case of InnoDB's buffer pool you can read a bit about it here: https://dev.mysql.com/doc/refman/8.0/en/innodb-buffer-pool.html

InnoDB maintains two separate queues of pages. The more recently accessed pages are "young" or "new" and they get their own LRU queue. The more distantly accessed pages are "old". I don't find these terms very intuitive, but I didn't make them up.

The first time a page is loaded, it's put at the head of the "old" queue. Pages can move from one queue to the other. For example, if a page in the old queue is accessed by a user query, it is moved to the new queue.

Then when pages are evicted, they prefer to be taken out of the "old" queue. This makes it more likely for rapid turnover in the buffer pool to affect pages that have only been accessed once. So even an operation like table-scan that caused complete turnover of the LRU buffer tends to evict only pages in the old queue, again and again, and doesn't disturb the pages in the new queue.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.