《高级数据库及大规模存储技术》全册配套课件

《高级数据库及大规模存储技术》全册配套课件高级数据库及大规模存储技术NoSQL的技术基础及其实践课程简介1.教学目的课程学习和课下实践理解云计算环境的数据存储和应用特性非关系型数据库的数据管理方法及其关键技术完成典型平台的构建、部署和一般管理使用计算机编程语言编写数据操作及其上的应用。2.主要内容NoSQL概念及原理NoSQL的外延MapReduce计算模型HBaseMongoDB数据层的设计技术3.课程要求数据库原理程序设计JavaScriptJava/Scala/Python面向服务概念HTTP协议Restful4.成绩课程实验60%计算共享独立完成课程考试40%两次考试，Middle和Final各20%5.ContactUS尹俊文国防科学技术大学计算机学院Email：jwyin_cn@163.comMobile:136073142606.教材1、NoSQL精粹塞得拉吉(PramodJ.Sadalage)(作者),福勒(MartinFowler)(作者),爱飞翔(译者)，机械工业出版社，2013年9月，ISBN:978-7-111-43303-36.教材2、Hadoop实战，ChuckLam(作者),韩冀中(译者)，人民邮电出版社，2011年10月，ISBN:978-7-115-26448-06.教材3、HBase实战，迪米达克(NickDimiduk)(作者),卡拉纳(AmandeepKhurana)(作者),谢磊(译者)，人民邮电出版社，2013年9月，ISBN:978-7-115-32446-77.参数书目2、MongoDB权威指南(第2版)，霍多罗夫(KristinaChodorow)(作者),

邓强(译者),王明辉(译者)，人民邮电出版社，2014年1月，ISBN:97871153410827.参数书目高级数据库及大规模存储技术NoSQL的技术基础及其实践NoSQL简介1.1TheEmergenceofNoSQL最早的NoSQL名词出现在1990s，是一个开源关系数据库项目用ASCII文件存储数据表CarloStrozzi不以SQL作为查询接口2006年9月组织的Meetup，给Twitter发起一个话题，易于记忆，比较醒目（被Google收录少）聚集BigTable和Dynamo催生的项目EricEvan建议使用NoSQLWho’sUsingNoSQL?1.2WhatisNoSQL?NoSQLisasetofconceptsthatallowstherapidandefficientprocessingofdatasetswithafocusonperformance,reliability,andagility.1.3WhatareNoSQLincludes不仅仅是行记录结构join-freeschema-free多处理器集群环境采用什么都不共享的货架计算机支持横向线性扩展开源创新1.4WhatareNoSQLdoseNOTincludeIt’snotabouttheSQLlanguageIt’snotonlybigdataIt’snotaboutcloudcomputingIt’snotaboutacleveruseofRAMandSSDIt’snotanelitegroupofproducts2NoSQL的业务驱动因子单节点RDBMS数据量敏捷性可变性速度2.1数据量(Volume)驱动因子大数据量处理始终是推动体系结构变革的关键因素在2005年，处理器处理速度的增长遇到了瓶颈——PowerWall大规模数据处理推动了：大规模并行计算、分布式计算、及其组合（超级计算）Web1.0

ReadIntensiveWebWeb2.0

WriteIntensiveWeb数据量的增长TheAgeofBigData

Exabytes(1018)ofdatastoredperyearBigDatasets

(Data-RichComputingthemeproposal.J.Campbell,etal,2007)2.2速度(Velocity)驱动因子尽管大数据问题可以通过并行计算得到缓解，单处理器的读写速度仍然很关键目前单处理器RDBMS系统的通用性解决方案无法应对当前新型的Web应用场景应用的使用模式是什么？2.3可变性(Variability)驱动因子应用的可变性任何新型的应用总是会带来新的数据类型是否应该严格遵守模式规范？关系模型如何应对数据类型的变化？2.4敏捷性(Agility)驱动因子应用的敏捷性在敏捷软件开发方法的带动下，开源社区出现了新的的结构和技术：多层软件体系结构测试优先连接池对象关系映射这些技术很多都是为了应对新型应用模式对RDBMS的需求2.5计算机领域的一般问题通用性和灵活性、性能的矛盾下层的机制约束了上层采用的策略上层的优化方法：隧道：绕开底层机制过设计上层不断增长的需求特性导致下层设计的无限膨胀3NoSQL的典型案例案例/标准动机发现LiveJournal’s

