HTAP與時(shí)俱進(jìn)

在線聯(lián)機(jī)事務(wù)處理（OLTP）和在線聯(lián)機(jī)分析處理（OLAP）這兩類數(shù)據(jù)處理分析場(chǎng)景，是公司日常工作中不可不說(shuō)的內(nèi)容，尤其是在大數(shù)據(jù)時(shí)代的當(dāng)下，說(shuō)它們決定了公司的成敗也不為過(guò)，因此誕生了各類成熟且高效地分布式計(jì)算、存儲(chǔ)系統(tǒng)，如計(jì)算側(cè)的MapReduce、Spark、Flink、Trino等，存儲(chǔ)側(cè)的Oracle、RocksDB、Clickhouse等。

但正是各類計(jì)算和存儲(chǔ)系統(tǒng)的遍地開(kāi)花，也導(dǎo)致了在實(shí)際中很難將不同的系統(tǒng)歸一、數(shù)據(jù)統(tǒng)一，導(dǎo)致各類負(fù)擔(dān)，尤其是流系統(tǒng)、批系統(tǒng)的天然隔閡，因此近年來(lái)大家都是力求找到或開(kāi)發(fā)出一個(gè)系統(tǒng)，能夠同時(shí)很好應(yīng)付日常工作中的絕大部分OLTP/OLAP的業(yè)務(wù)就行了，就像Snowflake那樣，實(shí)現(xiàn)一個(gè)相對(duì)完善的HTAP系統(tǒng)。

但要想做好一個(gè)HTAP系統(tǒng)，不可避免地需要要結(jié)合計(jì)算、存儲(chǔ)這兩個(gè)層面的特性來(lái)進(jìn)行設(shè)計(jì)，雖然我們?cè)趯?shí)際的工作中經(jīng)常強(qiáng)調(diào)要存算分離，保證集群系統(tǒng)能夠至少滿足BASE（Basically Available、Soft States、Eventually Consistent原則，也可以說(shuō)是AP原則吧）原則，但這僅僅是強(qiáng)調(diào)使用上的注意事項(xiàng)，而要實(shí)現(xiàn)這樣的系統(tǒng)，卻不能分開(kāi)計(jì)算而談存儲(chǔ)，反之亦然。

人都是“貪婪”的，一旦有了開(kāi)發(fā)了一個(gè)工具，不管是使用者還是開(kāi)發(fā)者，都希望隨著技術(shù)的進(jìn)步，這個(gè)工具能夠變得更好，比如說(shuō)時(shí)間，為別人/自己節(jié)省了多少時(shí)間，實(shí)時(shí)性達(dá)到秒級(jí)等，說(shuō)到這里，這篇博客也就隨著這篇論文Real-Time LSM-Trees for HTAP Workloads來(lái)看看學(xué)習(xí)和思考前人的成果，以幫助解決當(dāng)下或未來(lái)的問(wèn)題。

LASER中的存儲(chǔ)

關(guān)鍵知識(shí)

LSM（Log-Structured Merge Tree）

很多文章都介紹這個(gè)概念了，大家可以自行查找一下，當(dāng)然也有不少系統(tǒng)基于此原理實(shí)現(xiàn)了自己的存儲(chǔ)，如Google LevelDB、Clickhouse、Flink Table Store等。

SkipList（跳表）

這個(gè)概念也有不少的大佬分析了其理論與實(shí)踐，例如Redis中的應(yīng)用，還有Real-Time LSM-Trees for HTAP Workloads論文中的提到的LASER系統(tǒng)。

CDC（Changed Data Capture）

實(shí)際上對(duì)應(yīng)了數(shù)據(jù)庫(kù)中的INSERT、DELETE、UPDATE操作，更細(xì)節(jié)知識(shí)自行查閱吧。

SST（Sorted Sequence Table）

可以認(rèn)為就是持久化到磁盤上的數(shù)據(jù)文件，文件中的數(shù)據(jù)行都是按排序KEY有序的。

特性

列組（Column Group）

