《高級數(shù)據(jù)庫及大規(guī)模存儲技術(shù)》全冊配套課件

《高級數(shù)據(jù)庫及大規(guī)模存儲技術(shù)》全冊配套課件高級數(shù)據(jù)庫及大規(guī)模存儲技術(shù)NoSQL的技術(shù)基礎(chǔ)及其實(shí)踐課程簡介1.教學(xué)目的課程學(xué)習(xí)和課下實(shí)踐理解云計(jì)算環(huán)境的數(shù)據(jù)存儲和應(yīng)用特性非關(guān)系型數(shù)據(jù)庫的數(shù)據(jù)管理方法及其關(guān)鍵技術(shù)完成典型平臺的構(gòu)建、部署和一般管理使用計(jì)算機(jī)編程語言編寫數(shù)據(jù)操作及其上的應(yīng)用。2.主要內(nèi)容NoSQL概念及原理NoSQL的外延MapReduce計(jì)算模型HBaseMongoDB數(shù)據(jù)層的設(shè)計(jì)技術(shù)3.課程要求數(shù)據(jù)庫原理程序設(shè)計(jì)JavaScriptJava/Scala/Python面向服務(wù)概念HTTP協(xié)議Restful4.成績課程實(shí)驗(yàn)60%計(jì)算共享獨(dú)立完成課程考試40%兩次考試，Middle和Final各20%5.ContactUS尹俊文國防科學(xué)技術(shù)大學(xué)計(jì)算機(jī)學(xué)院Email：jwyin_cn@163.comMobile:136073142606.教材1、NoSQL精粹塞得拉吉(PramodJ.Sadalage)(作者),福勒(MartinFowler)(作者),愛飛翔(譯者)，機(jī)械工業(yè)出版社，2013年9月，ISBN:978-7-111-43303-36.教材2、Hadoop實(shí)戰(zhàn)，ChuckLam(作者),韓冀中(譯者)，人民郵電出版社，2011年10月，ISBN:978-7-115-26448-06.教材3、HBase實(shí)戰(zhàn)，迪米達(dá)克(NickDimiduk)(作者),卡拉納(AmandeepKhurana)(作者),謝磊(譯者)，人民郵電出版社，2013年9月，ISBN:978-7-115-32446-77.參數(shù)書目2、MongoDB權(quán)威指南(第2版)，霍多羅夫(KristinaChodorow)(作者),

鄧強(qiáng)(譯者),王明輝(譯者)，人民郵電出版社，2014年1月，ISBN:97871153410827.參數(shù)書目高級數(shù)據(jù)庫及大規(guī)模存儲技術(shù)NoSQL的技術(shù)基礎(chǔ)及其實(shí)踐NoSQL簡介1.1TheEmergenceofNoSQL最早的NoSQL名詞出現(xiàn)在1990s，是一個開源關(guān)系數(shù)據(jù)庫項(xiàng)目用ASCII文件存儲數(shù)據(jù)表CarloStrozzi不以SQL作為查詢接口2006年9月組織的Meetup，給Twitter發(fā)起一個話題，易于記憶，比較醒目（被Google收錄少）聚集BigTable和Dynamo催生的項(xiàng)目EricEvan建議使用NoSQLWho’sUsingNoSQL?1.2WhatisNoSQL?NoSQLisasetofconceptsthatallowstherapidandefficientprocessingofdatasetswithafocusonperformance,reliability,andagility.1.3WhatareNoSQLincludes不僅僅是行記錄結(jié)構(gòu)join-freeschema-free多處理器集群環(huán)境采用什么都不共享的貨架計(jì)算機(jī)支持橫向線性擴(kuò)展開源創(chuàng)新1.4WhatareNoSQLdoseNOTincludeIt’snotabouttheSQLlanguageIt’snotonlybigdataIt’snotaboutcloudcomputingIt’snotaboutacleveruseofRAMandSSDIt’snotanelitegroupofproducts2NoSQL的業(yè)務(wù)驅(qū)動因子單節(jié)點(diǎn)RDBMS數(shù)據(jù)量敏捷性可變性速度2.1數(shù)據(jù)量(Volume)驅(qū)動因子大數(shù)據(jù)量處理始終是推動體系結(jié)構(gòu)變革的關(guān)鍵因素在2005年，處理器處理速度的增長遇到了瓶頸——PowerWall大規(guī)模數(shù)據(jù)處理推動了：大規(guī)模并行計(jì)算、分布式計(jì)算、及其組合（超級計(jì)算）Web1.0

ReadIntensiveWebWeb2.0

WriteIntensiveWeb數(shù)據(jù)量的增長TheAgeofBigData

Exabytes(1018)ofdatastoredperyearBigDatasets

(Data-RichComputingthemeproposal.J.Campbell,etal,2007)2.2速度(Velocity)驅(qū)動因子盡管大數(shù)據(jù)問題可以通過并行計(jì)算得到緩解，單處理器的讀寫速度仍然很關(guān)鍵目前單處理器RDBMS系統(tǒng)的通用性解決方案無法應(yīng)對當(dāng)前新型的Web應(yīng)用場景應(yīng)用的使用模式是什么？2.3可變性(Variability)驅(qū)動因子應(yīng)用的可變性任何新型的應(yīng)用總是會帶來新的數(shù)據(jù)類型是否應(yīng)該嚴(yán)格遵守模式規(guī)范？關(guān)系模型如何應(yīng)對數(shù)據(jù)類型的變化？2.4敏捷性(Agility)驅(qū)動因子應(yīng)用的敏捷性在敏捷軟件開發(fā)方法的帶動下，開源社區(qū)出現(xiàn)了新的的結(jié)構(gòu)和技術(shù)：多層軟件體系結(jié)構(gòu)測試優(yōu)先連接池對象關(guān)系映射這些技術(shù)很多都是為了應(yīng)對新型應(yīng)用模式對RDBMS的需求2.5計(jì)算機(jī)領(lǐng)域的一般問題通用性和靈活性、性能的矛盾下層的機(jī)制約束了上層采用的策略上層的優(yōu)化方法：隧道：繞開底層機(jī)制過設(shè)計(jì)上層不斷增長的需求特性導(dǎo)致下層設(shè)計(jì)的無限膨脹3NoSQL的典型案例案例/標(biāo)準(zhǔn)動機(jī)發(fā)現(xiàn)LiveJournal’s

Memcache提高數(shù)據(jù)庫查詢的性能使用hashing和caching，RAM中的數(shù)據(jù)可以共享。

通過減少發(fā)送到數(shù)據(jù)庫讀請求的數(shù)量來提高性能Google’sMapReduce使用低成本硬件，對億數(shù)量級的網(wǎng)頁進(jìn)行搜索索引使用并行處理，可以利用大量貨架處理器快速完成億數(shù)量級的網(wǎng)頁索引Google’sBigtable在分布式系統(tǒng)中靈活存儲表格數(shù)據(jù)(tabularData)使用稀疏矩陣方法，無需預(yù)先建模，也可以讓用戶感覺到所有數(shù)據(jù)都存儲在一張有億級別數(shù)量行的表中Amazon’sDynamo接受7×24小時的web訂單即使有大量的數(shù)據(jù)需要處理，也可以復(fù)制具有簡單接口的key-value存儲MarkLogic使用標(biāo)準(zhǔn)查詢語言，查詢存儲在貨架硬件上的大量XML文檔集合貨架服務(wù)器存儲XML文檔索引，將查詢分布到這些服務(wù)器，每個服務(wù)器可以負(fù)責(zé)處理自己本地盤上的數(shù)據(jù)，然后將結(jié)果返回給查詢服務(wù)器3.1LiveJournal’s