Memcache提高数据库查询的性能使用hashing和caching，RAM中的数据可以共享。

通过减少发送到数据库读请求的数量来提高性能Google’sMapReduce使用低成本硬件，对亿数量级的网页进行搜索索引使用并行处理，可以利用大量货架处理器快速完成亿数量级的网页索引Google’sBigtable在分布式系统中灵活存储表格数据(tabularData)使用稀疏矩阵方法，无需预先建模，也可以让用户感觉到所有数据都存储在一张有亿级别数量行的表中Amazon’sDynamo接受7×24小时的web订单即使有大量的数据需要处理，也可以复制具有简单接口的key-value存储MarkLogic使用标准查询语言，查询存储在货架硬件上的大量XML文档集合货架服务器存储XML文档索引，将查询分布到这些服务器，每个服务器可以负责处理自己本地盘上的数据，然后将结果返回给查询服务器3.1LiveJournal’s

MemcacheLiveJournal是一个Blog系统将最常用的数据库查询结果保留在RAM中若干服务器可能持有同一查询的相同结果使用Memcache协议，交互持有查询结果的情况Memcache成了一种查询结果重用的前端工具不仅仅用于数据库查询处理3.2Google’sMapReduceNoSQL社区中最具影响力的项目之一开启了MapReduce广泛应用之门输入数据MapMapMapShuffleSortReduce查询结果3.3Google’sBigtableBigtable是google发布的另一个有影响的项目网络爬虫分解出了大量网页、图像、视频等媒体，它们无法进行关系建模一个有1亿行1亿列的表3.4Amazon’sDynamo相对于Bigtable关注大规模批处理，Dynamo更致力于系统的可扩展能力在复制、故障处理上给出了合理的解决方案4NoSQL的生态系统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高级数据库及大规模存储技术NoSQL的技术基础及其实践关系模型的分析1数据体系结构模式

