數據庫類型	存儲引擎	數據結構	源碼位置
tidb	RockDB	LSM樹	https://github.com/facebook/rocksdb
mongodb	WiredTiger	B 樹/LSM樹	https://github.com/wiredtiger/wiredtiger
TDengine	TSDB	BRIN	https://github.com/taosdata/TDengine

1、tidb存儲引擎概覽

LSM樹數據結構描述

LSM樹(Log Structured Merged Tree)

1. LSM樹是一個橫跨內存和磁盤的，包含多顆"子樹"的一個森林。
2. LSM樹分為Level 0，Level 1，Level 2 … Level n 多顆子樹，其中只有Level 0在內存中，其余Level 1-n在磁盤中。
3. 內存中的Level 0子樹一般采用排序樹（紅黑樹/AVL樹）、跳表或者TreeMap等這類有序的數據結構，方便后續順序寫磁盤。
4. 磁盤中的Level 1-n子樹，本質是數據排好序后順序寫到磁盤上的文件，只是叫做樹而已。
5. 每一層的子樹都有一個閾值大小，達到閾值后會進行合并，合并結果寫入下一層。
6. 只有內存中數據允許原地更新，磁盤上數據的變更只允許追加寫，不做原地更新。

LSM樹詳述：https://zhuanlan.zhihu.com/p/415799237

RocksDB內存結構描述
MemTable

MemTable是一個內存數據結構，他保存了落盤到SST文件前的數據。他同時服務于讀和寫——新的寫入總是將數據插入到memtable，讀取在查詢SST文件前總是要查詢memtable，因為memtable里面的數據總是更新的。一旦一個memtable被寫滿，他會變成不可修改的，并被一個新的memtable替換。一個后臺線程會把這個memtable的內容落盤到一個SST文件，然后這個memtable就可以被銷毀了。并且在flush的過程中，會完成數據的壓縮

RocksDB默認實現方式是SkipList，適用于范圍查詢和插入，但是如果是其他場景，RocksDB也提供了另外兩種實現方式。具體區別可參考https://github.com/facebook/rocksdb/wiki/MemTable

a vector memtable:適用于批量載入過程，每次新增元素都會追加到之前的元素后，當MemTable的數據被刷入L0時，數據會按之前的順利刷入SST file
a prefix-hash memtable:適用于帶有指定前綴的查詢，插入和scan

Immutable Memtable

所有的寫操作都是在memtable進行，當memtable空間不足時，會創建一塊新的memtable來繼續接收寫操作，原先的內存將被標識為只讀模式，等待被刷入sst。在任何時候，一個CF中，只存在一塊active memtable和0+塊immutable memtable。刷入時機有以下三個條件來確定：

write_buffer_size 設置一塊memtable的容量,一旦寫滿，就標記為只讀，然后創建一塊新的。
max_write_buffer_number 設置memtable的最大存在數(active 和 immutable 共享)，一旦active memtable被寫滿了，并且memtable的數量大于max_write_buffer_number,此時會阻塞寫操作。當flush操作比寫入慢的時候，會發生這種情況
min_write_buffer_number_to_merge 設置刷入sst之前，最小可合并的memtable數，例如，如果設置2，只有當 immutable memtable數量達到2的時候，會被刷入sst，數量為1的時候，則永遠不會被刷入。RocksDB 寫入數據描述

寫操作包含兩個具體步驟：

首先是將這條KV記錄以順序寫的方式追加到log文件末尾，因為盡管這是一個磁盤讀寫操作，但是文件的順序追加寫入效率是很高的，所以并不會導致寫入速度的降低。
第二個步驟是:如果寫入log文件成功，那么將這條KV記錄插入內存中的Memtable中，Memtable只是一層封裝，其內部其實是一個Key有序的SkipList列表，插入一條新記錄的過程也很簡單，即先查找合適的插入位置，然后修改相應的鏈接指針將新記錄插入即可。完成這一步，寫入記錄就算完成了，所以一個插入記錄操作涉及一次磁盤文件追加寫和內存SkipList插入操作，這是為何RocksDB寫入速度如此高效的根本原因。
刪除操作與插入操作相同，區別是，插入操作插入的是Key:Value值，而刪除操作插入的是“Key:刪除標記”，并不真正去刪除記錄，而是后臺Compaction的時候才去做真正的刪除操作。

RocksDB 讀取數據描述

