戳藍(lán)字“CSDN云計(jì)算”關(guān)注我們哦！

時(shí)光機(jī)：搭載這部時(shí)光機(jī)，帶您回顧《程序員》大量優(yōu)秀文章，重溫經(jīng)典技術(shù)干貨，我們發(fā)現(xiàn)硬核技術(shù)永不過時(shí)，對于get要點(diǎn)、solve難題、提高自我，仍有非凡意義。

作者：Richy?Ho，一名軟件架構(gòu)師，熱衷于分布式及并行計(jì)算、機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘、SaaS和云計(jì)算。先后在Cisco、eBay、Adobe等公司工作。博客為horicky.blogspot.com。

?

導(dǎo)讀

過去，一些用于存儲大規(guī)模數(shù)據(jù)的數(shù)據(jù)存儲機(jī)制逐漸成形，它們與RDBMS模型相去甚遠(yuǎn)，被統(tǒng)稱為NoSQL。提煉出各種NoSQL方案背后共通的技術(shù)原理，有助于更深刻地理解它們對應(yīng)用程序設(shè)計(jì)的內(nèi)在影響。

過去，?一 些 用 于 存 儲大規(guī)模數(shù)據(jù)的數(shù)據(jù)存儲機(jī)制逐漸成形。這些存儲方案與RDBMS模型相去甚遠(yuǎn)，被統(tǒng)稱為NoSQL。其中引人注目的主要角色有：

●?Google BigTable, HBase, Hypertable

● Amazon Dynamo, Voldemort, Cassendra, Riak

● Redis

● CouchDB, MongoDB

上面列舉的方案具有這樣一些共同的特點(diǎn)：

●?鍵/值存儲；

●?系統(tǒng)運(yùn)行在數(shù)量巨大的普通機(jī)器上；

●?數(shù)經(jīng)過分區(qū)和復(fù)制，散布在大量的機(jī)器上；

放松了對數(shù)據(jù)一致性的約束。（因?yàn)镃AP理論證明，一致性、可用性和分布不可能三者兼得。）本文意在提煉出以上方案背后共通的技術(shù)原理，以圖更深刻地理解它們對應(yīng)用程序設(shè)計(jì)的內(nèi)在影響。

?

API模型

?

底層的數(shù)據(jù)模型可以看作一個(gè)巨大的Hashtable（鍵/值存儲）。訪問Hashtable的API基本形式如下：get（key）：給定一個(gè)鍵，取得對應(yīng)的值。put（key,?value）：新建一個(gè)鍵/值對，或者更新給定的鍵對應(yīng)的值。delete（key）：移除一個(gè)鍵及其對應(yīng)的值。

?

通過更高級的API，還可以在服務(wù)器環(huán)境中執(zhí)行用戶定義的函數(shù)。execute（key,?operation,?parameters）：（通過給定的鍵）對特定的值調(diào)用某操作，該值可以具有特殊的數(shù)據(jù)結(jié)構(gòu)（如List、Set、Map……）。mapreduce（keyList,?mapFunc,?reduceFunc）：對給定范圍的鍵調(diào)用Map/Reduce函數(shù)。

?

機(jī)器布局

?

整套硬件設(shè)施由大量（數(shù)百臺、數(shù)千臺……）便宜的、普通的、不可靠的機(jī)器通過網(wǎng)絡(luò)連接而成。每臺機(jī)器稱為一個(gè)物理節(jié)點(diǎn)（PN）。每個(gè)PN上的軟件配置是相同的，但CPU數(shù)量、內(nèi)存、磁盤等硬件能力可能不同。在每個(gè)PN上，依據(jù)其硬件能力，運(yùn)行著數(shù)量不等的虛擬節(jié)點(diǎn)（VN）。

?

數(shù)據(jù)分區(qū)

?