MemcacheLiveJournal是一個Blog系統(tǒng)將最常用的數(shù)據(jù)庫查詢結(jié)果保留在RAM中若干服務(wù)器可能持有同一查詢的相同結(jié)果使用Memcache協(xié)議，交互持有查詢結(jié)果的情況Memcache成了一種查詢結(jié)果重用的前端工具不僅僅用于數(shù)據(jù)庫查詢處理3.2Google’sMapReduceNoSQL社區(qū)中最具影響力的項(xiàng)目之一開啟了MapReduce廣泛應(yīng)用之門輸入數(shù)據(jù)MapMapMapShuffleSortReduce查詢結(jié)果3.3Google’sBigtableBigtable是google發(fā)布的另一個有影響的項(xiàng)目網(wǎng)絡(luò)爬蟲分解出了大量網(wǎng)頁、圖像、視頻等媒體，它們無法進(jìn)行關(guān)系建模一個有1億行1億列的表3.4Amazon’sDynamo相對于Bigtable關(guān)注大規(guī)模批處理，Dynamo更致力于系統(tǒng)的可擴(kuò)展能力在復(fù)制、故障處理上給出了合理的解決方案4NoSQL的生態(tài)系統(tǒng)TypeTypicalusageExamplesKey-valuestore?Imagestores?Key-basedfilesystems?Objectcache?Systemsdesignedtoscale?BerkeleyDB、Memcache、Redis、Riak、DynamoDBColumnfamilystore?Webcrawlerresults?Bigdataproblemsthatcanrelaxconsistencyrules?ApacheHBase、ApacheCassandra、Hypertable、ApacheAccumulo

Graphstore?Socialnetworks?Frauddetection?Relationship-heavydata?Neo4j、AllegroGraph、Bigdata(RDFdatastore)、InfiniteGraph(Objectivity)Documentstore?High-variabilitydata?Documentsearch?Integrationhubs?Webcontentmanagement?Publishing?MongoDB(10Gen)、CouchDB、Couchbase、MarkLogic、

eXist-db、BerkeleyDBXML高級數(shù)據(jù)庫及大規(guī)模存儲技術(shù)NoSQL的技術(shù)基礎(chǔ)及其實(shí)踐關(guān)系模型的分析1數(shù)據(jù)體系結(jié)構(gòu)模式

dataarchitecturepattern如何存儲一張表格？更復(fù)雜的表格怎么辦？表格可以解決所有的問題嗎？？1.1數(shù)據(jù)體系結(jié)構(gòu)模式模式：對一個問題存在的已知的解決方案數(shù)據(jù)結(jié)構(gòu)模式：一種如何存取大量數(shù)據(jù)的解決方案1.2行存儲(rowstore)行是數(shù)據(jù)存取的原子單位1.3RDBMS設(shè)計(jì)模式基于關(guān)系模型的建模面向表的數(shù)據(jù)定義語言(DDL)基于關(guān)系代數(shù)的數(shù)據(jù)操作語言(DML)基于JOIN的數(shù)據(jù)關(guān)聯(lián)支持?jǐn)?shù)據(jù)完整性的trigger機(jī)制面向重用的storedprocedure機(jī)制1.4RDBMS的價值數(shù)據(jù)持久化并發(fā)訪問標(biāo)準(zhǔn)成熟應(yīng)用集成1.4.1數(shù)據(jù)持久化RDBMS提供了一種有效組織數(shù)據(jù)的方法RDBMS填補(bǔ)了文件系統(tǒng)在大規(guī)模數(shù)據(jù)管理方面的缺陷隨著個人計(jì)算機(jī)持有存儲器容量的增長，文件系統(tǒng)已經(jīng)不能滿足大量個人信息的組織要求RDBMS為快速、方便獲取信息提供了有效的支持1.4.2并發(fā)訪問細(xì)粒度的數(shù)據(jù)管理是共享的必要基礎(chǔ)條件粗粒度的文件共享是很罕見的，也是不情愿的共享也就帶來了并發(fā)訪問問題操作系統(tǒng)和數(shù)據(jù)在研究這類問題上的研究是共用的但是操作系統(tǒng)領(lǐng)域研究共享問題略顯矯情雖然在這個領(lǐng)域出現(xiàn)了很多的并發(fā)控制機(jī)制，但是事務(wù)和鎖機(jī)制在RDBMS中證明了自己的有效性1.4.3標(biāo)準(zhǔn)成熟標(biāo)準(zhǔn)的SQL使得應(yīng)用可以在不同的RDBMS之間移植成熟的ACID事務(wù)模型使得應(yīng)用開發(fā)更加得心應(yīng)手成熟的開發(fā)技術(shù)降低了軟件開發(fā)成本成熟的數(shù)據(jù)建模方法成熟的SQL編程方法成熟的軟件體系結(jié)構(gòu)成熟的軟件構(gòu)件與框架1.4.4應(yīng)用集成雖然SOA是目前最熱門的集成技術(shù)，但是數(shù)據(jù)集成是最常用和最成熟的應(yīng)用集成技術(shù)以O(shè)LAP、OLTP為基礎(chǔ)的集成技術(shù)成為企業(yè)ERP的主力數(shù)據(jù)庫甚至可以作為進(jìn)程間通信的手段接口集成數(shù)據(jù)集成界面集成2RDBMS的實(shí)現(xiàn)技術(shù)事務(wù)DDL和強(qiáng)類型列安全和訪問控制復(fù)制和同步2.1事務(wù)機(jī)制Atomicity,Consistency,Isolation,DurabilityBEGINTRANSACTION/COMMIT/ROLLBACK通常使用LOCK機(jī)制實(shí)現(xiàn)嚴(yán)格的ACID嚴(yán)重影響并發(fā)能力，可能死鎖隔離級別：SerializableRepeatablereadsReadcommittedReaduncommitted2.1.1臟讀/*Query1*/SELECTageFROMusersWHEREid=1;/*willread20*//*Query2*/UPDATEusersSETage=21WHEREid=1;/*Nocommithere*//*Query1*/SELECTageFROMusersWHEREid=1;/*willread21*/

