數(shù)據(jù)庫(kù)中數(shù)據(jù)模型的實(shí)例分析

數(shù)據(jù)庫(kù)中數(shù)據(jù)模型的實(shí)例分析，相信很多沒(méi)有經(jīng)驗(yàn)的人對(duì)此束手無(wú)策，為此本文總結(jié)了問(wèn)題出現(xiàn)的原因和解決方法，通過(guò)這篇文章希望你能解決這個(gè)問(wèn)題。

數(shù)據(jù)模型可以說(shuō)軟件開(kāi)發(fā)中最重要的部分，因?yàn)橛绊懼覀兊乃伎挤绞?、解題思路以及代碼的編寫(xiě)方式。多數(shù)應(yīng)用使用層層疊加的數(shù)據(jù)模型進(jìn)行構(gòu)建，對(duì)于每層數(shù)據(jù)模型的關(guān)鍵問(wèn)題是：它如何用低一層的數(shù)據(jù)模型來(lái)表示。

多數(shù)應(yīng)用程序開(kāi)發(fā)都使用面向?qū)ο缶幊痰木幊陶Z(yǔ)言來(lái)開(kāi)發(fā)，所以一個(gè)數(shù)據(jù)模型是否能夠很好表示對(duì)象以及對(duì)象之間的關(guān)系就成為我們選擇的標(biāo)準(zhǔn)。

對(duì)象由各類屬性組成，對(duì)象的關(guān)系通常有一對(duì)多/多對(duì)一和多對(duì)多。

關(guān)系模型

關(guān)系模型使用表、行、字段分別表示一類實(shí)體的集合、一個(gè)實(shí)體以及一個(gè)實(shí)體的一個(gè)屬性;在其中一個(gè)實(shí)體的字段中存儲(chǔ)另一實(shí)體的Id標(biāo)識(shí)來(lái)表示實(shí)體之間多對(duì)一的關(guān)系，使用單獨(dú)的關(guān)聯(lián)表存儲(chǔ)兩個(gè)實(shí)體的Id標(biāo)識(shí)來(lái)表示實(shí)體建多對(duì)多的關(guān)系。

關(guān)系模型具有強(qiáng)模式，必須在寫(xiě)數(shù)據(jù)前定義好，即寫(xiě)模式，類似編程語(yǔ)言的靜態(tài)(編譯時(shí))類型檢查。

下面的示例是Linked的一個(gè)簡(jiǎn)歷的關(guān)系型表示：

文檔模型

采用類似JSON的格式存儲(chǔ)，存儲(chǔ)的內(nèi)容是文檔型。利用JSON天然的嵌套關(guān)系可以靈活表示一對(duì)多的實(shí)體關(guān)系，當(dāng)然通過(guò)存儲(chǔ)文檔的Id，也可以表示多對(duì)一和多對(duì)多的關(guān)系。

相對(duì)于關(guān)系模型，文檔模型減少了應(yīng)用程序代碼和存儲(chǔ)層之間的阻抗不匹配，在一對(duì)多關(guān)系下，具有更好的局部性。

文檔模型具有讀時(shí)模式，對(duì)寫(xiě)入沒(méi)有模式要求。類似編程語(yǔ)言的動(dòng)態(tài)(運(yùn)行時(shí))類型檢查。

對(duì)于上面簡(jiǎn)歷的例子，使用文檔模型的表示如下：

圖模型

圖模型強(qiáng)調(diào)是對(duì)象之間的連接，當(dāng)應(yīng)用是圍繞眾多對(duì)象連接以及對(duì)這些連接進(jìn)行的查詢和計(jì)算時(shí)，就需要考慮使用圖模型的數(shù)據(jù)庫(kù)。

一個(gè)圖由頂點(diǎn)(表示的是實(shí)體)和邊(實(shí)體之間關(guān)系)組成，一個(gè)復(fù)雜的圖模型通常由數(shù)十億的頂點(diǎn)和千億的邊組成。

以下是社交網(wǎng)絡(luò)的一個(gè)示例：表示的是兩個(gè)人之間的以及居住地點(diǎn)。

每種數(shù)據(jù)模型都有其對(duì)應(yīng)的查詢語(yǔ)言，關(guān)系型使用SQL，而圖模型也有相應(yīng)的查詢語(yǔ)言來(lái)描述圖模型的特點(diǎn)，但是還沒(méi)有形成業(yè)界標(biāo)準(zhǔn)。

存儲(chǔ)引擎

上面我們熟悉了數(shù)據(jù)模型，但是了解數(shù)據(jù)內(nèi)部的存儲(chǔ)和檢索原理，對(duì)于我們?cè)O(shè)計(jì)和開(kāi)發(fā)應(yīng)用以及數(shù)據(jù)庫(kù)的選型也是非常有幫助的。

數(shù)據(jù)庫(kù)的主要功能是存儲(chǔ)數(shù)據(jù)以及后續(xù)進(jìn)行查詢和更新，目前主要有兩大類數(shù)據(jù)庫(kù)：傳統(tǒng)關(guān)系型數(shù)據(jù)庫(kù)(面向頁(yè)面 page-oriented) 和  NoSQL數(shù)據(jù)庫(kù)(基于日志結(jié)構(gòu)log-structured)。

面向頁(yè)面

B樹(shù)是幾乎是數(shù)據(jù)庫(kù)標(biāo)準(zhǔn)的索引實(shí)現(xiàn)，B數(shù)將數(shù)據(jù)庫(kù)分解成固定大小的塊或頁(yè)面，通常在4k-32k范圍，一次只能讀取或?qū)懭胍粋€(gè)頁(yè)面。這種設(shè)計(jì)更接近與底層的硬件，因?yàn)榇疟P(pán)也是由固定大小的塊組成的。

每個(gè)頁(yè)面都可以使用地址來(lái)標(biāo)識(shí)，一個(gè)頁(yè)面引用另一個(gè)頁(yè)面，類似于指針，但是在磁盤(pán)而不是在內(nèi)存中，如圖所示：

在B樹(shù)的頁(yè)面中對(duì)子頁(yè)面的引用的數(shù)量稱為分支因子，分支因子取決于頁(yè)面大小和索引key的大小，分支因子越大越好。(分支因子為500的4KB頁(yè)面的四級(jí)樹(shù)可以存儲(chǔ)多大256TB)

數(shù)據(jù)查詢時(shí)，從根頁(yè)面(通常緩存在內(nèi)存)出發(fā)，根據(jù)頁(yè)面引用尋找滿足條件范圍的頁(yè)面，一直到葉子節(jié)點(diǎn)。

數(shù)據(jù)更新時(shí)，定位到葉子結(jié)點(diǎn)，用新數(shù)據(jù)覆蓋磁盤(pán)的頁(yè)面。

數(shù)據(jù)插入和刪除時(shí)，會(huì)涉及到頁(yè)面的拆分和合并，來(lái)保持B樹(shù)的平衡