為了兼并行存和列存的優(yōu)勢(shì)，LASER在不同的存儲(chǔ)等級(jí)（LEVEL）上定義不了同列組規(guī)則，一個(gè)列組就是一個(gè)數(shù)據(jù)行中的部分或全部字段，對(duì)應(yīng)一個(gè)單獨(dú)的存儲(chǔ)文件，例如在下面的圖中顯示的，在Level 0層，文件是按行存儲(chǔ)的，文件中的一行就對(duì)應(yīng)了一條完整的Record；而在Leve 1層，會(huì)存儲(chǔ)兩個(gè)文件，分別保存(A, B)列以及(C, D)列；在Level 3層，一個(gè)列，就是一個(gè)單獨(dú)的文件。（這里說(shuō)一個(gè)文件并不準(zhǔn)確，實(shí)際上應(yīng)該是一類文件，畢竟文件一般會(huì)按大小被切分成多個(gè)）

圖-1 列組的定義與組織

部分列更新

LASER存儲(chǔ)的實(shí)現(xiàn)

數(shù)據(jù)插入流程

下圖展示了LASER中的基本存儲(chǔ)流程，圖中也展示了一些配套的索引技術(shù)，如BLOOM FILTERS用于加速文件的查找、SkipList查找新記錄的待插入位置。

一條新數(shù)據(jù)記錄（Record）完整地經(jīng)歷CDC過(guò)程的簡(jiǎn)單描述如下：

1. 決定Record的操作類型：Server接收到Record后，根據(jù)指定的排序Key、唯一Key，在內(nèi)存中的SKIPLIST以及磁盤中的LEVEL文件（這里指SST文件）查找，看是否存在相同的數(shù)據(jù)記錄。如果存在則更新這條RECORD的操作類型為UPDATE，否則為INSERT。
2. 插入到內(nèi)存中的MUTABLE SKIPLIT：通過(guò)跳表可以很快地確認(rèn)這條新的數(shù)據(jù)記錄的插入位置，因此就將其插入到內(nèi)存。
3. Flush到磁盤：如果新的數(shù)據(jù)記錄插入后，到達(dá)了一定的閾值，則系統(tǒng)會(huì)嘗試將MUTABLE的數(shù)據(jù)刷新到磁盤，但在Flush之前，需要將新記錄插入的內(nèi)存數(shù)據(jù)表標(biāo)記為IMMUTABLE，以保證數(shù)據(jù)寫出時(shí)，不會(huì)發(fā)生 變更。
4. 寫出數(shù)據(jù)到Level0：Level 0只定義了一個(gè)文件，因此會(huì)首先嘗試將新的RECORD，按行格式，插入到此文件中。
5. Compaction數(shù)據(jù)文件：如果新的RECORD插入Level 0后，導(dǎo)致文件的大小超過(guò)了閾值，則會(huì)觸發(fā)Compaction行為，將Level 0的文件，下沉到更下層，達(dá)到優(yōu)化存儲(chǔ)的目的，因此這里會(huì)首先將Level 0的文件，轉(zhuǎn)存到Level 1。文件由Level 0插入到Level 1的過(guò)程，實(shí)際上是一個(gè)歸并排序的過(guò)程，需要保證文件的有序性，因此這里可以采用二分查找來(lái)確認(rèn)需要合并Level 1中的哪些文件，例如Level 0文件的SORT KEY值范圍為[22, 66]，那么需要與Level 1中的21-50和51-88的兩個(gè)SST文件進(jìn)行合并。
6. 列組映射：上面的圖只顯示了文件的插入過(guò)程，但沒(méi)有展示出列出的合并邏輯，這里簡(jiǎn)單說(shuō)一下：

