[[349357]]

 分布式系統(tǒng)比起單機(jī)系統(tǒng)存在哪些難點(diǎn)呢?

0x01：網(wǎng)絡(luò)因素

由于服務(wù)和數(shù)據(jù)分布在不同的機(jī)器上，每次交互都需要跨機(jī)器運(yùn)行，這帶來如下幾個(gè)問題：

網(wǎng)絡(luò)延遲：性能、超時(shí)

同機(jī)房的網(wǎng)絡(luò)IO還是比較塊的，但是跨機(jī)房，尤其是跨IDC，網(wǎng)絡(luò)IO就成為不可忽視的性能瓶頸了。并且，延遲不是帶寬，帶寬可以隨便增加，千兆網(wǎng)卡換成萬兆，只是成本的問題，但延遲是物理限制，基本不可能降低。

這帶來的問題就是系統(tǒng)整體性能的降低，會帶來一系列的問題，比如資源的鎖住，所以系統(tǒng)調(diào)用一般都要設(shè)置一個(gè)超時(shí)時(shí)間進(jìn)行自我保護(hù)，但是過度的延遲就會帶來系統(tǒng)的RPC調(diào)用超時(shí)，引發(fā)一個(gè)令人頭疼的問題：分布式系統(tǒng)調(diào)用的三態(tài)結(jié)果：成功、失敗、超時(shí)。不要小看這個(gè)第三態(tài)，這幾乎是所有分布式系統(tǒng)復(fù)雜性的根源。

針對這個(gè)問題有一些相應(yīng)的解決方案：異步化，失敗重試。而對于跨IDC數(shù)據(jù)分布帶來的巨大網(wǎng)絡(luò)因素影響，則一般會采用數(shù)據(jù)同步，代理專線等處理方式。

網(wǎng)絡(luò)故障：丟包、亂序、抖動(dòng)。

這個(gè)可以通過將服務(wù)建立在可靠的傳輸協(xié)議上來解決，比如TCP協(xié)議。不過帶來的是更多的網(wǎng)絡(luò)交互。因此是性能和流量的一個(gè)trade off。這個(gè)在移動(dòng)互聯(lián)網(wǎng)中更需要考慮。

0x02：魚與熊掌不可兼得——CAP定律

• CAP理論是由Eric Brewer提出的分布式系統(tǒng)中最為重要的理論之一：
• Consistency：一致性，事務(wù)保障，ACID模型。
• Availiablity：[高]可用性，冗余以避免單點(diǎn)，至少做到柔性可用(服務(wù)降級)。
• Partition tolerance：[高]可擴(kuò)展性(分區(qū)容忍性)：一般要求系統(tǒng)能夠自動(dòng)按需擴(kuò)展，比如HBase。

CAP原理告訴我們，這三個(gè)因素最多只能滿足兩個(gè)，不可能三者兼顧。對于分布式系統(tǒng)來說，分區(qū)容錯(cuò)是基本要求，所以必然要放棄一致性。對于大型網(wǎng)站來說，分區(qū)容錯(cuò)和可用性的要求更高，所以一般都會選擇適當(dāng)放棄一致性。對應(yīng)CAP理論，NoSQL追求的是AP，而傳統(tǒng)數(shù)據(jù)庫追求的是CA，這也可以解釋為什么傳統(tǒng)數(shù)據(jù)庫的擴(kuò)展能力有限的原因。

在CAP三者中，“可擴(kuò)展性”是分布式系統(tǒng)的特有性質(zhì)。分布式系統(tǒng)的設(shè)計(jì)初衷就是利用集群多機(jī)的能力處理單機(jī)無法解決的問題。當(dāng)需要擴(kuò)展系統(tǒng)性能時(shí)，一種做法是優(yōu)化系統(tǒng)的性能或者升級硬件(scale up)，一種做法就是“簡單”的增加機(jī)器來擴(kuò)展系統(tǒng)的規(guī)模(scale out)。好的分布式系統(tǒng)總在追求”線性擴(kuò)展性”，即性能可以隨集群數(shù)量增長而線性增長。