為了保證數(shù)據(jù)查詢和寫(xiě)入的高性能，數(shù)據(jù)庫(kù)通常會(huì)對(duì)頁(yè)面數(shù)據(jù)進(jìn)行內(nèi)存緩存，當(dāng)數(shù)據(jù)有更新時(shí)，不會(huì)立即更新磁盤(pán)數(shù)據(jù)，而是先更新內(nèi)存緩存的頁(yè)面數(shù)據(jù)，同步追加寫(xiě)入WAL日志(write-ahead-log)，異步將內(nèi)存中的臟頁(yè)刷到磁盤(pán)上(將磁盤(pán)隨機(jī)寫(xiě)變?yōu)轫樞驅(qū)?。當(dāng)數(shù)據(jù)庫(kù)崩潰后恢復(fù)時(shí)，這個(gè)日志用來(lái)是B樹(shù)恢復(fù)到一致的狀態(tài)。

日志結(jié)構(gòu)

基于日志結(jié)構(gòu)的存儲(chǔ)模式，每次數(shù)據(jù)新增或更新時(shí)，僅僅將數(shù)據(jù)追加到特定日志文件中，當(dāng)文件超過(guò)一定大小時(shí)，則打開(kāi)一個(gè)新的文件寫(xiě)入。

每個(gè)日志結(jié)構(gòu)存儲(chǔ)段都是一系列鍵值對(duì)，但是為了后續(xù)便于查詢數(shù)據(jù)，要求鍵值對(duì)在文件中按照鍵排序，這種排序的字符串表(Sorted String  Table)稱為SSTable。

為了保證日志文件保持在一定的個(gè)數(shù)，多個(gè)文件段進(jìn)行合并(歸并算法)，當(dāng)出現(xiàn)多個(gè)同一鍵值時(shí)，用新的值覆蓋老的，保證一個(gè)合并段同一個(gè)鍵出現(xiàn)一次。

內(nèi)存中維護(hù)者鍵到日志文件的索引，該索引是稀疏的，每幾千個(gè)字節(jié)的段文件就有一個(gè)鍵就足夠了，因?yàn)閹浊ё止?jié)可以很快被掃描。(可以將部分記錄分組到塊，壓縮寫(xiě)入磁盤(pán))

如何構(gòu)建和維護(hù)SSTable呢(保證按照鍵排序存儲(chǔ))

• 寫(xiě)入數(shù)據(jù)時(shí)(新增、刪除、更改)，將其添加到內(nèi)存中的平衡樹(shù)結(jié)構(gòu)(如紅黑樹(shù))，這個(gè)內(nèi)存樹(shù)稱為內(nèi)存表(memtable);

• 為了避免丟失數(shù)據(jù)，寫(xiě)入內(nèi)存表的同時(shí)會(huì)通過(guò)追加的方式寫(xiě)入WAL日志(數(shù)據(jù)庫(kù)崩潰恢復(fù)時(shí)使用);

• 當(dāng)內(nèi)存表大于某個(gè)閾值(通常為幾兆字節(jié))時(shí)，將其作為SSTable文件寫(xiě)入磁盤(pán)。新的SSTable文件成為數(shù)據(jù)庫(kù)的最新部分。

數(shù)據(jù)查詢時(shí)，首先嘗試在內(nèi)存表中查找，然后在多個(gè)文件段中進(jìn)行查找。(通過(guò)合并文件段使其維持在一定的個(gè)數(shù)，保證查找效率)

這種基于合并和壓縮排序文件原理的存儲(chǔ)引擎通常被稱為L(zhǎng)SM存儲(chǔ)引擎。

當(dāng)查找不存在的鍵時(shí)，LSM樹(shù)算法可能會(huì)很慢。為了優(yōu)化這種訪問(wèn)，通常使用額外的Bloom過(guò)濾器。

LSM樹(shù)的基本思想

保存一系列在后臺(tái)合并的SSTables，即使數(shù)據(jù)集比可用內(nèi)存大得多，仍能繼續(xù)工作。由于數(shù)據(jù)按序存儲(chǔ)，因此可以高效地執(zhí)行范圍查詢(掃描所有高于某些最小值和最高值的所有鍵)，并且磁盤(pán)寫(xiě)入時(shí)連續(xù)的，所以可以支持非常高的寫(xiě)入吞吐量。

事務(wù)

在數(shù)據(jù)庫(kù)系統(tǒng)中，會(huì)遇到各種問(wèn)題：

• 數(shù)據(jù)庫(kù)軟件、硬件可能在任意時(shí)刻故障(包括寫(xiě)操作進(jìn)行一半時(shí))

• 應(yīng)用程序任何時(shí)刻都可能崩潰(包括一系列操作的中間)

• 網(wǎng)絡(luò)中斷會(huì)切斷應(yīng)用與數(shù)據(jù)庫(kù)的連接，或數(shù)據(jù)庫(kù)之間的連接

• 多個(gè)應(yīng)用可能會(huì)同時(shí)寫(xiě)入數(shù)據(jù)庫(kù)，覆蓋彼此的修改

• 應(yīng)用可能會(huì)讀取到無(wú)意義的數(shù)據(jù)，因?yàn)閿?shù)據(jù)只更新了一部分

• 應(yīng)用質(zhì)檢的競(jìng)爭(zhēng)條件可能導(dǎo)致各種非預(yù)期結(jié)果

事務(wù)一直是簡(jiǎn)化這些問(wèn)題的首選機(jī)制。事務(wù)是應(yīng)用程序?qū)⒍鄠€(gè)讀寫(xiě)操作組合成一個(gè)邏輯單元的一種方式。從概念上講，事務(wù)中的所有讀寫(xiě)操作被視為單個(gè)操作來(lái)執(zhí)行：整個(gè)事務(wù)要么成功，要么失敗后回滾。如果失敗，應(yīng)用可以安全地重試。對(duì)于事務(wù)來(lái)說(shuō)，應(yīng)用的錯(cuò)誤處理簡(jiǎn)單多了，不用擔(dān)心部分失敗的情況了。

事務(wù)提供的安全保障，由ACID來(lái)描述。即原子性Atomicity,一致性Consistency，隔離性Isolation，持久性Durability，旨在為數(shù)據(jù)庫(kù)中的容錯(cuò)性建立精確的術(shù)語(yǔ)。

單對(duì)象 vs 多對(duì)象

事務(wù)通常被理解為，將對(duì)多個(gè)對(duì)象上的多個(gè)操作合并為一個(gè)執(zhí)行單元的機(jī)制。但許多分布式數(shù)據(jù)庫(kù)只提供了單對(duì)象的原子性和隔離性(原子性通過(guò)同步寫(xiě)日志實(shí)現(xiàn)崩潰恢復(fù);隔離性通過(guò)每個(gè)對(duì)象上鎖實(shí)現(xiàn)單線程訪問(wèn))，以及更復(fù)雜的原子操作，如自增  和 CAS。所以要注意這一點(diǎn)，看是否滿足自己的應(yīng)用場(chǎng)景。