/*Query1*/SELECTageFROMusersWHEREid=1;/*willread21*/ROLLBACK;/*lock-basedDIRTYREAD*/2.1.2不可重復(fù)讀/*Query1*/SELECT*FROMusersWHEREid=1;/*Query2*/UPDATEusersSETage=21WHEREid=1;COMMIT;/*inmultiversionconcurrencycontrol,orlock-basedREADCOMMITTED*//*Query1*/SELECT*FROMusersWHEREid=1;COMMIT;/*lock-basedREPEATABLEREAD*/2.1.3幻讀/*Query1*/SELECT*FROMusersWHEREageBETWEEN10AND30;/*Query2*/INSERTINTOusersVALUES(3,'Bob',27);COMMIT;/*Query1*/SELECT*FROMusersWHEREageBETWEEN10AND30;COMMIT;2.2固定的DDL和強(qiáng)類型列物理模型要求預(yù)想定義表中所有列的名字、類型約束、以及索引和關(guān)系這樣的強(qiáng)類型約束為數(shù)據(jù)正確性驗(yàn)證提供了支持，可以避免數(shù)據(jù)的質(zhì)量下降問題在數(shù)據(jù)類型需要改變時，引起了問題：或者使用一個新的列存儲數(shù)據(jù)或者采用一種更靈活的數(shù)據(jù)類型前者會使得數(shù)據(jù)列越來越多，而原有列成了死列后者將使得強(qiáng)類型形同虛設(shè)2.3安全和訪問控制RDBMS提供了對表和視圖進(jìn)行安全控制的機(jī)制視圖是在RDBMS上實(shí)現(xiàn)行級和列級數(shù)據(jù)進(jìn)行訪問控制的有效手段2.4復(fù)制和同步RDBMS通常使用log文件保證關(guān)鍵數(shù)據(jù)的存儲log文件會降低系統(tǒng)性能，而且log主要用于保證事務(wù)的正確性主從數(shù)據(jù)庫模式的集群系統(tǒng)是提高數(shù)據(jù)庫系統(tǒng)可用性的一種手段集群數(shù)據(jù)庫系統(tǒng)引入了復(fù)制機(jī)制可用性問題可以在消息系統(tǒng)級別和存儲系統(tǒng)級別得到保證復(fù)制機(jī)制帶來了分布式系統(tǒng)中的經(jīng)典問題：一致性保證（同步）3RDBMS的難題關(guān)鍵字去規(guī)范化SQL技巧存儲過程和觸發(fā)器應(yīng)用設(shè)計(jì)3.1關(guān)鍵字問題業(yè)務(wù)關(guān)鍵字和數(shù)據(jù)關(guān)鍵字不滿足BCNF的業(yè)務(wù)關(guān)鍵字是常見的身份證號碼業(yè)務(wù)關(guān)鍵字可能發(fā)生變化學(xué)號需要變化嗎？業(yè)務(wù)關(guān)鍵字可能影響性能組合關(guān)鍵字變長字符串課本上講的有點(diǎn)忽悠人3.2去規(guī)范化物理設(shè)計(jì)時為了提高性能、完整性和可維護(hù)性所采用的方法使用幾張表格？表格中的列是否需要冗余？你如何設(shè)計(jì)一個機(jī)構(gòu)層次表？3.2.1去規(guī)范化技巧StoringDerivableValuesPre-joiningTablesHard-CodedValuesKeepingDetailswithMasterRepeatingSingleDetailwithMasterShort-CircuitKeys3.3SQL技巧SQL的編寫需要技巧如何動態(tài)拼接一個查詢語句？大量的SQL技巧用于解決層出不窮的查詢問題復(fù)雜查詢的支持通常需要特殊的數(shù)據(jù)庫設(shè)計(jì)是使用復(fù)雜的SQL語句，還是采用復(fù)雜的程序？是使用復(fù)雜的查詢語句，還是使用視圖？3.4存儲過程和觸發(fā)器如何正確使用存儲過程如何恰當(dāng)使用觸發(fā)器3.5應(yīng)用設(shè)計(jì)數(shù)據(jù)層數(shù)據(jù)訪問模式數(shù)據(jù)庫設(shè)計(jì)重構(gòu)4新型應(yīng)用OLAP/OLTP主動(Active)數(shù)據(jù)庫演繹(Deductive)時態(tài)(Temporal)數(shù)據(jù)庫4.1OLAP/OLTP4.1OLAP/OLTP星形體系結(jié)構(gòu)多維數(shù)據(jù)模型MDX查詢語言聚集計(jì)算4.2ActiveDatabase業(yè)務(wù)智能，主動處理主動規(guī)則和主動行為SQL99支持利用Trigger可以實(shí)現(xiàn)規(guī)則語言和規(guī)則管理問題4.3DeductiveDatabases將數(shù)據(jù)庫技術(shù)和專家系統(tǒng)合并事實(shí)、規(guī)則和完整性約束數(shù)據(jù)的表示問題數(shù)據(jù)操作語言SQL不再完全適用查詢處理算法需要特殊設(shè)計(jì)4.4TemporalDatabase包含歷史數(shù)據(jù)的數(shù)據(jù)庫系統(tǒng)數(shù)據(jù)具有timestamp特性與時間相關(guān)的數(shù)據(jù)操作和聚集計(jì)算數(shù)據(jù)的水平分解和垂直分解數(shù)據(jù)的存儲Thanks！RDBMScons:Theobject-relationalmappinglayercanbecomplex.Entity-relationshipmodelingmustbecompletedbeforetestingbegins,whichslowsdevelopment.RDBMSsdon’tscaleoutwhenjoinsarerequired.Shardingovermanyserverscanbedonebutrequiresapplicationcodeandwillbeoperationallyinefficient.Full-textsearchrequiresthird-partytools.Itcanbedifficulttostorehigh-variabilitydataintables.NoSQLpros:Loadingtestdatacanbedonewithdrag-and-droptoolsbeforeERmodelingis

complete.Modulararchitectureallowscomponentstobeexchanged.Linearscalingtakesplaceasnewprocessingnodesareaddedtothecluster.Loweroperationalcostsareobtainedbyautosharding.Integratedsearchfunctionsprovidehigh-qualityrankedsearchresults.There’snoneedforanobject-relationalmappinglayer.It’seasytostorehigh-variabilitydata.NoSQLcons:ACIDtransactionscanbedoneonlywithinadocumentatthedatabaselevel.Othertransactionsmustbedoneattheapplicationlevel.Documentstoresdon’tprovidefine-grainedsecurityattheelementlevel.NoSQL

