2017-09-13 雷鵬 Terark實(shí)驗(yàn)室

?

1.

背景

WiredTiger 是 KeyValue 存儲引擎,它最大的應(yīng)用場景是作為 MongoDB 的默認(rèn)存儲引擎,同時(shí) MongoDB 對 WiredTiger 性能改進(jìn)的探索也從未停止,于是,TerarkDB 以卓越的性能和壓縮率而獲得了 MongoDB 的興趣……

鑒于 TerarkDB 是 Terark 核心算法對 RocksDB 的適配,理論上相同的算法也可以用于 WiredTiger,我們經(jīng)過一段時(shí)間的緊密開發(fā),實(shí)現(xiàn)了第一個(gè)測試版本,期間 WiredTiger 的作者提供了大力的支持,在這里我們跟大家分享一下開發(fā)的經(jīng)歷與成果.

2.

WiredTiger 和 LSM

WiredTiger 本身支持 BTree 和 LSM ( Log-Structured Merge Trees ) 兩種數(shù)據(jù)結(jié)構(gòu)進(jìn)行數(shù)據(jù)存儲,用戶通常可以根據(jù)自己的需求進(jìn)行選擇.

2.1. BTree

BTree 讀性能優(yōu)良.但是在寫壓力較大的情況下,性能會下降的較為嚴(yán)重：

BTree 的寫放大很嚴(yán)重：很少量的寫就會引起整頁被重新寫入磁盤,假定一個(gè)頁包含 200 條記錄,其中有 2 條被修改,當(dāng)該頁被換出時(shí),就需要將整個(gè)頁都寫入磁盤/SSD,象這樣 2 條數(shù)據(jù)修改導(dǎo)致 200 條數(shù)據(jù)被寫入磁盤,其寫放大就是 100 倍.

這在 SSD 上導(dǎo)致了更加嚴(yán)重的后果：因?yàn)?SSD 的壽命取決于寫次數(shù),頻繁寫入會大幅降低 SSD 的壽命.

2.2. Log-Structured Merge Trees

LSM 是一個(gè)針對寫而進(jìn)行了優(yōu)化的數(shù)據(jù)結(jié)構(gòu),一個(gè) LSM 在物理層面由多個(gè)子片段組成,其中最近被更新的那個(gè)片段存在于內(nèi)存中,其余的以文件的方式存儲在磁盤中,當(dāng)內(nèi)存片段達(dá)到閾值時(shí)會被持久化成文件,同時(shí)產(chǎn)生一個(gè)新的內(nèi)存片段用于寫操作.

這里,通過將所有的寫操作以追加的方式寫到內(nèi)存中,就規(guī)避了 BTree 中出現(xiàn)的寫一條數(shù)據(jù)往往需要先讀磁盤,然后修改,然后再寫回磁盤的弊端.只需要在達(dá)到閾值時(shí)一次性的 flush 即可.

當(dāng)然,LSM 也有它自己的弊端,寫的優(yōu)化伴隨著讀性能的下降.簡單追加寫的方式意味著子片段之間可能會有數(shù)據(jù)的重疊,查詢也就往往需要讀取多個(gè)子片段才能返回有效的結(jié)果.LSM 通過后臺線程對已有數(shù)據(jù)進(jìn)行 compact 來解決(緩解)這個(gè)問題.

3.

WiredTiger 接口層

WiredTiger 提供了一套回調(diào)接口以方便用戶按照自己的需求去定制底層的數(shù)據(jù)存取.例如,LSM 的每一個(gè)子文件,數(shù)據(jù)是按照 BTree 的方式進(jìn)行存取的.熟悉 LevelDB / RocksDB 的同學(xué)可以通過回調(diào)實(shí)現(xiàn)一份以 Block Based 為組成文件的 LSM,和 原生的 BTree 比較一下性能.

WiredTiger 的回調(diào)接口如下：