多對(duì)象事務(wù)，除了要處理復(fù)雜原子性和隔離性，分布式場(chǎng)景下，還會(huì)涉及到跨分區(qū)(不能分區(qū)可能在不同的機(jī)器上)，即分布式事務(wù)。

隔離級(jí)別

如果兩個(gè)事務(wù)不觸及相同的數(shù)據(jù)，它們可以安全地并行執(zhí)行，因?yàn)閮烧叨疾灰蕾噷?duì)方。當(dāng)一個(gè)事務(wù)讀取另一個(gè)事務(wù)同時(shí)修改的數(shù)據(jù)，或者兩個(gè)事務(wù)試圖同時(shí)修改相同的數(shù)據(jù)，并發(fā)問(wèn)題才會(huì)出現(xiàn)。

并發(fā)bug很難通過(guò)測(cè)試找到，因?yàn)檫@樣的錯(cuò)誤只有在特殊時(shí)機(jī)下才會(huì)觸發(fā)，很難重現(xiàn)。出于這個(gè)原因，數(shù)據(jù)庫(kù)一直試圖通過(guò)提供事務(wù)隔離來(lái)隱藏應(yīng)用開(kāi)發(fā)者的并發(fā)問(wèn)題。事務(wù)隔離級(jí)別越強(qiáng)越能夠避免發(fā)生的并發(fā)問(wèn)題，比如可序列化保證事務(wù)的效果與串行執(zhí)行是一樣的，但這意味著并發(fā)性能的犧牲。所以數(shù)據(jù)庫(kù)系統(tǒng)通常使用較弱的隔離級(jí)別，來(lái)防止一部分并發(fā)問(wèn)題，而不是全部，所以了解這些對(duì)于開(kāi)發(fā)出正確的應(yīng)用非常重要。

臟寫(xiě)

臟寫(xiě)是指一個(gè)事務(wù)覆蓋另一個(gè)事務(wù)未提交的數(shù)據(jù)，現(xiàn)有的隔離級(jí)別都會(huì)保證沒(méi)有臟寫(xiě)。數(shù)據(jù)庫(kù)通常使用行鎖來(lái)防止臟寫(xiě)。

臟讀

臟讀是指一個(gè)事務(wù)寫(xiě)了部分?jǐn)?shù)據(jù)，未提交，這是另一個(gè)事務(wù)讀取到了這部分未提交的數(shù)據(jù)。

不可重復(fù)讀

同一個(gè)事務(wù)兩次讀取的數(shù)據(jù)(讀偏差) 或者 讀取的記錄數(shù)(幻讀)不一致

丟失更新

兩個(gè)事務(wù)同時(shí)讀取數(shù)據(jù)，并進(jìn)行更新，兩個(gè)事務(wù)都更新成功，更新邏輯都是基于原先讀取的值，但是事務(wù)提交會(huì)改變先前讀取的值，導(dǎo)致丟失更新。典型的場(chǎng)景就是 讀  -> 改 -> 寫(xiě)。

寫(xiě)偏差

可以將寫(xiě)入偏差視為丟失更新問(wèn)題的一般化。如果兩個(gè)事務(wù)讀取相同的對(duì)象，然后更新其中的一些對(duì)象(不同的事務(wù)可能更新不同的對(duì)象)，則可能發(fā)生寫(xiě)入偏差。

讀已提交

讀已提交提供兩種保證

• 從數(shù)據(jù)庫(kù)讀時(shí)，只能看到已經(jīng)提交的數(shù)據(jù)(沒(méi)有臟讀)

• 寫(xiě)入數(shù)據(jù)庫(kù)時(shí)，只能覆蓋已經(jīng)寫(xiě)入的數(shù)據(jù)(沒(méi)有臟寫(xiě))

可重復(fù)讀/快照隔離

支持快照隔離的數(shù)據(jù)庫(kù)保留了一個(gè)對(duì)象的不同的提交版本，因?yàn)楦鞣N正在進(jìn)行的事務(wù)可能需要看到數(shù)據(jù)庫(kù)在不同時(shí)間點(diǎn)的狀態(tài)。這種技術(shù)被稱為多版本并發(fā)控制(MVCC，multi-version  concurrency control)。

當(dāng)一個(gè)事務(wù)開(kāi)始，它被賦予一個(gè)唯一個(gè)的，永遠(yuǎn)增長(zhǎng)的事務(wù)ID(txid)。每當(dāng)事務(wù)向數(shù)據(jù)庫(kù)寫(xiě)入任何內(nèi)容時(shí)，它所寫(xiě)入的數(shù)據(jù)都會(huì)被標(biāo)記上寫(xiě)入者的事務(wù)ID。

一個(gè)事務(wù)能查到一個(gè)對(duì)象，滿足以下兩個(gè)條件：

• 讀事務(wù)開(kāi)始時(shí)，創(chuàng)建該對(duì)象的事務(wù)已經(jīng)提交

• 對(duì)象未被標(biāo)記為刪除，或如果被標(biāo)記為刪除，請(qǐng)求刪除的事務(wù)在讀事務(wù)開(kāi)始時(shí)尚未提交

對(duì)于丟失更新和有數(shù)據(jù)交叉的寫(xiě)偏差，數(shù)據(jù)庫(kù)可以結(jié)合快照隔，可以自動(dòng)檢測(cè)到丟失更新，中止相應(yīng)的事務(wù)。但是MySQL/InnoDB的可重復(fù)讀并不會(huì)檢測(cè)丟失更新。有些作者認(rèn)為，數(shù)據(jù)能防止丟失更新才能稱得上快照隔離，所以這種定義下，MySQL并不提供快照隔離。

MySQL/InnoDB可重復(fù)讀隔離級(jí)別下，可以使用 鎖定讀 (select for update)或者 比較并設(shè)置CAS 來(lái)避免丟失更新。

需要注意的是，如果數(shù)據(jù)庫(kù)允許where字句從舊快照中讀取，則此語(yǔ)句可能無(wú)法防止丟失更新，因?yàn)榧词拱l(fā)生了另一個(gè)并發(fā)寫(xiě)入，where條件也可能是真的。

序列化

但對(duì)于寫(xiě)入數(shù)據(jù)無(wú)交叉的寫(xiě)偏差，只能通過(guò)序列化的隔離級(jí)別來(lái)避免，但是可以在應(yīng)用層面通過(guò) 物化沖突的方式，人為的在數(shù)據(jù)庫(kù)中引入一個(gè)鎖對(duì)象。

序列化隔離級(jí)別有三種實(shí)現(xiàn)方式：

• 字面意義的串行順序執(zhí)行事務(wù)

