本博客在http://doc001.com/同步更新。
本文主要內(nèi)容翻譯自MySQL開發(fā)者Ulf Wendel在PHP Submmit 2013上所做的報(bào)告「Scaling database to million of nodes」论熙。翻譯過程中沒有全盤照搬原PPT持搜，按照自己的理解進(jìn)行了部分改寫泉粉。水平有限护盈，如有錯(cuò)誤和疏漏灵莲，歡迎指正路克。
本文是系列的第四篇，本系列所有文章如下：
- 百萬節(jié)點(diǎn)數(shù)據(jù)庫擴(kuò)展之道(5): NoSQL再討論
另外一些概念
組通信系統(tǒng)(group communication system)
設(shè)想一下琼开，你被要求為MySQL設(shè)計(jì)一個(gè)新的副本系統(tǒng)易结。這個(gè)副本系統(tǒng)里有一組MySQL服務(wù)器，你會(huì)選擇何種通信方式柜候？很顯然搞动，XML-RPC、Apache渣刷、HTTP鹦肿、PHP這樣的技術(shù)棧肯定會(huì)很慢辅柴。于是箩溃，你不得不直接處理網(wǎng)絡(luò)協(xié)議。你將會(huì)看到碌识，這個(gè)處理并不是很繁瑣碾篡。除了通信問題外虱而，另外一個(gè)重要的問題是如何確定組的成員筏餐。
組通信系統(tǒng)能夠極大地簡化上述的任務(wù)。它能夠提供不同保障的簡單牡拇、可理解的消息傳遞方法魁瞪。
組通信系統(tǒng)提供以下功能：
- 一組節(jié)點(diǎn)間的消息交換
- 知曉哪個(gè)節(jié)點(diǎn)在組內(nèi)
- 對網(wǎng)絡(luò)和路由細(xì)節(jié)進(jìn)行了抽象
- 提供不同保障的通信原語(communication primitive)
虛同步(virtual synchrony)
虛同步將多播(multicast)消息和組的概念融合到一起。在虛同步中惠呼，一個(gè)消息要么傳遞給所有的組成員导俘，要么一個(gè)都不傳遞。在消息被多播之前剔蹋，組內(nèi)的每一成員都同意它們是組的一部分,即形成一個(gè)組視圖(group view)旅薄。如果一個(gè)節(jié)點(diǎn)想加入或離開組，必須多播一個(gè)"視圖改變"(view change)消息泣崩。
例如少梁，組G1={P1,P2,P3}內(nèi)多播了三個(gè)消息M1、M2矫付、M3凯沪。節(jié)點(diǎn)P4想加入到組中，于是多播了一個(gè)"視圖改變"消息.而此時(shí)M3還在傳遞過程中买优，虛同步要求要么M3在視圖改變生效前傳遞到G1的所有成員妨马，要么一個(gè)都沒傳遞到挺举。
一個(gè)多播消息產(chǎn)生后，只有一種情況下可以不被投遞成功，那就是發(fā)送節(jié)點(diǎn)失效骄酗。繼續(xù)上面的例子凹联，組G2={P1,P2,P3,P4}多播了消息M5、M6瞻佛、M7。P4剛將消息M7傳遞給{P3}娇钱，然而伤柄，很不幸該節(jié)點(diǎn)崩潰了。P4的崩潰被P1注意到了文搂，觸發(fā)了一個(gè)“視圖改變”适刀。因?yàn)樾柰揭笙⒈粋鬟f給所有組成員，因此煤蹭，P3將M7丟棄掉笔喉，然后視圖改變才能生效。
虛同步提供可靠多播硝皂〕Ｖ浚可靠性可以由OSI模型中較高層次的協(xié)議提供，如TCP稽物。ISIS奄毡，一個(gè)早期的虛同步實(shí)現(xiàn)框架，使用了TCP協(xié)議的點(diǎn)對點(diǎn)連接來實(shí)現(xiàn)可靠服務(wù)贝或。TCP連接能夠自動(dòng)處理網(wǎng)絡(luò)錯(cuò)誤吼过，保證消息按序到達(dá)。但是咪奖，對于多個(gè)并發(fā)的TCP連接盗忱，消息的順序無法得到保證，不同連接消息的排序只能在應(yīng)用層實(shí)現(xiàn)羊赵。
原子廣播(atomic broadcast)將虛同步的所有消息進(jìn)行全序排序趟佃。當(dāng)虛同步在80年代中期被引入的時(shí)候，實(shí)際上明確允許其它的消息排序方法昧捷。例如闲昭，應(yīng)該能夠支持有消息交換概念的分布式應(yīng)用，利用該概念料身，可以改變消息發(fā)送的順序以提高性能汤纸。如果事件在不同的節(jié)點(diǎn)上以不同的順序執(zhí)行，那么系統(tǒng)就不能稱之為同步了——應(yīng)該稱之為虛擬同步芹血。
上面這坨的邏輯實(shí)在沒搞清楚贮泞！翻譯也感覺不到位楞慈，附上原文：
Atomic broadcast means Virtual Synchrony used with total-order message ordering. When Virtual Synchrony was introduced back in the mid 80s, it was explicitly designed to allow other message orderings. For example, it should be able to support distributed applications that have a notion of finding messages that commute, and thus may be applied in an order different from the order sent to improve performace. If events are applied in different order on different processes, the system cannot be called synchronous any more – the inventors called it virtually synchronous.
CAP再討論
腦裂
集群中孤立的節(jié)點(diǎn)或數(shù)據(jù)庫副本失效的情況已經(jīng)被討論過了。現(xiàn)在考慮這種情況：集群的一半節(jié)點(diǎn)與另一半節(jié)點(diǎn)失去了連接啃擦，哪半個(gè)集群會(huì)生存下來囊蓝？答案通常是實(shí)現(xiàn)相關(guān)的。例如令蛉，ISIS指定了一條規(guī)則聚霜，新的組視圖不應(yīng)該少于n/2+1個(gè)成員才能生效，其中n是當(dāng)前組成員的數(shù)量珠叔。因此蝎宇，在這個(gè)例子中，這兩個(gè)半數(shù)節(jié)點(diǎn)的集群都不會(huì)生存下來祷安。
CAP中隱藏的D
CAP中其實(shí)就隱含了ACID中的D(持久化)姥芥。
CAP中的C要求所有的節(jié)點(diǎn)都獲得全部的更新。正如我們看到的一樣汇鞭，事務(wù)更新必須序列化以達(dá)到節(jié)點(diǎn)間的一致性凉唐。因此，節(jié)點(diǎn)必須以定義好的順序獲得所有更新霍骄。進(jìn)一步台囱，節(jié)點(diǎn)必須從來不會(huì)丟失任何一個(gè)更新。那么读整，更新必須被持久化簿训！
從D到A
CAP理論說我們不可能同時(shí)實(shí)現(xiàn)一致性、可用性和分區(qū)容忍性绘沉。為了實(shí)現(xiàn)分區(qū)容忍性和一致性煎楣，我們需要法定人數(shù)協(xié)議豺总，這就是CP系統(tǒng)车伞。選舉人數(shù)協(xié)議會(huì)使系統(tǒng)變得很慢，因?yàn)槲覀儾荒苤粡囊粋€(gè)節(jié)點(diǎn)讀取消息喻喳，取而代之另玖，我們必須從很多個(gè)節(jié)點(diǎn)讀取消息。這其實(shí)就是CAP中A的終極含義：數(shù)據(jù)最終會(huì)變得一致表伦，只是整個(gè)過程很慢...
CP系統(tǒng)如果使用選舉人數(shù)協(xié)議谦去，ACID中的A就被違反了，因?yàn)椴⒎撬械墓?jié)點(diǎn)都應(yīng)用了更新蹦哼，而A鳄哭，原子性，意味著“要么都做纲熏，要么都不做”妆丘。但是锄俄，如果更新是持久化的，這個(gè)更新永遠(yuǎn)不會(huì)被“忘記”勺拣，它總能被看到奶赠，我們得到了A。因此药有，D是A的前置條件毅戈。
C不是一個(gè)障礙
CAP中的C對于實(shí)現(xiàn)ACID來說也不是一個(gè)阻礙。
一致性意味著我們不得不在所有的節(jié)點(diǎn)上按照確定的順序應(yīng)用更新愤惰。這很容易通過主副本方案做到苇经。在該方案中，所有的更新都會(huì)被路由到主副本宦言，主副本確定更新的順序塑陵，把更新發(fā)送給其它的副本。我們只需要在主副本和副本之間建立FIFO消息通道即可(例如TCP連接)蜡励，這不會(huì)對延時(shí)造成負(fù)面影響令花。
在更新時(shí)需要鎖嗎？不需要凉倚！首先兼都，我們有主副本，主副本對消息的排序能夠處理寫沖突稽寒；其次扮碧，我們可以引入多版本并發(fā)控制(multi version concurrency control，MVCC)消除讀寫沖突杏糙。
因此慎王，ACI都不是問題。我們真正需要的是D宏侍！
避免慢的讀選舉人
如果我們能夠立刻移除失效節(jié)點(diǎn)赖淤，那么就不會(huì)受到慢讀選舉人的影響，失效節(jié)點(diǎn)也不會(huì)導(dǎo)致不一致的過期數(shù)據(jù)谅河。
如果一個(gè)節(jié)點(diǎn)組里所有的節(jié)點(diǎn)都是最新咱旱、一致的，那么讀操作可以由任何一個(gè)成員服務(wù)绷耍。讀速度將比選舉人讀快很多吐限。虛同步做到了這一點(diǎn)。
視圖改變
如果一個(gè)虛同步組的成員認(rèn)為一個(gè)節(jié)點(diǎn)失效了褂始，就會(huì)進(jìn)行一次排除失效節(jié)點(diǎn)的投票诸典，這個(gè)過程就是「視圖改變」。更新操作必須等待到「視圖改變」過程結(jié)束才能進(jìn)行崎苗。BASE理論中也有類似的等待機(jī)制狐粱，BASE需要等待寫選舉人達(dá)成一致后赘阀，才能進(jìn)行其它更新操作。無論在虛同步還是在BASE中脑奠，等待操作都是昂貴的基公。
FLP不可能理論告訴我們在異步網(wǎng)絡(luò)中無法區(qū)分「慢」節(jié)點(diǎn)和「失效」節(jié)點(diǎn)。實(shí)際系統(tǒng)采取的做法是設(shè)置一個(gè)超時(shí)時(shí)間宋欺，超過超時(shí)時(shí)間未收到應(yīng)答就認(rèn)為節(jié)點(diǎn)失效了轰豆。這個(gè)超時(shí)時(shí)間決定了更新操作被禁止的最大時(shí)長。禁止期間的更新操作可以先暫時(shí)緩存起來齿诞。注意酸休，此時(shí)系統(tǒng)仍然是一致的，只不過祷杈，我們在一致狀態(tài)下等待操作結(jié)果斑司。
D的成本
持久化的成本取決于網(wǎng)絡(luò)協(xié)議：
- 更新不能丟失，它們必須是持久的
- 強(qiáng)迫組通信系統(tǒng)在不可靠的網(wǎng)絡(luò)協(xié)議上使用Paxos
- 早期的ISIS^2在800節(jié)點(diǎn)但汞、千兆網(wǎng)絡(luò)上的數(shù)據(jù)顯示更新操作的平均延時(shí)是25ms宿刮，最大100ms
- Google Spanner的數(shù)據(jù)表明，100個(gè)spanserver的平均延時(shí)是70ms私蕾，最高150ms僵缺；200個(gè)spanserver的平均延時(shí)是150ms，最高350ms
CAP與ACID結(jié)合
CAP并不禁止構(gòu)建一個(gè)一致的踩叭、可用的磕潮、分區(qū)容忍的ACID兼容數(shù)據(jù)庫。Spanner和ISIS^2就是這樣的系統(tǒng)容贝。
放寬一致性
在很多場景下自脯，一致性能夠且必須被放寬，以換取更好的性能斤富。最出名的例子就是ATM膏潮。即使一個(gè)ATM機(jī)和銀行失聯(lián)了，余額未知茂缚，你仍然能夠存款戏罢。但是屋谭，有個(gè)限制脚囊，就是，ATM業(yè)務(wù)的特點(diǎn)決定弱一致能容忍誤差范圍很小桐磁。
如果你能夠接受99.999%的ATM顯示準(zhǔn)確的余額悔耘，不一致的窗口期最多1分鐘。那么系統(tǒng)可以在1分鐘內(nèi)先使用類似于ICMP我擂、Gossip之類的快速衬以、不可靠協(xié)議將值傳播開缓艳，然后主副本使用慢速但是100%可靠的方法傳播正確的值。
一個(gè)明顯的數(shù)據(jù)對比就是看峻，如果使用不可靠的協(xié)議阶淘，ISIS^2的延時(shí)只有2ms。對比下互妓，之前列出的數(shù)據(jù)是25ms溪窒。
一般系統(tǒng)的經(jīng)驗(yàn)就是，軟狀態(tài)(soft-state)可以接受弱一致冯勉，硬狀態(tài)(hard-state)必須是強(qiáng)一致澈蚌。弱一致分兩種，一種是時(shí)間限制的弱一致灼狰，即限制不一致的時(shí)間窗口宛瞄；一種是誤差限制的弱一致，即限制不一致期間值的偏差交胚。
ACID可以變得多快份汗？
加快事務(wù)返回速度的一個(gè)方法是使用異步API。使用異步API時(shí)蝴簇，客戶端發(fā)送完更新后裸影，不等待確認(rèn)消息就直接返回【客戶端并不知道事務(wù)是否成功了轩猩，必須做好一段時(shí)間后發(fā)現(xiàn)事務(wù)失敗的準(zhǔn)備。
當(dāng)MySQL使用異步客戶端后荡澎，在一個(gè)30節(jié)點(diǎn)的集群上均践，寫操作可以達(dá)到1950萬次/s的響應(yīng)速度，讀操作可以達(dá)到7167萬次/s的響應(yīng)速度摩幔。
CAP的演進(jìn)
CAP理論推出已經(jīng)有十幾年彤委，其中的很多規(guī)則已經(jīng)發(fā)生了變化，CAP的作者Eric Brewer說道(2012年3月)：
「CAP提出后的十多年間或衡，幾被濫用焦影，設(shè)計(jì)師和研究者發(fā)展了很多新穎獨(dú)特的分布式系統(tǒng)。這些系統(tǒng)很多都可歸入NoSQL封断，NoSQL被認(rèn)為站在傳統(tǒng)數(shù)據(jù)庫的對立面...CAP中三選二的公式其實(shí)是一個(gè)誤導(dǎo)斯辰，它將三者的關(guān)系過于簡單化了。現(xiàn)在這個(gè)觀點(diǎn)應(yīng)該予以矯正坡疼。CAP事實(shí)上只禁止很微小的一部分設(shè)計(jì)空間彬呻，即完美的可用性和一致性在分區(qū)存在的情況下是不可能的，除此之外，別無其他...分區(qū)現(xiàn)象其實(shí)很罕見闸氮，因此CAP的C剪况、A在大部分時(shí)間可以完美實(shí)現(xiàn)。當(dāng)分區(qū)出現(xiàn)時(shí)蒲跨，需要策略檢測到分區(qū)译断，并保證一切井然有序。這個(gè)策略對分區(qū)的處理實(shí)際上分為三個(gè)步驟：1) 檢測分區(qū)或悲；2) 進(jìn)入分區(qū)模式镐作，禁用部分操作；3) 分區(qū)結(jié)束后隆箩，開始恢復(fù)進(jìn)程该贾，恢復(fù)一致性，處理分區(qū)期間的錯(cuò)誤...」
co-location(協(xié)同定位)
我們該如何擴(kuò)展數(shù)據(jù)庫規(guī)模捌臊？
分布式事務(wù)代價(jià)：
- 延時(shí)杨蛋，而不是吞吐量，是一個(gè)很大的問題
- 受到同一數(shù)據(jù)中心理澎、數(shù)據(jù)中心間的物理?xiàng)l件的約束(機(jī)架連線逞力、距離等)
強(qiáng)一致性的代價(jià)如下：
- Spanner：3數(shù)據(jù)中心，4K寫糠爬，大約14ms
- Gaios：4K寫寇荧，小于10ms，其中超過9ms是磁盤日志耗時(shí)
- Spinnaker：寫操作比Cassandra選舉人機(jī)制慢5-10%
可以看到执隧，實(shí)現(xiàn)分布式事務(wù)和強(qiáng)一致性都需要付出一定的代價(jià)揩抡。Spanner就是一個(gè)很明顯的例子。
在以太網(wǎng)中镀琉，可以通過廣播實(shí)現(xiàn)數(shù)據(jù)中心內(nèi)或鄰近數(shù)據(jù)中心間的強(qiáng)一致副本峦嗤。Paxos的研究系統(tǒng)Spinnaker的寫性能只比Cassandra略差，但是前者是強(qiáng)一致的屋摔，后者是最終一致烁设。Birman結(jié)合了向量鐘和Paxos也是向這個(gè)方向努力。這些研究表明钓试，只要操作的時(shí)間大于Paxos延時(shí)(即平均SQL查詢時(shí)間在10ms~15ms)装黑，那么Paxos適合用于保證強(qiáng)一致性。
co-location是必須的
從已有的Paxos實(shí)現(xiàn)看弓熏，一個(gè)較小的Paxos的平均延時(shí)大約在1ms恋谭。但是他們?nèi)绻谶\(yùn)行時(shí)需要要維護(hù)狀態(tài)，延時(shí)會(huì)增加很多硝烂。即使使用fast Paxos箕别，連ROWA(讀一寫全部)在數(shù)據(jù)量很大時(shí)都會(huì)成為擴(kuò)展瓶頸铜幽。
因此滞谢，數(shù)據(jù)需要分區(qū)串稀。一旦數(shù)據(jù)分區(qū)，我們又回到分布式事務(wù)的老問題狮杨。我們必須仔細(xì)考慮數(shù)據(jù)的分布式協(xié)同母截，以最小化分布式事務(wù)成本。
靜態(tài)co-location：實(shí)體組(entity group)
Megastore中實(shí)現(xiàn)co-location的方法是使用明確的模式信息橄教。和Spanner一樣清寇，Megastore讓用戶定義表/實(shí)體的具名、類型化的列护蝶。一組列形成主鍵华烟。實(shí)體間形成層次關(guān)系，并使得它們在物理存儲(chǔ)上保存到一起持灰。這對于email賬號盔夜、博客這類的業(yè)務(wù)是一個(gè)非常好的方法。
由于同一實(shí)體組的數(shù)據(jù)通常一起被查詢堤魁，實(shí)體組是數(shù)據(jù)分區(qū)的合適粒度喂链。實(shí)體組的數(shù)據(jù)是按照鍵值排序好的，這使得分區(qū)分裂操作和合并操作都相當(dāng)廉價(jià)妥泉。
靜態(tài)co-location：樹形模式(tree schema)
一個(gè)標(biāo)準(zhǔn)的樹形模式中椭微，外鍵關(guān)聯(lián)的數(shù)據(jù)應(yīng)該位于同一個(gè)分區(qū)中。樹形模式存在一個(gè)主表盲链，其它的次表包含一個(gè)外鍵指向主表的主鍵蝇率。整個(gè)樹的深度沒有限制。
表之間的關(guān)系通過全局查找表來維護(hù)刽沾。全局查找表的數(shù)據(jù)很少發(fā)生變化瓢剿，副本操作代價(jià)很低。
主表中所有屬于同一主鍵的行被稱之為一個(gè)行組(row group)悠轩。一個(gè)分區(qū)可存儲(chǔ)一個(gè)或多個(gè)行組间狂。
靜態(tài)co-location：鍵值表組(keyed table group)
鍵值表組是將任意表co-locate到一起的通用方法。該方法中火架，同一個(gè)分區(qū)的表共享相同的分區(qū)鍵(partition key)鉴象。分區(qū)鍵是表的某一列，并不一定是主鍵或外鍵何鸡。鍵值表組中同樣有行組的概念纺弊，其含義與樹形模式相同。
該模型被高并發(fā)分布式的云SQL所使用骡男，例如Microsoft Azure淆游。
靜態(tài)co-location：全副本節(jié)點(diǎn)(full replication node)
如果數(shù)據(jù)的規(guī)模不過分大，co-location的粒度可以更粗一些，為此犹菱，引入全副本節(jié)點(diǎn)拾稳。全副本節(jié)點(diǎn)將從許多數(shù)據(jù)分區(qū)復(fù)制數(shù)據(jù)，組合成一個(gè)完整的數(shù)據(jù)副本腊脱。需要跨分區(qū)執(zhí)行的查詢能夠高效地運(yùn)行在全副本節(jié)點(diǎn)上访得。在某種意義上，全副本節(jié)點(diǎn)類似于物化視圖陕凹。
在這種方式中悍抑，數(shù)據(jù)分片負(fù)責(zé)處理OLTP客戶端，全副本節(jié)點(diǎn)用于加速OLAP/join查詢杜耙。
動(dòng)態(tài)co-location：訪問驅(qū)動(dòng)(access driven)
Curino等人提出了一個(gè)學(xué)術(shù)模型搜骡，該模型將應(yīng)用訪問建模為一個(gè)圖。圖進(jìn)行分區(qū)佑女，通過將頻繁訪問的行復(fù)制多份來加速讀性能记靡，同時(shí)保證更新操作所需要的分布式事務(wù)數(shù)量盡可能地少。
這種方法能夠達(dá)到很好的分區(qū)性能珊豹，但是客戶端路由變得很復(fù)雜簸呈。客戶端和路由服務(wù)器很難通過一個(gè)簡單的查找函數(shù)來找到一個(gè)包含指定分區(qū)的節(jié)點(diǎn)店茶。許多改進(jìn)路由的方法被提出蜕便，但是沒有一個(gè)方案簡潔明了。
動(dòng)態(tài)co-location：應(yīng)用驅(qū)動(dòng)(applicatopn driven)
考慮一個(gè)游戲場景贩幻。玩家有很多游戲可選轿腺，但是通常，一旦選定了一個(gè)游戲丛楚，就會(huì)一直玩數(shù)個(gè)小時(shí)族壳。在玩的期間，玩家數(shù)據(jù)和游戲數(shù)據(jù)應(yīng)該被co-locate到一個(gè)節(jié)點(diǎn)上趣些。按照應(yīng)用程序要求仿荆，為需要的數(shù)據(jù)創(chuàng)建組，只在組內(nèi)保證數(shù)據(jù)操作的一致性坏平。當(dāng)游戲結(jié)束時(shí)拢操，組也跟著被釋放。提前切分?jǐn)?shù)據(jù)舶替，在該模式下并沒有必要令境。
擴(kuò)展閱讀
「In Search of an Understandable Consensus Algorithm」論文
「Unbundling Transaction Services in the Cloud」論文
「MoSQL: an elastic storage engine for MySQL」論文
NuoDB：分布式關(guān)系型數(shù)據(jù)庫
MySQL擴(kuò)展示意圖
分片
可用性
Co-location
用戶視圖
