MySQL Interview

MySQL interview MVCC Cassandra MongoDB CAP

1. MySQL InnoDB 的資料寫入流程

MySQL InnoDB是MySQL數據庫的一種存儲引擎，用於處理事務和數據持久化。下面是MySQL InnoDB的簡要數據寫入流程：

客戶端發送寫入請求：應用程序或客戶端向MySQL數據庫發送寫入請求，例如INSERT、UPDATE或DELETE語句。
查詢解析和優化：MySQL服務器接收到寫入請求後，會進行查詢解析和優化。這個過程包括解析SQL語句、語法檢查、查詢優化器生成執行計劃等。
鎖定：MySQL會根據事務隔離級別和表的鎖機制，對相關的數據行或表進行鎖定，以確保數據的一致性和並發性。
Redo日誌寫入：在寫入數據之前，MySQL會將寫入操作記錄到InnoDB的重做日誌（Redo Log = Write-ahead Log）中。重做日誌是用於持久化事務的關鍵組件，它記錄了所有已提交事務的變更操作。
內存緩存：數據修改操作還會被寫入InnoDB的緩衝池（Buffer Pool），這是InnoDB用於管理數據頁（Page）的內存區域。數據頁存儲了表的數據和索引。
並發控制：在數據修改過程中，InnoDB會使用各種並發控制技術來保證事務的隔離性和一致性，例如 MVCC（多版本並發控制）機制。
數據寫入磁盤：InnoDB週期性地將緩衝池中的數據頁寫入磁盤，以確保數據的持久性。這個過程稱為臟頁刷新（Flush）。
提交事務：當事務完成所有的寫入操作時，MySQL會將事務標記為已提交。此時，數據修改操作已經持久化到磁盤上的數據文件中。

上述是MySQL InnoDB的基本數據寫入流程。這個過程中涉及到事務管理、日誌記錄、並發控制和數據持久化等關鍵步驟，以確保數據的可靠性和一致性。

Multiversion Concurrency Control (MVCC)

MVCC(多版本並發控制)是一種數據庫並發控制的技術，用於提供高並發性和事務隔離性。它允許多個事務同時訪問數據庫的同一數據，而不會相互干擾或導致數據不一致。

MVCC的核心思想是通過在數據庫中創建多個數據版本來實現並發控制。當一個事務開始時，它會獲得數據的一個快照（Snapshot），該快照反映了事務開始時數據庫的狀態。而其他事務可以同時進行讀操作，讀取之前的版本或者已經提交的版本，這樣可以避免讀操作之間的衝突。

在MVCC中，每個數據行都會存儲多個版本，每個版本都有一個時間戳，表示該版本的創建時間。當一個事務更新某個數據行時，它會在數據庫中創建該數據行的一個新版本，並將該版本與事務的時間戳關聯起來。其他事務可以繼續讀取舊版本的數據，而不受到新版本的干擾。

當一個事務提交時，它的修改操作會變成可見的，並且會將其時間戳與事務的提交時間關聯起來。此時，其他事務可以看到這個已提交的版本。

MVCC通過使用快照和版本控制來實現高並發性和事務隔離性，避免了讀-寫衝突和寫-寫衝突。它使得數據庫可以同時支持多個並發事務，提高了數據庫的吞吐量和性能。

需要注意的是，MVCC並非適用於所有類型的數據庫和所有場景，它是一種常見的並發控制技術，用於支持高並發數據庫系統。不同的數據庫管理系統可能會有不同的實現方式和細節，但核心概念和原理基本相似。

2. 為什麼大部份的 RDBMS 會選擇 B+ Tree 作為其底層的資料結構？

高效的範圍查詢：B+樹是一種自平衡的樹結構，具有有序的葉子節點，並且葉子節點之間通過指針鏈接。這使得B+樹非常適合執行範圍查詢，例如在給定範圍內檢索數據。 B+樹的葉子節點形成了一個有序的鍊錶，可以輕鬆地遍歷整個範圍。
快速的查找和插入：B+樹的高度相對較小，通常可以保持較為平衡，因此查找和插入操作的時間複雜度為O(logN)，其中N是樹中的節點數量。這使得B+樹能夠高效地處理大量的數據，並提供快速的查找和插入操作。
適應性和可擴展性：B+樹可以根據數據的增長和縮小自動進行擴展和收縮，因為它具有自平衡的特性。這使得B+樹非常適應數據的動態變化，並且能夠在面對大量數據時保持高效。
支持順序訪問和範圍掃描：由於B+樹的葉子節點形成了一個有序鍊錶，所以它支持按順序訪問和範圍掃描操作。這對於需要按順序訪問大量數據的查詢非常重要，例如執行排序操作或分頁查詢。
有利於磁盤訪問模式：B+樹的節點大小通常與磁盤塊大小相當，這使得B+樹在磁盤上的訪問非常高效。相鄰節點的數據在物理上也更接近，減少了磁盤的隨機訪問。這對於處理大規模數據集並進行磁盤I/O操作的數據庫非常重要。