dataarchitecturepattern如何存储一张表格？更复杂的表格怎么办？表格可以解决所有的问题吗？？1.1数据体系结构模式模式：对一个问题存在的已知的解决方案数据结构模式：一种如何存取大量数据的解决方案1.2行存储(rowstore)行是数据存取的原子单位1.3RDBMS设计模式基于关系模型的建模面向表的数据定义语言(DDL)基于关系代数的数据操作语言(DML)基于JOIN的数据关联支持数据完整性的trigger机制面向重用的storedprocedure机制1.4RDBMS的价值数据持久化并发访问标准成熟应用集成1.4.1数据持久化RDBMS提供了一种有效组织数据的方法RDBMS填补了文件系统在大规模数据管理方面的缺陷随着个人计算机持有存储器容量的增长，文件系统已经不能满足大量个人信息的组织要求RDBMS为快速、方便获取信息提供了有效的支持1.4.2并发访问细粒度的数据管理是共享的必要基础条件粗粒度的文件共享是很罕见的，也是不情愿的共享也就带来了并发访问问题操作系统和数据在研究这类问题上的研究是共用的但是操作系统领域研究共享问题略显矫情虽然在这个领域出现了很多的并发控制机制，但是事务和锁机制在RDBMS中证明了自己的有效性1.4.3标准成熟标准的SQL使得应用可以在不同的RDBMS之间移植成熟的ACID事务模型使得应用开发更加得心应手成熟的开发技术降低了软件开发成本成熟的数据建模方法成熟的SQL编程方法成熟的软件体系结构成熟的软件构件与框架1.4.4应用集成虽然SOA是目前最热门的集成技术，但是数据集成是最常用和最成熟的应用集成技术以OLAP、OLTP为基础的集成技术成为企业ERP的主力数据库甚至可以作为进程间通信的手段接口集成数据集成界面集成2RDBMS的实现技术事务DDL和强类型列安全和访问控制复制和同步2.1事务机制Atomicity,Consistency,Isolation,DurabilityBEGINTRANSACTION/COMMIT/ROLLBACK通常使用LOCK机制实现严格的ACID严重影响并发能力，可能死锁隔离级别：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不可重复读/*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和强类型列物理模型要求预想定义表中所有列的名字、类型约束、以及索引和关系这样的强类型约束为数据正确性验证提供了支持，可以避免数据的质量下降问题在数据类型需要改变时，引起了问题：或者使用一个新的列存储数据或者采用一种更灵活的数据类型前者会使得数据列越来越多，而原有列成了死列后者将使得强类型形同虚设2.3安全和访问控制RDBMS提供了对表和视图进行安全控制的机制视图是在RDBMS上实现行级和列级数据进行访问控制的有效手段2.4复制和同步RDBMS通常使用log文件保证关键数据的存储log文件会降低系统性能，而且log主要用于保证事务的正确性主从数据库模式的集群系统是提高数据库系统可用性的一种手段集群数据库系统引入了复制机制可用性问题可以在消息系统级别和存储系统级别得到保证复制机制带来了分布式系统中的经典问题：一致性保证（同步）3RDBMS的难题关键字去规范化SQL技巧存储过程和触发器应用设计3.1关键字问题业务关键字和数据关键字不满足BCNF的业务关键字是常见的身份证号码业务关键字可能发生变化学号需要变化吗？业务关键字可能影响性能组合关键字变长字符串课本上讲的有点忽悠人3.2去规范化物理设计时为了提高性能、完整性和可维护性所采用的方法使用几张表格？表格中的列是否需要冗余？你如何设计一个机构层次表？3.2.1去规范化技巧StoringDerivableValuesPre-joiningTablesHard-CodedValuesKeepingDetailswithMasterRepeatingSingleDetailwithMasterShort-CircuitKeys3.3SQL技巧SQL的编写需要技巧如何动态拼接一个查询语句？大量的SQL技巧用于解决层出不穷的查询问题复杂查询的支持通常需要特殊的数据库设计是使用复杂的SQL语句，还是采用复杂的程序？是使用复杂的查询语句，还是使用视图？3.4存储过程和触发器如何正确使用存储过程如何恰当使用触发器3.5应用设计数据层数据访问模式数据库设计重构4新型应用OLAP/OLTP主动(Active)数据库演绎(Deductive)时态(Temporal)数据库4.1OLAP/OLTP4.1OLAP/OLTP星形体系结构多维数据模型MDX查询语言聚集计算4.2ActiveDatabase业务智能，主动处理主动规则和主动行为SQL99支持利用Trigger可以实现规则语言和规则管理问题4.3DeductiveDatabases将数据库技术和专家系统合并事实、规则和完整性约束数据的表示问题数据操作语言SQL不再完全适用查询处理算法需要特殊设计4.4TemporalDatabase包含历史数据的数据库系统数据具有timestamp特性与时间相关的数据操作和聚集计算数据的水平分解和垂直分解数据的存储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.高级数据库及大规模存储技术NoSQL的技术基础及其实践聚合数据类型Agenda对象关系映射领域驱动的聚合设计聚合数据模型1对象关系映射指不兼容面向对象编程语言的类型系统之间进行数据转换的技术对象模型和关系模型存在着固有差异可以在若干层次解决问题：语言库级别数据库级别Hibernate是典型的ORM框架面向对象数据库和NoSQL是数据库级别的解决方案1.1数据访问模式大多数业务应用主要考虑CRUD对磁盘的读写分层提供了组织这种逻辑的方法根据目的或主题将逻辑集中起来一站式购物(“1stopshopping”)1.1.2数据管理层持有持久存储的数据模型Dataentities(i.e.tables)Datatypes(i.e.columns)Datarelations(i.e.referentialintegrity)Dataintegrity(i.e.checkconstraints,triggers,etc.)管理对数据模型的读写执行SQL语句或者存储过程根本上确保所支持的ACID原则1.1.3数据模型的设计决定技术Normalizationvs.DenormalizationHorizontalandVerticalPartitioningMaterializedViews，……数据模型考虑的是如何最佳存取数据1.1.4对数据模型的观察随着时间的推移，可能发生变化可能服务于多个应用系统设计应该具有改变数据模型的灵活性将数据模型变化对其他层次的影响减小到最少(i.e.计入降低各层之间的耦合度)易于找到受到数据模型变化影响的代码1.1.5数据访问层知道数据源的标识知道如何连接数据管理层知道如何实现CRUD运用SQL和存储过程可能有，也可能没有具体的层次通常表现为一组“数据访问对象”DALlogic通常出现在领域对象

(DomainObjects)中1.1.6领域模型层领域对象标识问题域的实体e.g.Customer,Order,Vendor管理临时状态调用数据访问操作强制数据验证执行业务规则定义领域中实体之间的关系1.1.7领域模型的设计DataModel!=DomainModel数据模型定义数据如何存放数据模型的实际是最优地支持数据读写和完整性领域模型定义数据如何使用集成和多态扮演着重要角色领域模型和数据模型的松耦合可以出尽它们各自独立的演化1.2阻抗失配

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

Object-relationalimpedancemismatch90年代，面向对象数据库风靡一时，但是随着面向对象语言的崛起，面向对象数据库反而日渐式微面向关系数据库抓住了机会，强化了在计算机软件中作为集成机制的角色，分离了应用开发人员和数据库管理员两种角色。面向对象范式基于软件工程原理，而关系范式基于数学原理1.3OO与OR的差异数据类型差异鼓励/禁止传引用字符串差异结构和完整性差异对象组装/类继承机制是OR不具备的OR的声明式约束方式OO通常采用保护逻辑报异常的方式，或采用面向方面方法设计操作差异OR采用基于元组的原语操作OO采用底层的物理访问路径相关的命令式操作事务性差异OO语言没有类似隔离性和持久性概念1.3.1粒度(Granularity)差异对象模型中类数量和关系数据库中表的数目通常是不同的publicclassTeacher{}publicclassSchool{}1.3.2子类型差异(Subtypes(inheritance))继承是面向对象编程语言中得自然泛型，但是RDBMS不支持这个概念HumanManWomanInheritance1.3.3关联与数据导航实体关联通过外关键字对象关联通常是单向的部分出现在整体中部分对整体的应用并不常见Classuser_main{Teacherteacher;}ClassTeacher{}1.3.4数据类型差异字符串数据类型是典型的例子在RDBMS中字符串具有长度，尾部空格通常没有含义一般的面向对象语言字符串没有长度限制对象世界和关系世界的Date和time存在很大差异为了避免不必要的麻烦，有的应用在RDBMS中使用字符串类型标识Date和Time1.3.4数据类型差异1.3.5OR与OO的概念差异声明和命令接口OR视数据为接口，OO视行为为接口活动和实体之间的关系OR分离了实体与行为结构与行为基于集合论的OR，基于图论的OO对象范式与关系范式1.4

对象关系映射

一种现实的解决方案ORM桥接OO和OR为应用提供面向对象的数据访问接口Value

Object和Data

Access

Object成为主要的设计模式1.4.1

ORM组件模型MappingReflection,ProjectionandHydrationSQLQueryBuilderFetchingCachingandpersistenceSettings1.4.1MappingStorageModelConceptualModelMappingModel使用XML描述模型之间的映射关系Java

Annotation是另外的形式1.4.2Reflection

andProjection

1.4.3SQLQueryBuilder1.4.4Fetching是否需要在装载一个对象时，将其所有成员一起装载？lazyloading.Lazyloading是一种设计模式按需装载的意思只有在需要的时候才装载/初始化对象Lazyloading

Levels列级别关联级别1.4.5CachingandOptimizations缓存动态生成查询，不需要每次重建缓存避免了对数据源的重复调用查询优化处理环形引用处理层叠(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类映射到关系表支持一对多和多对多关系的映射支持自定义数据类型的映射Enum、一个属性映射到多个列支持QBE、QBA、QBL（HQL）查询支持POJO的透明持久化1.5.3MyBatis/iBATIS不将Java对象映射到关系表，而是将Java方法映射到SQL语句在应用端实现数据库中存储过程、视图和查询等机制提供一种将查询结果映射到对象树的机制2聚合来源于“领域驱动设计”它是作为一个单位进行处理的相关对象集合，特别是数据操作和一致性管理的单位使用源自操作来更新聚合，以聚合的形式与数据存储进行通信数据库可以将聚合作为复制和分片的单元2.1.1关系数据模型实例2.1.2关系存储的数据2.1.3聚合数据模型实例2.1.4聚合数据表示//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更内聚的聚合2.1.6聚合数据//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面向聚合的数据访问不是划分聚合边界，而是规划数据访问方式从领域角度看待数据易于将聚合数据分离在不同节点面向聚合不再支持ACID的事务大多数源自操作局限在聚合内部一般不支持跨越聚合边界的ACID事务2.2.1基于ORM的数据访问模式T1–HTMLintoJavaObjectsT2–JavaObjectsintoSQLTablesT4–TablesintoObjectsT3–ObjectsintoHTML2.2.2增加了Web

Service的数据访问T4–ObjectsintoHTMLT5–ObjectstoXMLT6–XMLtoObjectsT1–HTMLintoJavaObjectsT2–JavaObjectsintoSQLTablesT3–TablesintoObjects2.2.3

ORM陷入沼泽对象到表的映射问题模式所有权（Schema-Ownership）冲突双向模式(Dual-Schema)问题实体标识问题数据检索接口问题部分对象问题和装载时间悖论2.2.4是否真的需要RDBMS?大多数ORM都是与RDBMS紧耦合的范式扼杀了Web应用范式的目标是让数据尽可能地小Web应用的目标是尽可能地快具有广泛用户的Web应用都没有遵循3范式的Web应用受到性能压力会快速降低到更低范式(denormalization).RESTfulAPIs典型地适用于与单表应用/api/:resource/:id2.2.5可能需要的就是Key-Value存储不要奢望同时达到通用化和高性能如果确定使用一个特殊的数据库，应该按照数据库的特性优化应用对于一些特殊用例，直接访问数据库是一种最佳实践WikiMediaexample-directaccesstoMySQLandPostgreSQL

相对于RDBMS，Key-value存储可能更适合Web应用²适合复杂类型的JOIN操作不要用RDBMS实现key-value存储如果数据库足够快，不要使用cacheDon'tshardyourself.³2.2.5基于Key/Value的存储2.2.5一种特殊的Key/Value存储列族存储2.2.5基于引用的模型2.2.5标识引用关系的模型图存储2.2.6文档存储不需要翻译DocumentsinthedatabaseDocumentsintheapplicationNoobjectmiddletierNo"shredding”NoreassemblySimple!2.2.7零翻译

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

WebApplicationArchitectureNotranslation!2.3无模式数据库系统在数据装载到数据库的时候，自动决定如何索引数据不需要数据结构的先验知识不需要预先的逻辑数据建模数据模型依然存在，但是隐含在处理逻辑中2.3.1无模式数据的集成更易于存储实际得到的数据，而不是我们想我们可能得到的数据“Wecaneasilystorethedatathatweactually

get,notthedatawethought

wewouldget."2.3.2不再需要预先的ER建模不需要在插入第一条记录之前完成建模不需要数据定义语言元数据用于在数据到达时穿件索引建模编程了一个统计过程——编写查询来寻找异常或者规格化数据异常制造规则数据验证通常利用一些特殊工具来实现，例如XMLSchema、业务规则系统Schematron

2.3.3模式数据库的优势全局数据定义预先定义数据类型及其关系查询更有效可以根据数据类型、列值和关系类型约束行为优化访问用于确定如何最优存储、管理和访问特定数据类型易于QueryByExample，展示可用信息类型信息之间的关系2.3.3

模式数据库的优势互操作适应语言和环境控制模式的改变保持应用和数据的同步一致的安全控制2.3.4模式数据库的劣势模式需要维护应用要保持与模式的同步应用关心数据类型缺少特殊应用所需的灵活性2.3.5无模式数据库的优势灵活可以将任意类型的数据持久化可以创立任意类型的关系对数据的寻找不再关心数据类型可以容忍不同的ACID和一致性易于使用和维护不需要专职的DBA新型数据出现后应用也可以工作增加新的的数据成分或者改变数据成分，不会造成混乱亿量级数据的搜索可以达到次秒级的响应时间2.3.6无模式数据库的劣势混淆(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聚合数据模型Key-valueDocumentColumn

FamilyGraph3.1键值存储键用于访问不透明的一团数据值可以包含任意类型的数据(images,video)Pros:scalable,simpleAPI(put,get,delete)Cons:nowaytoquerybasedonthecontentofthevalue/*Query1*/SELECTageFROMusersWHEREid=1;/*willread21*/

