此前，帶你讀源碼第五篇《
戳這裡回顧：OceanBase 源碼解讀（五）：租戶的一生》為大家介紹了社群版中建立、删除租戶、資源隔離的相關代碼，本文将為大家詳細講解 OceanBase 存儲引擎。
本文将回答關于 OceanBase 資料庫的相關提問：
- OceanBase 是否依賴其他開源KV資料庫（例如：LevelDB、RocksDB）？
- OceanBase 底層引擎是什麼？是KV嗎 ？
- OceanBase 記憶體結構是 B+Tree 還是 LSMTree ？
- OceanBase 如何實作高性能服務？
背景
目前業界資料庫存儲引擎主要分為兩種：
- update-in-place ：原地更新，較常見于傳統關系型資料庫( MySQL、Oracle )采用的 B+Tree 結構。優點：更新記錄時對原有記錄進行覆寫寫。有較好的資料局部性，對掃描比較友好。缺點：是引入大量的随機寫，同時還有一定的并發問題；并且與業務流量疊加，對業務流量有一定的影響；
- log-structure storage：日志更新，例如LevelDB、RocksDB、HBase、BigTable 等采用的 LSMTree 結構。優點：日志更新無鎖，不會引入并發問題，能夠保證高效寫入，并且沒有空間碎片。缺點：是讀路徑變長，例如 LSMTree 結構在掃描時需要讀取 memtable 、L0層及其餘層的資料，并進行歸并，需要通過異步 compaction 進行GC以及均衡各個層級的資料來避免過多的讀放大。
為追求極緻的資料庫性能，scan 操作需要良好的空間局部性，get/put 操作需要高效的索引來定位，version/gc/compaction 會提升讀操作的性能但可能影響整體性能，目前的存儲引擎都存在着一定的局限性。
為此 OceanBase 選擇完全自主實作存儲引擎，沒有借助于任何其他已有的開源方案。
從架構上看，OceanBase 的存儲引擎可分為兩層：
①底層的分布式引擎實作了線性擴充、Paxos 複制、分布式事務等分布式特性進而達到持續可用；②上層的單機引擎融合了傳統關系資料庫以及記憶體資料庫的一些技術進而達到極緻性能。
本文将從單機引擎和分布式架構視角分别介紹。
01 單機引擎
讀寫分離架構
OceanBase 的存儲引擎采用分層 LSMTree 結構，資料分為兩部分：基線資料和增量資料。
基線資料是持久到磁盤上的資料，一旦生成就不會再修改，稱之為 SSTable。
增量資料存在于記憶體，使用者寫入都是先寫到增量資料，稱之為 MemTable，通過 Redo Log 來保證事務性。
當 MemTable 達到一定門檻值時會觸發當機( Frozen MemTable )，并重新開啟一個新的 MemTable( Active MemTable )，Frozen MemTable 被轉存到轉儲 SSTable 中，然後在合并( LSMTree 結構特有的 compaction 動作 )時将轉儲 SSTable 合并入基線 SSTable，生成新的 SSTable 。
在查詢時，需要将 MemTable 和 SSTable 的資料進行歸并，才能得到最終的查詢結果。
系統為基線資料和增量資料指定不同的版本，資料版本是連續遞增的。
每生成一個新的 Active MemTable，都會設定為上個 MemTable 的版本加1（實際生産中，兩次合并之間會有多次轉儲，這兩次合并之間生成的所有MemTable 表示一個大版本，每個 MemTable 會用小版本表示，例如下圖中的v3.1和v3.2）。當 SSTable 與 Frozen MemTable 合并之後，也會将版本設定為合并的 Frozen MemTable 的版本。
讀寫分離架構好處：因基線資料是靜止狀态，友善對其進行壓縮，減少存儲成本和提升查詢性能；做行級緩存不用擔心寫入帶來的緩存失效問題。
讀寫分離架構缺點：讀路徑變長，資料需要實時歸并可能帶來性能損耗，需要合并減少資料檔案，同時我們引入多層 Cache 來緩存頻繁通路的資料。
合并是基于 LSMTree 架構的存儲引擎特有的動作，用于基線資料和增量資料的歸并，在 HBase 和 RocksDB 稱為 major compaction。
OceanBase 通常在每天的業務低峰期觸發合并，非低峰期通過轉儲來釋放記憶體，我們稱之為“每日合并”。在合并視窗内做了資料壓縮、資料校驗、物化視圖、schema 變更等事情。
合并提供很多好處，但也需承受一定的代價——對系統的 IO 和 CPU 會有較多的消耗。
目前業界的 LSMTree 資料庫沒能很好的解決該問題，為此 OceanBase 做了優化，包括增量合并、漸進合并、并行合并、輪轉合并、IO隔離等技術。
相比較于傳統關系型資料庫，每日合并可以更好的利用業務低峰期的空閑IO，對資料壓縮、校驗、物化視圖等也提供更好的支援。
轉儲是将記憶體中的增量資料存儲于磁盤，類似于 HBase 和 RocksDB 的 minor compaction ，可以緩解 LSMTree 架構下的記憶體壓力。
OceanBase 采用了分層轉儲的政策，達到了讀取和寫入之間的平衡，避免轉儲 SSTable 過多拖慢讀性能，同時也避免了業務大量随機寫造成的轉儲寫放大。
OceanBase 還進行了資源隔離（包括CPU、記憶體、磁盤IO、網絡IO等四個方面的資源隔離）避免轉儲消耗過多資源，減少對使用者請求的影響。
這些方面的優化平滑了轉儲對性能的影響，使得 OceanBase 在 TPC-C 測試中性能曲線絕對平滑。
基線資料
SSTable 将資料按照主鍵的順序有序存儲，資料被劃分為2MB的塊，稱之為宏塊。
每個宏塊對應一個主鍵範圍的資料，為了避免讀一行要加載一個宏塊，宏塊内部又劃分為多個微塊，微塊的大小一般為16KB。合并時微塊寫滿16KB時，根據行資料的規律探測編碼規則，并根據選擇的編碼規則對資料進行編碼及計算 checksum ，是以微塊是讀IO的最小機關。
OceanBase 的微塊壓縮後是“變長資料塊”，空間浪費很少。而傳統關系型資料庫是“定長資料塊”，開啟壓縮會不可避免的造成存儲的空洞，存在較多的空間浪費，壓縮率受影響。
在相同塊大小（16KB），相同壓縮算法，相同資料的情況下，在 OceanBase 中要比在傳統關系型資料庫中節省相當多的空間。
宏塊是合并時的基本機關，SSTable 按照宏塊來疊代，MemTable 按照行來疊代。如果 MemTable 的行不在宏塊的資料範圍裡面，新版本的 SSTable 直接引用該宏塊。如果宏塊的資料範圍内有更新資料，需要将宏塊打開，解析微塊索引，并疊代所有微塊。
對于每一個微塊，加載行索引，将所有行解析出來跟MemTable進行合并，如果已經 append 的行達到16KB，則建構成一個新微塊，并進行編碼壓縮及計算 checksum。對于未修改過的微塊，不用解析微塊内的内容，直接将整個微塊拷貝到新的宏塊即可。
OceanBase 對資料品質保持着敬畏之心，合并時會做兩方面的資料校驗：
① 一方面同一份資料會有多個副本，會做副本間的一緻性檢驗，保障業務資料在不同副本間是一緻的；② 另一方面會做主表和索引表的一緻性校驗，保障資料在主表和索引表之間是一緻的。
資料校驗是 OceanBase 對自己的一道防火牆，保障傳遞給業務的資料是完全正确的，避免客戶投訴才知曉。
增量資料
MemTable在記憶體中維護曆史版本的事務，每一行将曆史事務針對該行的操作按時間序從新到舊組織成行操作鍊，新事務送出時會在行操作鍊頭部追加新的行操作。
如操作鍊儲存的曆史事務過多，将影響讀取性能，此時需要觸發 compaction 操作，融合曆史事務生成新的行操作鍊，compaction 操作不會删除老的行操作鍊。
OceanBase 基于以上 MVCC 機制實作并發控制，讀事務與寫事務互不影響:
① 如讀請求隻涉及一個分區或者單台 OBServer 的多個分區，執行快照讀即可；② 如涉及多台 OBServer 的多個分區，需要執行分布式快照讀。
MemTable 中采用雙索引結構，一塊是 Hashtable ，用于KV類的快速查詢；一塊是BTree，用于Scan等掃描查詢。在插入/更新/删除資料時，資料被寫入記憶體塊，在 Hashtable 和 BTree 中存儲的均為指向對應資料的指針。
每次事務執行時，會自動維護兩塊索引之間的一緻性。兩種資料結構各有優劣：
① 插入一行資料的時候，需要先檢查此行資料是否已經存在，檢查沖突時，用 Hashtable 比 BTree 快；② 事務在插入或者更新一行資料時，需要找到此行并對其進行上鎖，防止其他事務修改此行，在 ObMvccRow 中尋找行鎖時，用 Hashtable 比 BTree 快；③ 範圍查找時，由于 BTree 節點中的資料是有序的，能夠提高搜尋的局部性，而 Hashtable 是無序的，需要周遊整個 Hashtable 。
OceanBase 是一個準記憶體資料庫，絕大部分的熱點資料都是在記憶體中，以行的方式組織，且在記憶體不足時以MB粒度将資料寫入磁盤，避免了傳統關系型資料庫以頁面為機關的寫入放大問題，從架構層面大大提升了性能。
OceanBase 還引入記憶體資料庫的優化技術，包括記憶體多版本并發、無鎖資料結構等，實作最低延遲及最高性能。
同等硬體下，OceanBase 性能相比傳統關系型資料庫有很大提升，再加上得益于多副本強同步而采用的普通PC伺服器，資料庫的硬體成本大大降低。
緩存
上文提到由于讀路徑變長，我們引入了多層 Cache 機制。
Cache 主要用于緩存 SSTable 中頻繁通路的資料，有用于緩存 SSTable 資料的 block cache、有用于緩存微塊索引的 block index cache 、有用于緩存資料行的row cache，有用于緩存 bloomfilter 可以快速過濾空查的 bloomfilter cache。
由于 SSTable 非合并期間隻讀，是以不用擔心 Cache 失效的問題。
讀請求來臨時，首先從 Cache 中讀取資料，如果 Cache 沒有命中會産生磁盤IO讀取微塊資料，可以根據 Cache 命中次數及磁盤讀取次數來計算邏輯讀，邏輯讀用于評估 SQL 執行計劃的優劣。對于單行操作，如果行存在，則會命中 row cache；如果行不存在，則命中 bloomfilter cache。
是以絕大部分單行操作在基線資料中隻需要一次緩存查找，沒有額外開銷。
OceanBase 中有兩個子產品會占用大量的記憶體:① MemTable 為不可動态伸縮的記憶體；② 就是 Cache 為可動态伸縮的記憶體。
與 linux 的 Cache 政策一樣，OceanBase 中的 Cache 也會盡量使用記憶體，力求把除 MemTable 以外的記憶體用滿。是以 OceanBase 為 Cache 設計了優先級控制政策及智能淘汰機制。
類似于 Oracle 的 AMM，設計了一套統一的 Cache 架構，所有不同租戶不同類型的 Cache 都由架構統一管理，對于不同類型的 Cache，會配置不同的優先級。（例如 block index cache 優先級較高，一般是常駐記憶體很少淘汰，row cache 比 block cache 效率更高，是以優先級也會更高。）
不同類型的 Cache 會根據各自的優先級以及資料通路熱度做互相擠占。優先級一般不需要配置，特殊場景下可以通過參數控制各種 Cache 的優先級。如果寫入速度較快，MemTable 占用記憶體較多，會逐漸淘汰 Cache 記憶體給MemTable 使用。
Cache 記憶體以2MB為機關進行淘汰，根據每個2MB記憶體塊上各個元素的通路熱度為其計算一個分值，通路越頻繁的記憶體塊的分越高，同時有一個背景線程來定期對所有2M記憶體塊的分值做排序，淘汰掉分值較低的記憶體塊。
在淘汰時，會考慮各個租戶的記憶體上下限，控制各個租戶中 Cache 記憶體的使用量。
極緻性能
基以上介紹，OceanBase 的存儲引擎非常接近于傳統關系型資料庫的單機引擎特性——一個資料分區的所有資料（基線資料 + 增量資料 + 緩存資料 + 事務日志）全部放于一個 OBServer 中。
是以針對一個資料分區的讀寫操作不會有跨機操作（除了事務日志通過 Paxos 協定形成多數派同步），再加上準記憶體資料庫及極佳的 Cache 機制，進而能夠提供極緻的OLTP性能。
02 分布式架構
資料分區
OceanBase 的兩種方式：
① 引入傳統關系資料庫中的資料分區表( Partition )的概念；
② 相容傳統關系型資料庫的分區表文法，支援 hash 分區和 range 分區。
支援二級分區機制，例如對于曆史庫場景，單表資料量龐大，一級按使用者分區，二級按時間分區。進而很好的解決大使用者擴充性的問題，如果要删除過期資料，可以通過 drop 分區實作。
也支援生成列分區，生成列指這一列由其他列計算所得，該功能能夠滿足期望将某些字段進行一定處理後作為分區鍵的需求。
對分區表查詢進行優化：
① 對于查詢中包含分區鍵或者分區表達式的查詢，能夠準确的計算出該查詢對應的分區，稱為分區裁剪；
② 對于多分區查詢，能夠使用分區間并行查詢、分區間排序消除、partition-wise join 等技術，進而大大提升查詢性能。
同一資料分區的副本構成一個 Paxos Group，自主進行選主，推舉出其中某個副本作為 Leader，其他副本自動成為 Follower，後續所有針對這個資料分區的讀寫請求，都會自動路由到對應的 Leader 進行服務。
OceanBase 采用 share-nothing 的分布式架構，每個 OBServer 都是對等的，管理不同的資料分區。
① 對一個資料分區所有讀寫操作都在其所在的 OBServer 完成，屬于單分區事務；
② 多個資料分區的事務，采用兩階段送出的方式在多個 OBServer 上執行，屬于分布式事務。
單機多分區事務，依然需要走兩階段送出，且針對單機做了專門的優化。分布式事務會增加事務延遲，可以通過表格組(table group) 将經常一起通路的多張表格聚集在一起，同一表格組的分區具有相同的 OBServer 分布，且 Leader 位于同一台機器上，避免跨機事務。
傳統關系型資料庫也支援分區功能，但所有分區仍存放在同一台機器上。
而 OceanBase 能夠把所有分區打散到不同實體機器，進而能夠真正展現出分布式架構的優勢，進而徹底解決可擴充性問題。
當容量或者服務能力不足時，隻需要增加更多的資料分區并打散到更多的 OBServer 即可，進而可以通過線上線性擴充的方式提升整體讀寫性能。在同樣系統容量充足或者處理能力富餘時，将機器下線，降低成本，提供良好的彈性伸縮能力。
多副本Paxos同步
OceanBase 中的資料分區備援有多個副本（例如，同城三副本部署架構為3個，三地五副本部署架構為5個），分布于多個 OBServer 上。
事務送出時利用 Paxos 協定在多個副本間達成多數派送出，進而維護副本之間的一緻性。當單台 OBServer 當機時可以維護資料的完整性，并在較短的時間内恢複資料通路，達到 RPO=0、RTO<30秒的SLA。
使用者無需關心資料所在的具體位置，用戶端會根據使用者請求來定位資料所在的位置，進而将讀寫請求發送給 Leader 進行處理，對外仍然展現為一個單機資料庫。
基于以上介紹的多副本架構我們引入了輪轉合并的概念，将使用者請求流量與合并過程錯開來。
比如：一個OceanBase叢集中Partition的副本個數為3，這三個副本分布在3個不同的Zone(1,2,3)中，RootService在控制合并時，比如先合并Zone3，會首先将使用者流量切到Zone(1,2)中，隻要切換所有Partition的Leader到Zone(1,2)即可。Zone3合并完成之後，準備合并Zone2，則将Zone2的流量切走，之後再合并Zone1，最後三個副本全部合并完畢，恢複初始的Leader分布。
多副本架構帶來了三個比較大的架構提升：
- 資料庫服務的可用性得到提升，如果某個 OBServer 突發當機或者網絡分區，自動、迅速的把故障 OBServer 的讀寫服務切換到其他 OBServer 上，RPO=0，RTO<30秒。傳統關系型資料庫通過主備架構來容災，在不使用共享存儲的情況下，難以完美做到在主庫故障時資料零丢失，且由于資料一緻性問題無法自動切換，切換效率也難以保證；
- 資料庫的資源使用率得到提升，利用 OceanBase 多庫多活的特性，配置讓三個 Zone 中的兩個提供讀寫服務，第三個 Zone 作為熱備庫接受事務日志，随時待命提供讀寫服務。OceanBase 的機器使用率達到了2/3，而傳統關系型資料庫主備架構隻能使用到1/2的機器；
- 資料庫的資料壓縮率得到提升，由于輪轉合并的引入，使用者請求流量與合并過程錯峰，正在合并的 Zone 的 CPU 和磁盤IO可以大量用于複雜的資料編碼/壓縮，并選擇最優的編碼算法，并且對業務資料寫入零影響。高壓縮率不但節省了存儲空間，同時也會極大的提升查詢性能。傳統關系型資料庫原地更新資料，與業務流量疊加，在“高壓縮率”和“低計算成本”兩者之間隻能選擇後者，甚至建議使用者謹慎使用該功能。
03 總結
基于 LSMTree 的單機引擎和基于多副本強同步的分布式架構，才是完整的 OceanBase 存儲引擎。這種存儲引擎有衆多好處，既有類似于 Oracle 的關系型資料庫上層，又有類似于 spanner 的分布式底層。
這是 OceanBase 的核心能力，能夠規避 LSMTree 缺陷，獲得極緻性能和絲般順滑，支援最核心的 OLTP 業務。同時又獲得了分布式架構的優勢，包括持續可用、線性擴充、自動容錯、低成本等特性。
//作者感言
從2010年一路走來，每一步 OceanBase 猶如走在懸崖峭壁，走得十分小心翼翼。回頭看，非處當時之情景，不能了解當時之設計。好的設計不是“想”出來的，而是“痛”出來的，希望大家在閱讀時也能夠感受到這份成果背後的“痛并快樂着”。