從圖-1可以知道每一個(gè)Level的列組劃分是不同的，而Level 0中的文件中的一行可能包含了所有列值（如A、B、C、D四個(gè)列），而在Level 1中數(shù)據(jù)文件只有兩類(A, B）和（C, D），因此需要將0層的文件中的數(shù)據(jù)行按列拆分成兩個(gè)文件，分別以前兩個(gè)列為一行和后兩個(gè)列為一行，再分別進(jìn)行合并，最終生成兩類文件。

部分列更新流程

一般地，SQL中的UPDATE語(yǔ)句會(huì)更新部分列的歷史值，因此LASER也需要有能力支持。

初始化LEVELs

Level 0：數(shù)據(jù)文件行式存儲(chǔ)，因此文件中的一行，包含了全部列，A、B、C、D。
Level 1: 兩個(gè)文件，即兩人上Column Group，左邊文件包含A、B列；右邊文件包含C、D列
注意到每一行記錄之前有一個(gè)特殊的整數(shù)，例如106: a6, b6, c6, d6中的106，表示的是數(shù)據(jù)記錄排序鍵對(duì)應(yīng)的值，可以看到在每一個(gè)文件中，所有的數(shù)據(jù)記錄都是按此值有序。

插入一條新記錄并更新一條舊記錄（合并L0和L1）

插入一條新記錄：99: a9, b9, c9, d9
更新一條舊記錄：107: -, -, c9, d9，其中-表示不更新，即保留A, B列的原有值
注意到，這里插入新記錄后，導(dǎo)致LEVEL 0超過(guò)存儲(chǔ)閾值，因此會(huì)觸發(fā)L0的文件下沉到L1，因此下面的圖展示的是合并后的結(jié)果。
在合并L0和L1的過(guò)程中，可以看到，原本在L0的行文件中的記錄106: a6, b6, c6, d6，下沉到L1后，被縱向拆分到了兩個(gè)Column Group文件中；而新的更新記錄107: -, -, c9, d9最終只會(huì)在CG：<C, D>有值，而不會(huì)添加記錄107: -, -到CG：<A, B>中，節(jié)約了存儲(chǔ)空間。

插入一條新記錄并更新一條舊記錄（不合并）

插入一條新記錄：50: a0, b0, c0, d0
更新一條舊記錄：108: a1, b1, -, -，其中-表示不更新，即保留C, D列的原有值
可以看到由于新插入的數(shù)據(jù)后，被首先Flush到Level 0，但Level 0的數(shù)據(jù)大小沒(méi)有達(dá)到閾值，因此不會(huì)發(fā)生Compaction，新的數(shù)據(jù)就以行格式保留在L0中。

范圍查詢

ColumnMergingIterators：用于合并ColumnGroup，一個(gè)Iterator實(shí)例只會(huì)作用于同一個(gè)Level，因此不會(huì)真正的合并新舊數(shù)據(jù)，而是將要所有要檢索的列（這里是A、B、C、D列）拼接在一起。
LevelMergingIterators：用于合并來(lái)自不同Level的數(shù)據(jù)，這些數(shù)據(jù)經(jīng)過(guò)ColumnMergingIterators后返回了一個(gè)"臨時(shí)表"，包含了所有要檢索的列，同時(shí)會(huì)進(jìn)行新、舊列值的覆蓋。

查詢流程簡(jiǎn)述如下：

1. SQL解析：接收SELECT * FROM tbl WHERE sort_key >= 50 and sort_key <= 108，產(chǎn)生要返回的結(jié)果列的投影信息，即返回A、B、C、D。
2. 確認(rèn)數(shù)據(jù)所有層級(jí)：發(fā)現(xiàn)sort_key的取值范圍是[50, 108]，在3個(gè)Level中都存在數(shù)據(jù)，因此需要遍歷每一層的數(shù)據(jù)文件。
3. 遍歷每一層的數(shù)據(jù)文件：為每一個(gè)LEVEL創(chuàng)建ColumnMergingIterators實(shí)例，遍歷滿足條件的數(shù)據(jù)文件，返回的結(jié)果是一個(gè)臨時(shí)表且它們的Layout相同，均為A、B、C、D，例如對(duì)于sort_key = 107的數(shù)據(jù)記錄，通過(guò)列拼接，最終得到在臨時(shí)表中的對(duì)應(yīng)行107: -, -, c9, d9。
4. 合并每一層的臨時(shí)表：通過(guò)LevelMergingIterators實(shí)例，合并每一層的返回結(jié)果，同時(shí)進(jìn)行數(shù)據(jù)記錄的更新/刪除動(dòng)作，例如對(duì)于sort_key = 107的數(shù)據(jù)記錄，發(fā)現(xiàn)它的舊值為107: a7, b7, c7, d7，新值為107: -, -, c9, d9，因此通過(guò)覆蓋后的最終結(jié)果為107: a7, b7, c9, d9。
5. 返回最終結(jié)果：最終結(jié)果集包含了所有要檢索的列，以及包含了舊記錄中的列的最新值。

部分列的Compaction

通過(guò)后臺(tái)的Compaction線程，可以并行地在不同的ColumnGroup上進(jìn)行Compaction，因?yàn)樵?code>數(shù)據(jù)下沉的過(guò)程中，越往向，列組越小，并且互相不影響。

