云計(jì)算關(guān)鍵技術(shù).ppt

1、云計(jì)算關(guān)鍵技術(shù),鄭偉平 2011-7-26,Page 2,虛擬化技術(shù)內(nèi)容,1 虛擬化定義 2 虛擬化分類 3 全虛擬化與半虛擬化 4虛擬化實(shí)現(xiàn) 5虛擬化技術(shù)比較與選型 6虛擬化帶來(lái)的好處 7虛擬化帶來(lái)的問(wèn)題 8虛擬化適用范圍 9服務(wù)器虛擬化過(guò)程,MapReduce MapReduce是一個(gè)簡(jiǎn)單易用的并行編程模型，它極大簡(jiǎn)化了大規(guī)模數(shù)據(jù)處理問(wèn)題的實(shí)現(xiàn),Page 3,Divide and Conquer,“Work”,w1,w2,w3,r1,r2,r3,“Result”,“worker”,“worker”,“worker”,Partition,Combine,Parallelization Cha

2、llenges,How do we assign work units to workers? What if we have more work units than workers? What if workers need to share partial results? How do we aggregate partial results? How do we know all the workers have finished? What if workers die?,What is the common theme of all of these problems?,Comm

3、on Theme?,Parallelization problems arise from: Communication between workers (e.g., to exchange state) Access to shared resources (e.g., data) Thus, we need a synchronization mechanism,Managing Multiple Workers,Difficult because We dont know the order in which workers run We dont know when workers i

4、nterrupt each other We dont know the order in which workers access shared data Thus, we need: Semaphores (lock, unlock) Conditional variables (wait, notify, broadcast) Barriers Still, lots of problems: Deadlock, livelock, race conditions. Dining philosophers, sleepy barbers, cigarette smokers. Moral

5、 of the story: be careful!,Current Tools,Programming models Shared memory (pthreads) Message passing (MPI) Design Patterns Master-slaves Producer-consumer flows Shared work queues,But , now Mapreduce!,Mapreduce: Parallel/Distributed Computing Programming Model,Input split,shuffle,output,Typical prob