systemsarenewtomanystaffmembersandadditionaltrainingmayberequired.Thedocumentstorehasitsownproprietarynonstandardquerylanguage,whichprohibitsportability.Thedocumentstorewon’tworkwithexistingreportingandOLAPtools.高級數(shù)據(jù)庫及大規(guī)模存儲技術(shù)NoSQL的技術(shù)基礎(chǔ)及其實(shí)踐聚合數(shù)據(jù)類型Agenda對象關(guān)系映射領(lǐng)域驅(qū)動的聚合設(shè)計(jì)聚合數(shù)據(jù)模型1對象關(guān)系映射指不兼容面向?qū)ο缶幊陶Z言的類型系統(tǒng)之間進(jìn)行數(shù)據(jù)轉(zhuǎn)換的技術(shù)對象模型和關(guān)系模型存在著固有差異可以在若干層次解決問題：語言庫級別數(shù)據(jù)庫級別Hibernate是典型的ORM框架面向?qū)ο髷?shù)據(jù)庫和NoSQL是數(shù)據(jù)庫級別的解決方案1.1數(shù)據(jù)訪問模式大多數(shù)業(yè)務(wù)應(yīng)用主要考慮CRUD對磁盤的讀寫分層提供了組織這種邏輯的方法根據(jù)目的或主題將邏輯集中起來一站式購物(“1stopshopping”)1.1.2數(shù)據(jù)管理層持有持久存儲的數(shù)據(jù)模型Dataentities(i.e.tables)Datatypes(i.e.columns)Datarelations(i.e.referentialintegrity)Dataintegrity(i.e.checkconstraints,triggers,etc.)管理對數(shù)據(jù)模型的讀寫執(zhí)行SQL語句或者存儲過程根本上確保所支持的ACID原則1.1.3數(shù)據(jù)模型的設(shè)計(jì)決定技術(shù)Normalizationvs.DenormalizationHorizontalandVerticalPartitioningMaterializedViews，……數(shù)據(jù)模型考慮的是如何最佳存取數(shù)據(jù)1.1.4對數(shù)據(jù)模型的觀察隨著時間的推移，可能發(fā)生變化可能服務(wù)于多個應(yīng)用系統(tǒng)設(shè)計(jì)應(yīng)該具有改變數(shù)據(jù)模型的靈活性將數(shù)據(jù)模型變化對其他層次的影響減小到最少(i.e.計(jì)入降低各層之間的耦合度)易于找到受到數(shù)據(jù)模型變化影響的代碼1.1.5數(shù)據(jù)訪問層知道數(shù)據(jù)源的標(biāo)識知道如何連接數(shù)據(jù)管理層知道如何實(shí)現(xiàn)CRUD運(yùn)用SQL和存儲過程可能有，也可能沒有具體的層次通常表現(xiàn)為一組“數(shù)據(jù)訪問對象”DALlogic通常出現(xiàn)在領(lǐng)域?qū)ο?/p>

(DomainObjects)中1.1.6領(lǐng)域模型層領(lǐng)域?qū)ο髽?biāo)識問題域的實(shí)體e.g.Customer,Order,Vendor管理臨時狀態(tài)調(diào)用數(shù)據(jù)訪問操作強(qiáng)制數(shù)據(jù)驗(yàn)證執(zhí)行業(yè)務(wù)規(guī)則定義領(lǐng)域中實(shí)體之間的關(guān)系1.1.7領(lǐng)域模型的設(shè)計(jì)DataModel!=DomainModel數(shù)據(jù)模型定義數(shù)據(jù)如何存放數(shù)據(jù)模型的實(shí)際是最優(yōu)地支持?jǐn)?shù)據(jù)讀寫和完整性領(lǐng)域模型定義數(shù)據(jù)如何使用集成和多態(tài)扮演著重要角色領(lǐng)域模型和數(shù)據(jù)模型的松耦合可以出盡它們各自獨(dú)立的演化1.2阻抗失配

(impedancemismatch)源于電子工程的阻抗匹配1.2.1

Object-relationalimpedancemismatch90年代，面向?qū)ο髷?shù)據(jù)庫風(fēng)靡一時，但是隨著面向?qū)ο笳Z言的崛起，面向?qū)ο髷?shù)據(jù)庫反而日漸式微面向關(guān)系數(shù)據(jù)庫抓住了機(jī)會，強(qiáng)化了在計(jì)算機(jī)軟件中作為集成機(jī)制的角色，分離了應(yīng)用開發(fā)人員和數(shù)據(jù)庫管理員兩種角色。面向?qū)ο蠓妒交谲浖こ淘?，而關(guān)系范式基于數(shù)學(xué)原理1.3OO與OR的差異數(shù)據(jù)類型差異鼓勵/禁止傳引用字符串差異結(jié)構(gòu)和完整性差異對象組裝/類繼承機(jī)制是OR不具備的OR的聲明式約束方式OO通常采用保護(hù)邏輯報異常的方式，或采用面向方面方法設(shè)計(jì)操作差異OR采用基于元組的原語操作OO采用底層的物理訪問路徑相關(guān)的命令式操作事務(wù)性差異OO語言沒有類似隔離性和持久性概念1.3.1粒度(Granularity)差異對象模型中類數(shù)量和關(guān)系數(shù)據(jù)庫中表的數(shù)目通常是不同的publicclassTeacher{}publicclassSchool{}1.3.2子類型差異(Subtypes(inheritance))繼承是面向?qū)ο缶幊陶Z言中得自然泛型，但是RDBMS不支持這個概念HumanManWomanInheritance1.3.3關(guān)聯(lián)與數(shù)據(jù)導(dǎo)航實(shí)體關(guān)聯(lián)通過外關(guān)鍵字對象關(guān)聯(lián)通常是單向的部分出現(xiàn)在整體中部分對整體的應(yīng)用并不常見Classuser_main{Teacherteacher;}ClassTeacher{}1.3.4數(shù)據(jù)類型差異字符串?dāng)?shù)據(jù)類型是典型的例子在RDBMS中字符串具有長度，尾部空格通常沒有含義一般的面向?qū)ο笳Z言字符串沒有長度限制對象世界和關(guān)系世界的Date和time存在很大差異為了避免不必要的麻煩，有的應(yīng)用在RDBMS中使用字符串類型標(biāo)識Date和Time1.3.4數(shù)據(jù)類型差異1.3.5OR與OO的概念差異聲明和命令接口OR視數(shù)據(jù)為接口，OO視行為為接口活動和實(shí)體之間的關(guān)系OR分離了實(shí)體與行為結(jié)構(gòu)與行為基于集合論的OR，基于圖論的OO對象范式與關(guān)系范式1.4

對象關(guān)系映射

一種現(xiàn)實(shí)的解決方案ORM橋接OO和OR為應(yīng)用提供面向?qū)ο蟮臄?shù)據(jù)訪問接口Value

Object和Data

Access

Object成為主要的設(shè)計(jì)模式1.4.1

ORM組件模型MappingReflection,ProjectionandHydrationSQLQueryBuilderFetchingCachingandpersistenceSettings1.4.1MappingStorageModelConceptualModelMappingModel使用XML描述模型之間的映射關(guān)系Java

Annotation是另外的形式1.4.2Reflection

andProjection

1.4.3SQLQueryBuilder1.4.4Fetching是否需要在裝載一個對象時，將其所有成員一起裝載？lazyloading.Lazyloading是一種設(shè)計(jì)模式按需裝載的意思只有在需要的時候才裝載/初始化對象Lazyloading

Levels列級別關(guān)聯(lián)級別1.4.5CachingandOptimizations緩存動態(tài)生成查詢，不需要每次重建緩存避免了對數(shù)據(jù)源的重復(fù)調(diào)用查詢優(yōu)化處理環(huán)形引用處理層疊(cascade)更新批量更新和刪除1.5常見ORM軟件軟件平臺是否開源DoctrinePHP是RedBeanPHPPHP是Dapper.NET是ECO.NET否EntitySpaces.NET是EclipseLinkJava是HibernateJava是MyBatis/iBATIS跨平臺是jOOQJava是ApacheCayenneJava是LLBLGenPro.NET否軟件平臺是否開源MicrosoftADO.NETEntityFramework.NET否nHibernate.NET是ODB跨平臺C++否SQLAlchemyPython是SQLObjectPython是StormPython是SubSonic.NET是TopLinkJava否SkipperPHP否WebORBIntegrationServer.NET,Java,PHP是DBIx::ClassPerl是1.5.2Hibernate可以通過XML文件或者JavaAnnotation將Java類映射到關(guān)系表支持一對多和多對多關(guān)系的映射支持自定義數(shù)據(jù)類型的映射Enum、一個屬性映射到多個列支持QBE、QBA、QBL（HQL）查詢支持POJO的透明持久化1.5.3MyBatis/iBATIS不將Java對象映射到關(guān)系表，而是將Java方法映射到SQL語句在應(yīng)用端實(shí)現(xiàn)數(shù)據(jù)庫中存儲過程、視圖和查詢等機(jī)制提供一種將查詢結(jié)果映射到對象樹的機(jī)制2聚合來源于“領(lǐng)域驅(qū)動設(shè)計(jì)”它是作為一個單位進(jìn)行處理的相關(guān)對象集合，特別是數(shù)據(jù)操作和一致性管理的單位使用源自操作來更新聚合，以聚合的形式與數(shù)據(jù)存儲進(jìn)行通信數(shù)據(jù)庫可以將聚合作為復(fù)制和分片的單元2.1.1關(guān)系數(shù)據(jù)模型實(shí)例2.1.2關(guān)系存儲的數(shù)據(jù)2.1.3聚合數(shù)據(jù)模型實(shí)例2.1.4聚合數(shù)據(jù)表示//incustomers{