（一致性散列）由于整個(gè)散列表分散在許多VN上，我們需要找一種方法將每個(gè)鍵映射到相應(yīng)的VN。其中一種辦法是用以下式子確定分區(qū)位置：分區(qū)?=?鍵?mod總VN數(shù)量。這種方案的劣勢在于當(dāng)VN數(shù)量變化的時(shí)候，現(xiàn)有鍵的所有權(quán)（即位于哪個(gè)VN上）會發(fā)生極大的變化，全部數(shù)據(jù)都要重新分配到所有VN。因此多數(shù)大規(guī)模的存儲都采用一種“一致性散列”的技巧去最小化所有權(quán)變更的數(shù)量。

?

在?一?致?性?散?列?方?案?中?，?鍵?空間是有限的，且落在一個(gè)圓周上。虛擬節(jié)點(diǎn)的ID也從同一個(gè)鍵空間中分配。對于任意鍵，如果從該鍵開始，沿著圓周順時(shí)針走，遇到的第一個(gè)虛擬節(jié)點(diǎn)就是它所屬的節(jié)點(diǎn)。

如果某個(gè)節(jié)點(diǎn)崩潰了，它所屬的所有鍵都被移交到順時(shí)針方向的相鄰節(jié)點(diǎn)。因此，鍵的重新分配只發(fā)生在崩潰節(jié)點(diǎn)的鄰居身上，其他節(jié)點(diǎn)仍然保留原有鍵不變。

?

數(shù)據(jù)復(fù)制

?

為了用單個(gè)來說并不可靠的資源提供更高的可靠性，我們需要復(fù)制數(shù)據(jù)分區(qū)。

復(fù)制（Replication）不僅提高了數(shù)據(jù)的整體可靠性，還由于將工作負(fù)載分散到多個(gè)副本（Replica）而對性能有所幫助。

只?讀?請?求?可?以?分?發(fā)?到?任?意?的副本，而更新請求的處理則較為困難，我們必須小心地協(xié)調(diào)各副本的更新。

?

成員變更

?

請注意虛擬節(jié)點(diǎn)可在任意時(shí)刻加入或離開網(wǎng)絡(luò)，而不影響這個(gè)環(huán)的運(yùn)作。

當(dāng)新節(jié)點(diǎn)加入到網(wǎng)絡(luò)

1．新加入的節(jié)點(diǎn)公告自身存在，將ID告知若干重要節(jié)點(diǎn)（或者簡單地廣播到所有節(jié)點(diǎn)）。

2．左右兩側(cè)的相鄰節(jié)點(diǎn)調(diào)整鍵的所有權(quán)以及副本成員信息。這步驟通常是同步完成的。

3．新加入的節(jié)點(diǎn)開始從它的相鄰節(jié)點(diǎn)并行、異步地批量復(fù)制數(shù)據(jù)。

4．副本成員的變更信息異步地傳播到其他節(jié)點(diǎn)。

注意其他節(jié)點(diǎn)可能尚未更新其副本成員信息，因而繼續(xù)向舊的節(jié)點(diǎn)轉(zhuǎn)發(fā)請求。而因?yàn)榕f節(jié)點(diǎn)（即新加入節(jié)點(diǎn)的鄰居）已經(jīng)掌握新節(jié)點(diǎn)的信息（第2步），它們會將請求轉(zhuǎn)發(fā)給新加節(jié)點(diǎn)。

?

另一方面，新加節(jié)點(diǎn)可能還處于下載數(shù)據(jù)的狀態(tài)，尚不能提供服務(wù)。我們用“矢量時(shí)鐘”（見后文）去確定新加節(jié)點(diǎn)是否已準(zhǔn)備好處理請求，否則客戶可以聯(lián)系其他副本成員。

?

當(dāng)現(xiàn)有節(jié)點(diǎn)離開網(wǎng)絡(luò)（比如當(dāng)節(jié)點(diǎn)崩潰的時(shí)候）

?

1．崩潰的節(jié)點(diǎn)不再響應(yīng)Gossip消息，因此它的鄰居發(fā)現(xiàn)這一情況。

2．鄰居更新成員信息，并異步地復(fù)制數(shù)據(jù)。

?

?節(jié)點(diǎn)崩潰

