第22章并行與分布式數(shù)據(jù)庫

第22章并行與分布式數(shù)據(jù)庫22.1簡(jiǎn)介集中式數(shù)據(jù)庫管理系統(tǒng)——數(shù)據(jù)在獨(dú)立的站點(diǎn)進(jìn)行管理，順序地進(jìn)行事物處理。并行數(shù)據(jù)庫系統(tǒng)——通過并行實(shí)現(xiàn)各種數(shù)據(jù)操作，如數(shù)據(jù)載入、索引建立、數(shù)據(jù)查詢等，可以提高系統(tǒng)的性能。分布式數(shù)據(jù)庫系統(tǒng)——數(shù)據(jù)分布存儲(chǔ)于若干場(chǎng)地，并且每個(gè)場(chǎng)地由獨(dú)立于其它場(chǎng)地的DBMS進(jìn)行數(shù)據(jù)管理。并行與分布技術(shù)特點(diǎn)：增強(qiáng)的可用性：當(dāng)存儲(chǔ)某個(gè)關(guān)系的場(chǎng)地系統(tǒng)崩潰時(shí)，可繼續(xù)使用存儲(chǔ)在別的場(chǎng)地的復(fù)本。數(shù)據(jù)的分布訪問：企業(yè)數(shù)據(jù)可以分布于若干城市，分析時(shí)可能需要訪問不同場(chǎng)地的數(shù)據(jù)，但通常在訪問模式中得到數(shù)據(jù)存儲(chǔ)的局部性（如銀行經(jīng)理通常是查詢本地支行的顧客賬戶），這種局部性可用來分布數(shù)據(jù)。分布數(shù)據(jù)的分析：企業(yè)越來越需要分析所有可用的數(shù)據(jù)，即使這些數(shù)據(jù)存儲(chǔ)在不同場(chǎng)地和不同的數(shù)據(jù)庫系統(tǒng)中。22.2并行數(shù)據(jù)庫系統(tǒng)的可用結(jié)構(gòu)（一）實(shí)現(xiàn)并行DBMS的三種硬件結(jié)構(gòu)：（1）共享內(nèi)存系統(tǒng)（2）共享磁盤系統(tǒng)（3）無共享資源系統(tǒng)（一）實(shí)現(xiàn)并行DBMS的三種硬件結(jié)構(gòu)：連接網(wǎng)絡(luò)全局共享內(nèi)存DDD（1）共享內(nèi)存系統(tǒng)：多個(gè)cpu通過連接網(wǎng)絡(luò)進(jìn)行通信，并能訪問公共的主存。

MMM連接網(wǎng)絡(luò)DDD（2）共享磁盤系統(tǒng)：每個(gè)cpu擁有自己的私有內(nèi)存，并通過連接網(wǎng)絡(luò)直接訪問所有磁盤。沖突問題——隨著cpu數(shù)目的增加，由于內(nèi)存訪問的沖突增加、網(wǎng)絡(luò)通信帶寬有限，cpu性能下降。（一）實(shí)現(xiàn)并行DBMS的三種硬件結(jié)構(gòu)：連接網(wǎng)絡(luò)MMMDDD（3）無共享資源系統(tǒng)：每個(gè)cpu擁有自己的內(nèi)存和磁盤空間，并無公共區(qū)域，cpu之間所有通信通過連接網(wǎng)絡(luò)來完成。大型并行數(shù)據(jù)庫系統(tǒng)的最優(yōu)結(jié)構(gòu)(二)加速比和可擴(kuò)展性每秒處理事物數(shù)cpu數(shù)目線性加速比（理想）亞線性加速比加速比曲線表明對(duì)于固定的數(shù)據(jù)庫大小，通過增加cpu數(shù)目，每秒能處理更多的事物。無共享資源的并行結(jié)構(gòu)——具有近似線性加速比（隨cpu數(shù)目增加，各種操作所需時(shí)間減少。）(二)加速比和可擴(kuò)展性每秒處理事物數(shù)cpu數(shù)目數(shù)據(jù)庫大小線性可擴(kuò)展性亞線性可擴(kuò)展性每個(gè)事物的時(shí)間cpu數(shù)目，每秒處理事物數(shù)亞線性線性可擴(kuò)展性（理想）無共享資源的并行結(jié)構(gòu)——具有線性可擴(kuò)展性（cpu和磁盤數(shù)目隨著數(shù)據(jù)量的增加而按比例增加時(shí)，系統(tǒng)性能保持不變）可擴(kuò)展曲線表明，通過增加系統(tǒng)資源，系統(tǒng)能處理更大規(guī)模的問題。數(shù)據(jù)庫大小與可擴(kuò)展性每秒處理事務(wù)數(shù)與可擴(kuò)展性22.3并行查詢處理多個(gè)查詢并行執(zhí)行單個(gè)查詢并行執(zhí)行

