作者：(美)迪卫艾肯特·阿格拉沃尔(Divyakant Agrawal)
出版社：机械工业出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
云数据管理：挑战与机遇试读：
前言
当下大数据技术发展变化日新月异，大数据应用已经遍及工业和社会生活的方方面面，原有的数据管理理论体系与大数据产业应用之间的差距日益加大，而工业界对于大数据人才的需求却急剧增加。大数据专业人才的培养是新一轮科技较量的基础，高等院校承担着大数据人才培养的重任。因此大数据相关课程将逐渐成为国内高校计算机相关专业的重要课程。但纵观大数据人才培养课程体系尚不尽如人意，多是已有课程的“冷拼盘”，顶多是加点“调料”，原材料没有新鲜感。现阶段无论多么新多么好的人才培养计划，都只能在20世纪六七十年代编写的计算机知识体系上施教，无法把当下大数据带给我们的新思维、新知识传导给学生。
为此我们意识到，缺少基础性工作和原始积累，就难以培养符合工业界需要的大数据复合型和交叉型人才。因此急需在思维和理念方面进行转变，为现有的课程和知识体系按大数据应用需求进行延展和补充，加入新的可以因材施教的知识模块。我们肩负着大数据时代知识更新的使命，每一位学者都有责任和义务去为此“增砖添瓦”。
在此背景下，我们策划和组织了这套大数据管理丛书，希望能够培养数据思维的理念，对原有数据管理知识体系进行完善和补充，面向新的技术热点，提出新的知识体系/知识点，拉近教材体系与大数据应用的距离，为受教者应对现代技术带来的大数据领域的新问题和挑战，扫除障碍。我们相信，假以时日，这些著作汇溪成河，必将对未来大数据人才培养起到“基石”的作用。
丛书定位：面向新形势下的大数据技术发展对人才培养提出的挑战，旨在为学术研究和人才培养提供可供参考的“基石”。虽然是一些不起眼的“砖头瓦块”，但可以为大数据人才培养积累可用的新模块（新素材），弥补原有知识体系与应用问题之前的鸿沟，力图为现有的数据管理知识查漏补缺，聚少成多，最终形成适应大数据技术发展和人才培养的知识体系和教材基础。
丛书特点：丛书借鉴Morgan&Claypool Publishers出版的Synthesis Lectures on Data Management，特色在于选题新颖，短小精湛。选题新颖即面向技术热点，弥补现有知识体系的漏洞和不足（或延伸或补充），内容涵盖大数据管理的理论、方法、技术等诸多方面。短小精湛则不求系统性和完备性，但每本书要自成知识体系，重在阐述基本问题和方法，并辅以例题说明，便于施教。
丛书组织：丛书采用国际学术出版通行的主编负责制，为此特邀中国人民大学孟小峰教授（email：xfmeng@ruc.edu.cn）担任丛书主编，负责丛书的整体规划和选题。责任编辑为机械工业出版社华章分社姚蕾编辑（email：yaolei@hzbook.com）。
在此期望有志于大数据人才培养并具有丰富理论和实践经验的学者和专业人员能够加入到这套书的编写工作中来，共同为中国大数据研究和人才培养贡献自己的智慧和力量，共筑属于我们自己的“时代记忆”。欢迎读者对我们的出版工作提出宝贵意见和建议。
丛书即将出版书目
大数据管理概论
孟小峰 主编
2017年5月
异构信息网络挖掘：原理和方法
[美]孙艺洲（Yizhou Sun） 韩家炜（Jiawei Han）著；段磊 朱敏 唐常杰 译
2017年4月
大规模元搜索引擎技术
[美]孟卫一（Weiyi Meng） 於德（Clement T.Yu）著；朱亮 译
2017年4月
大数据集成
[美]董欣（Xin Luna Dong） 戴夫士·斯里瓦斯塔瓦（Divesh Srivas-tava）著
王秋月 杜治娟 王硕 译
2017年4月
短文本数据理解
王仲远 编著
2017年4月
个人数据管理
李玉坤 孟小峰 编著
2017年4月
位置大数据隐私管理
潘晓 霍峥 孟小峰 编著
2017年4月
移动数据挖掘
连德富 张富峥 王英子 袁晶 谢幸 编著
2017年4月
云数据管理：挑战与机遇
[美]迪卫艾肯特·阿格拉沃尔（Divyakant Agrawal） 苏迪皮托·达斯（Sudipto Das） 阿姆鲁·埃尔·阿巴迪（Amr El Abbadi）著；马友忠等译
2017年4月译者序
随着物联网、社交网络、移动互联网等新兴技术和服务的快速普及与应用，数据以前所未有的速度不断增长，人类进入了大数据时代。数据规模的海量性、数据种类的多样性以及数据产生速度的快速性等特点给数据管理带来了巨大挑战。为实现对大规模数据的有效管理，云数据管理技术应运而生。
云数据管理虽然已有十余年的发展历程，但仍存在诸多挑战和发展机遇。本书以面向数据存储和服务于互联网应用的云数据管理系统为主要对象，描述了其中存在的若干关键性挑战。本书共7章，第1章介绍了云计算、云数据管理的基本概念，对其中面临的关键挑战进行了概述，并描述了本书的组织结构；第2章主要介绍了分布式数据管理的相关知识，包括分布式系统、P2P系统、并发控制和分布式数据恢复等；第3章对云数据管理的早期研究工作进行了描述，包括不同的键–值存储系统在数据模型、数据分布和容错等方面的区别，以及Bigtable、PNUTS和Dynamo这三个有代表性的键–值存储系统的特点；第4章介绍了托管数据的事务问题，包括数据托管模式、托管数据的事务执行、数据存储和复制等内容；第5章主要介绍了分布式数据事务相关技术；第6章讨论了云数据管理中的多租户技术，包括多租户模型、云中的数据库弹性以及云中数据库负载的自动控制；第7章对相关经验教训进行了总结，并指出了未来的主要研究方向。
本书主要由马友忠负责翻译，孟小峰负责统稿和审校。本书于2016年9月译出初稿，责任编辑关敏对初稿进行了认真审核，张瑞玲、刘栋、贾世杰、张永新等也认真阅读初稿，给出了许多宝贵的修改意见。之后由孟小峰、马友忠根据责任编辑和同事提出的意见，逐章进行修改和完善。最后于2017年1月完成定稿。
本书译词主要遵从教科书及相关学术著作、科研论文中的习惯用法，并参考《计算机科学技术名词》等典籍。由于译者能力有限，译文中难免有不当之处，恳请读者批评指正并不吝赐教。如有任何建议或意见，敬请发邮件至ma_youzhong@163.com。马友忠2017年1月于洛阳前言
大数据和云计算是研究文献和主流媒体中大量使用的两个术语。当我们走进云计算和数据洪流的时代，经常被问到的一个问题是：云数据管理中的新挑战是什么？本书就是由我们寻求回答这个问题发展而来，并使我们自己对这一问题有了更为深入的理解。本书首先介绍了一些初步的综述性论文，这些综述论文总结了适合键–值存储系统的主要设计原则，这些系统如谷歌的Bigtable、亚马逊的Dynamo和雅虎的PNUTS，通过在一个数据中心或者有可能在世界不同地方的多个数据中心中部署成千上万台服务器来达到前所未有的规模。由于这一领域引起了学术界和工业界越来越多的研究人员的关注，该领域从键–值存储进一步发展到支持更丰富功能的可扩展数据存储，如事务或除简单键–值模型之外的模式。因此，我们将3个系统的简单综述在新加坡举办的VLDB 2010会议和在瑞典乌普萨拉举办的EDBT 2011会议扩展成一个3小时长的教程。后来又有很多相关资料的介绍，因为这些教程以及我们对该问题的理解也随时间的推移发生了改变。其间也提出了更多的系统。本书对我们这些年课程的学习以及来自于我们讲座的很多有趣的讨论进行了总结。
与传统数据管理时代事务处理与数据分析系统之间的划分一样，云数据管理也有一个类似的划分。一种是面向数据存储和服务于互联网应用的系统。这些系统与经典的事务处理系统类似，尽管有很多不同之处。另一种是数据分析系统，类似于数据仓库，通过分析大量数据来从中获得知识和智能。随着企业不断地搜集用户数据，并对来自于多种数据源的数据进行合并，基于MapReduce的系统，如Hadoop及其生态系统，使得数据分析和数据仓库更加大众化。云数据分析方面有几十个开源产品和数百篇相关领域的研究论文，已经成为一个热门的研究领域。因为企业试图从它们的数据库中获得新的见解，从而取得竞争优势，该领域会得到进一步扩展。
我们的研究、分析和调查主要关注于第一类系统，即数据管理和存储系统。因此，本书也主要关注这些系统。本书将深入探讨在设计这些更新密集型系统中存在的挑战，这些更新密集型系统必须对访问数据库小部分数据的查询和更新提供快速响应。在该类中，我们进一步将研究划分成两类系统。在第一类中，挑战在于对系统进行扩展，从而服务于拥有几千个并发请求和数百GB到数百TB频繁访问数据的大型应用。第二类包括这样一种情况，云服务提供商必须有效地服务于数十万个应用程序，每个应用程序的查询负载和资源需求都比较少。
致谢
本书源自于几年前我们试图更好地理解云数据管理设计领域的愿望。结果就有了我们对该设计领域的不断深入的理解。这得益于我们周围有很多人提供了帮助，人数太多，以至于这里无法一一列出。但是，我们想借此机会感谢那些在本书中发挥了重要作用的人。
首先，我们想感谢编辑M.Tamer zsu，他给了我们写这本书的机会，并在整个过程中为我们提供了持续的支持和反馈。他认真阅读了大量的早期草稿，并给出了很多意见和修正，大大完善了本书。Diane Cerra作为我们的出版商Morgan&Claypool的执行编辑，为我们提供了必要的行政支持。没有来自Tamer和Diane的帮助与支持，本书将无法出版。
本书中的大部分材料都以不同的形式在世界各地的不同地点呈现过。在这些演示过程中，我们收到了许多与会者的反馈，这些反馈直接或间接地改善了我们的演示，并经常会给我们提供不同的角度。我们非常感谢所有提供这些慷慨反馈的人。我们也从与Shyam Anthony、Philip Bernstein、Selcuk Candan、Aaron Elmore、Wen-syan Li、Klaus Schauser和Junichi Tatemura的大量讨论中获益匪浅，在此对他们表示感谢。我们还要感谢2008～2012年间学习研究生课程（CMPSC 271和CMPSC 274）的所有研究生的贡献。
最后，我们要感谢我们各自的家庭，他们容忍我们为准备本书和相关资料而花费了无数个小时。没有他们的一贯支持和理解，本书也不会有面世的一天。Divyakant Agrawal、Sudipto Das和Amr El Abbadi第1章简介
当代技术的快速发展导致大规模数据中心（也称为云）中的用户应用、服务和数据的数量急剧增加。云计算已经使得计算基础设施商品化，就像日常生活中的许多其他实用工具一样，并且大大减少了创新型应用及其大规模部署之间的基础设施障碍，从而可以支持分布在世界各地的大规模用户。在云计算出现之前，对一个拥有大规模用户群的新应用的市场验证，往往需要在计算基础设施方面进行大规模前期投资才能使得应用可用。由于云基础设施的即用即付收费机制和弹性特征，即根据工作负载动态地增加或减少服务器数量，大部分基础设施风险都转移到了云基础设施提供商身上，从而使得一个应用或服务能够支持全球范围内的用户，影响更多人。例如Foursquare、Instagram、Pinterest以及很多其他应用，在全世界范围内有数百万用户访问，正是云计算基础设施才使得如此大规模的部署成为可能。
虽然云平台简化了应用程序的部署，但是服务提供商面临着前所未有的技术和研究挑战，即，开发以服务器为中心的应用程序平台，能够实现无限数量用户的7×24小时的网络访问。过去10年，很多技术领先的网络服务提供商（如Google、Amazon和Ebay）积累的经验表明，云环境下的应用程序基础设施必须满足高可靠性、高可用性和高可扩展性。可靠性是确保一个服务能够连续访问的关键。同样，可用性是指一个给定系统能够正常工作的时间百分比。可扩展性需求代表系统处理逐渐增加的负载的能力，或者随着额外资源的增加（尤其是硬件资源），系统提高吞吐量的能力。可扩展性既是云计算环境下的关键要求，同时也是一个重大挑战。
一般来说，一个计算系统的硬件增加以后，如果其性能能够随增加的资源成比例提高的话，该系统就是一个可扩展的系统。系统有两种典型的硬件扩展方式。第一种方式是垂直扩展（vertically，或称scale-up），垂直扩展是指增加单个服务器的资源，或者用功能更强大的服务器进行替换，一般涉及更多的处理器、内存和服务器有更强的I/O能力。垂直扩展能够有效地为现有的操作系统和应用模块提供更多的资源，但是需要对硬件进行替换。此外，一旦超过一定规模以后，服务器能力的线性增加会导致开销的超线性增加，从而导致基础设施代价大幅度增加。另外一种系统扩展方式是水平增加硬件资源，又称为横向扩展（horizontally，或称水平扩展，scale-out）。水平扩展意味着无缝地增加更多的服务器，并进行工作负载的分配。新服务器可以逐渐添加到系统当中，这样可以保证基础设施的开销（几乎）是线性增加的，从而可以很经济地构建大规模的计算基础设施。但是，水平扩展需要高效的软件方法来无缝地管理这些分布式系统。
随着服务器价格的下降以及性能需求的不断增加，可以用低成本的系统来构建大规模的计算基础设施，部署高性能的应用系统，如网络搜索和其他基于网络的服务。可以用数百台普通服务器构建一个集群系统，其计算能力往往可以超过很多强大的超级电脑。这种模型也得益于高性能连接器的出现。水平扩展模型还促使对高I/O性能的共享数据中心的需求日益增加，这种数据中心也是大规模数据处理所需要的。除了硬件和基础设施的上述发展趋势外，虚拟化（virtualization）也为大规模基础设施的共享提供了优雅的解决方案，包括对单个服务器的共享。水平扩展模式是当今大规模数据中心的基础，构成了云计算的关键基础设施。谷歌、亚马逊和微软等技术引领者都证明，由于很多应用能够共享相同的基础设施，因此数据中心能够带来前所未有的规模效应。这3家公司不仅对公司内部的应用实现共享，同时还在各自的数据中心中提供Amazon Web Services（AWS）、Google AppEngine和Microsoft Azure等框架来为第三方应用提供服务，这样的数据中心称为公有云。
图1-1展示了部署在云基础设施中的网络应用的软件栈示意图。应用程序客户端通过互联网连接到应用程序（或服务）。应用程序接口往往是通过应用程序网关或者负载均衡服务器来把请求路由到网络和应用服务器层的相应服务器上。网络层主要负责处理访问请求并对应用逻辑进行封装。为了加快访问速度，频繁访问的数据一般都存储在由多个服务器构成的缓冲层上。这种类型的缓冲一般是分布式的，并且由应用层来负责显式管理。应用程序的持久化数据存储在一个或多个数据库服务器中（这些服务器组成数据库层）。存储在数据库管理系统（DBMS）中的数据构成了基准数据，即应用程序正常操作所依赖的数据。部署在大规模云基础设施中的大部分应用程序都是数据驱动的。数据和数据库管理系统在整个云软件栈中都是不可或缺的组成部分。由于数据管理系统是整个软件栈中的重要组成部分，所以数据往往被复制多份（参见图中的虚线部分）。这种复制机制在一个DBMS服务器宕机的情况下也能够提供高可用性。另外一个挑战是如何应对日益增长的数据量和访问请求。本书将主要关注云软件栈的数据库层设计中面临的诸多挑战。
云计算领域中数据库管理系统广泛使用的主要原因在于DBMS的成功，尤其是关系型数据库管理系统（RDBMS）的巨大成功能够满足不同类型应用程序在数据建模、存储、检索和查询方面的要求。DBMS成功的关键因素在于其所具备的诸多特性：完善的功能（用简单、直观的关系模型对不同类型应用程序进行建模），一致性（能有效地处理并发负载并保持同步），性能（高吞吐、低延迟和超过25年的工程应用经历），以及可靠性（在各种失效情况下确保数据的安全性和持久性）。图1-1 云基础设施中典型的网络应用程序软件栈
虽然取得了巨大的成功，但是在过去10年间人们一直认为DBMS和RDBMS并不适合云计算。主要原因在于，和云服务中的网络服务器、应用程序服务器等组件不同（网络服务器、应用程序服务器可以很容易从少数服务器扩展到成百上千甚至上万台服务器），DBMS不容易扩展。实际上，现有的DBMS技术无法提供足够的工具和方法来对一个现有数据库部署进行横向扩展（从几台机器扩展为很多机器）。
在云计算平台中确保基于Web的应用程序具有可扩展性的基本要求是能够支持无限数量的终端用户。因为系统的可扩展性仅能保证系统能够扩展到更多的服务器或用户请求，所以可扩展性只是一个静态属性。即，可扩展性无法确保系统的规模能随着用户负载的浮动而动态变化。相反，系统弹性则是动态属性，因为弹性允许系统在不宕机的情况下通过增加服务器进行动态扩展或者通过减少服务器缩减规模。弹性是系统的一个重要属性，其得益于底层云基础设施的弹性。
为了能够水平扩展到数千台服务器、具备弹性、可以跨越多个地理区域和具备高可用性，很多技术引领者都开发了具有自主知识产权的数据管理技术。从历史来看，由于需求的巨大不同，数据管理任务往往被宽泛地分成两大类。第一类是在线事务处理（OLTP），或者是数据服务负载（主要侧重于短小、简单的读/写操作或事务）。另一类是决策支持系统（DSS），或者称为数据分析负载（主要侧重于长时间的、只读的、复杂的分析处理操作）。两类不同的任务负载对系统有不同的要求，针对每种工作负载，历史上出现不同的系统架构。因此，为了应对不同种类的工作负载，两种技术路线共同得以发展。本书主要关注前一个问题（OLTP）在云环境下是如何解决的。分析处理也得到了云数据管理的重要推动，并且产生了很多重要的技术和系统。尤其是谷歌公司提出的MapReduce编程模型[Dean and Ghemawat，2004]，该编程模型适合用来在计算机集群中对大规模数据集进行分析。简单来说，MapReduce模式对大规模数据集进行划分，并把每一块映射到不同的服务器上。每个服务器负责处理一小块数据，并把处理结果传到一个reducer上，reducer负责收集来自不同mapper的所有结果，并对这些结果进行合并得到最终的输出结果。由于谷歌公司的广泛推广以及开源系统Hadoop[Apache Hadoop]的大受欢迎，MapReduce模式成为云时代最受关注的新兴技术。然而关于MapReduce和RDBMS的争论一直不断[Dean and Ghemawat，2010，Stonebraker et al.，2010]，广泛深入的研究也促进了MapReduce和基于Hadoop的分析平台的快速发展。本书的剩余章节将主要关注云环境的数据服务系统。
早期开发的可扩展的数据服务系统是一类称为“键–值存储”的系统。Bigtable[Chang et al.，2006]、Dynamo[DeCandia et al.，2007]和PNUTS[Cooper et al.，2008]等系统起到了引领作用，紧接着一系列开源系统涌现出来，这些开源系统或者是复制了这些内部（in-house）系统的设计思想，或者是受到这些内部系统的启发。键–值存储系统与RDBMS的主要区别在于，传统RDMS数据库中的所有数据都被视为是一个整体，DBMS的主要职责是确保所有数据的一致性。然而，在键–值存储系统中，这种关系被分隔成主键和其相关的值，键–值对被视为独立的数据单元或信息单元。应用程序的原子性和一致性以及用户访问仅仅在单个主键级别得以保证。这种细粒度的一致性允许键–值存储系统对数据库进行水平扩展，很方便地把数据从一台机器迁移到其他机器，能够把数据分布到数千台服务器上，同时能避免繁重的分布式同步，在部分数据不可用的情况仍然能够继续为用户提供服务。此外，键–值存储系统设计的目的是具有弹性，而传统的DBMS一般是用于具有静态配置的企业基础设施，其主要目的是对于给定的硬件和服务器设施实现最高的性能。
所有最初的内部系统都是根据良好的需求而定制的，能够适应特定应用的特点。例如，Bigtable主要是用来进行索引结构的创建和维护，从而为谷歌搜索引擎服务。同样，Dynamo的设计初衷是为亚马逊电子商务网站的购物篮服务，雅虎的社交属性促使了PNUTS的诞生。因此，虽然这些系统都属于键–值存储系统，但是每个系统也都有自己的独特设计。在本书后面的内容中，我们将详细分析每一个系统，从而理解这些设计原则及其权衡。然而，可扩展性、系统弹性和高可用性等关键特点使得这些系统在各自的应用领域大受欢迎，在其他领域，HBase、Cassandra、Voldemort及其他开源系统也得到了广泛使用。键–值系统的广泛使用也预示着NoSQL运动的到来[NoSQL]。虽然单个键–值对粒度的原子性和一致性已经能够满足实际应用的需求，但是在很多其他应用场景下这种访问模式还远远无法满足实际要求。在这种情况下，需要由应用程序开发者来保证多个数据的原子性和一致性。这就导致在不同的应用栈中重复使用多实体同步机制。针对多个数据的访问控制的实现机制在很多开发者博客[Obasanjo，2009]及相关论坛中都有所讨论[Agrawal et al.，2010，Dean，2010，Hamilton，2010]。
总体来说，所面临的关键挑战是如何在保证较高性能、可扩展性和系统弹性的同时实现针对数据库中多个数据片段访问的原子性。因此，在大规模数据中心中也要支持经典的事务[Eswaran et al.，1976，Gray，1978]概念。分布式事务已经有很多研究成果[通常是服务器的大集群）性能。这些基本的设计原则和各种设计方案是本书剩余章节的主要讨论内容。特别是我们会分析各种各样的系统和方法，其中有些是学术中的原型系统，有些是工业级的产品。这些方法经常利用一些巧妙的特性和应用程序的访问模式，或者对提供给应用层的功能加以限制。关键挑战在于如何在增强键–值存储系统功能的同时不降低系统性能、弹性和可扩展性。实际上，云平台成功的主要原因在于其能够在云环境下保证数据管理的简洁性、可扩展性、一致性和系统弹性。
把DBMS扩展到具有大规模并发访问用户的大型应用尚存在一些挑战，很多云平台在为大量小规模应用提供服务时也面临诸多挑战。例如，Microsoft Windows Azure、Google AppEngine和Salesforce.com等云平台一般都要为成千上万个应用提供服务，但是大部分应用可能只占用一小部分存储空间，并发请求的数量也只占整个云平台的很小比例。关键的挑战在于如何以一种高性价比的方式来为这些应用提供服务。这就导致了多租户技术的出现，多个租户可以共享资源并在一个系统中共存。多租户数据库已经成为云平台软件栈中重要且关键的组成部分。这些租户数据库一般不是很大，因此可以在单个服务器中运行。因此，DBMS的全部功能都可以得到实现，包括SQL操作和事务。然而，系统弹性、资源的有效共享和大量小租户的统一管理等问题也非常重要。为了满足这些需求，在数据库层已经产生了多种虚拟化方法。硬件和系统软件的虚拟化主要用于对大规模数据中心基础设施进行共享和管理。然而，数据库内部的虚拟化可以支持和隔离多个独立的租户数据库，该技术引起了数据库学术界和工业界的广泛关注。本书后面的部分将主要讨论设计灵活的多租户数据库系统面临的诸多挑战。
云计算和大规模数据中心的数据管理主要建立在基础的计算机科学研究之上，包括分布式系统和数据库管理。第2章中，我们主要提供分布式计算和数据库的一些基本背景资料，尤其是分布式数据库。第2章中涉及的很多主题都非常重要，有助于理解后面章节中的一些高级概念。但是对这些领域的文献资料比较熟悉的读者可以直接跳到第3章，第3章介绍云环境下关于数据管理的早期研究工作，特别介绍了基本的技术发展趋势以及取得的经验教训，并对一些特定的系统进行了重点讲述。接下来讨论了如何在云环境下支持原子操作（事务）。第4章讨论了一些新的尝试，试图将所需要的数据托管到一个地方，这样就可以避免复杂的分布式同步协议，也能够确保访问操作的原子性。第5章针对分布式事务和跨站点甚至跨数据中心的数据访问提供了通用的解决方案。第6章讨论多租户的问题，并对云环境下的实时迁移方法进行了探讨。第7章对相关经验教训进行了总结，并指出了未来的研究方案。第2章分布式数据管理
云计算建立在过去几十年计算机科学领域，尤其是在分布式计算和分布式数据管理领域积累的重要概念、协议和模型的基础上。本章主要讨论分布式系统和数据管理的基本背景，其构成了云数据库系统的基础。我们的主要目标是为读者提供足够的背景知识，以帮助读者理解后面章节的内容。对这些内容比较熟悉的读者可以直接跳过这些部分。我们同时也为读者提供了一些关于分布式数据库系统的参考资料[Gray and Reuter，1992，ozsu and valduriez,2011,weikum an vossen,2001]。我们首先在2.1节介绍了分布式系统的相关基础知识，主要包括计算因果模型、时间各种逻辑时钟；分布式互斥和仲裁集（quorums）概念；领导者选举（leader selection）；组播协议；还包括一致性，paxos和CAP理论的讨论。2.2节只要介绍了P2P系统的基本概念，P2P系统广泛用于集群数据中心的数据管理。2.3节主要介绍了并发控制和分布式数据库系统中的分布式恢复协议。2.1 分布式系统
我们首先介绍分布式系统的一些重要基本概念，这些基本概念也是与云计算和数据中心有关的相关概念和协议的重要基础。简单来说，分布式系统就是一些独立的计算进程或处理器（常称作节点）的集合，这些节点基于消息传递机制，通过通信网络相互通信。这意味着节点上的进程没有共享内存，拥有独立的故障模型，不共享相同的时钟。节点可能会因系统崩溃、停止运行、甚至人为恶意破坏而失效。网络可能会出现连接故障。一般情况下，系统也可能出现分区失效，也就是说，系统被划分成若干个子分区，单个子分区内部的节点之间可以相互通信，但是不同分区之间的节点之间无法通信。分区失效的原因可能包括由于网关故障而引起的连接故障和节点故障。
分布式系统也可以分为同步系统和异步系统。在异步分布式系统中，消息传递的时间、处理器处理时间和本地时钟漂移时间的界限是未知的。在同步系统中，这些界限都是已知的，因此，可以利用超时来进行故障检测，在必要的情况下，也可以执行相应的操作。2.1.1 逻辑时间和Lamport时钟
Lamport于1978年在他的一篇代表性论文里提出了一个简单的分布式系统模型[Lamport，1978]。该模型中，进程被建模成一个全序事件的序列。事件分为本地（local）事件、发送（send）事件和接收（receive）事件。发送事件负责发送消息，该消息由相应的接收事件接收。本地事件是非通信事件，如，内存读写、矩阵相乘等。图2-1展示了一个包括4个进程（p、p、p和p）的分布式系统示例。事1234件e和e在进程p上执行，事件e、e和e在进程p执行，等等。事2411392件e是进程p上的本地事件，而事件e是一个发送事件，e是相应的3212接收事件。
若两个事件e和f满足下列任一条件，则事件e发生在事件f之间，记作e→f：
1.如果e和f是发生在同一进程内的两个事件，并且e发生在f之前，那么e→f；
2.如果e代表了某个进程的消息发送事件send（m），f代表另一进程中针对这同一个消息的接收事件receive（m），那么e→f；
3.如果存在一个事件g，满足e→g并且g→f，那么e→f。图2-1 事件和消息“发生在前”（happens-before）关系可以很好地反映任意两个事件之间的潜在因果依赖关系。并且，如果两个事件e和f既不存在e→f关系，也不存在f→e关系，那么e和f是并发的。在图2-1中，事件e发4生在事件e6之前，而事件e与事件e和e都是并发的。324
时间概念以及时间与事件之间的关系对很多分布式系统协议来说都是至关重要的。一般情况下，不一定需要实时时钟或近似实时时钟，只要有一个时间概念能够捕获潜在的因果关系就足够了。Lamport引入了一种可以捕获事件之间的潜在因果关系的逻辑时钟概念。逻辑时钟为每一个事件e赋一个值clock（e），因此，对任意两个事件e和f，存在如下关系：
·如果e→f，那么clock（e） 为了能够实现这种逻辑时钟，Lamport为每一个进程设置了一个时钟计数器。该计数器在同一进程中的任意两个事件之间都必须是递增的，并且，每一个消息都携带了发送者的时钟值。当消息到达目的地之后，本地时钟计数器被设置为本地值的最大值，同时消息的时间戳加1。这种实现方式可以满足上述逻辑时钟的条件。 在图2-2中，使用与图2-1相同的例子，为系统中的所有事件都赋一个逻辑时间。图2-2 Lamport时钟 因为“发生在前”关系是一个偏序，因此，多个事件可能被赋值相同的逻辑时钟。但是，在很多协议中，为每一个事件赋一个唯一的时间值更为方便。这种情况下，为了打破这种关系，时间值可以设置为 逻辑时钟可以捕获潜在的因果关系，但是，这并不意味着一定有因果关系，逻辑时钟条件只是一个必要条件，并不是充分条件。分布式系统中的所有事件可能需要一个更强的时钟条件： ·e→f当且仅当clock（e） 该条件可按如下方式实现：为每一进程i赋一个长度为n的向量V，in是系统中所有进程的数量。每一个执行的事件都被赋一个本地向量。 每个向量都初始化为0，即：V[j]=0，其中i，j=1，…，N。进程ii在每一个事件之前增加本地向量元素的值，V[j]=V[j]+1。当进程i发送ii消息的时候，会将本地向量V和消息一起发送。当进程j接收消息时，i会将接收向量和本地向量的元素逐个进行比较，并将本地向量设置为两者之中较大的值，V[i]=max（V[i]，V[i]），i=1，…，N。jij 给定两个向量V和V'，V=V'当且仅当V[i]=V'[i]，i=1，…，N，并且V≤V'当且仅当V[i]≤V'[i]，i=1，…，N。如果至少存在一个j（1≤j≤N），使得V[j] 图2-3中，我们为图2-1示例中的所有事件都赋了向量时间值。图2-3 向量时钟 虽然向量时间可以准确地捕获因果关系，但是向量的大小是网络大小的函数，可能非常大，并且每一个消息都需要携带额外的向量。2.1.3 互斥和仲裁集 互斥是并发进程访问共享资源时涉及的一个基本概念。互斥是操作系统中的一个重要操作，后来也被扩展到数据库中。互斥可以按照如下方式进行定义：给定一个进程集合和一个单独的资源，开发一种协议，该协议可以确保在同一时间，一个资源只能被一个进程进行排他性访问。针对集中式系统和分布式系统都已经提出了多种解决方案。针对分布式互斥问题的一种简单的集中式解决方案可以设计如下：指定一个进程为协调者，当进程需要访问资源时，发送一个请求消息给协调者。协调者维护一个等待请求队列。当协调者接收一个请求消息时，检查该队列是否为空，如果队列为空，协调者就为请求客户端发送一个回复消息，请求客户端就可以访问共享资源。否则，请求消息就被添加到等待请求队列中。进程在共享资源上执行完成以后，向协调者发送一个释放消息。接收到释放消息以后，协调者从队列中移除请求，然后为其他等待的请求检查队列。该协议已经被Lamport[1978]扩展成分布式协议，很多其他研究人员对该协议进行了优化。 该基本协议的普遍应用需要系统中所有进程的参与。为了克服障碍，Gifford提出了仲裁集的概念。比较重要的发现是任意两个请求都应该有一个共同的进程来充当仲裁者。假定进程p（p）从集合ijq（q）中请求许可，其中q和q是仲裁集，也可以是系统中所有进程ijii的子集。q和q的交集不能为空。例如，包括系统中大部分进程的集ij合就可以构成一个仲裁集。使用仲裁集，而非系统中的所有进程，基本协议仍然有效，但是有可能出现死锁[Maekawa，1985]。图2-4a展示了一个包含7个进程的系统，任意一个大于等于4的集合和另外一个大于等于4的集合一定相交，即对于任意两个仲裁集，每一个仲裁集都包含大部分站点，它们的交集一定是非空的。 在数据库中，仲裁集的概念可以理解成基本的读、写操作，读操作不需要互斥。然而，多个读操作虽然可以并发执行，但是，针对数据的写操作仍需要互斥访问。因此，设计了两种仲裁集：读仲裁集和写仲裁集，其中，两个写仲裁集之间的交集不能为空，一个读仲裁集和一个写仲裁集之间的交集也不能为空，针对两个读仲裁集的交集没有强制性要求。图2-4b展示了一个包含6个进程的系统，写仲裁集是大小为4的任意集合，读仲裁集是大小为3的任意集合。需要注意的是，任意读仲裁集和写仲裁集必须相交，任意两个写仲裁集也必须相交。但是，读仲裁集之间不一定相交，因此，多个读操作可以并行执行。图2-4 仲裁集2.1.4 领导者选举 很多分布式算法都需要一个进程来充当协调者，然而，实际当中选择哪个进程作为协调者通常并不重要。该问题通常被称为领导者选举（leader election），其关键在于要确保一个唯一的协调者被选中。该协议非常简单，通常要求每个进程有一个进程编号，所有的进程编号都是唯一并且完全排序的。我们使用具有代表性的Bully算法（Bully Algorithm[Garcia-Molina，1982]）来对该协议进行举例，该算法假设通信是可靠的。其核心思想是努力选择具有最大进程编号的进程。任何一个进程，如果该进程刚从故障中恢复，或者该进程怀疑当前的协调者失效了，都可以发起新的选举。有三类消息可以使用：election、ok和I won。 进程可以同时发起选举。发起进程p向所有拥有较高ID的进程发送一个election消息，并等待ok消息。如果没有收到任何ok消息，则p成为协调者，并向所有拥有较低ID的进程发送I won消息。如果该进程收到ok消息，则退出并等待I won消息。如果一个进程收到了election消息，可以返回。一个ok消息，并发起一个新的选举。如果进程收到了一个I won消息，则发送者就是协调者。很容易证明Bully算法的正确性。选举协议也可以利用逻辑通信结构或者覆盖网络（如环）来实现。Chang and Roberts[1979]设计了这种协议，该协议把所有的节点组织成一个逻辑环，其中每一个进程都知道它的近邻，目的也是选择具有最大ID的进程作为协调者。一个进程如果刚刚恢复或者检测到协调者失效，可以发起新的选举。该进程按顺序对后继节点进行询问，直到发现活动节点，就把election消息发送给下游最近的活动节点。每一个接收到election消息的进程把自己的ID添加到该消息中并顺着环继续传递。一旦消息返回到发起者，就选择具有最大ID的节点作为领导者并顺着环发布一个特殊的coordinator消息。注意，多个选举可以并发执行。2.1.5 基于广播和多播的组通信 如果数据被复制到多个节点上进行存储，数据更新操作需要发送给所有的副本。广播或多播操作是一种简单的通信原语。一般来说，广播方式把同一条消息发送给系统中的所有站点，而多播只发送给部分站点。不失一般性，我们用多播来表示发送信息到特定的节点集合。下面将介绍已经提出的多种不同的原语，这些原语已经在分布式系统和数据中心等不同场景中得到了应用。 FIFO多播或发送者有序的多播：消息按照被发送的顺序传输（单个发送者）。 因果序多播：如果发送m和m两个消息，并且m的发送事件在121m的发送事件之前发生，那么在所有相同的目的地上，m都必须先21于m传输。2 全序（或原子）多播：所有消息都以相同的顺序发送给接收者。 实现不同多播协议的关键在于如何设计一种方法从而保证顺序一致性约束。假设底层网络只支持点对点通信，不支持任何多播原语。另外，需要把网络中消息的接收者和应用层中消息的实际传输者进行区分。接收到一条消息之后，该消息被插入到队列中，当序列条件满足时，消息才能开始传输。下面将对实现这些原语的协议进行描述。图2-5展示了一个包含3个因果相关多播e、e和e的示例。如果这些123多播都是因果相关多播，那么，部分消息的传输就需要推迟，直到因果序条件得到满足以后才能继续传输。例如，虽然进程r接收到e的2时间比e的接收者时间早，但是因为e发生在e之前，所以，必须等112到r对e完成接收和传输之后才能对e开始传输。同样，e必须等到123e和e传输完成之后才能开始传输。再看另外一个例子，图2-6也包12含了3个多播e、e和e。尽管e和e不是因果相关，并且是从不同12312的进程p和q发出的，如果它们是全序多播的话，那么所有的站点都要按照相同的顺序进行传输，而与它们的接收顺序无关。例如，虽然进程r接收e的时间比接收e的时间早，而在进程s中该顺序刚好相反，21但是，所有的站点都必须按照相同的顺序来传输这两个多播，比如先传输e，再传输e。需要说明的是，即使发送操作是因果相关的，全21序也不需要一定要满足因果序。例如，e和e是因果相关的，并且e232发生在e之前，但是所有的进程仍可能是先传输e，再传输e。332图2-5 因果序图2-6 全序 FIFO多播可以用一种类TCP传输协议来简单地实现，即消息发送者可以设置一个有序的消息标识符，任意一条消息在其之前的消息完成接收和传输之前都需要等待。如果有消息丢失了，接受者可以向发送者请求丢失的消息。 因果多播可以通过如下方式来实现：要求每一个广播消息都携带所有因果前置消息。在传输之前，接受者必须通过传输任何丢失的因果前置消息来确保因果关系。但是，这种协议的开销非常大。还有另外一种可供选择的协议（ISIS[Birman，1985]），该协议使用向量时钟来延迟消息的传输，直到所有的因果前置消息都被传输完成。每一个进程负责维护一个长度为n的向量时钟V，n是系统中节点的数量。V的元素被初始化为0。当节点i发送一个新的消息m时，对应节点i的元素值就加1。每一个消息都与发送者的本地向量组合在一起。当节点发送消息时，该节点需要利用如下方式对其向量进行更新：选择本地向量和随消息到达的向量之间的元素的较大值来更新。节点i利用向量VT发送消息m，如果向量VT中与发送者相对应的元素刚好比接收端本地向量中的发送者元素大1（即是下一条消息），并且，本地向量的所有元素都大于等于VT中的对应元素，那么接收者就接收到了所有的因果前置消息。 全序多播可以通过集中式方法来实现，例如固定的协调者（使用在Amoeba[Kaashoek et al.，1989]中），或者移动令牌等[Défago et al.，2004]。另外，ISIS[Birman，1985]也提出了分布式协议。在ISIS分布式协议中，所有进程通过三轮来对序号（或优先级）达成一致意见。发送者将具有唯一标识符的消息m发送给所有接收者。接受者会建议一个优先级（序号），并把建议的优先级反馈给发送者。发送者收集完所有的优先级建议，并确定一个最终的优先级（通过进程编号打破关系），然后针对消息的重新发送最终达成一致意见的优先级。最后，接收者再按照最终的优先级来传输消息m。2.1.6 一致性问题 一致性是一个基本的分布式系统问题，在出现故障的情况下，需要多个步骤来达成一致[Pease et al.，1980]。该问题经常出现在如下场景中：通信是可靠的，但是由于系统崩溃或认为恶意破坏等原因（即未按照指定的协议或代码进行响应），站点可能会失效。一般而言，该问题可以使用一个单独的协调者，或称general，协调者给n-1个参与者发送一个二进制值，并满足下列条件： 一致：所有参与者都认同一个值。 正确：如果general是正确的，那么每一个参与者都认同general发送的值。 接下来介绍两个不可能出现的结果。在异步系统中，如果进程由于崩溃而失效，并且进程是通过消息传递来进行通信的，Fischer et al.[1983，1985]证明一致性是不可能解决的。另一方面，在一个存在恶意故障的同步系统中，Dolev[1982]证明了如果一个系统的进程数量小于3f+1，其中，f是故障（恶意）进程的最大值，那么该系统也无法解决一致性问题。 已经有多种协议可以用来解决同步系统和异步系统中的一致性问题。同步系统需要指定恶意故障站点的最大数量的上界，如三分之一。另一方面，异步系统可能无法确保系统能够终止。近来，Lamport[1998，2001]为异步系统开发的Paxos协议广受欢迎。抽象地讲，Paxos是一个以领导者为基础的（leader-based）的协议，每一个进程都可以估计当前的领导者是谁。当一个进程希望在某个值上达成一致时，进程就把该值发送给领导者。领导者对操作进行排序并通过一致性算法来实现一致。通常情况下，该协议经历两个阶段。在每一个阶段，领导者会与大部分站点进行联系，往往会有多个并发的领导者。用投票来区分不同领导者提供的值。两个阶段的具体过程可以总结如下：第一阶段，又称为准备阶段，认为自己是领导者的节点可以选择一个新的唯一的投票号码，并把该号码发送给所有的站点，然后等待来自大部分站点的较小的投票号码的结果。第二阶段，又称接受阶段，领导者根据自己的投票号码建议一个值。如果领导者能够获得大多数支持，那么该值就会被接受，其他站点也会用对应的投票号码对该值进行判断。图2-7展示了基于Paxos协议的不同进程之间的通信模式。图2-7 基于Paxos协议的通信2.1.7 CAP理论 Brewer[2000]提出了下列理论，后来由Gilbert and Lynch[2002]加以证明：一个分布式共享数据系统最多同时满足下列三个属性中的两种： ·一致性（C） ·可用性（A） ·网络分区容忍性（P） 该理论就是著名的CAP理论。一般情况下，大规模云数据中心的分布式系统需要支持分区，以便能够处理大规模操作。此时，在进行网络划分的过程中，根据CAP理论的要求，就需要在一致性和可用性之间做出选择。传统的数据库系统选择一致性，而一些最新出现的数据存储系统，如键-值存储系统，比较偏爱可用性。Brewer[2012]对CAP理论的其他分支进行了评估，并对该理论中的任意两个方面的细微差别进行了详细描述。在分区故障不经常出现的情况下，可以设计一种大部分时间内兼顾一致性和可用性的系统。但是，当分区故障发生时，就需要采取一定的策略去检测分区，并开发最合适的策略对这种情况加以处理。另一个需着重强调的重要方面是延迟与分区之间的重要关系，分区归因于超时，因此，从使用的观点来看，分区故障是有时间限制的。Gilbert and Lynch[2012]对该问题进行了进一步的详细描述，CAP理论被认为是对不可靠分布式系统中安全性和活跃性之间进行均衡的一种描述，这与出现故障的异步系统中不可能存在分布式一致性有密切关系[Fischer et al.，1983]。2.2 P2P系统 作为传统的客户端–服务器模式的另外一种可替代方式，P2P（peer-to-peer）架构提供了一种可行的方案，P2P系统中的很多技术都已经在数据中心中得到了成功应用。P2P系统的主要目标是在数百万并发用户的情况下，确保数十亿对象的可用性，如音乐文件。为了实现上述目标，必须在物理网络之上构建一层虚拟的或逻辑的覆盖（overlay）网络。抽象地讲，覆盖构建了不同站点之间的相互通信方式以及数据存储方式。最简单的形式是一个对象可以看成是一个键–值对。覆盖提供了对象检索方法，并支持两种基本操作：给定一个键和值，可以把键–值元组插入（insert）到覆盖中，同时，给定一个键值，可以查询（lookup）并返回对应的值。覆盖一般可以表示成图的形式，以站点为节点，用边来连接不同的站点，可以分为结构化覆盖和非结构化覆盖。 非结构化覆盖没有在节点间的逻辑图上增加任何特定的结构。集中式方案是这种P2P设计的最简单实现，最早由Napster[Carlsson and Gustavsson，2001]加以应用，Napster方案用一个中央服务器来存储所有的键值和用来标识这些键值所在网络节点的数据库。每次键–值元组的查找都需要访问中央服务器。Napster于1999年发布，最高同时150万用户在线，2001年7月由于法律问题关闭。 除此之外，Gnutella（http://en.wikipedia.org/wiki/Gnutella）使用了分布式设计，每个节点都有若干个邻居，并且在本地数据库中存储若干个键。当需要查找键k时，某个站点首先检查自己的本地数据库，判断k是否在本地。如果在本地，则直接返回相应的值，否则，该站点递归地询问邻居站点。通常情况下，需要使用一个限制阈值来限定消息的无限制传播。 另外一方面，结构化覆盖在不同的节点上强加了具有良好定义的数据结构。这种数据结构一般称作分布式哈希表（Distributed Hash Table，DHT），DHT可以将对象映射到不同的站点，并且，给定相应的键，DHT可以快速检索相应的数据对象。特别是，在结构化覆盖中，边是按照特定的规则选择的，数据被存储在预先确定的站点上。通常情况下，每一个站点负责维护一个表，该表存储了用于查找操作的下一跳（next-hop）。我们将用一种非常流行的称为Chord[Stoica et al.，2001]的P2P系统来对结构化覆盖进行举例说明。在Chord中，每一个节点都使用一致性哈希函数（如SHA-1）进行哈希，哈希到一个mm位的标识符空间中（2个ID），其中，m一般取160。所有的站点依据各自的ID号被组织成一个逻辑环。键也被哈希到相同的标识符空间中，键（及其相应的值）存储在后继节点中，即下一个具有较大ID的节点。 一致性哈希可以确保：对任何n个节点和k个键的集合，一个节点最多负责个（1+∈）k/n键。另外，当一个新的节点加入或离开时，O（k/n）个键需要移动。为了支持高效和可扩展的查询，系统中的每一个节点都需要维护一个查询表（finger table）。节点n的查询表的第ii个元素是第一个后继节点或者等于n+2。图2-8展示了针对不同的网络规模，一个给定节点的路由表中的指针。换句话说，第i个指针沿（m–i）着环指向1/2方向。当接收到一个针对id项的查询时，节点首先检查是否存储在本地。如果不在本地，则将该查询往前发送给其查询表中最大的节点。假设Chord环中的节点呈正态分布，每一步中搜索空间的节点数量减半。因此，查询跳数的期望值是O（logn），其中，n是Chord环中节点的数量。图2-8 Chord中的路由表指针2.3 数据库系统 本节中，我们将为数据库系统中的一些主要概念提供一个相当抽象、简洁和高层次的描述。知识体系与Bernstein et al.[1987]一致。对数据库知识比较熟悉的读者可以跳过本部分内容。2.3.1 预备知识 数据库由对象的集合组成，如x、y、z。假设每个对象都有一个值，所有对象的值构成了数据库的状态。通常情况下，这些状态必须满足数据库的一致性约束。数据库对象支持两种原子操作：针对x的读和针对x的写，或者r[x]和w[x]。事务的概念在数据库系统中至关重要。一个事务是按照一定偏序执行的操作的集合。事务t执行的操作i记作r[x]和w[x]。如果一个事务是正确的，即，如果一个事务在一致ii数据库上单独执行，那么该事务可以将数据库转换成另外一个一致状态。 事务的执行必须是原子的，即必须满足如下两个属性： 1.事务之间互不干扰。 2.事务中的操作要么全部执行，要么都不执行。 事务t以commit（c）或abort（a）操作结束。并发控制协议可以iii确保并发执行的事务彼此之间互不影响。恢复协议可以确保all-or-nothing属性。 如果两个操作的执行顺序对结果有影响，即，如果其中一个是写操作，那么这两个操作是冲突的。给定一个事务集合T，T上的一个历史H是针对所有事务操作的偏序，该顺序反映了操作执行的顺序（事务顺序和冲突操作顺序）。 数据库管理系统必须满足ACID特性，即 原子性（atomicity）：每个事务要么全部执行，要么都不执行，即all-or-none属性。 一致性（consistency）：每个事务是一个一致的执行单位。 隔离型（isolation）：事务之间互不影响。 持久性（durability）：事务的效果是永久的。 当一个并发事务集合执行时，事务的正确性概念必须以每一个事务都是一致的（ACID中的C）为前提，因此，如果事务是隔离执行的，数据库将从一个一致状态转换成另外一个一致状态。因此，如果事务集合串行执行，那么可以保证其正确性。特别是，对于一个调度H中的任意两个事务t和t，如果t的所有操作在H中都位于t的所有操作之ijij前，或者相反，那么H是串行的。 为了允许事务之间在一定程度上并发执行，产生了可串行化的概念。如果一个历史的执行结果与一个串行历史的执行结果等价，那么该历史是可串行化的。如果两个历史产生相同的结果，即所有的事务
试读结束[说明：试读内容隐藏了图片]