大数据之处理模式-陈康

大数据处理的模式系统结构，方法以及发展趋势INFO陈康chenkangtsinghua@(最好给这个邮件发信)chenkangttps:///intl/zh-CN/edu/parallel/index.html这个是教学视频，英文大数据处理的关注对象网页数据各种日志电信，电信，信令数据用电数据政府经济统计数据社保，银行数据大数据处理的应用搜索引擎，网页排序电信掉线率分析用户的兴趣点分析，输入法数据审计智能翻译大数据处理的架构思路数据的存储数据分析编程数据的统计与查询SQL,MatLab,RC,JavaFS文件系统，数据库存储大数据处理的总体架构数据的存储数据分析编程数据的统计与查询LINQ,HIVE,PigLatinMapReduce,Dryad,Piccolo分布式文件系统GFS分布式Dynamo存储分布式BigTable存储，分布式数据库内容数据存储技术数据分析技术大规模平台下的数据分析编程模型基于编程模型的数据查询与优化开源平台技术发展分布式系统处理的关注点功能方面：易用性性能方面：扩展性分布式容错：可用性，出错容忍正确性方面：一致性安全性：访问控制，加密解密，入侵云计算架构与大数据分析层次将软件作为服务SaaS(SoftwareasaService)将平台作为服务PaaS(PlatformasaService)将基础设施作为服务IaaS(InfrastructureasaService)主要是使用云计算的方式构建具体的应用，如电子邮件，办公软件等，不作为平台的选型主要包括开发的平台包括大数据处理的平台例如MapReduce，Dryad，Pregel等，大数据平台需要存储平台的支持构建应用的平台，实际上是从原先的构造网络应用程序平台（如LAMP，J2EE等）衍生的云平台主要包括将物理硬件虚拟化的平台主机虚拟化：通过虚拟机的方式能够提供软件方式的虚拟硬件，提高灵活性网络虚拟化：通过虚拟网络，对虚拟机集群进行隔离存储虚拟化：提供面向对象的存储数据存储的格式没有任何格式的文件数据，任意的二进制流键值对数据，Key-ValuePair结构化的数据，组织成数据表格分布式环境下的研究问题可靠性扩展性安全性大数据研究中的重点K-V数据的存储在本地中的存储方式哈希表日志顺序表（B树，B+树，排序表等）分析上述各个方法的优缺点分布式环境下的K-V存储需要做的额外问题是如何将K定位到某个节点中方法：直接使用哈希？问题：扩展以及缩小的时候所需要移动的数据解决办法：使用一致性哈希哈希方法带来的问题不能进行range的检索方法：进行排序排序方法带来的问题需要存储元数据几个实际的分布式K-V存储分布式环境下的文件系统解决的关键问题：给一个文件名，定位这个文件名所代表的文件的具体存储的节点，剩下的事情交给本地文件系统去做Google文件系统举例，可靠性，扩展性的分析下一步是什么？分布式数据库，用来存储结构化的数据在此之前我们看一个分布式系统中几个重要的问题稳固的分布式建设套件，用以成为其他分布式系统构建的基础分布式套件能够处理比较恶劣的网络情况能够保持系统的可靠性（可用性）大家经常看到Paxos，我们下面聊聊Paxos如何构造一个稳固的分布式系统使用副本状态机什么是副本状态机ReplicatedStateMachine副本状态机的容错能力副本状态机的构造基础每一步转换都需要系统中的成员同意，采取一致行动状态转换时确定性的必须要考虑网络出错，节点出错，消息丢失，消息延迟，消息乱序的问题核心问题：如何在一个分布式环境下的多个节点共同决定一个值分布式环境下的协定协议Consensus和consistent是不一样的，有的时候都被翻译成为一致性Consistent一般指向数据，Consensus则是在一组机器之间获得一致性，例如在副本状态机FLP定理：在一个异步环境中，即使是一个进程（节点）出现问题，一致性是无法达成的关键一点：在异步系统中，无法区分消息是丢失来，还是仅仅是延迟到达Paxos算法：在半异步的环境下，是能够达成协定的半异步：Eventually（随着时间的推移，总会在某一个时间点），大部分的节点节点会正常工作，连接这些节点的网络也正常工作，所有的消息在一段时间内都完正确传输分布式算法的讨论Paxos算法达到一个目的，在一组机器内部获得一个一致的协定，即确定一个值算法需要保证安全性以及活跃性（能够得出结果）前提条件：每一个参与协议的节点都只能根据自己的内部状态以及别人传入的消息进行下一步的工作安全性safety：坏的事情永远永远不要发生活跃性liveness：好的事情会最终会发生（无法定出一个时间的期限，因为消息会延迟到达）Paxos算法的大概过程安全性：最后只能决定出一个值，不能是多个值最后决定的值必须某一个节点提出来的值，不能是一个没有意义的值一个值只有被确定之后才能够被节点以及外界所获知活跃性：最终这组节点会决定出一个值Paxos算法：是一个多轮的过程，每一轮都通过自己本地的状态以及消息来决定下一步的工作关键：在提出建议之前首先去了解一下系统的状况（通过发消息），然后才提建议（要么是新建议，要么是老建议），从而不去破坏系统可能决定的状态Step1:Prepare(a)AproposerselectsaproposalnumbernandsendsaPREPARErequestwithnumberntoamajorityofacceptors.Step2:PromisePROMISEn–Acceptorwillacceptproposalsonlynumberedn

