「ClickHouse系列」ClickHouse的優(yōu)化之Block+LSM
第一部分：
Block + LSM
其實本部分的標題也可以換成批處理+預(yù)排序。clickhouse通過block的設(shè)計來實現(xiàn)批處理，通過lsm算法來實現(xiàn)預(yù)排序。我們分別來分析一下，這個組合對查詢速度的影響。
首先，我們分析有序存儲和無序存儲對查詢速度的影響。我們一般在做查詢時，大致可以分為按值查詢和按范圍查詢兩種。
兩種查詢對的磁盤訪問
從表中可以看出，在都使用了索引的情況下，如果是按值查詢那么有序存儲和無序存儲基本都能做到一次磁盤IO就能實現(xiàn)數(shù)據(jù)讀取。但按范圍讀取，因為是有序存儲，因此只需要一次對磁盤的訪問即可讀取所有數(shù)據(jù)。而對于無序存儲的數(shù)據(jù)來說，最壞的情況可能需要讀取n次磁盤。
還是以一個小例子來做下說明:
SELECT?avg(price)?FROM?orders?where?age?between?20?and?30;
計算訂單中年齡在20到30歲用戶的平均訂單金額。假設(shè)數(shù)倉內(nèi)有1億條記錄，每條數(shù)據(jù)約1k，其中20-30歲之間的用戶訂單大約有10%。
在數(shù)據(jù)按照age有序存儲的情況下，讀取的數(shù)據(jù)量為1億*10%*1KB≈10G。
若數(shù)據(jù)未按照age有序存儲，這種情況下，讀取的數(shù)據(jù)量為1億*10%4K(1-27.1%)≈29.2G。兩者相差接近3倍。
由此可見，整體上來說，有序的數(shù)據(jù)在查詢時更占優(yōu)勢。因此，clickhouse在設(shè)計時使用了寫入前預(yù)排序，以保證查詢時能獲得更快的速度。不過這也必然帶來了數(shù)據(jù)寫入的延時，因此clickhouse不適合用在寫多讀少的場景。
說完了預(yù)排序，再來說下批處理對性能的影響。clickhouse能處理的最小單位是block，block就是一群行的集合，默認最大8192行組成一個block。
其實做了預(yù)排序后再做批處理很好理解，畢竟存儲到clickhouse中的數(shù)據(jù)都是有序的，而clickhouse設(shè)計出來是為了處理上百億條記錄的大數(shù)據(jù)數(shù)倉，因此一般的范圍查詢返回的數(shù)據(jù)量都非常大，如果每次處理1行數(shù)據(jù)的話，就會大大增加磁盤IO次的次數(shù)。當然，到目前為止，只是增加了IO次數(shù)，并沒有減少數(shù)據(jù)量，因此到此時，按照block讀取的優(yōu)化好像顯得沒有必要，畢竟一次IO的時間和讀取數(shù)據(jù)的時間相比，基本可以忽略不計。讀者們不用著急，真正block的省時的點就在下一段。
block真正發(fā)揮威力的點其實是在壓縮！對，沒錯，就是毫不起眼的壓縮！那么壓縮能節(jié)省多少數(shù)據(jù)量呢？我們還是拿clickhouse存儲引擎中實際存儲的數(shù)據(jù)說話。以clickhouse官方提供的hits_v1庫為例，我挑選了其中的UserID列為例，使用clickhouse提供的compressor工具讀取該列的數(shù)據(jù)文件，可以看到這個文件中每一個block的壓縮前和壓縮后的大小。
我大致看了一下，壓縮率最大的一個block壓縮前是130272字節(jié)，壓縮后只有639字節(jié)，壓縮率高達203倍！當然，這是特例，那我們統(tǒng)計下整個文件的block的壓縮前和壓縮后的大小，還是這個列為例，UserID列壓縮前是70991184字節(jié)，壓縮后是11596909字節(jié)，壓縮比約為6.2倍！
能達到這么高壓縮比，其實是列存的功勞，對于列存數(shù)據(jù)庫，由于每一列單獨存儲，因此每個數(shù)據(jù)文件相比行存數(shù)據(jù)庫來說更有規(guī)律，因此可以達到非常高的壓縮率。
到這里，批處理的威力就出來了，通過壓縮，再次降低了6倍的文件大小,也就是說再次減少6倍的磁盤IO時間。
這里就是clickhouse最重要的存儲引擎上的優(yōu)化，通過批處理+預(yù)排序，相比較于無此功能的列式數(shù)據(jù)庫來說，減少了范圍查詢量在10%左右時大約18倍的磁盤讀取時間。而若在百億數(shù)據(jù)庫中，查詢量1%左右時能節(jié)省24倍的磁盤讀取時間。
當然，任何架構(gòu)都有兩面性，在節(jié)省磁盤讀取時間的情況下，也帶來了如下缺點：
適合數(shù)據(jù)的大批量寫入，如果寫入頻繁，會影響寫入性能 如果范圍查詢的數(shù)據(jù)量大，那么性能提升會低。因此數(shù)據(jù)量太小時無法發(fā)揮最大優(yōu)勢。 由于按照block作為最小處理單位，因此刪除單條數(shù)據(jù)性能不高。 修改的性能很差，尤其是修改了用于排序的列。因此不適合做事務(wù)型數(shù)據(jù)庫。
附
可能有讀者會問，為什么無序存儲要乘以4K。這個原因是因為操作系統(tǒng)在讀取磁盤時，依據(jù)數(shù)據(jù)局部性原理，會按照頁為單位讀取，每頁的大小默認是4k。在unistd.h頭文件中的getpagesize()可以獲取本機的頁面大小，這里按照默認大小進行計算。
式子中的27.1%是指的緩存命中率，命中率由需要查詢的數(shù)據(jù)占所有數(shù)據(jù)的百分比r決定。在本例中按照4k的頁面大小和1k的記錄大小，命中率和數(shù)據(jù)占比之間的關(guān)系如下圖所示：
不難發(fā)現(xiàn)，兩者成負相關(guān)的相關(guān)性。
第二部分：
LSM算法最早出現(xiàn)在1991年的ACM期刊上，之后其思想在各大大數(shù)據(jù)存儲系統(tǒng)中被廣泛使用，例如LevelDB,HBase,Cassandra……LSM算法由于適應(yīng)的場景不同，存在很多的變體，clickhouse也使用lsm算來實現(xiàn)其預(yù)排序的功能，本部分將著重介紹clickhouse中的使用，同時也會適當涉及一些其他系統(tǒng)的使用用以讓讀者體會架構(gòu)設(shè)計的隨心所欲。
我們都知道，用戶在調(diào)用insert向clickhouse插入數(shù)據(jù)時，數(shù)據(jù)不一定是按已經(jīng)按照排序鍵排序好的數(shù)據(jù)，大概率是亂序數(shù)據(jù)。那么這種亂序的請求如何做到寫入磁盤時變得有序呢？這個就是LSM算法實現(xiàn)的。
LSM算法的幾個核心步驟：
在于數(shù)據(jù)寫入存儲系統(tǒng)前首先記錄日志，防止系統(tǒng)崩潰 記錄完日志后在內(nèi)存中以供使用，當內(nèi)存達到極限后寫入磁盤，記錄合并次數(shù)Level為0(L=0)。已經(jīng)寫入磁盤的文件不可變。 每過一段時間將磁盤上L和L+1的文件合并
我們用一個示例來展示下整個過程
T=0時刻，數(shù)據(jù)庫為空。
T=1時刻，clickhouse收到一條500條insert的插入請求，這500條數(shù)據(jù)時亂序的。此時，clickhouse開始插入操作。首先將500條插入請求一次性寫入日志。接著在內(nèi)存中進行排序，排序完成后將有序的結(jié)果寫入磁盤，此時L=0；
T=2時刻，clickhouse收到一條800條insert的插入請求，這800條數(shù)據(jù)時亂序的。此時，clickhouse開始插入操作。首先將800條插入請求一次性寫入日志。接著在內(nèi)存中進行排序，排序完成后將有序的結(jié)果寫入磁盤，此時L=0；
T=3時刻，clickhouse開始合并，此時此刻，磁盤上存在兩個L=0的文件。這兩個文件每個文件內(nèi)部有序，但可能存在重合。（例如第一批500條的范圍是300-400，第二批800條數(shù)據(jù)的范圍是350-700）。因此需要合并。clickhouse在后臺完成合并后，產(chǎn)生了一個新的L=1的文件。將兩個L=0的文件標記為刪除。
T=4時刻，clickhouse開始清理，將兩個被標記為刪除的文件真正地物理刪除。
T=5時刻，clickhouse收到一條100條insert的插入請求，這100條數(shù)據(jù)時亂序的。此時，clickhouse開始插入操作。首先將100條插入請求一次性寫入日志。接著在內(nèi)存中進行排序，排序完成后將有序的結(jié)果寫入磁盤，此時L=0；
T=6時刻，clickhouse開始合并，此時此刻，磁盤上存在1個L=0的文件和1個L=1的文件。這兩個文件每個文件內(nèi)部有序，但不存在重合。（例如L0文件的范圍是100-200，L1文件的范圍是300-700）。因此不需要合并。clickhouse在后臺將L=0的文件升級成L=1，此時數(shù)據(jù)庫內(nèi)存在兩個L=1的互不重合的文件。
……
以上就是LSM算法在clickhouse上的應(yīng)用，我們總結(jié)一下，clickhouse使用LSM算法將亂序的數(shù)據(jù)在內(nèi)存中排序為有序的數(shù)據(jù)，然后寫入磁盤保存，并且定期合并有重合的磁盤文件。
不難發(fā)現(xiàn)，上述所有的過程對于磁盤的來說都是順序?qū)?，因此這個也是LSM算法的一個特點——可以將大量的隨機寫入轉(zhuǎn)換為順序?qū)懭霃亩鴾p少磁盤IO時間。leveldb就借助了lsm的這個特性。當然，clickhouse并沒有使用到這個特性。下面會將簡單介紹下leveldb是如何使用LSM的。
clickhouse借助LSM實現(xiàn)了預(yù)排序的功能，提高了磁盤的利用率，但也同時帶來了一些犧牲。再次強調(diào)，沒有完美的架構(gòu)，當架構(gòu)解決一個問題的同時，一定會帶來一個全新的問題。
對于clickhouse也一樣，讀者們已經(jīng)知道了，clickhouse會在多次insert請求時創(chuàng)建獨立的數(shù)據(jù)文件。雖然clickhouse會在合適時間進行合并，但如果查詢發(fā)生在合并前，就有可能數(shù)據(jù)分布在兩個數(shù)據(jù)文件內(nèi)。此時clickhouse默認會返回兩個列表，這兩個列表內(nèi)部有序，但相互之間卻會有重合。這就給用戶使用帶來了不便，下圖展示了這種情況。
可以看出，此時clickhouse未合并時查詢結(jié)果分成了4個獨立的結(jié)果，每個結(jié)果內(nèi)部有序，但相互之間存在重合，也就說對于這種情況需要用戶自行合并。我們等待其合并后再次查詢，結(jié)果如下：
clickhouse合并后就能解決該問題。
LevelDB的用法
leveldb是一個允許修改的數(shù)據(jù)庫，因此其對于LSM的使用和clickhouse類似，主要的不同在于寫入日志后的操作不同。
clickhouse在記錄日志后，會直接在內(nèi)存中進行排序，從而寫入磁盤。此時如果clickhouse又接到一條寫入情況，會重新開啟一個新的進程。
而leveldb在記錄日志后，會將數(shù)據(jù)首先緩存在內(nèi)存中，等待后續(xù)操作繼續(xù)操作這塊內(nèi)存，直到這塊內(nèi)存被填滿，才會一次性將數(shù)據(jù)寫入磁盤。
這個差異主要時兩個數(shù)據(jù)庫面向的場景不同，clickhouse主要面向讀多寫少的分析場景，強調(diào)大批量一次性寫入增加吞吐量。而leveldb主要面向?qū)懚嘧x少的業(yè)務(wù)場景，強調(diào)低延時。
吞吐量和延時一向是互相對立的兩個指標，不同系統(tǒng)都在這兩個指標之間存在取舍。后續(xù)有機會我也會寫一篇關(guān)于這兩個指標之間的相愛相殺，以及知名開源軟件在這兩個指標之間的思考。
其他
扯回來，正因為面向的場景不同，clickhouse和leveldb對LSM的使用存在著不同。這也給了我們一個啟發(fā)，作為架構(gòu)師，我們要做到運用之妙存乎一心。要能夠了解我們正在設(shè)計的業(yè)務(wù)的需求是什么，然后進行符合需求的修改。而不是無腦地認為LSM一定是用在寫多讀少的場景。
做到這一點會有點難，但幸好我們可以站在前人肩膀上，多體會一下前人設(shè)計的精妙絕倫的架構(gòu)。有了這樣的經(jīng)驗和思考，我們在遇到相同問題的時候就能做到更深的思考。
這也是我寫這個系列的原因，clickhouse真的是工程師設(shè)計的典范之作，整個clickhouse沒有發(fā)明新的科學理論，但卻讓我們看到了借助已有的理論也能將性能在某一方面發(fā)揮到極致，這種追求極致的工程師精神讓我深深著迷，我覺得我需要將這種精妙的設(shè)計思想的傳遞給大家。希望有朝一日，我們中國的工程師也能將極致的產(chǎn)品帶給世界。因為有你，因為有我，許許多多平凡而偉大的工程師的共同努力，這一天一定能夠到來。向clickhouse的研發(fā)團隊致敬。