“id":1,"name":"Martin","billingAddress":[{"city":"Chicago"}]}//inorders{

“id":99,"customerId":1,"orderItems":[{"productId":27,"price":32.45,"productName":"NoSQLDistilled"}],"shippingAddress":[{"city":"Chicago"}]"orderPayment":[{"ccinfo":"1000-1000-1000-1000","txnId":"abelif879rft","billingAddress":{"city":"Chicago"}}],}2.1.5更內(nèi)聚的聚合2.1.6聚合數(shù)據(jù)//incustomers{"customer":{"id":1,"name":"Martin","billingAddress":[{"city":"Chicago"}],"orders":[{}]}}"id":99,"customerId":1,"orderItems":[{"productId":27,"price":32.45,"productName":"NoSQLDistilled"}],“shippingAddress”:[{“city”:“Chicago”}],"orderPayment":[{"ccinfo":"1000-1000-1000-1000","txnId":"abelif879rft","billingAddress":{"city":"Chicago"}}],2.2面向聚合的數(shù)據(jù)訪問不是劃分聚合邊界，而是規(guī)劃數(shù)據(jù)訪問方式從領(lǐng)域角度看待數(shù)據(jù)易于將聚合數(shù)據(jù)分離在不同節(jié)點(diǎn)面向聚合不再支持ACID的事務(wù)大多數(shù)源自操作局限在聚合內(nèi)部一般不支持跨越聚合邊界的ACID事務(wù)2.2.1基于ORM的數(shù)據(jù)訪問模式T1–HTMLintoJavaObjectsT2–JavaObjectsintoSQLTablesT4–TablesintoObjectsT3–ObjectsintoHTML2.2.2增加了Web

Service的數(shù)據(jù)訪問T4–ObjectsintoHTMLT5–ObjectstoXMLT6–XMLtoObjectsT1–HTMLintoJavaObjectsT2–JavaObjectsintoSQLTablesT3–TablesintoObjects2.2.3

ORM陷入沼澤對象到表的映射問題模式所有權(quán)（Schema-Ownership）沖突雙向模式(Dual-Schema)問題實(shí)體標(biāo)識問題數(shù)據(jù)檢索接口問題部分對象問題和裝載時間悖論2.2.4是否真的需要RDBMS?大多數(shù)ORM都是與RDBMS緊耦合的范式扼殺了Web應(yīng)用范式的目標(biāo)是讓數(shù)據(jù)盡可能地小Web應(yīng)用的目標(biāo)是盡可能地快具有廣泛用戶的Web應(yīng)用都沒有遵循3范式的Web應(yīng)用受到性能壓力會快速降低到更低范式(denormalization).RESTfulAPIs典型地適用于與單表應(yīng)用/api/:resource/:id2.2.5可能需要的就是Key-Value存儲不要奢望同時達(dá)到通用化和高性能如果確定使用一個特殊的數(shù)據(jù)庫，應(yīng)該按照數(shù)據(jù)庫的特性優(yōu)化應(yīng)用對于一些特殊用例，直接訪問數(shù)據(jù)庫是一種最佳實(shí)踐WikiMediaexample-directaccesstoMySQLandPostgreSQL

相對于RDBMS，Key-value存儲可能更適合Web應(yīng)用2適合復(fù)雜類型的JOIN操作不要用RDBMS實(shí)現(xiàn)key-value存儲如果數(shù)據(jù)庫足夠快，不要使用cacheDon'tshardyourself.32.2.5基于Key/Value的存儲2.2.5一種特殊的Key/Value存儲列族存儲2.2.5基于引用的模型2.2.5標(biāo)識引用關(guān)系的模型圖存儲2.2.6文檔存儲不需要翻譯DocumentsinthedatabaseDocumentsintheapplicationNoobjectmiddletierNo"shredding”NoreassemblySimple!2.2.7零翻譯

(XML)XMLlivesinthewebbrowser(Xforms)RESTinterfacesXMLinthedatabase(NativeXML,Xquery)XRX

WebApplicationArchitectureNotranslation!2.3無模式數(shù)據(jù)庫系統(tǒng)在數(shù)據(jù)裝載到數(shù)據(jù)庫的時候，自動決定如何索引數(shù)據(jù)不需要數(shù)據(jù)結(jié)構(gòu)的先驗(yàn)知識不需要預(yù)先的邏輯數(shù)據(jù)建模數(shù)據(jù)模型依然存在，但是隱含在處理邏輯中2.3.1無模式數(shù)據(jù)的集成更易于存儲實(shí)際得到的數(shù)據(jù)，而不是我們想我們可能得到的數(shù)據(jù)“Wecaneasilystorethedatathatweactually

get,notthedatawethought

wewouldget."2.3.2不再需要預(yù)先的ER建模不需要在插入第一條記錄之前完成建模不需要數(shù)據(jù)定義語言元數(shù)據(jù)用于在數(shù)據(jù)到達(dá)時穿件索引建模編程了一個統(tǒng)計(jì)過程——編寫查詢來尋找異?；蛘咭?guī)格化數(shù)據(jù)異常制造規(guī)則數(shù)據(jù)驗(yàn)證通常利用一些特殊工具來實(shí)現(xiàn)，例如XMLSchema、業(yè)務(wù)規(guī)則系統(tǒng)Schematron

2.3.3模式數(shù)據(jù)庫的優(yōu)勢全局?jǐn)?shù)據(jù)定義預(yù)先定義數(shù)據(jù)類型及其關(guān)系查詢更有效可以根據(jù)數(shù)據(jù)類型、列值和關(guān)系類型約束行為優(yōu)化訪問用于確定如何最優(yōu)存儲、管理和訪問特定數(shù)據(jù)類型易于QueryByExample，展示可用信息類型信息之間的關(guān)系2.3.3

