分布式數(shù)據(jù)庫總結(jié)

1、分布式數(shù)據(jù)庫總結(jié)簡介第一篇：分布式數(shù)據(jù)庫總結(jié)分布式數(shù)據(jù)庫系統(tǒng)及其應(yīng)用復(fù)習(xí)大綱 第一章分布式數(shù)據(jù)庫系統(tǒng)概述 1、理解分布式數(shù)據(jù)庫系統(tǒng)的特點(diǎn)分布式數(shù)據(jù)庫系統(tǒng)的定義： 分布式數(shù)據(jù)庫系統(tǒng)，通俗地說，是物理上分散而邏輯上集中的數(shù)據(jù)庫系統(tǒng)。分布式數(shù)據(jù)庫系統(tǒng)使用計(jì)算機(jī)網(wǎng)絡(luò)將地理位置分散而管理和控制又需要不同程度集中的多個(gè)邏輯單位（通常是集中是數(shù)據(jù)庫系統(tǒng)）連接起來，共同組成一個(gè)統(tǒng)一的數(shù)據(jù)庫系統(tǒng)。 分布式數(shù)據(jù)庫系統(tǒng)的特點(diǎn)：物理分布性：數(shù)據(jù)不是存放在一個(gè)站點(diǎn)上邏輯整體性：是與分散式數(shù)據(jù)庫系統(tǒng)的區(qū)別站點(diǎn)自治性：是與多處理機(jī)系統(tǒng)的區(qū)別數(shù)據(jù)分布透明性集中與自治相結(jié)合的控制機(jī)制存在適當(dāng)?shù)臄?shù)據(jù)冗余度事務(wù)管理的分布性 2、能

2、夠按照不同標(biāo)準(zhǔn)描述分布式數(shù)據(jù)庫系統(tǒng)的分類 按局部數(shù)據(jù)庫管理系統(tǒng)的數(shù)據(jù)模型分類：同構(gòu)性（homogeneous）（分為同構(gòu)同質(zhì)型和 同構(gòu)異質(zhì)型）ddbs和異構(gòu)性(heterogeneous)ddbs 按分布式數(shù)據(jù)庫系統(tǒng)的全局控制系統(tǒng)類型分類：全局控制集中型ddbs，全局控制分散型ddbs，全局控制可變型ddbs。 3、理解分布式數(shù)據(jù)庫中數(shù)據(jù)的獨(dú)立性和分布透明性 所謂數(shù)據(jù)獨(dú)立性是指用戶或用戶程序使用分布式數(shù)據(jù)庫如同使用集中式數(shù)據(jù)庫那樣，不必關(guān)心全局?jǐn)?shù)據(jù)的分布情況，包括全局?jǐn)?shù)據(jù)的邏輯分片情況、邏輯片段站點(diǎn)位置的分配情況，以及各站點(diǎn)上數(shù)據(jù)庫的數(shù)據(jù)模型等。也就是說，全局?jǐn)?shù)據(jù)的邏輯分片、片段的物理位置分配

3、，各站點(diǎn)數(shù)據(jù)庫的數(shù)據(jù)模型等情況對用戶和用戶程序透明。所以，在分布式數(shù)據(jù)庫中分布獨(dú)立性也稱為分布透明性。 分布透明性包括三個(gè)層次：分片透明性（完全分布透明性）：映像2 位置透明性（中級(jí)分布透明性）：映像3 局部數(shù)據(jù)模型透明性（低級(jí)分布透明性）：映像4 無分布透明性：異構(gòu)數(shù)據(jù) 第二章分布式數(shù)據(jù)庫系統(tǒng)設(shè)計(jì) 1、理解分布式數(shù)據(jù)庫的設(shè)計(jì)目標(biāo) 分布式數(shù)據(jù)庫設(shè)計(jì)的目標(biāo)1分布式數(shù)據(jù)庫的本地性或近地性2控制數(shù)據(jù)的適當(dāng)冗余3工作負(fù)荷分布4存儲(chǔ)的能力和費(fèi)用2、理解水平分片的定義、分類和應(yīng)用水平分片是對全局關(guān)系執(zhí)行“選擇操作”，把具有相同性質(zhì)的元組進(jìn)行分組，構(gòu)成若干個(gè)不相交的子集。水平分片的方法可歸為初級(jí)分片和導(dǎo)出分

4、片兩類。 初級(jí)分片：以關(guān)系自身的屬性性質(zhì)為基礎(chǔ)，執(zhí)行“選擇”操作，將關(guān)系分為若干個(gè)不相交的片段。例子2.1 s（s#，sname, age, sex） define fragment s1 as select * from where sex=m define fragment s2 as select * from where sex=f 導(dǎo)出分片：全局關(guān)系的導(dǎo)出分片不是以其自身的屬性性質(zhì)為基礎(chǔ)，而是從另一個(gè)關(guān)系的屬性性質(zhì)或水平片段推導(dǎo)出來的。采用導(dǎo)出分片可片可使片段與片段之間的“連接”變得更容易。 例2.3 設(shè)全局關(guān)系sc（，grade），s（s#，sname, age, sex）若要將劃

5、分 為男生的各門課成績和女生的各門課成績，這就不可能從sc本身的屬性性質(zhì)來執(zhí)行選擇，必須從關(guān)系s的屬性性質(zhì)或水平片段來導(dǎo)出。 define fragment sc1 as select sc.s#,c#,grade from sc,s where sc.s#=s.s# and sex=m define fragment sc2 as select sc.s#,c#,grade from sc,s where sc.s#=s.s# and sex=f 如果s已經(jīng)進(jìn)行水平分片，分為sf和sm，分別為男生全體和女生全體，則上述的片段定義可以基于片段sf和導(dǎo)出：define fragment sc1

6、as select * from sc where s# in(select sf.s# from sf) define fragment sc2 as select * from sc where s# in(select sm.s# from sm) 3、理解垂直分片的定義和應(yīng)用 一個(gè)全局關(guān)系的垂直分片是通過“投影”操作把它的屬性分為若干組。確定一個(gè)全局關(guān)系r的垂直分片需要根據(jù)應(yīng)用以“同樣方式”（例如具有相同的使用頻率）訪問的屬性來進(jìn)行分組。 例2.4全局關(guān)系emp（e#，name，sal，tel，magnum，dept），主碼為e#。主要應(yīng)用有：集中在站點(diǎn)3上的管理性應(yīng)用要求查詢雇員的：

7、name，sal，tel；和從其他站點(diǎn)發(fā)出的應(yīng)用要求查詢雇員的：name，dept，magnum。 解：如果使用垂直分片：emp（e#，name，sal，tel）和emp（e#，magnum，dept） 則name屬性只屬于一個(gè)片段，對于上述的應(yīng)用，必須進(jìn)行連接操作和非本地訪問。 如果使用垂直群集：emp（e#，name，sal，tel）和emp（e#，name，magnum，dept） 則對于上述應(yīng)用，不需要執(zhí)行連接操作，且可實(shí)現(xiàn)較好的本地性。 4、能夠描述分片的基本原則 完備性原則：要把所有的數(shù)據(jù)映射到各個(gè)片斷中 可重構(gòu)原則：關(guān)系分片后的各個(gè)片斷可重構(gòu)整個(gè)關(guān)系 不相交原則：關(guān)系分片后的各個(gè)

8、片斷不能重疊 5、掌握數(shù)據(jù)片斷分配的分類和常用方法 分配的簡化模型有：讀代價(jià)、寫代價(jià)、存儲(chǔ)代價(jià)和目標(biāo)函數(shù)。 常用方法：非冗余分配設(shè)計(jì)方法（包含最佳適應(yīng)法和其他方法）和冗余分配的設(shè)計(jì)方法（包含所有得益站點(diǎn)法和附加復(fù)制法） 6、掌握最佳適應(yīng)法和所有得益站點(diǎn)法的基本特點(diǎn) 最佳適應(yīng)法是對每一種分配方式進(jìn)行估算，然后選擇最佳的站點(diǎn)。這種方法不考慮把一個(gè)片段與一個(gè)相關(guān)片段放在同一站點(diǎn)的“相互”影響。 特點(diǎn)：將片斷ri分配到訪問ri次數(shù)最多的那個(gè)站點(diǎn)上bij= kfkj*nki 所有得益站點(diǎn)法：首先確定非復(fù)制為題的解，然后在全部站點(diǎn)中確定一組站點(diǎn)，給這組站點(diǎn)中的每一個(gè)站點(diǎn)分配片斷的一個(gè)副本，這樣做所得到的好