3.1.1键值数据模型只有两列Key/Value的表Value列没有数据类型约束接口简单Addakey-valueForthiskey,givemethevalueDeleteakey特别快而且易于扩展(nojoins)3.1.2储物柜比喻3.1.3类似于辞典单词“gouge”就是“键”内容和图片就是“值”3.1.3没有子集查询3.1.4键值存储的类型Eventually‐consistentkey‐valuestoreHierarchicalkey‐valuestoresKey-ValuestoresinRAMKey-ValuestoresondiskHighavailabilitykey-valuestoreOrderedkey‐valuestoresValuesthatallowsimplelistoperations3.2列族模型一种特殊的Key-Value存储Key包括行标识、列族和列名保持了Key-Value存储的一般特性，而且提供了更高级的数据抽象和访问接口行和列的设计非常重要但是相对于RDBMS来说，还是容易得多3.2.1Row/Column键(Bigtable)3.2.2特定语义的键Bigtable系统中的Key可以不仅有行和列ID还有其他属性，列族和时间戳列族在创建表的时候创建时间戳(Timestamps)允许存储不同版本的数据Value仅仅是一个字节序列，没有强类型3.2.3列族存储概念保留了与RDBMS类似的表结构没有针对JOIN的优化可以大量的行和列，但是行的列可以不同列族允许查询具有相同特性(组)的所有行插入新的列不需要"altertable"在插入时触发增加列3.2.4列族将一组列组成列族(Columnfamilies)将一组列族组成超列(Super-Columns)允许以超列和列族进行查询相似的数据组合在一起，以提高访问速度3.3文档存储数据存储为嵌套层次结构逻辑数据依然作为一个单元存储在一起可以查询文档中得任意元素排除了ORM的需要，易于搜索实现复杂，与SQL不兼容3.3.1文档数据模型将一份机器可读的文档作为一组数据存储在一起使用JSON或者XML格式类似于对象存储(objectstores)不需要将数据分割(Noshredding)为多张表文档的子树和属性可以用Xquery或者其它语言查询甚至可以包括ACID事务的支持脱离ORM，较好地支持敏捷开发3.3.2文档存储的收益3.3.3文档结构3.3.4模型比较一个容器包含了所有词语内容分析需要大量、复杂的算法关键词已经分解成了各个子文档成分3.1.5KeywordsandNodeIDs使用倒排索引，将关键词与每个文档的每个node-id关联起来3.4图存储数据存储为一系列节点、关系和属性查询是图遍历数据之间的关系是关键e.g.socialnetworks支持快速地网络搜索图太大时，可扩展性不好特殊的查询语言(RDF使用SPARQL)3.4.1庞大的社会网络3.4.1开放链接数据3.4.2图模型适用于数据项的关系以及关系类型非常重要的场合社会网络查询："friendsofmyfriends"推理和规则引擎模式识别适合开放链接数据公开数据的自动连接(joins)3.4.3属性图中的每个节点和边都有一组Key/Value对，即属性Thanks！高级数据库及大规模存储技术NoSQL的技术基础及其实践BASE事务模型AgendaCAP原理BASE模型一致性问题1.1