（1）并行處理多個(gè)操作----查詢的執(zhí)行計(jì)劃可用關(guān)系代樹表達(dá)式樹表示，其中操作都可并行執(zhí)行（2）并行處理單個(gè)操作----查詢計(jì)劃中的單個(gè)操作也能夠并行處理22.3并行查詢處理流水線并行技術(shù)——并行處理多個(gè)操作。當(dāng)一個(gè)操作需要另一個(gè)操作的輸出數(shù)據(jù)時(shí)，即在產(chǎn)生部分操作輸出數(shù)據(jù)的同時(shí)立即進(jìn)行隨后的操作。阻塞操作——如果一個(gè)操作必須在得到所有輸入數(shù)據(jù)后才能產(chǎn)生輸出數(shù)據(jù)，該操作稱為阻塞操作。阻塞操作不能用流水線技術(shù)?；跀?shù)據(jù)劃分的并行處理——對(duì)查詢計(jì)劃的單個(gè)操作的并行處理。首先對(duì)并行操作所需要的數(shù)據(jù)進(jìn)行劃分，然后并行地處理每個(gè)分片，最后再將結(jié)果合并。無共享資源的并行數(shù)據(jù)庫的查詢處理都使用基于數(shù)據(jù)劃分的并行查詢處理方法。22.3.1數(shù)據(jù)劃分將大數(shù)據(jù)集水平劃分到多個(gè)磁盤上，可以通過并行讀寫有效地利用多磁盤的I/O帶寬。將關(guān)系水平劃分方法：（1）輪轉(zhuǎn)劃分法——如果系統(tǒng)有n個(gè)cpu，將第i條記錄劃分到第imodn處理器的方法稱為輪轉(zhuǎn)劃分方法。（2）哈希劃分法——使用特定的哈希函數(shù)，作用于選定的屬性，將記錄劃分到不同的處理機(jī)。（3）區(qū)域劃分法——首先對(duì)記錄進(jìn)行排序，然后按照排序碼將其劃分成n個(gè)區(qū)域，使每個(gè)區(qū)域中近似含有相同數(shù)目的記錄，處于第i個(gè)區(qū)域的記錄分布于處理機(jī)i。22.3.1數(shù)據(jù)劃分優(yōu)勢(shì)劣勢(shì)：（1）輪轉(zhuǎn)法可有效應(yīng)用于需要訪問整個(gè)關(guān)系的查詢處理，當(dāng)需要訪問部分記錄時(shí)，哈希法和區(qū)域法更優(yōu)。（2）區(qū)域法可能會(huì)導(dǎo)致數(shù)據(jù)偏斜，也就是不同分片含有的記錄數(shù)目差別很大。數(shù)據(jù)偏斜會(huì)造成存有大片數(shù)據(jù)分片的處理機(jī)的性能瓶頸問題。（3）哈希法優(yōu)點(diǎn)是：即使數(shù)據(jù)隨時(shí)間增加或減少，也能保持均勻分布。22.3.2并行化順序數(shù)據(jù)操作處理程序并行DBMS軟件結(jié)構(gòu)能夠?qū)F(xiàn)有的關(guān)系操作順序處理程序快速并行化。該方法的基本思想——使用并行數(shù)據(jù)流技術(shù)數(shù)據(jù)流（來自不同的磁盤或者其它操作的輸出）在需要時(shí)進(jìn)行歸并以產(chǎn)生關(guān)系操作的輸入，并且在必要時(shí)進(jìn)行分裂以便于隨后的并行處理。一個(gè)并行查詢處理計(jì)劃是關(guān)系操作以及歸并和分裂操作共同組成的數(shù)據(jù)流網(wǎng)絡(luò)。

