大数据应用的中存储和处理问题剖析

大数据问题纽约证券交易所每天产生1TB的交易数据社交网站facebook的主机存储着约10亿张照片，占据PB级存储空间互联网档案馆存储着约2PB数据，并以每月至少20TB的速度增长。瑞士日内瓦附近的大型强子对撞机每年产生约15PB的数据这么大的数据该怎么存储和读取？传统关系型数据库（oracle）的成本Facebook的服务器大概1万台，按照oracle的标准10g版本计算大约需要21亿元Hadoop简介Hadoop一个分布式系统基础架构，由Apache基金会开发。用户可以在不了解分布式底层细节的情况下，开发分布式程序。充分利用集群的威力高速运算和存储。由 HDFS、MapReduce、HBase、Hive 和 ZooKeeper等成员组成。其中，HDFS 和 MapReduce 是两个最基础最重要的成员。HDFS 是 Google GFS 的开源版本，一个高度容错的分布式文件系统，它能够提供高吞吐量的数据访问，适合存储海量（PB 级）的大文件（通常超过 64M），其原理如图所示：Hadoop优点可扩展：不论是存储的可扩展还是计算的可扩展都是Hadoop的设计根本。经济：框架可以运行在任何普通的PC上。可靠：分布式文件系统的备份恢复机制以及MapReduce的任务监控保证了分布式处理的可靠性。（元数据磁盘错误，心跳测试，副本数，快照（目前还没实现）高效：分布式文件系统的高效数据交互实现以及MapReduce结合LocalData处理的模式，为高效处理海量的信息作了基础准备。Hadoop在国内的分布情况Hadoop作业调度默认调度算法FIFO公平份额调度算法Fair Scheduler计算能力调度算法Capacity Scheduler作业调度总结 默认调度算法FIFO简介最早的Hadoop Map/Reduce计算架构中，JobTracker在进行作业调度时使用的是FIFO(First In First Out)算法。所有用户的作业都被提交到一个队列中，然后由JobTracker先按照作业的优先级高低，再按照作业提交时间的先后顺序选择将被执行的作业。优点调度算法简单明了，JobTracker工作负担轻。缺点忽略了不同作业的需求差异。例如如果类似对海量数据进行统计分析的作业长期占据计算资源，那么在其后提交的交互型作业有可能迟迟得不到处理，从而影响到用户的体验。新的调度算法当前，新的调度器已经作为插件的形式集成在Hadoop当中。公平份额调度算法Fair SchedulerFair Scheduler提出背景Fair Scheduler基础知识Fair Scheduler两个关键问题Fair Scheduler的配置Fair Scheduler提出背景提出背景Facebook要处理生产型作业(数据统计分析,hive)、大型批处理作业(数据挖掘、机器学习)、小型交互型作业(hive查询)。不同用户提交的作业在计算时间、存储空间、数据流量和响应时间上都有不同需求。为使hadoop mapreduce框架能够应对多种类型作业并行执行，使得用户具有良好的体验，Facebook公司提出该算法。Fair Scheduler基础知识设计思想尽可能保证所有的作业都能够获得等量的资源份额。系统中只有一个作业执行时，它将独占集群所有资源。有其他作业被提交时就会有TaskTracker被释放并分配给新提交的作业，以保证所有的作业都能够获得大体相同的计算资源。作业池用户提交的作业将会放进一个能够公平共享资源的pool(池)中。每个作业池设定了一个最低资源保障(a guaranteed minimum share)，当一个池中包含job时，它至少可以获得minimum share的资源最低保障资源份额机制。池中的作业获得一定份额的资源。可以通过配置文件限制每个池中的作业数量。缺省情况下，每个作业池中选择将要执行的作业的策略是FIFO策略，先按照优先级高低排序，然后再按照提交时间排序。Fair Scheduler基础知识作业和作业池的权值weight缺省情况下，Fair Scheduler会为每一个用户建立一个单独的pool。所有用户能够获得等量的资源份额而无论他提交了多少作业，而每个pool中，各个作业将平分分配给所在池的资源。实际应用中，无论是作业池还是作业，都被赋予一定的权值，并以此为依据获得相应比例的资源。这种情况下，作业池和作业在资源分配时不是严格的平均分配，但这有利于根据作业的重要程度及实际需求合理分配资源。Fair Scheduler两个关键问题如何选择合适的作业执行默认是FIFO策略，此外还有一种基于缺额的策略。Fair Scheduler为每个作业定义了一个deficit(缺额)指标。Deficit是一个作业在理想情况下的获得的计算资源和实际中获得的计算资源之间的差距。Fair Scheduler会每隔几百毫秒观察每个作业中有多少任务已经在这个时间间隔内执行，并将结果与它应得的资源份额比较，以更新该作业的deficit值。一旦有空闲的task tracker出现，首先分配给当前具有最高deficit值的作业。例外如果系统中存在着尚未获得最低资源保障的作业池，那么该池中的作业将会优先调度，而选择池中的作业需要根据它们的deficit来决定。这样做是为了尽可能满足作业池最低保障资源份额的机制。Fair Scheduler两个关键问题如何确定每个作业的资源份额缺省情况是平分资源，此外提供一种基于权值的资源分配方法。作业资源份额的计算是根据作业的权值将集群的资源总量划分给各个可以运行的作业。默认情况下，权值基于作业优先级，每个优先级对应的权值是低一个优先级的2倍(优先级共有VERY_HIGH,HIGH,NORMAL,LOW,VERY_LOW五个等级，则VERY_HIGH具有4倍NORMAL的权值)。作业和作业池的权值可以在池配置文件中进行设定，例如可以基于作业的大小和提交时间来设定。作业池的最低资源保障也是按照权值比例分配给其中的作业。计算能力调度Capacity Scheduler Capcity Scheduler基础知识Capcity Scheduler一个关键问题Capcity Scheduler内存管理Capcity Scheduler的配置Capcity Schedule基础知识基础知识Capacity Scheduler是由雅虎提出的作业调度算法，它提供了类似于Fair Scheduler算法的功能。Capacity Scheduler中可以定义多个作业队列(multiple queues)，作业提交时将直接放入到一个队列中。每个队列都可以通过配置获得一定数量的task tracker资源用于处理map/reduce操作，调度算法将按照配置文件为队列分配相应的计算资源量。对于已经分配给了某队列但处于空闲的资源各个“忙”的队列会分享它们。当某一队列没有能够按照配置的数量值获得足够资源但是它的作业压力增加了时，之前那些曾分配给它但又由于之前空闲被别的队列所占用了的资源会在完成当前task后立即分配给回应属的队列。Capcity Schedule基础知识基础知识Capacity Scheduler的每个队列中采用的调度策略是FIFO算法。Capacity Scheduler默认情况下不支持优先级，但是可以在配置文件中开启此选项，如果支持优先级，调度算法就是带有优先级的FIFO。Capacity Scheduler不支持优先级抢占，一旦一个作业开始执行，在执行完之前它的资源不会被高优先级作业所抢占。Capacity Scheduler对队列中同一用户提交的作业能够获得的资源百分比进行了限制以使同属于一用户的作业不能出现独占资源的情况。Capcity Scheduler一个关键问题如何选择合适的作业去执行为队列定义了一个指标队列中正在运行的任务数与其应该分得的计算资源(配置文件中为此队列分配了相应数量的资源，而实际中该队列可能没有分配到)之间的比值。当系统中出现空闲的task tracker，算法会首先选择一个该比值最低的队列。队列被选中后，将按照作业优先级(如果支持的话)和提交时间顺序选择执行的作业。在选择作业的时候，还需要考虑作业所属的用户是否已经超出了他所能使用的资源限制。此外，还会考虑task tracker内存资源是否满足作业的要求。Capcity Scheduler内存管理内存资源的有效管理Capacity Scheduler能有效地对hadoop集群的内存资源进行管理，以支持内存密集型应用。作业对内存资源需求高时，调度算法将把该作业的相关任务分配到内存资源充足的task tracker上。在作业选择过程中，Capacity Scheduler会检查空闲task tracker上的内存资源是否满足作业要求。task tracker上的空闲资源(内存)数量值可以通过task tracker的内存资源总量减去当前已经使用的内存数量得到，而后者包含在task tracker向job tracker发送的周期性心跳信息中。目前，基于内存的调度只能在linux平台下起作用，关于内存调度的相关参数可以通过配置文件来设置。Hadoop公平调度器算法解析公平调度介绍hadoop-0.20.2公平调度算法分析 基于缺额的调度算法1.变量定义2.相关算法hadoop-0.21.0公平调度算法分析 层次调度算法公平调度介绍公平调度器按资源池（pool）来组织作业，并把资源公平的分到这些资源池里。默认情况下，每一个用户拥有一个独立的资源池，以使每个用户都能获得一份等同的集群资源而不管他们提交了多少作业。按用户的 Unix 群组或作业配置（jobconf）属性来设置作业的资源池也是可以的。在每一个资源池内，会使用公平共享（fair sharing）的方法在运行作业之间共享容量（capacity）。用户也可以给予资源池相应的权重，以不按比例的方式共享集群。公平调度介绍除了提供公平共享方法外，公平调度器允许赋给资源池保证（guaranteed）最小共享资源，这个用在确保特定用户、群组或生产应用程序总能获取到足够的资源时是很有用的。当一个资源池包含作业时，它至少能获取到它的最小共享资源，但是当资源池不完全需要它所拥有的保证共享资源时，额外的部分会在其它资源池间进行切分。公平调度介绍主要特点如下：支持多用户多队列 资源公平共享（公平共享量由优先级决定）保证最小共享量 支持时间片抢占 限制作业并发量，以防止中间数据塞满磁盘Pool资源池，或者作业池。每个pool里有一定量的资源（管理员配置），每个用户属于某个pool，其作业可使用这个pool中的资源，可限定每个pool中最大并发作业数和每个用户最多提交作业数。默认情况下，一个linux用户对应一个pool，而管理员也可以配以一个linux group对应一个pool。pool实际上也可以称为group或者队列。最小共享量管理员可给每个pool配置一个最小共享量，调度器在分配资源时，需要保证每个pool中的作业至少获取该数目的资源。一个常见的应用场景是，对产品pool设置最小共享量，而测试pool不设置，这样，当可用资源有限时时，优先保证产品pool有资源可用。公平共享量当集群中存在多个pool时，某些pool中的资源可能用不了，这时候调度器会自动将这些pool中剩余的资源共享给其他需要的pool，其他这些pool获取的共享资源多少主要由其pool weight决定，pool weight越大，获取的资源越多。一个pool的最小共享量加上其获取的共享资源数目，就是公平共享量。公平调度算法分析变量定义描述job信息的变量(JobInfo)jobWeight：作业的权重。实际计算时，map阶段和reduce阶段分开，分别记为mapWeight，reduceWeightjobDeficit：作业的缺额，即作业在理想调度器上所应得的计算时间与实际所获得的计算时间的缺额，这个是测量作业的“不公平”待遇的度量标准。实际运算时将map阶段和reduce阶段分开，分别记为mapDeficit和reduceDeficit。公平调度算法分析变量定义runningTasks：作业正在运行的task数。实际计算时，map task和reduce task需分开，分别记为：runningMaps和runningReducesminSlots：作业在相应的pool中的最小slot保证量，实际计算时，map阶段和reduce阶段分开，分别记为：minMaps和minReducesjobFairShare：上次更新给该job分配的公平共享量，实际计算时，map阶段和reduce阶段分开，分别记为mapFairShare和reduceFairShare公平调度算法分析变量定义l计算过程的中间变量poolWeight：pool的权重，这个可由用户自己设定，默认为1。tasksNum：某个作业正在运行任务与尚未运行的任务（包括Speculative 任务）数量和，有两种task类型：map task和reduce task，计算时需要分开priorityFactor：与作业优先级相关的因子，用于计算作业的权重，具体如图：prioritypriorityFactorVERY_HIGH4.0HIGH2.0NORMAL1.0LOW0.5Default0.25公平调度算法分析变量定义poolRunningJobsWeightSum：pool中已经开始运行的所有作业的权重之和poolLowJobsWeightSum：在某个pool中，已经开始运行的，但尚需slot（tasksNum数量大于其最小共享量）的那些作业权重之和systemJobsWeightSum：系统（可能有很多pool）中可以运行的所有作业的权重之和timeDelta：两次信息更新的时间间隔公平调度算法分析相关算法当出现一个空闲slot时，公平调度器会将此slot分配给缺额最大的作业。系统每隔500毫秒（UPDATE_INTERVAL）更新一次信息（有一个专门的更新线程对job信息进行更新），包括：作业缺额（作业的其他属性，如权重、最小共享量、公平共享量等，均是为计算缺额服务的）、权重、最小共享量、公平共享量等。公平调度算法分析相关算法1)作业权重计算方法（1）默认情况下，权重是基于作业优先权的，但也可以基于作业的大小和年龄。权重的计算方法如下：（2）根据优先权计算权重：（3）根据用户自定义的weightAdjuster类调整权重公平调度算法分析相关算法2)更新权重每个已经运行的作业权重更新公式：3)初始缺额计算每个作业的初始缺额mapDeficit,reduceDeficit设置为0.4)更新作业的最小共享量在每个pool中，将其拥有的slot按作业的权重分配给各个作业（由步骤(1)完成），分完之后将剩余的slot按作业的权重和缺额分配给仍需slot的作业（由步骤(2)和(3)完成），如果还有slot剩余，则将这些slot共享给其他pool。公平调度算法分析相关算法初始化：当前所有作业的最小共享量置零；pool的minMaps数或者minReduces数（由用户在配置文件中设定）重复以下几步，直到slotsLeft=0：公平调度算法分析相关算法（1）计算每个job的最小共享量：jobinfo.minMaps或jobinfo.minReduces首先计算该作业可获得的共享值：根据当前pool的剩余slot数，调整该共享值：其中runnableNum表示作业尚需的slot数与正在运行的slot数之和，curMin表示作业的当前最小共享量（jobinfo.minMaps或jobinfo.minReduces），初始值为0。将slotsToGive作为最小共享量赋予相应的job。修改值为值减去slotsToGive。如果此轮循环中，slotsLeft值未变，即没有slot分给任何作业，则将剩余的slot共享给pool中所有job，即，执行（2）（3）并结束算法：公平调度算法分析相关算法（2）将pool中的job按weight和deficit排序（3）按顺序依次计算每个job的最小共享量。首先计算该作业可获得的共享值：根据当前pool的剩余slot数，调整该共享值：将slotsToGive作为最小共享量赋予相应的job。修改slotsLeft值为slotsLeft值减去slotsToGive。需要注意的是，当执行完（2）（3）后，slotsLeft可能仍大于0，这时候会将剩余的slotsLeft个slot共享给其他pool。公平调度算法分析相关算法5)更新公平共享量主要思想：基于作业权重和最小共享量计算公平共享量。首先，根据权重分配可用slot数，如果作业的最小共享量大于公平共享量，先要满足最小共享量，更新可用slot数，重复以上步骤，直到所有作业的最小共享量小于或等于公平共享量，这样，每个作业的最小共享量都得到了满足，最后，所有作业平分剩下的slot数。公平调度算法分析相关算法算法实现：初始化：当前所有作业的公平共享量置零；slotsLeft=系统中map slot 或者reduce slot 总数；jobsLeft=系统中正在运行的作业(1)遍历集合jobsLeft中的所有作业，计算每个作业的jobFairShare：如果作业的最小共享量（minSlots）大于公平共享量（jobFairShare），则：将最小共享量作为公平共享量赋值给作业。同时将此作业从集合jobsLeft中删除。（2）将剩下的slot按权重比例给集合jobsLeft中剩余的作业：将jobFairShare作为公平共享量赋值给作业。公平调度算法分析相关算法6)更新缺额实际计算时，会分开：7)资源分配当系统中产生一个空闲slot时，将此slot分配给缺额最大的作业。Hadoop-0.21.0版本公平调度器新特性(1)将之前（0.21.0之前版本）的基于缺额的调度算法改为层次调度算法(2)支持资源抢占(3)添加delay scheduling机制，使调度策略更优。(4)每个队列的调度策略可以配置，支持两种调度策略，分别为FIFO和FAIR，不管采用哪种调度策略，以上三个功能全部支持。层次调度算法大的思想与Capacity Scheduler类似，首先选择一个pool，然后从该pool中选择一个job，最后从该job中选择一个locality的task。其中，选择pool和job的策略相同，均采用了FairShareComparator比较器对pool或者job进行排序，然后从头到尾扫描队列，选出合适的pool或者job。在FairShareComparator中，Schedulable封装了是一个pool或者job的基本信息。资源抢占当一定时间（管理员可配置）内，某个pool中获取的资源量少于最小共享量，或者公平共享量的一半，则调度器会找出哪个pool抢占了该pool的资源，并杀死相应数量的task以抢占资源。之所以要进行抢占，还是为了“公平”，即：保证每个pool能获取到它应得到的资源。delay scheduling机制当出现空闲slot时，如果排在队列前面的job对应的所有task均没有locality特性，则该作业会延迟调度，直到一段时间后，该job出现locality的task或者发生超时，才不得不调度该job的task。有些人可能不了解locality，在此解释如下：当出现空闲slot时，该slot来自某个节点，而该节点上存有部分数据，如果某个task所需要的数据正好位于该节点上，则将该slot分配给该task是非常好的，因为它避免了通过网络读取数据。公平共享量计算方法公平共享量是基于最小共享量和共享资源量计算得到的，它反映的是某个pool经过资源共享（某些pool的资源用不了，会自动共享给其他pool）之后，一共可以获取的资源总量，一般会大于等于最小共享量。如果每个pool没有配置最小共享量，且提交了无限量的作业，则让每个pool的slotsAssigned/weight值相同即可。（其中slotsAssgined表示分配给该pool的slot数，weight表示pool的权重）。而有了最小共享量minShare和pool中的需求量demand（该pool中所有作业尚需的slot总数）后，计算公平共享量fairShare需注意以下两种情况：(1)某些pool中的最小共享量可能用不完(2)给配给某些pool的资源量小于其最小共享量公平共享量计算方法考虑到以上两种情况，调度器设计了基于比率R的公平资源分配方法（设集群中资源总量为totalSlots）：1 如果一个pool的demandweight，则该pool的fairShare=minShare3 除此之外，所有pool的fairShare=R*weight4 所有pool的的fairShare之和应为totalSlots通过以上算法计算出的公平共享量即为“公平调度器”的“公平”含义之所在，应尽量保证每个pool获取的资源量为fairshare，如果一定时间期限内达不到，则抢占资源。公平共享量计算方法公平调度器缺点新版本的调度器仍不支持大内存作业，而Capacity Scheduler则早有了支持，其原理是：如果一个job需要较大内存，调度器会为该job分配多个slot，这样，作业可使用这些slot对应的内存资源。