This is the 31st day of my participation in the August Text Challenge.More challenges in August
Mysql: Internal structure of buffer pools
preface
In this section, we introduce the internal structure of the buffer pool. If you’re not sure what a buffer pool is, check out the first article in the series. Buffer pool is the most simple database disk files in memory mapping, is a very important core component, buffer pool content and details or quite a lot, this part of the content of the personal will limit the length of readers better digest.
Buffer pool introduction: Mysql column – Mysql, InnoDB storage engine, Binlog workflow # buffer pool
An overview of the
-
The internal structure of a Buffer pool
- Data page and cache page relationship
- What is the description of the data page?
- How does Mysql know which data pages are loaded
-
Dirty pages
- The pseudo-code implementation of dirty pages and the introduction of dirty pages
-
Focus on
-
Distinguish between free list and Flush list
Be familiar with the structure diagram of the entire buffer pool.
-
Buffer pool structure
The complete structure of the buffer pool is as follows. This paper will break down the contents of each block one by one:
Buffer pool status in mysql
A Buffer pool can be viewed as a component of a memory structure, which can be understood as a large area of memory, which is 128MB by default. It is important to note that the default value is small and is often not enough.
From the structure of the buffer pool is the very core of a component, because mysql data could not have finished on the disk operation, even faster than memory, no possibility to SSD buffer pool can be seen as a data manipulation one-to-one mapping of data disk files, but if we operate the memory will be another problem, the operation of the memory is very fast, However, the disk refresh speed is not as fast as the memory, so there will be a problem of data inconsistency between the memory and the disk, because of some operations after the update of the content of the updated data pages in mysql are collectively called dirty pages.
So the redo log, undo log, and bin log files can be considered as part of a strategy to ensure proper data synchronization.
Data pages and cache pages
Since the buffer pool is a memory space, is the data in the buffer pool? How is our data placed in the buffer pool?
Here we review the logical structure of the database, the database is divided into table + field + row mode, a table has many rows of data, so the content of the data page is multiple rows? In fact, the database abstractions a concept called a data page, multiple rows of data will be put into a data page, there are multiple pages on disk, each page has many rows of data merged together, and finally we update the data to find a certain row of a certain page.
The default size of the data page is 16KB, and the size of the cache page is also 16KB.
Summary: A buffer pool stores data pages, also known as cache pages. Since a buffer pool is similar to memory, data on hard disks will be cached in this “memory” one by one. The size of a cache page in the Buffer pool and a data page in the disk are both 16KB.
Description of the cache page
Although we know the size of the cached page and the rows of data stored in the cached page, the cached page itself does not know this information. In this case, mysql introduces another data block called the cached page description, which contains the following contents:
- Owning tablespace
- Data page Number
- The owning address of the cache page in the buffer pool
How big is the description? A description is about 5% of the size of the cache page, probably about 800 bytes, with a default buffer pool of 128 MB. Note that in order to prevent the description from overflowing the buffer pool, mysql provides some extra memory for the description to ensure that the description can record all the data pages (cached pages). So 128 megabytes is not completely fixed, there will be a few extra megabytes of cached page descriptions.
How to store description information?
Description and cache pages in accordance with the “symmetry” like structure for storage, describe the information on the front of the cached page, cache pages were placed in the back buffer pool, as for the reason of this design on the one hand, as far as possible let description information not interfere with the distribution of the data page, on the other hand is to let the buffer pool have “extra” and enough space to hold the description information.
How to minimize memory fragmentation in the buffer pool?
When the cache page and description are divided into blocks, there must be a small amount of space that can neither allocate the description nor put down the contents of the cache block, so this part of the content cannot be used.
How to reduce it?
When dividing cache pages, arrange them closely in order to minimize waste, which is actually sequential allocation of memory.
How do I know which cached pages are free?
So how does mysql know that a cached page is free? In the Buffer pool, there is a two-way linked list called the Free List. Each node in the linked list is the corresponding description data block of the data page. That is, if a data page is free, it will be placed in the free list, and the free list will hold all the description blocks when the database is started. In addition, if you are familiar with the structure of a linked list, you will know that there is a base node (actually the head pointer of the list, but with much more content) to store the start and end nodes and so on.
As for the update operation of this basic node, the people familiar with the linked list must be very clear at this time, in fact, is the insert operation and delete operation of the bidirectional linked list.
To get a better idea of what’s going on in the above section, let’s use a diagram to cover all of the above:
How much memory does freelist take up?
Is the data content in the Buffer pool and freelist exactly the same copy? ** is so wrong! ** Because the description is concatenated in a freelist according to the List’s node rules, and because the node only needs to find the Free cache block (all nodes in the Free List point to a cached page that has never been used, meaning each node has a one-to-one pointer to the Free cache page).
Free list According to the definition rules of linked lists, each description has two Pointers, one is free_pre (front node) and the other is free_NEXT (successor node). The basic node itself takes up 40 bytes, storing the addresses of the first and last nodes, as well as how many nodes are currently in the free list, and other information.
How to read a disk page into a buffer pool cache page?
How do I read pages from a disk into a buffer pool? Once we have the free list, we can get a block of description data from the free list. Then we can read the corresponding data page from the free list into the buffer pool. Finally, we can remove the nodes from the free list.
How do I remove a node?
In fact, you can find the node through the head and tail Pointers in the base node of the bidirectional list and set the reference of the front node or the back node to NULL. The familiar operation of deleting a bidirectional linked list.
How do you know if the data is really coming in?
Mysql knows which data page is loaded into the buffer pool. The usual procedure is to check whether the buffer pool has data when the request comes in. If there is no cached page, you need to go to the free list to find the description of the data page. The data page is then loaded into the buffer pool via the disk file and the free List description node is deleted.
What is the structure of the data page cache hash table?
If the data page is cached, how does the buffer pool know the request is for it? In fact, Mysql also has a hash table structure, which can be regarded as a Map, key stores the table space + data page. Value is the address of the cached page. When the request executor calls the interface, it will find the corresponding cache page based on the hash table. If there is no cache page, it will go to the freelist and find the data page to load.
Dirty pages
What is a dirty page?
When the buffer pool data is updated, but the disk data is inconsistent with the contents of the cached page, the page is said to be a “dirty” page.
How does mysql know which pages are dirty
So mysql uses the free List list for validation? This can’t be done because the linked list is a repository of data pages that aren’t loaded and doesn’t know which cached pages are dirty. So mysql introduced a linked list called Flush List, which is a two-way linked list similar to the free list structure, and also has a base node that maintains the information for the entire list. Unlike the Free List, however, it stores dirty page descriptions instead of all data page descriptions. (Also, there is a pointer to the corresponding cache page in each node)
Tip: If you remember that the first article in this series briefly mentioned how IO threads periodically flush cached pages to disk files, how do you find dirty pages? It’s actually done through this bidirectional list, but the refresh action is random. This issue will be addressed again in a future article.
The flush List structure is shown at the end of this article.
Flushlist and Freelist pseudocodes
The following two diagrams are used to analyze the pseudo-code structure diagram of the two linked lists. The specific explanation is put in the code comments, so there is no more verbose here:
Here’s what happens after the second node is introduced:
Consider:
Logical structure and physical structure
We use tables and rows in SQL statements, but what is the relationship between table Spaces and data pages?
Tables and rows are logical storage structures.
But data pages, table Spaces, are physical storage structures. Table space consists of data files (data blocks). Data files store rows and rows of data. Therefore, the entire mysql disk file can be abstractly interpreted as consisting of data blocks.
The difference between physical structure and logical structure is their essential difference.
Summary:
Mysql has two linked lists and one hash table, and there will be more linked lists in the future to maintain information. These are very confusing, so I will review the structure of the above mentioned to help readers review:
Write in the last
The content of the buffer pool looks complicated, but it is almost the same according to the structure diagram. The difficulty of the content of this article will not be too difficult, but the difficulty will gradually increase with the details of the buffer pool. In the end, please point out any mistakes in the content arrangement.