Split- Merge 實(shí)現(xiàn)并行查詢技術(shù)22.4數(shù)據(jù)操作的并行化假設(shè)：（1）無共享資源的并行結(jié)構(gòu)（2）關(guān)系都水平劃分到若干磁盤上分布式DBMS的數(shù)據(jù)存儲(chǔ)水平劃分——每個(gè)分片是原始關(guān)系所有數(shù)據(jù)行的子集合垂直劃分——每個(gè)分片是原始關(guān)系所有數(shù)據(jù)列的子集合Idnameaddressagephone123…22.4.1掃描A．讀一個(gè)關(guān)系R的整個(gè)內(nèi)容B．僅讀出R中滿足謂詞的元組定位R中基本元組的方法：a.表掃描

b.索引掃描掃描并行化——如果關(guān)系被劃分到若干磁盤上，可以首先按頁并行讀入，然后歸并得到所需的記錄。2.4.2排序簡(jiǎn)單方法：每個(gè)cpu先對(duì)本地磁盤上的記錄進(jìn)行排序，然后歸并有序記錄集合，并行程度受歸并階段的影響。2.4.2排序更好方法：a.用區(qū)域劃分法先將關(guān)系的所有記錄重新分布再進(jìn)行排序。例：employee按屬性salary排序，salary的取值范圍從10~210，處理機(jī)數(shù)目2010~20的所有記錄分布于處理機(jī)121~30……………2

……

……200~210…………20b.每個(gè)cpu使用排序算法對(duì)分配給它的記錄排序。每個(gè)處理機(jī)得到分配給它的所有記錄的有序序列。

c.通過按照區(qū)域劃分的對(duì)應(yīng)次序訪問處理機(jī)得到完整的有序關(guān)系。難點(diǎn)：如何進(jìn)行區(qū)域劃分來使得每個(gè)處理機(jī)分布的記錄數(shù)目近似相等。否則，對(duì)具有大量記錄的處理機(jī)排序時(shí)將產(chǎn)生性能瓶頸，從而限制并行排序的可擴(kuò)展性。2.4.3連接假設(shè)：對(duì)關(guān)系A(chǔ)和B進(jìn)行劃分時(shí)，連接屬性為age，關(guān)系初始分布在若干磁盤上，但不是基于連接屬性分布的。方法：對(duì)關(guān)系A(chǔ)和B重新劃分：把連接屬性age的取值分成k個(gè)區(qū)域假設(shè)10個(gè)處理機(jī)，age取值范圍0~100

記錄按照相應(yīng)的age值進(jìn)行分布

0<=age<10處理機(jī)1

10<=age<20處理機(jī)2

……

……90<=age<100處理機(jī)10缺點(diǎn)：產(chǎn)生由對(duì)數(shù)據(jù)偏斜不同分片的記錄數(shù)目差別很大并行連接操作的數(shù)據(jù)流網(wǎng)絡(luò)合并

Ai分離分離分離合并分離合并合并掃描掃描掃描掃描A’B’AB

A”B”A連接連接

Ai∞BiAj∞BjAiAiAiAjAjAjAjBiBiBiBiBjBjBjBjB存儲(chǔ)關(guān)系A(chǔ)與B的處理機(jī)處理連接的處理機(jī)并行連接操作的數(shù)據(jù)流網(wǎng)絡(luò)（1）掃描A劃分AAi 0<=age<50Aj 50<=age<100

