Skip to Main Content

Breadcrumb

Question and Answer

Tom Kyte

Thanks for the question, Caglar.

Asked: January 13, 2014 - 10:09 pm UTC

Last updated: January 15, 2014 - 8:29 pm UTC

Version: 11.2.0

Viewed 10K+ times! This question is

You Asked

Dear Tom Kyte,

I am wondering couple of things about LRU list. Unfortunately, I couldn't find elaborated information.

q1) Basically, What does LRU list hold?

q2) Does it cover (link) to every data blocks (dirty, free, unused, etc.) in the buffer cache?

q3) How data block addresses and corresponding memory addresses match each other? What is the role of LRU list for matching each other.

q4) If it holds empty (free) buffers, how does LRU list work when phsical I/O happens?

Could you please give a simple example?

Thanks in advance.



and Tom said...

q1) anything? an LRU can hold anything you want and we have many "LRU's" for many bits of data.

LRU stands for 'least recently used'. It is a computer algorithm/technique used to manage data in a cache. When a cache becomes full and you need space for new things - you discard the least recently used items first (things you haven't used for a while but are in the cache consuming space).

q2) it is not specific to data blocks - and data blocks are not really kept in an LRU list, they are managed by a touch count these days - but that touch count algorithm is very much like an LRU so you can think of it that way. I prefer to describe it like that as most people are familiar with the concept of LRU

In short, when you hear LRU, think of a cache that manages some data (any data), and tends to discard items from the cache based on whether they have been used recently or not. The more recently something has been used - the more likely it is to stay in the cache.

q3) each block has a DBA - data block address - that consists of a file# and block#. This uniquely identifies a block in a database. We use that as the "key" to the block in the buffer cache.

The buffer cache can be thought of as being like a two dimensional array. There is an array of lists - the lists are blocks that are in the cache. In order to locate a block in the cache - we will take the DBA of the block and hash that to figure out what array would contain that block (if it is in the cache at all). So, we get that hash which will be a number between 0 and N-1 where N is the size of the array of lists. We would then use a cache buffers chains latch to secure access to that array element (a root pointer to a list of blocks). Once we have that latch - we can search that list for the block.

q4) there are many lists, when a buffer cache block is empty - it would be one a free list. When it is filled up - and has a block with a DBA assigned to it - it would be unlinked from the free list (which wouldn't need to be an LRU of course, it would just be a list) and linked into one of the lists in the array of lists based on the hash of its DBA.


see also:

http://docs.oracle.com/cd/E11882_01/server.112/e40540/memory.htm#CNCPT9833

Rating

  (2 ratings)

Is this answer out of date? If it is, please let us know via a Comment

Comments

Caglar, January 15, 2014 - 11:14 am UTC

First of all, thanks for your remarkable and valuable thoughts.

Could you please clear my doubts related to your respond.

"data blocks are not really kept in an LRU list"

So, canb we say DBAs are kept in an LRU list?

"they are managed by a touch count these days - but that touch count algorithm is very much like an LRU so you can think of it that way."

I thought touch count algorith works on LRU list?

"there are many lists, when a buffer cache block is empty"

Could you please elaborate above quote? As far as I know, there is two list in the buffer cache, one is write list and the other is LRU list?


Regards



Tom Kyte
January 15, 2014 - 8:29 pm UTC

DBAs (data block addresses) are just that - data block addresses. They are not something "kept in a list", they have a definition.


A database block is managed in a set of lists in the SGA. This list is managed using a touch count algorithm. It is not a true "LRU" list. HOWEVER, that said, a touch count process is very similar to a LRU process - so from a conceptual perspective - thinking of the buffer cache being managed as an LRU is convenient.

technically, it is not a LRU list, it is a list of blocks where the blocks are inserted in the mid-point and move out to the ends based on a touch count. However, when just talking about the buffer cache - it is very convenient to think in terms of an LRU from a concepts perspective, and it is more than sufficient for our understanding of how things work.


You are mincing terms. LRU is an "algorithm". touch count is an "algorithm". they are just processes, methods, ways, implementations to manage a cache:

http://en.wikipedia.org/wiki/Cache_algorithms

... Could you please elaborate above quote? As far as I know, there is two list in
the buffer cache, one is write list and the other is LRU list? ...

there are lists of lists of lists of lists

there is a list of totally empty buffers
there is a dirty list of buffers
there is a list of the buffers in the cache
there are lists of blocks to be cleaned out on commit
there are lists of ......


a database block may be on more than one list. a list is just a list. There is way more than one list in the buffer cache.

Helena Marková, January 28, 2014 - 8:29 am UTC


more

Connor and Chris don't just spend all day on AskTOM. You can also catch regular content via Connor's blog and Chris's blog. Or if video is more your thing, check out Connor's latest video and Chris's latest video from their Youtube channels. And of course, keep up to date with AskTOM via the official twitter account.

More to Explore

Analytics

Analytic SQL got you confused? Check out Connor McDonald's complete video course.