我們尚未提及虛擬節(jié)點(diǎn)如何映射到物理節(jié)點(diǎn)。實(shí)際的方案有很多，主要目標(biāo)是不讓相同副本的各個(gè)虛擬節(jié)點(diǎn)落在同一個(gè)物理節(jié)點(diǎn)上。其中一種簡單的方案是隨機(jī)地將虛擬節(jié)點(diǎn)分配到物理節(jié)點(diǎn)，但增加一重檢查，保證物理節(jié)點(diǎn)上不存在擁有相同鍵范圍的副本。

?

請注意，由于機(jī)器崩潰發(fā)生在物理節(jié)點(diǎn)的層次，意味著上面運(yùn)行的許多虛擬節(jié)點(diǎn)一同崩潰。當(dāng)這種情況發(fā)生的時(shí)候，（多個(gè)虛擬節(jié)點(diǎn)的）負(fù)載由很多臺物理機(jī)器分擔(dān)。因此由于物理節(jié)點(diǎn)崩潰而增加的負(fù)載被均勻地均衡掉了。

?

客戶端的一致性

?

當(dāng)我們擁有同一數(shù)據(jù)的多份副本，就有必要操心如何同步它們，才能使得在客戶端看來，數(shù)據(jù)是一致的。有很多種客戶端一致性模型：

1．嚴(yán)格一致性：語義上相當(dāng)于只存在一份數(shù)據(jù)副本。任何更新看上去

都是即時(shí)發(fā)生的。

2．“讀己之所寫”一致性：客戶端可立即看到自己所作的更新（且客戶端可在不同請求之間切換服務(wù)器），但不能立即看到其他客戶端所作的更新。

3．會話（Session）一致性：對于客戶端在同一會話作用域中發(fā)起的請求（通常綁定到同一臺服務(wù)器），提供“讀己之所寫”一致性。

4．單調(diào)讀一致性：保證時(shí)間上的單調(diào)性，保證客戶端在未來的請求中，只會讀到比當(dāng)前更為新的數(shù)據(jù)。

5．最終一致性：這是最弱的一種保證。在更新的過程中，客戶端將看到一幅不一致的視圖。當(dāng)并發(fā)訪問同一數(shù)據(jù)幾率非常小的時(shí)候，此模型效果良好。

?

客戶端需要等待一段時(shí)間才能看到自己先前所作的更新。取決于采用何種一致性模型，需要安排兩種機(jī)制：客戶端請求如何分發(fā)到副本。副本如何傳播及執(zhí)行更新。圍繞著如何實(shí)現(xiàn)這兩方面，出現(xiàn)了許多模型，各有不同的權(quán)衡取舍。

?

主從（或單主）模型

?

在此模型下，每個(gè)數(shù)據(jù)分區(qū)都有一個(gè)主節(jié)點(diǎn)和多個(gè)從節(jié)點(diǎn)。所有更新請求都必須發(fā)給主節(jié)點(diǎn)，主節(jié)點(diǎn)執(zhí)行更新后再異步地傳播給從節(jié)點(diǎn)。如果主節(jié)點(diǎn)在將更新傳播給任何從節(jié)點(diǎn)之前發(fā)生崩潰，就會出現(xiàn)一個(gè)丟失數(shù)據(jù)的時(shí)間窗口。因此有的系統(tǒng)會選擇同步等待，到更新傳播到至少一個(gè)從節(jié)點(diǎn)為止。

?

如果客戶端能容忍某種程度的舊數(shù)據(jù)，讀請求可以分發(fā)到任何副本。負(fù)載因此可以分散到多個(gè)副本上。如果對于某些數(shù)據(jù)，客戶端不能容忍取得非最新的數(shù)據(jù)，那就必須向主節(jié)點(diǎn)請求。