可用性和可擴(kuò)展性一般是相關(guān)聯(lián)的，可擴(kuò)展性好的系統(tǒng)，其可用性一般會比較高，因?yàn)橛卸鄠€(gè)服務(wù)(數(shù)據(jù))節(jié)點(diǎn)，不是整體的單點(diǎn)。所以分布式系統(tǒng)的所有問題，基本都是在一致性與可用性和可擴(kuò)展性這兩者之間的一個(gè)協(xié)調(diào)和平衡。對于沒有狀態(tài)的系統(tǒng)，不存在一致性問題，根據(jù)CAP原理，它們的可用性和分區(qū)容忍性都是很高，簡單的添加機(jī)器就可以實(shí)現(xiàn)線性擴(kuò)展。而對于有狀態(tài)的系統(tǒng)，則需要根據(jù)業(yè)務(wù)需求和特性在CAP三者中犧牲其中的一者。一般來說，交易系統(tǒng)類的業(yè)務(wù)對一致性的要求比較高，一般會采用ACID模型來保證數(shù)據(jù)的強(qiáng)一致性，所以其可用性和擴(kuò)展性就比較差。而其他大多數(shù)業(yè)務(wù)系統(tǒng)一般不需要保證強(qiáng)一致性，只要最終一致就可以了，它們一般采用BASE模型，用最終一致性的思想來設(shè)計(jì)分布式系統(tǒng)，從而使得系統(tǒng)可以達(dá)到很高的可用性和擴(kuò)展性。

CAP定律其實(shí)也是衡量分布式系統(tǒng)的重要指標(biāo)，另一個(gè)重要的指標(biāo)是性能。

一致性模型

主要有三種：

• Strong Consistency(強(qiáng)一致性)：新的數(shù)據(jù)一旦寫入，在任意副本任意時(shí)刻都能讀到新值。比如：文件系統(tǒng)，RDBMS，Azure Table都是強(qiáng)一致性的。
• Week Consistency(弱一致性)：不同副本上的值有新有舊，需要應(yīng)用方做更多的工作獲取最新值。比如Dynamo。
• Evantual Consistency(最終一致性)：一旦更新成功，各副本的數(shù)據(jù)最終將達(dá)到一致。

從這三種一致型的模型上來說，我們可以看到，Weak和Eventually一般來說是異步冗余的，而Strong一般來說是同步冗余的(多寫)，異步的通常意味著更好的性能，但也意味著更復(fù)雜的狀態(tài)控制。同步意味著簡單，但也意味著性能下降。

以及其他變體：

• Causal Consistency(因果一致性)：如果Process A通知Process B它已經(jīng)更新了數(shù)據(jù)，那么Process B的后續(xù)讀取操作則讀取A寫入的最新值，而與A沒有因果關(guān)系的C則可以最終一致性。
• Read-your-writes Consistency(讀你所寫一致性)：如果Process A寫入了最新的值，那么 Process A的后續(xù)操作都會讀取到最新值。但是其它用戶可能要過一會才可以看到。
• Session Consistency(會話一致性)：一次會話內(nèi)一旦讀到某個(gè)值，不會讀到更舊的值。
• Monotonic Read Consistency(單調(diào)一致性)：一個(gè)用戶一旦讀到某個(gè)值，不會讀到比這個(gè)值更舊的值，其他用戶不一定。

其中最重要的變體是第二條：Read-your-Writes Consistency。特別適用于數(shù)據(jù)的更新同步，用戶的修改馬上對自己可見，但是其他用戶可以看到他老的版本。Facebook的數(shù)據(jù)同步就是采用這種原則。

0x03：分布式系統(tǒng)常用技術(shù)和應(yīng)用場景

• consistent hashing [with virtual node]：一致性哈希，數(shù)據(jù)分布
• vector clock：時(shí)鐘向量，多版本數(shù)據(jù)修改
• Quorum W+R>N [with vector clock]：抽屜原理，數(shù)據(jù)一致性的另一種解決方案。時(shí)鐘向量，多版本數(shù)據(jù)修改。
• Merkle tree [with anti-entropy]：數(shù)據(jù)復(fù)制
• MVCC：copy-on-write與snapshot
• 2PC/3PC：分布式事務(wù)
• Paxos：強(qiáng)一致性協(xié)議
• Symmetry and Decentralization：對稱性和去中心化。對稱性(symmetry)簡化了系統(tǒng)的配置和維護(hù)。去中心化是對對稱性的延伸，可以避免master單點(diǎn)，同時(shí)方便集群scale out。
• Map-Reduce：分而治之;移動(dòng)數(shù)據(jù)不如移動(dòng)計(jì)算。將計(jì)算盡量調(diào)度到與存儲節(jié)點(diǎn)在同一臺物理機(jī)器上的計(jì)算節(jié)點(diǎn)上進(jìn)行，這稱之為本地化計(jì)算。本地化計(jì)算是計(jì)算調(diào)度的一種重要優(yōu)化。
• Gossip協(xié)議：節(jié)點(diǎn)管理
• Lease機(jī)制：

