Terark—重新定義數據技術（23頁）.pdf

1、T重新定義數據技術雷鵬Terark Inc.CTO-Preface-Terark是一個數據技術提供商Terark成立于2015年11月致力于研發領先世界的高壓縮存儲和高性能檢索技術Terark目前的性能已經大幅超越了rocksdb等開源存儲引擎我們的存儲引擎能為典型的大數據應用節省30%以上的成本Big Data Market Revenue Trend 20112026市場需求巨大-世界上92%的數據是在過去兩年產生,并且還在加速,每年增長40%50%-云端,終端,都在處理越來越大的數據量,需要新型數據技術極高的性能和存儲能力Wikibon報告20112026 Market Forecast

2、可檢索壓縮 SeComp(Seekable Compression)技術這個技術擁有超高的壓縮率(一般在5倍以上),同時可以直接在壓縮的數據上進行定點訪問(微秒級),避免了傳統數據庫使用的分塊壓縮技術固有的缺點索引技術我們實現了多種獨有的索引技術。其中最關鍵的是“數據即索引，索引即數據”,從而節約了空間，同時并保持甚至提高了性能存儲引擎技術Terark存儲引擎可以便捷的融入各種數據系統,為其提供高效的核心存儲技術,大幅提升整個系統的容量和性能核心技術TerarkDB 是高性能、高壓縮的存儲引擎我們測試過一組800G的數據，Terark壓縮后只有47.9G，同時Query延遲達到微秒級。使用Te

3、rark，只需要1臺普通64G內存的服務器就夠了，而用其它數據庫可能就需要搭建一個小集群了。適用場景 云平臺 互聯網 企業大數據 數據庫 手機 功能豐富：支持豐富數據類型的Schema定義和靈活的索引,原生支持正則表達式檢索 性能強大：TerarkDB的QPS比同類產品提高12個數量級,降低延遲,提高吞吐量 容量大成本低：壓縮率5倍以上,極大的降低IO壓力,提高數據容量,降低基礎設施成本與谷歌、Facebook的產品相比占空間更小同時檢索更快非時間空間的折衷,而是技術革新TerarkDB 技術精要功能概要 索引壓縮 數據（Value）壓縮 Succinct TerarkDB 架構索引壓縮Has

4、hB+TreeTerark Nest Succinct Trie壓縮率膨脹還行 很高搜索速度極快較快很快精確搜索支持支持支持范圍搜索不支持支持支持前綴搜索不支持支持支持正則搜索不支持不支持支持反向搜索(id到key)可支持不支持支持動態索引：TRB:Terark Thread Red Black Tree傳統 RBTreeB+TreeTRB數據結構消耗4 ptr 0.75 keylen64 bits搜索速度較快很快很快數據耦合緊耦合緊耦合松耦合反向搜索(id到key)不支持不支持支持key可與結點分離Key 數據可以保存在另外的數組，用平行的數組下標訪問 例如，以最小代價，用作鏈式 HashM

5、ap 的沖突鏈，用作 DFA 的狀態轉移表只有 Left/Right，用數組下標代替指針；使用兩個 bit 表示 threadtag，iterate更快數據（Value）壓縮塊壓縮:leveldb,rocksdb,wiredtiger短數據:Terark Nest Succinct Trie長數據:Terark Global Compression壓縮率還行 很高很高 隨機讀取速度很慢很快 很快 順序讀取速度很快 較慢很快 雙緩沖問題有無無壓縮速度快慢慢索引壓縮:Succinct Tree，概念Succinct Data Structure 是一種能夠在接近于信息論下限的空間內來表達對象的技術