RocksDB首先會去查看內存中的Memtable，如果Memtable中包含key及其對應的value，則返回value值即可；如果在Memtable沒有讀到key，則接下來到同樣處于內存中的Immutable Memtable中去讀取，類似地，如果讀到就返回，若是沒有讀到,那么會從磁盤中的SSTable文件中查找。
總的讀取原則是這樣的：首先從屬于level 0的文件中查找，如果找到則返回對應的value值，如果沒有找到那么到level 1中的文件中去找，如此循環往復，直到在某層SSTable文件中找到這個key對應的value為止（或者查到最高level，查找失敗，說明整個系統中不存在這個Key)。
相對寫操作，讀操作處理起來要復雜很多。RocksDB為了提高讀取速遞，增加了讀cache和Bloomfilter。
2、mongodb存儲引擎概覽

mongodb目前的默認引擎WiredTiger的默認數據結構是B樹，創建LSM樹的集合需要指定

db.createCollection(
“test”,
{ storageEngine: { wiredTiger: {configString: “type=lsm”}}}
)

B樹數據結構描述

B 樹的非葉結點也可以存儲數據，所以查詢一條數據所需要的平均隨機 IO 次數會比 B+ 樹少，使用 B 樹的 MongoDB在單條記錄的等值查詢場景性能優于B+樹。

LSM 樹的寫入性能是 B 樹的 1.5 ~ 2 倍；LSM 樹的讀取性能是 B 樹的 1/6 ~ 1/3；wiredtiger官方提供的兩種數據結構的測試對比 https://github.com/wiredtiger/wiredtiger/wiki/Btree-vs-LSM

WiredTiger數據組織方式

這種數據組織結構分為兩部分：

in-memory page： 內存中的數據頁（page）disk extent： 基于磁盤文件的偏移量的范圍存儲

WiredTiger 內存中的 page 是一個松散自由的數據結構，而磁盤上的 extent 只是一個變長的序列化后的數據塊，這樣做的目的（設計目標）有以下幾點：

內存中的 page 松散結構可以不受磁盤存儲方式的限制和 The FIX Rules 規則的影響，可以自由的構建 page 無鎖多核并發結構，充分發揮 CPU 多核的能力。可以自由的在內存 page 和磁盤 extent 之間實現數據壓縮，提高磁盤的存儲效率和減少 I/O 訪問時間。WiredTiger內存中的數據頁（b樹數據結構）

WiredTiger 數據組織方式就是 in-memory page 加 block-extent。先來對它內存部分的 in-memory page（內存數據頁，簡稱為 page）來做分析。

WiredTiger 引擎中的 page 分以下幾類：

row internal page： 行存儲 b-tree 的索引頁
row leaf page：行存儲 b-tree 的數據頁
column internal page： 列存儲 b-tree 的索引頁
column fix leaf page：列存儲 b-tree 的定長數據頁column var leaf page： 列存儲 b-tree 的變長數據頁

因為 MongoDB 主要是使用行存儲，所以在這里主要分析 row leaf page 這個結構和原理，結構圖如下：

上圖中主要有以下幾個單元：

wt_page：內存中的 page 結構對象，page 的訪問入口。wt_modify：page 的修改狀態信息，主要包含臟頁標示、當前更新事務 ID 和 page 的 insert lock等。row_array：磁盤上原有 row 的位置索引數組，主要用于頁內檢索。row_insert_array：一個增加 kv（insert k/v）的跳表對象數組row_update_array：一個在 row 基礎上做更新（update k/v）的 value mvcc list對象素組。page_disk： 從磁盤上讀取到的 extent 數據緩沖區，包含一個 page_header 和一個數據存儲緩沖區（disk data）page disk data：存儲在磁盤上的 page k/v cell 行集合數據

更新和插入示例：

我們通過一個實例來說明，假如一個 page 存儲了一個 [0，100] 的 key 范圍，磁盤上原來存儲的行 key=2， 10 ，20， 30 ， 50， 80， 90，他們的值分別是value = 102， 110， 120， 130， 150， 180， 190。在 page 數據從磁盤讀到內存后，分別對 key=20 的 value 進行了兩次修改，兩次修改的值是分別 402，502。對 key = 20 ，50 的 value 做了一次修改，修改后的 value = 122， 155，后有分配 insert 了新的 key = 3，5， 41， 99，value = 203，205，241，299。

那么在內存中的 page 就是如下圖組織數據的：

row_array 的長度是根據 page 從磁盤中讀取出來的行數確定的，每個數組單元（wt_row）存儲的是這個 kv row 在 page_disk_data 緩沖區偏移的位置和編碼方式（這個位置和編碼方式在 WT 上定義成一個 wt_cell 對象，在后面的 K/V cell章節來分析），通過這個信息偏移位置信息就可以訪問到這一樣在 disk_data緩沖區中的 K/V 內容值。