9、處要比為此而付出的費(fèi)用合算。 特點(diǎn)：將片斷ri的副本分配到所有得益站點(diǎn)j上 bij= kfkj*rki -c*k jj fkj*uki 如果bij0，則站點(diǎn)j是得益站點(diǎn)，放置ri的一個(gè)副本 7、能夠描述dataid-d方法設(shè)計(jì)分布式數(shù)據(jù)庫的各個(gè)階段 需求分析，概念設(shè)計(jì)，分布要求分析，全局邏輯設(shè)計(jì)，分布設(shè)計(jì)，局部邏輯設(shè)計(jì)，局部物理設(shè)計(jì)。邏輯設(shè)計(jì)分為全局邏輯設(shè)計(jì)和局部邏輯設(shè)計(jì) 8、能夠根據(jù)給出的條件對關(guān)系進(jìn)行具體分片，給出正確的限定關(guān)系 上邊的例子。 第三章分布式數(shù)據(jù)庫系統(tǒng)中的查詢處理和優(yōu)化1、掌握分布式數(shù)據(jù)庫查詢的分類 局部查詢、遠(yuǎn)程查詢和全局查詢 2、理解關(guān)系代數(shù)運(yùn)算的交換率 È1

10、(2 (r) =2 (1 (r) 條件:1 2 是 選擇操作 時(shí)總成立，1 2 是 投影操作時(shí)要求其屬性集合相等 1 與2 是投影和選擇操作時(shí):a1,an(f(r) =f (a1,an (r) 的條件是 f中的屬性是 a1, . an 的子集。r s = s r r × s = s × r r s = s r r s = s r r s È s r r r 3、掌握直接連接優(yōu)化算法的分類 利用站點(diǎn)依賴信息的算法，分片與復(fù)制算法，站點(diǎn)依賴和數(shù)據(jù)復(fù)制結(jié)合算法，hash劃分算法 4、掌握半連接運(yùn)算 見例子 5、掌握半連接和直接連接查詢優(yōu)化算法的區(qū)別 取決于數(shù)據(jù)傳輸和局部

11、處理的相對費(fèi)用；如果傳輸費(fèi)用是主要的，采用半連接；如果本地費(fèi)用是主要的，采用直接連接, 6、理解hash劃分算法的特點(diǎn) 數(shù)據(jù)傳送量是r；索引方面, 比片段復(fù)制算法更低，每個(gè)站點(diǎn)的連接數(shù)據(jù)量同站點(diǎn)依賴 7、能夠描述基于半連接算法查詢優(yōu)化的基本原理和步驟 基本原理是在傳到另一個(gè)站點(diǎn)做連接前，消除與連接無關(guān)的數(shù)據(jù)，減少做連接操作的數(shù)據(jù)量，從而減小傳輸代價(jià) 步驟：計(jì)算每種半連接方案的代價(jià)，并從中選擇一種最佳方案選擇傳輸代價(jià)最小的站點(diǎn)，計(jì)算采用全連接的方案的代價(jià)比較兩種方案，確定最優(yōu)方案 8、能夠描述基于關(guān)系代數(shù)等價(jià)變換的查詢優(yōu)化算法原理、算法實(shí)現(xiàn)步驟 原理：1查詢問題關(guān)系代數(shù)表達(dá)式2分析得到查詢樹3進(jìn)

12、行全局到片段的變換得到基于片段的查詢樹4利用關(guān)系代數(shù)等價(jià)變換規(guī)則的優(yōu)化算法，盡可能先執(zhí)行選擇和投影操作 算法：1連接和合并盡可能上提（樹根方向）2選擇和投影操作盡可能下移（葉子方向） 實(shí)現(xiàn)步驟：轉(zhuǎn)換一：1查詢問題關(guān)系代數(shù)表達(dá)式。2轉(zhuǎn)換二：關(guān)系代數(shù)表達(dá)式查詢樹。3轉(zhuǎn)換三：全局查詢樹分拆成片段查詢樹。4優(yōu)化：利用關(guān)系代數(shù)等價(jià)變換規(guī)則的優(yōu)化算法，優(yōu)化查詢樹，進(jìn)而優(yōu)化查詢 9、能夠根據(jù)提供的條件完成分片和復(fù)制算法應(yīng)用，通過計(jì)算判斷哪個(gè)關(guān)系保持分片最優(yōu) p88例3-6 考試 第四章分布式數(shù)據(jù)庫中的事務(wù)管理和恢復(fù) 1、掌握事務(wù)的四大特性 原子性（atomicity）,一致性（consistency）,持久

13、性（durability）.隔離性（ isolation）2、能夠描述兩階段提交協(xié)議的工作流程 兩階段提交協(xié)議的基本思想是：將本地原子性提交行為的效果擴(kuò)展到分布式事務(wù), 保證了分布式事務(wù)提交的原子性, 并在不損壞log的情況下, 實(shí)現(xiàn)快速故障恢復(fù), 提高ddb系統(tǒng)的可靠性. 2pc把事務(wù)的提交過程分為兩個(gè)階段：第一階段：表決階段，目的是形成一個(gè)共同的決定 首先，協(xié)調(diào)者給所有參與者發(fā)送“準(zhǔn)備”消息，進(jìn)入等待狀態(tài) 其次，參與者收到“準(zhǔn)備”消息后，檢查是否能夠提交本地事務(wù) 如能，給協(xié)調(diào)者發(fā)送“建議提交”消息,進(jìn)入就緒狀態(tài) 如不能，給協(xié)調(diào)者發(fā)送“建議撤銷”消息，可以單方面撤銷 第三，協(xié)調(diào)者收到所有參與

14、者的消息后，他就做出是否提交事務(wù)的決定， 只要有一個(gè)參與者投了反對票，就決定撤銷整個(gè)事務(wù)，發(fā)送“全局撤銷”消息給所有參與者，進(jìn)入撤銷狀態(tài) 否則，就決定提交整個(gè)事務(wù)，發(fā)送“全局提交”消息給所有參與者，進(jìn)入提交狀態(tài) 第二個(gè)階段：執(zhí)行階段，實(shí)現(xiàn)表決階段的決定，提交或者撤銷 3、掌握事務(wù)故障的分類 分布是數(shù)據(jù)庫的故障 分布是數(shù)據(jù)庫的故障分為站點(diǎn)故障和通信故障。站點(diǎn)故障包括事務(wù)故障、系統(tǒng)故障和介質(zhì)故障。 事務(wù)故障包括計(jì)算溢出。完整性被破壞、操作員干預(yù)、輸入或輸出出錯(cuò)等。 通信故障分為報(bào)文故障和網(wǎng)絡(luò)分割故障。 4、掌握分布式數(shù)據(jù)庫事務(wù)執(zhí)行的控制模型的分類 分為三類：主從模型，三角模型，層次控制模型 5、理

15、解日志文件的特點(diǎn) 日志文件保存到磁盤上。日志 log：記錄所有對db的操作 事務(wù)標(biāo)識(shí)：每個(gè)事務(wù)給定一個(gè)具有惟一性的標(biāo)識(shí)符 log記錄項(xiàng) : start_transaction, t write_item, t, x, 舊值, 新值 read_item, t, x commit, t abort, t 寫動(dòng)作：寫log比寫數(shù)據(jù)優(yōu)先 log存儲(chǔ)：一般存在盤上, 還會(huì)定期備份到磁帶上 6、理解分布式數(shù)據(jù)庫數(shù)據(jù)更新常見方法 多站點(diǎn)數(shù)據(jù)更新、主文本更新法、快照方法 7、理解故障恢復(fù)時(shí)檢查點(diǎn)知識(shí) 檢查點(diǎn)（checkpoint）：設(shè)置一個(gè)周期性（時(shí)間/容量）操作點(diǎn) a) log buffer內(nèi)容寫入log數(shù)

16、據(jù)集 b) 寫檢查點(diǎn)log信息：當(dāng)前活動(dòng)事務(wù)表, 每個(gè)事務(wù)最近一次log記錄在log文件中的位置 c) db buffer內(nèi)容寫入db d) 將本次檢查點(diǎn)log項(xiàng)在log文件中的地址記入“重啟動(dòng)文件” 8、能夠描述兩階段提交協(xié)議的特點(diǎn)：2pc協(xié)議的重要特點(diǎn)：1允許參與者單方面撤銷事務(wù) 2一旦參與者確定了提交或撤銷協(xié)議，它就不能再更改它的提議3當(dāng)參與者處于就緒狀態(tài)時(shí)，根據(jù)協(xié)調(diào)者發(fā)出的消息種類，它可以轉(zhuǎn)換為提交狀態(tài)或者撤銷狀態(tài)4協(xié)調(diào)者根據(jù)全局提交規(guī)則做出全局終止決定5協(xié)調(diào)者和參與者可能進(jìn)入互相等待對方消息的狀態(tài)，使用定時(shí)器，保證退出消息等待狀態(tài) 第五章分布式數(shù)據(jù)庫中的并發(fā)控制 1、理解封鎖的基本準(zhǔn)

