Chapter five

The fifth chapter is an important chapter in this book , There are three sections . It is some advanced component problems behind the storage structure , Including buffer management 、 Lock management and recovery . In order to understand database transactions more conveniently .

Buffer management

Page caching

For a two-tier storage system , The access speed of disk is slow , So in order to reduce access to disk , Pages are cached in memory .
When the data on the disk has not been modified , You can reuse cached pages in memory , Called virtual disk . But when the memory copy is full , Will access the disk , The above is called page caching .
When the storage engine requests pages , First, check whether there is a cached version in memory , If so, visit directly , If not, go to the disk , Convert logical address and page number to physical address , Load into memory , Then give the cached version of the storage engine .
Dirty page ： The dirty flag bit on the page indicates that the content is out of sync with the disk , You must brush to disk to ensure persistence .

Recycling

It is better to keep the page cache full .
Persistence maintenance ： You need to pre write the log （WAL） And page caching . Because if the database crashes, the unwritten data will be lost , So set the log , The log records are discarded only after the brush is completed .

Prewrite log 、 Page caching （ Cache page swiping completed ）-> Log records are discarded -> Dirty page swap out cache

Lock page

according to b The data structure of the tree , It can be understood that he is “ Short and fat ” The shape of the , It can be considered that high-level nodes will hit in most reads . At the same time, it is often hit in the split and merge operation . So for these pages with high frequency, you can “ Fix ”.

Page replacement strategy ： Same as os Replacement strategy in .

FIFO： Attention will produce belady abnormal .
LRU： Not used for the longest time , If you maintain one queue at a time , When changing a page , It is expensive to re reference and link nodes .
CLOCK/CLOCK-sweep：（ Clock page replacement algorithm ）
LFU： Minimum frequency algorithm .tinyLFU Is a frequency based page replacement strategy , It's not an element that you choose to swap out , The selected elements to be retained form a protection queue , Elements with relatively high access frequency are kept in the queue for a long time . A frequency histogram is used to maintain a compact cache access history .
There are three queues in this strategy ：
Enter the queue ---- Investigation queue ---- Protection queue

recovery

Through the pre write log, which is an additional auxiliary disk data structure , Ensure that the database system has persistence semantics .
WAL Save separate operation records , And save the record of transaction completion .
In order to ensure the normal operation of the system during rollback or recovery , The compensation log record will be recorded and stored in the log when the operation is undone .

checkpoint

Checkpoints are used to mark that previous logging is no longer needed , Reduced workload . The process of forcing all dirty pages to be written to disk is called synchronization checkpoint .
Because it's unrealistic to brush it all , So most databases choose fuzzy checkpoints .
Log header with last——checkpoint The pointer records the last successful checkpoint information . Fuzzy checkpoints start from begin-checkpoint Record start to end-checkpoint end .

steal and force Strategy （ I don't quite understand , Look back ）

To determine when to brush memory changes to disk , Defined strategies .
steal The policy is to allow the page modified by the transaction to be written before the transaction is committed .
no-sreal The policy does not allow uncommitted transaction content to be written to disk .
force The policy requires that all the pages modified by the transaction be written to disk before the transaction is committed .
no-force Policy even if the page modified by the transaction has not been written to disk , You can also submit .
Now? DBMS What is commonly used is steal/no-force Strategy , Therefore, it is generally necessary to record redo log and undo log. This allows faster runtime performance , The price is in database recovery （recovery） You need to do a lot of things when you're in trouble , It increases the time of system restart .
The recovery process of restarting after database crash is divided into three stages ：

analysis phase ： Identify dirty pages in the page cache and transactions that occur when they crash .
Redo phase ： Replay the history until the crash point .
The cancellation phase ： Rollback all outstanding transactions , Restore to consistent state . Prevent another crash , The undo transaction operation will also be recorded in the log .

concurrency control

This chapter studies the local concurrency control technology .
Optimistic concurrency control ：
Allow multiple transactions to read and write concurrently , Transactions do not block each other , Instead, keep records , And check whether these history records conflict before submitting , If there is a conflict, terminate a conflict transaction .

Multi version concurrency control mvcc：
Allow multiple timestamp versions of a piece of data at the same time , In this way, transactions read a consistent view of a certain time in the past . Subsequent operations are carried out for one version of data （ The translation here is very confusing ）.

Pessimistic Concurrency ：
The locked version will require the maintenance of locks on database records . The implementation without locking is scheduled according to incomplete transactions , Maintain a list of read and write operations .

abnormal

Read and write exceptions will occur during concurrent transaction execution ： Dirty reading 、 It can't be read repeatedly 、 Fantasy reading ; Dirty write 、 Lost update 、 Write slant .

Dirty reading ： Uncommitted data read , For example, rollback after updating the previous transaction , Later transactions read uncommitted data .
Don't reread ： The same transaction is executed twice , The data read is inconsistent ,t1 Read a line ,t2 Revise and submit ,t1 Read the data again and change .
Fantasy reading ： It means that the row sets obtained by two range reads are different .

Lost update ： Two transactions update a value at the same time , Jidu commit, Then the submitted later overwrites the submitted earlier .
Dirty write ： It is modified in case of dirty reading .
Write slant ： A single transaction satisfies some constraints , Combining transactions violates .

Several methods to deal with database deadlock ：

1. Introduce a timeout mechanism and terminate long-running transactions .

2. conservative 2PL（ Two stage lock ）.

Databases often use wait charts （waits-for graph Realization ） To detect or avoid deadlocks ：