MySQL InnoDB快取
1. 背景
對於各種用戶數據、索引數據等各種數據都是需要持久化存儲到磁碟，然後以「頁」為單位進行讀寫。
相對於直接讀寫快取，磁碟IO的成本相當高昂。
對於讀取的頁面數據，並不是使用完就釋放掉，而是放到緩衝區，因為下一次操作有可能還需要讀區該頁面。
對於修改過的頁面數據，也不是馬上同步到磁碟，也是放到緩衝區，因為下一次有可能還會修改該頁面的數據。
但是快取的空間是有大小限制的，不可能無限擴充。
對於緩衝區的數據，需要有合理的頁面淘汰演算法，將未來使用概率較小的頁面釋放或者同步到磁碟，
給當下需要存放到快取的頁面騰出位置。
2. 存儲器性能差異
暫存器：CPU暫存指令、數據的小型存儲區域，速度快，容量小。
CPU高速快取(CPU Cache)：用於減少CPU訪問記憶體所需平均時間的部件。
記憶體：用於暫時存放CPU中的運算數據，以及與硬碟等外部存儲器交換的數據。
硬碟：分為固態硬碟(SSD)和機械硬碟(HHD)，是非易失性存儲器。
下圖是各種快取器的價格和性能差距，
從下圖可以看出，SSD的隨機訪問延時在微妙級別，而記憶體的的隨機訪問延時在納秒級別，記憶體比SSD大概快1000倍左右。
圖片來自 小林Coding
3. Buffer Pool
一個緩衝池(緩衝池)是向作業系統申請的一塊記憶體空間，這塊記憶體空間由多個chunk組成，每個chunk均包含多個控制塊和對應的緩衝頁。
chunk是向作業系統申請記憶體的最小單位，緩衝頁大小與InnoDB表空間使用的頁面大小一致。
Buffer Pool的示意圖如下
每一個控制塊都對應一個緩衝頁，控制塊包含該緩衝頁所屬的表空間編號、頁號、在Buffer Pool中的地址、鏈表結點資訊等等。
當剛讀取一個頁面時，需要知道緩衝區有哪些空閑頁面，當修改過後緩衝頁後，需要記錄該緩衝頁需要持久化到磁碟，
當緩衝區沒有空閑頁面了，需要有頁面淘汰演算法來將緩衝頁移出緩衝區，
以上涉及到Free鏈表、Flush鏈表、LRU鏈表，下面注意說明。
4. Free鏈表
Free鏈表是由空閑的緩衝頁對應的控制塊組成的鏈表，通過Free鏈表就獲取到空閑的緩衝頁及其在緩衝區中的地址。
每當需要從磁碟載入一個頁面到緩衝區時，從該Free鏈表取出一個控制塊結點，從Free鏈表移除該結點，並加入LRU鏈表。
如果這個緩衝區頁面被修改過，那麼會被加入到Flush鏈表中。
5. Flush鏈表
如果一修改緩衝頁的數據之後就刷新到磁碟，這種頻繁的IO操作勢必影響程式等整體性能。
試想一下，先後修改1000次同一緩衝區頁面的一位元組數據，每次修改都刷新到磁碟，與修改1000次後再將最終結果刷新磁碟，節省了999次刷新磁碟的操作。
因此，當頁面的數據被修改之後，需要將改頁面放到Flush鏈表，排隊等候寫入磁碟。
這既可以減少在用戶進程中刷新磁碟的次數，也從整體上減少了磁碟IO到次數。
6. LRU鏈表
記憶體空間有限，不可能將所有數據都快取在記憶體當中，因此需要有一定的演算法將記憶體中頁面淘汰掉(修改過的頁面持久化到磁碟)。
LRU(Least Recently Used)鏈表主要用於輔助實現記憶體頁面淘汰，故名思義，最先淘汰的是最近最少使用的緩衝頁。
LRU鏈表的結果如下圖所示
將LRU鏈表分為young區域和old區域。
對於初次載入到緩衝區的頁面，會放到LRU鏈表old區域的頭部，這主要避免了預讀的頁面被放到了LRU鏈表的首部。
當第二次訪問緩衝頁且時間間隔超過innodb_old_blocks_time(默認1s)時，才將該頁面移動到LRU鏈表的首部。
進一步，為了避免頻繁的移動鏈表結點，當某個緩衝頁已經在young區域的前3/4時，則不會移動該結點到首部。
7. 其它
如何定位頁面是否被緩衝呢？
表空間號和頁號可以唯一識別緩衝頁，因此InnoDB引擎建立了以表空間號+頁號為key，以緩衝頁控制塊地址為value的哈希表，
從而快速判斷頁面是否被緩衝，快速定位到數據所在地址。