6、lem solved by MapReduce,讀入數(shù)據(jù): key/value 對(duì)的記錄格式數(shù)據(jù) Map: 從每個(gè)記錄里extract something map (in_key, in_value) - list(out_key, intermediate_value) 處理input key/value pair 輸出中間結(jié)果key/value pairs Shuffle: 混排交換數(shù)據(jù) 把相同key的中間結(jié)果匯集到相同節(jié)點(diǎn)上 Reduce: aggregate, summarize, filter, etc. reduce (out_key, list(intermediate_valu

7、e) - list(out_value) 歸并某一個(gè)key的所有values，進(jìn)行計(jì)算 輸出合并的計(jì)算結(jié)果 (usually just one) 輸出結(jié)果,Mapreduce Framework,Mapreduce Framework,Shuffle Implementation,Partition and Sort Group,Partition function: hash(key)%reducer number Group function: sort by key,Example uses:,Model is Widely ApplicableMapReduce Programs In

8、 Google Source Tree,Google MapReduce Architecture,MapReduce Operation,Initial data split into 64MB blocks,Computed, resultslocally stored,M sends datalocation to R workers,Final output written,Master informed ofresult locations,Execution overview,1. Input files are split into M pieces (16 to 64 MB)

9、Many worker copies of the program are forked. 2. One special copy, the master, assigns map and reduce tasks to idle slave workers 3. Map workers read input splits, parse (key,value) pairs, apply the map function, create buffered output pairs. 4. Buffered output pairs are periodically written to loca

10、l disk, partitioned into R regions, locations of regions are passed back to the master. 5. Master notifies reduce worker about locations. Worker uses remote procedure calls to read data from local disks of the map workers, sorts by intermediate keys to group same key records together.,Execution over

11、view cont,6. Reduce worker passes key plus corresponding set of all intermediate data to reduce function. The output of the reduce function is appended to the final output file. 7. When all map and reduce tasks are completed the master wakes up the user program, which resumes the user code.,Fault To

12、lerance: workers,master保持一些數(shù)據(jù)結(jié)構(gòu)。它為每個(gè)map和reduce任務(wù)存儲(chǔ)它們的狀態(tài)(空閑，工作中，完成)，和worker機(jī)器(非空閑任務(wù)的機(jī)器)的標(biāo)識(shí)。 Master pings workers periodically. No response: worker marked as failed. Completed map tasks are reset to idle state, so that they can be restarted, because their results (local to failed worker) are lost. Com

13、pleted reduce tasks do not need to be re-started (output stored in global file system). Reduce tasks are notified of the new map tasks, so they can read unread data from the new locations.,Fault Tolerance: Master,Master writes checkpoints Only one master, less chance of failure If master failes, Map

14、Reduce task aborts.,Refinement: Redundant Execution,Slow workers significantly delay completion time Other jobs consuming resources on machine Bad disks w/ soft errors transfer data slowly Solution: Near end of phase, spawn backup tasks Whichever one finishes first wins Dramatically shortens job com

15、pletion time,Refinement: Locality Optimization,Master scheduling policy: Asks GFS for locations of replicas of input file blocks Map tasks typically split into 64MB (GFS block size) Map tasks scheduled so GFS input block replica are on same machine or same rack Effect Thousands of machines read inpu

16、t at local disk speed Without this, rack switches limit read rate,Refinement: Skipping Bad Records,Map/Reduce functions sometimes fail for particular inputs Best solution is to debug & fix Not always possible third-party source libraries On segmentation fault: Send UDP packet to master from signal h

17、andler Include sequence number of record being processed If master sees two failures for same record: Next worker is told to skip the record,Compression of intermediate data Combiner “Combiner” functions can run on same machine as a mapper Causes a mini-reduce phase to occur before the real reduce p

18、hase, to save bandwidth Local execution for debugging/testing User-defined counters,Other Refinements,Hadoop MapReduce Architecture,Master/Worker Model Load-balancing by polling mechanism,History of Hadoop,2004 - Initial versions of what is now Hadoop Distributed File System and Map-Reduce implement

19、ed by Doug Cutting & Mike Cafarella December 2005 - Nutch ported to the new framework. Hadoop runs reliably on 20 nodes. January 2006 - Doug Cutting joins Yahoo! February 2006 - Apache Hadoop project official started to support the standalone development of Map-Reduce and HDFS. March 2006 - Formatio

20、n of the Yahoo! Hadoop team May 2006 - Yahoo sets up a Hadoop research cluster - 300 nodes April 2006 - Sort benchmark run on 188 nodes in 47.9 hours May 2006 - Sort benchmark run on 500 nodes in 42 hours (better hardware than April benchmark) October 2006 - Research cluster reaches 600 Nodes Decemb

21、er 2006 - Sort times 20 nodes in 1.8 hrs, 100 nodes in 3.3 hrs, 500 nodes in 5.2 hrs, 900 nodes in 7.8 January 2006 - Research cluster reaches 900 node April 2007 - Research clusters - 2 clusters of 1000 nodes Sep 2008 - Scaling Hadoop to 4000 nodes at Yahoo! April 2009 release 0.20.0, many improvem

22、ents, new features, bug fixes and optimizations.,分布式文件系統(tǒng),分布式文件系統(tǒng) 特點(diǎn)和基本要求 緩存 容錯(cuò)和可擴(kuò)展性,Page 28,29,2020/9/24,分布式文件系統(tǒng)的特點(diǎn)和基本要求,分布式文件系統(tǒng)的特點(diǎn) 為整個(gè)網(wǎng)絡(luò)上的文件系統(tǒng)資源提供了一個(gè)邏輯樹(shù)結(jié)構(gòu)，用戶可以拋開(kāi)文件的實(shí)際物理位置，僅通過(guò)一定的邏輯關(guān)系就可以查找和訪問(wèn)網(wǎng)絡(luò)的共享資源。用戶能夠像訪問(wèn)本地文件一樣，訪問(wèn)分布在網(wǎng)絡(luò)中多個(gè)服務(wù)器上的文件。 分布式文件系統(tǒng)的顧客、服務(wù)員和存儲(chǔ)設(shè)備分散在各機(jī)器上，服務(wù)活動(dòng)必須跨網(wǎng)完成。 存儲(chǔ)設(shè)備不是單一的集中數(shù)據(jù)存儲(chǔ)器。 分布式文件系統(tǒng)的具體配置

23、和實(shí)現(xiàn)可以有很大的不同，有的服務(wù)員運(yùn)行在專用的服務(wù)器上，有的機(jī)器既是服務(wù)員又是顧客。,30,2020/9/24,分布式文件系統(tǒng)的特點(diǎn)和基本要求,分布式文件系統(tǒng)的基本要求 透明性 位置透明性：服務(wù)員和存儲(chǔ)器的多重性和分散性對(duì)顧客透明。 移動(dòng)透明性：用戶意識(shí)不到資源的移動(dòng)。 性能透明性：當(dāng)服務(wù)負(fù)載在一定范圍內(nèi)變化時(shí)，客戶程序可以保持滿意的性能。 擴(kuò)展透明性：文件服務(wù)可以擴(kuò)充，以滿足負(fù)載和網(wǎng)絡(luò)規(guī)模的增長(zhǎng)。 性能分布式文件系統(tǒng)比常規(guī)文件系統(tǒng)類似（有時(shí)更好）的性能和可靠性,31,2020/9/24,容錯(cuò) 為了處理暫時(shí)的通信錯(cuò)誤，容錯(cuò)設(shè)計(jì)可以基于最多一次性語(yǔ)義 無(wú)狀態(tài)的服務(wù)器: 崩潰重啟時(shí)不需恢復(fù) 安全性

24、 身份驗(yàn)證，訪問(wèn)控制，安全通道 效率：應(yīng)提供比傳統(tǒng)文件系統(tǒng)相同或更強(qiáng)的性能和可靠性,分布式文件系統(tǒng)的特點(diǎn)和基本要求,32,2020/9/24,分布式文件系統(tǒng)的緩存,緩存方案的設(shè)計(jì)需要考慮的問(wèn)題： 緩存的單位問(wèn)題 存儲(chǔ)部分文件的位置 如何決定各個(gè)顧客緩存中的數(shù)據(jù)是否一致,33,2020/9/24,分布式文件系統(tǒng)的緩存,緩存的粒度和地點(diǎn) 緩存的粒度：如果數(shù)據(jù)單元(即粒度)愈大，則下次訪問(wèn)的數(shù)據(jù)在顧客方的本地找到的可能性愈大，但傳送數(shù)據(jù)的時(shí)間和一致性問(wèn)題也增加了。反之，粒度太小，通信的開(kāi)銷也隨之增加。 緩存的地點(diǎn)在一個(gè)各自有主存和磁盤(pán)的客戶-服務(wù)器系統(tǒng)中，有四個(gè)地方可以用來(lái)存儲(chǔ)文件或存儲(chǔ)部分文件：服

25、務(wù)器磁盤(pán)、服務(wù)器主存、客戶磁盤(pán)（如果可用的話）或者客戶主存。,34,2020/9/24,分布式文件系統(tǒng)的緩存,更新策略、緩存有效性檢驗(yàn)和一致性 判定本地緩存的數(shù)據(jù)副本是否與原本一致，有兩個(gè)基本方法驗(yàn)證其有效性： 顧客發(fā)動(dòng)的方法。顧客與服務(wù)員聯(lián)系，檢查本地?cái)?shù)據(jù)與原本是否一致。這個(gè)方法的關(guān)鍵是有效性檢驗(yàn)的頻度。 服務(wù)員發(fā)動(dòng)的方法。服務(wù)員為每個(gè)顧客登記被該顧客緩存的文件或文件的某個(gè)部分。當(dāng)服務(wù)員檢測(cè)出可能不一致時(shí)，必須做出反應(yīng)。服務(wù)員發(fā)動(dòng)方法的一個(gè)問(wèn)題是違背顧客/服務(wù)員模型,35,2020/9/24,容錯(cuò)和可擴(kuò)充性,可用性與文件復(fù)制 可恢復(fù)性：當(dāng)對(duì)某個(gè)文件的操作失敗，或由顧客夭折此操作時(shí)，如果文件能