每一個 wt_row 對象在 row_update_array 數組中對應一個 mvcc list 對象，mvcc_list 與 wt_row 是一一對應的，mvcc list 當中存儲對 wt_row 修改的值，修改的值包括值更新和值刪除，是一個無鎖單向鏈表。

相鄰的兩 wt_row 之間可能不是連續的，他們之間可以插入新的單元，例如 row1(key = 2) 和 row2(key=10) 可以插入 3 和 5，這兩個 row 之間需要有一個排序的數據結構（WT用 skiplist 數據結構）來存儲插入的 K/V，就需要一個 skiplist 對象數組 page_insert_array與row array對應。這里需要說明的是 圖6 當中紅色框當中的 skiplist8，它是用于存儲 row1(key=2) 范圍之前的 insert 數據，圖6 中如果有 key =1 的數據 insert，那么這個數據會新增到 skiplist8 當中。

那么 上圖 中 row 與 insert skiplist 的對應關系就是：

row1 之前的范圍對應 insert 是 skiplist8row1 和 row2之間對應的 insert 是 skiplist1row2 和 row3之間對應的 insert 是 skiplist3…row7 之后的范圍對應的 insert 是 skiplist7

wt_row 結構

從上面對應 page 的整體分析來看在 WT 的 page 中，row 對象是整個 row leaf page 的關鍵結構，row 其實就是 K/V 位置的描述值（kv_pos），它的定義：