orhigherProposer1isineligiblebecauseaquorumhasvotedforahighernumberthanj(b)Ifanacceptorreceivesapreparerequestwithnumberngreaterthanthatofanypreparerequesttowhichithasalreadyresponded,thenitrespondstotherequestwithapromisenottoacceptanymoreproposalsnumberedlessthannandwiththehighest-numberedproposal(ifany)thatithasaccepted.P1a.Anacceptorcanacceptaproposalnumberedniffithasnotrespondedtoapreparerequesthavinganumbergreaterthann.Step3:Accept!(a)Iftheproposerreceivesaresponsetoitspreparerequests(numberedn)fromamajorityofacceptors,thenitsendsanACCEPTrequesttoeachofthoseacceptorsforaproposalnumberednwithavaluev,wherevisthevalueofthehighest-numberedproposalamongtheresponses,orisanyvalueiftheresponsesreportednoproposals.Step4:Accepted(b)Ifanacceptorreceivesanacceptrequestforaproposalnumberedn,itacceptstheproposalunlessithasalreadyrespondedtoaPREPARErequesthavinganumbergreaterthann.LearningvaluesIfalearnerinterrogatesthesystem,aquorumwillrespondwithfactV_kAlearnerwillsendLEARNrequesttoall(ormajority)oftheaccepters.Acceptorswillresponsewiththeacceptedproposals.Ifaproposalisacceptedbythemajorityofaccepters,thisproposalisthedecidedone.Paxos算法以及RSM的应用分布式系统中有一些关键信息可以放在副本状态机中（副本状态机可以存放在地里位置分离的位置，以保证可靠性）接口：一个复制形态的文件系统，能够存储少量数据（例如配置文件，数据库中表格的位置）提供分布式的锁的环境，提供超时，能够对共享资源进行保护典型系统：Chubby，是Google内部一个稳固的分布式组件，在多个数据中心之间进行同步，提供简单的文件存储以及锁服务继续分布式存储BigTable：在google中用以存储半结构化数据要点：建立在GoogleFileSystem之上有一个关联的数据模型（不是一个纯的关系型数据库）使用类似于B+树的结构完成数据的排序与查询优化手段提高速度，以下是要点一个典型的分布式后台服务集群配置集群调度主节点锁服务GFS主节点SchedulerslaveGFSchunkserverLinux节点

1SchedulerslaveGFSchunkserverLinux节点

2SchedulerslaveGFSchunkserverLinux节点

N…MapReduceJob1MapReduceJob1SingleTaskBigTableServerBigTableServerBigTableMasterBigTable中的基本数据模型例子模型:

网络数据表“Contents:”“anchor:”“anchor:my.look.ca”“n.www”“CNN”“CNN.com”t3t5t6t9t8<html><html><html>

Bigtable的数据模型是一个多维映射表

多维映射表还是传统的记录格式，包括行和列，一行是一条记录，一列是一项属性

一行和一列共同维持了一个到数据单元的映射，每一个单元有一个时间戳i.e.(row:string,column:string,time:int64)String(cellcontents).

每一行都有一个行的主键key，所有行按照行主键进行排序

一段行的范围是动态划分的，每一行的范围被称为一个分表Tablet

列被组织成列组的形式

family:qualifier.

表中的每一个单元都被打上一个时间戳的版本信息BigTable的系统结构BigtableCellBigtableMasterBigtabletabletserverBigtabletabletserverBigtabletabletserverPerformsmetadataops+LoadbalancingServesdataServesdataServesdataClusterschedulingsystemGFSLockserviceHandlesfailover,monitoringHoldstabletdata,logsHoldsmetadataHandlesmaster-electionBigtableclientBigtableclientlibraryOpen()read/writemetadata从锁服务开始定位数据表通过数据的预取以及缓存，大部分操作都可以直接与对应的服务节点进行通信，无需元数据服务器的交互，更无需主服务器的交互ChubbyfileRoottablet(1stMETADATAtablet)……………OtherMETADATAtablets……………………UserTable1UserTableN…数据分表的内存以及硬盘数据结构SSTable:是BigTable在硬盘上的数据结构，是一个排序的字符串到字符串的映射

stringstringStringkeys:<row,column,timestamp>triplesWritebufferinmemory(random-access)Append-onlylogonGFSSSTableonGFSSSTableonGFSSSTableonGFS(mmap)Tabletwriteread下一步：分布式数据处理数据的存储数据分析编程数据的统计与查询LINQ,HIVE,PigLatinMapReduce,Dryad,Piccolo分布式文件系统GFS分布式Dynamo存储分布式BigTable存储，分布式数据库数据处理的需求数据处理技术的使用者是应用程序员系统程序员应用程序员应用程序员，例如日志分析员，图形处理人员，或者进行数据处理的程序员应用程序员应当只关注应用问题的本身，而不应当关注：系统的可靠性（错误处理）系统的扩展性系统的学习曲线不应当成为一个使用系统的问题现有的使用多个处理模块的编程方法共享内存编程方式消息传递方式问题:应用程序员必须自己去考虑系统的可靠性以及扩展性问题大数据处理面对的机器数目至少已数千计算应用程序员无法面对系统的底层细节隐式消息传递模型编程模式BSP编程模式消息传递被潜入到整个系统的内部，不需要程序员明确进行消息传递自动处理出错的问题，自动处理扩展性的问题MapReduce编程模型Dryad编程模型MapReduce程序的特征自动并行化以及分布式错误容忍提供状态以及监控工具对于应用程序编写人员提供清晰的编程接口MapReduce程序的编程模型MapReduce程序的编程模型从函数式编程方式中借鉴每一个应用程序编写人员只需要编写两个函数即可，分别是Map函数以及Reduce函数map(in_key,in_value)-> (out_key,intermediate_value)listreduce(out_key,intermediate_valuelist)-> out_valuelistMap函数从系统层面看的输入输出接口输入：函数接口是一个Key-Value的对，这个Key-Value的对是可以针对不同的输入进行不同的定义，例如：数据库中的一条记录，文本文件中的一行，或者是一副图片。输出：Map函数是用户自定义的函数，在Map函数中可以针对数据的Key-Value对做任意的操作，并且输出一系列的Key-Value对。输出到什么地方：输出是一个抽象的位置，即一个由MapReduce框架给出的抽象位置，程序员不必关心，由框架自己解决。输出的所有Key-Value对会进行归并，所有相同Key的会搜集在一起交给一个Reduce函数处理Reduce函数的输入输出在Map函数完成之后，所有中间的map输出的key-value对会被搜集起来，相同的key的所有value会组合成一个列表，交给一个reduce函数去处理Reduce函数将这些中间的结果进行处理，形成最后一个value的值作为输出在实际工作过程中，针对每一个key通常会处理成一个value的结果（比较抽象？下面看一个具体的例子）MapReduce的例子—WordCountWordCount是MapReduce的HelloWorld程序程序的目的是统计大量文档中每个单词出现的次数程序具有实际的意义，即可以统计单词在文档集合中出现的频率，这是进行词语重要程度的基本统计请想一下一个串行的程序如何完成这样的工作读取每一个文件单词拆分使用哈希表进行统计如果文件太大怎么办？MapReduce下的WordCount程序map(Stringinput_key,Stringinput_value)://input_key:documentname//input_value:documentcontents

