Shulou(Shulou.com)05/31 Report--

How to understand the LRU chain, dirty block and dirty LRU chain in the LRU algorithm of Oracle database? I believe that many inexperienced people don't know what to do about it. Therefore, this paper summarizes the causes and solutions of the problem. Through this article, I hope you can solve this problem.

Overview

The basic concept of the so-called LRU (Least recently used) algorithm is that when there is not enough free space in memory, the buffer retains the most commonly used data as much as possible, in other words, it first clears the "less frequently used data" and frees its space. The reason for using quotation marks for less frequently used data is that the so-called less frequently used criteria are artificial and lax. The meaning of the so-called MRU (Most recently used) algorithm is exactly the opposite of the LRU algorithm.

Oracle uses this algorithm in the working mechanism of high-speed buffer. Let's take a look at it.

LRU chain:

The size of any cache is limited and is not as large as the amount of data being cached. Just as Buffer cache is used to cache data files, data files are much larger than Buffer cache.

As a result, the cache is always full. When there are no free memory blocks in the cache, if the new data is required to enter the cache, we have to select a victim from the original data in the cache and overwrite the victim with the new data entering the cache. The choice of this victim is very important. Caching is so that data can be reused, so you should usually pick the blocks in the cache that are least likely to be reused as victims. The choice of victims, from CPU's L1 and L2 caches to shared pools and Buffer cache pools, the vast majority of cache pools use the famous LRU algorithm, but in Oracle, Oracle uses the improved LRU algorithm. The specific algorithm has not been announced, but the general purpose of the LRU algorithm is "the least recent", which means that the last accessed block of memory is the farthest from now as a victim.

For example, there are now three blocks of memory, A, B, and CMagi A, which have been accessed 10 times, the last visit is 15 times at 10 purge 20 line B, the last time is 10 times 10 times for 10 gazetteers, and the last visit is at 10:22. When the victim needs to be selected, B visits the most times, and the victim is definitely not it. An and C visited the same number of times, but A was visited at 10:20, C was visited at 10:22, A was last visited earlier, and the victim was A.

In order to realize the function of LRU, Oracle creates a LRU linked list in Buffer cache. Oracle sorts all memory blocks in Buffer cache in the linked list according to access times and access time. The two ends of the linked list are called the hot end and the cold end respectively, as shown in the following figure:

When you access a block for the first time, if the block is not in Buffer cache, Oracle chooses to read it into Buffer cache. When selecting a victim in Buffer cache, Oracle will start with the cold end, and in the example in the figure above, memory block U will be the victim.

As shown above, the new block will be read into U, overwriting the original contents of U. Here, we assume that the new block is V. But block V will not be placed at the cold end, because the block at the cold end will soon be covered as a victim. This is not in line with the purpose of "taking the block with the farthest time of the last visit as the victim". Block V is the last time closest to the current moment, and it should not be the next victim. Let's continue to see how Oracle experimented with LRU.

Oracle divides the LRU chain into two halves, half recording the hot end block and half recording the cold end block. As shown in the figure above, and the block V that has just been accessed is shown in the following figure:

If a new block enters the Buffer cache, for example, block X is read into Buffer cache, it will overwrite T and be moved to the front of block V, as shown below:

If you continue in this way, the block at the cold end on the right must be the farthest from the last visit. So, blocks with more visits will not be chosen as victims. How does Oracle achieve this? This is very simple, Oracle is generally subject to 2 times, the block has been accessed more than 2 times, it will have a chance to enter the hot end.

Oracle adds a flag bit for each block in memory to record the number of accesses, assuming that the number of accesses for each block in the figure is as follows:

If there is a new block to be read into the Buffer cache,Oracle and starts looking for a victim from the cold end, the first block S at the cold end, whose number of visits is 2, then it cannot be overwritten. As long as the number of visits is greater than or equal to 2, Oracle will think that it may be accessed frequently, and if Oracle wants to move it to the hot end, it will choose R as the victim this time:

Block S will be moved from the cold end to the hot end, and its visits will be cleared zero. At this point, block R is the victim because it has been visited less than twice.

The new block Y covers block R and is moved to the beginning of the cold end block, which has a visit number of 1. If block Y is accessed again, its number of visits becomes 2:

Although Y has been visited twice, it will not be moved to the hot end immediately, it will remain in its original position, and it will continue to be pushed backward as new blocks are added and inserted in front of it.