17、則 1事務(wù)t在執(zhí)行任何read_item（x）操作之前，必須先執(zhí)行read_lock(x)或者write_lock(x)操作 2事務(wù)t在執(zhí)行任何write_item（x）操作之前，必須先執(zhí)行write_lock(x)操作 3如果事務(wù)t執(zhí)行read_lock(x)操作,數(shù)據(jù)項(xiàng)x必須沒有加鎖或者已經(jīng)加了讀鎖，否則事務(wù)t的這個(gè)操作不能進(jìn)行 4如果事務(wù)t執(zhí)行write_lock(x)操作,數(shù)據(jù)項(xiàng)x必須沒有加鎖，否則事務(wù)t的這個(gè)操作不能進(jìn)行 5事務(wù)t在完成所有read_item（x）和write_item（x）操作之后，必須執(zhí)行unlock(x)操作6如果事務(wù)t已經(jīng)持有數(shù)據(jù)項(xiàng)x上的一個(gè)讀鎖或者一個(gè)寫鎖，

18、那么它不能再執(zhí)行read_lock(x)操作 7如果事務(wù)t已經(jīng)持有數(shù)據(jù)項(xiàng)x上的一個(gè)讀鎖或者一個(gè)寫鎖，那么它不能再執(zhí)行write_lock(x)操作 8如果事務(wù)t沒有持有數(shù)據(jù)項(xiàng)x上的一個(gè)讀鎖或者一個(gè)寫鎖，那么它不能執(zhí)行unlock(x)操作 2、理解基于時(shí)標(biāo)的并發(fā)控制方法 并發(fā)控制方法包含全局時(shí)標(biāo)和局部時(shí)標(biāo) 3、掌握死鎖檢測的方法分類 局部死鎖：僅在一個(gè)站點(diǎn)上發(fā)生的死鎖 全局死鎖：涉及多個(gè)站點(diǎn)的死鎖(即等待圈由多個(gè)站點(diǎn)組成) 4、理解一致性調(diào)度和可串行化調(diào)度的特點(diǎn) 一致性調(diào)度：調(diào)度可以使得數(shù)據(jù)庫從一個(gè)一致性狀態(tài)轉(zhuǎn)變?yōu)榱硪粋€(gè)一致性狀態(tài)，則稱調(diào)度為一致性調(diào)度 可串行化調(diào)度：如果一個(gè)調(diào)度等價(jià)于某個(gè)串行

19、調(diào)度，則該調(diào)度稱為可串行化調(diào)度。 也就是說，該調(diào)度可以通過一系列非沖突動(dòng)作的交換操作使其成為串行調(diào)度 5、能夠描述死鎖發(fā)生的四個(gè)必要條件：會(huì)考試 互斥條件：事務(wù)請求對資源的獨(dú)占控制 等待條件：事務(wù)已持有分配給它的資源, 又去申請并等待別的資源 非搶占條件：直到資源被持有它的事務(wù)釋放前, 不可能將資源強(qiáng)制從持有它的事務(wù)奪去 循環(huán)等待條件：存在事務(wù)互相等待的等待圈 6、能夠列舉并發(fā)控制算法 悲觀并發(fā)控制法和樂觀并發(fā)控制法 悲觀并發(fā)控制法有基于封鎖的算法、基于時(shí)標(biāo)排序的算法和混合算法。樂觀的方法也可分為基于封鎖或基于時(shí)標(biāo)排序的算法。 第六章分布式數(shù)據(jù)庫中的可靠性 1、理解可靠性和可用性的含義與關(guān)系

20、可靠性：指數(shù)據(jù)庫在一給定時(shí)間間隔內(nèi)不產(chǎn)生任何失敗的概率。它強(qiáng)調(diào)數(shù)據(jù)庫的正確性，要求數(shù)據(jù)庫正確運(yùn)行。通常用來描述不可修復(fù)的系統(tǒng)。 可用性：強(qiáng)調(diào)的是當(dāng)需要訪問數(shù)據(jù)庫時(shí)，它是可用的。指在給定的時(shí)間點(diǎn)系統(tǒng)可以正常運(yùn)行的概率。通常用于描述那些可以修復(fù)的系統(tǒng)。 兩者關(guān)系：通常認(rèn)為構(gòu)建可用性的系統(tǒng)比可靠性的系統(tǒng)容易。兩者是統(tǒng)一的，可靠性高的系統(tǒng)可用性自然是好的。 兩者又是矛盾的，增加錯(cuò)誤風(fēng)險(xiǎn)的情況下，可提高可用性;采用太謹(jǐn)慎的策略會(huì)降低可用性 2、理解兩階段提交協(xié)議如何轉(zhuǎn)為三階段提交協(xié)議 2pc中的狀態(tài)： c(提交)狀態(tài)是可提交狀態(tài), 其它為不可提交狀態(tài)。ready 狀態(tài)是不可提交狀態(tài)。wait狀態(tài)是不可提

21、交狀態(tài)。它們都侵犯了非阻斷協(xié)議的充要條件, 從而考慮改變2pc, 使其滿足非阻斷協(xié)議條件。在wait 和 commit 之間, 或者在ready和commit之間加入另一種狀態(tài)作為緩沖狀態(tài), 從而有了3pc協(xié)議 3、掌握分布式可靠性協(xié)議的組成。簡答 可靠性協(xié)議組成 ：包括提交、終結(jié)、恢復(fù)協(xié)議。提交和恢復(fù)協(xié)議詳細(xì)說明提交命令和恢復(fù)命令是如何執(zhí)行的。終結(jié)協(xié)議是分布式系統(tǒng)特有的協(xié)議。在執(zhí)行一個(gè)分布式事務(wù)時(shí)，若一個(gè)site故障，希望其它site也停止該事務(wù)。處理這種情況的技術(shù)就稱為終止協(xié)議。 4、理解發(fā)生網(wǎng)絡(luò)分割時(shí)冗余分布式數(shù)據(jù)庫和非冗余數(shù)據(jù)庫采用的處理協(xié)議 非冗余數(shù)據(jù)庫：任何需要訪問存儲(chǔ)在另一網(wǎng)絡(luò)區(qū)

22、域里的數(shù)據(jù)項(xiàng)的新事務(wù)都被阻斷, 等待網(wǎng)絡(luò)修復(fù)。位于同一區(qū)域里的數(shù)據(jù)項(xiàng)的并發(fā)訪問由并發(fā)控制算法處理。網(wǎng)絡(luò)分割時(shí)由提交協(xié)議處理 冗余數(shù)據(jù)庫：分割時(shí), 副本可能位于不同的區(qū)域。由復(fù)制協(xié)議處理 5、能夠描述三階段提交協(xié)議中事務(wù)協(xié)調(diào)者和參與者的狀態(tài)轉(zhuǎn)換 p188頁圖6.4 考試 6、能夠采用版本號(hào)法進(jìn)行不一致性檢測，并且應(yīng)用于實(shí)際。大題 需要首先發(fā)現(xiàn)哪些數(shù)據(jù)部分已經(jīng)不一致（不一致性檢測） 然后根據(jù)發(fā)生的情況，給這些部分賦予一個(gè)最合理的值（不一致性的解法） 檢測方法：采用版本號(hào) p200頁例子 第七章分布式數(shù)據(jù)庫的安全性與目錄管理1、理解分布式數(shù)據(jù)庫的動(dòng)態(tài)授權(quán)語句的形式 1用戶對自己生成的關(guān)系擁有全權(quán),