6、，通常使用位圖來表示，用位圖上的rank和select來定位。雖然能夠極大的降低內存占用量，但是實現起來較為復雜，目前開源的有SDSL-Lite。注意：Succinct數據結構的性能比相應的傳統(基于指針)數據結構更低。Terark 使用自己實現的 Rank-Select，性能遠高于開源實現。索引壓縮:Succinct Tree，圖示每個結點用兩個bit表示,Pre-Order 10110100100每個結點用兩個bit表示,Level-Order 101110010000LOUDSParent(c)=rank0(select1(c)Child(p,i)=select0(p)p+iNeeds

7、findopen,findclose,enclose,which are much slower than rank/select,rarely used Simple and fast,small:DFUDS存儲了 hat,is,it,a 的Trie對于第i個節點=Nodei，其孩子節點：child0=NodeSelect0(i+1)-i child1=NodeSelect0(i+1)-i+1 child2=NodeSelect0(i+1)-i+2 httaiasPosition012345678910111213141516Bits10111010110010000Nodesuper012

8、345670175423711101011001000010Patricia Trie+嵌套Patricia Trie:路徑壓縮的Trie 路徑壓縮:把一串僅包含一個孩子的結點壓縮成一個嵌套:把壓縮的路徑存入另一個棵Trie 需要:Trie 數據結構支持“反向搜索”，即從結點搜索出能到達該結點的字符串(除了 Succinct，Double Array Trie也支持反向搜索，但無壓縮效果)對壓縮路徑進行了翻轉對數據(Value)的壓縮全局壓縮 全局字典+局部字典，貪心最長匹配 可選熵編碼 對短數據友好（50字節）數據集越大，壓縮效果越好 定點訪問（根據 record id）可認為是 lz77

9、系列變種（加上熵編碼，整體類似 gzip）TerarkDB 架構TerarkDB 最上層邏輯是“表”(Table)，每個表可以通過 Schema定義其字段及相應的索引、特性等。TerarkDB 可以嵌入其他上層數據庫，如MongoDB、MySQL、SSDB等，只需要將其引擎替換掉即可。TerarkDB目前在Github開源：https:/ 中每一行有邏輯刪除和物理刪除的標記，物理刪除的記錄一定也是邏輯刪除的，邏輯刪除的可能沒有物理刪除。邏輯ID（record id）和物理ID(physical id)之間通過 Rank Select 算法進行雙向映射。segdel_markcol0col1.c

10、olN-1s0record00,0record10,0record21,0 邏輯刪除，還沒有物理刪除s1record31,1 邏輯刪除，并且也物理刪除record4.邏輯Id01234567物理刪除標記10011010物理id=Rank0(邏輯id)0(NA)012(NA)2(NA)23(NA)3物理id0123邏輯id=Select0(物理id)1257分段(Segment)TerarkDB的段根據狀態和類型分為：只讀段(Readonly Segment)可寫段(Writable Segment)正在寫段(Writing Segment)凍結段(Frozen Segment)正在寫的段只能有

11、一個，其他的有多個。Readonly/Writable 是按類型來區分Writing/Frozen 是按狀態來區分Writing segment 的類型是 WritableWriting SegmentRead-Only SegmentRead-Only SegmentRead-Only SegmentWriable SegmentWriable SegmentFrozen Writable Segment新數據WritableFrozenRocksDB on Terark:TerarkX使用 Terark 索引壓縮與數據壓縮算法，實現 RocksDB SSTable 利用 Terark 的獨

12、特優勢，通過 RocksDB，來造福整個生態 壓縮率遠高于 RocksDB 內置的壓縮(3 倍)隨機讀性能遠高于 RocksDB 內置的壓縮(10 倍)Terark 數據壓縮算法需要掃描數據源兩遍，RocksDB 不支持 Terark 為了實現高壓縮與高速讀，犧牲了壓縮速度 僅在最底層 level 使用 Terark 使用 universal compaction減小寫放大改進 RocksDB 底層架構我們的技術非常適用于，對性能要求極高，對壓縮率有特殊需求，以及對海量數據高性能處理的場景 歡迎相關廠商的合作Terark Inc.提升核心引擎性能和穩定性MongoDB的集成Terark數據產品發布計劃更多產品的集成2016-122017-32017-62017-9TerarkXTerarkDB運維工具集MongoDB+TerarkRedis+TerarkMySQL+Terark