請注意此模型并不意味著某個(gè)物理節(jié)點(diǎn)扮演主節(jié)點(diǎn)的角色。主從關(guān)系發(fā)生在虛擬節(jié)點(diǎn)的層次。每個(gè)物理節(jié)點(diǎn)上，既有充當(dāng)某分區(qū)主節(jié)點(diǎn)的虛擬節(jié)點(diǎn)，也有扮演其他分區(qū)從節(jié)點(diǎn)的虛擬節(jié)點(diǎn)。因此，寫負(fù)載也被分散到不同的物理節(jié)點(diǎn)上，只不過這是由于分區(qū)的結(jié)果而非復(fù)制的結(jié)果。當(dāng)一個(gè)物理節(jié)點(diǎn)崩潰時(shí)，將會失去特定分區(qū)的主節(jié)點(diǎn)。此時(shí)一般將更新最及時(shí)的從節(jié)點(diǎn)選為新的主節(jié)點(diǎn)。當(dāng)應(yīng)用的讀/寫比很高的時(shí)候，主從模型效果顯著；當(dāng)更新涉及的鍵范圍分布均勻的時(shí)候，它的效果也很好。因?yàn)檫@些因素，大多數(shù)數(shù)據(jù)復(fù)制方案都選擇了主從模型。

?

更新由主節(jié)點(diǎn)傳播到從節(jié)點(diǎn)有兩種方式：傳狀態(tài)和傳操作。如果是傳狀態(tài)，主節(jié)點(diǎn)將它的最新狀態(tài)傳遞給從節(jié)點(diǎn)，然后從節(jié)點(diǎn)用得到的最新狀態(tài)替換掉自己的當(dāng)前狀態(tài)。如果是傳操作，主節(jié)點(diǎn)傳遞一系列操作給從節(jié)點(diǎn)，然后從節(jié)點(diǎn)對自己的本地狀態(tài)執(zhí)行操作。傳狀態(tài)模型更能抵御消息丟失的情況，因?yàn)橹灰罄m(xù)的更新消息能正確抵達(dá)，副本仍然能成功更新到最新的狀態(tài)。

?

即使在傳狀態(tài)模型里，我們也不希望發(fā)送完整的對象給其他副本，因?yàn)橥ǔＰ薷牡闹皇菍ο蟮囊恍〔糠帧０l(fā)送對象未變的部分等于浪費(fèi)帶寬。我們需要一種機(jī)制去檢查并發(fā)送更新的部分。常見的做法是將對象打散成小塊，并且計(jì)算出對象中各小塊的一棵散列樹。于是副本通過比較各自的散列樹，就能知道對象中的哪些小塊改動過了，只發(fā)送改動過的小塊即可。

?

一般來說，傳操作模型需要通過網(wǎng)絡(luò)發(fā)送的數(shù)據(jù)量較少。然而傳操作模型需要一種可靠的消息機(jī)制去保證消息的傳遞順序。

?

多主（或無主）模型

如果某些鍵范圍存在熱點(diǎn)，寫請求比較密集，主從模型沒辦法很好地將負(fù)載均勻地分散掉。多主模型允許將更新請求發(fā)送給任何副本（可能稱之為無主模型更合適）。如果任意客戶端可向任意服務(wù)器發(fā)出任意請求，那么我們?nèi)绾瓮綘顟B(tài)，才能保持客戶端的一致性，同時(shí)使所有副本最終都能達(dá)到相同的狀態(tài)？下文將介紹幾種辦法。

?

基于多數(shù)決的兩段式提交

?

為了實(shí)現(xiàn)“嚴(yán)格一致性”，我們可以采用傳統(tǒng)的兩段式提交（2PC）協(xié)議。假設(shè)某數(shù)據(jù)有N個(gè)副本。當(dāng)更新數(shù)據(jù)的時(shí)候，有一個(gè)“預(yù)備”階段，由協(xié)調(diào)者詢問所有副本，是否已準(zhǔn)備好執(zhí)行各個(gè)更新。然后每個(gè)副本將數(shù)據(jù)寫入日志文件，成功后通知協(xié)調(diào)者。收到所有副本的成功消息之后，協(xié)調(diào)者發(fā)起第二階段——“提交”階段，要求所有副本都完成提交，此時(shí)每個(gè)副本寫入另一條日志條目確認(rèn)更新。請注意這里存在一些可伸縮性的問題，因?yàn)閰f(xié)調(diào)者需要“同步地”等待很多輪網(wǎng)絡(luò)消息來回，還要等待磁盤I/O完成。