B+樹 : https://zh.wikipedia.org/zh-tw/B%2B%E6%A0%91

B+ 樹是一種樹數據結構，是一個n叉排序樹，每個節點通常有多個孩子，一棵B+樹包含根節點、內部節點和葉子節點。根節點可能是一個葉子節點，也可能是一個包含兩個或兩個以上孩子節點的節點。

（ ps:舉例說明3階B-樹指的是每個結點最多2個關鍵字，3個孩子)

B+樹是對B樹的一種變形樹，它與B樹的差異在於：

有k個子結點的結點必然有k個關鍵碼；
非葉結點僅具有索引作用，跟記錄有關的信息均存放在葉結點中。
樹的所有葉結點構成一個有序鍊錶，可以按照關鍵碼排序的次序遍歷全部記錄，便於區間查找和遍歷。
B+ 樹的優點在於：由於B+樹在內部節點上不包含數據信息，因此在內存頁中能夠存放更多的key。數據存放的更加緊密，具有更好的空間局部性。因此訪問葉子節點上關聯的數據也具有更好的緩存命中率。 B+樹的葉子結點都是相連的，因此對整棵樹的便利只需要一次線性遍歷葉子結點即可。而且由於數據順序排列並且相連，所以便於區間查找和搜索。而B樹則需要進行每一層的遞歸遍歷。相鄰的元素可能在內存中不相鄰，所以緩存命中性沒有B+樹好。但是B樹也有優點，其優點在於，由於B樹的每一個節點都包含key和value，因此經常訪問的元素可能離根節點更近，因此訪問也更迅速。下面是B 樹和B+樹的區別圖：

b+樹的應用場景:

B/B+樹是為了磁盤或其它存儲設備而設計的一種平衡多路查找樹(相對於二叉,B樹每個內節點有多個分支), 與紅黑樹(RBTree)相比,在相同的的節點的情況下, 一顆B/B+樹的高度遠遠小於紅黑樹的高度(在下面B/B+樹的性能分析中會提到). B/B+樹上操作的時間通常由存取磁盤的時間和CPU計算時間這兩部分構成,而CPU的速度非常快, 所以B樹的操作效率取決於訪問磁盤的次數,關鍵字總數相同的情況下B樹的高度越小，磁盤I/O所花的時間越少. 二叉查找樹的結構不適合數據庫，因為它的查找效率與層數相關。越處在下層的數據，就需要越多次比較。對於數據庫來說，每進入一層，就要從硬盤讀取一次數據，這非常致命，因為硬盤的讀取時間遠遠大於數據處理時間，數據庫讀取硬盤的次數越少越好。這種數據結構，非常有利於減少讀取硬盤的次數。假定一個節點可以容納100個值，那麼3層的B樹可以容納100萬個數據，如果換成二叉查找樹，則需要20層！假定操作系統一次讀取一個節點，並且根節點保留在內存中，那麼B樹在100萬個數據中查找目標值，只需要讀取兩次硬盤。

2.1 為什麼不使用 RBTree 或 AVLTree？

雖然RB樹（Red-Black Tree）和AVL樹是常見的自平衡二叉搜索樹，但在關係型數據庫管理系統中通常不作為底層數據結構的選擇。以下是一些原因：

圍查詢性能：RB樹和AVL樹在範圍查詢操作上性能較差。由於這些樹結構不具備有序葉子節點形成的鍊錶，範圍查詢可能需要更多的遍歷操作，導致性能下降。而B+樹的有序葉子節點鍊錶使得範圍查詢非常高效。
磁盤訪問模式：RB樹和AVL樹由於節點大小較小，可能導致更頻繁的磁盤I/O操作。相鄰節點的數據在物理上較遠，增加了磁盤的隨機訪問。 B+樹的節點大小通常與磁盤塊大小相當，這使得B+樹更適合磁盤訪問模式，能夠更有效地利用磁盤讀取和寫入操作。
順序訪問和範圍掃描：由於B+樹的葉子節點形成了有序鍊錶，它支持按順序訪問和範圍掃描操作。這對於需要按順序訪問大量數據的查詢非常重要，例如執行排序操作或分頁查詢。
數據庫操作需求：關係型數據庫通常需要支持複雜的數據庫操作，例如事務、並發控制、索引和查詢優化等。 B+樹作為一種常見的數據庫索引結構，能夠較好地滿足這些需求，並提供高效的數據訪問。