26、轉(zhuǎn)換到原來(lái)的一致?tīng)顟B(tài)，則說(shuō)此文件是可恢復(fù)的。 堅(jiān)定性：如果當(dāng)某個(gè)存儲(chǔ)器崩潰和存儲(chǔ)介質(zhì)損壞時(shí)某個(gè)文件能保證完好，則說(shuō)此文件是堅(jiān)定的。 可用性：如果無(wú)論何時(shí)一旦需要就可訪問(wèn)，甚至在某個(gè)機(jī)器和存儲(chǔ)器崩潰，或者在發(fā)生通信失效的情況下，某個(gè)文件仍然可被訪問(wèn)，則這種文件叫做是可用的。,36,2020/9/24,容錯(cuò)和可擴(kuò)充性,可用性與文件復(fù)制 文件復(fù)制：文件復(fù)制是一個(gè)冗余措施。這里指的是不同機(jī)器上的文件復(fù)制，而不是同一機(jī)器上不同介質(zhì)上的文件復(fù)制(如鏡像磁盤(pán))。 文件復(fù)制的原因 通過(guò)對(duì)每個(gè)文件的獨(dú)立備份來(lái)增加系統(tǒng)的可靠性。 當(dāng)一個(gè)文件服務(wù)器出現(xiàn)問(wèn)題時(shí)，仍允許進(jìn)行文件訪問(wèn)； 將工作量分配到多個(gè)服務(wù)器上，避免運(yùn)

27、行性能上的瓶頸。,37,2020/9/24,容錯(cuò)和可擴(kuò)充性,可用性與文件復(fù)制 用戶需要了解文件復(fù)制到何種程度嗎？在文件復(fù)制進(jìn)程中需要達(dá)到什么要求呢？ 文件復(fù)制的要求： 應(yīng)對(duì)用戶隱匿復(fù)制細(xì)節(jié)。把一份復(fù)制件名字變換成指定的復(fù)制件是命名方案的任務(wù)。 與復(fù)制件有關(guān)的主要問(wèn)題是它們的更新。從用戶觀點(diǎn)看，文件的所有復(fù)制品代表同一邏輯實(shí)體，所以對(duì)任何復(fù)制件的更新必須反映到所有其他復(fù)制件。 大多數(shù)情況下，不能放棄文件數(shù)據(jù)的一致性，因此使用復(fù)制來(lái)增加可用性時(shí)還要使用復(fù)雜的更新傳播協(xié)議。,38,2020/9/24,容錯(cuò)和可擴(kuò)充性,可擴(kuò)充性 設(shè)計(jì)大規(guī)模系統(tǒng)要考慮的問(wèn)題： 首先是有界資源(bounded resour

28、ces)原理：“從系統(tǒng)的任何部分來(lái)的服務(wù)要求應(yīng)該限于一個(gè)常數(shù)，此常數(shù)和系統(tǒng)中的節(jié)點(diǎn)數(shù)無(wú)關(guān)”。負(fù)載和系統(tǒng)規(guī)模成比例的任何服務(wù)員，一旦系統(tǒng)擴(kuò)充到超過(guò)某一范圍則必然阻塞，再增加資源也緩解不了這個(gè)問(wèn)題。 廣播是一種使網(wǎng)絡(luò)中的每個(gè)機(jī)器都參加的活動(dòng)。在廣播基礎(chǔ)上建立的機(jī)構(gòu)對(duì)超大型系統(tǒng)很明顯不實(shí)際。 網(wǎng)絡(luò)擁擠和延遲是大規(guī)模系統(tǒng)的主要障礙。使用緩存和實(shí)施放松的共享語(yǔ)義，使跨機(jī)器的交互作用最少。,39,2020/9/24,容錯(cuò)和可擴(kuò)充性,可擴(kuò)充性 設(shè)計(jì)大規(guī)模系統(tǒng)要考慮的問(wèn)題： 不應(yīng)當(dāng)使用集中控制方案和集中的資源建立可擴(kuò)充的和容錯(cuò)的系統(tǒng)。 分散化的一個(gè)重要方面是系統(tǒng)的管理。分配管理職責(zé)時(shí)，應(yīng)有利于自治性和對(duì)稱性，

29、不干擾分布式系統(tǒng)的連貫性和一致性。 將系統(tǒng)劃分為若干半自治的小組。每個(gè)小組包括一些機(jī)器和一個(gè)專用的小組服務(wù)員。為了盡量減少跨越小組的文件訪問(wèn)，大多數(shù)時(shí)間，每個(gè)機(jī)器的請(qǐng)求應(yīng)由其小組服務(wù)員滿足。,HDFS（Hadoop Distributed File System）,Hadoop分布式文件系統(tǒng)(HDFS )被設(shè)計(jì)成適合運(yùn)行在通用硬件(commodity hardware)上的分布式文件系統(tǒng)。 它和現(xiàn)有的分布式文件系統(tǒng)有很多共同點(diǎn)。但同時(shí)，它和其他的分布式文件系統(tǒng)的區(qū)別也是很明顯的。 HDFS是一個(gè)高度容錯(cuò)性的系統(tǒng)，適合部署在廉價(jià)的機(jī)器上。 HDFS能提供高吞吐量的數(shù)據(jù)訪問(wèn)，適合大規(guī)模數(shù)據(jù)集上的應(yīng)

