問題
- 分布式存儲(chǔ)的系統(tǒng)設(shè)計(jì)中，有一個(gè)問題一直困擾著我：
方式1. 集群中所有的機(jī)器妨猩，都存儲(chǔ)完整的數(shù)據(jù)潜叛，然后所有的機(jī)器都可以提供完整服務(wù)；
方式2. 集群中的所有機(jī)器，都只存儲(chǔ)數(shù)據(jù)的一部分威兜，然后根據(jù)實(shí)際情況選擇合適的機(jī)器進(jìn)行服務(wù)销斟。
- 問題1. 方式1中所有的機(jī)器中存儲(chǔ)的數(shù)據(jù)如何保證一致性，意味著一臺(tái)機(jī)器的數(shù)據(jù)被寫入椒舵，其它機(jī)器也需要同步蚂踊；
- 問題2. 方式2中有什么方式可以保證數(shù)據(jù)的一部分被分配到合適的機(jī)器，同時(shí)新增或者減少機(jī)器的話應(yīng)當(dāng)如何處理笔宿。
回答
- 今天的思考暫時(shí)回避問題1犁钟，這是一個(gè)龐大的題目。
- 問題2隱藏有兩個(gè)基本的需求：a. 平衡性：數(shù)據(jù)被均勻地分配到不同的機(jī)器泼橘；b. 單調(diào)性：機(jī)器的增減應(yīng)該對數(shù)據(jù)的分布影響較小涝动。
首先，均勻分配這個(gè)需求炬灭，很容易聯(lián)想到hash算法取模的方式：
pos = hash(obj) % N
由于hash算法的獨(dú)特性醋粟，保證了取模的隨機(jī)性；
然而又引出另一個(gè)問題重归，如果新增一臺(tái)機(jī)器或者宕機(jī)一臺(tái)米愿，pos已經(jīng)固定的obj，會(huì)因?yàn)镹的變動(dòng)受到影響
pos = hash(obj) % (N + 1)
pos = hash(obj) % (N - 1)
此時(shí)鼻吮，一致性hash粉墨登場育苟。
一致性哈希，使用一致性哈希環(huán)的數(shù)據(jù)結(jié)構(gòu)狈网，將obj于pos都分布在這個(gè)環(huán)上宙搬。
如果obj沒有命中任何一個(gè)pos，則在環(huán)上順時(shí)針尋找最近的一個(gè)pos拓哺。
這樣做的效果勇垛，就會(huì)讓新增或者減少機(jī)器時(shí)，只會(huì)影響到一臺(tái)機(jī)器士鸥。
而如果算法中甚至做一些冗余的做法闲孤，會(huì)讓影響降低到更小。