自平衡是指在樹結構中，通過對節點進行旋轉和重新調整，保持樹的平衡性。這可以確保樹的高度保持在較小的範圍內，從而保持樹的性能和效率。 RB樹和AVL樹都是自平衡樹，其中RB樹通過使用紅黑節點的顏色約束來保持平衡，而AVL樹通過維護每個節點的平衡因子（左子樹高度和右子樹高度之差）來保持平衡。

自平衡樹的主要目的是防止樹結構傾斜，從而保證樹的高度不會過高，使得查找、插入和刪除操作的時間複雜度保持在較低的水平，通常是O(logN)。通過自平衡操作，樹可以快速適應數據的動態變化，保持高效性能。

雖然RB樹和AVL樹在某些情況下具有優勢，但對於關係型數據庫管理系統來說，B+樹更適合處理範圍查詢、磁盤訪問和內存佔用等方面的要求。它在處理大量數據時表現更好，並且能夠提供高效的查詢和存儲操作。

RB樹和AVL樹在某些情況下具有優勢?

需要較快的插入和刪除操作：相對於B+樹來說，RB樹和AVL樹通常需要更少的旋轉和調整操作來維持平衡。這使得它們在需要頻繁插入和刪除操作的場景下具有優勢，例如在內存中維護的索引結構。
內存限制：由於RB樹和AVL樹需要較少的指針和額外信息來維持平衡，它們相對於B+樹來說佔用更少的內存空間。這使得它們在內存受限的環境下更具優勢，例如嵌入式設備或資源有限的系統。
需要更快的查找操作：由於RB樹和AVL樹的高度相對較小且保持平衡，查找操作的時間複雜度為O(logN)，其中N是樹中的節點數量。相對於B+樹而言，RB樹和AVL樹的查找操作可能更快一些。
不需要頻繁的範圍查詢：RB樹和AVL樹在範圍查詢操作上相對較慢，因為它們不具備有序葉子節點形成的鍊錶。如果應用程序需要大量的範圍查詢操作，那麼B+樹可能更適合，因為它在這方面表現更好。

2.2 B Tree 跟 B+ Tree 又有什麼差異呢？

數據存儲方式：在B樹中，每個節點既包含索引鍵值，又包含對應的數據值。而在B+樹中，只有葉子節點存儲了數據值，而非葉子節點僅包含索引鍵值和指向下一層節點的指針。這使得B+樹的內部節點可以存儲更多的鍵值對，提高了索引的利用率。
葉子節點的有序鍊錶：B+樹的葉子節點通過鍊錶連接成一個有序序列。這使得範圍查詢和順序訪問非常高效，因為只需要遍歷鍊錶即可。而B樹中的葉子節點沒有這種有序的關係。
範圍查詢性能：由於B+樹的有序鍊錶，範圍查詢的性能通常比B樹更好。在B+樹中，可以從起始節點開始順序遍歷，而不需要進行額外的查找操作。
磁盤訪問模式：B+樹更適合磁盤訪問模式。由於B+樹的非葉子節點不存儲數據值，它們的大小通常比B樹的節點小。這使得在磁盤上進行讀取和寫入操作時，B+樹能夠更好地利用磁盤塊，減少隨機訪問的需求。
聚簇索引支持：B+樹更適合支持聚簇索引。聚簇索引是將數據存儲在索引中的一種技術，可以提高特定查詢的性能。 B+樹的葉子節點存儲了完整的數據記錄，使得聚簇索引更容易實現。

2.3 近年來，LSM-Tree 相當盛行，能聊聊它與 B+ Tree 的差異嗎，以及你認為為什麼它會流行起來？

LSM-Tree（Log-Structured Merge Tree）和傳統的B+樹之間的差異時，以下是一些關鍵點：