掃描B劃分BBi0<=age<50Bj50<=age<100

（2）將第i個(gè)分片的記錄發(fā)給處理機(jī)i（3）歸并——?dú)w并所有來自A（B）的記錄（4）每個(gè)處理機(jī)將分配給它的A和B的記錄進(jìn)行連接（5）歸并22.6分布式數(shù)據(jù)庫簡(jiǎn)介分布式數(shù)據(jù)庫——數(shù)據(jù)分布存儲(chǔ)于若干個(gè)場(chǎng)地上，每個(gè)場(chǎng)地都由獨(dú)立運(yùn)行的DBMS進(jìn)行數(shù)據(jù)管理。分布式數(shù)據(jù)庫系統(tǒng)的特點(diǎn)：

(1)分布數(shù)據(jù)的獨(dú)立性：用戶無需提供關(guān)系或關(guān)系副本的存儲(chǔ)地點(diǎn)，就可以對(duì)數(shù)據(jù)進(jìn)行查詢。

(2)分布式事物的原子性：用戶可以提交事物訪問或者修改若干個(gè)場(chǎng)地上的數(shù)據(jù)，涉及多個(gè)場(chǎng)地的事物具有原子性。分布式數(shù)據(jù)庫系統(tǒng)的類型同步分布式數(shù)據(jù)庫系統(tǒng)——數(shù)據(jù)分布在各個(gè)場(chǎng)地，但各場(chǎng)地上運(yùn)行相同的DBMS。異步分布式數(shù)據(jù)庫系統(tǒng)（多數(shù)據(jù)庫系統(tǒng)）——數(shù)據(jù)分布在各個(gè)場(chǎng)地，不同場(chǎng)地運(yùn)行不同的DBMS。22.7分布式DBMS體系結(jié)構(gòu)（1）客戶/服務(wù)器（2）協(xié)同服務(wù)器（3）中間件22.71客戶/服務(wù)器系統(tǒng)客戶/服務(wù)器系統(tǒng)——每個(gè)都能夠處理本地事務(wù)，擁有一個(gè)或多個(gè)客戶進(jìn)程，一個(gè)或多個(gè)服務(wù)器進(jìn)程，并且客戶進(jìn)程可以向任一服務(wù)器進(jìn)程提交查詢?？蛻暨M(jìn)程負(fù)責(zé)和用戶進(jìn)行交互，服務(wù)器進(jìn)程負(fù)責(zé)管理數(shù)據(jù)并進(jìn)行事物處理。客戶進(jìn)程可運(yùn)行在個(gè)人計(jì)算機(jī)上，將查詢提交給大型主機(jī)上的服務(wù)器進(jìn)程執(zhí)行。缺點(diǎn)：不能處理涉及多個(gè)服務(wù)器的單個(gè)查詢，因此客戶進(jìn)程必須將查詢分解成合適的子查詢，分別在不同場(chǎng)地執(zhí)行，然后將各個(gè)子查詢的結(jié)果組合起來得到最終查詢結(jié)果?？蛻暨M(jìn)程將變得非常復(fù)雜。22.72協(xié)同服務(wù)器系統(tǒng)中的數(shù)據(jù)庫服務(wù)器，每個(gè)都能夠處理本地事務(wù)，并能協(xié)同執(zhí)行涉及多個(gè)服務(wù)器的事務(wù)。當(dāng)服務(wù)器收到的查詢需要訪問其它服務(wù)器的數(shù)據(jù)時(shí)，將產(chǎn)生合適的子查詢，提交給其它服務(wù)器，得到結(jié)果組合產(chǎn)生原始查詢的最終結(jié)果。22.7.3中間件系統(tǒng)中間件系統(tǒng)允許提交涉及多個(gè)服務(wù)器的單個(gè)查詢，并且數(shù)據(jù)庫服務(wù)器不需要都具有多場(chǎng)地查詢執(zhí)行能力。該方法對(duì)于集成很難擴(kuò)展的若干遺留系統(tǒng)非常有效?；旧?，只需要一個(gè)服務(wù)器有能力處理涉及多個(gè)服務(wù)器的查詢或者事物就可以了，其余的服務(wù)器只需要處理本地的查詢和事物。中間件——將協(xié)同執(zhí)行涉及多服務(wù)器的查詢或事物的特殊服務(wù)器看成一個(gè)軟件層。中間件本身并不維護(hù)數(shù)據(jù)，但能夠?qū)碜云渌?wù)器的數(shù)據(jù)進(jìn)行連接和其他關(guān)系操作。22.8分布式DBMS的數(shù)據(jù)存儲(chǔ)分布式DBMS，關(guān)系可以存儲(chǔ)于若干場(chǎng)地。將經(jīng)常使用的數(shù)據(jù)存儲(chǔ)于本地，并且將使用頻率較高的關(guān)系數(shù)據(jù)復(fù)制存儲(chǔ)于每個(gè)場(chǎng)地。22.8.1劃分劃分——將關(guān)系分離成若干個(gè)小關(guān)系或者分片，每個(gè)分片存儲(chǔ)于不同場(chǎng)地。（1）水平劃分——每個(gè)分片是原始關(guān)系所有數(shù)據(jù)行的子集合。（2）垂直劃分——每個(gè)分片是原始關(guān)系所有數(shù)據(jù)列的子集合。22.8.1劃分Idnamecityagesal001JonesMadra233000002SmithChicago254500003MaryChicago195000004JakcBombay358000005MadaBombay469800垂直劃分——可用π得到.πid，name水平劃分——可以用σ得到例：來自同一個(gè)城市的雇員位于一個(gè)分片將Chicago數(shù)據(jù)存儲(chǔ)于場(chǎng)地Chicago。相當(dāng)多的查詢是本地查詢22.8.2復(fù)制復(fù)制——同時(shí)存儲(chǔ)關(guān)系或者關(guān)系分片的若干個(gè)版本。一個(gè)完整的關(guān)系可以在一個(gè)或多個(gè)場(chǎng)地進(jìn)行復(fù)制與存儲(chǔ)。同樣，關(guān)系分片也可以復(fù)制存儲(chǔ)于若干場(chǎng)地。例：關(guān)系劃分成R1，R2，R3三個(gè)分片，可以只存儲(chǔ)R1的一個(gè)副本，復(fù)制存儲(chǔ)R2的多個(gè)副本，在所有場(chǎng)地復(fù)制存儲(chǔ)R3的副本。復(fù)制的作用：增加數(shù)據(jù)的可用性：當(dāng)存儲(chǔ)數(shù)據(jù)的某個(gè)場(chǎng)地的系統(tǒng)發(fā)生故障時(shí)，可以在其他場(chǎng)地找到數(shù)據(jù)?？焖俚牟樵兲幚恚菏褂帽镜馗北敬嬖L問遠(yuǎn)程數(shù)據(jù)，減少了訪問遠(yuǎn)程場(chǎng)地的數(shù)據(jù)將導(dǎo)致額外的傳輸代價(jià)，能加快查詢的執(zhí)行速度。22.9分布式目錄管理跟蹤分布到多個(gè)場(chǎng)地的數(shù)據(jù)，保存關(guān)系進(jìn)行劃分以及進(jìn)行復(fù)制的信息，即關(guān)系分片如何分布到若干個(gè)場(chǎng)地以及分片副本存儲(chǔ)在哪里。22.9.1命名對(duì)象關(guān)系進(jìn)行了劃分和復(fù)制后，要對(duì)之命名以唯一地識(shí)別每個(gè)分片的每個(gè)副本。<load-name,birth-site>本地名（load-name），關(guān)系所在場(chǎng)地生成的名字。同一場(chǎng)地兩個(gè)對(duì)象不能同名。產(chǎn)生場(chǎng)地名（birth-site），用于標(biāo)識(shí)關(guān)系產(chǎn)生的場(chǎng)地，以及對(duì)關(guān)系的所有分片和副本的信息進(jìn)行維護(hù)的場(chǎng)地。22.9.2目錄結(jié)構(gòu)場(chǎng)地目錄：描述該場(chǎng)地存儲(chǔ)的所有分片和副本本場(chǎng)地產(chǎn)生的關(guān)系的副本的分布情況22.10分布式查詢處理Sailors（sid:integer,sname:string,rating:integer,age:real）Reserves(sid:integer,bid:integer,day:date,rname:string)SELECTAVG(S.age)FROMSailorsSWHERES.rating>3ANDS.rating<722.10.1分布式DBMS中無連接的查詢Sailors水平劃分：rating<5存在shanhai>=5存在Tokyo——必須在兩個(gè)場(chǎng)地分別計(jì)算SUM（age），COUNIT（age）（記錄數(shù)）再利用上述信息計(jì)算AVG（age）——如果WHERE子句只有一個(gè)條件S.rating>6,只需在一個(gè)場(chǎng)地Tokyo查詢處理Sailors垂直劃分：場(chǎng)地shanghai存儲(chǔ)sid和rating場(chǎng)地Tokyo存儲(chǔ)sanme和age