foreachwordwininput_value:

EmitIntermediate(w,"1");reduce(Stringoutput_key,Iteratorintermediate_values)://output_key:aword//output_values:alistofcounts

intresult=0;

foreachvinintermediate_values:result+=ParseInt(v);

Emit(AsString(result));举例说明MapReduce程序的执行过程

下面是数据集Page1:theweatherisgoodPage2:todayisgoodPage3:goodweatherisgood.每一个Map函数的输出Worker1:(the1),(weather1),(is1),(good1).Worker2:(today1),(is1),(good1).Worker3:(good1),(weather1),(is1),(good1).思考：Map函数的输出到什么地方去了？每一个Reduce函数的输入Worker1:(the1)Worker2:(is1),(is1),(is1)Worker3:(weather1),(weather1)Worker4:(today1)Worker5:(good1),(good1),(good1),(good1)思考：在Map函数执行完毕，Reduce函数开始之前发生了什么？程序的最终结果Worker1:(the1)Worker2:(is3)Worker3:(weather2)Worker4:(today1)Worker5:(good4)再次思考一下这个程序的执行过程，并对照上面的源代码进行程序执行过程的模拟MapReduce实现的结构MapReduce程序的运行过程以MapReduce为例子讨论分布式计算的特性自动并行化以及分布式错误容忍提供状态以及监控工具对于应用程序编写人员提供清晰的编程接口MicrosoftDryad系统简介Dryad系统的执行引擎是比MapReduce更加底层的引擎，因此可以通过Dryad来执行MapReduce的程序Dryad的执行引擎能够执行一个二维的有向无环图，当所有的节点执行完毕的时候，整个系统就执行完毕Dryad仍然是一个BSP的编程模型2-DPipingUnixPipes:1-D grep|sed|sort|awk|perlDryad:2-D grep1000|sed500|sort1000|awk500|perl5049Virtualized2-DPipelines50Virtualized2-DPipelines51Virtualized2-DPipelines52Virtualized2-DPipelines53Virtualized2-DPipelines542DDAGmulti-machinevirtualizedDryadJobStructure55grepsedsortawkperlgrepgrepsedsortsortawkInput

filesVertices

(processes)Output

filesChannelsStagegrep1000|sed500|sort1000|awk500|perl50Architecture56Files,TCP,FIFO,NetworkjobscheduledataplanecontrolplaneNSPDPDPDVVVJobmanagerclusterJMcodevertexcodeStaging1.Build2.Send

.exe3.StartJM5.Generategraph7.Serialize

vertices8.MonitorVertexexecution4.Query

clusterresourcesCluster

