來(lái)源：xybaby
聽過(guò)很多道理，卻依然過(guò)不好這一生嗓违。
看過(guò)很多關(guān)于學(xué)習(xí)的技巧瓷翻、方法赖歌，卻沒(méi)應(yīng)用到自己的學(xué)習(xí)中缺虐。
隨著年紀(jì)變大芜壁，記憶力越來(lái)越差，整塊的時(shí)間也越來(lái)越少，于是慧妄，越來(lái)越希望能夠更高效的學(xué)習(xí)顷牌。學(xué)習(xí)是一種習(xí)慣也是一種能力，這種能力在上學(xué)期間養(yǎng)成是最好的塞淹，畢竟那個(gè)時(shí)候絕大部分時(shí)間都在學(xué)習(xí)韧掩。但很遺憾，我沒(méi)有養(yǎng)成適合自己的窖铡、好的學(xué)習(xí)習(xí)慣。工作之后坊谁，除了在日常工作中用到的知識(shí)技術(shù)费彼，很難通過(guò)自學(xué)掌握新的知識(shí)（偏向于專業(yè)知識(shí)，即技術(shù)）口芍。而互聯(lián)網(wǎng)行業(yè)的分支箍铲、知識(shí)點(diǎn)又是如此之多，于是會(huì)出現(xiàn)這樣的情況鬓椭，遇到一個(gè)新的知識(shí)颠猴，覺(jué)得很厲害很感興趣，看兩天小染，但很快就忘記了翘瓮。另外，對(duì)于一些比較龐雜的技術(shù)裤翩，又無(wú)從下手资盅，也很難堅(jiān)持下去。
根本的問(wèn)題在于學(xué)習(xí)不系統(tǒng)踊赠，沒(méi)有把一個(gè)個(gè)的知識(shí)點(diǎn)連接起來(lái)呵扛，本來(lái)這些新的知識(shí)就很少在工作中實(shí)踐，如果又是一個(gè)個(gè)的信息孤島筐带，很快就會(huì)被遺忘今穿。另一個(gè)問(wèn)題，沒(méi)有良好的規(guī)劃伦籍，今天看看這里蓝晒，明天看看哪里，糾結(jié)于細(xì)枝末節(jié)鸽斟，忘了從整體上把握拔创。
幸好，差不多半年前開始意識(shí)到了這個(gè)問(wèn)題富蓄，開始看書剩燥，看別人的博客，開始思考如何充分利用好有限的時(shí)間。自己也實(shí)踐了一些想法灭红，比如寫博客侣滩，堅(jiān)持寫博客。也有很多沒(méi)做好变擒，比如如何學(xué)習(xí)掌握一門新技術(shù)君珠。關(guān)于這一點(diǎn)，其實(shí)看了許多文章娇斑，也有很多印象深刻策添，覺(jué)得很有道理；也有一些好書毫缆，比如《study more唯竹，learn less》。紙上得來(lái)終覺(jué)淺苦丁，絕知此事要躬行浸颓，別人的辦法再好也需要親身實(shí)踐才知道是否對(duì)自己適用。
需要學(xué)習(xí)的技術(shù)很多旺拉，要自學(xué)新知識(shí)也不是一件容易的事产上，選擇一個(gè)自己比較感興趣的會(huì)是一個(gè)比較好的開端，于是蛾狗，打算學(xué)一學(xué)分布式系統(tǒng)晋涣。
帶著問(wèn)題，有目的的學(xué)習(xí)沉桌，先了解整體架構(gòu)姻僧，在深入感興趣的細(xì)節(jié)，這是我的計(jì)劃蒲牧。
首先得有問(wèn)題撇贺，如果每日重復(fù)相同的工作，也不主動(dòng)去學(xué)習(xí)冰抢，很難發(fā)現(xiàn)新的問(wèn)題松嘶。不怕自己無(wú)知，就怕不知道自己無(wú)知挎扰，只有不斷的學(xué)習(xí)翠订，才會(huì)發(fā)現(xiàn)更多未知的知識(shí)領(lǐng)域！
帶著問(wèn)題出發(fā)
分布式要解決什么問(wèn)題呢遵倦？解決持久化數(shù)據(jù)太大尽超，單個(gè)節(jié)點(diǎn)的硬盤無(wú)法存儲(chǔ)的問(wèn)題；解決運(yùn)算量太大梧躺，單個(gè)節(jié)點(diǎn)的內(nèi)存似谁、CPU無(wú)法處理的問(wèn)題傲绣。解決這些問(wèn)題，有兩種思路：scale up巩踏，scale out秃诵。前者就是提升單個(gè)節(jié)點(diǎn)的能力，更大的磁盤塞琼，更快的CPU菠净，定制的軟硬件，然而這意味著更高的價(jià)格彪杉，而且再怎么scaleup 也是有上限的毅往。后者就是把存儲(chǔ)、計(jì)算任務(wù)分擔(dān)到普通的機(jī)器上派近，通過(guò)動(dòng)態(tài)增加節(jié)點(diǎn)來(lái)應(yīng)對(duì)數(shù)據(jù)量的增長(zhǎng)煞抬，但缺點(diǎn)是多個(gè)節(jié)點(diǎn)的管理、任務(wù)的調(diào)度比較麻煩构哺，這也是分布式系統(tǒng)研究和解決的問(wèn)題。只有當(dāng)數(shù)據(jù)量達(dá)到單機(jī)無(wú)法存儲(chǔ)战坤、處理的情況下才考慮分布式曙强，不然都是自找麻煩。
狀態(tài)的維護(hù)比計(jì)算要難很多途茫，所謂狀態(tài)就是需要持久化的數(shù)據(jù)碟嘴。因此主要考慮分布式存儲(chǔ)，況且即使是分布式計(jì)算囊卜，為了節(jié)省帶寬需要盡量保證data locality娜扇，也是需要分布式存儲(chǔ)。
現(xiàn)在有一堆數(shù)據(jù)栅组，可能是結(jié)構(gòu)化或者半結(jié)構(gòu)化雀瓢，需要將數(shù)據(jù)分片（segment、fragment玉掸、shard）刃麸，形成一個(gè)個(gè)的數(shù)據(jù)子集，存儲(chǔ)到一組物理節(jié)點(diǎn)上司浪，物理節(jié)點(diǎn)之間通過(guò)網(wǎng)絡(luò)通信泊业。那么需要考慮兩個(gè)問(wèn)題：
第一：數(shù)據(jù)如何劃分;
第二：數(shù)據(jù)的可靠性、可用性問(wèn)題
數(shù)據(jù)分片
數(shù)據(jù)分片是指將數(shù)據(jù)子集盡可能均衡的劃分到各個(gè)物理節(jié)點(diǎn)上啊易。那么會(huì)有哪些挑戰(zhàn)呢吁伺？
（1）如果某個(gè)物理節(jié)點(diǎn)宕機(jī)，如何將該物理節(jié)點(diǎn)負(fù)責(zé)的數(shù)據(jù)盡快的轉(zhuǎn)移到其他物理節(jié)點(diǎn)租谈；
（2）如果新增了物理節(jié)點(diǎn)篮奄，怎么從其他節(jié)點(diǎn)遷移數(shù)據(jù)到新節(jié)點(diǎn)；
（3）對(duì)于可修改的數(shù)據(jù)（即不是只能追加的數(shù)據(jù)），比如數(shù)據(jù)庫(kù)數(shù)據(jù)宦搬，如果某節(jié)點(diǎn)數(shù)據(jù)量變大牙瓢，怎么將部分?jǐn)?shù)據(jù)遷移到其他負(fù)載較小的節(jié)點(diǎn)，及達(dá)到動(dòng)態(tài)均衡的效果间校。
（4）元數(shù)據(jù)的管理問(wèn)題：當(dāng)數(shù)據(jù)分布在各個(gè)節(jié)點(diǎn)矾克，那么當(dāng)用戶使用的時(shí)候需要知道具體的數(shù)據(jù)在哪一個(gè)節(jié)點(diǎn)上。因此憔足，系統(tǒng)需要維護(hù)數(shù)據(jù)的元數(shù)據(jù)：即每一個(gè)數(shù)據(jù)所在的位置胁附、狀態(tài)等信息。當(dāng)用戶需要具體的數(shù)據(jù)時(shí)滓彰，先查詢?cè)獢?shù)據(jù)控妻，然后再去具體的節(jié)點(diǎn)上查詢。當(dāng)數(shù)據(jù)在節(jié)點(diǎn)之間遷移的時(shí)候揭绑，也需要更新元數(shù)據(jù)弓候。元數(shù)據(jù)的管理節(jié)點(diǎn)這里稱之為meta server。元數(shù)據(jù)的管理也帶來(lái)了新的挑戰(zhàn)：
（4.1）如何抽取數(shù)據(jù)的特征（特征是分片的依據(jù)他匪，也是用戶查詢數(shù)據(jù)時(shí)的key）菇存，或者支持用戶自定義數(shù)據(jù)特征；
（4.2）如何保證meta server的高性能和高可用邦蜜，是單點(diǎn)還是復(fù)制集
（5）分片的粒度依鸥，即數(shù)據(jù)子集的大小，也是數(shù)據(jù)遷移的基本單位悼沈。粒度過(guò)粗贱迟，不利于數(shù)據(jù)均衡；粒度過(guò)細(xì)絮供，管理衣吠、遷移成本又會(huì)比較大。
數(shù)據(jù)冗余
前面提到壤靶，分布式系統(tǒng)中的節(jié)點(diǎn)都是普通的節(jié)點(diǎn)蒸播，因此有一定的概率會(huì)出現(xiàn)物理故障，比如斷電萍肆、網(wǎng)絡(luò)不可用袍榆，這些故障導(dǎo)致數(shù)據(jù)的暫時(shí)不可用；另外一些故障更嚴(yán)重塘揣，會(huì)導(dǎo)致數(shù)據(jù)的丟失包雀，比如磁盤損壞。即使單個(gè)節(jié)點(diǎn)的故障是小概率亲铡，當(dāng)集群中的節(jié)點(diǎn)數(shù)目很多是才写，故障就成為了一個(gè)大概率事件葡兑。因此，保證數(shù)據(jù)的高可用和可靠性是分布式系統(tǒng)必須解決的問(wèn)題赞草。
為了避免單點(diǎn)故障讹堤，可行的辦法就是數(shù)據(jù)冗余（復(fù)制集），即將同一份數(shù)據(jù)放在不同的物理節(jié)點(diǎn)厨疙，甚至是不同的數(shù)據(jù)中心洲守。如果數(shù)據(jù)是一次寫，多次讀那很好辦沾凄，隨便從哪個(gè)副本讀取都行梗醇。但對(duì)于很多分布式存儲(chǔ)系統(tǒng)，比如數(shù)據(jù)庫(kù)撒蟀，數(shù)據(jù)是持續(xù)變化的叙谨，有讀有寫。那么復(fù)制集會(huì)帶來(lái)什么樣的挑戰(zhàn)呢保屯，需要如何權(quán)衡呢手负，假設(shè)有三個(gè)副本：
（1）三個(gè)副本的地位，大家都是平等的還是有主（primary姑尺、master）有次（secondary竟终、slave），如果是平等的股缸，那么每個(gè)節(jié)點(diǎn)都可以接收寫操作；如果不平等吱雏，可以一個(gè)節(jié)點(diǎn)負(fù)責(zé)所有的寫操作敦姻，所有節(jié)點(diǎn)都提供讀操作，
（2）在平等的情況下歧杏，怎么保證寫入操作不沖突镰惦，保證各個(gè)節(jié)點(diǎn)的數(shù)據(jù)是一致的，怎么保證能讀取到最新的數(shù)據(jù)
（3）不平等的情況下
（3.1）寫節(jié)點(diǎn)怎么將變更的數(shù)據(jù)同步到其他節(jié)點(diǎn)犬绒，同步還是異步旺入；
（3.2）非寫節(jié)點(diǎn)能否提供讀數(shù)據(jù)，如果能夠允許凯力，會(huì)不會(huì)讀取到過(guò)時(shí)的數(shù)據(jù)茵瘾。
（3.3）主節(jié)點(diǎn)是怎么產(chǎn)生的，當(dāng)主節(jié)點(diǎn)宕機(jī)的時(shí)候咐鹤，怎么選擇出新的主節(jié)點(diǎn)拗秘。是有統(tǒng)一的復(fù)制集管理中心（記錄誰(shuí)主誰(shuí)次，各自的狀態(tài)）祈惶，還是復(fù)制集自己選舉出一個(gè)主節(jié)點(diǎn)雕旨？
（4）不管復(fù)制集內(nèi)部的節(jié)點(diǎn)是平等的扮匠，還是有集中式節(jié)點(diǎn)的，只要有多個(gè)數(shù)據(jù)副本凡涩，就需要考慮數(shù)據(jù)的一致性可用性問(wèn)題棒搜。按照CAP理論，只能同時(shí)滿足一致性 可用性 分區(qū)容錯(cuò)性之間的二者活箕，不同的分布式系統(tǒng)需要權(quán)衡力麸。
在前文中，提出了分布式系統(tǒng)（尤其是分布式存儲(chǔ)系統(tǒng)）需要解決的兩個(gè)最主要的問(wèn)題讹蘑，即數(shù)據(jù)分片和數(shù)據(jù)冗余末盔，下面這個(gè)圖片形象生動(dòng)的解釋了其概念和區(qū)別：
其中數(shù)據(jù)即A、B屬于數(shù)據(jù)分片座慰，原始數(shù)據(jù)被拆分成兩個(gè)正交子集分布在兩個(gè)節(jié)點(diǎn)上陨舱。而數(shù)據(jù)集C屬于數(shù)據(jù)冗余，同一份完整的數(shù)據(jù)在兩個(gè)節(jié)點(diǎn)都有存儲(chǔ)版仔。當(dāng)然游盲，在實(shí)際的分布式系統(tǒng)中，數(shù)據(jù)分片和數(shù)據(jù)冗余一般都是共存的蛮粮。
本文主要討論數(shù)據(jù)分片的三個(gè)問(wèn)題：
（1）如何做數(shù)據(jù)分片益缎，即如何將數(shù)據(jù)映射到節(jié)點(diǎn)
（2）數(shù)據(jù)分片的特征值，即按照數(shù)據(jù)中的哪一個(gè)屬性（字段）來(lái)分片
（3）數(shù)據(jù)分片的元數(shù)據(jù)的管理然想，如何保證元數(shù)據(jù)服務(wù)器的高性能莺奔、高可用，如果是一組服務(wù)器变泄，如何保證強(qiáng)一致性
所謂分布式系統(tǒng)令哟，就是利用多個(gè)獨(dú)立的計(jì)算機(jī)來(lái)解決單個(gè)節(jié)點(diǎn)（計(jì)算機(jī)）無(wú)法處理的存儲(chǔ)、計(jì)算問(wèn)題妨蛹，這是非常典型的分而治之的思想屏富。每個(gè)節(jié)點(diǎn)只負(fù)責(zé)原問(wèn)題（即整個(gè)系統(tǒng)需要完成的任務(wù)）的一個(gè)子集，那么原問(wèn)題如何拆分到多個(gè)節(jié)點(diǎn)蛙卤？在分布式存儲(chǔ)系統(tǒng)中狠半，任務(wù)的拆分即數(shù)據(jù)分片。
何為數(shù)據(jù)分片（segment颤难，fragment神年， shard， partition）行嗤，就是按照一定的規(guī)則瘤袖，將數(shù)據(jù)集劃分成相互獨(dú)立、正交的數(shù)據(jù)子集昂验，然后將數(shù)據(jù)子集分布到不同的節(jié)點(diǎn)上捂敌。注意艾扮，這里提到，數(shù)據(jù)分片需要按照一定的規(guī)則，不同的分布式應(yīng)用有不同的規(guī)則，但都遵循同樣的原則：按照最主要趾痘、最頻繁使用的訪問(wèn)方式來(lái)分片。
三種數(shù)據(jù)分片方式
首先介紹三種分片方式：hash方式酌予，一致性hash（consistent hash），按照數(shù)據(jù)范圍（range based）奖慌。對(duì)于任何方式抛虫，都需要思考以下幾個(gè)問(wèn)題：
具體如何劃分原始數(shù)據(jù)集？
當(dāng)原問(wèn)題的規(guī)模變大的時(shí)候简僧，能否通過(guò)增加節(jié)點(diǎn)來(lái)動(dòng)態(tài)適應(yīng)建椰？
當(dāng)某個(gè)節(jié)點(diǎn)故障的時(shí)候，能否將該節(jié)點(diǎn)上的任務(wù)均衡的分?jǐn)偟狡渌?jié)點(diǎn)岛马？
對(duì)于可修改的數(shù)據(jù)（比如數(shù)據(jù)庫(kù)數(shù)據(jù)）棉姐，如果某節(jié)點(diǎn)數(shù)據(jù)量變大，能否以及如何將部分?jǐn)?shù)據(jù)遷移到其他負(fù)載較小的節(jié)點(diǎn)啦逆，及達(dá)到動(dòng)態(tài)均衡的效果伞矩？
元數(shù)據(jù)的管理（即數(shù)據(jù)與物理節(jié)點(diǎn)的對(duì)應(yīng)關(guān)系）規(guī)模？元數(shù)據(jù)更新的頻率以及復(fù)雜度夏志？
為了后面分析不同的數(shù)據(jù)分片方式乃坤，假設(shè)有三個(gè)物理節(jié)點(diǎn)，編號(hào)為N0沟蔑， N1湿诊， N2；有以下幾條記錄：
R0: {id: 95, name: ‘a(chǎn)a’, tag:’older’}
R1: {id: 302, name: ‘bb’,}
R2: {id: 759, name: ‘a(chǎn)a’,}
R3: {id: 607, name: ‘dd’, age: 18}
R4: {id: 904, name: ‘ff’,}
R5: {id: 246, name: ‘gg’,}
R6: {id: 148, name: ‘ff’,}
R7: {id: 533, name: ‘kk’,}
hash方式
哈希表（散列表）是最為常見的數(shù)據(jù)結(jié)構(gòu)溉贿，根據(jù)記錄（或者對(duì)象）的關(guān)鍵值將記錄映射到表中的一個(gè)槽（slot）枫吧，便于快速訪問(wèn)浦旱。絕大多數(shù)編程語(yǔ)言都有對(duì)hash表的支持宇色，如python中的dict， C++中的map颁湖，Java中的Hashtable宣蠕， Lua中的table等等。在哈希表中甥捺，最為簡(jiǎn)單的散列函數(shù)是 mod N（N為表的大星朗础）。即首先將關(guān)鍵值計(jì)算出hash值（這里是一個(gè)整型）镰禾，通過(guò)對(duì)N取余皿曲，余數(shù)即在表中的位置唱逢。
數(shù)據(jù)分片的hash方式也是這個(gè)思想，即按照數(shù)據(jù)的某一特征（key）來(lái)計(jì)算哈希值屋休，并將哈希值與系統(tǒng)中的節(jié)點(diǎn)建立映射關(guān)系,從而將哈希值不同的數(shù)據(jù)分布到不同的節(jié)點(diǎn)上坞古。
我們選擇id作為數(shù)據(jù)分片的key，那么各個(gè)節(jié)點(diǎn)負(fù)責(zé)的數(shù)據(jù)如下：
由此可以看到劫樟，按照hash方式做數(shù)據(jù)分片痪枫，映射關(guān)系非常簡(jiǎn)單；需要管理的元數(shù)據(jù)也非常之少叠艳，只需要記錄節(jié)點(diǎn)的數(shù)目以及hash方式就行了奶陈。
但hash方式的缺點(diǎn)也非常明顯：當(dāng)加入或者刪除一個(gè)節(jié)點(diǎn)的時(shí)候，大量的數(shù)據(jù)需要移動(dòng)附较。比如在這里增加一個(gè)節(jié)點(diǎn)N3吃粒，因此hash方式變?yōu)榱薽od 4，數(shù)據(jù)的遷移如下：
在這種方式下翅睛，是不滿足單調(diào)性（Monotonicity）的：如果已經(jīng)有一些內(nèi)容通過(guò)哈希分派到了相應(yīng)的緩沖中声搁，又有新的緩沖加入到系統(tǒng)中。哈希的結(jié)果應(yīng)能夠保證原有已分配的內(nèi)容可以被映射到原有的或者新的緩沖中去捕发，而不會(huì)被映射到舊的緩沖集合中的其他緩沖區(qū)疏旨。
在工程中，為了減少遷移的數(shù)據(jù)量扎酷，節(jié)點(diǎn)的數(shù)目可以成倍增長(zhǎng)檐涝，這樣概率上來(lái)講至多有50%的數(shù)據(jù)遷移。
hash方式還有一個(gè)缺點(diǎn)法挨，即很難解決數(shù)據(jù)不均衡的問(wèn)題谁榜。有兩種情況：原始數(shù)據(jù)的特征值分布不均勻，導(dǎo)致大量的數(shù)據(jù)集中到一個(gè)物理節(jié)點(diǎn)上凡纳；第二窃植，對(duì)于可修改的記錄數(shù)據(jù)，單條記錄的數(shù)據(jù)變大荐糜。在這兩種情況下巷怜，都會(huì)導(dǎo)致節(jié)點(diǎn)之間的負(fù)載不均衡，而且在hash方式下很難解決暴氏。
一致性hash
一致性hash是將數(shù)據(jù)按照特征值映射到一個(gè)首尾相接的hash環(huán)上延塑，同時(shí)也將節(jié)點(diǎn)（按照IP地址或者機(jī)器名hash）映射到這個(gè)環(huán)上。對(duì)于數(shù)據(jù)答渔，從數(shù)據(jù)在環(huán)上的位置開始关带，順時(shí)針找到的第一個(gè)節(jié)點(diǎn)即為數(shù)據(jù)的存儲(chǔ)節(jié)點(diǎn)。這里仍然以上述的數(shù)據(jù)為例沼撕，假設(shè)id的范圍為［0宋雏， 1000］芜飘，N0， N1磨总， N2在環(huán)上的位置分別是100燃箭， 400， 800舍败，那么hash環(huán)示意圖與數(shù)據(jù)的分布如下：
可以看到相比于上述的hash方式招狸，一致性hash方式需要維護(hù)的元數(shù)據(jù)額外包含了節(jié)點(diǎn)在環(huán)上的位置，但這個(gè)數(shù)據(jù)量也是非常小的邻薯。
一致性hash在增加或者刪除節(jié)點(diǎn)的時(shí)候裙戏，受到影響的數(shù)據(jù)是比較有限的，比如這里增加一個(gè)節(jié)點(diǎn)N3厕诡，其在環(huán)上的位置為600累榜，因此，原來(lái)N2負(fù)責(zé)的范圍段（400灵嫌， 800］現(xiàn)在由N2（400壹罚， 600] N3(600, 800]負(fù)責(zé)，因此只需要將記錄R2(id:759), R3(id: 607) 從N2,遷移到N3:
不難發(fā)現(xiàn)一致性hash方式在增刪的時(shí)候只會(huì)影響到hash環(huán)上響應(yīng)的節(jié)點(diǎn)寿羞，不會(huì)發(fā)生大規(guī)模的數(shù)據(jù)遷移猖凛。
但是，一致性hash方式在增加節(jié)點(diǎn)的時(shí)候绪穆，只能分?jǐn)傄粋€(gè)已存在節(jié)點(diǎn)的壓力辨泳；同樣，在其中一個(gè)節(jié)點(diǎn)掛掉的時(shí)候玖院，該節(jié)點(diǎn)的壓力也會(huì)被全部轉(zhuǎn)移到下一個(gè)節(jié)點(diǎn)菠红。我們希望的是“一方有難，八方支援”难菌，因此需要在增刪節(jié)點(diǎn)的時(shí)候试溯，已存在的所有節(jié)點(diǎn)都能參與響應(yīng)，達(dá)到新的均衡狀態(tài)郊酒。
因此遇绞，在實(shí)際工程中，一般會(huì)引入虛擬節(jié)點(diǎn)（virtual node）的概念猎塞。即不是將物理節(jié)點(diǎn)映射在hash換上试读，而是將虛擬節(jié)點(diǎn)映射到hash環(huán)上杠纵。虛擬節(jié)點(diǎn)的數(shù)目遠(yuǎn)大于物理節(jié)點(diǎn)荠耽，因此一個(gè)物理節(jié)點(diǎn)需要負(fù)責(zé)多個(gè)虛擬節(jié)點(diǎn)的真實(shí)存儲(chǔ)。操作數(shù)據(jù)的時(shí)候比藻，先通過(guò)hash環(huán)找到對(duì)應(yīng)的虛擬節(jié)點(diǎn)铝量，再通過(guò)虛擬節(jié)點(diǎn)與物理節(jié)點(diǎn)的映射關(guān)系找到對(duì)應(yīng)的物理節(jié)點(diǎn)倘屹。
引入虛擬節(jié)點(diǎn)后的一致性hash需要維護(hù)的元數(shù)據(jù)也會(huì)增加：第一，虛擬節(jié)點(diǎn)在hash環(huán)上的問(wèn)題慢叨，且虛擬節(jié)點(diǎn)的數(shù)目又比較多纽匙；第二，虛擬節(jié)點(diǎn)與物理節(jié)點(diǎn)的映射關(guān)系拍谐。但帶來(lái)的好處是明顯的烛缔，當(dāng)一個(gè)物理節(jié)點(diǎn)失效是，hash環(huán)上多個(gè)虛擬節(jié)點(diǎn)失效轩拨，對(duì)應(yīng)的壓力也就會(huì)發(fā)散到多個(gè)其余的虛擬節(jié)點(diǎn)践瓷，事實(shí)上也就是多個(gè)其余的物理節(jié)點(diǎn)。在增加物理節(jié)點(diǎn)的時(shí)候同樣如此亡蓉。
工程中晕翠，Dynamo、Cassandra都使用了一致性hash算法砍濒，且在比較高的版本中都使用了虛擬節(jié)點(diǎn)的概念淋肾。在這些系統(tǒng)中，需要考慮綜合考慮數(shù)據(jù)分布方式和數(shù)據(jù)副本爸邢，當(dāng)引入數(shù)據(jù)副本之后樊卓，一致性hash方式也需要做相應(yīng)的調(diào)整， 可以參加cassandra的相關(guān)文檔杠河。
range based
簡(jiǎn)單來(lái)說(shuō)简识，就是按照關(guān)鍵值劃分成不同的區(qū)間，每個(gè)物理節(jié)點(diǎn)負(fù)責(zé)一個(gè)或者多個(gè)區(qū)間感猛。其實(shí)這種方式跟一致性hash有點(diǎn)像七扰，可以理解為物理節(jié)點(diǎn)在hash環(huán)上的位置是動(dòng)態(tài)變化的。
還是以上面的數(shù)據(jù)舉例陪白，三個(gè)節(jié)點(diǎn)的數(shù)據(jù)區(qū)間分別是N0(0, 200]颈走， N1(200, 500]， N2(500, 1000]咱士。那么數(shù)據(jù)分布如下：
注意立由，區(qū)間的大小不是固定的，每個(gè)數(shù)據(jù)區(qū)間的數(shù)據(jù)量與區(qū)間的大小也是沒(méi)有關(guān)系的序厉。比如說(shuō)锐膜，一部分?jǐn)?shù)據(jù)非常集中，那么區(qū)間大小應(yīng)該是比較小的弛房，即以數(shù)據(jù)量的大小為片段標(biāo)準(zhǔn)道盏。在實(shí)際工程中，一個(gè)節(jié)點(diǎn)往往負(fù)責(zé)多個(gè)區(qū)間，每個(gè)區(qū)間成為一個(gè)塊（chunk荷逞、block）媒咳，每個(gè)塊有一個(gè)閾值，當(dāng)達(dá)到這個(gè)閾值之后就會(huì)分裂成兩個(gè)塊种远。這樣做的目的在于當(dāng)有節(jié)點(diǎn)加入的時(shí)候涩澡，可以快速達(dá)到均衡的目的。
不知道讀者有沒(méi)有發(fā)現(xiàn)坠敷，如果一個(gè)節(jié)點(diǎn)負(fù)責(zé)的數(shù)據(jù)只有一個(gè)區(qū)間妙同，range based與沒(méi)有虛擬節(jié)點(diǎn)概念的一致性hash很類似；如果一個(gè)節(jié)點(diǎn)負(fù)責(zé)多個(gè)區(qū)間膝迎，range based與有虛擬節(jié)點(diǎn)概念的一致性hash很類似渐溶。
range based的元數(shù)據(jù)管理相對(duì)復(fù)雜一些，需要記錄每個(gè)節(jié)點(diǎn)的數(shù)據(jù)區(qū)間范圍弄抬，特別單個(gè)節(jié)點(diǎn)對(duì)于多個(gè)區(qū)間的情況茎辐。而且，在數(shù)據(jù)可修改的情況下掂恕，如果塊進(jìn)行分裂拖陆，那么元數(shù)據(jù)中的區(qū)間信息也需要同步修改。
range based這種數(shù)據(jù)分片方式應(yīng)用非常廣泛懊亡，比如MongoDB, PostgreSQL依啰， HDFS
小結(jié)
在這里對(duì)三種分片方式（應(yīng)該是四種，有沒(méi)有virtual node的一致性hash算兩種）進(jìn)行簡(jiǎn)單總結(jié)店枣，主要是針對(duì)提出的幾個(gè)問(wèn)題：
上面的數(shù)據(jù)動(dòng)態(tài)均衡速警，值得是上述問(wèn)題的第4點(diǎn)，即如果某節(jié)點(diǎn)數(shù)據(jù)量變大鸯两，能否以及如何將部分?jǐn)?shù)據(jù)遷移到其他負(fù)載較小的節(jié)點(diǎn)
分片特征值的選擇
上面的三種方式都提到了對(duì)數(shù)據(jù)的分片是基于關(guān)鍵值闷旧、特征值的。這個(gè)特征值在不同的系統(tǒng)中有不同的叫法钧唐，比如MongoDB中的sharding key忙灼， Oracle中的Partition Key，不管怎么樣钝侠，這個(gè)特征值的選擇都是非常非常重要的该园。
那么。怎么選擇這個(gè)特征值呢帅韧？《Distributed systems for fun and profit》給出了言簡(jiǎn)意賅的標(biāo)準(zhǔn)：
based on what you think the primary access pattern will be
大概翻譯為：基于最常用的訪問(wèn)模式里初。訪問(wèn)時(shí)包括對(duì)數(shù)據(jù)的增刪改查的。比如上面的列子忽舟，我們選擇“id”作為分片的依據(jù)双妨，那么就是默認(rèn)對(duì)的數(shù)據(jù)增刪改查都是通過(guò)“id”字段來(lái)進(jìn)行的淮阐。
如果在應(yīng)用中，大量的數(shù)據(jù)操作都是通過(guò)這個(gè)特征值進(jìn)行斥难，那么數(shù)據(jù)分片就能提供兩個(gè)額外的好處：
（1）提升性能和并發(fā)，操作被分發(fā)到不同的分片帘饶，相互獨(dú)立
（2）提升系統(tǒng)的可用性哑诊，即使部分分片不能用，其他分片不會(huì)受到影響
如果大量操作并沒(méi)有使用到特征值及刻，那么就很麻煩了镀裤。比如在本文的例子中，如果用name去查詢缴饭，而元數(shù)據(jù)記錄的是如何根據(jù)按照id映射數(shù)據(jù)位置暑劝，那就尷尬了，需要到多有分片都去查一下颗搂，然后再做一個(gè)聚合担猛！
另外一個(gè)問(wèn)題，如果以單個(gè)字段為特征值（如id）丢氢，那么不管按照什么分布方式傅联，在多條數(shù)據(jù)擁有相同的特征值（如id）的情況下，這些數(shù)據(jù)一定都會(huì)分布到同一個(gè)節(jié)點(diǎn)上疚察。在這種情況下有兩個(gè)問(wèn)題蒸走，一是不能達(dá)到節(jié)點(diǎn)間數(shù)據(jù)的均衡，二是如果數(shù)據(jù)超過(guò)了單個(gè)節(jié)點(diǎn)的存儲(chǔ)能力怎么辦貌嫡？關(guān)鍵在于比驻，即使按照分布式系統(tǒng)解決問(wèn)題的常規(guī)辦法 — 增加節(jié)點(diǎn) –也是于事無(wú)補(bǔ)的。
在這個(gè)時(shí)候岛抄，單個(gè)字段做特征值就不行了别惦，可能得再增加一個(gè)字段作為“聯(lián)合特征值”，類似數(shù)據(jù)庫(kù)中的聯(lián)合索引夫椭。比如步咪，數(shù)據(jù)是用戶的操作日志，可以使用id和時(shí)間戳一起作為hash函數(shù)的輸入益楼，然后算出特征值猾漫；但在這種情況下，如果還想以id為查詢關(guān)鍵字來(lái)查詢感凤，那就得遍歷所有節(jié)點(diǎn)了悯周。
所以說(shuō)沒(méi)有最優(yōu)的設(shè)計(jì)，只有最符合應(yīng)用需求的設(shè)計(jì)陪竿。
下面以MongoDB中的sharding key為例禽翼，解釋特征值選擇的重要性以及對(duì)數(shù)據(jù)操作的影響屠橄。如果有數(shù)據(jù)庫(kù)操作基礎(chǔ)，即使沒(méi)有使用過(guò)MongoDB闰挡，閱讀下面的內(nèi)容應(yīng)該也沒(méi)有問(wèn)題锐墙。
以MongoDB sharding key為例
關(guān)于MongoDB Sharded cluster，之前也寫過(guò)一篇文章《通過(guò)一步步創(chuàng)建sharded cluster來(lái)認(rèn)識(shí)mongodb》长酗，做了簡(jiǎn)單介紹溪北。在我的工作場(chǎng)景中，除了聯(lián)合查詢（join）和事務(wù)夺脾，MongoDB的使用和Mysql還是比較相似的之拨，特別是基本的CRUD操作、數(shù)據(jù)庫(kù)索引咧叭。MongoDb中蚀乔，每一個(gè)分片成為一個(gè)shard，分片的特征值成為sharding key菲茬，每個(gè)數(shù)據(jù)稱之為一個(gè)document吉挣。選擇適合的字段作為shardingkey非常重要，why婉弹？
前面也提到听想，如果使用非sharding key去訪問(wèn)數(shù)據(jù)，那么元數(shù)據(jù)服務(wù)器（或者元數(shù)據(jù)緩存服務(wù)器马胧，后面會(huì)講解這一部分）是沒(méi)法知道對(duì)應(yīng)的數(shù)據(jù)在哪一個(gè)shard上汉买，那么該訪問(wèn)就得發(fā)送到所有的shard，得到所有shard的結(jié)果之后再做聚合佩脊，在mongoDB中蛙粘，由mongos（緩存有元數(shù)據(jù)信息）做數(shù)據(jù)聚合。對(duì)于數(shù)據(jù)讀韧谩（R： read or retrieve）出牧，通過(guò)同一個(gè)字段獲取到多個(gè)數(shù)據(jù)，是沒(méi)有問(wèn)題的歇盼，只是效率比較低而已舔痕。對(duì)于數(shù)據(jù)更新，如果只能更新一個(gè)數(shù)據(jù)豹缀，那么在哪一個(gè)shard上更新呢伯复，似乎都不對(duì)，這個(gè)時(shí)候邢笙，MongoDB是拒絕的啸如。對(duì)應(yīng)到MongoDB（MongoDD3.0）的命令包括但不限于：
- findandmodify：這個(gè)命令只能更新一個(gè)document，因此查詢部分必須包含sharding key
When using findAndModify in a sharded environment, the query must contain the shard key for all operations against the shard cluster for the sharded collections.
- update：這個(gè)命令有一個(gè)參數(shù)multi氮惯，默認(rèn)是false叮雳，即只能更新一個(gè)document想暗，此時(shí)查詢部分必須包含sharding key
All update() operations for a sharded collection that specify the multi: false option must include theshard key or the _id field in the query specification.
- remove：有一個(gè)參數(shù)JustOne，如果為True帘不，只能刪除一個(gè)document说莫，也必須使用sharidng key
另外，熟悉sql的同學(xué)都知道寞焙，在數(shù)據(jù)中索引中有unique index（唯一索引）储狭，即保證這個(gè)字段的值在table中是唯一的。mongoDB中棺弊，也可以建立unique index晶密，但是在sharded cluster環(huán)境下擒悬，只能對(duì)sharding key創(chuàng)建unique index模她，道理也很簡(jiǎn)單，如果unique index不是sharidng key懂牧，那么插入的時(shí)候就得去所有shard上查看侈净，而且還得加鎖敷存。
接下來(lái)绅项，討論分片到shard上的數(shù)據(jù)不均的問(wèn)題和屎，如果一段時(shí)間內(nèi)shardkey過(guò)于集中（比如按時(shí)間增長(zhǎng)）端铛，那么數(shù)據(jù)只往一個(gè)shard寫入别伏，導(dǎo)致無(wú)法平衡集群壓力崇败。
MongoDB中提供了”range partition“和”hash partition“菌瘫，這個(gè)跟上面提到的分片方式 hash方式熊户， ranged based不是一回事兒途事，而是指對(duì)sharding key處理验懊。MongoDB一定是ranged base分片方式,document中如是說(shuō)：
MongoDB partitions data in the collection using ranges of shard key values. Each range defines a non-overlapping range of shard key values and is associated with a chunk.
那么什么是”range partition”和”hash partition”，官網(wǎng)的一張圖很好說(shuō)明了二者的區(qū)別：
上圖左是range partition尸变，右是hash partition义图。range partition就是使用字段本身作為分片的邊界，比如上圖的x召烂；而hash partition會(huì)將字段重新hash到一個(gè)更大碱工、更離散的值域區(qū)間。
hash partition的最大好處在于保證數(shù)據(jù)在各個(gè)節(jié)點(diǎn)上均勻分布（這里的均勻指的是在寫入的時(shí)候就均勻奏夫，而不是通過(guò)MongoDB的balancing功能）怕篷。比如MongoDB中默認(rèn)的_id是objectid，objectid是一個(gè)12個(gè)字節(jié)的BSON類型酗昼，前4個(gè)字節(jié)是機(jī)器的時(shí)間戳匙头，那么如果在同一時(shí)間大量創(chuàng)建以O(shè)bjectId為_id的數(shù)據(jù) 會(huì)分配到同一個(gè)shard上，此時(shí)若將_id設(shè)置為hash index 和 hash sharding key仔雷，就不會(huì)有這個(gè)問(wèn)題蹂析。
當(dāng)然舔示，hash partition相比range partition也有一個(gè)很大的缺點(diǎn)，就是范圍查詢的時(shí)候效率低电抚！因此到底選用hash partition還是range partition還得根據(jù)應(yīng)用場(chǎng)景來(lái)具體討論惕稻。
最后得知道，sharding key一但選定蝙叛，就無(wú)法修改（Immutable）俺祠。如果應(yīng)用必須要修改sharidng key，那么只能將數(shù)據(jù)導(dǎo)出借帘，新建數(shù)據(jù)庫(kù)并創(chuàng)建新的sharding key蜘渣，最后導(dǎo)入數(shù)據(jù)。
元數(shù)據(jù)服務(wù)器
在上面討論的三種數(shù)據(jù)分片分式中肺然，或多或少都會(huì)記錄一些元數(shù)據(jù)：數(shù)據(jù)與節(jié)點(diǎn)的映射關(guān)系蔫缸、節(jié)點(diǎn)狀態(tài)等等。我們稱記錄元數(shù)據(jù)的服務(wù)器為元數(shù)據(jù)服務(wù)器（metaserver）际起，不同的系統(tǒng)叫法不一樣拾碌，比如master、configserver街望、namenode等校翔。
元數(shù)據(jù)服務(wù)器就像人類的大腦，一只手不能用了還沒(méi)忍受灾前，大腦不工作整個(gè)人就癱瘓了防症。因此，元數(shù)據(jù)服務(wù)器的高性能哎甲、高可用蔫敲，要達(dá)到這兩個(gè)目標(biāo)，元數(shù)據(jù)服務(wù)器就得高可擴(kuò)展 — 以此應(yīng)對(duì)元數(shù)據(jù)的增長(zhǎng)烧给。
元數(shù)據(jù)的高可用要求元數(shù)據(jù)服務(wù)器不能成為故障單點(diǎn)（single point of failure）燕偶，因此需要元數(shù)據(jù)服務(wù)器有多個(gè)備份，并且能夠在故障的時(shí)候迅速切換础嫡。
有多個(gè)備份指么，那么問(wèn)題就來(lái)了，怎么保證多個(gè)備份的數(shù)據(jù)一致性榴鼎？
多個(gè)副本的一致性伯诬、可用性是CAP理論討論的范疇，這里簡(jiǎn)單介紹兩種方案巫财。第一種是主從同步盗似，首先選出主服務(wù)器，只有主服務(wù)器提供對(duì)外服務(wù)平项，主服務(wù)器將元數(shù)據(jù)的變革信息以日志的方式持久化到共享存儲(chǔ)（例如nfs）赫舒，然后從服務(wù)器從共享存儲(chǔ)讀取日志并應(yīng)用悍及，達(dá)到與主服務(wù)器一致的狀態(tài)，如果主服務(wù)器被檢測(cè)到故障（比如通過(guò)心跳）接癌，那么會(huì)重新選出新的主服務(wù)器心赶。第二種方式，通過(guò)分布式一致性協(xié)議來(lái)達(dá)到多個(gè)副本件的一致缺猛，比如大名鼎鼎的Paxos協(xié)議缨叫，以及工程中使用較多的Paxos的特化版本 — Raft協(xié)議，協(xié)議可以實(shí)現(xiàn)所有備份均可以提供對(duì)外服務(wù)荔燎，并且保證強(qiáng)一致性耻姥。
HDFS元數(shù)據(jù)
HDFS中，元數(shù)據(jù)服務(wù)器被稱之為namenode有咨，在hdfs1.0之前琐簇，namenode還是單點(diǎn)，一旦namenode掛掉摔吏，整個(gè)系統(tǒng)就無(wú)法工作鸽嫂。在hdfs2.0纵装，解決了namenode的單點(diǎn)問(wèn)題征讲。
上圖中NN即NameNode， DN即DataNode（即實(shí)際存儲(chǔ)數(shù)據(jù)的節(jié)點(diǎn)）橡娄。從圖中可以看到诗箍， 兩臺(tái) NameNode 形成互備，一臺(tái)處于 Active 狀態(tài)挽唉，為主 NameNode滤祖，另外一臺(tái)處于 Standby 狀態(tài)，為備 NameNode瓶籽，只有主 NameNode 才能對(duì)外提供讀寫服務(wù)匠童。
Active NN與standby NN之間的數(shù)據(jù)同步通過(guò)共享存儲(chǔ)實(shí)現(xiàn)，共享存儲(chǔ)系統(tǒng)保證了Namenode的高可用塑顺。為了保證元數(shù)據(jù)的強(qiáng)一致性汤求，在進(jìn)行準(zhǔn)備切換的時(shí)候，新的Active NN必須要在確認(rèn)元數(shù)據(jù)完全同步之后才能繼續(xù)對(duì)外提供服務(wù)严拒。
另外扬绪，Namenode的狀態(tài)監(jiān)控以及準(zhǔn)備切換都是Zookeeper集群負(fù)責(zé)，在網(wǎng)絡(luò)分割（network partition）的情況下裤唠，有可能zookeeper認(rèn)為原來(lái)的Active NN掛掉了挤牛，選舉出新的ActiveNN，但實(shí)際上原來(lái)的Active NN還在繼續(xù)提供服務(wù)种蘸。這就導(dǎo)致了“雙主“或者腦裂（brain-split）現(xiàn)象墓赴。為了解決這個(gè)問(wèn)題竞膳，提出了fencing機(jī)制，也就是想辦法把舊的 Active NameNode 隔離起來(lái)诫硕，使它不能正常對(duì)外提供服務(wù)顶猜。
MongoDB元數(shù)據(jù)
MongoDB中，元數(shù)據(jù)服務(wù)器被稱為config server痘括。在MongoDB3.2中长窄，已經(jīng)不再建議使用三個(gè)鏡像(Mirrored)MongoDB實(shí)例作為config server，而是推薦使用復(fù)制集（replica set）作為config server纲菌，此舉的目的是增強(qiáng)config server的一致性挠日，而且config sever中mongod的數(shù)目也能從3個(gè)達(dá)到replica set的上線（50個(gè)節(jié)點(diǎn)），從而提高了可靠性翰舌。
在MongoDB3.0及之前的版本中嚣潜，元數(shù)據(jù)的讀寫按照下面的方式進(jìn)行：
When writing to the three config servers, a coordinator dispatches the same write commands to the three config servers and collects the results. Differing results indicate an inconsistent writes to the config servers and may require manual intervention.
MongoDB的官方文檔并沒(méi)有詳細(xì)解釋這一過(guò)程，不過(guò)在stackexchange上椅贱，有人指出這個(gè)過(guò)程是兩階段提交懂算。
MongoDB3.2及之后的版本，使用了replica set config server庇麦，在《CAP理論與MongoDB一致性计技、可用性的一些思考》文章中，詳細(xì)介紹了replica set的write concern山橄、read concern和read references垮媒，這三個(gè)選項(xiàng)會(huì)影響到復(fù)制集的一致性、可靠性與讀取性能航棱。在config server中睡雇，使用了WriteConcern：Majority；ReadConcern：Majority饮醇；ReadReferences：nearest它抱。
元數(shù)據(jù)的緩存
即使元數(shù)據(jù)服務(wù)器可以由一組物理機(jī)器組成，也保證了副本集之間的一致性問(wèn)題朴艰。但是如果每次對(duì)數(shù)據(jù)的請(qǐng)求都經(jīng)過(guò)元數(shù)據(jù)服務(wù)器的話观蓄，元數(shù)據(jù)服務(wù)器的壓力也是非常大的。很多應(yīng)用場(chǎng)景呵晚，元數(shù)據(jù)的變化并不是很頻繁蜘腌，因此可以在訪問(wèn)節(jié)點(diǎn)上做緩存，這樣應(yīng)用可以直接利用緩存數(shù)據(jù)進(jìn)行數(shù)據(jù)讀寫饵隙，減輕元數(shù)據(jù)服務(wù)器壓力撮珠。
在這個(gè)環(huán)境下，緩存的元數(shù)據(jù)必須與元數(shù)據(jù)服務(wù)器上的元數(shù)據(jù)一致，緩存的元數(shù)據(jù)必須是準(zhǔn)確的芯急，未過(guò)時(shí)的勺届。相反的例子是DNS之類的緩存，即使使用了過(guò)期的DNS緩存也不會(huì)有太大的問(wèn)題娶耍。
怎么達(dá)到緩存的強(qiáng)一致性呢免姿？比較容易想到的辦法是當(dāng)metadata變化的時(shí)候立即通知所有的緩存服務(wù)器（mongos），但問(wèn)題是通信有延時(shí)榕酒，不可靠胚膊。
解決不一致的問(wèn)題，一個(gè)比較常見的思路是版本號(hào)想鹰，比如網(wǎng)絡(luò)通信紊婉，通信協(xié)議可能會(huì)發(fā)生變化，通信雙方為了達(dá)成一致辑舷，那么可以使用版本號(hào)喻犁。在緩存一致性的問(wèn)題上，也可以使用版本號(hào)何缓，基本思路是請(qǐng)求的時(shí)候帶上緩存的版本號(hào)肢础，路由到具體節(jié)點(diǎn)之后比較實(shí)際數(shù)據(jù)的版本號(hào)，如果版本號(hào)不一致碌廓，那么表示緩存信息過(guò)舊传轰，此時(shí)需要從元數(shù)據(jù)服務(wù)器重新拉取元數(shù)據(jù)并緩存。在MongoDB中氓皱，mongos緩存上就是使用的這種辦法路召。
另外一種解決辦法勃刨，就是大名鼎鼎的lease機(jī)制 — “An Efficient Fault-Tolerant Mechanism for Distributed File Cache Consistency”波材，lease機(jī)制在分布式系統(tǒng)中使用非常廣泛，不僅僅用于分布式緩存身隐，在很多需要達(dá)成某種約定的地方都大顯身手廷区，在《分布式系統(tǒng)原理介紹》中，對(duì)lease機(jī)制有較為詳細(xì)的描述贾铝，下面對(duì)lease機(jī)制進(jìn)行簡(jiǎn)單介紹隙轻。
Lease機(jī)制
既然，Lease機(jī)制提出的時(shí)候是為了解決分布式存儲(chǔ)系統(tǒng)中緩存一致性的問(wèn)題垢揩，那么首先來(lái)看看Lease機(jī)制是怎么保證緩存的強(qiáng)一致性的玖绿。注意，為了方便后文描述叁巨，在本小節(jié)中斑匪，我們稱元數(shù)據(jù)服務(wù)器為服務(wù)器，緩存服務(wù)器為客戶端锋勺。
要點(diǎn)：
服務(wù)器向所有客戶端發(fā)送緩存數(shù)據(jù)的同時(shí)蚀瘸，頒發(fā)一個(gè)lease狡蝶，lease包含一個(gè)有限期（即過(guò)期時(shí)間）
lease的含義是：在這個(gè)有效期內(nèi)，服務(wù)器保證元數(shù)據(jù)不會(huì)發(fā)生變化
因此客戶端在這個(gè)有效期內(nèi)可以放心大膽的使用緩存的元數(shù)據(jù)贮勃，如果超過(guò)了有效期贪惹，就不能使用數(shù)據(jù)了，就得去服務(wù)器請(qǐng)求寂嘉。
如果外部請(qǐng)求修改服務(wù)器上的元數(shù)據(jù)（元數(shù)據(jù)的修改一定在服務(wù)器上進(jìn)行）奏瞬，那么服務(wù)器會(huì)阻塞修改請(qǐng)求，直到所有已頒發(fā)的lease過(guò)期泉孩，然后修改元數(shù)據(jù)丝格，并將新的元數(shù)據(jù)和新的lease發(fā)送到客戶端
如果元數(shù)據(jù)沒(méi)有發(fā)生變化，那么服務(wù)器也需要在之前已頒發(fā)的lease到期之間棵譬，重新給客戶端頒發(fā)新的lease（只有l(wèi)ease显蝌，沒(méi)有數(shù)據(jù)）
在Lease論文的標(biāo)題中，提到了“Fault-Tolerant”订咸，那么lease是怎么做到容錯(cuò)的呢曼尊。關(guān)鍵在于，只要服務(wù)器一旦發(fā)出數(shù)據(jù)和lease脏嚷，不關(guān)心客戶端是否收到數(shù)據(jù)骆撇，只要等待lease過(guò)期，就可以修改元數(shù)據(jù)父叙；另外神郊，lease的有效期通過(guò)過(guò)期時(shí)間（一個(gè)時(shí)間戳）來(lái)標(biāo)識(shí)，因此即使從服務(wù)器到客戶端的消息延時(shí)到達(dá)趾唱、或者重復(fù)發(fā)送都是沒(méi)有關(guān)系的涌乳。
不難發(fā)現(xiàn)，容錯(cuò)的前提是服務(wù)器與客戶端的時(shí)間要一致甜癞。如果服務(wù)器的時(shí)間比客戶端的時(shí)間慢夕晓，那么客戶端收到lease之后很快就過(guò)期了，lease機(jī)制就發(fā)揮不了作用悠咱；如果服務(wù)器的時(shí)間比客戶端的時(shí)間快蒸辆，那么就比較危險(xiǎn)，因?yàn)榭蛻舳藭?huì)在服務(wù)器已經(jīng)開始更新元數(shù)據(jù)的時(shí)候繼續(xù)使用緩存析既，工程中躬贡，通常將服務(wù)器的過(guò)期時(shí)間設(shè)置得比客戶端的略大，來(lái)解決這個(gè)問(wèn)題眼坏。為了保持時(shí)間的一致拂玻，最好的辦法是使用NTP（Network Time Protocol）來(lái)保證時(shí)鐘同步。
Lease機(jī)制的本質(zhì)是頒發(fā)者授予的在某一有效期內(nèi)的承諾，承諾的范圍是非常廣泛的：比如上面提到的cache纺讲；比如做權(quán)限控制擂仍，例如當(dāng)需要做并發(fā)控制時(shí)，同一時(shí)刻只給某一個(gè)節(jié)點(diǎn)頒發(fā)lease熬甚，只有持有l(wèi)ease的節(jié)點(diǎn)才可以修改數(shù)據(jù)逢渔；比如身份驗(yàn)證，例如在primary-secondary架構(gòu)中乡括，給節(jié)點(diǎn)頒發(fā)lease肃廓，只有持有l(wèi)ease的節(jié)點(diǎn)才具有primary身份；比如節(jié)點(diǎn)的狀態(tài)監(jiān)測(cè)诲泌，例如在primary-secondary架構(gòu)中監(jiān)測(cè)primary是否正常盲赊，這個(gè)后文再詳細(xì)介紹。
工程中敷扫，lease機(jī)制也有大量的應(yīng)用：GFS中使用Lease確定Chuck的Primary副本, Lease由Master節(jié)點(diǎn)頒發(fā)給primary副本哀蘑，持有Lease的副本成為primary副本。chubby通過(guò)paxos協(xié)議實(shí)現(xiàn)去中心化的選擇primary節(jié)點(diǎn)葵第，然后Secondary節(jié)點(diǎn)向primary節(jié)點(diǎn)發(fā)送lease绘迁，該lease的含義是：“承諾在lease時(shí)間內(nèi)，不選舉其他節(jié)點(diǎn)成為primary節(jié)點(diǎn)”卒密。chubby中缀台，primary節(jié)點(diǎn)也會(huì)向每個(gè)client節(jié)點(diǎn)頒發(fā)lease。該lease的含義是用來(lái)判斷client的死活狀態(tài)哮奇，一個(gè)client節(jié)點(diǎn)只有只有合法的lease膛腐，才能與chubby中的primary進(jìn)行讀寫操作。
總結(jié)
本文主要介紹分布式系統(tǒng)中的分片相關(guān)問(wèn)題鼎俘，包括三種分布方式：hash哲身、一致性hash、range based而芥，以及各自的優(yōu)缺點(diǎn)律罢。分片都是按照一定的特征值來(lái)進(jìn)行，特征值應(yīng)該從應(yīng)用的使用場(chǎng)景來(lái)選取棍丐，并結(jié)合MongoDB展示了特征值（mongodb中的sharding key）對(duì)數(shù)據(jù)操作的影響。分片信息（即元數(shù)據(jù)）需要專門的服務(wù)器存儲(chǔ)沧踏，元數(shù)據(jù)服務(wù)器是分布式存儲(chǔ)系統(tǒng)的核心歌逢，因此需要提到其可用性和可靠性，為了減輕元數(shù)據(jù)服務(wù)器的壓力翘狱，分布式系統(tǒng)中秘案，會(huì)在其他節(jié)點(diǎn)緩存元數(shù)據(jù)，緩存的元數(shù)據(jù)由帶來(lái)了一致性的挑戰(zhàn)，由此引入了Lease機(jī)制阱高。