?

另一方面，如果某個(gè)副本崩潰了，更新將會失敗。當(dāng)副本的數(shù)量越多，其中之一發(fā)生問題的幾率也越大。因此，數(shù)據(jù)復(fù)制反而損害了系統(tǒng)的可用性。所以傳統(tǒng)的2PC在高吞吐量的事務(wù)系統(tǒng)中間并不流行。基?于?q?u?o?r?u?m?的?2?P?C?（?如PAXOS）效率更高一些。在此模型中，協(xié)調(diào)者只需要同步更新W個(gè)副本（而非全部N個(gè)副本）。

?

協(xié)調(diào)者仍舊寫入全部N個(gè)副本，但只等待其中任意W個(gè)副本確認(rèn)寫入成功。站在概率的角度看，這種做法具有更高的效率。然而，由于并非全部副本都完成了更新，我們在讀取數(shù)據(jù)的時(shí)候需要小心地保證讀到的節(jié)點(diǎn)中至少有一個(gè)是成功更新過的。

?

當(dāng)讀取數(shù)據(jù)的時(shí)候，我們需要讀取R個(gè)副本，并返回其中時(shí)間戳最新的一個(gè)結(jié)果。為了保證“嚴(yán)格一致性”，只要保證讀的集合與寫的集合有重疊即可，也就是W?+?R?>?N。你可能也想到了，基于多數(shù)決的2PC可以看作是2PC協(xié)議的一般化推廣，傳統(tǒng)的2PC是當(dāng)W?=?N和R?=?1時(shí)的特例。一般化之后的模型使我們可以根據(jù)讀寫負(fù)載的比率，權(quán)衡選擇不同的W和R。如果用戶不能承受選取足夠大的W和R，即當(dāng)W?+?R?<=?N的時(shí)候，那么客戶端的一致性模型就要放寬到較弱的類型。

?

如果客戶端可以容忍較寬松的一致性模型，那么我們沒必要采用上述的2PC提交或者基于多數(shù)決的協(xié)議。后文將介紹一種傳言（Gossip）模型，通過異步的傳言消息交換傳播更新，使所有副本最終都達(dá)到最新的狀態(tài)。

?

矢量時(shí)鐘

?

矢量時(shí)鐘是一種時(shí)間戳機(jī)制，透過它我們可以推導(dǎo)更新之間的因果關(guān)系。首先，每個(gè)副本都持有矢量時(shí)鐘。假設(shè)副本i的時(shí)鐘是Vi。Vi[i]是副本根據(jù)特定規(guī)則更新其矢量時(shí)鐘之后的邏輯時(shí)鐘。

當(dāng)副本i執(zhí)行了一則內(nèi)部操作，副本i的時(shí)鐘加一。當(dāng)副本i向副本j發(fā)送一則消息，副本i首先把自己的時(shí)鐘Vi[i]加一，并將自己的矢量時(shí)鐘Vi附加到消息中發(fā)送出去。當(dāng)副本j收到來自副本i的消息，它首先自增其時(shí)鐘Vj[j]，然后合并其時(shí)鐘及消息所附的時(shí)鐘Vm。即Vj[k]?=?max（Vj[k],?Vm[k]）。

?

于是可定義偏序關(guān)系，Vi?>?Vj，當(dāng)且僅當(dāng)對于所有的k，V?i?[?k?]?>?=?Vj[k]。根據(jù)這樣的偏序關(guān)系，我們就可以推導(dǎo)出更新之間的因果關(guān)系。背后的原理是這樣的：內(nèi)部操作的效果可在同一節(jié)點(diǎn)上立即看到。

?

