本博客在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ù)庫(kù)擴(kuò)展之道(1): 傳統(tǒng)關(guān)系型數(shù)據(jù)庫(kù)
前言
今天的數(shù)據(jù)庫(kù)世界讓人倍感迷惑花吟〗掌纾回想十年前進(jìn)行Web開發(fā)，可選擇的數(shù)據(jù)庫(kù)還極為有限衅澈。然而現(xiàn)在键菱，除了傳統(tǒng)的數(shù)據(jù)庫(kù)外，有150+的NoSQL數(shù)據(jù)庫(kù)供君選擇今布。這期間究竟發(fā)生了什么翻天覆地的變化纱耻，使得單節(jié)點(diǎn)數(shù)據(jù)庫(kù)逐步演變?yōu)閿?shù)百萬節(jié)點(diǎn)的全球數(shù)據(jù)庫(kù)？為了解答這個(gè)疑惑险耀，本文將引導(dǎo)讀者回顧這些年數(shù)據(jù)庫(kù)的那些事兒。
在正文之前玖喘，讀者應(yīng)當(dāng)明白甩牺，與傳統(tǒng)開發(fā)相比，在海量數(shù)據(jù)庫(kù)系統(tǒng)上進(jìn)行應(yīng)用開發(fā)存在一定區(qū)別累奈，而開發(fā)海量數(shù)據(jù)庫(kù)本身則有天壤之別贬派。
數(shù)據(jù)庫(kù)的出現(xiàn)
1960年代——黑暗歲月
有誰曾經(jīng)接觸過大型機(jī)的日常數(shù)據(jù)交換？2000年以后呢澎媒？
這個(gè)時(shí)候的應(yīng)用數(shù)據(jù)被存儲(chǔ)在磁帶上搞乏，數(shù)據(jù)庫(kù)還未被發(fā)明出來。公司在生產(chǎn)環(huán)境使用的每一個(gè)應(yīng)用都有自己的數(shù)據(jù)存儲(chǔ)方式戒努。開發(fā)者使用十六進(jìn)制編譯器來解讀數(shù)據(jù)请敦，制作報(bào)告時(shí)需要花費(fèi)了很多額外的時(shí)間從多個(gè)應(yīng)用抽取數(shù)據(jù)。從這個(gè)安全問題頻出的年代看储玫，這是怎樣天真美好的歲月侍筛，應(yīng)用安全到只有知悉所有實(shí)現(xiàn)細(xì)節(jié)才能保持運(yùn)行的地步，就算你拿到數(shù)據(jù)也白搭撒穷。(Zz..囧)
1970年代——神跡初顯
這個(gè)時(shí)代的數(shù)據(jù)存儲(chǔ)的目標(biāo)包括：
- 數(shù)據(jù)的內(nèi)在視圖(存儲(chǔ)細(xì)節(jié))和外在視圖(外在表現(xiàn))分離
- 中心式存儲(chǔ)
- 數(shù)據(jù)一致性匣椰，高效的數(shù)據(jù)訪問
- 多用戶支持，訪問控制
(關(guān)系型)數(shù)據(jù)庫(kù)終于被發(fā)明了出來端礼，成為解決一個(gè)公司內(nèi)部不同應(yīng)用的數(shù)據(jù)共享問題的有效手段禽笑。
一個(gè)數(shù)據(jù)庫(kù)系統(tǒng)必須確保數(shù)據(jù)一致性入录，并提供諸如訪問控制之類的手段保證多應(yīng)用、多用戶環(huán)境下的數(shù)據(jù)安全佳镜。當(dāng)然僚稿，數(shù)據(jù)的存儲(chǔ)效率也極為關(guān)鍵。
使用數(shù)據(jù)庫(kù)帶來的一個(gè)好處就是邀杏，用戶看到的數(shù)據(jù)外在視圖和內(nèi)在視圖是完全隔離的贫奠。用戶根本不需要關(guān)心數(shù)據(jù)的存儲(chǔ)細(xì)節(jié)。不管內(nèi)部的存儲(chǔ)方式如何望蜡，數(shù)據(jù)庫(kù)使用一致的SQL語言提供數(shù)據(jù)唤崭。
基本數(shù)據(jù)概念
什么是數(shù)據(jù)？
我們知道數(shù)據(jù)一致性是一個(gè)數(shù)據(jù)庫(kù)系統(tǒng)的核心問題脖律，然而谢肾，究竟什么是數(shù)據(jù)？
顯然小泉，所有的數(shù)據(jù)都會(huì)有一個(gè)類型和一個(gè)值域芦疏。例如，一個(gè)字符串是一組字母的序列微姊，一個(gè)數(shù)卻只包含數(shù)字酸茴，它們的類型就是不一樣的。
操作符(operator)與數(shù)據(jù)結(jié)構(gòu)(data structure)
數(shù)據(jù)可以分為標(biāo)量(scalar)數(shù)據(jù)類型和非標(biāo)量(non-scalar)數(shù)據(jù)類型兩類兢交。一個(gè)標(biāo)量數(shù)據(jù)類型只保存唯一的數(shù)據(jù)項(xiàng)薪捍，字符串、整數(shù)就是典型的標(biāo)量數(shù)據(jù)類型配喳。與之相反酪穿，一個(gè)非標(biāo)量數(shù)據(jù)類型是包含多個(gè)數(shù)據(jù)項(xiàng)的類型，類就是典型的非標(biāo)量數(shù)據(jù)類型晴裹。
操作符用于操作數(shù)據(jù)類型被济，每一個(gè)數(shù)據(jù)類型都有一組適用的操作符集合。例如涧团，類的構(gòu)造器(constructor)是用于初始化類成員的操作符只磷。
數(shù)據(jù)結(jié)構(gòu)規(guī)定了數(shù)據(jù)的組織、存儲(chǔ)方式泌绣。一些數(shù)據(jù)庫(kù)系統(tǒng)允許自定義數(shù)據(jù)結(jié)構(gòu)喳瓣。一個(gè)對(duì)象(object)由一個(gè)數(shù)據(jù)結(jié)構(gòu)和定義在其上的一組操作符組成，而POD(plain old data)數(shù)據(jù)結(jié)構(gòu)就只包含數(shù)據(jù)結(jié)構(gòu)赞别。
狀態(tài)(state)
在一個(gè)程序中畏陕，數(shù)據(jù)是動(dòng)態(tài)的。數(shù)據(jù)的狀態(tài)隨時(shí)間發(fā)生變化仿滔，修改操作會(huì)導(dǎo)致數(shù)據(jù)狀態(tài)變化惠毁，通常這些狀態(tài)遵循一定的規(guī)則犹芹。
數(shù)據(jù)庫(kù)的數(shù)據(jù)模型
數(shù)據(jù)庫(kù)的一個(gè)數(shù)據(jù)模型定義了數(shù)據(jù)庫(kù)的數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)方式鞠绰，和全局操作符腰埂。數(shù)據(jù)庫(kù)會(huì)長(zhǎng)期運(yùn)行，全局操作符實(shí)際上規(guī)定了可能發(fā)生的狀態(tài)變化蜈膨。
數(shù)據(jù)庫(kù)內(nèi)部使用數(shù)據(jù)庫(kù)模式(schema)描述一個(gè)特定數(shù)據(jù)模型屿笼。很少有數(shù)據(jù)庫(kù)以無模式的方式存儲(chǔ)數(shù)據(jù)，當(dāng)然翁巍，很多的NoSQL系統(tǒng)的模式非常靈活驴一。
常見數(shù)據(jù)模型分為四種：
- 關(guān)系模型(Relational data model)
- 文檔模型(Document model)
- 鍵值模型(Key-Value model)
- 寬列模型(Wide columnar model)
后三種都屬于NoSQL的范疇。接下來將簡(jiǎn)要介紹這四種模型灶壶。
關(guān)系型數(shù)據(jù)庫(kù)
盡管關(guān)系模型的缺點(diǎn)被一些NoSQL所改進(jìn)肝断，但是除了這些缺點(diǎn)，我們不應(yīng)該忘記關(guān)系模型的優(yōu)點(diǎn)驰凛。至少到現(xiàn)在胸懈，關(guān)系模型仍然占有統(tǒng)治地位。
NoSQL的革新本質(zhì)在于數(shù)據(jù)模型本身恰响，而其它的改進(jìn)多流于表面趣钱，完全可以被關(guān)系型數(shù)據(jù)庫(kù)借鑒。例如胚宦，關(guān)系型數(shù)據(jù)庫(kù)也可以實(shí)現(xiàn)HTTP接口首有；關(guān)系型數(shù)據(jù)庫(kù)也可以提供更低層次的訪問接口來繞開SQL；關(guān)系型數(shù)據(jù)庫(kù)也可以簡(jiǎn)化管理體系间唉；等等。
模式設(shè)計(jì)
模式設(shè)計(jì)是關(guān)系型數(shù)據(jù)庫(kù)應(yīng)用開發(fā)的第一步利术，包含3個(gè)步驟：
- 提煉出需要存儲(chǔ)的信息呈野。
- 創(chuàng)建實(shí)體-關(guān)系(E-R)模型：
- 實(shí)體：主題、事情印叁、物體
- 屬性：對(duì)實(shí)體的描述被冒、信息項(xiàng)、規(guī)則
- 候選鍵：能夠唯一標(biāo)識(shí)一個(gè)實(shí)體的屬性集合
- 關(guān)系：實(shí)體間的關(guān)聯(lián)轮蜕，1:1昨悼、1:n、n:m
- 將E-R模型轉(zhuǎn)化為物理數(shù)據(jù)模型：
- 網(wǎng)絡(luò)模型跃洛、關(guān)系模型率触、分層模型
- 關(guān)系模型：表、屬性汇竭、主鍵
- 關(guān)系模型：應(yīng)用數(shù)據(jù)庫(kù)規(guī)范化法則
數(shù)據(jù)庫(kù)規(guī)范化(database normalization)
數(shù)據(jù)庫(kù)規(guī)范化的目的是降低數(shù)據(jù)表的冗余和依賴程度葱蝗。數(shù)據(jù)庫(kù)規(guī)范化有很多范式穴张，其中第一范式(first normal form, 1NF)規(guī)定：
- 一個(gè)關(guān)系的所有屬性都是不可再分的原子數(shù)據(jù)項(xiàng)
- 每一個(gè)屬性只包含唯一的值
該范式禁止創(chuàng)建嵌套的表結(jié)構(gòu)，例如下圖中两曼，在一張博客發(fā)表表內(nèi)嵌套一個(gè)博客評(píng)論列表皂甘。嵌套的表結(jié)構(gòu)在NoSQL中比較常見。
為了不破壞1NF悼凑，同時(shí)滿足一些必要的嵌套需求偿枕，SQL:99和SQL:2003引入了非原子數(shù)據(jù)結(jié)構(gòu)。SQL:99增加了ROW和ARRAY户辫，SQL:2003增加了MULTISET渐夸。遺憾的是，很多關(guān)系型數(shù)據(jù)庫(kù)都沒有實(shí)現(xiàn)這些數(shù)據(jù)類型寸莫。進(jìn)一步說捺萌，如果這些數(shù)據(jù)類型得到了實(shí)現(xiàn)，關(guān)系型數(shù)據(jù)庫(kù)連接(join)操作將會(huì)變得非常高效膘茎，鍵值數(shù)據(jù)庫(kù)和文檔數(shù)據(jù)庫(kù)在這方面的優(yōu)勢(shì)也就不那么明顯了桃纯。
查詢
關(guān)系型數(shù)據(jù)庫(kù)的查詢通過SQL語言進(jìn)行，其理論基礎(chǔ)是關(guān)系代數(shù)披坏。
ACID事務(wù)
關(guān)系型數(shù)據(jù)庫(kù)的事務(wù)滿足ACID：
- 原子性(atomicity)
- 一個(gè)事務(wù)的操作要么全做态坦，要么全不做
- 在各種失效情況下也予以保證：掉電、崩潰...
- 一致性(consistency)
- 事務(wù)只能導(dǎo)致數(shù)據(jù)庫(kù)從一個(gè)有效狀態(tài)轉(zhuǎn)變到另外一個(gè)有效狀態(tài)
- 已定義的規(guī)則不會(huì)被違反：約束棒拂、觸發(fā)器...
- 隔離性(isolation)
- 并行執(zhí)行的事務(wù)與串行執(zhí)行的效果等效伞梯，不會(huì)互相干擾
- 持久性(durability)
- 一旦事務(wù)提交，就不可撤銷
- 在各種失效情況下也予以保證：掉電帚屉、崩潰...
ACID反映了數(shù)據(jù)庫(kù)管理系統(tǒng)(database management system谜诫，DBMS)設(shè)計(jì)和開發(fā)的目標(biāo)。DBMS不僅僅保證數(shù)據(jù)被正確組織(數(shù)據(jù)模型攻旦，模式)喻旷，保證數(shù)據(jù)被輕松訪問(關(guān)系代數(shù)、SQL)牢屋，也需要保證多用戶環(huán)境下的數(shù)據(jù)安全且预。
在RDMS事務(wù)中，用戶的工作要么全做烙无，要么都不做锋谐，不存在中間狀態(tài)。事務(wù)不會(huì)破壞任何已定義的規(guī)則截酷，在完成時(shí)保證數(shù)據(jù)庫(kù)仍然處于一個(gè)已定義的一致狀態(tài)涮拗。事務(wù)在被提交前，不會(huì)被其它并發(fā)的事務(wù)妨礙。事務(wù)一旦提交多搀，其結(jié)果永遠(yuǎn)不會(huì)丟失歧蕉。
并發(fā)控制
假設(shè)兩個(gè)事務(wù)同時(shí)想修改同一個(gè)數(shù)據(jù)項(xiàng)，需要保證它們的修改不會(huì)相互沖突康铭。這個(gè)工作由并發(fā)控制(concurrency control)算法來完成惯退。
并發(fā)控制算法的分類如下圖所示：
這張圖是從原PPT翻譯得到的，對(duì)該分類有疑問的請(qǐng)參考其它文獻(xiàn)从藤。
并發(fā)控制算法可以分為悲觀算法和樂觀算法兩大類催跪。悲觀算法在事務(wù)開始前就檢查沖突數(shù)據(jù)，提前鎖定夷野，使事務(wù)訪問順序化懊蒸。樂觀算法將沖突檢查推遲到最后進(jìn)行，如果沖突悯搔，則回滾事務(wù)骑丸。
隔離級(jí)別
ANSI/ISO SQL定義了若干隔離級(jí)別，隔離級(jí)別會(huì)影響并發(fā)控制算法的效率：
- 可序列化(serializable)
- 最高級(jí)別的隔離妒貌，在事務(wù)期間對(duì)沖突數(shù)據(jù)的讀寫保持范圍鎖(range lock)通危，即沖突事務(wù)順序進(jìn)行
- 可重復(fù)讀(repeatable read)
- 沒有范圍鎖，可能存在「幻影讀(phantom read)」現(xiàn)象
- 授權(quán)讀(read committed)
- 可能發(fā)生「不可重復(fù)讀(non-repeatable read)」
- 未授權(quán)讀(read uncommitted)
- 允許「臟讀(dirty read)」
幻象讀：一個(gè)事務(wù)中灌曙，兩個(gè)完全相同的查詢語句執(zhí)行得到不同的「結(jié)果集」菊碟。在下圖的例子中，事務(wù)1的第2次查詢語句讀到了事務(wù)2新提交的數(shù)據(jù)在刺。
幻象讀
不可重復(fù)讀：在一次事務(wù)中逆害，「一行數(shù)據(jù)」獲取兩遍得到不同的結(jié)果。在下圖的例子中蚣驼，事務(wù)2提交成功魄幕，因此它對(duì)id為1的行的修改就對(duì)其它事務(wù)可見了，與事務(wù)1之前已經(jīng)從這行讀到了另外一個(gè)「age」的值不同颖杏。
不可重復(fù)讀
臟讀：當(dāng)一個(gè)事務(wù)允許讀取另外一個(gè)事務(wù)修改但未提交的數(shù)據(jù)時(shí)纯陨，就可能發(fā)生臟讀。在下圖的例子中输玷，事務(wù)2修改了一行队丝，但是沒有提交靡馁，事務(wù)1讀了這個(gè)沒有提交的數(shù)據(jù)∮簦現(xiàn)在如果事務(wù)2回滾了剛才的修改或者做了另外的修改的話，事務(wù)1中查到的數(shù)據(jù)就是不正確的了
臟讀
物理層面
關(guān)系型數(shù)據(jù)庫(kù)將記錄存儲(chǔ)在「頁(yè)(page)」中臭墨，每一個(gè)頁(yè)是4~32KB大小的連續(xù)內(nèi)存區(qū)域赔嚎。一個(gè)頁(yè)可以包含一個(gè)或多個(gè)記錄。如果單個(gè)頁(yè)不能存儲(chǔ)下一個(gè)記錄的全部數(shù)據(jù)，那么將使用額外的溢出頁(yè)(overflow page)尤误。為了優(yōu)化訪問效率侠畔，關(guān)系型數(shù)據(jù)庫(kù)使用B-tree或其衍生數(shù)據(jù)結(jié)構(gòu)將頁(yè)按序存儲(chǔ)在磁盤上。如果數(shù)據(jù)的實(shí)際存儲(chǔ)順序與一個(gè)索引的順序一致损晤，那么這個(gè)索引是一個(gè)聚集索引(clustered index)软棺。例如，InnoDB就使用聚集索引按照主鍵來組織數(shù)據(jù)表尤勋。聚集索引有助于獲得更高的順序搜索性能喘落。
連接(join)
考慮一個(gè)數(shù)據(jù)表連接操作r?s(r、s分別是兩個(gè)數(shù)據(jù)表)最冰，常見的執(zhí)行策略包括：
- 嵌套循環(huán)(nested loop)
- 通過兩層嵌套循環(huán)完成瘦棋，首先掃描表r，每讀到一條記錄暖哨，就去掃描表s以查找符合要求的記錄
- 算法復(fù)雜度O(nr*ns)赌朋，其中nr和ns分別是表r和表s中的記錄數(shù)量
- 對(duì)索引和連接條件無任何要求
- 塊嵌套循環(huán)(block nested loop)
- 嵌套循環(huán)的一個(gè)變種，以塊為單位而不是以記錄為單位處理關(guān)系
- 相比嵌套循環(huán)篇裁，能夠減少?gòu)挠脖P傳輸數(shù)據(jù)的次數(shù)沛慢，因此，效率有所改進(jìn)
- 索引嵌套循環(huán)(indexed nested loop)
- 如果內(nèi)層嵌套的被連接表的連接屬性上有索引茴恰，則可以利用索引來優(yōu)化符合要求記錄的查找
- 歸并連接(merge join颠焦，又稱排序-歸并-連接，sort-merge join)
- 對(duì)連接的兩個(gè)表按公共屬性排序往枣，利用歸并排序算法尋找公共屬性相同的符合條件的記錄
- 可用于計(jì)算自然連接和等值連接
- 散列連接(hash join)
- 將連接的兩個(gè)表按照公共屬性使用相同的hash函數(shù)將記錄映射到同一空間伐庭，再對(duì)相同hash值的記錄做匹配
- 實(shí)際的實(shí)現(xiàn)只對(duì)一個(gè)較小的表建hash查找表，另外一個(gè)表直接匹配記錄
- 可用于計(jì)算自然連接和等值連接
原PPT只提及了nested loop和hash join分冈，這里根據(jù)其它材料進(jìn)行了補(bǔ)充圾另。
關(guān)系型數(shù)據(jù)庫(kù)架構(gòu)擴(kuò)展
盡可能地緩存
緩存是提高數(shù)據(jù)庫(kù)性能的一個(gè)有效手段。
數(shù)據(jù)庫(kù)保存的數(shù)據(jù)有狀態(tài)的(stateful)雕沉，且為硬狀態(tài)(hard-state)集乔，保證數(shù)據(jù)一致性(consistent)；緩存保存的數(shù)據(jù)無狀態(tài)(stateless)坡椒，且為軟狀態(tài)(soft-state)扰路，不保證數(shù)據(jù)一致性(inconsisteng)。
一個(gè)典型的緩存系統(tǒng)如下圖所示：
軟狀態(tài)維持一段有限的時(shí)間倔叼，在過期前需要重新刷新汗唱，否則自動(dòng)失效。軟狀態(tài)可能比數(shù)據(jù)庫(kù)中的狀態(tài)滯后丈攒。相反哩罪，硬狀態(tài)一直存在授霸，且一定正確。
緩存的無狀態(tài)特征允許緩存系統(tǒng)簡(jiǎn)單地通過增加/減少資源來調(diào)整規(guī)模际插。
接下來的描述都是以MySQL為例展開的碘耳。
MySQL內(nèi)置緩存
除了外部的緩存系統(tǒng)，MySQL本身也進(jìn)行了兩項(xiàng)重要的改進(jìn)：
- 內(nèi)置了查詢緩存框弛，該緩存的數(shù)據(jù)狀態(tài)與數(shù)據(jù)庫(kù)是一致的辛辨。
- 通過InnoDB提供了Memcache協(xié)議的底層記錄訪問接口，訪問速度比外部的Memcache更快瑟枫，簡(jiǎn)化了架構(gòu)愉阎。
MySQL主從
MySQL對(duì)可擴(kuò)展性的答案是主從復(fù)制模式。在該模式中力奋，所有的客戶端寫請(qǐng)求由唯一的master進(jìn)行處理榜旦。master將操作記錄到二進(jìn)制日志中，該日志被異步發(fā)送給slave們景殷，slave們重放操作溅呢，完成數(shù)據(jù)的更新。slave可以處理客戶端的讀操作猿挚，前提是咐旧，應(yīng)用可以容忍極短時(shí)間的數(shù)據(jù)滯后。該模式應(yīng)該和緩存結(jié)合使用绩蜻。
在一個(gè)讀操作為主的環(huán)境(如Web應(yīng)用)中铣墨，該模式具備極佳的橫向擴(kuò)展能力，增加新slave的代價(jià)可以忽略不計(jì)办绝。
在一個(gè)寫操作為主的環(huán)境中伊约，該模式很難橫向擴(kuò)展：
- 只有一個(gè)master處理所有的寫操作，很容易單節(jié)點(diǎn)故障
- 很難讀寫分離孕蝉，即使使用PECL/mysqlnd_ms效果也不是很好
- MySQL要努力啊...
更多MySQL演示資料參見slideshare屡律。
架構(gòu)擴(kuò)展的目標(biāo)
每一個(gè)MySQL工程師都應(yīng)該知道架構(gòu)擴(kuò)展的目標(biāo)有這些：
- 可用性(availability)
- 節(jié)點(diǎn)失效不會(huì)對(duì)集群造成影響
- 可伸縮性
- 地理分布
- 能夠根據(jù)用戶和數(shù)據(jù)的規(guī)模伸縮
- 均衡讀/寫負(fù)載
- 分區(qū)透明
- 一切內(nèi)部細(xì)節(jié)對(duì)客戶端都是透明的
MySQL架構(gòu)擴(kuò)展方案分類
根據(jù)欲達(dá)到的目標(biāo)，可對(duì)現(xiàn)有的MySQL解決方案進(jìn)行歸類降淮。在這里超埋，按照「事務(wù)執(zhí)行的位置」和「節(jié)點(diǎn)同步發(fā)生的時(shí)間」將解決方案分為四類：
未完待續(xù)...
下一部分將介紹NoSQL理論和Amazon Dynamo，參見：