23、通過授權(quán)和收權(quán)語句完成對數(shù)據(jù)開放, 保密的存取權(quán)授予(grant, revoke)。授權(quán)語句授權(quán)語句：granttowith grant option 2訪問表(at)法 2、理解數(shù)據(jù)庫的安全性含義 數(shù)據(jù)庫安全性包括兩個(gè)方面的內(nèi)容：數(shù)據(jù)庫數(shù)據(jù)的保密性和安全性。 第二篇：分布式oa系統(tǒng)的數(shù)據(jù)庫同步復(fù)制技術(shù)分布式oa系統(tǒng)的數(shù)據(jù)庫同步復(fù)制技術(shù) 一、背景概述 隨著政府上網(wǎng)、電子政務(wù)的不斷普及和深入，ibm公司的lotus domino系統(tǒng)在國內(nèi)得到廣泛的應(yīng)用。其中不乏大型的、跨地域的企事業(yè)單位或集團(tuán)公司應(yīng)用案例。這些案例一般采用分布式系統(tǒng)結(jié)構(gòu)，即分布在全國各地的分支機(jī)構(gòu)分別設(shè)有獨(dú)立的數(shù)據(jù)庫服務(wù)器，各地

24、數(shù)據(jù)庫服務(wù)器采用數(shù)據(jù)庫同步復(fù)制的方式更新本地?cái)?shù)據(jù)庫復(fù)本內(nèi)容。從而使得各地終端用戶及時(shí)、快捷、可靠地訪問到最新公告、新聞等。 本文結(jié)合呼和浩特鐵路局客運(yùn)公司辦公自動(dòng)化系統(tǒng)案例討論基于ibm公司的lotus domino技術(shù)構(gòu)建的分布式oa系統(tǒng)中數(shù)據(jù)庫之間的同步復(fù)制技術(shù)。 二、幾個(gè)概念 ibm公司的lotus產(chǎn)品包含lotus domino server ，lotus notes，lotus domino administrator和lotus domino designer。lotus domino server為后臺(tái)數(shù)據(jù)庫平臺(tái)，lotus notes為客戶端，lotus domino admi

25、nistrator為系統(tǒng)管理平臺(tái)，lotus domino designer設(shè)計(jì)開發(fā)工具。先介紹幾個(gè)domino中和同步復(fù)制有關(guān)的概念。1、復(fù)制 notes允許在多個(gè)服務(wù)器或工作站上保存數(shù)據(jù)庫的多個(gè)拷貝，這些拷貝稱做“復(fù)本”。它們使各個(gè)地方的不同網(wǎng)絡(luò)上的用戶共享相同的信息。復(fù)本與文件的拷貝不同之處在于在復(fù)制時(shí)源文件與其復(fù)本具有相同的復(fù)本標(biāo)識(shí)符。 復(fù)制是在復(fù)本之間共享更改信息的過程。復(fù)制時(shí)，notes通過把更改信息從一個(gè)復(fù)本拷貝到另一個(gè)復(fù)本來更新復(fù)本。最終，notes 使所有復(fù)本保持一致?？梢赃x擇在復(fù)本拷貝之間進(jìn)行復(fù)制，這時(shí)兩個(gè)復(fù)本都發(fā)送并接收更新信息，或者選擇僅從一個(gè)復(fù)本復(fù)制到另一個(gè)復(fù)本。 也

26、可以定期安排復(fù)制，或者根據(jù)需要手動(dòng)進(jìn)行復(fù)制。復(fù)制可以在兩臺(tái)服務(wù)器之間或者在服務(wù)器和工作站之間進(jìn)行。如果設(shè)定為定期進(jìn)行完整復(fù)制，那么 notes會(huì)根據(jù)時(shí)間使所有復(fù)本保持同步。 2、復(fù)本標(biāo)識(shí)符 復(fù)本與源文件或數(shù)據(jù)庫有相同的復(fù)本標(biāo)識(shí)符。這是數(shù)據(jù)庫的復(fù)本與拷貝的區(qū)別所在，因?yàn)橛泄餐臉?biāo)識(shí)符才能使復(fù)本與源數(shù)據(jù)庫之間可以復(fù)制更改信息。如果數(shù)據(jù)庫的兩個(gè)拷貝具有不同的復(fù)本標(biāo)識(shí)符，則不能在它們之間進(jìn)行復(fù)制。 3、復(fù)制沖突和保存沖突 在復(fù)制之間，如果有兩個(gè)或多個(gè)用戶對相同文檔的不同復(fù)本進(jìn)行了編輯，就會(huì)導(dǎo)致復(fù)制沖突。而保存沖突則是在兩個(gè)或多個(gè)用戶同時(shí)編輯服務(wù)器上同一個(gè)數(shù)據(jù)庫的同一個(gè)文檔時(shí)發(fā)生。當(dāng)發(fā)生復(fù)制沖突或保存沖

27、突時(shí)，notes 將在視圖頁面左邊把發(fā)生沖突的文檔標(biāo)注出來。 notes對復(fù)制沖突的處理是這樣的，在兩個(gè)或多個(gè)用戶編輯并保存同一個(gè)文檔之后，下次進(jìn)行復(fù)制時(shí)，notes 將編輯和保存最頻繁的文檔指定為主文檔，而將其他文檔顯示為主文檔的答復(fù)文檔，并在視圖頁面左邊用一個(gè)菱形符號(hào)標(biāo)注出來。如果用戶在一個(gè)復(fù)本中編輯并保存了某文檔，然后另一個(gè)用戶將該文檔刪除，則認(rèn)為該文檔是被刪除的。然而，如果文檔被編輯和保存了多次，或者在該文檔被刪除之后又被另一個(gè)用戶編輯和保存過，則把編輯過的文檔作為主文檔。 note對保存沖突的處理如下，當(dāng)多個(gè)用戶同時(shí)打開相同的文檔進(jìn)行編輯時(shí)，notes指定最先保存的文檔為主文檔。當(dāng)另

28、一個(gè)用戶試圖保存同一文檔時(shí)，notes 就會(huì)提示該用戶把它作為“保存沖突”文檔來保存。如果用戶這樣做了，那么 notes 將它顯示為主文檔的答復(fù)文檔，并在視圖頁面左邊用一個(gè)菱形符號(hào)標(biāo)注出來。 根據(jù)筆者的經(jīng)驗(yàn)，在實(shí)際開發(fā)過程中，我們應(yīng)該通過設(shè)計(jì)控制保存沖突，避免文檔產(chǎn)生“保存沖突”的答復(fù)文檔。對于復(fù)制沖突可以設(shè)置數(shù)據(jù)庫合并復(fù)制沖突，這樣如果產(chǎn)生增量改動(dòng)，服務(wù)器在復(fù)制過程中會(huì)自動(dòng)合并沖突。需要說明的是，notes在進(jìn)行復(fù)制時(shí)，并不是傳統(tǒng)意義上的完全拷貝，而是一系列的規(guī)則進(jìn)行增量的合并。 4、復(fù)制類型 domino中支持四種不同的復(fù)制方式 拉入推出：是一個(gè)雙向過程。此過程進(jìn)行時(shí)，呼叫服務(wù)器從響應(yīng)服務(wù)

29、器拉入更新，然后向響應(yīng)服務(wù)器推出自己的更新。使用“拉入推出”時(shí)，呼叫服務(wù)器上的 replicator 任務(wù)執(zhí)行所有的工作。拉入推出是系統(tǒng)缺省的復(fù)制方式。 分別拉入：是兩個(gè)服務(wù)器交換更新的雙向過程。使用“分別拉入”時(shí)，兩個(gè)復(fù)制器（一個(gè)在呼叫服務(wù)器上，另一個(gè)在響應(yīng)服務(wù)器上）共同進(jìn)行復(fù)制工作。 只推出：是呼叫服務(wù)器向響應(yīng)服務(wù)器推出更新的單向過程。單向復(fù)制總是比雙向復(fù)制耗時(shí)少。 只拉入：是呼叫服務(wù)器從響應(yīng)服務(wù)器拉入更新的單向過程。單向復(fù)制總是比雙向復(fù)制耗時(shí)少。 三、案例 筆者曾經(jīng)參與呼和浩特鐵路局客運(yùn)公司辦公自動(dòng)化系統(tǒng)的設(shè)計(jì)、開發(fā)和實(shí)施工作。呼和浩特鐵路局客運(yùn)公司包括三個(gè)信息中心，分別在呼和浩特市、包