services6.InitializeverticesFaultToleranceDryad系统的简单分析扩展性可靠性对于编程的支持数据分析用户的需求程序员可以进行编程工作数据分析员更加注重系统的本身，不试图去编程解决问题这部分的数据分析员经常使用的工具是SQL语言而不是使用编程工具区做具体的编程工作因此，针对这一部分用户需要建立对于脚本查询语言的支持通用的实现方式定义数据查询语言（为了降低复杂性，会依据SQL语言来定义一个新的查询语言，一方面是降低用户学习曲线，另外一个是简化系统实现的方式）通过编译器的方式，将高层的查询语言编译为底层的执行代码，并在底层通过执行引擎进行执行Hive的系统结构Hive客户端通过将Hive运行为服务器hive–servicehiveserver可以启动一个服务，而后可以通过不同的客户端连接到这个服务去访问Hive提供的功能开源平台的架构Google早期系统平台架构现在仍在使用GoogleCloudInfrastructureSchedulerChubbyNodeNodeNode…UserApplicationSchedulerslaveGFSchunkserverLinuxNodeMapReduceJobBigTableServer针对不同的应用有不同的大规模数据处理方法并行处理基于事件处理的流式计算处理无耦合MapRed离线计算处理支持性能隔离的在线计算处理超大规模图计算处理智能分析海量数据的图存储和查询技术面向社会网络中海量数据的个性化推荐算法分布式文件系统非线性智能分析算法软件包分布式块存储在线计算流式计算图计算离线计算系统性能优化及评价大规模数据处理应用大数据处理开源平台生态系统NoSQL数据库支持工具监控和管理ETL工具数据处理统计分析和挖掘流数据处理高速在线分析框架并行算法和框架搜索基于Hadoop的开源大数据处理框架开源大数据平台几乎没有任何其它选在,只能选择Hadoop，只能有几个组件可能可以选择别的平台（例如云存储可以选择moosefs等），但是体系结构由于有google的实践基础，几乎不能换成别的其它结构Hadoop是当前大数据处理的代名词，构建的基础是google所发表的一系列论文Hadoop中的主要模块：工具与构建基础模块Common，分布式文件系统HDFS，分布式计算框架MapReduce，分布式查询处理语言Pig，Hive，分布式数据库HBase，分布式协调程序ZooKeeper，结构化数据传输服务Sqoop，跨语言数据框架Avro，工作流程序Oozie新版本的Hadoop2.0的特性HDFSHA能够支持NameNode的热备份，通过手动的方式进行活动以及等待NameNode的求欢MR2/YARN全新的调度架构以支持多种的分布式程序类型HDFSFederation在NameNode上进行切分，降低NameNode的负担HDFSSnapshot支持文件系统的快照HDFSHANameNode分为两种角色：activeNN与standbyNN，activeNN对外提供读写服务，一旦出现故障，便切换到standbyNN。支持Client端重定向，也就是说，当activeNN切换到standbyNN过程中，Client端所有的进行时操作都可以无缝透明重定向到standbyNN上，Client自己感觉不到切换过程。DN同时向activeNN和standbyNN汇报block信息。当前HadoopHA只能实现人工切换，该功能在某些情况下非常有用，比如，对NN进行升级时，先将NN切换到standbyNN，并对之前的activeNN进行升级，升级完成后，再将NN切换至升级后的NN上，然后对standbyNN进行升级。以后将支持自动切换，也就是说，监控模块可检测出activeNN何时出现故障，并自动将之切换到standbyNN上，这样可大大较小Hadoop集群运维人员的工作量。（这个功能特性在计划上将通过ZooKeeper的监控来实现，由ZooKeeper来确定到底哪一个NameNode是正确活动的NameNode）HDFSHANext（准备实现）调度器的框架YARN/MapReduceV2(Hadoop0.23)通用的运行时框架，用户可以编写自己的计算框架(包括但不限于MapReduce)，在该运行环境中运行该框架提供了以下几个组件：资源管理：包括应用程序管理和机器资源管理资源双层调度容错性：各个组件均有考虑容错性扩展性：可扩展到上万个节点可以支持的框架包括MapReduceApacheGiraph：图算法处理框架，采用BSP模型（bulk-synchronousparallelmodel）ApacheHAMA：基于BSP模型的分布式计算框架，可用于大规模科学计算，如矩阵，图算法，网络算法等OpenMPI：这是一个高性能计算函数库，通常在HPC（HighPerformanceComputing）中采用，与MapReduce相比，其性能更高，用户可控性更强，但编程复杂，容错性差调度器框架的改进ResourceManager:包括调度器和应用管理器，用以管理资源以及任务，具体的任务由ApplicationManager来进行管理NodeManager:NM主要用于管理某个节点上的task和资源ApplicationsManager:ASM主要负责接收作业，协商获取第一个容器用于执行AM和提供重启失败AMcontainer的服务。即用以管理AM。ApplicationMaster：AM主要用以管理其对应的应用程序，如MapReduce，DAG等作业Container:容器中封装了机器资源，如内存，CPU,磁盘，网络等，每个任务会被分配一个容器，该任务只能在该容器中执行，并使用该容器封装的资源。HDFS其它新特性HDFS的其它新特性HDFSFederation传统HDFS是master/slave结构，其中，master（也就是NameNode）需要存储所有文件系统的元数据信息，且所有文件存储操作均需要访问多次NameNode，因而NameNode成为制约扩展性的主要瓶颈所在。为了解决该问题，引入了HDFSFederation，允许HDFS中存在多个NameNode，且每个NameNode分管一部分目录，而DataNode不变。缩小了故障带来的影响范围，并起到一定的隔离作用HDFSSnapshot用户可在任意时间对HDFS做快照，这样，在HDFS出现故障时，可将数据恢复到某个时间点的状态。即将实现，当前还未实现HadoopHAMA，基于BSP的通用编程模型BSP编程模型Hama的整体系统架构Hama的集群中需要有HDFS的运行环境负责持久化存储数据(例如:job.jar),BSPMaster负责进行对GroomServer进行任务调配，groomServer负责进行对BSPPeers进行调用程序进行具体的调用，Zookeeper负责对GroomServer进行失效转发。Hadoop中的大规模图计算GiraphGiraph基于Hadoop的大规模图像处理框架，Giraph基于Pregel的编程模型，并通过ZooKeeper来协调（选举Coordinator）以获得高可靠性Giraph依据BSP模型编写，在一个superstep中，图的顶点可以通过边向其它的顶点发送消息，Giraph可以在计算的过程中进行检查点操作。编程模型基于开源方式的大数据处理平台组成物理或者虚拟的计算平台OpenStack(Folsom)Linux(Ubuntu12),Xen(4.2),KVM(3.6)海量数据存储服务与分布式文件系统HDFS(2.0.2)大规模数据库存储服务HBase(0.94.2)大规模数据处理方法和编程模型MapReduce(2.0.2)，BSP(Hama0.6.0)数据查询语言的支持HIVE(0.9.0)运行时支持服务