模式數(shù)據(jù)庫的優(yōu)勢互操作適應(yīng)語言和環(huán)境控制模式的改變保持應(yīng)用和數(shù)據(jù)的同步一致的安全控制2.3.4模式數(shù)據(jù)庫的劣勢模式需要維護(hù)應(yīng)用要保持與模式的同步應(yīng)用關(guān)心數(shù)據(jù)類型缺少特殊應(yīng)用所需的靈活性2.3.5無模式數(shù)據(jù)庫的優(yōu)勢靈活可以將任意類型的數(shù)據(jù)持久化可以創(chuàng)立任意類型的關(guān)系對數(shù)據(jù)的尋找不再關(guān)心數(shù)據(jù)類型可以容忍不同的ACID和一致性易于使用和維護(hù)不需要專職的DBA新型數(shù)據(jù)出現(xiàn)后應(yīng)用也可以工作增加新的的數(shù)據(jù)成分或者改變數(shù)據(jù)成分，不會造成混亂億量級數(shù)據(jù)的搜索可以達(dá)到次秒級的響應(yīng)時間2.3.6無模式數(shù)據(jù)庫的劣勢混淆(Confusion)性能問題(Performancesuffers)完整性問題(PoorIntegrity)含糊(Ambiguity)SCHEMA

vs.Schema-FreeSCHEMA:Network[CODASYL]databases-DDL[1972]RelationalDatabases-DataDictionaryObjectDatabases-ODMG'93MostGraphDatabasesSchema-less:KSAM/ISAM/DSAM/ESAMIMS(hierarchical)PickOSDatabase(hash-tables)MUMPS(hierarchicalarray-storage)MongoDB

-aspecializedJSON(andJSON-like)documentstore.CouchDB

-aJSONdocumentstore.3聚合數(shù)據(jù)模型Key-valueDocumentColumn

FamilyGraph3.1鍵值存儲鍵用于訪問不透明的一團(tuán)數(shù)據(jù)值可以包含任意類型的數(shù)據(jù)(images,video)Pros:scalable,simpleAPI(put,get,delete)Cons:nowaytoquerybasedonthecontentofthevalue/*Query1*/SELECTageFROMusersWHEREid=1;/*willread21*/

3.1.1鍵值數(shù)據(jù)模型只有兩列Key/Value的表Value列沒有數(shù)據(jù)類型約束接口簡單Addakey-valueForthiskey,givemethevalueDeleteakey特別快而且易于擴(kuò)展(nojoins)3.1.2儲物柜比喻3.1.3類似于辭典單詞“gouge”就是“鍵”內(nèi)容和圖片就是“值”3.1.3沒有子集查詢3.1.4鍵值存儲的類型Eventually‐consistentkey‐valuestoreHierarchicalkey‐valuestoresKey-ValuestoresinRAMKey-ValuestoresondiskHighavailabilitykey-valuestoreOrderedkey‐valuestoresValuesthatallowsimplelistoperations3.2列族模型一種特殊的Key-Value存儲Key包括行標(biāo)識、列族和列名保持了Key-Value存儲的一般特性，而且提供了更高級的數(shù)據(jù)抽象和訪問接口行和列的設(shè)計(jì)非常重要但是相對于RDBMS來說，還是容易得多3.2.1Row/Column鍵(Bigtable)3.2.2特定語義的鍵Bigtable系統(tǒng)中的Key可以不僅有行和列ID還有其他屬性，列族和時間戳列族在創(chuàng)建表的時候創(chuàng)建時間戳(Timestamps)允許存儲不同版本的數(shù)據(jù)Value僅僅是一個字節(jié)序列，沒有強(qiáng)類型3.2.3列族存儲概念保留了與RDBMS類似的表結(jié)構(gòu)沒有針對JOIN的優(yōu)化可以大量的行和列，但是行的列可以不同列族允許查詢具有相同特性(組)的所有行插入新的列不需要"altertable"在插入時觸發(fā)增加列3.2.4列族將一組列組成列族(Columnfamilies)將一組列族組成超列(Super-Columns)允許以超列和列族進(jìn)行查詢相似的數(shù)據(jù)組合在一起，以提高訪問速度3.3文檔存儲數(shù)據(jù)存儲為嵌套層次結(jié)構(gòu)邏輯數(shù)據(jù)依然作為一個單元存儲在一起可以查詢文檔中得任意元素排除了ORM的需要，易于搜索實(shí)現(xiàn)復(fù)雜，與SQL不兼容3.3.1文檔數(shù)據(jù)模型將一份機(jī)器可讀的文檔作為一組數(shù)據(jù)存儲在一起使用JSON或者XML格式類似于對象存儲(objectstores)不需要將數(shù)據(jù)分割(Noshredding)為多張表文檔的子樹和屬性可以用Xquery或者其它語言查詢甚至可以包括ACID事務(wù)的支持脫離ORM，較好地支持敏捷開發(fā)3.3.2文檔存儲的收益3.3.3文檔結(jié)構(gòu)3.3.4模型比較一個容器包含了所有詞語內(nèi)容分析需要大量、復(fù)雜的算法關(guān)鍵詞已經(jīng)分解成了各個子文檔成分3.1.5KeywordsandNodeIDs使用倒排索引，將關(guān)鍵詞與每個文檔的每個node-id關(guān)聯(lián)起來3.4圖存儲數(shù)據(jù)存儲為一系列節(jié)點(diǎn)、關(guān)系和屬性查詢是圖遍歷數(shù)據(jù)之間的關(guān)系是關(guān)鍵e.g.socialnetworks支持快速地網(wǎng)絡(luò)搜索圖太大時，可擴(kuò)展性不好特殊的查詢語言(RDF使用SPARQL)3.4.1龐大的社會網(wǎng)絡(luò)3.4.1開放鏈接數(shù)據(jù)3.4.2圖模型適用于數(shù)據(jù)項(xiàng)的關(guān)系以及關(guān)系類型非常重要的場合社會網(wǎng)絡(luò)查詢："friendsofmyfriends"推理和規(guī)則引擎模式識別適合開放鏈接數(shù)據(jù)公開數(shù)據(jù)的自動連接(joins)3.4.3屬性圖中的每個節(jié)點(diǎn)和邊都有一組Key/Value對，即屬性Thanks！高級數(shù)據(jù)庫及大規(guī)模存儲技術(shù)NoSQL的技術(shù)基礎(chǔ)及其實(shí)踐BASE事務(wù)模型AgendaCAP原理BASE模型一致性問題1.1

ACID語義Atomicity:Allornothing.Consistency:Consistentstateofdataandtransactions.Isolation:Transactionsareisolatedfromeachother.Durability:Whenthetransactioniscommitted,statewillbedurable.任何存儲都可以獲得原子性、格里性和持久性，但是我們會一直需要一致性？No！可以通過放棄ACID特性，以達(dá)到更高性能和可伸縮性1.2

CAP定理AlsoknownasBrewer’sTheorembyProf.EricBrewer,publishedin2000atUniversityofBerkeley.“Ofthreepropertiesofashareddatasystem:dataconsistency,systemavailabilityandtolerancetonetworkpartitions,onlytwocanbeachievedatanygivenmoment.”ProvenbyNancyLynchetal.MITlabs./~brewer/cs262b-2004/PODC-keynote.pdf1.3

CAP語義1.3

CAP語義Consistency任何節(jié)點(diǎn)在同一時刻看到的數(shù)據(jù)是一樣的Availability每個請求都會得到一個是否成功地響應(yīng)PartialTolerance由于網(wǎng)絡(luò)失效，數(shù)據(jù)劃分成跨越網(wǎng)絡(luò)的片段盡管消息丟失或者系統(tǒng)部分失效，系統(tǒng)依然能夠運(yùn)轉(zhuǎn)159