30、頭市和東河區(qū)三個(gè)地方，三地之間通過64k的ddn專線連接。因?yàn)閹挼南拗?，用戶遠(yuǎn)程訪問速度成為本系統(tǒng)的瓶頸，經(jīng)過再三論證，我們決定構(gòu)建分布式數(shù)據(jù)庫存儲(chǔ)架構(gòu)，采用后臺(tái)數(shù)據(jù)庫實(shí)時(shí)同步復(fù)制技術(shù)使三個(gè)異地服務(wù)器內(nèi)容一致，將遠(yuǎn)程訪問轉(zhuǎn)化為本地訪問，從而提高終端用戶訪問速度。 詳細(xì)步驟如下。 1、安裝服務(wù)器 在三地信息中心分別安裝domino服務(wù)器，服務(wù)器的詳細(xì)配置并不復(fù)雜，讀者可以參閱相關(guān)資料，一般情況下按照安裝配置向?qū)牟骄涂梢钥旖菖渲猛戤叀Ｗ⒁馊_(tái)domino服務(wù)器不要同名，其簡單拓?fù)浣Y(jié)構(gòu)如下： 圖中呼市處于相對中心的位置，所以呼市和包頭之間，呼市和東河之間分別建立了互推復(fù)制機(jī)制，為了降低網(wǎng)絡(luò)負(fù)擔(dān)和

31、流通環(huán)節(jié)，沒有建立包頭和東河之間的復(fù)制，各地直接通過與呼市同步來保持三地?cái)?shù)據(jù)的一致。一般而言，如果各分支機(jī)構(gòu)處于平等位置，互相之間的數(shù)據(jù)流量相當(dāng)，也可以兩兩之間建立復(fù)制機(jī)制。 2、建立服務(wù)器之間的連接 對于兩個(gè)服務(wù)器之間進(jìn)行的復(fù)制，應(yīng)創(chuàng)建一個(gè)“連接”文檔來指定進(jìn)行信息交換的方式和時(shí)間?！斑B接”文檔存儲(chǔ)在“domino 目錄”中。一次僅使用一個(gè)“連接”文檔來處理每對服務(wù)器之間的所有復(fù)制。創(chuàng)建不必要的“連接”文檔會(huì)增加網(wǎng)絡(luò)傳輸量和阻塞。 缺省情況下，郵件路由和復(fù)制都已被啟用，但是可以更改此設(shè)置并使用單獨(dú)的“連接”文檔來安排每項(xiàng)任務(wù)。這樣，就可以分別控制復(fù)制和郵件路由的特定時(shí)間、時(shí)間范圍或重復(fù)間隔，

32、并根據(jù)需要增加或減小這些設(shè)置。 怎么保證服務(wù)器之間的連接能順利的連通？實(shí)際上對于物理連接形式domino并不關(guān)心，也就是說物理上無論通過什么連接方式，專線、光纖、x.25、電話撥號(hào)等，只要tcp/ip通，簡單說只要能ping通，就能夠保證服務(wù)器之間順利連接。 下面給出了建立服務(wù)器之間連接的操作步驟和主要參數(shù)的設(shè)置說明： a）在 domino administrator 中單擊“配置”附簽。 b）在“使用目錄”域中選擇連接服務(wù)器的“domino 目錄”。 c）單擊“服務(wù)器”，然后單擊“連接”。 d）單擊“添加連接”。 f）關(guān)鍵域配置描述：域輸入 源服務(wù)器連接服務(wù)器的名稱 使用以下端口連接服務(wù)器或

33、源服務(wù)器使用的網(wǎng)絡(luò)端口（或協(xié)議）名稱 使用優(yōu)先級(jí)選擇一個(gè)：“一般”（缺?。暗汀?目標(biāo)服務(wù)器響應(yīng)服務(wù)器的名稱 可選網(wǎng)絡(luò)地址與所選協(xié)議相適應(yīng)的目標(biāo)服務(wù)器的地址。對于 tcp/ip，應(yīng)使用完全有效的網(wǎng)絡(luò)域名稱（首選）或 ip 地址（例如：hr-e.a 或者 192.22.256.36）。 對 tcp/ip 或其他需要特定網(wǎng)絡(luò)地址的協(xié)議，建議填寫此域。 復(fù)制類型缺省情況下，domino 的復(fù)制方向?yàn)椤袄胪瞥觥薄５鶕?jù)實(shí)際情況，為了平衡服務(wù)器之間的負(fù)載，充分發(fā)揮每個(gè)服務(wù)器的性能，我們可以設(shè)定雙方互推或者互拉，本例中我們采用服務(wù)器雙方互推的方式，即每個(gè)服務(wù)器上的連接復(fù)制類型都是由源服務(wù)器向目標(biāo)服務(wù)器推

34、出。 復(fù)制文件/目錄如果為空，則服務(wù)器將data目錄下的所有存在復(fù)本的數(shù)據(jù)庫全部進(jìn)行復(fù)制，否則填寫哪個(gè)庫系統(tǒng)就復(fù)制哪個(gè)庫。 安排在安排中可以設(shè)置連接時(shí)間、重復(fù)間隔、每周復(fù)制日期等參數(shù)。可根據(jù)實(shí)際情況設(shè)定，本例設(shè)置為每日8：00到晚上10：00連接，連接期間每一小時(shí)進(jìn)行同步復(fù)制或服務(wù)器依據(jù)增量自動(dòng)復(fù)制，非連接時(shí)間服務(wù)器處理其他性能調(diào)優(yōu)動(dòng)作，如更新數(shù)據(jù)庫索引等。 h）保存文檔。 3、建立數(shù)據(jù)庫復(fù)本 連接建立成功以后，保證服務(wù)器之間可以進(jìn)行通訊了，下一步就是對要進(jìn)行同步的數(shù)據(jù)庫建立復(fù)本，當(dāng)建立了復(fù)本以后，通過連接設(shè)定就能保證異地各個(gè)復(fù)本之間的數(shù)據(jù)完全一致。 這里需要說明的是，我們在第一臺(tái)服務(wù)器上建立

35、了一套數(shù)據(jù)庫系統(tǒng)，對于需要同步復(fù)制的所有數(shù)據(jù)庫，在其他服務(wù)器上只需要產(chǎn)生他們的復(fù)本，而不能再在每臺(tái)服務(wù)器上分別創(chuàng)建相同的數(shù)據(jù)庫。在本例中我們在呼市客運(yùn)公司信息中心安裝配置好第一臺(tái)服務(wù)器后，在包頭信息中心和東河信息中心的domino服務(wù)器上則通過呼市信息中心服務(wù)器建立各自本地所有需要的數(shù)據(jù)庫復(fù)本。 如果要在本地domino服務(wù)器上創(chuàng)建源domino服務(wù)器的復(fù)本數(shù)據(jù)庫，需要本地服務(wù)器的系統(tǒng)管理員具有對源服務(wù)器訪問和創(chuàng)建復(fù)本的權(quán)限，因?yàn)閐omino對權(quán)限控制很嚴(yán)格，尤其是多域用戶之間的訪問，其目的就是為了充分保證系統(tǒng)的安全性。那么怎樣才能具有這樣的創(chuàng)建復(fù)本的權(quán)限呢？需要具有兩個(gè)基本的存取權(quán)限就可以在

36、本服務(wù)器上創(chuàng)建源服務(wù)器的數(shù)據(jù)庫復(fù)本，一是源服務(wù)器配置中允許本地服務(wù)器的系統(tǒng)管理員訪問，二是允許本地服務(wù)器的系統(tǒng)管理員創(chuàng)建數(shù)據(jù)庫復(fù)本，這兩個(gè)權(quán)限由源數(shù)據(jù)庫的系統(tǒng)管理員設(shè)置給目標(biāo)數(shù)據(jù)庫的系統(tǒng)管理員。結(jié)合本例，需要在包頭信息中心的服務(wù)器上建立呼市信息中心的數(shù)據(jù)庫復(fù)本，則首先在呼市信息中心的服務(wù)器上配置“當(dāng)前服務(wù)器”文檔。 a ）在 domino administrator 中單擊“當(dāng)前服務(wù)器”文檔。 b）單擊“編輯服務(wù)器” c）選擇“安全”標(biāo)簽頁，填寫以下兩項(xiàng)：域輸入 訪問服務(wù)器本例為包頭信息中心系統(tǒng)服務(wù)器名稱及管理員的用戶名稱 創(chuàng)建數(shù)據(jù)庫復(fù)本同樣是包頭信息中心系統(tǒng)管理員的用戶名稱 d保存后退出。