ZooKeeper(3.4.5)外部数据获取接口

MySQL(5.5)云计算应用程序构造支持Mahout(0.7)基于Hadoop的开源大数据处理平台演示HDFS的基本操作MapReduce的程序的运行Hive数据查询的演示ZooKeeper的演示与说明HBase的演示与说明当前研究的发展趋势数据分析支撑平台大规模的数据存储技术数据处理编程技术面向问题的数据查询技术任何大数据需要获得处理都首先需要对其存储，依据存储数据结构的不同，可以分为分布式文件系统用以存储任意结构的数据；KeyValue对的存储用以存储简单结构的数据以及分布式数据库用以存储具有一定结构的数据与单机上的类似C语言的高级程序语言类似，通过数据处理编程方式可以对数据进行灵活以及大规模快速处理。这里主要问题是解决数据处理中的扩展性和可靠性问题。与单机中的查询语言SQL类似，对于具有固定结构的数据进行查询会有一套有效并且方便的处理手段，用户无需进行编程即可以完成大规模数据的查询工作大数据处理支撑平台的研究大规模的数据存储技术数据处理编程技术面向问题的数据查询技术关于存储的研究：1扩展性：提高存储的效率，降低能耗2可用性：提高存储的可靠性，使得具有全球的访问能力，降低模块失败的影响3一致性：如何保证在存储的多个版本之间的一致性4功能性：在存储系统中加入一些计算功能，提高存储系统的灵活性和能力5安全性：提供多用户的安全访问关于计算的研究1在现有的计算框架的基础上的研究，对现有框架进行改良，提高系统的效率，提高系统吞吐率2在面对新问题的时候，需要针对新问题提出合适的计算框架，以能够在新问题中取得良好效果数据支撑平台的研究公司研究院公司研究院的特点还是需要配合公司的主营业务主要包括：Google，Microsoft，Yahoo，Facebook，Amazon等大型的互联网公司公司研究院或者公司本身发表论文的特点是由于公司本身的能力，可以创建大规模的分布式系统依据公司问题的本身出发来特别针对应用设计系统去解决；或者对于现有系统进行改进，来更加适应新的形式的数据存储与处理需求或者对现有的系统进行测试以及总结，分享构建大规模系统的经验学术研究机构学术机构包括大学以及国家实验室主要的研究机构包括：MIT，WashingtonU,Berkeley,Stanford,CMU,Princeton,Umassetc.学术机构研究不可能去构造真正的大规模系统，因此关注点是更有学术价值的东西，即更有“思想性”的东西在公司没有看到之前去发现一些系统性的问题，例如一些新问题，通过新方法去解决一些具有理论价值的问题，如分布式系统中的一致性问题分布式存储的模型与系统按照研究技术点分，技术点内容丰富：高性能分布式数据库存储MegaStore全球一致的数据库存储Spanner其它地理分布的存储系统其它技术

模块化，采用低功耗部件，面向应用的优化等按照研究对象类型分可以总体分为三类：分布式文件系统分布式的key-value对的存储分布式的结构化与半结构化的存储文献综述方法是选取以下四个会议的论文：SOSP2009，SOSP2011，OSDI2010，OSDI2012这两个会议是系统领域里面的会议，提供了大量详实的参考其它的可以参考的会议：NSDI，EuroSys，USNIXATCGoogle早期系统平台架构现在仍在使用GoogleCloudInfrastructureSchedulerChubbyNodeNodeNode…UserApplicationSchedulerslaveGFSchunkserverLinuxNodeMapReduceJobBigTableServerGoogle大规模分布式数据存储方面的演进GFS分布式文件系统搜索引擎存储需求Percolator结构化数据需求随机读写需求SpannerBigTable分布式数据库数据库中的触发器跨行的一致性Colossus分布式文件系统对上层支持过少功能集成，重新设计以及增强MegastoreLinearizable的特殊模式的分布式数据库分布式存储模型与系统：MegastoreMegastore是谷歌一个内部的存储系统，它的底层数据存储依赖Bigtable实现了类似RDBMS的数据模型，同时提供数据的强一致性解决方案数据进行细颗粒度的分区(这里的分区是指在同一个datacenter，所有datacenter都有相同的分区数据)数据更新在机房间进行同步复制(这个保证所有datacenter中的数据一致)Megastore能够在数据中心之间得到一致的数据Megastore:ProvidingScalable,HighlyAvailableStorageforInteractiveServices,Google,CIDR2011分布式存储模型与系统：Megastore分区与同步Megastore的数据复制是通过paxos进行同步复制的，也就是如果更新一个数据，所有机房都会进行同步更新因为使用paxos进行复制，所以不同机房针对同一条数据的更新复制到所有机房的更新顺序都是一致的，同步复制保证数据的实时可见性，采用paxos算法则保证了所有机房更新的一致性Paxos被使用在一个EntityGroup内部，在这个EntityGroup的内部所使用的Paxos算法能够达到ACID特性在跨多个EntityGroup的时候，可以使用2PC，仍然可以达到一致性，但性能较低，也可以使用异步复制Megastore将数据分区为一个EntityGroups的集合，这里的EntityGroups相当于一个按id切分的分库，这个EntityGroups里面有多个EntityGroup(相当于分库里面的表)，而一个EntityGroup有多个Entity(相当于表中的记录)分布式存储模型与系统：