1.3.1

ConsistencyDBnode1DBnode2Client1Client2readaccountXbalance->100setaccountXbalance=0setaccountXbalance=0setaccountXbalance=0setaccountXbalance=0160

1.3.2

AvailabilityDBnode1DBnode2Client1Client2readaccountXbalance->100setaccountXbalance=0setaccountXbalance=0setaccountXbalance=0readaccountXbalance->100setaccountXbalance=0Happycustomerwalksaway,richerby200.Serverseventuallyagreebalanceis0.1.3.3網(wǎng)絡(luò)失效問題IP網(wǎng)絡(luò)會面臨所有情況TCP網(wǎng)絡(luò)duplicate、reorderDrop是一種特殊的delay完全的失效檢測是不可能的1

“ImpossibilityofDistributedConsensuswithOneFaultyProcess”,Fischer,LynchandPaterson1.4證明（1）Let’sconsiderasimplesystem:ServiceAwrites

valuesServiceBreads

valuesValuesarereplicatedbetweennodesTheseare“ideal”systemsBug-free,predictableNode1V0ANode2V0B1.4證明（2）“Sunnydayscenario”:Awrites

anewvalueV1Thevalueisreplicated

tonode2Breads

thenewvalueNode1V0ANode2V0BV1V1V1V11.4證明（3）Whathappensifthenetworkdrops?Awrites

anewvalueV1ReplicationfailsBstillseestheoldvalueThesystemisinconsistentNode1V0ANode2V0BV1V0V11.4證明（4）PossiblemitigationissynchronousreplicationAwritesanewvalueV1Cannotreplicate,sowriteisrejectedBothAandBstillseeV0ThesystemislogicallyunavailableNode1V0ANode2V0BV1CAPSemanticsConsistency:StrictConsistency–RDBMS.TunableConsistency–Cassandra.EventualConsistency–AmazonDynamo.2.BASE語義BasicallyAvailable:分布式環(huán)境下地節(jié)點(diǎn)可以失效，但是整個系統(tǒng)不會受到影響SoftState(scalable)系統(tǒng)的狀態(tài)和數(shù)據(jù)會隨時間而變化EventualConsistency給定足夠的時間，數(shù)據(jù)會在跨越分布系統(tǒng)的節(jié)點(diǎn)間取得一致2.1

ACID

vs.BASEACID強(qiáng)一致性稍弱的可用性悲觀的并發(fā)控制策略復(fù)雜BASE可用性是最重要的更弱的一致性盡力簡單快速樂觀的并發(fā)控制策略2.2分布式事務(wù)兩段式提交2PC可能的失效網(wǎng)絡(luò)失效數(shù)據(jù)庫失效分布式3PC模型問題:一個節(jié)點(diǎn)失效，可能鎖住整個集群可以使用超時機(jī)制，超時判定帶來了事務(wù)延遲可能使用Quorum.Quorum在分布式環(huán)境下，如果存在分區(qū)，由節(jié)點(diǎn)投票決定提交或者回滾CoordinatorCommitCompleteoperationReleaselocksAcknowledgeRollback2.2.12PC問題客戶沒有收到Ack？系統(tǒng)處于不一致狀態(tài)inconsistentstateClient如果采取了不當(dāng)?shù)奶幚泶胧?，會進(jìn)一步加劇不一致的局面ClientServerCommitStoreAck?2.2.2分布式2PC的示例171clienttransactioncoordinatorbankAbankBstartresultpreparepreparerBrAoutcomeoutcomeIfrA==yes&&rB==yesoutcome=“commit”elseoutcome=“abort”Bcommitsuponreceiving“commit”Lossofavailabilityandhigherlatency!Locked2.3選擇NoSQL解決方案2.3.1

Consistent,Available(CA)CA-systemshavetroublewithpartitionsanddealwithitwithreplication.ExamplesMySQL(relational)AsterData(relational)Greenplum(relational)Vertica(column)2.3.2

Availability,Partition-Tolerant(AP)AP-systemshavetroublewithconsistency,achieve“eventualconsistency”throughreplication.ExamplesCassandra(column/tabular)Dynamo(key-value)Voldemort(key-value)TokyoCabinet(key-value)CouchDB

(document)SimpleDB

(document)Riak

(document)2.3.3

Consistent,Partition-Tolerant(CP)CP-systemshavetroublewithavailabilitywhilekeepingdataconsistentacrosspartitionednodes.ExamplesMongoDB

(document)BigTable

(column/tabular)HyperTable

(column/tabular)Hbase

(column/tabular)Redis

(key-value)Scalaris

(key-value)MemcacheDB

(key-value)3一致性問題ABC3.1一致性強(qiáng)度StrongConsistencyWeakConsistencyEventualConsistencyCausalConsistencyRead-your-writes

ConsistencySessionConsistencyMonotonicRead

ConsistencyMonotonicWrite

Consistency3.1.1

強(qiáng)一致性在更新之后，所有的后續(xù)訪問都必須返回更新值3.1.2弱一致性系統(tǒng)不保證在后續(xù)的任何時候訪問中都能返回更新值3.1.3最終一致性如果沒有更新操作，系統(tǒng)保證最終所有的訪問都能返回最后的更新值3.1.4因果一致性后續(xù)對B的訪問可以返回更新值，而且系統(tǒng)保證會有一個寫操作完成對原有值的替換3.1.5

Read-Your-Writes一致性進(jìn)程A永遠(yuǎn)都會看到自己更新的值，不會是原有值3.1.6會話一致性在一次會話中，系統(tǒng)保證Read-Your-Writes一致性3.1.7單調(diào)讀一致性如果一個進(jìn)程看到了一個對象的部分值，那么后續(xù)的訪問中不會返回以前的值3.1.8單調(diào)寫一致性系統(tǒng)保證同一進(jìn)程的寫順序是一致的3.2最終一致性系統(tǒng)預(yù)計(jì)數(shù)據(jù)會發(fā)生分歧但是包含了一些機(jī)制重獲收斂(convergence)部分排序最小化沖突合并功能消解沖突3.2.1可伸縮性帶來的網(wǎng)絡(luò)分區(qū)問題？3.2.1選擇在性能和成本要求驅(qū)動下，系統(tǒng)必須具有可伸縮性可伸縮系統(tǒng)的網(wǎng)絡(luò)分區(qū)必然的P固定的情況下，必須在A和C之間進(jìn)行取舍3.2.2最終一致性的設(shè)計(jì)目標(biāo)更傾向于可用性但是也保證，客戶可以最終得到一致的結(jié)果git:局部總是可用的push/pull來收斂由人來決定沖突消解方案3.2.3

RDBMS的最終一致性3.2.4NRWN存儲數(shù)據(jù)副本的節(jié)點(diǎn)數(shù)目W在更新結(jié)束前，需要確認(rèn)接受更新的副本數(shù)目R在讀操作訪問數(shù)據(jù)對象時，需要聯(lián)系的副本數(shù)目W+R>N

強(qiáng)一致性3.2.4.2優(yōu)化讀優(yōu)化R=1

N=W寫優(yōu)化W=1