37、接下來就可以在包頭信息中心的服務(wù)器上創(chuàng)建源數(shù)據(jù)庫的復(fù)本了，這步動(dòng)作比較簡單，選擇源數(shù)據(jù)庫，從菜單中執(zhí)行創(chuàng)建復(fù)本功能即可，這里不在詳細(xì)描述。 同樣的處理在東河的服務(wù)器上如法炮制一遍，則所有數(shù)據(jù)庫復(fù)本成功建立完畢。 4、復(fù)制測試 完成以上三步，配置就全部完成，接下來就要測試一下配置是否完全成功以及配置是否生效。我們測試主要包括兩個(gè)內(nèi)容：一是測試連接是否成功，能否進(jìn)行復(fù)制動(dòng)作。二是測試設(shè)置的復(fù)制安排是否按照預(yù)定生效。 a）進(jìn)行第一項(xiàng)測試的辦法是在domino的控制臺(tái)上，使用domino的系統(tǒng)命令，進(jìn)行數(shù)據(jù)庫的推、拉測試，檢查復(fù)制是否能成功進(jìn)行，命令格式如下： 拉入復(fù)制 語法：pull servern

38、ame databasename 描述：強(qiáng)制從指定服務(wù)器到本地服務(wù)器進(jìn)行單向復(fù)制。通過在命令行中包括單個(gè)數(shù)據(jù)庫名稱，將其從特定服務(wù)器單向復(fù)制到本地服務(wù)器。發(fā)起復(fù)制的服務(wù)器從指定的服務(wù)器接受數(shù)據(jù)，但不能申請將自己的數(shù)據(jù)復(fù)制到其他服務(wù)器上。該命令重設(shè)在“domino 目錄”中預(yù)定的任何復(fù)制，而強(qiáng)制一臺(tái)服務(wù)器與發(fā)起復(fù)制的服務(wù)器立即進(jìn)行復(fù)制。如果可能，請輸入服務(wù)器完整的層次結(jié)構(gòu)名稱。 推出復(fù)制 語法：push servername databasename 描述：強(qiáng)制進(jìn)行從本地服務(wù)器到指定服務(wù)器的單向復(fù)制。也可以通過在命令行中包括要復(fù)制的單個(gè)數(shù)據(jù)庫名稱，來將其從本地服務(wù)器單向復(fù)制到特定服務(wù)器。發(fā)起復(fù)制

39、的服務(wù)器將數(shù)據(jù)發(fā)送到指定的服務(wù)器，但不申請獲得數(shù)據(jù)。該命令可以重設(shè)在“domino 目錄”中預(yù)定的任何復(fù)制，而強(qiáng)制一臺(tái)服務(wù)器立即與發(fā)起復(fù)制的服務(wù)器進(jìn)行復(fù)制。如果可能的話，請指定服務(wù)器完整的層次結(jié)構(gòu)名稱。 b）第二項(xiàng)測試通過將連接文檔的安排時(shí)間設(shè)置為兩分鐘進(jìn)行一次，同時(shí)觀察domino的系統(tǒng)控制臺(tái)，查看服務(wù)器的動(dòng)作，以確保安排設(shè)定生效。正確的結(jié)果是從控制臺(tái)上能看到系統(tǒng)報(bào)告復(fù)制過程。 按照以上實(shí)例說明進(jìn)行，沒有任何問題。 四、結(jié)束語 我們同樣可以在客戶端利用復(fù)制技術(shù)，例如在本地客戶端建立郵件文件數(shù)據(jù)庫的復(fù)本，以便與我們在外出或者脫機(jī)狀態(tài)下還可以訪問郵件文件。本地復(fù)本要求沒有在服務(wù)器之間進(jìn)行復(fù)制的要

40、求那么高，本地復(fù)本的作用體現(xiàn)在通過本地復(fù)本，可以在沒有通過網(wǎng)絡(luò)連接服務(wù)器時(shí)對數(shù)據(jù)庫進(jìn)行操作。當(dāng)設(shè)置 notes 為遠(yuǎn)程工作站時(shí)，就可以通過調(diào)制解調(diào)器呼叫服務(wù)器并在本地復(fù)本和服務(wù)器數(shù)據(jù)庫之間交換更新信息。 第三篇：從google spanner漫談分布式存儲(chǔ)與數(shù)據(jù)庫技術(shù)從google spanner漫談分布式存儲(chǔ)與數(shù)據(jù)庫技術(shù) 文/曹偉 spanner 的設(shè)計(jì)反映了 google 多年來在分布式存儲(chǔ)系統(tǒng)領(lǐng)域上經(jīng)驗(yàn)的積累和沉淀，它采用了 megastore 的數(shù)據(jù)模型，chubby 的數(shù)據(jù)復(fù)制和一致性算法，而在數(shù)據(jù)的可擴(kuò)展性上使用了 bigtable 中的技術(shù)。新穎之處在于，它使用高精度和可觀測誤差

41、的本地時(shí)鐘來判斷分布式系統(tǒng)中事件的先后順序。spanner 代表了分布式數(shù)據(jù)庫領(lǐng)域的新趨勢newsql。 spanner 是 google 最近公開的新一代分布式數(shù)據(jù)庫，它既具有 nosql 系統(tǒng)的可擴(kuò)展性，也具有關(guān)系數(shù)據(jù)庫的功能。例如，它支持類似 sql 的查詢語言、支持表連接、支持事務(wù)（包括分布式事務(wù)）。spanner 可以將一份數(shù)據(jù)復(fù)制到全球范圍的多個(gè)數(shù)據(jù)中心，并保證數(shù)據(jù)的一致性。一套 spanner 集群可以擴(kuò)展到上百個(gè)數(shù)據(jù)中心、百萬臺(tái)服務(wù)器和上t條數(shù)據(jù)庫記錄的規(guī)模。目前，google 廣告業(yè)務(wù)的后臺(tái)（f1）已從 mysql 分庫分表方案遷移到了 spanner 上。 數(shù)據(jù)模型 傳統(tǒng)的

42、 rdbms（例如 mysql）采用關(guān)系模型，有豐富的功能，支持 sql 查詢語句。而 nosql 數(shù)據(jù)庫多是在 key-value 存儲(chǔ)之上增加有限的功能，如列索引、范圍查詢等，但具有良好的可擴(kuò)展性。spanner 繼承了 megastore 的設(shè)計(jì)，數(shù)據(jù)模型介于 rdbms 和 nosql 之間，提供樹形、層次化的數(shù)據(jù)庫 schema，一方面支持類 sql 的查詢語言，提供表連接等關(guān)系數(shù)據(jù)庫的特性，功能上類似于 rdbms；另一方面整個(gè)數(shù)據(jù)庫中的所有記錄都存儲(chǔ)在同一個(gè) key-value 大表中，實(shí)現(xiàn)上類似于 bigtable，具有 nosql 系統(tǒng)的可擴(kuò)展性。 在 spanner 中，應(yīng)

43、用可以在一個(gè)數(shù)據(jù)庫里創(chuàng)建多個(gè)表，同時(shí)需要指定這些表之間的層次關(guān)系。例如，圖 1 中創(chuàng)建的兩個(gè)表用戶表（users）和相冊表（albums），并且指定用戶表是相冊表的父節(jié)點(diǎn)。父節(jié)點(diǎn)和子節(jié)點(diǎn)間存在著一對多的關(guān)系，用戶表中的一條記錄（一個(gè)用戶）對應(yīng)著相冊表中的多條記錄（多個(gè)相冊）。此外，要求子節(jié)點(diǎn)的主鍵必須以父節(jié)點(diǎn)的主鍵作為前綴。例如，用戶表的主鍵（用戶 id）就是相冊表主鍵（用戶 id+ 相冊 id）的前綴。 圖 1 schema 示例，表之間的層次關(guān)系，記錄排序后交錯(cuò)的存儲(chǔ) 顯然所有表的主鍵都將根節(jié)點(diǎn)的主鍵作為前綴，spanner 將根節(jié)點(diǎn)表中的一條記錄，和以其主鍵作為前綴的其他表中的所有記錄的