接收到消息之后，接收節(jié)點(diǎn)得知發(fā)送節(jié)點(diǎn)在消息發(fā)送之時(shí)的情況。情況不僅包括了發(fā)送節(jié)點(diǎn)上發(fā)生的事情，還包括了發(fā)送節(jié)點(diǎn)所知的所有其他節(jié)點(diǎn)上發(fā)生的事情。換言之，Vi[i]反映了節(jié)點(diǎn)i上發(fā)生最后一次內(nèi)部操作的時(shí)間。Vi[k]?=?6意味著副本i已經(jīng)知道副本k在它的邏輯時(shí)鐘6的時(shí)刻的情況。請注意這里是在一種抽象的意義上使用“情況（situation）”一詞。取決于消息中傳遞何種信息，“情況”有不同的具體含義。情況的具體含義會影響如何增加矢量時(shí)鐘。下文介紹的“傳狀態(tài)模型”和“傳操作模型”在消息中傳遞的信息不一樣，它們矢量時(shí)鐘如何增加，也因此不同。

?

由于狀態(tài)總是從副本流向客戶端，絕不會反過來，所以客戶端不占矢量時(shí)鐘的條目。矢量時(shí)鐘里每個(gè)副本占一條。不過，客戶端可以持有它最后聯(lián)系的副本的矢量時(shí)鐘，這對于實(shí)現(xiàn)我們先前討論的客戶端一致性甚為關(guān)鍵。例如，為了支持單調(diào)讀一致性，副本可以保證附在數(shù)據(jù)上的矢量時(shí)鐘大于客戶端在查詢時(shí)提交的矢量時(shí)鐘。

?

傳言（傳狀態(tài)模型）

?

在傳狀態(tài)模型里，每個(gè)副本都維護(hù)著一個(gè)矢量時(shí)鐘和一個(gè)狀態(tài)的版本樹，版本樹中的狀態(tài)無法（通過比較矢量時(shí)鐘）得出狀態(tài)之間的“大于”或“小于”關(guān)系。換言之，狀態(tài)版本樹包含了所有存在沖突的更新。

在查詢的時(shí)候，客戶端將它的矢量時(shí)鐘一并提交，副本將狀態(tài)樹中早于客戶端時(shí)鐘的子集發(fā)回給客戶端（這就實(shí)現(xiàn)了單調(diào)讀一致性）。然后客戶端通過合并所有的版本，增加其時(shí)鐘。這意味著客戶端要負(fù)責(zé)解決所有的版本沖突，因?yàn)楫?dāng)客戶端稍后發(fā)送更新的時(shí)候，它的矢量時(shí)鐘會早于所有的版本。

?

在更新的時(shí)候，客戶端發(fā)送它的矢量時(shí)鐘，副本檢查客戶端的狀態(tài)是否早于任意現(xiàn)有版本，如果是，副本將丟棄客戶端的更新。各個(gè)副本還可以在后臺互相傳言，嘗試將各自的版本樹合并起來。

?

在傳操作方式下，執(zhí)行操作的次序非常重要，至少需要保證因果序（causal?order）。因?yàn)榇涡虻年P(guān)系，只要之前的操作還沒執(zhí)行完，副本就不得不推遲任何新的操作。因此副本需要將操作請求保存到一個(gè)日志文件，并彼此交換日志，通過統(tǒng)一合并日志推導(dǎo)出正確的操作序列，才能相應(yīng)地更新各自的本地存儲。

?

“ 因 果 序 ” 意 味 著 每 個(gè) 副 本要 先 完 成 對 “ 因 ” 的 修 改 才 能 執(zhí)

行對“果”的修改。“全序（totalorder）”則要求每個(gè)副本都執(zhí)行同一個(gè)序列中的操作。在此模型中，每個(gè)副本持有一個(gè)矢量時(shí)鐘列表。Vi為副本自身的矢量時(shí)鐘，Vj為副本i接收到副本j傳言消息時(shí)的矢量時(shí)鐘。V-state代表最后更新狀態(tài)的矢量時(shí)鐘。

?

當(dāng)客戶端提交查詢的時(shí)候，它會一并發(fā)送客戶端的矢量時(shí)鐘，這個(gè)時(shí)鐘代表了客戶端的視圖。副本檢查自己所知的狀態(tài)是否遲于客戶端所知的狀態(tài)。

?

當(dāng)收到更新操作，副本會將操作緩沖起來，直到可以將之應(yīng)用到本地狀態(tài)。每個(gè)提交的操作都會帶上兩個(gè)時(shí)間戳，V-client標(biāo)明客戶端在其發(fā)出更新請求時(shí)的視圖。V-@receive標(biāo)明副本在收到請求時(shí)的視圖。