static WT_DATA_SOURCE my_dsrc = {

alter,

create,

compact,

drop,

open_cursor, // *

rename,

salvage,

truncate,

range_truncate,

verify,

checkpoint,

terminate

};

error_check(conn->add_data_source(conn, "dsrc:", &my_dsrc, NULL));

回調(diào)里包含了創(chuàng)建、刪除、重命名、停止等函數(shù).這里需要注意標(biāo) * 的 open_cursor 回調(diào),用戶程序?qū)?wt 的訪問,是統(tǒng)一經(jīng)由抽象的 cursor 來實(shí)現(xiàn)的.

WiredTiger 的內(nèi)部也遍布了 cursor 的調(diào)用,所以要重載數(shù)據(jù)存儲實(shí)現(xiàn),cursor 相關(guān)的操作也不可避免：

WT_CURSOR::close

WT_CURSOR::next

WT_CURSOR::prev

WT_CURSOR::reset

WT_CURSOR::search

WT_CURSOR::search_near

WT_CURSOR::insert

WT_CURSOR::update

WT_CURSOR::remove

4.

將 Terark 算法集成進(jìn) WiredTiger

基于上面的理由,我們?yōu)?LSM 實(shí)現(xiàn)了一個(gè) TerarkZipTable 數(shù)據(jù)源,把我們的可檢索壓縮算法嵌入到 WiredTiger 中.

4.1. LSM-Chunk

LSM-chunk (在WiredTiger語境里,LSM-file 以 chunk 來指代)或者是由內(nèi)存數(shù)據(jù)轉(zhuǎn)化而成,或者是由若干個(gè) chunk 通過 compact 生成.無論哪種方式,遍歷源數(shù)據(jù)都是必不可少的.為了實(shí)現(xiàn)高壓縮率和可檢索壓縮,Terark-chunk 需要遍歷源數(shù)據(jù)二次,對比原生的 LSM-chunk 只需要遍歷一次.這里的差異,可以簡單理解為Terark需要第一遍收集全局信息,為壓縮做準(zhǔn)備,第二遍執(zhí)行壓縮.

4.2. 重載粒度

需要強(qiáng)調(diào)的是,WiredTiger 的數(shù)據(jù)源含義較為寬泛,它可以是 LSM,也可以是組成 LSM 的子文件即 LSM-chunk.

我們這里重載的,是 LSM-chunk,涉及到 LSM 層面的 Merge , Checkpoint 是未受影響的.

4.3. 來自 WiredTiger 官方的協(xié)助

在整個(gè)修改過程中,WiredTiger 本身也有一些需要調(diào)整和修改的地方,為此 WiredTiger 在一個(gè)新分支上與我們進(jìn)行協(xié)作：

1. 為了支持兩次遍歷,WiredTiger 為我們提供了一個(gè)額外的接口；

2. LSM-chunk 默認(rèn)是以 BTree 方式實(shí)現(xiàn)的并在幾處代碼內(nèi)寫死了,新分支已經(jīng)修復(fù)；

3. WiredTiger 內(nèi)部是按照名稱前綴來判斷數(shù)據(jù)類型的,LSM-chunk 對應(yīng)的前綴是 BTree 通用的 file:,不巧有幾處也寫死了,新分支已修復(fù)；

4. LSM-chunk 默認(rèn)需要生成 Bloom Filter 文件以提高查找效率,而 Terark 并不需要該文件,新分支目前正在修改,但不影響我們的測試；

5. 為了保證 Transaction 相關(guān)操作不受影響,WiredTiger 內(nèi)存駐留的 LSM-chunk 仍然以 BTree 方式存在,其他的 chunk 可以通過重載 data-source 來實(shí)現(xiàn),新分支已改；

6. 經(jīng)過我們的提議,WiredTiger 新增了一個(gè) cursor 選項(xiàng)(unpositioned),該選項(xiàng)指示 CURSOR::search 不要保留 cursor 位置

