如何評價國產高性能存儲引擎 TerarkDB ?

01-15

目前我們在做一款國產的存儲引擎，完全拋棄了B+樹或者LSM結構，使用自動機做索引，大家如何怎麼看待我們這樣的一個全新的存儲引擎的前景？
評測報告: Terark - 重新定義數據技術

我是 TerarkDB 的作者，題主也是我們公司的初創人員之一。

目前我們的存儲引擎產品還在快速的迭代，大家可以關注一下我們的 GitHub - TerarkDB ，作為一家中國本土的公司，我們希望把中國人做的存儲引擎推廣到全世界，目前我們也非常需要相關領域的技術大牛加入我們！

以下，我對目前已有的疑問進行一些解答（持續更新）：

前面 @李黃河提到了 AmpLab 的 Succinct，我在去年九月份就看到了 AmpLab 的那篇 Paper。AmpLab 的 succinct 是 FM-Index 的一個實現，FM-Index 的優點不用多說，可以 google 出來非常豐富的資料，但它最大的缺點，就是 Throughput （不是 Latency，不是 QPS）太差，在 i7-6700K 上也大約只有 7MB/s，壓縮率也很一般，可以說這是 FM-Index 為自己的豐富功能付出的代價。

@楊東東提到的 sdsl-lite，我也很早就在 github 發現了，sdsl-lite 實現了絕大部分常用的 Succinct 數據結構，單論其中的 Wavelet tree(實現FM-Index的一種基礎數據結構) 性能比 AmpLib 的對應物要高。但更基本的 Rank-Select 實現，其性能完全無法與 Terark 的實現相比。

TerarkDB 只在 Index 上（和長度較短的 string 類型的欄位）使用了 Succinct ，並且 TerarkDB 使用的 Succinct，不是 FM-Index，是我們自己實現的一種多層嵌套的 Succinct Trie。這種 Succinct 的壓縮率更高，只比較壓縮率，一般介於bzip2和gzip之間，Throughput 也更高，同樣在 i7-6700K 上，一般在 20~30MB/s，最快能超過100MB/s，這裡我們可以簡單地把 Throughput 定義為：單位時間內匹配的 text/key 的總長度，比如說，key 的平均長度是 30 個位元組，Throughput = 30MB/s 時，就相當於每秒鐘能進行 1M(100萬)次 key 的搜索。

所以，把 Succinct 用於 Index 時，即便 Throughput 並不是特別高，也可以達到較高的 QPS。但是慢著，作為資料庫，光匹配個 Key 並沒有什麼用，關鍵是要拿到對應的 Value （最簡單的 Key-Value 模型）。這時，該我們的第二種壓縮技術登場了：

對 Data 的壓縮

先說現有資料庫中對 data 壓縮的主流技術：

對時間與空間進行折衷：壓縮的方式都是使用通用壓縮技術按塊/頁(block/page)壓縮（塊尺寸通常是 4K~32K，以壓縮率著稱的 TokuDB 塊尺寸是 2M~4M）。

當啟用壓縮的時候，隨之而來的是訪問速度下降，這是因為：

寫入時，很多條記錄被打包在一起壓縮成一個個的塊，增大塊尺寸，壓縮演算法可以獲得更大的上下文，從而提高壓縮率；相反地，減小塊尺寸，會降低壓縮率。
讀取時，即便是讀取很短的數據，也需要先把整個塊解壓，再去讀取解壓後的數據。這樣，塊尺寸越大，同一個塊內包含的記錄數目越多，為讀取一條數據，所做的不必要的解壓就也就越多，性能也就越差。相反地，塊尺寸越小，性能也就越好。

一旦啟用壓縮，為了緩解以上問題，傳統資料庫一般都需要比較大的專用緩存，用來緩存解壓後的數據，這樣可以大幅提高熱數據的訪問性能，但又引起了雙緩存的空間佔用問題，一是操作系統緩存中的壓縮數據，二是專用緩存中解壓後的數據。還有一個同樣很嚴重的問題：專用緩存終歸是緩存，當緩存未命中時，仍需要解壓整個塊，這就是慢Query問題的一個來源；慢Query 的另一個來源是操作系統緩存未命中時……

這些都導致現有傳統資料庫在訪問速度和空間佔用上是一個此消彼長，無法徹底解決的問題，只能進行這樣或那樣的折衷。