consistent hashing：一致性哈希，解決數(shù)據(jù)均衡分布問題

我們通常使用的hash算法是hash() mod n，但是如果發(fā)生某個(gè)節(jié)點(diǎn)失效時(shí)，無法快速切換到其他節(jié)點(diǎn)。為了解決單點(diǎn)故障的問題，我們?yōu)槊總€(gè)節(jié)點(diǎn)都增加一個(gè)備用節(jié)點(diǎn)，當(dāng)某個(gè)節(jié)點(diǎn)失效時(shí)，就自動(dòng)切換到備用節(jié)點(diǎn)上，類似于數(shù)據(jù)庫的master和slave。但是依然無法解決增加或刪除節(jié)點(diǎn)后，需要做hash重分布的問題，也就是無法動(dòng)態(tài)增刪節(jié)點(diǎn)。這時(shí)就引入了一致性hash的概念 ，將所有的節(jié)點(diǎn)分布到一個(gè)hash環(huán)上，每個(gè)請求都落在這個(gè)hash環(huán)上的某個(gè)位置，只需要按照順時(shí)針方向找到的第一個(gè)節(jié)點(diǎn)，就是自己需要的服務(wù)節(jié)點(diǎn)。當(dāng)某個(gè)節(jié)點(diǎn)發(fā)生故障時(shí)，只需要在環(huán)上找到下一個(gè)可用節(jié)點(diǎn)即可。

一致性hash算法最常用于分布式cache中，比如注意的memcached。Dynamo也用其作為數(shù)據(jù)分布算法，并且對一致性算法進(jìn)行了改進(jìn)，提出了基于虛擬節(jié)點(diǎn)的改進(jìn)算法，其核心思路是引入虛擬節(jié)點(diǎn)，每個(gè)虛擬節(jié)點(diǎn)都有一個(gè)對應(yīng)的物理節(jié)點(diǎn)，而每個(gè)物理節(jié)點(diǎn)可以對應(yīng)若干個(gè)虛擬節(jié)點(diǎn)。

關(guān)于一致性hash的更多內(nèi)容，可以參考筆者另一篇博文：Memcached的分布式算法學(xué)習(xí)。

這篇文章也可以看看：某分布式應(yīng)用實(shí)踐一致性哈希的一些問題

virtual node

前面說過，有的Consistent Hashing的實(shí)現(xiàn)方法采用了虛擬節(jié)點(diǎn)的思想。使用一般的hash函數(shù)的話，服務(wù)器的映射地點(diǎn)的分布非常不均勻。因此，使用虛擬節(jié)點(diǎn)的思想，為每個(gè)物理節(jié)點(diǎn)(服務(wù)器)在continuum上分配100～200個(gè)點(diǎn)。這樣就能抑制分布不均勻，最大限度地減小服務(wù)器增減時(shí)的緩存重新分布。

Quorum W+R>N：抽屜原理，數(shù)據(jù)一致性的另一種解決方案

N: 復(fù)制的節(jié)點(diǎn)數(shù)，即一份數(shù)據(jù)被保存的份數(shù)。R: 成功讀操作的最小節(jié)點(diǎn)數(shù)，即每次讀取成功需要的份數(shù)。W: 成功寫操作的最小節(jié)點(diǎn)數(shù) ，即每次寫成功需要的份數(shù)。

所以 W+R>N的意思是：對于有N份拷貝的分布式系統(tǒng)，寫到W(W<=N)份成功算寫成功，讀R(R<=N)份數(shù)據(jù)算讀成功。

這三個(gè)因素決定了可用性，一致性和分區(qū)容錯(cuò)性。W+R>N可以保證數(shù)據(jù)的一致性(C)，W越大數(shù)據(jù)一致性越高。這個(gè)NWR模型把CAP的選擇權(quán)交給了用戶，讓用戶自己在功能，性能和成本效益之間進(jìn)行權(quán)衡。