1)之前 WiredTiger 的 CURSOR::search 在搜索成功時(shí)總會保留 cursor 的位置；

2)而維護(hù) cursor 位置的搜索已由接口 CURSOR::search_near 提供完美支持；

3)對于 TerarkZipTable,保留 cursor 位置是一筆不小的開銷

無 unpositioned 選項(xiàng)時(shí),TerarkZipTable 通過投機(jī)方法來減小這種開銷；

有 unpositioned 選項(xiàng)時(shí),就可以完全避免這種不必要的開銷.

4.4. TerarkDB 不需要 Bloom Filter

Bloom Filter 用來做否定測試,也就是說,如果 Bloom Filter 搜索 Key 失敗,則該 Key 一定不存在,如果 Bloom Filter 搜索成功,該 Key 可能存在,也可能不存在.

Bloom Filter 的優(yōu)點(diǎn)是占用空間很小(一般情況下平均每個(gè) Key 1~2 字節(jié)),搜索速度又很快,當(dāng)然缺點(diǎn)就是它只能確認(rèn) Key 不存在.

傳統(tǒng) SST 使用 Bloom Filter 來加速高層 Level 中 SST 的搜索.

高層(Level 值更小的 Level)的數(shù)據(jù)尺寸更小,并且都是新數(shù)據(jù),訪問更頻繁,未命中的概率更高,而傳統(tǒng)索引搜索速度較慢,內(nèi)存占用高,所以,用 Bloom Filter 可以實(shí)現(xiàn)很好的加速效果,并且相對內(nèi)存占用較低.

然而,Terark SST 用了 CO-Index,CO-Index 的壓縮率和性能都非常高,和 Bloom Filter 相比,甚至在很多情況下空間和搜索性能同時(shí)占優(yōu),而且還是確定性的搜索(存在就是存在,不存在就是不存在),所以 Terark SST 就完全舍棄了 Bloom Filter.

4.5. 實(shí)現(xiàn)接口

WT_DATA_SOURCE

trk_create

trk_drop

trk_open_cursor

trk_pre_merge // *

這里的 trk_pre_merge 是 WiredTiger 官方提供的新的接口,用來供 Terark 實(shí)現(xiàn)兩次遍歷.

WT_CURSOR @ building

trk_builder_cursor_insert

trk_builder_cursor_close

trk_builder_cursor_reset

WT_CURSOR @ reading

trk_reader_cursor_next

trk_reader_cursor_prev

trk_reader_cursor_search

trk_reader_cursor_search_near

trk_reader_cursor_close

trk_reader_cursor_reset

上面的接口顯示,每個(gè) chunk 按功用可以劃分為兩個(gè)階段：構(gòu)建和查詢.

構(gòu)建階段的 chunk 不需要提供 search 相關(guān)的功能,此時(shí)對應(yīng)的回調(diào)可以設(shè)置為 NULL；同理,一旦 chunk 構(gòu)建完畢,它就是 immutable 的,不需要考慮 insert 相關(guān)的操作.所以這里的 cursor 按照 chunk 的生命期拆分為兩組.

需要留心的有以下幾點(diǎn)：

初始化的 cursor 可以立即調(diào)用 next(),此時(shí)是從頭開始正向遍歷；

初始化的 cursor 可以立即調(diào)用 prev() ,此時(shí)是從尾開始反向遍歷；

search()對應(yīng)的是精確查找,search_near()對應(yīng)的是類 lower_bound() 的查找；

5.

初步的集成測試結(jié)果

5.1. 測試環(huán)境

CPU: Intel(R) Xeon(R) CPU E5-2630 v3 @ 2.40GHz x2 (共16核32線程)

內(nèi)存: DDR4 1866 MHz(共192G)

SSD: INTEL 730 IOPS 89000

CentOS Linux release 7.3.1611 (Core)

5.2. 測試數(shù)據(jù)

測試程序使用的是我們自己開發(fā)的測試工具: terarkdb-tests