TerarkDB 的壓縮技術

對整個資料庫（Key-Value 資料庫中所有 Value 的集合）進行壓縮，而不是按 block/page 壓縮，是對整個資料庫壓縮，對整個資料庫壓縮！

這種壓縮是我們專門針對資料庫的需求，精心設計的一個壓縮演算法，用來徹底解決傳統資料庫壓縮的問題：

壓縮率更高，沒有雙緩存的問題，只要把壓縮後的數據裝進內存，不需要專用緩存，可以按 RowID/RecordID 直接讀取單條數據，如果把這種讀取單條數據看作是一種解壓，那麼——

按 RowID 順序解壓時，解壓速度（Throughput）一般在 500MB每秒(單線程)，最高達到約 7GB/s，適合離線分析性需求，傳統資料庫壓縮也能做到這一點
按 RowID 隨機解壓時，解壓速度一般在 300MB每秒(單線程)，最高達到約3GB/s，適合在線服務需求，這一點完勝傳統資料庫壓縮：按隨機解壓 300MB/s 算，如果每條記錄平均長度 1K，相當於 QPS = 30萬，如果每條記錄平均長度300個位元組，相當於QPS = 100萬！
預熱(warmup)，在某些特殊場景下，資料庫可能需要預熱。因為去掉了專用緩存，TerarkDB 的預熱非常簡單卻又極其高效，只要設置 mmapPopulate，資料庫載入成功後就是預熱好的，這個預熱的 Throughput 就是 ssd 連續讀的 io 性能(較新的 ssd 性能以 GB/s計)。

最終，把所有這些技術整合為一個資料庫，增加了若干中間開銷，這個性能表現我其實還不太滿意。

大家一般情況下都會認為資料庫壓縮總是基於傳統技術，做一些折衷，然後在某項指標上表現比較好，而我們的測試結果卻基本上全面勝出，大家會覺得這個數據有水分。希望大家能更多了解我們的產品和技術，把這些更好的技術推廣開來。

@黃立峰認為相比我們的技術， leveldb/rocksdb 的強項在於順序訪問，而不是隨機訪問，這確實通過我們的評測證實了……

@Gary Chen@pig pig 數據量遠大於內存的情況下（測試中數據是內存的3~4倍），因為我們的壓縮演算法，資料庫本身不再需要專用緩存，所以只要內存能放得下壓縮後的數據，就不會有cache miss……

@槍騎兵叔叔提的問題非常好！這其實是因為我上面說的「整庫壓縮」不夠嚴謹，更嚴謹得講，是這樣的：

整庫壓縮只發生在用戶主動調用 compact 時。在普通工況下，是按 segment 壓縮的：

一個 TerarkDB 資料庫(Table)包含多個 segment，按照 segment 的狀態可分為 writing segment，frozen writable segment，以及 readonly segment。數據會首先寫入 writing segment，這個 segment 中的數據可以直接更新及檢索。當寫入的數據達到一定的尺寸時，writing segment 會成為 frozen writable segment ，同時開始被後台線程進行壓縮。當後台壓縮結束時，就會生成 readonly segment，並刪除 frozen writable segment。除此之外，數據的物理刪除、segment 合併等工作也都在後台線程中執行。最終，大部分數據都會處於 readonly segment 中。

@呂不胖離線時間，你說的應該是指壓縮耗時，壓縮演算法本身，根據數據的不同：

對索引(key)的壓縮，單線程每秒大約20M~70M，同一索引無法多線程並行壓縮，好在索引尺寸一般比較小
對數據(value)的壓縮，單線程每秒大約15M~100M(變化範圍更大)，可以多線程並行壓縮

針對 Benchmark 中的數據集(9GB): Amazon movie reviews ，對數據(value)的壓縮啟用了8個線程

將數據寫入 Writing Segment 耗時103秒
將 frozen writable segment 轉化為 Readonly segment，也就是壓縮，總耗時 342 秒，包括壓縮演算法本身的耗時和壓縮前後的數據轉化，數據組織等額外時間消耗，總體 Throughput 是 26.3MB/s

這其中對數據的壓縮（我們自己研發的全局壓縮演算法）消耗cpu最多，不過單測壓縮演算法本身：

8線程並行壓縮（其中有一部分計算是串列的），耗時 163秒
單線程壓縮，耗時 453 秒，8線程總體提速大約是3倍左右

