The principle of Mysql storage engine

How is Mysql data organized?
Of course it is page, which means that mysql exchanges internal and external memory in units of pages.

1. MySQL record storage (page unit)

Insert picture description here

Page header
Records the control information of the page, which occupies a total of 56 bytes, including the page pointers of the left and right brothers of the page , and the usage of the page space.

Virtual record
Largest virtual record: larger than the largest primary key in the page.
Smallest virtual record: smaller than the smallest primary key on the page.
(Function: For example, if we want to check whether a record is on this page, we must see whether the record is in the largest or smallest virtual record. Within the record range)

Record heap
Row record storage area, divided into valid records and deleted records

Free space linked list A linked list
composed of deleted records
(reuse space)

Unallocated space The
unused storage space of the page;

Slot area

Page Footer The
last part of the page, which occupies 8 bytes, mainly stores the verification information of the page;

In-page record maintenance

Clustered index

1. Order guarantee

  1. Physically ordered (conducive to query, not conducive to insertion and deletion)
Insert picture description here

2. Logically ordered (high insert and delete performance, low query efficiency). By default,

Insert picture description here

mysql organizes data in an orderly manner as shown in the figure below.

Insert picture description here

2. Insertion strategy

  1. Free space linked list (Priority to use free space linked list)
  2. Unused space
Insert picture description here

3. In-page query


Binary search (the data is not the same size, you cannot use the binary search)

Insert picture description here

Use the slot to do dichotomy to achieve an approximate dichotomy search, which is similar to a jump table

Two, MySQL InnoDB storage engine memory management

Pre-allocated memory space

  1. Memory pool

Data is loaded in units of pages (reduce the number of io visits)

Memory page management

  1. Page mapping (record which disk data is loaded on which memory)
  2. Page data management

Data storage and exchange

Data elimination

  1. Out of memory pages
  2. Need to load new data
Insert picture description here

Page management
Free pages
Data pages
Dirty pages (flush back to disk)

Page elimination
LRU (eliminate cold data)

Insert picture description here

State at a certain moment -> visit P2 -> visit new page P7

The impact of full table scan on memory?
May eliminate hot data in memory (for example, perform a full table scan on a table that has almost no access)

So mysql is not simply using the LRU algorithm

Solve the problem: How to avoid the elimination of hot data?

access time + frequency (redis)
two LRU tables

Mysql solution

Insert picture description here

MySQL memory management-LRU

Insert picture description here

Page loading

Disk data to memory

Insert picture description here
Insert picture description here

What if there is no free page?
Take from the Free list> Eliminate from LRU> LRU Flush

Page eliminated
LRU tail eliminated
Flush LRU eliminated

Will the first dirty page in the LRU linked list be flushed and "released"
to the end of the LRU? Put FreeList directly?

The position moves from
old to new
new to old.

Insert picture description here

Thinking: What is the timing of the move?
old zone survival time, greater than this value, there is a chance to enter the new zone

Insert picture description here

The operation of LRU_new
Linked list operation is very efficient, has access moved to the head of the table?
Lock! ! !
MySQL design ideas: reduce the number of moves

Two important references:
1. freed_page_clock: Buffer Pool eliminated pages
2. LRU_new length 1/4

Current freed_page_clock-freed_page_clock>LRU_new length 1/4 when moved to Header last time

Three, MySQL transaction implementation principle

Basic concepts of MySQL transaction

1. Transaction characteristics
A (Atomicity atomicity): All success or all failures
I (Isolation isolation): Parallel transactions do not interfere with each other
D (Durability durability): After the transaction is submitted, it will take effect permanently
C (Consistency consistency): Guaranteed by AID

2. Concurrency problems.
Dirty Read: Uncommitted data
is read. Non-repeatable read: Two read results are different.
Phantom Read: Data represented by the result of the select operation Status cannot support subsequent business operations

3. Isolation level
Read Uncommitted: The lowest isolation level, uncommitted data of other transactions will be read. Dirty read;
Read Committed (committed read): The data submitted by other transactions can be read during the transaction. Non-repeatable read;
Repeatable Read: read the same result set every time, regardless of whether other transactions are submitted or not, phantom read; (two current reads will not produce phantom read)
Serializable: transaction is queued, The highest isolation level and the worst performance;

MySQL transaction implementation principle (transaction management mechanism)

1. MVCC multi-version concurrency control to
resolve read-write conflicts
How to work: hide columns

-Current read (read the data stored in the storage engine)

Insert picture description here

under the RR level

Insert picture description here

2. undo log

Rollback log to
ensure transaction atomicity.
Implement multiple versions of data.
Delete undo log: used to roll back and clean up after submission;
update undo log: used to roll back and read snapshots at the same time, and cannot be deleted casually

Insert picture description here

Thinking: How to clean up undolog?
According to the minimum active transaction ID Read view is active in the system,
why is InnoDB count(*) so slow?

3. Redo log

l Realize transaction persistence

Insert picture description here

Write process
l The modification of the record page, the state is prepare
l The transaction is submitted, and the transaction record is in the commit state

Insert picture description here
Insert picture description here

is small, the modification of the record page is lower than the cost of writing the page, the
end is appended, random writing is changed in order, and the changed page is not fixed

Four, MySQL lock implementation principle

Insert picture description here

All current reads plus exclusive locks, which ones are current reads?

Insert picture description here

Insert picture description here

Unique index/ non-unique index * RC/RR
4 cases are analyzed one by one

Insert picture description here

There will be a phantom reading problem, and it can’t be read repeatedly.

Insert picture description here

Insert picture description here

Insert picture description here

Insert picture description here

Insert picture description here

Insert picture description here

The deadlock is recorded in the library table and can be deleted by kill the lock