如下圖所示，當(dāng)前一共有兩個(gè)Compaction任務(wù)在執(zhí)行，第一個(gè)任務(wù)是合并L1和L2中的CG：<A, B>；第二個(gè)任務(wù)是合并L2和L3中的CG: <C>。

但這里有一個(gè)潛在的問(wèn)題：為什么選擇L1中的<A, B>下沉，以及L2中的<C>下沉？

簡(jiǎn)單來(lái)說(shuō)，LASER為每一個(gè)Level配置了不同的Quota，例如為L(zhǎng)1配置了上限記錄數(shù)為2，而當(dāng)前L1中一共存在3條記錄，因此需要合并L1和L2；同時(shí)注意到CG: <A, B> 的占比最多，因此優(yōu)先選擇此CG下沉，故就對(duì)應(yīng)了任務(wù)1，同理生成任務(wù)2。

最終，經(jīng)過(guò)部分列上的下沉，可以避免對(duì)它列的影響，在一定程度上能夠減緩由于數(shù)據(jù)下沉，導(dǎo)致在這些列上的檢索時(shí)間變長(zhǎng)的問(wèn)題，當(dāng)然也可以結(jié)合一些冷熱策略可以更精細(xì)地控制正常過(guò)程。

LASER存儲(chǔ)的性能

rocksdb：行存
rocksdb-col：列存
HTAP-simple：行、列混合存儲(chǔ)，25%數(shù)據(jù)行存，其它列存。
Postgress：行存
MySQL：行存
MyRocks：行存
MonetDB：列存
Hyper：全內(nèi)存列存

整體性能

如下圖所示，在同時(shí)進(jìn)行INSERT、UPDATE、SELECT操作時(shí)，LASER的整體性能是最好的，尤其是在設(shè)置了ColumnGroup的大小為6（6列）、15（15列）的場(chǎng)景下，而次強(qiáng)的則是HTAP-simple和rocksdb-col（它們完全是基于內(nèi)存的）。

插入性能

如下圖所示，當(dāng)僅執(zhí)行INSERT操作時(shí)，LASER表現(xiàn)最好，尤其是設(shè)置CG的大小為2和3時(shí)，而HTAP-simple和rocksdb將之。

檢索性能

??1: INSERT INTO R VALUES (??0, ??1, …, ???? )
??2: SELECT ??1, ??2, …, ???? FROM R WHERE ??0 = ??
??3: UPDATE R SET ??1 = ??1, …, ???? = ???? WHERE ??0 = ??
??4: SELECT ??1 + ??2 + … + ???? FROM R WHERE ??0 ∈ [???? , ???? )
??5: SELECT ?????? (??1), …, ?????? (????) FROM RWHERE??0 ∈ [???? , ???? )