• 兩階段鎖定(2PL，two-phase  locking)，通過(guò)對(duì)讀操作對(duì)象加共享鎖，對(duì)寫(xiě)操作對(duì)象加獨(dú)占鎖實(shí)現(xiàn)，共享鎖可以升級(jí)為獨(dú)占鎖。共享鎖之間不互斥，共享鎖與獨(dú)占鎖 以及  獨(dú)占鎖之間互斥。同時(shí)數(shù)據(jù)庫(kù)會(huì)自動(dòng)檢測(cè)事務(wù)之間的思索，并中止一個(gè)。兩階段是一種所謂的悲觀并發(fā)控制機(jī)制。

• 樂(lè)觀并發(fā)控制技術(shù)，可序列化的快照隔離SSI(serializable snapshot  isolation)，是一種樂(lè)觀的并發(fā)控制機(jī)制，讀寫(xiě)數(shù)據(jù)時(shí)并不加鎖，而是在事務(wù)提交時(shí)，通過(guò)特定的算法檢測(cè)寫(xiě)入之間的序列化沖突，并確定要中止哪些事務(wù)。好處是讀和寫(xiě)不相互阻塞，只讀查詢運(yùn)行在一致的快照上，對(duì)于讀取繁重的場(chǎng)景非常有吸引力。但是中止率顯著影響SSI整體的表現(xiàn)。長(zhǎng)時(shí)間讀取和寫(xiě)入數(shù)據(jù)的事務(wù)很可能會(huì)發(fā)生沖突并中式，因?yàn)镾SI要求同時(shí)讀寫(xiě)的事務(wù)盡量短。

分布式事務(wù)

在多對(duì)象事務(wù)中，如果不同對(duì)象存在不同的分區(qū)中，則就需要處理分布式事務(wù)。提到分布式事務(wù)，就不得不介紹兩階段提交，兩階段提交是分布式事務(wù)的基本思想。

兩階段提交

兩階段提交2PC(two-phase  commit)是一種用于實(shí)現(xiàn)跨多個(gè)節(jié)點(diǎn)的原子事務(wù)提交的算法。可以在數(shù)據(jù)庫(kù)內(nèi)部使用，也可以以XA事務(wù)的形式對(duì)應(yīng)用可用。

兩階段提交引入了協(xié)調(diào)者的角色，整體分為兩個(gè)階段，具體的過(guò)程如下：

• 當(dāng)應(yīng)用想要啟動(dòng)一個(gè)分布式事務(wù)時(shí)，它向協(xié)調(diào)者請(qǐng)求一個(gè)全局唯一的事務(wù)ID。

• 應(yīng)用在每個(gè)參與者啟動(dòng)單節(jié)點(diǎn)事務(wù)，每個(gè)單節(jié)點(diǎn)事務(wù)都帶上這個(gè)全局事務(wù)ID。所有的讀寫(xiě)都是在單節(jié)點(diǎn)事務(wù)中各自完成的。如果這個(gè)階段出現(xiàn)任何問(wèn)題，則協(xié)調(diào)者或任何參與者都可以中止。

• 當(dāng)應(yīng)用準(zhǔn)備提交時(shí)，協(xié)調(diào)者向所有參與者發(fā)送一個(gè)準(zhǔn)備請(qǐng)求，并帶上全局事務(wù)ID。如果任意一個(gè)請(qǐng)求失敗或超時(shí)，則協(xié)調(diào)者向所有參與者發(fā)送針對(duì)該事務(wù)ID的中止請(qǐng)求。

• 參與者收到準(zhǔn)備請(qǐng)求時(shí)，需要確保在任何情況下都的確可以提交事務(wù)。這包括所有事務(wù)數(shù)據(jù)寫(xiě)入磁盤(pán)(出現(xiàn)故障，電源故障，或磁盤(pán)空間不足都不能是稍后拒絕提交的理由)以及檢查是否存在任何額沖突或違反約束。一旦作出承諾，就不允許反悔。

• 當(dāng)協(xié)調(diào)者收到所有準(zhǔn)備請(qǐng)求的答復(fù)時(shí)，會(huì)就提交或中止事務(wù)作出明確的決定(只有所有參與者贊成的情況下才會(huì)提交)。協(xié)調(diào)者必須吧這個(gè)決定寫(xiě)到磁盤(pán)的事務(wù)日志中。

• 一旦協(xié)調(diào)者的決定落盤(pán)，提交或放棄請(qǐng)求會(huì)發(fā)送給所有參與者。如果請(qǐng)求超時(shí)或失敗，協(xié)調(diào)者必須永遠(yuǎn)保持重試。

兩階段提交固有的成本：由于崩潰恢復(fù)所需的強(qiáng)制刷盤(pán)以及額外的網(wǎng)絡(luò)往返，另外整個(gè)過(guò)程會(huì)進(jìn)行資源的鎖定。

Percolator

Percolator是由Google公司開(kāi)發(fā)的、為大數(shù)據(jù)集群進(jìn)行增量處理更新的系統(tǒng)，主要用于google網(wǎng)頁(yè)搜索索引服務(wù)。使用基于Percolator的增量處理系統(tǒng)代替原有的批處理索引系統(tǒng)后，Google在處理同樣數(shù)據(jù)量的文檔時(shí)，將文檔的平均搜索延時(shí)降低了50%。

Percolator  是一個(gè)無(wú)中心化(沒(méi)有協(xié)調(diào)者)的兩階段提交，基于BigTable的單行事務(wù)，實(shí)現(xiàn)了跨行的事務(wù)引擎。另外借助BigTable的多時(shí)間戳版本，可以實(shí)現(xiàn)快照隔離級(jí)別。

Percolator依賴中心的授時(shí)器，沒(méi)有單點(diǎn) Coordinator 的角色，交由所有客戶端來(lái)協(xié)調(diào)上鎖協(xié)議，但是趕上崩潰鎖會(huì)泄露。Percolator  選擇了惰性地回收泄露的鎖：其他客戶端在 Get() 到這行數(shù)據(jù)時(shí)，如果遇到鎖，則選擇等待退避重試，或者清理鎖。

但是由于Percolator使用樂(lè)觀鎖檢測(cè)機(jī)制，對(duì)于熱點(diǎn)數(shù)據(jù)的并發(fā)更新不友好。我覺(jué)得這一點(diǎn)可以通過(guò)在Percolator之上實(shí)現(xiàn)悲觀鎖機(jī)制來(lái)解決。

分區(qū)

分區(qū)(partitions)也叫分片(sharding)，是將數(shù)據(jù)集進(jìn)行拆分成多個(gè)分區(qū)，每個(gè)分區(qū)存儲(chǔ)在不同的機(jī)器上，擴(kuò)展了整體的存儲(chǔ)量，提高了寫(xiě)入和讀取的性能。但也帶來(lái)了新的困難，數(shù)據(jù)庫(kù)要支持跨分區(qū)的寫(xiě)入和讀取。

分區(qū)方式