?

更新操作的請求會留在隊(duì)列里，直到副本收到該請求所依賴的所有其他請求。這個(gè)條件反映在矢量時(shí)鐘Vi上，即當(dāng)Vi大于V-client時(shí)條件滿足。

更新（傳操作模型）

?

在后臺，各個(gè)副本交換它們記錄的更新隊(duì)列日志并更新彼此的矢量時(shí)鐘。在日志交換之后，副本檢查特定的操作是否可以執(zhí)行（當(dāng)所有依賴操作都已收到），然后完成操作。請注意在同一時(shí)刻，有可能存在多個(gè)操作準(zhǔn)備好執(zhí)行，此時(shí)副本將按照因果序（通過比較矢量時(shí)鐘）排列各操作，依次執(zhí)行。還有可能發(fā)生不同副本上的并發(fā)更新問題。也就是說可能存在多個(gè)合法的操作序列，為了使不同副本以相同次序執(zhí)行并發(fā)的更新，我們需要一種“全序”機(jī)制。

?

其中一種方法是設(shè)立一個(gè)單調(diào)增加的序列號，不管哪個(gè)更新先執(zhí)行都好，序列號先到先得。另一方面，如果操作本身是可以互換的，那么操作的執(zhí)行次序也就無關(guān)緊要了。執(zhí)行更新之后，更新操作還不能立即從隊(duì)列中刪除，因?yàn)楦驴赡苓€沒有交換到到所有的副本。我們繼續(xù)檢查每次日志交換后每個(gè)副本的矢量時(shí)鐘，直到確認(rèn)所有副本都已收到更新，才可以將它從隊(duì)列中刪除。

?

Map Reduce的執(zhí)行過程

?

分布式的存儲架構(gòu)也適合分布式的處理。例如對一個(gè)鍵列表執(zhí)行Map/Reduce操作的情況。

系統(tǒng)將Map和Reduce函數(shù)推送給所有的節(jié)點(diǎn)（即將處理邏輯向數(shù)據(jù)靠攏）。Map函數(shù)分布到鍵所屬的各個(gè)副本上去處理，然后Map函數(shù)的輸出被轉(zhuǎn)交給Reduce函數(shù)去執(zhí)行聚合操作。

?

對刪除的處理

在多主復(fù)制系統(tǒng)中，我們用矢量時(shí)鐘時(shí)間戳去判定因果序，我們需要非常小心地處理“刪除”的情況，以免丟失掉刪除對象關(guān)聯(lián)的時(shí)間戳信息，否則我們根本無法推導(dǎo)何時(shí)執(zhí)行刪除。

?

因此，我們通常將刪除當(dāng)作一種特殊的更新來處理，把對象標(biāo)記為刪除，但仍然保留其元數(shù)據(jù)、時(shí)間戳信息。當(dāng)經(jīng)過足夠長的時(shí)間，我們確信所有節(jié)點(diǎn)都已經(jīng)將該對象標(biāo)記為刪除之后，我們才通過垃圾收集回收已刪除對象的空間。

?

福利

掃描添加小編微信，備注“姓名+公司職位”，加入【云計(jì)算學(xué)習(xí)交流群】，和志同道合的朋友們共同打卡學(xué)習(xí)！

推薦閱讀：

• VMware竟然出了一款防火墻

• 技術(shù)頭條

• 你的 AI 老師已上崗

• 要成為年薪百萬的技術(shù)大牛必經(jīng)歷這5個(gè)階段, 收好這份超實(shí)用的技術(shù)進(jìn)階指南 | 技術(shù)頭條

• 助力?Android?抗衡?iOS，華為發(fā)布方舟編譯器！

• 程序員的黑磚窯，東南亞博彩騙局詳解

• 售價(jià)910元！周志華等人英文新書《演化學(xué)習(xí)》出爐！
  

真香，朕在看了！ 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的一文读懂NoSQL的模式 | 时光机的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。