Megastore的数据模型Megastore的数据模型是定义schema中并且是强类型的每一个schema有一个表集合，每个表包含一个实体集合(相当于record)每个实体有一系列的属性(相当于列属性)，属性是命名的，并且指定类型，这些类型包括字符串，各种数字类型，或者google的protocolbuffer。这些属性可以被设置成必需的，可选的，或者可重复的(一个属性上可以具有多个值)。一个或者多个属性可以组成一个主键。表包括根表和字表，字表必须包含一个指向根表的唯一标识符指向根表的同一个key所代表的所有根表以及字表中的记录都会被保存到同一个entitygroup，每一个entity被映射到BigTable中的一行Megastore的事务与并发处理每一个EntityGroup是一个小的数据库，一个事务写操作会首先写入对应EntityGroup的日志中，然后才会更新具体数据，具有ACID的特性BigTable具有一项在相同row/column中存储多个版本带有不同时间戳的数据。正是因为有这个特性，Megastore实现了多版本并发控制(MVCC)不同的读类型current，当开始一个current读操作时，事务系统会首先确认所有之前提交的写已经生效了；然后系统从最后一个成功提交的事务时间戳位置读取数据snapshot，系统拿到己经知道的完整提交的事务时间戳并且从那个位置直接读取数据，和current读取不同的是，这个时候可能提交的事务更新数据还没有完全生效(提交和生效是不同的)inconsistent，读取在数据库中的最新数据，可能不一致数据写入的过程：一个写事务通常开始于一个current读操作以便确定下一个可用的日志位置。提交操作将数据变更聚集到日志，并且分配一个比之前任何一个都高的时间戳，并且使用Paxos将这个logentry加入到日志中由于Paxos协议的保证，只有一个写能够成功，其他写退出，重试Megastore的事务处理流程完整事务生命周期包括以下步骤：1.读：获取时间戳和最后一个提交事务的日志位置2.应用逻辑：从BigTable读取并且聚集写操作到一个日志Entry3.提交：使用Paxos将日志Entry加到日志中4.生效：将数据更新到BigTable的实体和索引中5.清理：删除不再需要的数据Megastore的体系结构副本的类型Full:containalltheentityandindexdata,abletoservicecurrentreadsWitness:storingthewrite-aheadlog(forwritetransaction)Read-only:inverseofwitness(storingfullsnapshotofthedata)Coordinator用以指示本地副本是否是最新的Megastore数据读取过程DatastructureandalgorithmsEachreplicastoresmutationsandmetadataforthelogentriesReadprocess1.QueryLocalUp-to-datecheck2.FindpositionHighestlogpositionSelectreplica3.CatchupChecktheconsensus

valuefromother

replica4.ValidateSynchronizingwith

up-to-data5.QuerydataReaddatawithtimestampMegastore数据写入过程DatastructureandalgorithmsEachreplicastoresmutationsandmetadataforthelogentriesWriteprocess1.AcceptleaderAsktheleadertoaccept

thevalueasproposal

number2.PrepareRunthePaxosPrepare

phaseatallreplica3.AcceptAskremainingreplicas

