LSM-樹在-Apache-HBase-等存儲系統(tǒng)中的應(yīng)用課件

1、課時(shí)1LSM 樹在 Apache HBase 等存儲系統(tǒng)中 的應(yīng)用Log-Structured 吉構(gòu)的優(yōu)化SSTable 和 LSM 樹LSM 樹的應(yīng)用課時(shí) 12前言這種方法存在的一個(gè)問題就是當(dāng)我們不斷地添加新數(shù)據(jù)進(jìn)去之后，所占用的空間會(huì)越來越大 而且遍歷整個(gè)數(shù)據(jù)吉構(gòu)的時(shí)間也隨之越來越長可以通過一種叫 Compaction 的方法把數(shù)據(jù)合并Log-Structured 吉構(gòu)的優(yōu)化首先可以定義一個(gè)大小為 N 的固定數(shù)組，稱它為 Segment一個(gè) Segment 最多可以存儲 N 個(gè)數(shù)據(jù)，當(dāng)有第 N+1 個(gè)數(shù)據(jù)需要寫入 Log-Structured 吉構(gòu)的時(shí)候會(huì)創(chuàng)建一個(gè)新的 Segment，然后

2、將 N+1 個(gè)數(shù)據(jù)寫入到新的 Segment 中定義一個(gè) Segment 的大小為 16當(dāng) Segment 1 寫滿了 16 個(gè)數(shù)據(jù)之后會(huì)將新的數(shù)據(jù)寫入到 Segment 2 里L(fēng)og-Structured 吉構(gòu)的優(yōu)化假設(shè)我們定義當(dāng) Segment 的數(shù)最到達(dá)兩個(gè)的時(shí)候，后臺線程就會(huì)執(zhí)行 Compaction 來合并吉果Log-Structured 吉構(gòu)的優(yōu)化SSTable 和 LSM 樹SSTable（Sorted String Table）數(shù)據(jù)吉構(gòu)是在 Log-Structured 吉構(gòu)的基礎(chǔ)上，多加了一條規(guī)則就是所有保存在 Log-Structured 吉構(gòu)里的數(shù)據(jù)都是鍵值對，并且鍵必須

3、是字符串在經(jīng)過了 Compaction 操作之后，所有的 Compacted Segment 里保存的鍵值對都必須按照字符排序SSTable 和 LSM 樹假設(shè)現(xiàn)在想利用 Log-Structured 吉構(gòu)來保存一本書里的詞頻為了方便說明，把 Segment 的大小設(shè)為 4SSTable 和 LSM 樹SSTable 和 LSM 樹二叉查找樹里的一個(gè)特性：二叉查找樹的任意一個(gè)節(jié)點(diǎn)都比它的左子樹所有節(jié)點(diǎn)大，同時(shí)比右子樹所有節(jié)點(diǎn)小在業(yè)界上，我們?yōu)榱司S護(hù)數(shù)據(jù)吉構(gòu)讀取的高效，一般都會(huì)維護(hù)一個(gè)平衡樹 比如，在上一講中說到的紅黑樹或者 AVL 樹而這樣一個(gè)平衡樹在 Log-Structured 吉構(gòu)里通常

4、被稱為 memtable上面所講到的概念，通過內(nèi)部維護(hù)平衡樹來進(jìn)行 Log-Structured 吉構(gòu)的 Compaction 優(yōu)化 這樣一種數(shù)據(jù)吉構(gòu)被稱為是 LSM 樹（Log-Structured Merge-Tree）它是由 Patrick ONeil 等人在 1996 年所提出的LSM 樹的應(yīng)用在數(shù)據(jù)庫里面，有一項(xiàng)功能叫做 Range Query，用于查詢在一個(gè)下界和上界之間的數(shù)據(jù)比如查找時(shí)間戳在 A 到 B 之內(nèi)的所有數(shù)據(jù)許多著名的數(shù)據(jù)庫系統(tǒng)，像是 HBase、SQLite 和 MongoDB，它們的底層索引因?yàn)椴捎昧?LSM 樹 所以可以很快地定位到一個(gè)范圍LSM 樹的應(yīng)用互聯(lián)網(wǎng)人實(shí)戰(zhàn)大學(xué)LSM 樹的應(yīng)用采用 Lucene 作為后臺索引引擎的開源搜索框架，像 ElasticSearch 和 Solr，底層其實(shí)運(yùn)用了 LSM 樹因?yàn)樗阉饕娴奶厥庑裕锌赡軙?huì)遇到一些情況那就是：所搜索的詞并不在保存的數(shù)據(jù)里，而想要知道一個(gè)數(shù)據(jù)是否存在 Segment 里面，必須遍歷一 次整個(gè) Segment，時(shí)間開銷還并不是最優(yōu)