分區(qū)的目標(biāo)是將數(shù)據(jù)和查詢負(fù)載均勻的分布在各個(gè)節(jié)點(diǎn)上。如果分區(qū)是不公平的，或者沒(méi)有考慮熱點(diǎn)數(shù)據(jù)，那么一些分區(qū)比其他分區(qū)有更多的數(shù)據(jù)或查詢，我們稱之為偏斜(skew)。數(shù)據(jù)分區(qū)通常基于Key進(jìn)行拆分，在考慮數(shù)據(jù)偏斜的情況，要根據(jù)數(shù)據(jù)庫(kù)的特定的分區(qū)算法，特別注意Key的設(shè)計(jì)。

根據(jù)Key的范圍分區(qū)  為每個(gè)分區(qū)指定一塊連續(xù)的Key范圍，分區(qū)Key的邊界一般由數(shù)據(jù)庫(kù)自動(dòng)選擇。好處是范圍掃描非常簡(jiǎn)單。但是如果Key的設(shè)計(jì)不合理，會(huì)到熱點(diǎn)數(shù)據(jù)，影響查詢效率。

根據(jù)Key的散列分區(qū) 通過(guò)一個(gè)散列函數(shù)對(duì)Key進(jìn)行計(jì)算后，再進(jìn)行分區(qū)。這樣可以消除偏斜和熱點(diǎn)的風(fēng)險(xiǎn)，但是失去了原有Key的范圍查詢的屬性。

有些數(shù)據(jù)庫(kù)，如Cassandra，采取了折中的策略，使用多個(gè)列組成的復(fù)合主鍵來(lái)聲明。鍵中只有第一列會(huì)作為散列的依據(jù)，而其他列則被用作Cassandra的SSTables中排序數(shù)據(jù)的連接索引。盡管查詢無(wú)法在復(fù)合主鍵的第一列中按掃描掃表，但如果第一列已經(jīng)指定了固定值，則可以對(duì)該鍵的其他列執(zhí)行有效的范圍掃描。組合索引的方法為一對(duì)多關(guān)系提供了一個(gè)優(yōu)雅的數(shù)據(jù)模型。

索引構(gòu)建

上面我們討論了主鍵的分區(qū)策略，實(shí)際情況上輔助索引/二級(jí)索引也是很有必要的，特別是在關(guān)系模型中。

輔助索引的構(gòu)建方式有兩種：本地索引和全局索引

本地索引  文檔分區(qū)所以，在這種索引方法中，每個(gè)分區(qū)是完全獨(dú)立的，每個(gè)分區(qū)維護(hù)自己的二級(jí)索引，僅覆蓋該分區(qū)中的文檔。當(dāng)數(shù)據(jù)寫(xiě)入時(shí)(添加、刪除、更新)，只需要處理分區(qū)內(nèi)數(shù)據(jù)的索引更新。數(shù)據(jù)查詢時(shí)，則需要將查詢發(fā)送到所有的分區(qū)，并合并所有返回的結(jié)果。

這種查詢分區(qū)數(shù)據(jù)庫(kù)的方法有時(shí)被稱為分散/聚集(scatter/gather)，并且可能會(huì)是二級(jí)索引上的讀取查詢相當(dāng)昂貴。即使并行查詢分區(qū)，已容易導(dǎo)致尾部延遲放大。MongoDB、Cassandra、ElasticSearch、SolrCloud都是使用這種文檔分區(qū)二級(jí)索引。

全局索引  關(guān)鍵詞分區(qū)，這種索引方法跟主鍵分區(qū)的方式是一樣的。相對(duì)于文檔分區(qū)索引，讀取更有效率，不需要分散/聚集所有分區(qū)，客戶端只需要向包含關(guān)鍵詞的分區(qū)發(fā)出請(qǐng)求。缺點(diǎn)在于寫(xiě)入速度較慢且較為復(fù)雜，因?yàn)閷?xiě)入單個(gè)文檔可能會(huì)影響索引的多個(gè)分區(qū)。

理想情況下，索引總是最新的。寫(xiě)入數(shù)據(jù)庫(kù)的每個(gè)文檔都會(huì)立即反映在索引中。在基于關(guān)鍵詞的全局索引中，這需要跨分區(qū)的分布式事務(wù)，并不是所有的數(shù)據(jù)庫(kù)都支持。在實(shí)踐中，對(duì)全局二級(jí)索引的更新通常是異步的。

分區(qū)再平衡

隨著數(shù)據(jù)集大小增加、查詢吞吐量的增加，需要更多的機(jī)器來(lái)處理。這些都需要數(shù)據(jù)和請(qǐng)求從一個(gè)節(jié)點(diǎn)移動(dòng)到另一個(gè)節(jié)點(diǎn)，這一過(guò)程稱為再平衡(reblancing)。

再平衡通常要滿足以下幾點(diǎn)要求：

• 再平衡之后，負(fù)載(數(shù)據(jù)存儲(chǔ)、讀取和寫(xiě)入請(qǐng)求)應(yīng)該在集群中的節(jié)點(diǎn)之間公平地共享

• 再平衡發(fā)生時(shí)，數(shù)據(jù)庫(kù)應(yīng)該繼續(xù)接受讀取和寫(xiě)入

• 節(jié)點(diǎn)之間只移動(dòng)必須的數(shù)據(jù)，以便快速再平衡，并減少網(wǎng)絡(luò)和磁盤(pán)I/O負(fù)載

平衡策略可以分為幾種：固定數(shù)量的分區(qū)、動(dòng)態(tài)數(shù)量的分區(qū)和按節(jié)點(diǎn)比例分區(qū)

固定數(shù)量的分區(qū)  創(chuàng)建比節(jié)點(diǎn)更多的分區(qū)，并為每個(gè)節(jié)點(diǎn)分配多個(gè)分區(qū)。如果一個(gè)節(jié)點(diǎn)被添加到集群中，新節(jié)點(diǎn)可以從當(dāng)前每個(gè)節(jié)點(diǎn)中竊取一些分區(qū)，直到分區(qū)再次公平分配。ElasticSearch使用這種方式分區(qū)策略。

只有分區(qū)在節(jié)點(diǎn)間移動(dòng)，分區(qū)的數(shù)量不會(huì)改變，鍵所對(duì)應(yīng)的分區(qū)也不會(huì)改變，唯一改變的是分區(qū)所在的節(jié)點(diǎn)。這種變更不是實(shí)時(shí)的(網(wǎng)絡(luò)上傳輸數(shù)據(jù)需要時(shí)間)，傳輸過(guò)程中，原有分區(qū)仍然會(huì)接手讀寫(xiě)請(qǐng)求。

分區(qū)的數(shù)量通常在數(shù)據(jù)庫(kù)第一次建立時(shí)確定，之后不會(huì)改變。每個(gè)分區(qū)包含了總數(shù)據(jù)量固定比率的數(shù)據(jù)，因此每個(gè)分區(qū)的大小與集群中的數(shù)據(jù)總量成比例增長(zhǎng)。如果數(shù)據(jù)集的總大小難以預(yù)估，選擇正確的分區(qū)數(shù)是困難的。分區(qū)太大，再平衡和節(jié)點(diǎn)故障恢復(fù)變得昂貴;分區(qū)太小，則會(huì)產(chǎn)生太多的開(kāi)銷。