對于一個(gè)分布式系統(tǒng)來說，N通常都大于3，也就說同一份數(shù)據(jù)需要保存在三個(gè)以上不同的節(jié)點(diǎn)上，以防止單點(diǎn)故障。W是成功寫操作的最小節(jié)點(diǎn)數(shù)，這里的寫成功可以理解為“同步”寫，比如N=3，W=1，那么只要寫成功一個(gè)節(jié)點(diǎn)就可以了，另外的兩份數(shù)據(jù)是通過異步的方式復(fù)制的。R是成功讀操作的最小節(jié)點(diǎn)數(shù)，讀操作為什么要讀多份數(shù)據(jù)呢?在分布式系統(tǒng)中，數(shù)據(jù)在不同的節(jié)點(diǎn)上可能存在著不一致的情況，我們可以選擇讀取多個(gè)節(jié)點(diǎn)上的不同版本，來達(dá)到增強(qiáng)一致性的目的。

NWR模型的一些設(shè)置會造成臟數(shù)據(jù)和版本沖突問題，所以一般要引入vector clock算法來解決這個(gè)問題。

需要保證系統(tǒng)中有max(N-W+1,N-R+1)個(gè)節(jié)點(diǎn)可用。

關(guān)于NWR模型，建議閱讀 分布式系統(tǒng)的事務(wù)處理，寫的很通俗易懂。

vector clock：時(shí)鐘向量，多版本數(shù)據(jù)修改

參見 分布式系統(tǒng)的事務(wù)處理，寫的很通俗易懂。

lease機(jī)制

chubby、zookeeper 獲得lease(租約)的節(jié)點(diǎn)得到系統(tǒng)的承諾：在有效期內(nèi)數(shù)據(jù)/節(jié)點(diǎn)角色等是有效的，不會變化的。

lease機(jī)制的特點(diǎn)：

• lease頒發(fā)過程只需要網(wǎng)絡(luò)可以單向通信，同一個(gè)lease可以被頒發(fā)者不斷重復(fù)向接受方發(fā)送。即使頒發(fā)者偶爾發(fā)送lease失敗，頒發(fā)者也可以簡單的通過重發(fā)的辦法解決。
• 機(jī)器宕機(jī)對lease機(jī)制的影響不大。如果頒發(fā)者宕機(jī)，則宕機(jī)的頒發(fā)者通常無法改變之前的承諾，不會影響lease的正確性。在頒發(fā)者機(jī)恢復(fù)后，如果頒發(fā)者恢復(fù)出了之前的lease 信息，頒發(fā)者可以繼續(xù)遵守lease的承諾。如果頒發(fā)者無法恢復(fù)lease信息，則只需等待一個(gè)最大的lease超時(shí)時(shí)間就可以使得所有的lease都失效，從而不破壞lease機(jī)制。
• lease機(jī)制依賴于有效期，這就要求頒發(fā)者和接收者的時(shí)鐘是同步的。(1)如果頒發(fā)者的時(shí)鐘比接收者的時(shí)鐘慢，則當(dāng)接收者認(rèn)為lease已經(jīng)過期的時(shí)候，頒發(fā)者依舊認(rèn)為lease有效。接收者可以用在lease到期前申請新的lease的方式解決這個(gè)問題。(2)如果頒發(fā)者的時(shí)鐘比接收者的時(shí)鐘快，則當(dāng)頒發(fā)者認(rèn)為lease已經(jīng)過期的時(shí)候，可能將lease頒發(fā)給其他節(jié)點(diǎn)，造成承諾失效，影響系統(tǒng)的正確性。對于這種時(shí)鐘不同步，實(shí)踐中的通常做法是將頒發(fā)者的有效期設(shè)置得比接收者的略大，只需大過時(shí)鐘誤差就可以避免對lease的有效性的影響。

工程中，常選擇的lease時(shí)長是10秒級別，這是一個(gè)經(jīng)過驗(yàn)證的經(jīng)驗(yàn)值，實(shí)踐中可以作為參考并綜合選擇合適的時(shí)長。

雙主問題(腦裂問題)