測試數(shù)據(jù)使用了 Wikipedia,原始數(shù)據(jù)約 103 GB

5.3. 測試準(zhǔn)備

分別使用原生 wiredtiger-with-snappy 和 適配了 terark-as-data-source 的 引擎,灌入上文提到的數(shù)據(jù),總大小102G . 數(shù)據(jù)的前3列合并作為 key, 剩余的字段作為 value.

原生 wiredtiger 生成的數(shù)據(jù)集大小是 62G,其中 bloom-filter 文件 0.1G,數(shù)據(jù)文件 62G .

適配 terark 生成的數(shù)據(jù)集大小是 23G,因?yàn)槭强蓹z索壓縮,所以不需要 bloom-filter.

原生 WiredTiger 配置：

wiredtiger_open

(

db

=./

wiredtigerdb_lsm

,

conf

=

create

,

cache_size

=

137438953472

,

log

=(

enabled

,

recover

=

on

),

checkpoint

=(

log_size

=

64MB

,

wait

=

60

),

lsm_manager

=(

worker_thread_max

=

8

),

extensions

=[

libwiredtiger_snappy

.

so

])

session

->

create

(

uri

=

lsm

:

dbbench_wt

-

0

,

conf

=

key_format

=

S

,

value_format

=

S

,

checksum

=

off

,

internal_page_max

=

128K

,

leaf_page_max

=

16K

,

type

=

lsm

,

os_cache_dirty_max

=

16MB

,

lsm

=(

bloom_config

=(

leaf_page_max

=

8MB

),

bloom_bit_count

=

28

,

bloom_hash_count

=

19

,

bloom_oldest

=

true

,

chunk_max

=

40GB

,

chunk_size

=

100MB

,

merge_min

=

2

),

block_compressor

=

snappy

)

修改版配置：

wiredtiger_open

(

db

=./

wiredtigerdb_terark

,

conf

=

create

,

cache_size

=

34359738368

,

log

=(

enabled

,

recover

=

on

),

checkpoint

=(

log_size

=

64MB

,

wait

=

60

),

lsm_manager

=(

worker_thread_max

=

8

),

extensions

=[

libwiredtiger_snappy

.

so

])

session

->

create

(

uri

=

lsm

:

dbbench_wt

-

0

,

conf

=

key_format

=

S

,

value_format

=

S

,

checksum

=

off

,

internal_page_max

=

128K

,

leaf_page_max

=

16K

,

type

=

lsm

,

os_cache_dirty_max

=

16MB

,

lsm

=(

bloom_config

=(

leaf_page_max

=

8MB

),

bloom_bit_count

=

28

,

bloom_hash_count

=

19

,

bloom_oldest

=

true

,

chunk_max

=

20GB

,

chunk_size

=

500MB

,

merge_min

=

2

,

merge_custom

=(

prefix

=

terark

,

start_generation

=

2

,

suffix

=.

trk

)))

補(bǔ)充說明：

WiredTiger 會在 level0 和 level1 產(chǎn)生原生的 lsm-chunk, level2 及以上的層級才會產(chǎn)生 terark-chunk.在本測試中,完成 compact 后所有 chunk 都轉(zhuǎn)為了 terark-chunk.這里的 bloom_filter 只作用于初期的 lsm-chunk 而不作用于 terark-chunk.

5.4. 測試用例

壓縮率在上面已經(jīng)對比很明顯了,對于不同用例下,壓縮率是不變的(23 GB vs. 62 GB).

剩下的測試主要是在給定時(shí)間內(nèi),重復(fù)進(jìn)行隨機(jī)訪問.

key 提取于原文件,保證查詢都會命中.這里要說明的是,key 文件有 1.2G 大小,因?yàn)槭峭慌_機(jī)子上測試,可以認(rèn)為測試程序自身會占用約 2G 大小的空間.

限制內(nèi)存方面,