動(dòng)態(tài)數(shù)量的分區(qū)  對(duì)于使用鍵范圍進(jìn)行分區(qū)的數(shù)據(jù)庫(kù)，具有固定邊界的固定數(shù)量的分區(qū)將非常不方便：如果出現(xiàn)邊界錯(cuò)誤，則可能會(huì)導(dǎo)致某些分區(qū)的沒(méi)有數(shù)據(jù)。按鍵范圍進(jìn)行分區(qū)的數(shù)據(jù)庫(kù)通常會(huì)動(dòng)態(tài)創(chuàng)建分區(qū)。

當(dāng)分區(qū)增長(zhǎng)到超過(guò)配置的大小時(shí)，會(huì)被拆分成兩個(gè)分區(qū)，每個(gè)分區(qū)約占一半的數(shù)據(jù)。動(dòng)態(tài)分區(qū)的優(yōu)點(diǎn)是分區(qū)數(shù)量適應(yīng)總數(shù)據(jù)量，能夠平衡各方面的開(kāi)銷。HBase和MongoDB采用的就是這種策略。

數(shù)據(jù)集開(kāi)始時(shí)很小，直到達(dá)到第一個(gè)分區(qū)的分隔點(diǎn)，所有寫(xiě)入操作都必須由單個(gè)節(jié)點(diǎn)處理，而其他節(jié)點(diǎn)處于空閑狀態(tài)。為了解決這個(gè)問(wèn)題，HBase和MongoDB允許在一個(gè)空的數(shù)據(jù)庫(kù)上配置一組初始分區(qū)(預(yù)分隔，pre-splitting)。在鍵范圍分區(qū)的情況下，預(yù)分隔需要提前知道鍵時(shí)如何分配的。

按照節(jié)點(diǎn)比例分區(qū)  分區(qū)數(shù)與節(jié)點(diǎn)數(shù)量成正比，即每個(gè)節(jié)點(diǎn)具有固定數(shù)量的分區(qū)。每個(gè)分區(qū)的大小與數(shù)據(jù)集大小成比例的增長(zhǎng)。當(dāng)增加節(jié)點(diǎn)時(shí)，隨機(jī)選擇固定數(shù)量的現(xiàn)有分區(qū)進(jìn)行拆分，然后占有這些拆分分區(qū)中的每個(gè)分區(qū)的一半。

請(qǐng)求路由

現(xiàn)在我們已經(jīng)數(shù)據(jù)集分割到多個(gè)節(jié)點(diǎn)上運(yùn)行的多個(gè)分片上，客戶端發(fā)起請(qǐng)求時(shí)，如何知道連接哪個(gè)結(jié)點(diǎn)。隨著分區(qū)再平衡，分區(qū)對(duì)節(jié)點(diǎn)的分配也發(fā)生變化。

不僅限于數(shù)據(jù)庫(kù)，這個(gè)問(wèn)題可以概括為服務(wù)發(fā)現(xiàn)(service discovery)，通常有以下三種方案：

• 允許客戶端連接任何節(jié)點(diǎn)，如果該節(jié)點(diǎn)恰巧擁有請(qǐng)求的分區(qū)，則直接處理該請(qǐng)求;否則將請(qǐng)求轉(zhuǎn)發(fā)到適當(dāng)?shù)墓?jié)點(diǎn)，接收結(jié)果并返回給客戶端。

• 客戶端發(fā)送請(qǐng)求到路由層，它決定了應(yīng)該處理請(qǐng)求的節(jié)點(diǎn)，并相應(yīng)的轉(zhuǎn)發(fā)。

• 客戶端知道分區(qū)和節(jié)點(diǎn)的分配，直接連接到適當(dāng)?shù)墓?jié)點(diǎn)。

以上問(wèn)題的關(guān)鍵在于：做出路由決策的組件如何了解分區(qū)-節(jié)點(diǎn)之間的分配關(guān)系變化?這是一個(gè)具有挑戰(zhàn)性的問(wèn)題，因?yàn)樾枰械膮⑴c者達(dá)成一致。

很多分布式系統(tǒng)都依賴于一個(gè)獨(dú)立的協(xié)調(diào)服務(wù)，比如ZooKeeper來(lái)跟蹤集群元數(shù)據(jù)。

• 每個(gè)節(jié)點(diǎn)在ZooKeeper上注冊(cè)自己，ZooKeeper維護(hù)分區(qū)到節(jié)點(diǎn)的可靠映射

• 路由層可以在ZooKeeper訂閱此信息，當(dāng)分區(qū)分配發(fā)生變化能實(shí)時(shí)感知

復(fù)制

復(fù)制意味著在通過(guò)網(wǎng)絡(luò)連接的多臺(tái)機(jī)器上保留相同數(shù)據(jù)的副本，復(fù)制數(shù)據(jù)能帶來(lái)以下的好處：

• 提高可用性，即使系統(tǒng)的一部分出現(xiàn)故障，系統(tǒng)也能繼續(xù)工作

• 擴(kuò)展可以接受讀請(qǐng)求的機(jī)器數(shù)量，從而提高讀取吞吐量

• 使得數(shù)據(jù)與用戶再地理上接近，從而減少延遲

復(fù)制的困難之處在于處理復(fù)制數(shù)據(jù)的變更。目前流行有三種變更復(fù)制算法：?jiǎn)晤I(lǐng)導(dǎo)者(single leader)，多領(lǐng)導(dǎo)(multi  leader)和無(wú)領(lǐng)導(dǎo)者(leaderless)，幾乎所有的分布式數(shù)據(jù)庫(kù)都使用這三種方法之一。

單領(lǐng)導(dǎo)者復(fù)制過(guò)程：

• 每一次向數(shù)據(jù)庫(kù)的寫(xiě)入操作都需要傳播到所有的副本上，否則副本就會(huì)包含不一樣的數(shù)據(jù)。最常見(jiàn)的解決方案被稱為基于領(lǐng)導(dǎo)者的復(fù)制 或 主從復(fù)制

• 副本之一被指定為領(lǐng)導(dǎo)者(或主庫(kù))，當(dāng)客戶端要向數(shù)據(jù)庫(kù)寫(xiě)入時(shí)，它必須發(fā)給領(lǐng)導(dǎo)者，領(lǐng)導(dǎo)者會(huì)將新數(shù)據(jù)寫(xiě)入其本地存儲(chǔ);

• 其他副本被稱為追隨者(只讀副本、從庫(kù))，會(huì)同步主庫(kù)的變更日志，按照主庫(kù)相同的順序?qū)懭?/p>

• 當(dāng)客戶端從數(shù)據(jù)庫(kù)讀取數(shù)據(jù)時(shí)，可以向領(lǐng)導(dǎo)者或追隨者查詢

同步 or 異步