寫入性能：LSM-Tree在寫入方面具有顯著的性能優勢。它採用了寫入時追加（write-append）的方式，將新數據追加到內存中的日誌結構（log structure），而不是直接更新原始數據。這樣可以減少磁盤的隨機寫入，並且對於寫入密集的工作負載表現更好。
讀取性能：B+樹在讀取方面通常比LSM-Tree更高效。由於B+樹的葉子節點形成有序鍊錶，支持範圍查詢和順序訪問，因此對於讀取密集的工作負載，B+樹通常更適合。而LSM-Tree可能需要在多個層級進行合併（merge）操作，以獲得最新的數據。
空間利用率：B+樹通常具有更好的空間利用率，因為它在非葉子節點上存儲了完整的鍵值對信息。相比之下，LSM-Tree通過使用內存中的日誌結構和磁盤上的合併操作，可能會導致一些冗餘的數據複製和存儲。
數據一致性：B+樹在寫入過程中保持較好的數據一致性。每次寫入操作都直接更新原始數據，並且支持事務機制。相比之下，LSM-Tree採用了寫入追加和合併操作，可能在某些情況下引入一定的數據不一致性。

罗辑精读DDIA 第三章 Storage & Retrieval 下篇｜系统设计经典教材 Designing Data-Intensive Applications

為什麼LSM-Tree近年來變得流行起來呢？這主要歸因於以下因素：

大數據和寫入密集工作負載的需求：隨著數據規模和寫入負載的不斷增加，傳統的B+樹在寫入性能方面可能面臨挑戰。 LSM-Tree通過優化寫入操作，能夠更好地適應大規模和寫入密集的應用場景。
磁盤隨機訪問的開銷：B+樹在磁盤隨機訪問方面的開銷較高，而LSM-Tree通過批量合併和順序寫入的方式，減少了磁盤的隨機訪問，提高了磁盤的利用率。
分佈式系統和高可用性：LSM-Tree對於分佈式系統和高可用性方面的需求較為友好。它的寫入追加和合併操作可以更好地支持分佈式存儲和數據複製，以提供數據的持久性

3. 請簡單描述一下 CAP 理論

Interview/02_Backend.md 後端面試問題- 8.2. 關於CAP理論，舉一些CP、AP、CA系統的例子。

AP Database — 犧牲一致性的分散式資料庫

在分區容忍的前提下（因為都已經採用分散式架構了），犧牲一致性來提高可用性（盡可能每次都得到回應），不過雖然犧牲了一致性，卻仍可以達到最終一致性（Eventual Consistency，例如總統大選開票時每家新聞台的即時票數都不一致，但在選舉結束後的票數還是會達成一致。），適合在需要快速讀寫，但資料對於一致性的需求較低的場景，例如臉書或各大媒體平台的按讚系統。

例如：Amazon DynamoDB

DynamoDB 實現可用性的主要方法：

多區域部署：DynamoDB 允許在多個 AWS 區域中部署數據表。這樣做可以實現跨區域的冗餘和故障恢復能力。當一個區域出現故障時，可以自動切換到另一個可用的區域。
自動故障檢測和恢復：DynamoDB 內建了自動故障檢測和恢復機制。它可以檢測節點和服務器的故障，並自動遷移數據和重新平衡負載，以確保數據的可用性。
冗餘數據存儲：DynamoDB 使用冗餘數據存儲機制，將數據副本存儲在多個節點上。這樣即使單個節點或服務器發生故障，仍然可以從其他節點獲取數據，確保數據的可用性。
容錯設計：DynamoDB 的架構和設計考慮了容錯性。它使用分散式架構和分區數據存儲，避免單點故障和單一故障域，從而提供高可用性。
自動水平擴展：DynamoDB 具有自動水平擴展的能力。它可以根據負載情況自動調整節點和資源，以應對流量的增長和變化

CP Database — 犧牲可用性的分散式資料庫

在分區容忍的前提下，依然可以得到最新版本的資料，常用於貼文系統、訊息系統等不能犧牲一致性的系統。例如：Google BigTable、MongoDB、分散式的 RDBMS

CA Database — 犧牲分區容忍性的資料庫

這樣就違反了分散式架構的初衷，因此基本上不會存在於分散式系統中。例如：單機或是經過 Sharding 的資料庫（不能承受單機損壞）。

3.1 MongoDB 叢集是犧牲了 CA 的哪個點來達到 P 的?

MongoDB is a CP system and Cassandra is an AP system.

在MongoDB的副本集（Replica Set）中，數據在主節點（Primary）和從節點（Secondary）之間進行同步複製。主節點負責處理寫入操作，並將寫入操作複製到從節點上。因此，在發生網絡分區或主節點故障的情況下，系統會選擇維持一致性，暫停對外提供服務，直到分區問題解決或選舉出新的主節點。

Database Interview