有損分解兩個(gè)字段無公共字段兩個(gè)分片加額外標(biāo)識(shí)字段（id）存儲(chǔ)于兩個(gè)場(chǎng)地，才能合并兩個(gè)分片得到原關(guān)系。22.10.1分布式DBMS中無連接的查詢Sailors同時(shí)存儲(chǔ)于場(chǎng)地shanghai和Tokyo選擇哪個(gè)場(chǎng)地進(jìn)行查詢？取決于：將查詢結(jié)果傳輸?shù)讲樵兲峤粓?chǎng)地的代價(jià)在場(chǎng)地shanghai或Tokyo執(zhí)行查詢的代價(jià)22.10.2分布式DBMS中的連接操作LONDONPARISSailorsReserves每條記錄50字節(jié)每頁存80條記錄總共有500頁每條記錄40字節(jié)每頁有100條記錄總共有1000頁記錄D——從磁盤讀?。▽懀╉摂?shù)據(jù)所需的時(shí)間

S——傳輸一頁數(shù)據(jù)（從一個(gè)場(chǎng)地到另一個(gè)場(chǎng)地）所需的時(shí)間不同執(zhí)行策略：（1）需要時(shí)取得數(shù)據(jù)（2）傳輸?shù)揭粋€(gè)場(chǎng)地（3）半連接和布魯連接不同執(zhí)行策略的執(zhí)行代價(jià)：（1）需要時(shí)取得數(shù)據(jù)在場(chǎng)地London做基于頁的嵌套循環(huán)連接，Sailors作為外關(guān)系，則對(duì)于Sailors的每頁數(shù)據(jù)，都需要從場(chǎng)地Paris得到Reserves的所有數(shù)據(jù)，并進(jìn)行連接。代價(jià)：500D+500*1000（D+S）如果查詢不是在場(chǎng)地London提交的，查詢的處理代價(jià)還需要加上將查詢結(jié)果傳輸?shù)讲樵兲峤粓?chǎng)地的傳輸代價(jià)，這個(gè)取決于查詢結(jié)果的大小。如果查詢場(chǎng)地不再London也不在Paris，傳輸查詢結(jié)果的代價(jià)將大于將關(guān)系Sailors和Reserves都傳到查詢場(chǎng)地的代價(jià)。所以應(yīng)將兩個(gè)關(guān)系傳輸?shù)讲樵儓?chǎng)地，再執(zhí)行連接操作?？梢栽趫?chǎng)地London使用索引嵌套循環(huán)連接方法，對(duì)于關(guān)系Sailors的每條記錄，只訪問關(guān)系Reserves中合適的記錄。對(duì)關(guān)系Reserves建立基于屬性sid哈希索引。都需要從遠(yuǎn)程場(chǎng)地取得數(shù)據(jù)，傳輸代價(jià)所占比重大。不同執(zhí)行策略的執(zhí)行代價(jià)：（2）傳輸?shù)揭粋€(gè)場(chǎng)地可將Sailors從London傳到Paris，然后在Paris執(zhí)行連接。500（2D+S）+4500D可將Reservs從Paris傳到London，連接