復(fù)制系統(tǒng)的一個(gè)重要細(xì)節(jié)是 復(fù)制 是 同步發(fā)生 還是  異步發(fā)生。同步復(fù)制會(huì)使得數(shù)據(jù)寫(xiě)入時(shí)間變長(zhǎng)，而異步復(fù)制會(huì)使得副本之間的數(shù)據(jù)不一致，客戶端可能會(huì)讀取到歷史的數(shù)據(jù)，并且在主庫(kù)故障時(shí)有可能會(huì)丟失數(shù)據(jù)。所以復(fù)制系統(tǒng)的核心就是如何讓副本保持一致，并且在主庫(kù)故障時(shí)能夠自動(dòng)切換。

一致性模型

一致性模型(consistency  model)實(shí)質(zhì)上是進(jìn)程和數(shù)據(jù)存儲(chǔ)存儲(chǔ)之間的一個(gè)約定。即，如果進(jìn)程同意遵守某些規(guī)則，那么數(shù)據(jù)存儲(chǔ)將正常運(yùn)行。正常情況下，一個(gè)進(jìn)程在一個(gè)數(shù)據(jù)項(xiàng)執(zhí)行讀操作時(shí)，它期待該操作返回的是該數(shù)據(jù)在其最后一次寫(xiě)操作之后的結(jié)果。

在沒(méi)有全局時(shí)鐘的情況下，精確地定義哪次寫(xiě)操作時(shí)最后一次寫(xiě)操作是十分困難的。作為替代的方法，我們需要提供其他的定義，因此產(chǎn)生了一系列的一致性模型。每種模型都有效地限制了在一個(gè)數(shù)據(jù)項(xiàng)上執(zhí)行一次讀操作所應(yīng)返回的值。

注意：不將數(shù)據(jù)庫(kù)事務(wù)的一致性與其混淆，分布式副本的一致性指的是單個(gè)對(duì)象的寫(xiě)入和讀取。

以數(shù)據(jù)為中心

線性一致性

線性一致性也稱為嚴(yán)格一致性(Strict Consistency)或者原子一致性(Atomic Consistency)，需要滿足以下兩個(gè)條件：

• 任何一次讀都能讀取到某個(gè)數(shù)據(jù)最近的一次寫(xiě)的數(shù)據(jù)。

• 所有進(jìn)程看到的操作順序都跟全局時(shí)鐘下的順序一致。

線性一致性的想法是讓一個(gè)系統(tǒng)看起來(lái)只有一個(gè)數(shù)據(jù)副本，而且所有的操作都是原子性的。應(yīng)用不用擔(dān)心多個(gè)副本帶來(lái)諸多問(wèn)題，是一個(gè)完美的理想模型，作為其他模型的參考(最強(qiáng)一致性模型)。

在線性一致性的數(shù)據(jù)存儲(chǔ)中不存在并發(fā)操作：必須有且僅有一條時(shí)間線，所有的操作都在這條時(shí)間線上，構(gòu)成一個(gè)全序關(guān)系。

順序一致性

順序一致性最早出現(xiàn)在Shared-Memory Multi-Processor  System單機(jī)模型中，為程序員提供了極強(qiáng)的內(nèi)存可見(jiàn)性保證。順序一致性內(nèi)存模型有兩大特性：

• 任何執(zhí)行的結(jié)果都與所有處理器的操作按某種順序執(zhí)行的相同。

• 每個(gè)單獨(dú)的處理器的操作順序均按照其程序指定的順序。

• 所有操作都必須相對(duì)于每個(gè)其他處理器立即或原子執(zhí)行(立即可見(jiàn))。

  

在時(shí)間順序上，C1發(fā)生于B2之后。對(duì)于線性一致性來(lái)說(shuō)，C1一定在B2之后，但是對(duì)于順序一致性B2可以發(fā)生在C1之后。

順序一致性可能會(huì)產(chǎn)生不確定的結(jié)果。這是因?yàn)樵诔绦虻牟煌\(yùn)行期間，處理器之間的順序操作的順序可能會(huì)有所不同。

對(duì)于順序一致性來(lái)說(shuō)，它要找到一個(gè)合法的順序執(zhí)行過(guò)程，該執(zhí)行過(guò)程要保留線程/進(jìn)程內(nèi)部原有的順序

對(duì)于線性一致性來(lái)說(shuō)，它也是要找到一個(gè)合法的順序執(zhí)行過(guò)程。但是這個(gè)順序執(zhí)行過(guò)程，不僅要保留線程/進(jìn)程內(nèi)部的先后順序，還要保留線程/進(jìn)程之間的操作的先后順序。

線性一致性可以定義為具有實(shí)時(shí)約束(real-time constraint)的順序一致性。

個(gè)人理解，在分布式副本的領(lǐng)域中，不太可能找到 除了時(shí)序之外，各個(gè)進(jìn)程能夠一致認(rèn)可的順序。所以在分布式副本領(lǐng)域參考意義不大，更容易造成疑惑。

因果一致性

相對(duì)于線性一致性保證讀寫(xiě)具有全局順序，而因果一致性只需要保證具有相互依賴的讀寫(xiě)操作保持相同的順序即可。實(shí)際上因果一致性是性能和可用最高的強(qiáng)一致性模型。

因果一致性實(shí)現(xiàn)的難點(diǎn)在于如何定義和捕獲因果關(guān)系，你需要知道哪個(gè)操作發(fā)生在哪個(gè)操作之前(happen  before)。但是這種因果關(guān)系更多是來(lái)自上層應(yīng)用，底層存儲(chǔ)是無(wú)法感知的，所以跟蹤所有的因果關(guān)系是不及實(shí)際的。

因果關(guān)系的操作在時(shí)序上一定是有先后，所以通過(guò)全序的的序列化或時(shí)間戳(邏輯時(shí)鐘)來(lái)排序操作，這樣所有的操作都有了時(shí)間上的因果先后關(guān)系。所以線性一致性是所有操作都滿足因果一致性(即使大部分操作沒(méi)有依賴關(guān)系)。

最終一致性

最終一致性不能算是一致性模型，沒(méi)有任何一致性保證，只是說(shuō)在沒(méi)有更新的情況下，副本之間會(huì)在一定時(shí)間內(nèi)保持一致。因?yàn)橛捎诰W(wǎng)絡(luò)延遲的存在，應(yīng)用任何時(shí)候都可能讀取到不一致的數(shù)據(jù)。可以說(shuō)是可接受的最弱的一致性模型。

以客戶端為中心

上面討論的以數(shù)據(jù)存儲(chǔ)為視角的一致性，在因果一致性以及更強(qiáng)的一致性模型中，從客戶端而言是不會(huì)發(fā)生預(yù)料之外的讀寫(xiě)問(wèn)題的。但是在更弱的一致性模型而言，出現(xiàn)各種讀寫(xiě)問(wèn)題。

以客戶端為中心的一致性為單一客戶端提供一致性保證，保證該客戶端對(duì)數(shù)據(jù)存儲(chǔ)的訪問(wèn)的一致性，但是它不為不同客戶端的并發(fā)訪問(wèn)提供任何一致性保證。