30、用。 HDFS放寬了一部分POSIX約束，來(lái)實(shí)現(xiàn)流式讀取文件系統(tǒng)數(shù)據(jù)的目的。,Page 40,Goals of HDFS,Very Large Distributed File System 10K nodes, 100 million files, 10 PB Assumes Commodity Hardware Files are replicated to handle hardware failure Detect failures and recovers from them Optimized for Batch Processing Data locations exposed

31、so that computations can move to where data resides Provides very high aggregate bandwidth User Space, runs on heterogeneous OS,HDFS采用master/slave架構(gòu)。一個(gè)HDFS集群是由一個(gè)Namenode和一定數(shù)目的Datanodes組成。 Namenode是一個(gè)中心服務(wù)器，負(fù)責(zé)管理文件系統(tǒng)的名字空間(namespace)以及客戶端對(duì)文件的訪問(wèn)。 Namenode執(zhí)行文件系統(tǒng)的名字空間操作，比如打開(kāi)、關(guān)閉、重命名文件或目錄。它也負(fù)責(zé)確定數(shù)據(jù)塊到具體Datanod

32、e節(jié)點(diǎn)的映射。 集群中的Datanode一般是一個(gè)節(jié)點(diǎn)一個(gè)，負(fù)責(zé)管理它所在節(jié)點(diǎn)上的存儲(chǔ)。HDFS暴露了文件系統(tǒng)的名字空間，用戶能夠以文件的形式在上面存儲(chǔ)數(shù)據(jù)。從內(nèi)部看，一個(gè)文件其實(shí)被分成一個(gè)或多個(gè)數(shù)據(jù)塊，這些塊存儲(chǔ)在一組 Datanode上。 Datanode負(fù)責(zé)處理文件系統(tǒng)客戶端的讀寫(xiě)請(qǐng)求。在Namenode的統(tǒng)一調(diào)度下進(jìn)行數(shù)據(jù)塊的創(chuàng)建、刪除和復(fù)制。,Page 43,Distributed File System,Single Namespace for entire cluster Data Coherency Write-once-read-many access model Clien

33、t can only append to existing files Files are broken up into blocks Typically 128 MB block size Each block replicated on multiple DataNodes Intelligent Client Client can find location of blocks Client accesses data directly from DataNode,NameNode Metadata,Meta-data in Memory The entire metadata is i

34、n main memory No demand paging of meta-data Types of Metadata List of files List of Blocks for each file List of DataNodes for each block File attributes, e.g creation time, replication factor A Transaction Log Records file creations, file deletions. Etc Namenode全權(quán)管理數(shù)據(jù)塊的復(fù)制，它周期性地從集群中的每個(gè)Datanode接收心跳信號(hào)

35、和塊狀態(tài)報(bào)告(Blockreport)。 集群中單一Namenode的結(jié)構(gòu)大大簡(jiǎn)化了系統(tǒng)的架構(gòu)。Namenode是所有HDFS元數(shù)據(jù)的仲裁者和管理者，這樣，用戶數(shù)據(jù)永遠(yuǎn)不會(huì)流過(guò) Namenode。,DataNode,A Block Server Stores data in the local file system (e.g. ext3) Stores meta-data of a block (e.g. CRC) Serves data and meta-data to Clients Block Report Periodically sends a report of all exis

36、ting blocks to the NameNode Facilitates Pipelining of Data Forwards data to other specified DataNodes,Block Placement,Current Strategy - One replica on local node - Second replica on a remote rack - Third replica on same remote rack - Additional replicas are randomly placed Clients read from nearest

37、 replica Would like to make this policy pluggable,Page 48,在大多數(shù)情況下，副本系數(shù)是3 HDFS的存放策略是將一個(gè)副本存放在本地機(jī)架的節(jié)點(diǎn)上，一個(gè)副本放在同一機(jī)架的另一個(gè)節(jié)點(diǎn)上，最后一個(gè)副本放在不同機(jī)架的節(jié)點(diǎn)上。 這種策略減少了機(jī)架間的數(shù)據(jù)傳輸，這就提高了寫(xiě)操作的效率。機(jī)架的錯(cuò)誤遠(yuǎn)遠(yuǎn)比節(jié)點(diǎn)的錯(cuò)誤少，所以這個(gè)策略不會(huì)影響到數(shù)據(jù)的可靠性和可用性。于此同時(shí)，因?yàn)閿?shù)據(jù)塊只放在兩個(gè)（不是三個(gè)）不同的機(jī)架上，所以此策略減少了讀取數(shù)據(jù)時(shí)需要的網(wǎng)絡(luò)傳輸總帶寬。在這種策略下，副本并不是均勻分布在不同的機(jī)架上。三分之一的副本在一個(gè)節(jié)點(diǎn)上，三分之二的副本在一

38、個(gè)機(jī)架上，其他副本均勻分布在剩下的機(jī)架中，這一策略在不損害數(shù)據(jù)可靠性和讀取性能的情況下改進(jìn)了寫(xiě)的性能。,Data Correctness,Use Checksums to validate data Use CRC32 File Creation Client computes checksum per 512 byte DataNode stores the checksum File access Client retrieves the data and checksum from DataNode If Validation fails, Client tries other repl