ACID语义Atomicity:Allornothing.Consistency:Consistentstateofdataandtransactions.Isolation:Transactionsareisolatedfromeachother.Durability:Whenthetransactioniscommitted,statewillbedurable.任何存储都可以获得原子性、格里性和持久性，但是我们会一直需要一致性？No！可以通过放弃ACID特性，以达到更高性能和可伸缩性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任何节点在同一时刻看到的数据是一样的Availability每个请求都会得到一个是否成功地响应PartialTolerance由于网络失效，数据划分成跨越网络的片段尽管消息丢失或者系统部分失效，系统依然能够运转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网络失效问题IP网络会面临所有情况TCP网络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:分布式环境下地节点可以失效，但是整个系统不会受到影响SoftState(scalable)系统的状态和数据会随时间而变化EventualConsistency给定足够的时间，数据会在跨越分布系统的节点间取得一致2.1

ACID

vs.BASEACID强一致性稍弱的可用性悲观的并发控制策略复杂BASE可用性是最重要的更弱的一致性尽力简单快速乐观的并发控制策略2.2分布式事务两段式提交2PC可能的失效网络失效数据库失效分布式3PC模型问题:一个节点失效，可能锁住整个集群可以使用超时机制，超时判定带来了事务延迟可能使用Quorum.Quorum在分布式环境下，如果存在分区，由节点投票决定提交或者回滚CoordinatorCommitCompleteoperationReleaselocksAcknowledgeRollback2.2.12PC问题客户没有收到Ack？系统处于不一致状态inconsistentstateClient如果采取了不当的处理措施，会进一步加剧不一致的局面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一致性强度StrongConsistencyWeakConsistencyEventualConsistencyCausalConsistencyRead-your-writes