如下圖所示，分別執(zhí)行不同Query時(shí)的延遲統(tǒng)計(jì)圖，從中可以看到當(dāng)前執(zhí)行Q1、Q2、Q3時(shí)，LASER能夠達(dá)到其它優(yōu)勢(shì)引擎的最好性能；而執(zhí)行Q4的算術(shù)運(yùn)算時(shí)，Hyper表現(xiàn)最好，比LASER快5倍（而MonetDB比LASER慢20倍）；而執(zhí)行Q5的聚合運(yùn)算時(shí)，MonetDB和Hyper比LASER快5倍，這是由于Hyper和Monet存儲(chǔ)的數(shù)據(jù)記錄都是按列連續(xù)的，因此不需要像LASER那樣需要先合并數(shù)據(jù)。

因此整體上看，在高負(fù)載，和能用場(chǎng)景下，LASER的表是所有列式引擎、行式引擎中綜合表現(xiàn)最好的，也更加活動(dòng)地通過(guò)CG的大小來(lái)適配不再的場(chǎng)景。

LASER存儲(chǔ)的問(wèn)題

下面提到的這些問(wèn)題，都是論文中有提到的，同時(shí)也給出了估算公式，但是著實(shí)需要細(xì)致分析每一個(gè)算法才能更好地理解架構(gòu)設(shè)計(jì)的精妙，這里就不展開(kāi)分析了，也怕功力不夠，引發(fā)解讀錯(cuò)誤，那就栽了?。?！

寫放大

不難想象，當(dāng)我們更新更新或插入數(shù)據(jù)時(shí)，至少需要讀取索引數(shù)據(jù)、舊的的數(shù)據(jù)記錄，以確定當(dāng)前數(shù)據(jù)行的操作類型；當(dāng)發(fā)生數(shù)據(jù)合并（Compaction過(guò)程）時(shí)，需要將新舊數(shù)據(jù)寫出到一個(gè)新的數(shù)據(jù)文件，同時(shí)保證舊的數(shù)據(jù)文件依然在此期間可以為查詢作業(yè)提供服務(wù)，因此這么大的倍數(shù)與寫入或更新的數(shù)據(jù)模型有關(guān)。

為了緩解此問(wèn)題，可以基于ColumnGroup機(jī)制，同時(shí)為每一個(gè)Level制定不同的數(shù)據(jù)下沉策略。

點(diǎn)查放大

僅僅是等值查詢，最壞情況下，需要在內(nèi)存遍歷，同時(shí)需要檢查所有Level中的數(shù)據(jù)范圍，以確定數(shù)據(jù)是否存在。

范圍查詢放大

比點(diǎn)查更壞，最壞情況下，要查詢的數(shù)據(jù)在每一個(gè)Level中都存在，因此遍歷記錄每一層的數(shù)據(jù)文件的信息，來(lái)確定要讀取的數(shù)據(jù)。

更新放大

在點(diǎn)查放大問(wèn)題的基礎(chǔ)之上，需要將新數(shù)據(jù)寫出到Level 0，同時(shí)很可能會(huì)引發(fā)Compcation過(guò)程。

總結(jié)

Real-Time LSM-Trees for HTAP Workloads介紹了一個(gè)支持實(shí)現(xiàn)寫入的、基于LSM的、支持HTAP場(chǎng)景的存儲(chǔ)系統(tǒng)，LASER。論文提出了ColumnGroup存儲(chǔ)規(guī)范，能在兼并行存、列存的優(yōu)點(diǎn)，以相對(duì)最好的性能同時(shí)支持OLTP和OLAP事務(wù)，為打造流批一體計(jì)算&存儲(chǔ)系統(tǒng)提供了借鑒，非學(xué)值得我們細(xì)細(xì)口味。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-809982.html

思考

1. 使用什么的索引或算法，能夠快速定位范圍所包含的數(shù)據(jù)文件？
2. 時(shí)間旅行？
3. 并發(fā)寫事務(wù)的支持？
4. 如何支持插入入新的列？
5. 。。。

到了這里，關(guān)于HTAP（Hybrid Transactional/Analytical Processing）系統(tǒng)之統(tǒng)一存儲(chǔ)的實(shí)時(shí)之道的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！