39、icas,NameNode Failure,A single point of failure Transaction Log stored in multiple directories A directory on the local file system A directory on a remote file system (NFS/CIFS),Page 51,HDFS未實(shí)現(xiàn)的功能總結(jié)： 1、 文件追加寫(xiě)入，這個(gè)功能近期內(nèi)不會(huì)實(shí)現(xiàn)，沒(méi)有這個(gè)功能會(huì)引起當(dāng)文件尚未關(guān)閉的時(shí)候，數(shù)據(jù)服務(wù)器死機(jī)或者目錄服務(wù)器死機(jī)，會(huì)引起文件文件丟失，并且不可后續(xù)恢復(fù)寫(xiě)入。 2、 系統(tǒng)快照，一個(gè)全系統(tǒng)的快照功能

40、，如果沒(méi)有這個(gè)功能就不能實(shí)現(xiàn)文件系統(tǒng)的回滾操作。 3、 集群負(fù)載均衡，均衡策略暫時(shí)沒(méi)有實(shí)現(xiàn)，有幾個(gè)策略十分有用，比如在某臺(tái)數(shù)據(jù)機(jī)可能磁盤(pán)過(guò)低的時(shí)候，把該數(shù)據(jù)機(jī)上面的一些數(shù)據(jù)轉(zhuǎn)移到還有很多空間剩余的數(shù)據(jù)機(jī)上；當(dāng)某個(gè)文件突然被大量讀寫(xiě)的時(shí)候，動(dòng)態(tài)增加該文件的冗余因子，并且數(shù)據(jù)塊復(fù)制到更多的數(shù)據(jù)機(jī)上面，以提高讀取性能。 4、 文件系統(tǒng)的用戶權(quán)限，這個(gè)也是近期內(nèi)不會(huì)實(shí)現(xiàn)的了。 5、訪問(wèn)權(quán)限，現(xiàn)在是無(wú)限制訪問(wèn)的，沒(méi)有訪問(wèn)權(quán)限控制。,分布式數(shù)據(jù)庫(kù)技術(shù),定義 特點(diǎn) 分類 體系結(jié)構(gòu) 分片與分布 模式結(jié)構(gòu) 事務(wù)模型,分布式數(shù)據(jù)庫(kù)的定義,分布式數(shù)據(jù)庫(kù)的定義 通俗地說(shuō)是物理上分散而邏輯上集中的數(shù)據(jù)庫(kù)系統(tǒng)。 使用計(jì)算

41、機(jī)網(wǎng)絡(luò)將地理位置分散而管理和控制又需要不同程度集中的多個(gè)邏輯單位連接起來(lái)，共同組成一個(gè)統(tǒng)一的數(shù)據(jù)庫(kù)系統(tǒng)。 可以看作是數(shù)據(jù)處理即數(shù)據(jù)庫(kù)系統(tǒng)和計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)的結(jié)合。,分布式數(shù)據(jù)庫(kù)的特點(diǎn) 物理分布性 邏輯整體性，不同于分散式數(shù)據(jù)庫(kù)，有全局?jǐn)?shù)據(jù)庫(kù)和局部數(shù)據(jù)庫(kù)的概念。 站點(diǎn)自治性：場(chǎng)地自治，各站點(diǎn)數(shù)據(jù)由本地DBMS管理，具有自治處理能力，完成本地應(yīng)用。這一點(diǎn)與多機(jī)系統(tǒng)不同。 數(shù)據(jù)分布透明性：分片透明、數(shù)據(jù)復(fù)制透明、數(shù)據(jù)位置透明。 集中與自治相結(jié)合的控制機(jī)制：局部共享和全局共享 一定的數(shù)據(jù)冗余：可靠、可用，單個(gè)站點(diǎn)故障不會(huì)影響整體。不利于更新，維護(hù)成本高，查詢速度快。 事務(wù)管理的分布性：全局事務(wù)可以分解為

42、若干子事務(wù)。事務(wù)的ACID特性受到考驗(yàn)。,分布式數(shù)據(jù)庫(kù)的特點(diǎn),分布式數(shù)據(jù)庫(kù)的12條準(zhǔn)則 本地自治性 不依賴于中心站點(diǎn) 可連續(xù)操作性 位置獨(dú)立性 數(shù)據(jù)分片獨(dú)立性 數(shù)據(jù)復(fù)制獨(dú)立性 分布式查詢處理 分布式事務(wù)處理 硬件獨(dú)立性 操作系統(tǒng)獨(dú)立性 網(wǎng)絡(luò)獨(dú)立性 數(shù)據(jù)庫(kù)管理系統(tǒng)獨(dú)立性,單個(gè)DBMS的本地運(yùn)算不受多數(shù)據(jù)庫(kù)系統(tǒng)中其它DBMS的加入而影響。 單個(gè)DBMS處理查詢和優(yōu)化查詢的方式不受訪問(wèn)多數(shù)據(jù)庫(kù)的全局查詢執(zhí)行的影響。 系統(tǒng)已執(zhí)行或操作在單個(gè)DBMS加入或離開(kāi)多數(shù)據(jù)庫(kù)聯(lián)盟時(shí)不受危害。,分布式數(shù)據(jù)庫(kù)的分類 按局部數(shù)據(jù)庫(kù)管理系統(tǒng)的數(shù)據(jù)模型分類 同構(gòu)型（homogenous）DDBS：數(shù)據(jù)模型相同 同構(gòu)同質(zhì)型