44、集合稱作一個(gè) directory。例如，一個(gè)用戶的記錄及該用戶所有相冊的記錄組成了一個(gè) directory。directory 是 spanner 中對數(shù)據(jù)進(jìn)行分區(qū)、 復(fù)制和遷移的基本單位，應(yīng)用可以指定一個(gè) directory 有多少個(gè)副本，分別存放在哪些機(jī)房中，例如把用戶的 directory 存放在這個(gè)用戶所在地區(qū)附近的幾個(gè)機(jī)房中。 這樣的數(shù)據(jù)模型具有以下好處。 · 一個(gè) directory 中所有記錄的主鍵都具有相同前綴。在存儲(chǔ)到底層 key-value 大表時(shí)，會(huì)被分配到相鄰的位置。如果數(shù)據(jù)量不是非常大，會(huì)位于同一個(gè)節(jié)點(diǎn)上，這不僅提高了數(shù)據(jù)訪問的局部性，也保證了在一個(gè) dir

45、ectory 中發(fā)生的事務(wù)都是單機(jī)的。 · directory 還實(shí)現(xiàn)了從細(xì)粒度上對數(shù)據(jù)進(jìn)行分區(qū)。整個(gè)數(shù)據(jù)庫被劃分為百萬個(gè)甚至更多個(gè) directory，每個(gè) directory 可以定義自己的復(fù)制策略。這種 directory-based 的數(shù)據(jù)分區(qū)方式比 mysql 分庫分表時(shí) table-based 的粒度要細(xì)，而比 yahoo!的 pnuts 系統(tǒng)中 row-based 的粒度要粗。 · directory 提供了高效的表連接運(yùn)算方式。在一個(gè) directory 中，多張表上的記錄按主鍵排序，交錯(cuò)（interleaved）地存儲(chǔ)在一起，因此進(jìn)行表連接運(yùn)算時(shí)無需排序即

46、可在表間直接進(jìn)行歸并。 復(fù)制和一致性 spanner 使用 paxos 協(xié)議在多個(gè)副本間同步 redo 日志，從而保證數(shù)據(jù)在多個(gè)副本上是一致的。google 的工程師鐘情于 paxos 協(xié)議，chubby、megastore 和 spanner 等一系列產(chǎn)品都是在 paxos 協(xié)議的基礎(chǔ)上實(shí)現(xiàn)一致性的。 paxos 的基本協(xié)議很簡單。協(xié)議中有三個(gè)角色：proposer、acceptor 和 learner，learner 和 proposer 分別是讀者和寫者，acceptor 相當(dāng)于存儲(chǔ)節(jié)點(diǎn)。整個(gè)協(xié)議描述的是，當(dāng)系統(tǒng)中有多個(gè) proposer 和 acceptor 時(shí)，每次 proposer

47、 寫一個(gè)變量就會(huì)啟動(dòng)一輪決議過程（paxos instance），如圖 2 所示。決議過程可以保證即使多個(gè) proposer 同時(shí)寫，結(jié)果也不會(huì)在 acceptor 節(jié)點(diǎn)上不一致。確切地說，一旦某個(gè) proposer 提交的值被大多數(shù) acceptor 接受，那么這個(gè)值就被選中，在整輪決議的過程中該變量就不會(huì)再被修改為其他值。如果另一個(gè) proposer 要寫入其他值，必須啟動(dòng)下一輪決議過程，而決議過程之間是串行（serializable）的。 圖 2 paxos 協(xié)議正常執(zhí)行流程 一輪決議過程分為兩個(gè)階段，即 prepare 階段和 accept 階段。 · 第一階段a：propo

48、ser 向所有 acceptor 節(jié)點(diǎn)廣播 prepare 消息，消息中只包含一個(gè)序號(hào)n。proposer 需要保證這個(gè)序號(hào)在這輪決議過程中是全局唯一的（這很容易做到，假如系統(tǒng)中有兩個(gè) proposer，那么一個(gè) proposer 使用1，3，5，7，9，另一個(gè) proposer 則使用0，2，4，6，8，）。 ·第一階段b：acceptor 接收到 prepare 消息后，如果n是到目前為止見過的最大序號(hào)，就返回一個(gè) promise 消息，承諾不會(huì)接受序號(hào)小于n的請求；如果已接受過其他 proposer 提交的值，則會(huì)將這個(gè)值連同提交這個(gè)值的請求的序號(hào)一同返回。 · 第二

49、階段a：當(dāng) proposer 從大多數(shù) acceptor 節(jié)點(diǎn)收到了 promise 消息后，就可以選擇接下來要向 acceptor 提交的值了。一般情況下，當(dāng)然選原本打算寫入的值，但如果從收到的 promise 消息中發(fā)現(xiàn)已經(jīng)有其他值被 acceptor 接受了，那么為了避免造成數(shù)據(jù)不一致的風(fēng)險(xiǎn)，這時(shí) proposer 就必須“大義滅親”，放棄自己打算寫入的值，從其他 proposer 提交的序號(hào)中選擇一個(gè)最大的值。接下來 proposer 向所有的 acceptor 節(jié)點(diǎn)發(fā)送 accept 包，其中包含在第一階段中挑選的序號(hào)n和剛才選擇的值v。 ·第二階段b：acceptor 收

50、到 accept 包之后，如果n的大小不違反對其他 proposer 的承諾，就接受這個(gè)請求，記錄下值v和序號(hào)n，返回一個(gè) ack 消息。反之，則返回一個(gè) reject 消息。 如果 proposer 從大多數(shù) acceptor 節(jié)點(diǎn)收到了 ack 消息，說明寫操作成功。而如果在寫操作過程中失敗，proposer 可以增大序號(hào)，重新執(zhí)行第一階段。 基本的 paxos 協(xié)議可以保證值一旦被選出后就一定不會(huì)改變，但不能保證一定會(huì)選出值來。換句話說，這個(gè)投票算法不一定收斂。有兩個(gè)方法可以加速收斂的過程：一個(gè)是在出現(xiàn)沖突后通過隨機(jī)延遲把機(jī)會(huì)讓給其他 proposer，另一個(gè)是盡量讓系統(tǒng)中只有一個(gè) pr

51、oposer 去提交。在 chubby 和 spanner 系統(tǒng)中這兩種方法都用上了，先用隨機(jī)延遲的方法通過一輪 paxos 協(xié)議，在多個(gè) proposer 中選舉出一個(gè) leader 節(jié)點(diǎn)。接下來所有的寫操作都通過這個(gè) leader 節(jié)點(diǎn)，而 leader 節(jié)點(diǎn)一般還是比較“長壽”的，在廣域網(wǎng)環(huán)境下平均“任期”可以達(dá)到一天以上。而 megastore 系統(tǒng)中沒有很好地解決這個(gè)問題，所有的 proposer 都可以發(fā)起寫操作，這是 megastore 寫入性能不高的原因之一。 基本的 paxos 協(xié)議還存在性能上的問題，一輪決議過程通常需要進(jìn)行兩個(gè)回合通信，而一次跨機(jī)房通信的代價(jià)為幾十到一百毫

52、秒不等，因此兩個(gè)回合的通信就有點(diǎn)開銷過高了。不過幸運(yùn)的是，絕大多數(shù)情況下，paxos 協(xié)議可以優(yōu)化到僅需一個(gè)回合通信。決議過程的第一階段是不需要指定值的，因此可以把 prepare/promise 的過程捎帶在上一輪決議中完成，或者更進(jìn)一步，在執(zhí)行一輪決議的過程中隱式地涵蓋接下來一輪或者幾輪決議的第一階段。這樣，當(dāng)一輪決議完成之后，其他決議的第一階段也已經(jīng)完成了。如此看來，只要 leader 不發(fā)生更替，paxos 協(xié)議就可以在一個(gè)回合內(nèi)完成。為了支持實(shí)際的業(yè)務(wù)，paxos 協(xié)議還需要支持并發(fā)，多輪決議過程可以并發(fā)執(zhí)行，而代價(jià)是故障恢復(fù)會(huì)更加復(fù)雜。 因?yàn)?leader 節(jié)點(diǎn)上有最新的數(shù)據(jù)，而在