lease機(jī)制可以解決網(wǎng)絡(luò)分區(qū)問題造成的“雙主”問題，即所謂的“腦裂”現(xiàn)象。配置中心為一個(gè)節(jié)點(diǎn)發(fā)放lease，表示該節(jié)點(diǎn)可以作為primary節(jié)點(diǎn)工作。當(dāng)配置中心發(fā)現(xiàn)primary有問題時(shí)，只需要等到前一個(gè)primary的lease過期，就可以安全地頒發(fā)新的lease給新的primary節(jié)點(diǎn)，而不會出現(xiàn)“雙主”問題。在實(shí)際系統(tǒng)中，若用一個(gè)中心節(jié)點(diǎn)作為配置中心發(fā)送lease也有很大的風(fēng)險(xiǎn)。實(shí)際系統(tǒng)總是使用多個(gè)中心節(jié)點(diǎn)互為副本，成為一個(gè)小的集群，該小集群具有高可用性，對外提供頒發(fā)lease的功能。chubby和zookeeper都是基于這樣的設(shè)計(jì)。

chubby一般有五臺機(jī)器組成一個(gè)集群，可以部署成兩地三機(jī)房。chubby內(nèi)部的五臺機(jī)器需要通過Paxos協(xié)議選取一個(gè)chubby master機(jī)器，其它機(jī)器是chubby slave，同一時(shí)刻只有一個(gè)chubby master。chubby相關(guān)的數(shù)據(jù)，比如鎖信息，客戶端的session信息等都需要同步到整個(gè)集群，采用半同步的做法，超過一半的機(jī)器成功就可以回復(fù)客戶端。最后可以確保只有一個(gè)和原有的chubby master保持完全同步的chubby slave被選取為新的chubby master。

Gossip協(xié)議

Gossip用于P2P系統(tǒng)中自治節(jié)點(diǎn)獲悉對集群認(rèn)識(如集群的節(jié)點(diǎn)狀態(tài)，負(fù)載情況等)。系統(tǒng)中的節(jié)點(diǎn)定期互相八卦，很快八卦就在整個(gè)系統(tǒng)傳開了。A、B兩個(gè)節(jié)點(diǎn)八卦的方式主要是：A告訴B知道哪些人的什么八卦;B告訴A這些八卦里B知道哪些更新了;B更新A告訴他的八卦...... 說是自治系統(tǒng)，其實(shí)節(jié)點(diǎn)中還有一些種子節(jié)點(diǎn)。種子節(jié)點(diǎn)的作用主要是在有新節(jié)點(diǎn)加入系統(tǒng)時(shí)體現(xiàn)。新節(jié)點(diǎn)加入系統(tǒng)中，先與種子節(jié)點(diǎn)八卦，新節(jié)點(diǎn)獲得系統(tǒng)信息，種子節(jié)點(diǎn)知道系統(tǒng)中多了新節(jié)點(diǎn)。其他節(jié)點(diǎn)定期與種子節(jié)點(diǎn)八卦的時(shí)候就知道有新節(jié)點(diǎn)加入了。各個(gè)節(jié)點(diǎn)互相八卦的過程中，如果發(fā)現(xiàn)某個(gè)節(jié)點(diǎn)的狀態(tài)很長時(shí)間都沒更新，就認(rèn)為該節(jié)點(diǎn)已經(jīng)宕機(jī)了。

Dynamo使用了Gossip協(xié)議來做會員和故障檢測。

2PC、3PC、Paxos協(xié)議: 分布式事務(wù)的解決方案

分布式事務(wù)很難做，所以除非必要，一般來說都是采用最終一致性來規(guī)避分布式事務(wù)。

目前底層NoSQL存儲系統(tǒng)實(shí)現(xiàn)分布式事務(wù)的只有Google的系統(tǒng)，它在Bigtable之上用Java語言開發(fā)了一個(gè)系統(tǒng) Megastore，實(shí)現(xiàn)了兩階段鎖，并通過Chubby來避免兩階段鎖協(xié)調(diào)者宕機(jī)帶來的問題。Megastore實(shí)現(xiàn)目前只有簡單介紹，還沒有相關(guān)論文。

2PC

實(shí)現(xiàn)簡單，但是效率低，所有參與者需要block，throughput低;無容錯(cuò)，一個(gè)節(jié)點(diǎn)失敗整個(gè)事務(wù)失敗。如果第一階段完成后，參與者在第二階沒有收到?jīng)Q策，那么數(shù)據(jù)結(jié)點(diǎn)會進(jìn)入“不知所措”的狀態(tài)，這個(gè)狀態(tài)會block住整個(gè)事務(wù)。

3PC

改進(jìn)版的2PC，把2PC的第一個(gè)段break成了兩段: 詢問，然后再鎖資源，最后真正提交。3PC的核心理念是：在詢問的時(shí)候并不鎖定資源，除非所有人都同意了，才開始鎖資源。