N=R3.2.5典型的分布式模型3.2.6不變數(shù)據(jù)不變：不會隨時間變化，也不可變更

不可刪除不可更新不存在合并沖突復(fù)制是平凡而容易實(shí)施的3.2.7冪等操作冪等操作:實(shí)施一次或者多次，都會產(chǎn)生相同的效果可以重試不是總有可能副作用是否存在？VectorClocks部分排序技術(shù)，時間戳不足以解決問題每個節(jié)點(diǎn)維持一個邏輯鐘logicalclock每次寫得時候鐘向前走一步對每個數(shù)據(jù)項(xiàng)記錄最后觀察(observed)到的時鐘在副本中包含這個向量（<節(jié)點(diǎn)，時鐘>對）如果觀察到的向量和入境的向量沒有共同的祖先，那么就存在沖突可以知道何時發(fā)生了分歧VectorClocks:Example11

“WhyVectorClocksAreHard”,JustinSheehyontheBashoBlogCommutativeReplicatedDataTypes1可交換復(fù)制的數(shù)據(jù)類型最終收斂到一致的狀態(tài)保證副本的無沖突1

“AcomprehensivestudyofConvergentandCommutativeReplicatedDataTypes”,ShapiroetalCRDTsCRDTsprovidespecializedsemantics:G-Counter:MonotonouslyincreasingcounterPN-Counter:AlsosupportsdecrementsG-Set:Asetthatonlysupportsadds2P-Set:SupportsremovalsbutonlyonceOR-SetsareparticularlyusefulKeepstrackofbothadditionsandremovalsCanbeusedforshoppingcarts高級數(shù)據(jù)庫及大規(guī)模存儲技術(shù)NoSQL的技術(shù)基礎(chǔ)及其實(shí)踐MapReduce計(jì)算模型AgendaMapReduce簡介工作原理基本組件另外的聲音1MapReduce編程模型1.1并行體系結(jié)構(gòu)的分類1.2MapReduceAsharednothingarchitectureforprocessinglargedatasetswitha

parallel/distributedalgorithmonclustersofcommodityhardware.1.3應(yīng)對挑戰(zhàn)怎樣將計(jì)算進(jìn)行分布如何讓分布式編程更加容易？如何對待機(jī)器失效？1.4好主意

?

網(wǎng)絡(luò)上大規(guī)模的數(shù)據(jù)復(fù)制產(chǎn)生大量開銷讓計(jì)算靠近數(shù)據(jù)數(shù)據(jù)可以存儲多份，支持可靠性1.5簡單性不再擔(dān)心并行化、容錯、數(shù)據(jù)分布和負(fù)載均衡MapReduce自己去關(guān)心對程序員隱藏系統(tǒng)級別的細(xì)節(jié)2.1MapinLisp(Scheme)(mapf

list[list2list3…])(mapsquare‘(1234))(14916)(reduce+‘(14916))(+16(+9(+41)))30(reduce+(mapsquare(map–l1l2))))UnaryoperatorBinaryoperator2.2基本假設(shè)需要大量的計(jì)算機(jī)(可伸縮)對輸入的兩個基本操作MapReduce2.3DistributedGrepVerybigdataSplitdataSplitdataSplitdataSplitdatagrepgrepgrepgrepmatchesmatchesmatchesmatchescatAllmatches2.4熱身

(1/2)有一個巨型的文本文檔計(jì)算文件中每個單詞出現(xiàn)的次數(shù)應(yīng)用：分析web服務(wù)器的日志尋找最頻繁訪問的URLs.2.4熱身(2/2)文件太大，超出的內(nèi)存的存儲能力但是內(nèi)存可以容納所有的<word,count>對words(doc.txt)|sort|uniq-cwords例程對文件進(jìn)行格式化，一行一個單詞這個任務(wù)抓住了MapReduce的本質(zhì)：greatthingisthatitisnaturallyparallelizable.大事自然是可并行化的2.5MapReduce方案words(doc.txt)|sort|uniq-c順序讀入大量數(shù)據(jù)Map:抽取關(guān)心的數(shù)據(jù)按照關(guān)鍵字分組:sortandshuffle.Reduce:聚集計(jì)算,概括,過濾，或者變換輸出/寫結(jié)果2.5.1MapReduceDataflowmap函數(shù)：處理數(shù)據(jù)，并產(chǎn)生一組中間結(jié)果鍵值對reduce函數(shù)：

將中間結(jié)果中相同“鍵”的所有中間結(jié)果值進(jìn)行合并2.5.2Example:WordCount使用MapReduce對下面的文件進(jìn)行單詞計(jì)數(shù)：HelloWorldByeWorldHelloHadoopGoodbyeHadoop2.5.3單詞計(jì)數(shù)——mapmap函數(shù)一次讀一個單詞，而且為每個解析出的單詞輸出一個(word,1)map函數(shù)的輸出是：(Hello,1)(World,1)(Bye,1)(World,1)(Hello,1)(Hadoop,1)(Goodbye,1)(Hadoop,1)2.5.4單詞計(jì)數(shù)——shuffle在map和reduce階段之間，shuffle階段為每個“鍵”建立一個值列表shuffle的輸出/reduce函數(shù)的輸入是：(Bye,(1))(Goodbye,(1))(Hadoop,(1,1))(Hello,(1,1))(World,(1,1))2.5.5單詞計(jì)數(shù)——reducereduce函數(shù)對每個“鍵”的值列表進(jìn)行求和計(jì)算輸出(word,count)對reduce函數(shù)的輸出是：(Bye,1)(Goodbye,1)(Hadoop,2)(Hello,2)(World,2)2.5.6單詞計(jì)數(shù)——Combiner(1/2)在很多情況下，map任務(wù)產(chǎn)生的中間鍵值對中有大量的重復(fù)，而且reduce函數(shù)通常具有交換律（commutative）和結(jié)合律（associative）.Machine1:(Hello,1)(World,1)(Bye,1)(World,1)Machine2:(Hello,1)(Hadoop,1)(Goodbye,1)(Hadoop,1)CombinerFunction(2/2)可以使用一個combiner函數(shù)對中間結(jié)果進(jìn)行合并，以減少網(wǎng)絡(luò)開銷combiner和reduce一般是一樣的滿足交換律和結(jié)合律Machine1:(Hello,1)(World,2)(Bye,1)Machine2:(Hello,1)(Hadoop,2)(Goodbye,1)2.5.7Map+ReduceMap:Acceptsinputkey/valuepairEmitsintermediatekey/valuepairReduce:Acceptsintermediatekey/value*pairEmitsoutputkey/valuepairVerybigdataResultMAPREDUCEPartitioningFunction2.6函數(shù)式編程的根源Map(S:array,f())Applyf(s∈S)forallitemsinSFold(S:array,g())Recursivelyapplyg()toeachiteminSandtheresultofthepreviousoperation,ornilifsuchanoperationdoesnotexist2.7MapReduce程序員編寫兩個函數(shù):map(k1,v1)→[<k2,v2>]reduce(k2,[v2])→[<k3,v3>]所有具有相同“鍵”的“值”都發(fā)送給同一個reducer執(zhí)行框架處理所有事情，除了…2.7.1MapReduce圖示2.8MapReduce

“Runt