今年，Spanner 終于發(fā)了另一篇 Paper Spanner: Becoming a SQL System，里面提到 Spanner 使用了一直新的存儲格式 - Ressi，用來支持 OLTP 和 OLAP。在 Ressi 里面，使用了 PAX 來組織數(shù)據(jù)。因為 TiDB 定位就是一個 HTAP 系統(tǒng)，所以我也一直在思考在 TiKV 這層如何更好的存儲數(shù)據(jù)，用來滿足 HTAP 的需要，既然 Spanner 使用了 PAX，那么就有研究的必要了。
PAX 的論文可以看看 Weaving Relations for Cache Performance 或者 Data Page Layouts for Relational Databases on Deep Memory Hierarchies。
NSM and DSM
在談 PAX 之前，NSM 和 DSM 還是繞不開的話題，NSM 就是通常說的行存，對于現(xiàn)階段很多偏重 OLTP 的數(shù)據(jù)，譬如 MySQL 等，都采用的這種方式存儲的數(shù)據(jù)。而 DSM，則是通常的說的列存，幾乎所有的 OLAP 系統(tǒng)，都采用的這種方式來存儲的底層數(shù)據(jù)。
NSM 會將 record 依次在磁盤 page 里面存放，每個 page 的末尾會存放 record 的 offset，便于快速的定位到實際的 record。如果我們每次需要得到一行 record，或者 scan 所有 records，這種格式非常的高效。但如果我們的查詢，僅僅是要拿到 record 里面的一列數(shù)據(jù)，譬如 select name from R where age < 40，那么對于每次 age 的遍歷，除了會將無用的其他數(shù)據(jù)一起讀入，每次讀取 record，都可能會引起 cache miss。
不同于 NSM，DSM 將數(shù)據(jù)按照不同的 attributes 分別存放到不同的 page 里面。對于上面只需要單獨根據(jù)某一個 attribute 進行查詢的情況，我們會直接讀出page，遍歷處理，這個對 cache 也是非常高效友好的。
但是，如果一個查詢會涉及到多個不同的 attributes，那么我們就可能需要多次 IO 來組合最終的 tuple。同時，對于寫入，DSM 因為會將不同的 attributes 對應的數(shù)據(jù)寫到不同的 page，也會造成較多的隨機 IO。
PAX
可以看到，NSM 和 DSM 都有各自的優(yōu)劣，所以如何將它們和優(yōu)點結合起來，就是現(xiàn)在很多 hybrid storage 包括 PAX 考慮的問題。
PAX 全稱是 Partition Attributes Across，它在 page 里面使用了一種 mini page 的方式，將 record 切到到不同的 mini page 里面。
假設有 n 個 attributes，PAX 就會將 page 分成 n 個 mini pages，然后將第一個 attribute 的放在第一個 mini page 上面，第二個放在第二個 mini page，以此類推。
在每個 page 的開頭，會存放每個 mini page 的 offset，mini page 對于 Fixed-length attribute 的數(shù)據(jù)，會使用 F-minipage ，而對于 variable-length attribute 的數(shù)據(jù)，則會使用 V-minipage。對于 F-minipage 來說，最后會有一個 bit vector 來存放 null value。而對于 V-minipage 來說，最后會保存每個每個 value 的在 mini page 里面的 offset。
可以看到，PAX 的格式其實是 NSM 和 DSM 的一種折中，當要依據(jù)某一列進行 scan 的時候，我們可以方便的在 mini page 里面順序掃描，充分利用 cache。而對于需要訪問多 attributes 得到最終 tuple 的時候，我們也僅僅是需要在同一個 page 里面的 mini page 之間讀取相關的數(shù)據(jù)。
Data Manipulation
Insert
當數(shù)據(jù)插入的時候，PAX 會首先生成一個新的 page，然后根據(jù) attribute 的 value size 分配好不同的 mini page， 這里需要注意下 variable-length value，因為它們的長度是不固定的，PAX 會使用一些 hint 來得到一個平均的 size。插入一個 record 的時候，PAX 會將這個 record 里面的數(shù)據(jù)分別 copy 到不同的 mini page 上面。如果一個 record 還能插入到這個 page，但這個 record 里面某一個 attribute 的數(shù)據(jù)不能插入到對應的 mini page 了，PAX 會重新調整不同 mini page 的 boundary。如果一個 page 已經 full 了，那么 PAX 就會重新分配一個 page。
Update
當數(shù)據(jù)更新的時候，PAX 會首先計算這個 record 需要更新的 attributes 在不同 mini page 里面的 offset，對于 variable-length value 來說，如果更新的數(shù)據(jù)大小超出了 mini page 可用空間，mini page 就會嘗試向周圍的 mini page 借一點空間。如果鄰居也沒有額外的空間了，那么這個 record 就會被移到新的 page 上面。
Delete
當數(shù)據(jù)刪除的時候，PAX 會在 page 最開始會維護一個 bitmap，用來標記刪除的數(shù)據(jù)。當刪除標記越來越多的時候，就可能會影響性能，因為會導致 mini page 里面出現(xiàn)很多 gap，并不能高效的利用 cache。所以 PAX 會定期去對文件重新組織。
小結
PAX 其實是一個原理比較簡單的東西，但它并沒有成為一個業(yè)界主流的存儲方案，應該有一些局限是我現(xiàn)在還不知道的。但既然 Spanner 敢用，證明在 HTAP 領域，PAX 也是一個可選擇的方案，對我們后續(xù) HTAP storage 的技術選型也有一定的指導作用。這里也就先記錄一下，也希望能跟這方面有經驗的同學多多交流下心得體會。