ConsistencySessionConsistencyMonotonicRead

ConsistencyMonotonicWrite

Consistency3.1.1

强一致性在更新之后，所有的后续访问都必须返回更新值3.1.2弱一致性系统不保证在后续的任何时候访问中都能返回更新值3.1.3最终一致性如果没有更新操作，系统保证最终所有的访问都能返回最后的更新值3.1.4因果一致性后续对B的访问可以返回更新值，而且系统保证会有一个写操作完成对原有值的替换3.1.5

Read-Your-Writes一致性进程A永远都会看到自己更新的值，不会是原有值3.1.6会话一致性在一次会话中，系统保证Read-Your-Writes一致性3.1.7单调读一致性如果一个进程看到了一个对象的部分值，那么后续的访问中不会返回以前的值3.1.8单调写一致性系统保证同一进程的写顺序是一致的3.2最终一致性系统预计数据会发生分歧但是包含了一些机制重获收敛(convergence)部分排序最小化冲突合并功能消解冲突3.2.1可伸缩性带来的网络分区问题？3.2.1选择在性能和成本要求驱动下，系统必须具有可伸缩性可伸缩系统的网络分区必然的P固定的情况下，必须在A和C之间进行取舍3.2.2最终一致性的设计目标更倾向于可用性但是也保证，客户可以最终得到一致的结果git:局部总是可用的push/pull来收敛由人来决定冲突消解方案3.2.3

