引言：
最近重讀http://book.mixu.net/distsys/ebook.html，在分布式文件系統(tǒng)，如何掌握寫入內(nèi)容的先后關(guān)系是重要的一環(huán)，因?yàn)樵诓l(fā)寫入的過程中，可能會導(dǎo)致多個(gè)版本同時(shí)出現(xiàn)的情況，但是使用物理時(shí)鐘顯然是不靠譜的，所以我們采用一種邏輯時(shí)鐘來為對象構(gòu)建一種偏序的（partial ordering）的時(shí)序集合，同時(shí)這個(gè)也是Amazon在他們的Dynamo中的實(shí)踐原理。
簡介：
VectorClock是一種用向量來表示偏序關(guān)系的邏輯時(shí)鐘，從數(shù)據(jù)結(jié)構(gòu)上可以理解為一個(gè)集合內(nèi)包含所有節(jié)點(diǎn)的“時(shí)間戳”，當(dāng)然這個(gè)時(shí)間戳并不是物理意義上的時(shí)間（也有些實(shí)踐會同時(shí)加入timestamps以解決沖突問題），而是由程序賦予的邏輯計(jì)數(shù)（count），{Node1:0,Node2:2,Node3:3.......}，如果我們已經(jīng)統(tǒng)一了向量內(nèi)的位置對應(yīng)的node，那么時(shí)鐘可以直接用一個(gè){0,2,3}來表示。
對于每一個(gè)分布式存儲的對象副本都有這樣一個(gè)時(shí)間戳，那么存在一下幾種關(guān)系：
a： 本機(jī)：{0，0，1} 消息：{0，1，2}。消息的每個(gè)節(jié)點(diǎn)的count都大于等于本機(jī)的，那么舍棄本機(jī)，同步消息
b: 本機(jī)：{0，1，2} 消息：{0，1，1}。消息的每個(gè)節(jié)點(diǎn)的count都小于等于本機(jī)的，那么舍棄消息，保留本機(jī)
c: 本機(jī)：{0，3，1} 消息：{0，1，2}。出現(xiàn)沖突，有的大，有的小，無法判斷出來到底誰是最新版本。就要進(jìn)行沖突仲裁。
舉例：
假設(shè)有一個(gè)K-V數(shù)據(jù)庫，{K，V}為一個(gè)分布式對象，通過3個(gè)副本保存，分別在Node 1,Node 2, Node 3上，初始的vectorclock為 {0,0,0}
- 首先寫入，Node1，那么node1 的vclock會增加node1的count，可以理解為node1修改了{(lán)K,V}，先在的vclock就變?yōu)閧1,0,0}
- 此時(shí)Node1將這個(gè)副本及其vclock分發(fā)給Node2和Node3，因?yàn)榇藭r(shí)這兩個(gè)Node都是{0，0，0}的狀態(tài)，所以符合a關(guān)系，2，3同步
- 此時(shí)又有一次在Node1的寫入，變?yōu)閧2,0,0}，此時(shí)Node1接到了來到了Node2的消息，此時(shí)符合b關(guān)系，Node1保留
- 此時(shí)有了一次Node2的寫入，Node2的vclock變?yōu)閧1,1,0}，但此時(shí)Node1的上次寫入沒有傳遞給Node2，Node2覺得自己這里就是對了，如果這個(gè)時(shí)候Node1的消息來了就會產(chǎn)生3關(guān)系，沖突。
其實(shí)在我們平時(shí)使用Dropbox同步盤的時(shí)候就會出現(xiàn)這種情況，當(dāng)你在進(jìn)行頻繁保存的時(shí)候，上一次的保存結(jié)果告訴了服務(wù)端，然后你在服務(wù)端返回已同步修改前又保存了一次，結(jié)果服務(wù)端不愿意了，怎么你本地的和我的對不上了，直接留下了兩個(gè)版本和時(shí)間戳讓用戶自己去選擇。
實(shí)現(xiàn)：
function VectorClock(value) {
// expressed as a hash keyed by node id: e.g. { node1: 1, node2: 3}
this.value = value || {};
}
VectorClock.prototype.get = function() {
return this.value;
};
//根據(jù)寫入節(jié)點(diǎn)增加vector clock
VectorClock.prototype.increment = function(nodeId) {
if(typeof this.value[nodeId] == 'undefined') {
this.value[nodeId] = 1;
} else {
this.value[nodeId]++;
}
};
VectorClock.prototype.merge = function(other) {
var result = {}, last,
a = this.value,
b = other.value;
// This filters out duplicate keys in the hash
(Object.keys(a)
.concat(b))
.sort()
.filter(function(key) {
var isDuplicate = (key == last);
last = key;
return !isDuplicate;
}).forEach(function(key) {
result[key] = Math.max(a[key] || 0, b[key] || 0);
});
this.value = result;
};
小結(jié)：
關(guān)于沖突仲裁：一種解決方法是請求用戶的介入，另一種可以通過引入輔助的時(shí)間戳來判斷。
一般3個(gè)副本就足夠
Quorum NRW模型：
N: 復(fù)制的節(jié)點(diǎn)數(shù)量
R: 成功讀操作的最小節(jié)點(diǎn)數(shù)
W: 成功寫操作的最小節(jié)點(diǎn)數(shù)只需W + R > N，就可以保證強(qiáng)一致性。
?
當(dāng)需要高可寫的系統(tǒng)時(shí)，可以設(shè)置W=1 R=3
當(dāng)需要高可讀的系統(tǒng)時(shí)，可以設(shè)置W=3 R=1 （寫的效率較低）