43、：各站點(diǎn)上的數(shù)據(jù)模型（關(guān)系、網(wǎng)狀、層次）相同，且都是同一種DBMS。 同構(gòu)異質(zhì)性：各站點(diǎn)上的數(shù)據(jù)模型（關(guān)系、網(wǎng)狀、層次）相同，但不是同一種DBMS。 異構(gòu)型（heterogenous）DDBS：各站點(diǎn)上的數(shù)據(jù)模型不同。,分布式數(shù)據(jù)庫(kù)的分類,按分布式數(shù)據(jù)庫(kù)系統(tǒng)的全局控制類型分類 全局控制集中型DDBS ：全局控制機(jī)制和全局?jǐn)?shù)據(jù)字典位于一個(gè)中心點(diǎn)，中心點(diǎn)完成全局事務(wù)的協(xié)調(diào)和局部數(shù)據(jù)庫(kù)的轉(zhuǎn)換 全局控制分散型DDBS：全局控制機(jī)制和全局?jǐn)?shù)據(jù)字典位于各個(gè)站點(diǎn)上，每個(gè)站點(diǎn)都能完成全局事務(wù)的協(xié)調(diào)和局部數(shù)據(jù)庫(kù)的轉(zhuǎn)換，每個(gè)站點(diǎn)既是全局事務(wù)的協(xié)調(diào)者，也是參與者。 全局控制可變型DDBS：主從型DDBS，站點(diǎn)有兩類

44、：主站點(diǎn)和從站點(diǎn)，主戰(zhàn)點(diǎn)上包含全局控制機(jī)制和全局?jǐn)?shù)據(jù)字典；輔助站點(diǎn)不包含全局控制機(jī)制和全局?jǐn)?shù)據(jù)字典,分布式數(shù)據(jù)庫(kù)系統(tǒng)的體系結(jié)構(gòu),包括： 局部DB、全局DB 局部DBMS和全局DBMS 局部DBA和全局DBA 局部數(shù)據(jù)字典LDD和全局?jǐn)?shù)據(jù)字典GDD 通信模塊CM,分片：又稱為數(shù)據(jù)分割，有三種分片方式 水平分片：按特定條件將全局關(guān)系劃分成若干互不相交的片段。通過(guò)對(duì)全局關(guān)系進(jìn)行選擇運(yùn)算得到。 垂直分片：把全局關(guān)系的屬性集分成若干子集。通過(guò)對(duì)全局關(guān)系進(jìn)行投影運(yùn)算獲得。 混合分片：上述兩種方法的混合。 分片規(guī)則 完備性條件：不多，即全局關(guān)系的所有數(shù)據(jù)必須映射到各個(gè)片段中，不允許有屬于全局關(guān)系的數(shù)據(jù)不屬于

45、它的任何一個(gè)片段。 可重構(gòu)條件：不少，即必須保證能夠由同一個(gè)全局關(guān)系的各個(gè)片段來(lái)重構(gòu)該全局關(guān)系。 水平：合并 垂直：連接 不相交條件：一個(gè)全局關(guān)系被分割后所得的各個(gè)數(shù)據(jù)片段不重疊。,分布式數(shù)據(jù)庫(kù)中的分片與分布,分布：根據(jù)需要將數(shù)據(jù)劃分成邏輯片段，按照某種策略將這些片段分散存儲(chǔ)在各個(gè)站點(diǎn)上，策略： 集中式：所有數(shù)據(jù)片段放在同一個(gè)站點(diǎn)上。 對(duì)數(shù)據(jù)控制和管理容易 數(shù)據(jù)一致性和完整性能夠得到保證 系統(tǒng)對(duì)數(shù)據(jù)站點(diǎn)依賴過(guò)重 數(shù)據(jù)站點(diǎn)故障將導(dǎo)致整個(gè)系統(tǒng)崩潰 檢索效率低 分割式：所有數(shù)據(jù)只有一份，經(jīng)過(guò)邏輯分割后形成多個(gè)片段，每個(gè)片段放在某個(gè)特定的站點(diǎn)上。 充分利用各個(gè)站點(diǎn)的存儲(chǔ)能力 每個(gè)站點(diǎn)可自治檢索和修改數(shù)

46、據(jù)，并發(fā)能力強(qiáng) 部分站點(diǎn)故障，系統(tǒng)仍能運(yùn)行，可靠性高 全局查詢和修改，響應(yīng)時(shí)間長(zhǎng)， 網(wǎng)絡(luò)通信代價(jià)較大,全復(fù)制式：全局?jǐn)?shù)據(jù)有多個(gè)副本，每個(gè)站點(diǎn)上都有一個(gè)完整的數(shù)據(jù)副本。 可靠性高 查詢速度快 數(shù)據(jù)同步困難 系統(tǒng)冗余大 混合式：全部數(shù)據(jù)被分為若干個(gè)子集，每個(gè)子集安置在不同的站點(diǎn)上，但任一站點(diǎn)都不保存全部數(shù)據(jù)。 靈活性好 系統(tǒng)效率高 復(fù)雜,分布式數(shù)據(jù)庫(kù)系統(tǒng)的模式結(jié)構(gòu),全局 DBMS,全局外模式：全局應(yīng)用的用戶視圖。 全局概念模式：描述分布式數(shù)據(jù)庫(kù)中全局?jǐn)?shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)特性，是分布式數(shù)據(jù)庫(kù)的全局概念視圖。 分片模式：描述全局?jǐn)?shù)據(jù)的邏輯劃分。 分配模式：根據(jù)選定的數(shù)據(jù)分配策略，定義各片段的物理存放位