As in the picture above, a lot of new blocks have been added, and Y has been pushed to the cold end. When a new block enters the Buffer cache, Y will not be the victim, it will be moved to the front of the hot end S, and Z behind Y, whose number of visits will not reach 2, will be the victim.

This is how Buffer cache manages LRU in Oracle. Operating in this way, Oracle can keep commonly used blocks in the Buffer cache as long as possible. Moreover, every time a new block enters the Buffer cache,Oracle, the victim block is searched from the cold end from right to left. Because the closer to the cold end, the less the number of visits to the block, and the last access time is farthest from now.

Dirty blocks and dirty LRU chains:

The rule for modifying blocks in Oracle is to modify only the blocks in Buffer cache, not directly to the blocks on disk. If the block to be modified is not in Buffer cache, Oracle reads it into Buffer cache and then modifies it in Buffer cache.

When a block in Buffer cache is modified, Oracle marks it as a "dirty" block. Dirty blocks contain dirty data, and dirty data is the data modified by the user. Oracle writes dirty blocks to disk on a regular basis. There is a special background process that is responsible for writing dirty blocks to disk, which is DBWn. We also call the process of writing DBWn dirty blocks to disk called refreshing dirty blocks. after refreshing, the dirty blocks are not dirty and become clean again. In fact, there is a block A, and if the data in this block in Buffer cache is inconsistent with that in the block on disk, then this block is a dirty block. Otherwise, it's a clean piece. When the modification is complete, because Oracle only modifies the Buffer cache, the data in the block must be inconsistent with the disk, and the block is a dirty block. When the block is refreshed and the block is written to disk, the data of the block in the disk is the same as that in the Buffer cache, and the block becomes a clean block again.

A dirty block cannot be overwritten before it is written back to disk, that is, when it is still dirty, because the dirty block contains user-modified data that has not yet been written to disk. If the dirty block is overwritten at this time, the user's modification will be lost.

Let the current LRU chain look like the figure above, where V, L, O, P, Q are dirty blocks. When the new block is about to enter the Buffer cache, Oracle selects the sacrificial block from the cold end. Q, P and O cannot be used as the sacrificial block, because they are dirty blocks, N is the victim this time, and the new block will cover N and then insert the new block in front of Y. Then, the next time a block enters the Buffer cache, Oracle starts searching from the cold end, checks one side of Q, P, and O, finds that none of them can be covered, and then defines M as the victim. Wait, wait, When the block becomes dirty, the block is not immediately moved to the dirty LRU. Only when the Oracle starts from the cold end, looking for a victim, will the found dirty block be moved into the dirty LRU chain. The purpose of this is that the next time you look for a victim, you don't have to check these dirty lumps.

From the principle of LRU chain and dirty LRU chain, we can find that Oracle leaves a lot of work to search for victims at the cold end of LRU. When the number of visits to the block increases by more than 2, the position of the block in the LUR chain remains unchanged; when the block becomes dirty, the position of the LRU chain of the block remains the same. Only when searching for victims from the cold end of LRU, the dirty blocks found will be moved to the dirty LRU chain, and those with more than 2 visits will be inserted into the hot end, which is Oracle's improved LRU algorithm.

When there are too many blocks with more than 2 visits, or too many dirty blocks, these blocks cannot be covered anyway, and Oracle has to move them to where they should go. When such blocks are encountered more than 40% of the total number of blocks in LRU, that is, a small half of the LRU chain is searched, and no victims are found that can be covered, Oracle is no longer looking for them, and it will wake up DBWn to refresh dirty blocks. Waits during a DBWn refresh are recorded in the free buffer waits event.

When a dirty block is found in the process of finding the victim, Oracle moves it to the dirty LRU chain, but the number of dirty blocks in the dirty LRU chain reaches the limit, DBWn is awakened and begins to refresh the dirty block. Oracle must wait for the refresh of the dirty block before continuing to look for the victim. The waiting event will also be recorded in the free buffer inspected.

In a word, the main reason for the occurrence of free buffer waits events is that it takes too long to find victims in LRU. If this wait event occurs frequently, there are too many dirty blocks in Buffer cache, which is usually due to the slow refresh speed of DBWn writes.

After reading the above, have you mastered how to understand the LRU chain, dirty block and dirty LRU chain in the LRU algorithm of Oracle database? If you want to learn more skills or want to know more about it, you are welcome to follow the industry information channel, thank you for reading!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.