RDBMS的最终一致性3.2.4NRWN存储数据副本的节点数目W在更新结束前，需要确认接受更新的副本数目R在读操作访问数据对象时，需要联系的副本数目W+R>N

强一致性3.2.4.2优化读优化R=1

N=W写优化W=1

N=R3.2.5典型的分布式模型3.2.6不变数据不变：不会随时间变化，也不可变更

不可删除不可更新不存在合并冲突复制是平凡而容易实施的3.2.7幂等操作幂等操作:实施一次或者多次，都会产生相同的效果可以重试不是总有可能副作用是否存在？VectorClocks部分排序技术，时间戳不足以解决问题每个节点维持一个逻辑钟logicalclock每次写得时候钟向前走一步对每个数据项记录最后观察(observed)到的时钟在副本中包含这个向量（<节点，时钟>对）如果观察到的向量和入境的向量没有共同的祖先，那么就存在冲突可以知道何时发生了分歧VectorClocks:Example11

“WhyVectorClocksAreHard”,JustinSheehyontheBashoBlogCommutativeReplicatedDataTypes1可交换复制的数据类型最终收敛到一致的状态保证副本的无冲突1

“AcomprehensivestudyofConvergentandCommutativeReplicatedDataTypes”,ShapiroetalCRDTsCRDTsprovidespecializedsemantics:G-Counter:MonotonouslyincreasingcounterPN-Counter:AlsosupportsdecrementsG-Set:Asetthatonlysupportsadds2P-Set:SupportsremovalsbutonlyonceOR-SetsareparticularlyusefulKeepstrackofbothadditionsandremovalsCanbeusedforshoppingcarts高级数据库及大规模存储技术NoSQL的技术基础及其实践MapReduce计算模型AgendaMapReduce简介工作原理基本组件另外的声音1MapReduce编程模型1.1并行体系结构的分类1.2MapReduceAsharednothingarchitectureforprocessinglargedatasetswitha