所以其實很大部分時間消耗是在數據的轉化和組織上，這應該還有一定的優化空間。

手動和諧

粗看了下，在數據量遠大於內存的情況下，QPS可以到20萬？不好相信，建議補充具體的數據類型和測試步驟。以及說明，為什麼會比其他資料庫快很多。

首先給這家公司點個贊。給這個產品的工程師點個贊。

=========================

官方文檔介紹Terark的核心技術是使用了Trie 和 Succinct技術。

Trie不說了，所以官方說支持正則查詢也不奇怪了。

關鍵是這個Succinct 數據存儲。這個目前百度搜索基本沒有結果，只有：大數據時代的壓縮表現形式這裡對Succinct做了簡單介紹：

Succinct：在Apache Spark里搜索和點查詢壓縮過的數據
Succinct是一個「壓縮」的數據存儲方式。可以讓很多點查詢方法（搜索、計數、求範圍、隨機查詢）直接對輸入數據的壓縮模式進行操作。Succinct使用的壓縮技術在實際應用中可以獲得和gzip差不多的壓縮率，同時不需要二級索引、數據掃描或解壓縮等技術來支持上述的操作。Succinct並不保存數據文件本身，僅僅是壓縮後的形式。通過讓用戶直接對壓縮過的數據直接進行操作，Succinct同時具有低延遲和低存儲空間兩大優點。
圖2：定量比較數據掃描、數據索引和Succinct。因為Succinct是用壓縮方式存儲數據，並直接對壓縮後的形式進行操作，它可以在內存里存放並使用大的多的數據。
作為斯坦福AMPLab實驗室的一個研究項目，Succinct已經在2015年年底作為Apache Spark的一部分發布了。這意味著Spark的使用者可以利用Succinct來對文件進行壓縮，並可以直接使用搜索查詢（包括對壓縮的RDD進行正則表達式查詢）、計數和範圍查詢。另外，已經基於Succinct的文件（非結構化）應用介面開發了新的抽象，這就可以把Spark作為文本或鍵值對型的存儲，並使用現有的DataFrame的API來做搜索、計數、範圍查詢以及隨機查詢。

google 的結果也不多:

Succinct Spark from AMPLab: Queries on Compressed RDDs

Succinct: Enabling Queries on Compressed Data

這是一個2015年底才在Apache Spark發布的研究項目，距今才不過6個月的時間。TerarkDB官方的數據跟國外Succinct數據也基本一致：(下面是國外的數據)

但官方文檔中只提到了優勢，沒有說到劣勢或者是適用場景。

我給補充下：

用 Succinct: Enabling Queries on Compressed Data里的一句話來說明：

What do We lost?

Preprocessing expensive(4GB/hour/core)
CPU (for data access)
Sequential scan throughput (13Mbps/thread)
In-place updates

官方拿TerarkDB跟levelDB，RockDB做比較似乎不太合適，LevelDB是犧牲讀增強寫而優化的LSM樹，但Succinct卻是專為讀優化的。除非TerarkDB專門又為寫做了優化，否則做為OLTP資料庫可能不合適。

樓主的東東核心部分木有開源哦，那就嘗試著猜測下：

索引：

succinct trie= trie + succinct的狀態轉移圖(實現一個快速rang/select的LOUDS結構，目的只有一個：通過對這個bit vector計算，實現狀態跳轉)

表是分segment的，segment是個succinct trie，如果這樣還不過癮，就可以搞嵌套，這樣性能也算可以，因為是後台線程

數據：

對數據進行BTW變換，組織成自己的格式(可以認為是壓縮，但無需解壓，通過計算即可還原)

不對之處還望指正。

來說一下我的了解。

先上一個結論：和LSM來比較是不妥當的，我不認為LSM可以當作一個索引結構，LSM主要體現的是通過犧牲一部分讀性能來達到寫優化的目的，但是這個資料庫的底層技術寫效率極低，至少和LSM相比是差別極大的，LSM可以拿來大量寫入數據，而這個資料庫的底層技術幾乎只能支持離線處理，雖然通過離線處理的方式可以達到異常高的讀效率，但是離線方式本身限制了它的應用場景和LSM幾乎完全不會重合。以上結論是基於一年前對這個技術的了解，如果現在有比較大的革新，歡迎指正。

