The use of LRU algorithm in MySQL and Redis

LRU is also known as the least recently unused algorithm. As the most commonly used memory elimination algorithm, LRU can be seen in the mainstream system, and is also used in MySQL and Redis. It can be said that they are used to manage storage space, timely eliminate and update data, and improve the utilization rate of storage space.

Redis memory flushing mechanism

Conf has a line of arguments to configure the memory flushing policy

maxmemory-policy volatile-LRU
Copy the code

Volatile -LRU: disables volatile- TTL by selecting the least recently used data from a set with an expiration time (server.db[I].expires) : Nullify volatile-random: Nullify allKees-lru from a set that has expired (server.db[I].expires) : Select the least recently used data from the dataset (server.db[I].dict) and discard allkeys-random: select the least recently used data from the dataset (server.db[I].dict) As you can see, if volatile-LRU is used, the LRU data structure will be used to clean up the data in memory.

Redis LRU concrete implementation:

The traditional LRU is to use the stack form, each time the latest use of the stack to the top of the stack, but using the stack form will cause a large number of non-hot data in the select * header data, so it needs to be improved. Each time Redis fetches a value by key, it updates the LRU field in the value to the current second-level timestamp. The initial implementation algorithm of Redis is very simple. Five keys are randomly extracted from the dict and the smallest LRU field is eliminated. In 3.0, another version of the algorithm was improved. Firstly, all the randomly selected keys were put into a pool (the size of the pool is 16), and the keys in the pool were sorted according to the LRU size. Each subsequent randomly selected keyLRU value must be less than the smallest LRU in the pool before the pool is full. After the pool is full, remove the largest LRU key from the pool every time a new key needs to be added. To flush, select a minimum LRU value from the pool and flush it out.

MySQL InnoDB engine on LRU usage scenarios

A buffer pool is a large area of memory that holds various types of pages. Buffer pools in databases are managed by the LRU algorithm. Because pages in the Buffer pool may also be allocated to adaptive hash indexes, Lock information, Insert buffers, and so on, this page does not need to be maintained by the LRU algorithm and therefore does not exist in the LRU list.

LRU stored procedures

The LRU list is used to manage pages that have been read, but when the database is started, the LRU list is empty, that is, there are no pages. The pages are stored in the Free list. When paging from the buffer pool is required, the Free list is first checked to see if there are any Free pages available. If there are, the page is removed from the Free list and placed in the LRU list. Otherwise, according to the LRU algorithm, the page at the end of the LRU list is eliminated and the memory space is allocated to the new page.

The most frequently used pages are at the front of the LRU list and the least used pages are at the bottom of the LRU list. When the buffer pool cannot hold newly read pages, the pages at the end of the LRU list are first released. In the InnoDB storage engine, the default size of pages in the buffer pool is 16KB, and the buffer pool is also managed using the LRU algorithm. A slight difference is that the InnoDB storage engine has made some improvements to the traditional LRU algorithm. In the InnoDB storage engine, the LRU list also includes midpoint locations. The newly read page, although the most recently accessed page, is not placed directly at the head of the LRU list, but at the MIDpoint location of the LRU list. This algorithm is called midpoint Insertion Strategy in InnoDB storage engine. In the default configuration, this location is 58 in the length of the LRU list. Midpoint 1 position can be controlled by innodb old Blocks PCT:.

Why not use the naive LRU algorithm and put the read pages directly at the head of the LRU list? This is because if you put the read pages directly at the head of the LRU, some SQL operations may flush the pages out of the buffer pool, affecting the efficiency of the buffer pool. A common such operation is an index or data scan operation. This type of operation requires access to many, or even all, pages of the table, and these pages are usually only needed for this query operation, not active hot data. If the page is placed at the head of the LRU list, it is very likely that the desired hot data page will be removed from the LRU list and the InnoDB storage engine will need to access the disk again the next time it needs to read the page.