wt_row{uint64 kv_pos；//這個值是在page讀入內存時根據KV存儲在page_disk的位置確定的}

這個 kv_pos 的對應的數據有對應的 K/V 存儲位置信息，kv_pos 表示這個 K/V 的值有三種方式，結構如下圖：

上圖中的 wt_row 對應的空間上都有 2 個 bit 的 flag，這個 flag 的值：

CELL_FLAG： 0x01，表示這個 row 用 cell 對象來 k/v 標示存儲位置的，因為 key 和 value 的值有可能很大，一個 page 存儲不下，這個時候引入 cell 只是存儲這些超長值對應的 overflow page 的索引值（extent adress）。K_FLAG：0x02，表示這個 row 只標示了 k/v 中 key 的存儲位置，但是 value 比較大，value 是 CELL_FLAG 方式標示位置存儲的，因為 value 的 CELL 是緊跟在 key 存儲的位置后面，找到 key 就能讀取 value 的 cell 并找到 value。KV_FLAG：0x03，表示這個 row 同時標示了 k/v 中 key 和 value 的存儲位置。

Cell 結構

Cell 是一個值 key 或者 value 信息被序列化后的數據塊，cell 在磁盤上和在內存中內容是一致的，它是根據值（key 或者 value）內容、長度、值類型序列化構建的。在內存中 cell 是存儲在 page_disk 緩沖區中，在磁盤上是存儲在 extent body 上，在讀取 cell 的時候需要根據 cell 數據內容進行反序列化得到一個 cell_unpack 內存結構對象，讓后再根據這個 cell_unpack 對象中的內容來讀取這個值（key 或者 value）。以下是它們之間的結構關系：

那么在 row 對象中的 CELL_FLAG row、K_FLAG row 和 KV_FLAG row 對應的值是怎么產生的呢？

其實是在 page 的數據從磁盤讀到內存中時，先會對整個 page_disk 按照 cell 為單位轉化成 cell_unpack，并根據 cell_unpack 中的信息構造 row 的這三種格式，這樣做的目的是讓能生成 K_FLAG /KV_FLAG 的 row 在每次被訪問的時候不需要去做這個過程的轉化，加快訪問速度。
內存中的修改

內存中的 row 對象主要是為了幫助 page 數據從磁盤上載入到內存中后建立查詢索引，而 page 數據被載入內存后除了查詢讀以外，還會對其進行修改行為（增刪改），對于修改行為 WT 并沒有在 row 內存結構上進行操作，而是設計兩個結構，一個是針對 insert 操作的 insert_skiplist，一個針對刪改操作的 mvcc list。關于這兩個對象結構與 row 之間的關系在 圖6 中有過描述。在這里重點來分析它們的內部構造和運行原理。
跳表（skiplist）

從前面的介紹知道 page 在內存中存儲新增的 k/v 時采用的是 skiplist 數據結構，在 WiredTiger 中不僅僅這個地方使用了 skiplist，在其他需要快速查詢和增刪的地方基本上都使用了 skiplist，了解 skiplist 的原理有利于理解 WiredTiger 的實現。skiplist 其實是個多層鏈表，層級越高越稀疏，最底層是個普通的鏈表。

skiplist 原理參看 https://en.wikipedia.org/wiki/Skip_list

skiplist 實現參看 https://github.com/yuanrongxi/wb-skiplist
新增的 K/V 結構

WiredTiger 中 insert_skiplist 實現時是結合了它本身的 k/v 內存結構來實現的，WT 基于skiplist定義了一個 wt_insert 的 k/v 跳表單元結構，定義如下：

wt_insert{key_offset：//存儲key的緩沖區偏移key_size：//key的長度value：//存儲值的mvcc list的頭單元，一個wt_update結構對象next[]：//skiplist的各層的下一個單元指針key_data[]：//存儲key的緩沖區}

insert_skiplist 的結構示意圖：

WiredTiger 為什么選用 skiplist 來作為新增記錄的數據結構？主要是幾個方面的考慮：

skiplist 實現起來簡單，而且可以根據使用場景因地制宜的和 K/V 在內存做比較結合。skiplist 復雜度為 O(log n)，可以在內存中管理大量 k/v 的增刪改查操作，而且 skiplist 在內存中按照 key 大小排序的，可以進行范圍查找。skiplist 在增刪操作時可以不排斥讀操作，也就是說一個線程在讀 skiplist 時不需要檢查 skiplist 的 write_lock，相當于無鎖讀，這實現增加了 skiplist 的讀并發。

修改的 value

WiredTiger 引擎在 insert 一個 k/v 時，key 值是存儲在 wt_insert 中，那么它的 value 存儲在什么地方？

在 wt_insert 結構中有一個 wt_update 類型的 value 說明，這個結構其實就是來存儲內存中各個修改版本的 value 值的鏈表對象，也就是提到的 MVCC list 鏈表。在 圖6 中也有提到 row 更新的時候，會向 row_update_array 對應的 mvcc list 當中加入更新的值單元（wt_update），這個結構的定義如下：

wt_update{txnid：//產生修改的事務IDnext ptr：//鏈表的下一個wt_update單元指針size：//value值長度value[]：//存儲value的緩沖區}

size = 0，表示這個是一個刪除 k/v 的修改。

整個鏈表在平常情況下只會進行 append 操作，而且每次 append 都是在鏈表頭的位置，這樣做的目的是為了整個鏈表的無鎖讀寫操作。這里涉及無鎖讀好理解，只要做到無鎖 append 就可以做到無鎖讀。mvcc list 無鎖 append 采用的是 CPU 的 CAS 操作來完成，大致的步驟如下：

先將需要 append 的單元（new_upd）的 next 指針指向 list header 對應的單元（header_upd），并記錄 list_header 指針。使用原子操作 CAS_SWAP 將 list header 設置成為 new_upd，CAS_SET 設置期間如果沒有其他線程先以它完成設置，那么本次 append 就完成。如果有其他線程先以它設置，那么本次設置失敗，進入第 3 步。用 memory barrier 讀取 list_header 的指針，重復第 1 步。

第 2 步的判斷是否有其他線程先以自己設置 list_header 的依據就是 CAS_SWAP 時 list_header 的值不是自己讀取到值。關于這個過程更多的細節可以去了解GCC 編譯器的 __sync_val_compare_and_swap 函數功能和實現。
overflow page

WiredTiger 支持是支持超大的 K/V，key 和 value 的值最大可以到 4GB（其實不到 4G，大概是 4GB - 1KB，因為除了數據外還需要存儲 page 頭信息）。

WiredTiger 通過定義一種叫做 overflow page 來存儲超出 leaf page 最大存儲范圍的超大 k/v。超大的 k/v 在 insert 到 leaf page 還是存儲在 insert_skiplist 當中，只有當這個 leaf page 進行存盤的時候，WT 會對超出 page 允許的最大空間的 k/v 值用單獨的 overflow page 來存儲，overflow page 在磁盤文件中有自己單獨的 extent。

那么什么時候在內存中會出現 overflow page 呢？在用于 overflow page 的 leaf page 從磁盤上讀入內存中時會構建對應的 overflow page內存對象。overflow page 本身的結構很簡單，就是一個 page_header 和一個 page_disk 緩沖區。leaf page 與 overflow page 之間通過 row cell 信息來關聯，cell 里面存有這個 overflow page 的 extent address 信息。

為了對 overflow page 的快速訪問，WT 定義了一個的 skiplist（extent address與overflow page內存對象映射關系）來緩存內存中的 overflow page 內存對象，對 overflow page 的讀流程如下：

先 cell_unpack 對應的 cell，獲取到 overflow page 的 extent addr使用 extent address 在 overflow page 緩存 skiplist 查找 overflow page 是否已經讀入內存，已經讀入內存，返回對應的 overflow page 讀取者，如果沒有進入第 3 步.根據 extent address 信息從磁盤文件中將 overflow page 的信息讀入內存，并構建一個 overflow page 加入到 skiplist 當中。最后返回讀入的 overflow page 對象給讀取者。

這里提到的 extent address 參考下面的 extent addresss 結構章節。
Page 的頁內檢索

WiredTiger 實現松散的內存 page 結構為的就是能快速檢索和修改，也使得數據在內存中的組織方式更加自由。不管是讀還是修改，需要依賴 page 的頁內檢索，在讀取或者修改某個 k/v 值前需要根據對應的 key 在 page 內部做一次檢索來定位 k/v 的位置，而整個頁內檢索的核心參考軸是通 row_array 這個數組做二分查找來定位的。

在這里還是以 圖6 來進行說明，假設需要在 圖6 中查找 key=41 的值，步驟如下：

先通過二分法在 row_array 定位到存儲 key = 41 的對象 row4定位到 row4 后先匹配 row key 與檢索的 key 是否匹配，如果匹配，在 row4 對應的 mvcc list（upd4）中讀取可以訪問的值。如果不匹配，在其對應的 insert_skiplist 進行查找用 key = 41 在跳表 skiplist4 進行查找，定位到 value = 241，返回。

因為都是 row_array/insert_array/update_array 數組一一對應的查找，而且這些數組的在發生修改時也不會發生改變，所以不需要對其進行鎖保護，insert_skiplist 和 mvcc list 都是支持修改時無鎖讀取的（這個在分析這兩個結構時已經說明過），所以說整個檢索過程是無鎖的。

如果是增刪改（insert/delete/update）操作，也是先用檢索過程找到對應修改的位置，再進行對應修改。如果是 insert，或獲取 wt_modify 中的 page_lock 來串行化 insert 操作，如果是對值進行 update/delete，只是在 mvcc list 無鎖增加一個修改后的值即可（這個過程在上面已經分析過）。
Disk extent 結構

Page 在磁盤上文件上對應的結構叫做 extent。其實它就是磁盤文件上的一塊區域。

在 WT 引擎中，每一個索引對應一個文件，文件中按照 page 寫入的大小和當前文件被使用的空間來確定寫入的位置和寫入的長度，寫入的位置（offset）和寫入的長度（size）被命名成 extent，并且將 extent 的位置信息（extent address）記錄到一個索引空間中。

Extent 由三部分構成，他們分別是

page header：記錄當前數據頁的狀態信息block header： extent 存儲的頭信息，主要存有數據的 chucksum 和長度等。extent data：存儲的數據，是一個 cell 數據集合.

page header 在 page 的內存對象中，對應的是 page_disk 的頭信息部分 wt_page_header，他們的內容是完全一致的。page header 包含當前 page 的記錄實例數（entries）、page類型（row leaf page/internal page等），在 page 數據載入內存時需要用這些數據來構建 page 內存對象。

Block header 中的 checksum 是 extent data 的數據 checksum，也是 extent address 中的 checksum。用于 extent 讀入內存時做合法性校驗。
Extent address

Extent address 用于索引 extent 的信息，它作為一個數據條目存在一個特殊的索引 extent 中（關于這個特殊的索引 extent 在后續的磁盤 I/O 篇來詳細分析）。

這里主要分析下它的內部構造和定義，extent address 中有三個值：

offset：extent 在 btree 文件中的偏移位置size：extent 的長度chucksum：extent 的 checksum， 用 page header/block header/extent data 整體計算得到的 checksum，用于判斷 extent 的合法性。

這三個值是序列化后作為 extent address 條目存儲的。
Extent data

Extent data 是真正存儲 page 數據的地方，它是 page 中所有 k/v cell 的集合。Page 數據從內存存入磁盤時，會將每個 k/v pair 用 cell_pack 函數轉化成一個 key cell 和一個 value cell 存入序列化緩沖區中。這個緩沖區的數據寫入到 extent 中就是 extent data，存儲結構如下圖：

Page 的磁盤讀寫

btree 索引管理的最小單元是 page，那么從磁盤到內存的讀操作和從內存到磁盤的寫操作都是以 page 為單位來讀寫。

在 WT 引擎中從磁盤讀取一個頁到內存的操作叫做 in-memory，從內存 page 寫入磁盤的操作叫做 reconcile。in-memory 過程就是將 extent 從磁盤文件中讀取出來轉換成內存 page ，而 reconcile 操作就是將內存中的 page 轉換成 extent 寫入到磁盤上，reconcile 過程會造成 btree page 的分裂。

讀寫序列圖如下：

讀過程（in-memory）

Page 的讀過程是磁盤到內存的過程，步驟如下：

根據 btree 索引上的 extent address 信息，從 btree 對應的文件中讀取這個 extent 到內存緩沖區中。通過讀取的 extent 數據生成 checksum，并與 extent address 中的 checksum 校驗合法性。根據 btree 配置的 meta 信息判斷是否開啟壓縮，如果沒有壓縮直接到第 5 步，如果有壓縮進行第 4 步。根據配置的壓縮算法信息獲取 WT 支持的 compressor 對象，并對 extent data 做解壓縮。通過 wt_page_header 信息構建內存中的 page 對象。通過 wt_page_header 的 entries 數對整個 page_disk_data 遍歷，按照 cell 的信息逐行構建 row_array、insert_array 和 update_array。

如果讀入的 page 包含 overflow page，overflow page 并不會在這個過程中讀取到內存中，而是在訪問它的時候讀取到內存中的，這個過程只會讀取 overflow page 對應的 extent address 作為 row 對象的內容。在 overflow page 一節分析過 overflow page 的讀取過程。
寫過程（reconcile）

寫過程比較復雜，page 的寫過程如果 page 的內存空間過大會對 page 做 split 操作，對于超過 page 容忍的大 K/V 會生成 overflow page。整個寫過程步驟如下：

按照 row_array 為軸，掃描整個 row_array/upate_array 和 insert_array，將 k/v 內存中的值生成 cell 對象，并將其存入一個緩沖區（rec buffer）中。判斷這個緩沖區是否超出了配置的 page_max_size，如果超過了，進行 split 操作。對單個 key 或者 value 超過 page_max_size，生成一個 overflow page，并將 overflow page 對應的 extent address 生成 cell。重復 1 ~ 3 步直到所有的 k/v cell 都寫入到 rec buffer 中。假如 btree 配置了數據壓縮項，在 WT 引擎中查找壓縮對象，并用這個壓縮對象對 rec buffer 進行數據壓縮得到 data buffer，如果沒有配置壓縮跳過這一步（data buffe = rec buffer）。根據 page 對象中的 wt_page_header 的信息將它對應的信息寫入到 data buffer 頭位置。

根據 btree 文件的偏移和空間狀態產生一個 extent，計算 data buffer 的 checksum，并將 data buffer 填充到 extent data 當中。

根據 extent 的信息填充 block_header，將整個 externt 寫入到 btree 的文件當中并返回 extent address。
Page 壓縮

通過 page 的讀寫過程分析知道這兩個過程如果配置了壓縮，就需要調用壓縮解壓縮操作。WT 實現壓縮和解壓縮是通過一個外部自定義的插件對象來實現的，下面是這個對象的接口定義

__wt_compressor{compress_func()；//壓縮接口函數pre_size_func()；//預計算壓縮后數據長度接口函數decompress_func()；//解壓縮接口函數terminate_func()；//銷毀壓縮對象，有點像析構函數}；

WT 提供 LZO/ZIP/snappy 這幾個壓縮算法，也支持自定義壓縮算法，只要按照上面的對象接口實現即可。要讓 WT 支持壓縮算法，需要在 WT 啟動時通過 wiredtiger_open 加載壓縮算法模塊，例子如下：

wiredtiger_open(db_path， NULL， “extensions=[/usr/local/lib/libwiredtiger_zlib.so]”，&connection)；

然后在 WT 引擎創建表時可以配置壓縮啟用壓縮配置即可，例如：

session->create(session， “mytable”， “block_compressor=zlib”)；

WT 的插件式壓縮非常靈活和方便，MongoDB 默認支持 ZIP 和 snappy 壓縮，4.2以后開始支持zstd（Facebook開源，壓縮速率極大提升），在 MongoDB 創建 collection 時是可以進行選擇壓縮算法。

①　mongodb 默認的 snappy 壓縮算法壓縮比約為 2.2-4.5 倍

②　zlib 壓縮算法壓縮比約為 4.5-7.5 倍(本次遷移采用 zlib 高壓縮算法)

壓縮算法	真實數據量	真實磁盤空間消耗
snappy	3.5T	1-1.8T
zlib	3.5T	0.5-0.7T

優化建議

WiredTiger 引擎采用內存和磁盤上不同的結構來實現 page 的數據組織，目標還是讓內存中的 page 結構更加方便在 CPU 多核下的增刪查改的并發操作，精簡磁盤上的 extent 結構，讓磁盤上的表空間管理不受內存結構的影響。基于 extent（偏移 + 數據長度）的方式也讓 WiredTiger 引擎的數據文件結構更簡便，可以輕松實現數據壓縮。

然而這種內存和磁盤上結構不一致的設計也有不好的地方，數據從磁盤到內存或者從內存到磁盤需要多次拷貝，中間還需要額外的內存作為這兩種結構的臨時緩沖區，在物理內存不足的情況下會讓 swap 問題雪上加霜，性能會急劇下降，這個在測試樣例里面有體現。所以要讓 WiredTiger 引擎發揮好的性能，盡讓配備更大物理內存給它使用。

MongoDB 3.2 版本已經將 WiredTiger 作為默認引擎，我們在使用 MongoDB 時一般不會對 WiredTiger 做配置，這可能會有些業務場景發揮不出 WiredTiger 的優勢。MongoDB 在創建 collection 時可以對 WiredTiger 的表做配置，格式如下：

db.createCollection("<collectionName>"， {storageEngine： {wiredtiger： {configString："<option>=<setting>，<option>=<setting>"}}})；

不同的業務場景是可以配置進行不同的配置。

如果是讀多寫少的表在創建時我們可以盡量將 page size 設置的比較小 ，比如 16KB，如果表數據量不太大（<2G），甚至可以不開啟壓縮。那么 createCollection 的 configString 可以這樣設置：

"leaf_value_max=8KB，os_cache_max=1GB"

如果這個讀多寫少的表數據量比較大，可以為其設置一個壓縮算法，例如：

"block_compressor=zlib， internal_page_max=16KB，leaf_page_max=16KB，leaf_value_max=8KB"

如果是寫多讀少的表，可以將 leaf_page_max 設置到 1MB，并開啟壓縮算法，也可以為其制定操作系統層面 page cache 大小的 os_cache_max 值，讓它不會占用太多的 page cache 內存，防止影響讀操作。
優化參數說明：

參數名稱	默認配置值	含義
allocation_size	4KB	磁盤上最小分配單元
memory_page_max	5MB	內存中允許的最大page值
internal_page_max	4KB	磁盤上允許的最大internal page值
leaf_page_max	32KB	磁盤上允許的最大leaf page值
leaf_key_max	1/10*leaf_page? 0	leaf page上允許的最大key值
leaf_value_max	1/2*leaf_page? 64M	leaf page上允許的最大value值
split_pct	75%	reconciled的page的分割百分比

3、TDengine存儲引擎概覽

內存中數據組織形式：SkipList

SkipList：其實跳表就是在普通單向鏈表的基礎上增加了一些索引，而且這些索引是分層的

Skip需要更新的部分比較少，鎖的東西也更少，而諸如AVL樹插入過程中可能需要多次旋轉，導致插入效率較低

（1）查找操作

示意圖如下:

比如我們要查找key為19的結點，那么我們不需要逐個遍歷，而是按照如下步驟:

從header出發，從高到低的level進行查找，先索引到9這個結點，發現9 < 19,繼續查找(然后在level2這層)，查找到21這個節點，由于21 > 19, 所以結點不往前走，而是level由2降低到1
然后索引到17這個節點，由于17 < 19, 所以繼續往后，索引到21這個結點，發現21>19, 所以level由1降低到0
在結點17上，level0索引到19,查找完畢。
如果在level==0這層沒有查找到，那么說明不存在key為19的節點，查找失敗

（2）插入操作

示意圖如下:

其實插入節點的關鍵就是找到合適的插入位置，即從所有小于待插入節點key值的節點中，找出最大的那個，所以插入節點的過程如下:

查找合適的插入位置，比如上圖中要插入key為17的結點，就需要一路查找到12,由于12 < 17,而12的下一個結點19 > 17,因而滿足條件
創建新結點，并且產生一個在1~MAX_LEVEL之間的隨機level值作為該結點的level
調整指針指向

落盤：

TSDB 內存中的時序數據為行存儲，為了便于查詢和亂序數據的處理，內存中建立了一個 SkipList 作為內存索引：

TSDB 內存中的數據積累到一定量時，會觸發落盤。在落盤時，時序數據由行存儲形式轉化為列存儲形式，并維護 BRIN 索引，引入 LAST 文件和 SUB-BLOCK 機制處理文件碎片化。列存儲形式如下圖所示：

列式存儲：每一列都是一種數據類型，這樣就可以使用針對數據類型的壓縮方法將數據壓縮；一次磁盤定位順序讀取，加快查詢。

磁盤中數據組織形式：Block Range INdex

Block Range INdex：即數據塊范圍的索引，它的設計初衷是為了解決當數據表極其龐大時的迅速掃描問題。

BRIN索引是先排除不再范圍內的數據塊，一旦找到包含目標數據的數據塊范圍之后，采用位圖掃描獲取相應數據行。

TDengine：每個數據文件(.data 結尾)都有一個對應的索引文件（.head 結尾），該索引文件對每張表都有一數據塊的摘要信息，記錄了每個數據塊在數據文件中的偏移量，數據的起止時間等信息，以幫助系統迅速定位需要查找的數據

工作流程：

（1）master vnode 收到應用的數據插入請求，驗證OK，進入下一步；
（2）如果系統配置參數 walLevel 大于 0，vnode 將把該請求的原始數據包寫入數據庫日志文件 WAL。如果 walLevel 設置為 2，而且 fsync 設置為 0，TDengine 還將 WAL 數據立即落盤，以保證即使宕機，也能從數據庫日志文件中恢復數據，避免數據的丟失；
（3）如果有多個副本，vnode 將把數據包轉發給同一虛擬節點組內的 slave vnodes, 該轉發包帶有數據的版本號(version)；
（4）寫入內存，并將記錄加入到 skip list；
（5）master vnode 返回確認信息給應用，表示寫入成功。
（6）如果第 2、3、4 步中任何一步失敗，將直接返回錯誤給應用。

寫入與讀取示意圖：

（1）TSDB 啟動時會事先分配一個 BUFFER POOL 作為寫入緩沖（默認16 MB*6=96 MB），緩沖區塊大小和個數可配，區塊個數可修改。

（2）META 數據和時序數據從緩沖塊申請寫入空間，寫入引擎向 BUFFER POOL 申請緩沖區塊，寫滿的緩沖區塊占總緩沖區塊的1/3時觸發落盤操作。

（3）落盤時，緩沖區塊中的數據寫入到 META 等文件中，落盤結束后緩沖區塊歸還給 BUFFER POOL，形成循環機制。

（4）查詢時，對 MEM，IMEM 以及數據文件中的數據進行合并查詢。

業務使用設計：一個數據采集點（設備）一張表的策略

（1）由于不同數據采集點產生數據的過程完全獨立，每個數據采集點的數據源是唯一的，一張表也就只有一個寫入者，這樣就可采用無鎖方式來寫，寫入速度就能大幅提升。
（2）一個設備一張表，就保證了一張表插入的數據是有時序保證的（不同設備由于網絡的原因，到達服務器的時間無法控制，是完全亂序的），這樣數據插入操作就變成了一個簡單的追加操作，插入性能大幅度提高。
（3）一個數據采集點的數據是以塊為單位連續存儲的。如果讀取一個時間段的數據，它能大幅減少隨機讀取操作，成數量級的提升讀取和查詢速度。
（4）一個數據塊內部，采用列式存儲，對于不同數據類型，采用不同壓縮算法，而且由于一個數據采集點的采集量的變化是緩慢的，壓縮率更高。

數據分片設計：虛擬節點（vnode）

（1）為更好的支持數據分片、負載均衡，防止數據過熱或傾斜，數據節點被虛擬化成多個虛擬節點（vnode）。每個 vnode 都是一個相對獨立的工作單元，是時序數據存儲的基本單元，具有獨立的運行線程、內存空間與持久化存儲的路徑。一個 vnode 包含一定數量的表（數據采集點）。

（2）如何打散表到vnode中：以下3個參數決定

maxVgroupsPerDb: 每個數據庫中能夠使用的最大vnode個數（單個副本），默認為64；

minTablesPerVnode: 每個vnode中必須創建的最小表數，即是說這是第一輪建表用的步長（就是滿多少表寫下一個vnode），默認1000；

tablelncStepPerVnode：每個vnode中超過最小表數后的遞增步長（即是后續滿多少表寫下一個vnode），默認1000。

說明：在第一個vnode中，表數量從0開始逐漸遞增，隨著數量達到minTablesPerVnode后，開始創建下一個vnode并繼續在其中建表。之后，重復該過程直到vnode數量達到maxVgroupsPerDb。之后，TDengine將回到第一個vnode繼續創建新表，在補充每個vnode的表數達到tablelncStepPerVnode數量后，后續以tablelncStepPerVnode為步長繼續在vnode中依次創建表，直到建完全部表。