3PC比2PC的好處是，如果結(jié)點(diǎn)處在P狀態(tài)(PreCommit)的時(shí)候發(fā)生了Fail/Timeout的問題，3PC可以繼續(xù)直接把狀態(tài)變成C狀態(tài)(Commit)，而2PC則不知所措。

不過3PC實(shí)現(xiàn)比較困難，而且無法處理網(wǎng)絡(luò)分離問題。如果preCommit消息發(fā)送后兩個(gè)機(jī)房斷開，這時(shí)候coordinator所在的機(jī)房會abort，剩余的participant會commit。

Paxos

Paxos的目的是讓整個(gè)集群的結(jié)點(diǎn)對某個(gè)值的變更達(dá)成一致。Paxos算法是一種基于消息傳遞的一致性算法。Paxos算法基本上來說是個(gè)民主選舉的算法——大多數(shù)的決定會成個(gè)整個(gè)集群的統(tǒng)一決定。

任何一個(gè)點(diǎn)都可以提出要修改某個(gè)數(shù)據(jù)的提案，是否通過這個(gè)提案取決于這個(gè)集群中是否有超過半數(shù)的結(jié)點(diǎn)同意(所以Paxos算法需要集群中的結(jié)點(diǎn)是單數(shù))。這個(gè)是Paxos相對于2PC和3PC最大的區(qū)別，在2f+1個(gè)節(jié)點(diǎn)的集群中，允許有f個(gè)節(jié)點(diǎn)不可用。

Paxos的分布式民主選舉方式，除了保證數(shù)據(jù)變更的一致性之外，還常用于單點(diǎn)切換，比如Master選舉。

Paxos協(xié)議的特點(diǎn)就是難，both 理解 and 實(shí)現(xiàn) :(

關(guān)于2PC，3PC和Paxos，強(qiáng)烈推薦閱讀 分布式系統(tǒng)的事務(wù)處理。

目前大部分支付系統(tǒng)其實(shí)還是在2PC的基礎(chǔ)上進(jìn)行自我改進(jìn)的。一般是引入一個(gè)差錯(cuò)處理器，進(jìn)行差錯(cuò)協(xié)調(diào)(回滾或者失敗處理)。

MVCC：多版本并發(fā)控制

這個(gè)是很多RDMS存儲引擎實(shí)現(xiàn)高并發(fā)修改的一個(gè)重要實(shí)現(xiàn)機(jī)制。具體可以參考：

1. 多版本并發(fā)控制(MVCC)在分布式系統(tǒng)中的應(yīng)用

2. MVCC (Oracle, Innodb, Postgres).pdf

Map-Reduce思想

1. 分而治之

2. 移動(dòng)數(shù)據(jù)不如移動(dòng)計(jì)算

如果計(jì)算節(jié)點(diǎn)和存儲節(jié)點(diǎn)位于不同的物理機(jī)器則計(jì)算的數(shù)據(jù)需要通過網(wǎng)絡(luò)傳輸，此種方式的開銷很大。另一種思路是，將計(jì)算盡量調(diào)度到與存儲節(jié)點(diǎn)在同一臺物理機(jī)器上的計(jì)算節(jié)點(diǎn)上進(jìn)行，這稱之為本地化計(jì)算。本地化計(jì)算是計(jì)算調(diào)度的一種重要優(yōu)化。

經(jīng)典論文和分布式系統(tǒng)學(xué)習(xí)

Dynamo

HBase

LSM Tree

• LSM(Log Structured Merge Trees)是B+ Tree一種改進(jìn)
• 犧牲了部分讀性能，用來大幅提高寫性能
• 思路：拆分樹(1)首先寫WAL，然后記錄數(shù)據(jù)到內(nèi)存中，構(gòu)建一顆有序子樹(memstore)(2)隨著子樹越來越大，內(nèi)存的子樹會flush到磁盤上(storefile)(3)讀取數(shù)據(jù)：必須遍歷所有的有序子樹(不知數(shù)據(jù)在哪棵子樹) (4) Compact：后臺線程對磁盤中的子樹進(jìn)行歸并，變成大樹(子樹多了讀得慢)

事實(shí)上，lucene的索引機(jī)制也類似HBase的LSM樹。也是寫的時(shí)候分別寫在單獨(dú)的segment，后臺進(jìn)行segement合并。