parallel/distributedalgorithmonclustersofcommodityhardware.1.3应对挑战怎样将计算进行分布如何让分布式编程更加容易？如何对待机器失效？1.4好主意

?

网络上大规模的数据复制产生大量开销让计算靠近数据数据可以存储多份，支持可靠性1.5简单性不再担心并行化、容错、数据分布和负载均衡MapReduce自己去关心对程序员隐藏系统级别的细节2.1MapinLisp(Scheme)(mapf

list[list2list3…])(mapsquare‘(1234))(14916)(reduce+‘(14916))(+16(+9(+41)))30(reduce+(mapsquare(map–l1l2))))UnaryoperatorBinaryoperator2.2基本假设需要大量的计算机(可伸缩)对输入的两个基本操作MapReduce2.3DistributedGrepVerybigdataSplitdataSplitdataSplitdataSplitdatagrepgrepgrepgrepmatchesmatchesmatchesmatchescatAllmatches2.4热身

(1/2)有一个巨型的文本文档计算文件中每个单词出现的次数应用：分析web服务器的日志寻找最频繁访问的URLs.2.4热身(2/2)文件太大，超出的内存的存储能力但是内存可以容纳所有的<word,count>对words(doc.txt)|sort|uniq-cwords例程对文件进行格式化，一行一个单词这个任务抓住了MapReduce的本质：greatthingisthatitisnaturallyparallelizable.大事自然是可并行化的2.5MapReduce方案words(doc.txt)|sort|uniq-c顺序读入大量数据Map:抽取关心的数据按照关键字分组:sortandshuffle.Reduce:聚集计算,概括,过滤，或者变换输出/写结果2.5.1MapReduceDataflowmap函数：处理数据，并产生一组中间结果键值对reduce函数：

将中间结果中相同“键”的所有中间结果值进行合并2.5.2Example:WordCount使用MapReduce对下面的文件进行单词计数：HelloWorldByeWorldHelloHadoopGoodbyeHadoop2.5.3单词计数——mapmap函数一次读一个单词，而且为每个解析出的单词输出一个(word,1)map函数的输出是：(Hello,1)(World,1)(Bye,1)(World,1)(Hello,1)(Hadoop,1)(Goodbye,1)(Hadoop,1)2.5.4单词计数——shuffle在map和reduce阶段之间，shuffle阶段为每个“键”建立一个值列表shuffle的输出/reduce函数的输入是：(Bye,(1))(Goodbye,(1))(Hadoop,(1,1))(Hello,(1,1))(World,(1,1))2.5.5单词计数——reducereduce函数对每个“键”的值列表进行求和计算输出(word,count)对reduce函数的输出是：(Bye,1)(Goodbye,1)(Hadoop,2)(Hello,2)(World,2)2.5.6单词计数——Combiner(1/2)在很多情况下，map任务产生的中间键值对中有大量的重复，而且reduce函数通常具有交换律（commutative）和结合律（associative）.Machine1:(Hello,1)(World,1)(Bye,1)(World,1)Machine2:(Hello,1)(Hadoop,1)(Goodbye,1)(Hadoop,1)CombinerFunction(2/2)可以使用一个combiner函数对中间结果进行合并，以减少网络开销combiner和reduce一般是一样的满足交换律和结合律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函数式编程的根源Map(S:array,f())Applyf(s∈S)forallitemsinSFold(S:array,g())Recursivelyapplyg()toeachiteminSandtheresultofthepreviousoperation,ornilifsuchanoperationdoesnotexist2.7MapReduce程序员编写两个函数:map(k1,v1)→[<k2,v2>]reduce(k2,[v2])→[<k3,v3>]所有具有相同“键”的“值”都发送给同一个reducer执行框架处理所有事情，除了…2.7.1MapReduce图示2.8MapReduce

“Runt