最早看到這個技術，是看到這個項目當前的參與者之一「雷鵬」的一個關於自動機的slide《有窮自動機的原理及應用》，分享了一些關於自動機的通用技術，並提及了一些他的DFA構建工具，很可惜相關的項目不開源，作為一直對自動機很感興趣的一個人，我深表遺憾。

由於對自動機領域和文本匹配了解還比較多，所以曾經試著自己開發這個技術，但是很快遇到了瓶頸。

首先，內存不夠用，我曾採用了很多方式來試圖解決這個問題，但是終究這個問題是很難解的，最終需要藉助磁碟來完成中間數據的存儲，這個項目有一些可試用的demo，稍經試用之後發現，這個demo用了一個奇怪的方式來實現了內存池，由於作者不開源，我就不方便在這裡公布具體的推測了。

第二，在內存不夠的情況下，寫入速度很低，幾乎必需離線。

第三，生成速率不穩定，這個可能是我自己實現的問題，但是從原理上來看，壓縮的效率和生成的速率都受數據集特點影響比較大。

以上，在一些離線場景，這個處理方法確實比較有優勢，依然非常期待這款資料庫的成功。

https://www.usenix.org/system/files/conference/nsdi15/nsdi15-paper-agarwal.pdfSuccinct,

a distributed
data store that supports a wide range of queries while operating at a new point in the design space [確實, 非常新穎] between
data scans (memory-efficient, but high latency and
low throughput) and indexes (memory-inefficient, low
latency, high throughput).

We ran a simple microbenchmark
to evaluate the performance of Succinct
over a single extract request for varying sizes of reads.
Succinct achieves a constant throughput of 13Mbps using
a single core [這個值是很低的，大概看文章中實現原理，猜測是suffx tree的跳躍訪問導致的cpu cache miss] single thread implementation. This is essentially
a tradeoff that Succinct makes for achieving
high throughput for short reads and for search queries
using a small memory footprint.

集成到已有系統作為一個新的引擎放到適合的業務上也不錯。

GitHub - simongog/sdsl-lite: Succinct Data Structure Library 2.0 簡單了解，看代碼說明可能比看文章方便

對比的產品裡面有三個都是屬於用lsm技術的，也就是leveldb系的，這個技術本身就是強調寫多於讀，而且讀可以很容易通過提升內存、cpu等硬體資源來提速的場景，這裡把讀作為主要的比較，一點都不科學；另外把個壓縮比例進行比較，也只是設計決策而已，壓縮比例高並不代表你的資料庫產品就有多好，壓縮比例高是要耗費更多資源的啊

看測試數據，確實很漂亮。只不過，這麼高的數據壓縮率，離線時間得多久啊？

之前也有人提到了，實驗選擇的幾個對比對象有的使用了寫優化的LSM，對比不夠公平。實驗裡面無論讀還是寫，性能都太好了，有點兒不敢相信。留個坑有時間看看這個神器。

因為它深度依賴glibc，gcc，tbb等具體版本的動態庫，我為它做了一個綠色包，便於在我們的機器centos6上部署

好像是ex-yahooer大牛做的，性能很好，目前還不太成熟，但是開發進度非常快。

目前我們在ssdb，pika，redis中做選擇，最終選擇pika。

看了Succinct相關論文, 感覺succint是一顆支持取明細的壓縮的後綴樹.

對於壓縮率,和點查詢(其他參考沒索引的情況)性能應該沒啥問題

但如果業務應用需要大量的寫, 而且估計邊寫,邊讀,邊合併, 應該有點嗆

感覺更適合append模式的業務. 冷數據一次壓縮,再也不需要動,否則cpu肯定吃不消的

@雷鵬 terakDB中提到，在Key-Value 模型中， Succinct 用於key壓縮，整個Value 按照segment進行壓縮；key和value是分別進行壓縮的，那key和value映射關係怎樣對應起來的呢？

我不是非常懂存儲，但是我在想，這麼高的壓縮率，會不會比較吃cpu啊。

測試報告裡面好像沒有提這個事情。

當然還是很佩服。

看到@雷鵬提到了整庫壓縮。

有個小疑問，整庫壓縮的話，是不是犧牲了動態寫入的性能呢？

每插入一部分數據，就相當於原資料庫變化了，這樣還得對整個庫進行重新壓縮吧

如果覺得涉及核心技術的話，不需要透露細節