以客戶端為中心的一致性包含了四種模型：

• 單調(diào)讀一致性(Monotonic-read Consistency)：如果一個(gè)進(jìn)程讀取數(shù)據(jù)項(xiàng) x 的值，那么該進(jìn)程對(duì)于 x  后續(xù)的所有讀操作要么讀取到第一次讀取的值要么讀取到更新的值。即保證客戶端不會(huì)讀取到舊值。

• 單調(diào)寫(xiě)一致性(Monotonic-write Consistency)：一個(gè)進(jìn)程對(duì)數(shù)據(jù)項(xiàng) x 的寫(xiě)操作必須在該進(jìn)程對(duì) x  執(zhí)行任何后續(xù)寫(xiě)操作之前完成。即保證客戶端的寫(xiě)操作是串行的。

• 讀寫(xiě)一致性(Read-your-writes Consistency)：一個(gè)進(jìn)程對(duì)數(shù)據(jù)項(xiàng) x 執(zhí)行一次寫(xiě)操作的結(jié)果總是會(huì)被該進(jìn)程對(duì) x  執(zhí)行的后續(xù)讀操作看見(jiàn)。即保證客戶端能讀到自己最新寫(xiě)入的值。

• 寫(xiě)讀一致性(Writes-follow-reads Consistency)：同一個(gè)進(jìn)程對(duì)數(shù)據(jù)項(xiàng) x 執(zhí)行的讀操作之后的寫(xiě)操作，保證發(fā)生在與 x  讀取值相同或比之更新的值上。即保證客戶端對(duì)一個(gè)數(shù)據(jù)項(xiàng)的寫(xiě)操作是基于該客戶端最新讀取的值。

但是真實(shí)情況是，由于服務(wù)器負(fù)載均衡以及服務(wù)器故障的存在，會(huì)導(dǎo)致客戶端會(huì)話會(huì)發(fā)生轉(zhuǎn)移，因此基于客戶端訪問(wèn)的一致性模型是不靠譜的。

共識(shí)協(xié)議

Lamport時(shí)間戳

我們知道分布式系統(tǒng)中，各個(gè)機(jī)器擁有相同的時(shí)鐘(全局時(shí)鐘)是不太可能的。1978年Lamport在一篇論文中提出了一種邏輯時(shí)間戳，來(lái)解決分布式系統(tǒng)中區(qū)分事件發(fā)生的時(shí)序問(wèn)題。這篇論文是分布式系統(tǒng)領(lǐng)域被引用最多的論文之一。

Lamport時(shí)間戳就是兩者的簡(jiǎn)單結(jié)合：時(shí)間戳/計(jì)數(shù)器 + 節(jié)點(diǎn)ID，規(guī)則如下：

每個(gè)事件對(duì)應(yīng)一個(gè)Lamport時(shí)間戳，初始值為0

如果事件在節(jié)點(diǎn)內(nèi)發(fā)生，本地進(jìn)程中的時(shí)間戳加1

如果事件屬于發(fā)送事件，本地進(jìn)程中的時(shí)間戳加1并在消息中帶上該時(shí)間戳

如果事件屬于接收事件，本地進(jìn)程中的時(shí)間戳 = Max(本地時(shí)間戳，消息中的時(shí)間戳) + 1

事件的順序按照時(shí)間戳排序，時(shí)間戳相同則按照節(jié)點(diǎn)ID大小排序

上圖，ABC節(jié)點(diǎn)的所有事件的全序關(guān)系如下：

Lamport時(shí)間戳背后的思想是：兩個(gè)事件可以建立時(shí)序(因果)關(guān)系的前提是兩個(gè)事件之間是否發(fā)生過(guò)信息傳遞。因此Lamport時(shí)間戳只保證因果關(guān)系(偏序)的正確性，不保證絕對(duì)時(shí)序的正確性。

全序廣播

Lamport時(shí)間戳通過(guò)消息的傳遞來(lái)確定事件的時(shí)序關(guān)系，引出了全序廣播(在節(jié)點(diǎn)間交換消息的協(xié)議)。全序廣播需要滿足兩個(gè)安全屬性：

• 可靠交付 (reliable delivery)，沒(méi)有消息丟失：如果消息被傳遞到一個(gè)節(jié)點(diǎn)，它將傳遞到所有節(jié)點(diǎn)

• 全序交付(total ordered delivery)，消息以相同的順序傳遞給每個(gè)節(jié)點(diǎn)

全序廣播正是數(shù)據(jù)庫(kù)復(fù)制所需要的：如果每個(gè)消息都代表一次數(shù)據(jù)庫(kù)寫(xiě)入，且每個(gè)副本都按照相同的順序處理相同的寫(xiě)入，那么副本相互保持一致(除了臨時(shí)的復(fù)制延遲，可以將讀操作也作為消息，來(lái)實(shí)現(xiàn)一致讀)。這個(gè)原理被稱為狀態(tài)機(jī)復(fù)制(state  machine replication)。

因?yàn)閿?shù)據(jù)庫(kù)的寫(xiě)入和讀取操作都是通過(guò)消息交互達(dá)成一致，依據(jù)Lamport時(shí)間戳，所有的操作是全序的，因此可以實(shí)現(xiàn)線性一致性存儲(chǔ)。

Raft協(xié)議

Raft是一種共識(shí)算法，旨在使其易于理解。 它在容錯(cuò)和性能上與Paxos等效。  不同之處在于它被分解為相對(duì)獨(dú)立的子問(wèn)題，并且干凈地解決了實(shí)際系統(tǒng)所需的所有主要部分，實(shí)際將上面的 全序廣播/狀態(tài)機(jī)復(fù)制 的工程化。

Raft協(xié)議動(dòng)畫(huà)演示：thesecretlivesofdata.com/raft/

在Raft集群里，服務(wù)器可能會(huì)是這三種身份其中一個(gè)：領(lǐng)導(dǎo)(leader)、追隨者(follower)，或是候選人(candidate)。在正常情況下只會(huì)有一個(gè)領(lǐng)導(dǎo)，其他都是追隨者。而領(lǐng)導(dǎo)會(huì)負(fù)責(zé)所有外部的請(qǐng)求，如果不是領(lǐng)導(dǎo)的機(jī)器收到時(shí)，請(qǐng)求會(huì)被導(dǎo)到領(lǐng)袖。

Raft將問(wèn)題拆成數(shù)個(gè)子問(wèn)題分開(kāi)解決：

• 領(lǐng)導(dǎo)選舉(Leader Election)

• 日志復(fù)制(Log Replication)

• 集群成員變化 (Cluster membership changes)

• 安全性(Safety)

看完上述內(nèi)容，你們掌握數(shù)據(jù)庫(kù)中數(shù)據(jù)模型的實(shí)例分析的方法了嗎？如果還想學(xué)到更多技能或想了解更多相關(guān)內(nèi)容，歡迎關(guān)注億速云行業(yè)資訊頻道，感謝各位的閱讀！