53、其他節(jié)點(diǎn)上為了獲取最新的數(shù)據(jù)來執(zhí)行 paxos 協(xié)議的第一階段，需要一個(gè)回合的通信代價(jià)。因此，chubby 中的讀寫操作，以及 spanner 中的讀寫事務(wù)都僅在 leader 節(jié)點(diǎn)上執(zhí)行。而為了提高讀操作的性能，減輕 leader 節(jié)點(diǎn)的負(fù)載，spanner 還提供了只讀事務(wù)和本地讀。只讀事務(wù)只在 leader 節(jié)點(diǎn)上獲取時(shí)間戳信息，再用這個(gè)時(shí)間戳在其他節(jié)點(diǎn)上執(zhí)行讀操作；而本地讀則讀取節(jié)點(diǎn)上最新版本的數(shù)據(jù)。 與 chubby、 spanner 這種讀寫以 leader 節(jié)點(diǎn)為中心的設(shè)計(jì)相比，megastore 體現(xiàn)了一定的“去中心化”設(shè)計(jì)。每個(gè)客戶端都可以發(fā)起 paxos 寫操作， 而讀操作

54、則盡可能在本地執(zhí)行。如果客戶端發(fā)現(xiàn)本地?cái)?shù)據(jù)不是最新的，會(huì)啟動(dòng) catchup 流程更新數(shù)據(jù)，再執(zhí)行本地讀操作返回給客戶端。 最后，對比下其他系統(tǒng)中 replication 的實(shí)現(xiàn)。在 bigtable 系統(tǒng)中每個(gè) tablet 服務(wù)器是沒有副本的，完全依賴底層 gfs 把數(shù)據(jù)存到多臺(tái)機(jī)器上。數(shù)據(jù)的讀寫都通過單個(gè) tablet 服務(wù)器，在 tablet 服務(wù)器出現(xiàn)故障的時(shí)需要 master 服務(wù)器將 tablet 指派到其他 tablet 服務(wù)器上才能恢復(fù)可用。dynamo 系統(tǒng)則貫徹了“去中心化”的思想，將數(shù)據(jù)保存在多個(gè)副本上，每個(gè)副本都可以寫入（update everywhere）。而不同副

55、本同時(shí)寫入的數(shù)據(jù)可能會(huì)存在不一致，則需要使用版本向量（version vector）記錄不同的值和時(shí)間戳，由應(yīng)用去解釋或合并不一致的數(shù)據(jù)。盡管 dynamo 系統(tǒng)還提供了 nwr 的方式來支持有一致性保證的讀寫操作，但總的來說 dynamo 為了高可用性犧牲了一致性。zookeeper、mongodb 與 chubby、spanner 類似，通過 leader 選舉協(xié)議從多個(gè)副本中選擇一個(gè) leader，所有寫操作都在經(jīng)過 leader 節(jié)點(diǎn)序列化后，同步到其他副本上。zookeeper 則是在寫入大多數(shù)節(jié)點(diǎn)后返回，而 mongodb 主要采用異步的主從復(fù)制方式。 分布式事務(wù) spanner

56、系統(tǒng)中的分布式事務(wù)通過兩階段提交協(xié)議（2pc）實(shí)現(xiàn)。2pc 是一類特殊的一致性協(xié)議，假設(shè)一個(gè)分布式事務(wù)涉及了多個(gè)數(shù)據(jù)節(jié)點(diǎn)，2pc 可以保證在這些節(jié)點(diǎn)上的操作要么全部提交，要么全部失敗，從而保證了整個(gè)分布式事務(wù)的原子性（acid 里的a）。協(xié)議中包含兩個(gè)角色：協(xié)調(diào)者（coordinator）和參與者（participant/cohort）。協(xié)調(diào)者是分布式事務(wù)的發(fā)起者，而參與者是參與了事務(wù)的數(shù)據(jù)節(jié)點(diǎn)。在協(xié)議最基本的形式中，系統(tǒng)中有一個(gè)協(xié)調(diào)者和多個(gè)參與者。 顧名思義，2pc 也包含兩個(gè)階段，即投票階段和提交階段（如圖 3 所示）。 圖 3 兩階段提交協(xié)議 · 在第一階段，協(xié)調(diào)者向所有的參與

57、者發(fā)送投票請求，每個(gè)參與者決定是否要提交事務(wù)。如果打算提交的話需要寫好 redo、undo 等日志，并向協(xié)調(diào)者回復(fù) yes 或 no。 · 在第二階段，協(xié)調(diào)者收到所有參與者的回復(fù)，如果都是 yes，那么決定提交這個(gè)事務(wù)，寫好日志后向所有參與者廣播提交事務(wù)的通知。反之，則中止事務(wù)并且通知所有參與者。參與者收到提交/中止事務(wù)的命令后，執(zhí)行相應(yīng)操作，如果提交的話還需要寫日志。 協(xié)議過程包括兩回合的通信，在協(xié)調(diào)者和參與者端需要多次寫日志，而且整個(gè)過程中所有參與者都占有讀鎖、寫鎖，可見 2pc 開銷不菲。 2pc 最令人詬病之處還不在于性能，而是在有些故障條件下，會(huì)造成所有參與者占有讀鎖、寫鎖

58、堵塞在第二階段，需要人工干預(yù)才能繼續(xù)，存在嚴(yán)重的可用性隱患。假設(shè)故障發(fā)生在第二階段，協(xié)調(diào)者在做出決定后，通知完一個(gè)參與者就宕機(jī)了，更糟糕的是被通知的這位參與者在執(zhí)行完“上級(jí)指示”之后也宕機(jī)了，這時(shí)對其他參與者來說，就必須堵塞在那里等待結(jié)果。 spanner 利用基于 paxos 協(xié)議的復(fù)制技術(shù)，改善了 2pc 的可用性問題。2pc 協(xié)議過程中的協(xié)調(diào)者和參與者生成的日志都會(huì)利用 paxos 協(xié)議復(fù)制到所有副本中，這樣無論是協(xié)調(diào)者或參與者宕機(jī)，都會(huì)有其他副本代替它們，完成 2pc 過程而不至于堵塞。在 paxos 協(xié)議上實(shí)現(xiàn) 2pc 這一思路很巧妙，paxos 協(xié)議保證了大多數(shù)節(jié)點(diǎn)在線情況下的可用

59、性，而 2pc 保證了分布式協(xié)議的一致性。 事件的順序 傳統(tǒng)上，在設(shè)計(jì)一個(gè)分布式系統(tǒng)時(shí)，都會(huì)假設(shè)每個(gè)節(jié)點(diǎn)的運(yùn)行速度和時(shí)鐘的快慢各不相同的情況，并且在節(jié)點(diǎn)之間進(jìn)行同步的唯一方法就是異步通信。系統(tǒng)中的每個(gè)節(jié)點(diǎn)都扮演著觀察者的角色，并從其他節(jié)點(diǎn)接收事件發(fā)生的通知。判斷系統(tǒng)中兩個(gè)事件的先后順序主要依靠分析它們的因果關(guān)系，包括 lamport 時(shí)鐘、向量時(shí)鐘等算法，而這一切都存在通信開銷。 因此，spanner 提出了一種新的思路，在不進(jìn)行通信的情況下，利用高精度和可觀測誤差的本地時(shí)鐘 （truetime api）給事件打上時(shí)間戳，并且以此比較分布式系統(tǒng)中兩個(gè)事件的先后順序。利用這個(gè)方法，spanner 實(shí)現(xiàn)了事務(wù)之間的外部一致性（external consistency）（如圖 4 所示），也就是說，一個(gè)事務(wù)結(jié)束后另一個(gè)事務(wù)才開始，spanner 可以保證第一個(gè)事務(wù)的時(shí)間戳比第二個(gè)事務(wù)的時(shí)間戳要早，從而兩個(gè)事務(wù)被串行化后也一定能保持正確的順序。 圖 4 事務(wù)外部一致性的實(shí)現(xiàn) truetime api 是一個(gè)提供本地時(shí)間的接口，但