toacceptthevalue4.InvalidateFaulthandlingforreplicaswhichdidnotacceptthevalue5.ApplyApplythevalue’smutationatasmanyreplicasaspossible全球一致性的分布式存储SpannerDatacenter1Datacentern…Datacenter2GPStimemasterGPStimemasterGPStimemasterAtomic-clocktimemasterGPStimemasterClientGPStimemasterComputereference[earliest,latest]=now±εGoogle使用全局一致性的时钟，通过GPS的方法获得时钟，从而建立了一个强一致性的全球分布式存储Spanner:Google’sGlobally-DistributedDatabase,google,OSDI2012Spanner关键特性与技术Spanner的关键特性第一，在数据的副本配置方面，应用可以在一个很细的粒度上进行动态控制。第二，Spanner有两个重要的特性，很难在一个分布式数据库上实现，即Spanner提供了读和写操作的外部一致性，以及在一个时间戳下面的跨越数据库的全球一致性的读操作。Spanner的关键技术全球定位的时钟，精度能够达到1ms通过Paxos保证数据副本在全球中一致通过TwoPhaseCommit来保证数据在跨多个副本状态机的时候的一致性Spanner服务器的组织一个Spanner叫做一个Universe，包括多个zone一个zone包括一个zonemaster和一百至几千个spanserver。zonemaster把数据分配给spanserver，spanserver把数据提供给客户端。客户端使用每个zone上面的locationproxy来定位可以为自己提供数据的spanserver。Universemaster和placementdriver，当前都只有一个。Universemaster主要是一个控制台，它显示了关于zone的各种状态信息，可以用于相互之间的调试。Placementdriver会周期性地与spanserver进行交互，来发现那些需要被转移的数据，或者是为了满足新的副本约束条件，或者是为了进行负载均衡。Spanner软件栈结构每个spanserver负载管理100-1000个称为tablet的数据结构的实例。一个tablet就类似于BigTable中的tablet，也实现了下面的映射：(key:string,timestamp:int64)->stringSpanner会把时间戳分配给数据一个tablet的状态是存储在类似于B-树的文件集合和写前(write-ahead)的日志中，所有这些都会被保存到一个分布式的文件系统中，这个分布式文件系统被称为Colossus，它继承自GoogleFileSystem每个spanserver会在每个tablet上面实现一个单个的Paxos状态的机器，每个状态机器都会在相应的tablet中保存自己的元数据和日志会对每个Paxos写操作进行两次记录：一次是写入到tablet日志中，一次是写入到Paxos日志中多个Paxos的状态机需要通过一个participant进行协调，完成对数据的写入SpannerTrueTimeTrueTime会显式地把时间表达成TTinterval，这是一个时间区间，具有有界限的时间不确定性TrueTime使用的时间是GPS和原子钟。TrueTime使用两种类型的时间，是因为它们有不同的失败模式。GPS参考时间的弱点是天线和接收器失效、局部电磁干扰和相关失败（比如设计上的缺陷导致无法正确处理闰秒和电子欺骗），以及GPS系统运行中断。原子钟也会失效，不过失效的方式和GPS无关，不同原子钟之间的失效也没有彼此关联。Datacenter1Datacentern…Datacenter2GPStimemasterGPStimemasterGPStimemasterAtomic-clocktimemasterGPStimemasterClientGPStimemasterComputereference[earliest,latest]=now±ε通过TrueTime可以获得并发访问如下特性：外部一致性的事务无锁机制的只读事务针对历史数据的非阻塞读这些特性可以保证，在时间戳为t的时刻的数据库读操作，一定只能看到在t时刻之前已经提交的事务。地理分布式存储的可用性研究各种因素对可用性影响典型的失败是短时的，可以修复磁盘失败会带来数据丢失，节点失败要比磁盘失败的概率更高节点失败不是独立的，会带来连锁效应，引起一大堆的节点都失败通过隐马尔科夫模型可以建立失败模型AvailabilityinGloballyDistributedStorageSystems,OSDI2010,Google,Columbia地理分布的事务存储Transactionalstorageforgeo-replicatedsystems,NYU,SOSP2011CStart_TXCommit_TXReadWriteCCCCCReplicatedataCoordinateforPSISite1Site2Mainchallenge:avoidwrite-writeconflictacrosssitesWalter’ssolution PreferredsiteCountingset提供地理分布的事务存储，提供独立的ParallelSnapshotIsolation语义以支持地理分布式的事务存储这个语义是在站点内部通过强的语义维持方法维持事务一致性，在站点之间通过异步方式进行同步，维持写入的顺序地理分布存储的一致性Don’tSettleforEventual:ScalableCausalConsistencyforWide-AreaStoragewithCOPS,SOSP2011,Princeton为分布式存储提供causal+consistency，causality被定义为线程内部的语义，put/get语义以及递归语义，causal+consistency在causal的基础上加入了冲突解决语义(比前面的PSI稍弱)地理分布的快速存储并且在必要的时候提供一致性MakingGeo-­‐ReplicatedSystemsFastasPossibleConsistentwhenNecessary,Cornell,OSDI2012提供一种一致性可调的语义以能够实现快速的地理分布存储，在下面两个consistency之间进行调整，不是一个新的consistency低功耗的数据存储DavidG.Andersen,JasonFranklin,MichaelKaminsky,AmarPhanishayee,LawrenceTan,VijayVasudevan:FAWN:afastarrayofwimpynodes.CMU,SOSP2009分布式Key-value存储使用合适的处理器而不是性能最高的处理器，使用合适的设备SSD，构造低能耗存储系统主要技术：1使用DHT解决可靠性问题2使用LogStructure解决可靠性以及降低Random写分布式存储的模块化技术MikeMammarella,ShantHovsepian,EddieKohler:ModulardatastoragewithAnvil.UCLA,SOSP2009对象为分布式Key-Value对的存储提供各种KeyValue技术，应用可以依据自己的需求来建立特定的dTable以满足应用的需求，无需从头建设存储底层不同的构建KeyValue对的存储方法：1使用Hash表存储2使用排序表B树存储3使用日志存储4使用BloomFilter帮助过滤扩展大规模照片存储的速度FindinganeedleinHaystack:Facebook’sphotoStorage,Facebook,OSDI2010文件系统在进行文件读取的时候需要查元数据，会有很多磁盘操作通过把元数据放在内存中（日志方式写入到磁盘中）能够提高元数据访问速度通过索引，修改现有的基于NFS的存储方式，使得照片可以通过一次磁盘操作即可获得对等计算方式的存储嵌入处理功能Comet:anActiveDistributedKey-ValueStore,OSDI2010,UniversityofWashington传统的P2Poverlaynetwork保存的是被动的存储对象，如果保存的是活动对象的话ActiveObject，就可以支持很多种的应用程序自主构造分布式缓存TransactionalConsistencyandAutomaticManagementinanApplicationDataCache,MIT,OSDI2010语义，以更加符合底层的数据库系统，并且能够进行自动管理，程序只需要标记可以cache的内容即可Azure的云存储体系结构WindowsAzureStorage–AHighlyAvailableCloudStorageServicewithStrongConsistency,SOSP2011,Microsoft最底层为分布式文件系统（日志文件系统形式），元数据通过Paxos进行副本中间层是数据分片层，用以定位数据所在的位置最上层为请求层，用以用户认证获得可用性，扩展性云存储中的扁平化架构FlatDatacenterStorage,MicrosoftResearch,OSDI2012没有中心的控制节点，没有中心的元数据，使用大规模的网络结构将处理器和存储连接在一起多租户存储提供公平性PerformanceIsolationandFairnessforMulti-TenantCloudStorage,Princeton,OSDI2012云存储中需要加入多租户的考虑，需要在多租户存储环境中增加公平性的考虑大规模数据处理的平台技术按照研究技术点分利用列数据存储等技术达到实时交互的要求（Dremel）等调度器方法的改进，例如Facebook的Corona，微软的兼顾公平性的调度器等其它提高单个MapReduce任务性能的方法，如使用缓存和分表降低I/O量等其它技术，如新型的编程方式，性能问题分析与解决等按照研究对象类型分可以总体分为两类：底层的基本数据处理方式，例如MapReduce，Dryad，Pregel等，在编程上相当于C语言等高级语言分布式的查询方法，例如Hive，SCOPE等，在编程上相当于SQL等查询语言Google分布式数据处理方面的演进以及与相关技术的关系MapReduce搜索引擎需求Sawzall对数据查询语言的支持，翻译为底层MapReduce对等物：HadoopMapReduceMicrosoftDryadPregel对列式数据库支持提高查询效率Dremel对图计算重新设计对等物：HIVE,DryadLINQ针对不同的应用有不同的大规模数据处理方法并行处理基于事件处理的流式计算处理无耦合MapRed离线计算处理支持性能隔离的在线计算处理超大规模图计算处理智能分析海量数据的图存储和查询技术面向社会网络中海量数据的个性化推荐算法分布式文件系统非线性智能分析算法软件包分布式块存储在线计算流式计算图计算离线计算系统性能优化及评价大规模数据处理应用大规模数据的交互查询分析系统DremelDremel是Google的“交互式”数据分析系统。可以组建成规模上千的集群，处理PB级别的数据。MapReduce处理一个数据，需要分钟级的时间，只能用于离线处理，不能用于交互处理。Google开发了Dremel将处理时间缩短到秒级，作为MapReduce的有力补充ABCDE***......r1r2r1r2r1r2r1r2Readless,cheaper

