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?


(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.

  • 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 '19 at 19:30
  • @sanjihan - Geez, 10 sentences? A "reference count" is usually just a number.
    – Rick James
    Aug 8 '19 at 22:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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