1000（2D+S）+4500D將兩個(gè)關(guān)系都傳到查詢提交的場(chǎng)地，在那里連接不同執(zhí)行策略的執(zhí)行代價(jià)（3）半連接和布魯連接例：將Reserves傳到London并連接實(shí)際上Reserves的部分記錄并不能和Sailors的記錄進(jìn)行連接，事先確定哪些記錄和Sailors不能進(jìn)行連接，可避免傳輸這些記錄，從而可減少傳輸Reserves記錄的數(shù)目。半連接：（1）在場(chǎng)地London對(duì)關(guān)系Sailors進(jìn)行投影得到連接字段sid，將結(jié)果傳到場(chǎng)地Paris（2）在場(chǎng)地Paris，將London傳來的投影結(jié)果和關(guān)系Peserves進(jìn)行自然連接。連接的結(jié)果就稱為Reserves的一個(gè)基于關(guān)系Sailors的約減。只有約減的Reserves記錄能和Sailors的記錄進(jìn)行連接。所以約減后的Reserves傳輸?shù)綀?chǎng)地London（3）在場(chǎng)地London，對(duì)約減后的Reserves和Sailors進(jìn)行連接代價(jià)：200S+6500D半連接的傳輸代價(jià)小，但總代價(jià)可能比傳輸整個(gè)關(guān)系要大布魯連接（1）傳送位向量，不是Sailors的投影。位向量長(zhǎng)度為k，關(guān)系Sailors的每條記錄（使用屬性sid）通過哈希函數(shù)映射到區(qū)域0~k-1，如果記錄的哈希值為i，則向量的第i位設(shè)為1，否則為0。（2）對(duì)關(guān)系Reserves進(jìn)行約減時(shí)，使用相同的哈希函數(shù)將Reserves的每個(gè)記錄（使用屬性sid）映射到區(qū)域0~k-1，對(duì)于哈希值為i的記錄，如果向量的第i位值為0，表示沒有哈希值為i的Sailors記錄，即沒有Sailors可進(jìn)行連接，忽略該Reserves中的記錄。SailorsReservessid：sid：h（sid）=1，2……k-101234k-101100……1*位向量傳輸代價(jià)低，更有效。22.11分布式數(shù)據(jù)的更新同步復(fù)制——在更新事物提交時(shí)，同步更新數(shù)據(jù)的所有副本異步復(fù)制——關(guān)系的副本只需要定期更新;

因此一個(gè)事物讀取每個(gè)關(guān)系的不同副本結(jié)果可能不同異步復(fù)制危害了分布數(shù)據(jù)的獨(dú)立性，但比同步復(fù)制能更有效地實(shí)現(xiàn)。22.11.1同步復(fù)制1）投票技術(shù)——事物在修改每個(gè)對(duì)象時(shí)寫該對(duì)象的大多數(shù)副本，并且在讀時(shí)要讀足夠數(shù)量的副本來保證其中之一為當(dāng)前副本例：總共有10個(gè)副本，更新事物寫了其中7個(gè)副本，那么至少應(yīng)該讀4個(gè)副本。*很多應(yīng)用中，讀數(shù)據(jù)比更新數(shù)據(jù)頻繁，所以應(yīng)提高了讀的性能，所以此技術(shù)沒吸引力2）讀任意寫全部技術(shù)——事物可以讀對(duì)象的任一個(gè)副本，但寫時(shí)需要所有副本。和投票比較：讀的速度快，寫的速度慢讀操作比寫頻繁時(shí)，此技術(shù)有吸引力。通常情況使用此技術(shù)來實(shí)現(xiàn)同步復(fù)制。22.11.2異步復(fù)制