decompressionDocId:10LinksForward:20NameLanguageCode:'en-us'Country:'us'Url:'http://A'NameUrl:'http://B'r1Dremel交互式数据查询特性Dremel是一个大规模系统。在一个PB级别的数据集上面，将任务缩短到秒级，无疑需要大量的并发。磁盘的顺序读速度在100MB/S上下，那么在1S内处理1TB数据，意味着至少需要有1万个磁盘的并发读。但是机器越多，出问题概率越大，如此大的集群规模，需要有足够的容错考虑，保证整个分析的速度不被集群中的个别慢(坏)节点影响。Dremel是MR交互式查询能力不足的补充。和MapReduce一样，Dremel也需要和数据运行在一起，将计算移动到数据上面。需要GFS这样的文件系统作为存储层。Dremel并非是MapReduce的替代品，它只是可以执行非常快的分析，在使用的时候，常常用它来处理MapReduce的结果集或者用来建立分析原型。Dremel的数据模型是嵌套(nested)的。互联网数据常常是非关系型的。Dremel还需要有一个灵活的数据模型，这个数据模型至关重要。Dremel支持一个嵌套(nested)的数据模型，类似于Json。而传统的关系模型，由于不可避免的有大量的Join操作，性能较差。Dremel中的数据是用列式存储的。使用列式存储，分析的时候，可以只扫描需要的那部分数据的时候，减少CPU和磁盘的访问量。同时列式存储是压缩友好的，使用压缩，可以综合CPU和磁盘，发挥最大的效能。Dremel结合了Web搜索

和并行DBMS的技术。借鉴Web搜索中的“查询树”的概念，将一个相对巨大复杂的查询，分割成较小较简单的查询。并发的在大量节点上跑。与并行DBMS类似，Dremel可以提供了一个SQL-like的接口，就像Hive和Pig那样。Dremel系统中的列式存储数据一开始是放在GFS上的。通过MapReduce将数据导入到Dremel中去，在这些MapReduce中还可以做一些处理。分析师使用Dremel可以建立模型。最后可以编制成一个长期运行的MapReduce任务。Dremel提供按列存储的嵌套数据格式。如图所示，在按记录存储的模式中，一个记录的多列是连续的写在一起的。在按列存储中，可以将数据按列分开。也就是说，可以仅仅扫描A.B.C而不去读A.E或者A.B.C。因此难点在于，如何能同时高效地扫描若干列，并做一些分析。Dremel系统中的数据模型数据模型可以用数学方法严格的表示如下(实际上类似于JSON，但是没有Map)：t=dom|<A

1

:t[∗|?],...,A

n

:t[∗|?]>实际的数据实际的存储格式RepetitionLevel是记录该列的值是在哪一个级别上重复的DefinitionLevel

是定义的深度，用来记录该列是否是”虚拟”出来的Dremel系统中的数据重构通过状态机进行重构，例如只读取DocID和Name.Language.Country。可以同时扫描两个字段，先扫描DocID。记录下第一个，然后发现下一个DocID的R是0；于是该读Name.Language.Country，如果下一个R是1或者2就继续读，如果是0就开始读下一个DocID右图则给出了能够读出所有数据的状态机基于树形结构的查询方式Dremel可以使用一种SQL-like的语法查询嵌套数据。由于Dremel的数据是只读的，并且会密集的发起多次类似的请求。所以可以保留上次请求的信息，还优化下次请求的explain(对请求进行分解)过程。当Client发其一个请求，根节点受到请求，根据metadata，将其分解到枝叶，直到到位于数据上面的叶子Server。他们扫描处理数据，又不断汇总到根节点。大规模数据处理Hadoop调度器的改进：CoronafromFacebookUndertheHood:SchedulingMapReducejobsmoreefficientlywithCorona,2012,FacebookFacebook改进了现有的调度器框架，使得在任务调度的时候能够充分利用集群中的资源，提高调度的效率现有的hadoop调度器由右图显示，主要存在以下几点问题：JobTracker主要的工作有两点，一个是管理集群的资源，一个如调度用户的任务，会带来调度的负担提高，调度效率下降现有的调度方式是pollbased，只有在心跳的时候分配任务，会提高小任务的执行时间Hadoop使用了静态配置的slotbased的策略，对于非MapReduce任务调度不合适在升级的时候需要杀掉所有的任务，升级软件，然后才重启需要进行的工作Corona对现有调度