47、置，確定是否冗余及冗余的程度。 局部概念模式：是全局概念模式的子集，由分配在同一站點(diǎn)上的一個(gè)或多個(gè)邏輯片段組成 局部?jī)?nèi)模式：是分布式數(shù)據(jù)庫(kù)關(guān)于物理數(shù)據(jù)庫(kù)的描述，跟集中式內(nèi)模式類似，但是不僅包含本站點(diǎn)數(shù)據(jù)的存儲(chǔ)描述，還包括全局?jǐn)?shù)據(jù)在本站點(diǎn)的存儲(chǔ)描述,全局關(guān)系R的邏輯片段與物理影像,67,分布式事務(wù)模型 事務(wù)的ACID 局部事務(wù)、全局事務(wù) 局部事務(wù)管理器 保證本地節(jié)點(diǎn)上執(zhí)行的事務(wù)的ACID 本次事務(wù)可能是全局事務(wù)的一部分 維護(hù)一個(gè)易于恢復(fù)的日志 參與適當(dāng)?shù)牟l(fā)控制 事務(wù)協(xié)調(diào)器 協(xié)調(diào)該節(jié)點(diǎn)上發(fā)起的事務(wù)（全局或局部）的執(zhí)行 啟動(dòng)事務(wù)的執(zhí)行 分發(fā)事務(wù) 協(xié)調(diào)事務(wù)的終止（在所有節(jié)點(diǎn)上提交或中止）,分布式事務(wù)

48、模型,68,TC1,TCn,TMn,TM1,事務(wù)管理器,事務(wù)協(xié)調(diào)器,69,故障 節(jié)點(diǎn)故障 消息丟失 網(wǎng)絡(luò)故障 提交 原子性 事務(wù)T必須要么在所有節(jié)點(diǎn)上提交，要么在所有節(jié)點(diǎn)上都中止 兩階段提交 三階段提交,70,兩階段提交 階段1（決定階段） 協(xié)調(diào)器 prepare T 節(jié)點(diǎn)事務(wù)管理器 ready T 或 abort T 階段2（執(zhí)行階段） 收到有一個(gè)abort T ,則abort T 收到所有ready T ,則commit T 節(jié)點(diǎn)commit T并寫(xiě)Log后，發(fā)出acknowledge T 收到所有acknowledge ，則complete T 阻塞： 協(xié)調(diào)器發(fā)出prepare T 后故

49、障，處于不定狀態(tài) 雙方針對(duì)超時(shí)均可重發(fā),71,三階段提交 階段1 同兩階段方式 階段2 收到有一個(gè)abort T ,則abort T 收到所有ready T ,則precommit T 節(jié)點(diǎn)precommit T之后，寫(xiě)Log，發(fā)出acknowledge T 階段3 收到所有ack，則commit T 節(jié)點(diǎn)commit 后，發(fā)出ack T 收到所有ack T后，complete T 恢復(fù) 只要有一個(gè)具有commit T,則提交 只要有一個(gè)precommit T,已ready T，可提交 都沒(méi)有收到precommit T，則回滾,72,協(xié)議的比較 兩階段提交 有阻塞的可能，使用較廣 三階段提交

50、對(duì)于網(wǎng)絡(luò)鏈路故障的處理能力偏弱,Hbase,Hbase是一個(gè)分布式開(kāi)源數(shù)據(jù)庫(kù)，基于Hadoop分布式文件系統(tǒng)，模仿并提供了基于Google文件系統(tǒng)的Bigtable數(shù)據(jù)庫(kù)的所有功能。 為什么需要HBASE 數(shù)據(jù)庫(kù)系統(tǒng)已無(wú)法適應(yīng)大型分布式數(shù)據(jù)存儲(chǔ)的需要 改良的關(guān)系數(shù)據(jù)庫(kù)（副本、分區(qū)等）難于安裝與維護(hù) 關(guān)系模型對(duì)數(shù)據(jù)的操作使數(shù)據(jù)的存貯變得復(fù)雜 主要特點(diǎn) HBASE從設(shè)計(jì)理念上就為可擴(kuò)展做好了充分準(zhǔn)備 Column-oriented 空間的擴(kuò)展只需要加入存儲(chǔ)結(jié)點(diǎn) 使用表的概念，但不同于關(guān)系數(shù)據(jù)庫(kù)，不支持SQL 它又不適合事務(wù)處理 實(shí)質(zhì)上是一張極大的、非常稀疏的，存儲(chǔ)在分布式文件系統(tǒng)上的表,Page

51、73,Page 74,HBase歷史,2006年底由PowerSet 的Chad Walters和Jim Kellerman 發(fā)起 2008年成為Apache Hadoop的一個(gè)子項(xiàng)目 現(xiàn)已作為產(chǎn)品被使用 WorldLingo S OpenPlaces Yahoo Adobe,HBASE用例WebTable,存儲(chǔ)抓取網(wǎng)頁(yè)和相關(guān)信息 每個(gè)頁(yè)面對(duì)應(yīng)一行，是個(gè)有百萬(wàn)行的大表 要基于此表進(jìn)行分析與解析并由搜索引擎對(duì)關(guān)鍵字進(jìn)行索引 表需要并發(fā)地被眾多網(wǎng)頁(yè)抓取程序隨機(jī)地訪問(wèn)以及更新數(shù)據(jù) 表內(nèi)容也要作為網(wǎng)頁(yè)實(shí)時(shí)緩存被大量用戶隨機(jī)訪問(wèn),邏輯視圖,RowKey,Row Key 與nosql數(shù)據(jù)庫(kù)們一樣,row

52、key是用來(lái)檢索記錄的主鍵。訪問(wèn)hbase table中的行，只有三種方式： 1 通過(guò)單個(gè)row key訪問(wèn) 2 通過(guò)row key的range 3 全表掃描 Row key行鍵 (Row key)可以是任意字符串(最大長(zhǎng)度是 64KB，實(shí)際應(yīng)用中長(zhǎng)度一般為 10-100bytes)，在hbase內(nèi)部，row key保存為字節(jié)數(shù)組。 存儲(chǔ)時(shí)，數(shù)據(jù)按照Row key的字典序(byte order)排序存儲(chǔ)。設(shè)計(jì)key時(shí)，要充分排序存儲(chǔ)這個(gè)特性，將經(jīng)常一起讀取的行存儲(chǔ)放到一起。(位置相關(guān)性) 注意： 行的一次讀寫(xiě)是原子操作 (不論一次讀寫(xiě)多少列)。這個(gè)設(shè)計(jì)決策能夠使用戶很容易的理解程序在對(duì)同一個(gè)行