原生 wiredtiger 通過設(shè)置內(nèi)核參數(shù),以限制物理內(nèi)存的方式完成；

適配了 terark 的經(jīng)由 cgroup 完成；

二者方式不同在于原生 wiredtiger 間接使用的系統(tǒng)緩存是無法通過 cgroup 限制的.

5.4.1. 不限內(nèi)存

不限制內(nèi)存的情況下,原生WT會使用非常多的內(nèi)存,實(shí)際場景中幾乎不存在數(shù)據(jù)能全部裝入內(nèi)存的情況.

原生WiredTiger(約100萬QPS)：

?
?

修改版WiredTiger(約122萬QPS):

?
?

注：Terark 版本的波動很小是因?yàn)槌跏紩r(shí)有內(nèi)存預(yù)熱,數(shù)據(jù)駐留在內(nèi)存后不會 eviction.

5.4.2. 內(nèi)存限制 27G

在這種情況下,Terark 版的 WT 可以完全裝入內(nèi)存,而原生的對內(nèi)存需求太大,無法完全裝入,性能差距明顯(此時(shí) Terark 版本的數(shù)據(jù)總尺寸約為 23 GB)

原生 WiredTiger(約1.3萬)：

?
?

修改版 WiredTiger (和不限內(nèi)存保持一致,即122萬左右)：

?
?

5.4.3. 內(nèi)存限制為12G

注：鑒于 terark 生成的數(shù)據(jù)集大小 23G,12G 的測試就是為了測試當(dāng)數(shù)據(jù)集大于內(nèi)存時(shí)的效果.

原生 WiredTiger(約6700)：

?
?

此處原本的 WiredTiger 在 12G 內(nèi)存下和 27G 下的性能曲線都是先高后低.

我們的理解是初期 WiredTiger 的 DBCache 還未填滿(默認(rèn)值是物理內(nèi)存的一半),這部分內(nèi)存就被系統(tǒng)緩存用了,從而大量的已壓縮數(shù)據(jù)塊存在于系統(tǒng)緩存中,系統(tǒng)緩存的命中率就比較高,從而性能較好.

隨著時(shí)間的推進(jìn),wiredtiger 不斷申請新的內(nèi)存,系統(tǒng)會犧牲系統(tǒng)緩存,優(yōu)先保證進(jìn)程的內(nèi)存要求,直到把 DBCache 填滿(達(dá)到 DBCache 上限,即物理內(nèi)存的一半),此時(shí) DBCache 內(nèi)有大量已解壓的數(shù)據(jù),在相同的內(nèi)存中,存放壓縮的數(shù)據(jù)和已解壓的數(shù)據(jù),已解壓的數(shù)據(jù)必然只能存放得更少,而系統(tǒng)緩存中有沒有多少存量,從而整體上減小了 Cache 命中率,進(jìn)而頻繁的 IO 導(dǎo)致曲線轉(zhuǎn)而向下.

這也說明在 IO 能力不足時(shí),增大系統(tǒng)緩存比增大 DBCache 更能獲得性能的提升,我們相信,如果這里使用的是 PCIe 的高端 SSD,情況會很不一樣.

修改版 WiredTiger(約14萬)：

?
?

6.

總結(jié)

目前和 MongoDB 官方的合作還在繼續(xù),我們期待未來 MongoDB 的用戶能夠使用上 Terark 的技術(shù),在 OLTP 領(lǐng)域能夠獲得更好的性能,更低的成本.

同時(shí)也非常期待能夠和其他數(shù)據(jù)庫廠商產(chǎn)生深度合作,把中國的技術(shù)推向世界.

?

Terark 專注于存儲引擎的研發(fā)

提供領(lǐng)先的數(shù)據(jù)庫和存儲系統(tǒng)優(yōu)化服務(wù)

搜索 "Terark" 了解更多

聯(lián)系我們：contact@terark.com

?

Terark 實(shí) 驗(yàn) 室