53、進(jìn)行并發(fā)更新操作時(shí)的行為。,Page 78,數(shù)據(jù)模型行,每行數(shù)據(jù)有一可排序的關(guān)鍵字和任意列項(xiàng) 字符串、整數(shù)、二進(jìn)制串甚至與串行化的結(jié)構(gòu)都可以作為行鍵 表按照行鍵的“逐字節(jié)排序”順序?qū)π羞M(jìn)行有序化處理 表內(nèi)數(shù)據(jù)非常稀疏，不同的行的列的數(shù)完全目可以大不相同 可以只對(duì)一行上“鎖” 對(duì)行的寫(xiě)操作是始終是“原子”的,數(shù)據(jù)模型行,行鍵,列,列,數(shù)據(jù)模型列,列必須用族(family)來(lái)定義 任意一列有如下形式 “族：標(biāo)簽” 其中，族和標(biāo)簽都可為任意形式的串 物理上將同“族”數(shù)據(jù)存儲(chǔ)在一起 數(shù)據(jù)可通過(guò)時(shí)間戳區(qū)分版本,列族 hbase表中的每個(gè)列，都?xì)w屬與某個(gè)列族。列族是表的chema的一部分(而列不是)，必須

54、在使用表之前定義。列名都以列族作為前綴。例如courses:history，courses:math都屬于courses 這個(gè)列族。 訪問(wèn)控制、磁盤(pán)和內(nèi)存的使用統(tǒng)計(jì)都是在列族層面進(jìn)行的。實(shí)際應(yīng)用中，列族上的控制權(quán)限能幫助我們管理不同類型的應(yīng)用：我們?cè)试S一些應(yīng)用可以添加新的基本數(shù)據(jù)、一些應(yīng)用可以讀取基本數(shù)據(jù)并創(chuàng)建繼承的列族、一些應(yīng)用則只允許瀏覽數(shù)據(jù)（甚至可能因?yàn)殡[私的原因不能瀏覽所有數(shù)據(jù)）。,Page 82,列族 hbase表中的每個(gè)列，都?xì)w屬與某個(gè)列族。列族是表的chema的一部分(而列不是)，必須在使用表之前定義。列名都以列族作為前綴。例如courses:history，courses:ma

55、th都屬于courses 這個(gè)列族。 訪問(wèn)控制、磁盤(pán)和內(nèi)存的使用統(tǒng)計(jì)都是在列族層面進(jìn)行的。實(shí)際應(yīng)用中，列族上的控制權(quán)限能幫助我們管理不同類型的應(yīng)用：我們?cè)试S一些應(yīng)用可以添加新的基本數(shù)據(jù)、一些應(yīng)用可以讀取基本數(shù)據(jù)并創(chuàng)建繼承的列族、一些應(yīng)用則只允許瀏覽數(shù)據(jù)（甚至可能因?yàn)殡[私的原因不能瀏覽所有數(shù)據(jù)）。,Page 83,數(shù)據(jù)模型列,族,標(biāo)簽,物理視圖,HTable小結(jié),HBASE物理存儲(chǔ),1 已經(jīng)提到過(guò)，Table中的所有行都按照row key的字典序排列。 2 Table 在行的方向上分割為多個(gè)Hregion。 3 region按大小分割的，每個(gè)表一開(kāi)始只有一個(gè)region，隨著數(shù)據(jù)不斷插入表，re

56、gion不斷增大，當(dāng)增大到一個(gè)閥值的時(shí)候，Hregion就會(huì)等分會(huì)兩個(gè)新的Hregion。當(dāng)table中的行不斷增多，就會(huì)有越來(lái)越多的Hregion。,Page 87,4 HRegion是Hbase中分布式存儲(chǔ)和負(fù)載均衡的最小單元。最小單元就表示不同的Hregion可以分布在不同的HRegion server上。但一個(gè)Hregion是不會(huì)拆分到多個(gè)server上的。,Page 88,5 HRegion雖然是分布式存儲(chǔ)的最小單元，但并不是存儲(chǔ)的最小單元。 HRegion由一個(gè)或者多個(gè)Store組成，每個(gè)store保存一個(gè)columns family。 每個(gè)Strore又由一個(gè)memStore和0

57、至多個(gè)StoreFile組成。 StoreFile以HFile格式保存在HDFS上。,Page 89,Page 90,HFile分為六個(gè)部分： Data Block 段保存表中的數(shù)據(jù)，這部分可以被壓縮 Meta Block 段 (可選的)保存用戶自定義的kv對(duì)，可以被壓縮。 File Info 段Hfile的元信息，不被壓縮，用戶也可以在這一部分添加自己的元信息。 Data Block Index 段Data Block的索引。每條索引的key是被索引的block的第一條記錄的key。 Meta Block Index段 (可選的)Meta Block的索引。 Trailer這一段是定長(zhǎng)的。保存了每一段的偏移量，讀取一個(gè)HFile時(shí)，會(huì)首先讀取Trailer，Trailer保存了每個(gè)段的起始位置(段的Magic Number用來(lái)做安全check)，然后，DataBlock Index會(huì)被讀取到內(nèi)存中，這樣，當(dāng)檢索某個(gè)key時(shí)，不需要掃描整個(gè)HFile，而只需從內(nèi)存中找到key所在的block，通過(guò)一次磁盤(pán)io將整個(gè)block讀取到內(nèi)存中，再找到需要的key。DataBlock Index采用LRU機(jī)制淘汰。 HFile的Data Block，Meta