精华内容
下载资源
问答
  • 并行分布仿真对复杂大规模动态系统的研究以及探索,对长远的应用提供...在分别论述四类基本的时间推进同步机制,即保守机制、乐观机制、混合机制和自适应机制的同时,还分析了各自的优缺点,指出了今后的研究发展方向
  • 提高GPU性能开发分布式并行图形绘制技术成为了提高绘制性能的两个主流方向。但对大规模的场景实时绘制的应用而言单GPU的处理能力仍满足不了需求,并行绘制成为了唯一的选择。分布图形并行绘制系统从最

    近年来图形学应用出现以下几个特点:模型复杂度急剧增大,场景对象更加复杂,绘制真实感要求更高,显示分辨率呈子数级递增以及真实感与实时性统一的要求。这些特点最终体现在对计算机图形硬件的绘制性能提出了更高的要求。提高GPU性能与开发分布式并行图形绘制技术成为了提高绘制性能的两个主流方向。但对大规模的场景实时绘制的应用而言单GPU的处理能力仍满足不了需求,并行绘制成为了唯一的选择。分布图形并行绘制系统从最初的专用并行绘制硬件发展到现在日渐完善的建立在高速网络上的基于PC集群的分布式并行图形绘制系统。并大量应用于大规模战场仿真、流体仿真与可视化、高性能建模、模拟驾驶、海量高维信息实时可视化等领域。

           集群并行绘制系统虽得到广泛应用,但仍然有许多问题没有得到很好的解决或者有待进一步提高:如采用什么样的结构来组织集群的图形绘制流水线、如何划分绘制任务、如何同步控制保证所有机器协同完成绘制任务、采用什么样的方法来实现系统的负载均衡等。这些问题都相互交织,很难将他们割裂开。一个问题的解决方案的选择总是对其他问题解决方案的选取产生重大影响。下面将选取几个典型的问题加以讨论。

    1、体系结构的选取

         Molnar等人根据归属判断在图形绘制流水线中发生的时机将集群并绘制系统的体系结构归纳出三种基本类型:sort-first、sort-middle、sort-last。其中sort-middle一般需要特定的图形硬件支持,在PC集群的并行绘制系统中一般不采用这种体系结构。对其他两种体系结构而言,不同的体系结构有着自身特有的优势适合于某些特定的应用环境,同时也带来不同的系统瓶颈。对sort-first型系统而言任务划分、负载均衡是其难点,对sort-last型系统而言图像传输、合成是个瓶颈问题。

           实际中的应用完全按照上面这三种基本类型的体系结构来开发并行系统,并不能很好的解决问题,因此如何根据应用需求选取一种并行绘制的体系结构或者开发一种混合的体系结构是并行绘制的基础性工作,它决定了任务的划分、负载的控制等的解决方法的选取。

    2、绘制任务的划分与分配

           在大规模场景绘制应用中,并行绘制处理的对象是大规模的场景数据,并行绘制的计算任务为点、面、体所表示的图形对象。任务划分就是控制节点按照一定的规则将这些数据分配给集群中绘制服务器处理的过程。面对海量的场景数据,从系统的整体效率角度考虑,不可能按照点面体这些基本的图形对象来划分,因此必须选择一定的划分粒度实现绘制任务的划分,随之带来的问题就是如何选择任务划分的粒度与任务划分的方式,使得按照这种方法进行的任务划分能够最大限度的提高系统性能的性能。

           绘制任务划分好之后,绘制任务如何分配到各个绘制服务器上?在实时交互式系统中,场景与视点随着时间的变化经常发生改变,场景数据在二维平面空间上的分布也随之发生改变,必然需要进行任务的重新划分,在这种情况下,数据如何在绘制服务器之间进行调度。这些就是并行绘制中的任务分配与调度机制需要解决的问题。

    3、负载均衡策略

           良好的负载均衡是提高并行绘制系统性能的必要条件,也是并行绘制系统一直没有得到很好解决的一大难题。对并行绘制系统而言,在本帧数据绘制完成之前,是无法准确得出其绘制开销的,如何选取一个行之有效的负载度量标准完成对场景负载分布的估计(即量化工作负载)是做负载均衡必须解决的首要问题,因为负载度量的标准直接影响负载均衡算法的性能。

        不同的体系结构做负载的重点难点有所不同,但总体来说它们都必须解决如下三个问题:其一、如何根据集群并行绘制系统所处理的特定图形应用和场景数据来确定绘制任务的划分、分配、调度策略,使得集群中各个绘制节点的负载大致相当,并保持系统始终处于相对稳定。其二、当负载分布发生改变时,如何评判系统是否处于均衡状态,当系统失衡时,如何合理的调整各个绘制服务器之间的负载使得系统迅速重新达到负载均衡状态。其三、如何降低负载均衡算法本身的开销,以最小的代价达到最佳的均衡性效果。

           对sort-last型并行绘制系统而言,负载均衡较为容易实现。但对sort-first型而言,任务划分的方式、粒度大小与负载均衡密切相关,总体来说任务划分的粒度越小越容易达到负载均衡,但同时增大了任务划分与负载均衡的计算量。所以在良好的均衡效果与简明高效的算法实现上找到一个平衡点是sort-first型并行绘制系统的负载均衡研究的难点。

    4、同步控制与容错处理

           集群中所有绘制节点收到各自的绘制任务后,相互独立的完成各自的绘制任务。如何保证集群中所有绘制与合成节点协同工作以保持系统正确流畅的运行(即:整个系统的帧率保持稳定,最终显示结果正确。)?其次,在实时交互式系统中,交互指令的响应须有严格的实时限制。当系统出现绘制任务堆积与实时交互指令的到来的情况,如何处理合理的处理堆积任务与实时交互的硬实时的矛盾,使得系统不仅能够提供良好的人机交互体验,而且能够保证画面的流畅?再次,集群并行绘制系统中每个节点共同为整个系统的正常运行服务,集群中的每一台PC的正常与否与整个系统能否正常运行有紧密关系。系统不允许出现这样的情况:因其中一台PC因故障宕机后造成整个系统的崩溃。如何采取一种容错处理策略使得系统能够快速地从故障中恢复,避免因为集群中的某几台PC出现故障而使整个系统崩溃的情况发生。

    5、绘制结果的合成显示

           面对高分辨率显示的需求,单一显示屏已无法满足应用,因此无论对于sort-first型还是sort-last型的并行绘制系统而言都需要做同一件事情:将各个绘制服务器的绘制结果进行合成并分发显示,对sort-first而言做的是最终图像的拼接与分割,对sort-last而言则进行的是对各个绘制节点的绘制结果做基于深度的图像合成。面对高分辨率的图像,无论是像素的拼接还是基于深度的合成其开销均不可忽略,如何在现有的硬件条件下快速的实现绘制结果的合成使之不影响系统的整体绘制性能是提高并行绘制系统性能的又一因素。

    6、网络带宽瓶颈

           一方面随着绘制真实感的不断增强,模型的精细度、场景的复杂程度不断增强,场景数据量也不断增加;另一方面近年来显示分辨率呈子数级递增,每帧图像的数据量也急剧增长。并行绘制系统运行过程中,场景数据的传输与绘制结果的传输对网络带宽的需求已成为制约并行绘制系统性能的又一重要因素。现单以sort-first型的绘制结果的传输来说明系统的网络带宽:假设系统由五块单屏分辨率为2560*1440的显示器拼接显示,则绘制结果的最终合成的显示分辨率为12800*1440,系统帧率为60FPS,图像格式采用RGBA,则1s内系统传输的数据量采用如下计算:

           12800*1440*4*60Byte = 4423680000Bytes = 4.12GB

           对sort-last型而言带宽则更高,负责合成的节点的带宽需求与绘制服务器的台数成线性关系。这样的带宽需求无论是对于基于传统TCP/IP体系的千兆以太网还是其他体系的网络设备而言都是不小的挑战。如何根据市面上现有的网络硬件设计系统的网络体系结构与数据格式来满足系统的带宽需求?

    展开全文
  • 《大数据:互联网大规模数据挖掘与分布式处理》源自作者在斯坦福大学教授多年的“Web挖掘”课程材料,主要关注大数据环境下数据挖掘的实际算法。书中分析了海量数据集数据挖掘常用的算法,介绍了目前Web应用的许多...
  • 《大数据:互联网大规模数据挖掘与分布式处理》源自作者在斯坦福大学教授多年的“Web挖掘”课程材料,主要关注大数据环境下数据挖掘的实际算法。书中分析了海量数据集数据挖掘常用的算法,介绍了目前Web应用的许多...
  • 分布式系统设计

    热门讨论 2007-07-12 15:59:47
    显然,未来对计算速度、系统可靠性和成本实效性的...第12章包括分布式设计在操作系统、文件系统、共享存储系统、数据库系统和异型处理中的应用,同时列出将来可能的研究方向。附录包括了DCDL中的常用符号列表。
  • 并行数据库技术分析发展展望

    千次阅读 2014-12-17 11:51:29
    最后展望一下并行数据库的未来发展方向。 一、并行数据库的定义和架构特点 在维基百科上,并行数据库被定义为通过并行使用多个CPU和磁盘来将诸如装载数据、建立索引、执行查询等操作并行化以提升性能的数据库系统...
    我将首先描述什么是并行数据库以及它们的典型特征;然后从存储、执行、管理等方面分析其技术要点;最后展望一下并行数据库的未来发展方向。
    

    一、并行数据库的定义和架构特点

    在维基百科上,并行数据库被定义为通过并行使用多个CPU和磁盘来将诸如装载数据、建立索引、执行查询等操作并行化以提升性能的数据库系统。其中最重要的关键词是并行

    在组成大规模计算机集群的时候,通常有两种特性要考虑:并行和分布式。并行强调多节点同时执行,共同解决一个大问题,通常在严格的高性能网络环境中,有严格的执行要求和反馈时限。因此,并行和并发大多数时候是矛盾的两面,您不应该指望并行数据库能在极短的时间处理大量的请求,因为它是为了解决大问题而设计的,而不是大量的小问题。

    分布式则是另外一个特性,它强调数据或计算分布在不同的节点,并对上提供透明性。它可以是分布在一个广域网上,提供位置透明性,比如CouchDB那样;也可以像Mysql网关那样,提供任务透明性。

    因为目的不一样,通常在设计运行在大规模集群的软件的时候,不会同时追求这两者。MPP数据库被设计为最求极致的并行,即使仅查询一条数据的SQL,也会被扔给所有的数据节点来执行;而HDFS则不是这样,它不会要求一个文件块完全分布在所有的数据节点上,并同时提供访问,它只需要将一个文件按照顺序分成几个块分布在数个节点上即可,一个接一个地被访问。因此一个HDFS数据节点失效影响不了全局;但是一个MPP的数据节点失效会影响全局。这是两种特性的典型差别。其它的软件分布在中间,按照应用的需求,或者偏并行一些,或者偏分布式一些。理解了这个“并行”的特点对理解并行数据库的设计非常重要。

    通常我们构建一个数据库集群的时候,可以采取Share Nothing、Share Disk和Sharding三种方式,其中前两个都可以视为并行数据库的范畴,其中Share Disk不属于极端的并行;后一个其实是分布式的范畴,它被普遍应用在构建事务处理型系统(OLTP)上,我们在这里不做展开讨论。

    Share Nothing因为基本没有“共享”的环节,因此非常适合做“并行”。1983年的Teradata、1984年的DB2就是典型的Share Nothing并行数据库架构。当前典型的MPP数据库,比如Gbase 8a、Vertica、GP、ParAccel仍旧采用这样的架构。

    Share Disk因为共享了磁盘,其实不适合做“并行”。因此其传统的产品,比如Oracle、Sybase什么的并行其实不是太好。以前都是通过任务间的并行把负载拉起来,后来任务内读的并行部分解决了,但任务内写的并行仍旧很难,Oracle在保证执行节点之间信息同步的开销很大。

    最近几年出现的SQL over Hadoop方案在架构上也可以视为Share Disk,不过这个Disk不是一个集中的磁盘阵列,而是一个分布式的文件系统而已。

    如果是SQL over Hadoop的情况下,这个SQL引擎本身又是并行的,而且直接跑在Hadoop集群之上,看起来似乎和典型的MPP架构一样,都是Share Nothing的。但是实际上,还是有很重要的差别。因为HDFS是一个分布式文件系统,因此通常情况下它对SQL引擎(或称为执行引擎、查询引擎)的集群是透明的,SQL引擎的集群既不能控制一个表分散在所有的节点上,也不能控制可能会被同时访问的几个表放在一个节点上以便执行控制在一个节点内的join操作。它唯一能利用的就是HDFS的数据本地性特性,类似Hbase一样,SQL引擎自己写入的数据可以优先写本节点的磁盘。这种透明性使得SQL over Hadoop的方案可扩展性很好,或者说分布式的特性展现得不错。但是并行性能就稍微差一些,这个后面有所分析。

    虽然Hadoop被视为处理大数据的首选工具,但不应该忽视并行数据库的作用。eBay、Facebook、Twitter把典型的并行数据库作为它们大数据工具箱中的一种。在中国移动的集中化大数据平台中,因为我们有大量的结构化数据,也有大量的即席查询,因此我们也使用了MPP数据库,目前单个集群最大规模为300节点。

    很明显,因为并行数据库的技术特点是为了某类需求设计的,因此它有自己的适用环境。首先因为它采用关系理论,因此它仅适合结构化数据,非结构化或者说某些半结构化数据当然也可以在其中存和取,但是实际上有很多更好的解决方案可以选择。其次还是因为它采用关系理论,关系代数和关系演算是其擅长的,因此它在并行计算,特别是复杂的多表关联、流水线等一系列操作中特别擅长,如果只是存入和取出的话,NoSQL会更加适合。再次,因为并行数据库的SQL语言是一种申明式的语言,甚至当初设计的目的并不是给程序猿使用,而是给业务人员用的,因此在处理日常重复性任务的时候有更好的解决方案,比如MapReduce和Spark。最后一点因为并行数据库需要在数据分布(计算Hash)和存储格式(比如列存、压缩、索引、页面统计信息等)方面进行较多的处理以便为查询进行优化,因此装载数据是比较耗费精力,时间较长的。因此入库后只会被读取少数次的任务最好不要麻烦它来做。

    并行数据库目前的主要问题来自于它的设计目的,因为要实现完美的并行,因此它大多被设计为计算和存储紧密耦合,这样计算可以控制每行数据的存储位置和每个数据块的存储格式,这样对大任务提供了很好的性能(类比于“鱼”)。同时也使得系统鲁棒性不高,这体现在一个节点退服后性能下降严重,两个节点退服有全库停止的可能。另外系统扩展性也收到了限制,一是规模不能太大,二是基本需要对等性能的机器,三是重新计算Hash并移动数据是非常麻烦和缓慢的(类比于“熊掌”,目前是鱼与熊掌不可兼得)。

    二、并行数据库技术要点分析

    并行数据库主要由执行引擎、存储引擎和管理功能模块组成。它们的不同技术风格形成了各个有特色的并行数据库产品。

    因为是大规模集群的数据库,所以首要要面对的就是节点的风格。其中最重要的就是主节点,类似HDFS中的NameNode,主节点要承担入口、元数据管理、SQL Parser、生成执行计划和任务调度、管理两阶段提交等功能。目前有两种方式:有专职Master和无专职Master。

    从开源的PostgreSQL演变来的并行数据库多为有专职Master的,因为这样代码最易分开,比如GP等。这种架构比较简单,因此数据节点的对等性比较容易维护,不会形成性能短板。它们的Master形成了主备模式,切换的时候影响比较大,而且主节点的动态伸缩也是问题。

    从头设计的并行数据库多为无专职Master的,比如Gbase 8a和Vertica。数据节点和Master节点代码部署到一台物理机,被连接上即充当此次连接的Master。其优点是足够的扩展性和更好的高可用,但是缺点在于Master的进程可能拖慢数据节点,形成性能短板。而且Master之间的元数据同步也是一个负担。

    两种方式各有优劣,在大规模集群下,无专职Master架构优势更加明显,其向“多Master”架构发展也很容易,比如Gbase8a已经支持这种模式,Vertica在大集群模式下支持这样的部署方式。我认为多Master是未来方向,这样在提供良好的扩展性和高可用的同时,也保持了数据节点的对等性。

    在存储引擎中最为关键的就是数据分布。按行进行Hash分布是并行数据库的重要特征。其它数据分布方式无法精确控制数据摆放,也无法提供足够的用于查询优化的存储信息。

    就像之前说的那样:这种紧密耦合的非透明的方式带来了巨大的好处(同样分布的表的高效关联),同时也带来了麻烦(扩展性、高可用等)。鱼与熊掌不可兼得。

    一些改进的SQL over Hadoop方案借用了这一点,比如HDFS Colocation、Pivotal HAWG、Vertica VIVE等。注意前者和后两者不一样。前者在NameNode中加了一个表用来存储Hash元数据;后两者自己实现Hash表的管理,主要用到的是HDFS的目录功能,利用数据本地性原则来优化。

    没有解决Hash分布的解决方案都难以处理多个大表关联(Join)的问题,它们多通过预关联的方式来规避这个问题,形成某种类似OLAP多维立方体的解决方案(比如Google Dremel、Mesa,eBayKylin等);或通过shuffle实现重新分布(比如Hive或者SparkSQL)。

    解决了数据分布以后,就要思考计算好Hash后的数据在一个节点中怎么存。通常三种方式:行、列或者行列混合。

    它们有各自的适用场景。值得一提的是“仅列存储”与“列存储+针对性优化的执行引擎”有很大差别。如果存储引擎和执行引擎进行了联合的深度优化,那么原则上,如果列已经排序好后重复的行是可以消除的。比如记录“第一行到第五亿行为男”,“第五亿到第十亿行为女”,这样只用两行数据即可,Vertica和Gbase 8a可以做到这点。而仅将列存储作为存储引擎的一种是无法做到这点,只能存储十亿行进行字典压缩后的“男”和“女”。现在几大老牌的数据库提供商还提供行列混合的方案,比如Oracle、IBM和Teradata都提供,不过似乎在生产系统中,很少看到这样的例子出现。

    行存储、列存储方式的测试结果显示了不同的存储方式的不同特性,行存装载普遍比列存储快,但是查询起来一般都要慢许多。因此需要根据应用访问的需要来选择存储方式。如果是一次装载、多次查询的分析型应用,基本是选用列存储的方式。

    选择了行列存储格式和压缩算法等,接下来就要考虑到底存储到什么“存储系统”上。最早数据库多选用裸设备,因为当时的存储很贵,性能又不行,因此要努力减少哪怕一点点的性能损失。但是在类似X86的开放硬件环境中,这会使得软件很复杂。这种用软件复杂度换取硬件成本的方式随着摩尔定律的不断作用而变得不经济。因此现在数据库大多就直接使用操作系统文件系统,这样屏蔽了很多不同硬件和操作系统的细节问题。

    HDFS等分布式文件系统出现后,又多了一种选择。这是一个新的方向,提供了多一些可能。可以有两种使用方式:作为一个本地文件系统看待,或者以外部表的方式,后面有具体的情况分析。

    最后要考虑的是硬件问题。目前典型的并行数据库多使用SAS磁盘,而HDFS使用的容量更大、价格更便宜但性能和可靠性稍差的SATA磁盘。使用这种慢速的磁盘是并行数据库目前最大的瓶颈,使得它无法实现效率和可扩展高可用的兼得,也就是鱼与熊掌不可兼得的难题主要来源就在于此。磁盘IO的速度难以匹配摩尔定律要求的速度,但是电子盘和内存是可以的。随着后两者的价格快速下降、性能快速提高,并行数据库可能又将面临一次重大的变革,并解决那个难题。

    并行数据库目前主要的数据存储仍然使用磁盘,电子盘和内存盘最多只能作为缓存来使用。我认为接下来的1到2年,我们很快就将面对以SATA接口的SSD替代SAS磁盘的过程。现在一些高端的并行数据库一体机已经可以采用全SSD的配置了。目前的并行数据库几乎不用任何代码的改动,就可以运行在SSD之上。

    但是,因为硬件特性的不一样,只有全新设计一个并行数据库系统才能最佳发挥SSD的作用。因为现有的并行数据库系统是为了旋转磁盘的特性设计的,为了将随机的读写转换为顺序的读写,用了非常多复杂的机制和复杂的代码。比如用内存来缓存写入或更新的数据,到达一定的块容量后再顺序写入磁盘,但是这给事务处理带来了麻烦,因此内存是断电后数据无法持久,所以数据还有“活动”和“非活动”之分。当然事务日志也有“活动”和“非活动”之分,为了保证数据和日志的一致性,它们还得互相配合,这样就多了很多代码。如果单个数据或者一小块数据的随机访问速度和顺序访问相当,那么就没有必要这样做,节省下的代码将提高效率、提高系统的稳定性、可用性和扩展性。

    我认为未来是内存为王的时代,天下武功为快不破。内存是数据存储的终极目标。目前柏睿Rapids DB和HANA等产品就是将内存作为数据的实际存储地方,SSD只是拿来做快照和日志的存储而已。这种方式,将解决MPP面临的“鱼与熊掌不可兼得”的问题。在短期内,这种方案不能成为所有数据存储的选择,但是我坚信硬件的发展是持续的,用硬件来解决软件的问题是最直接有效的方式。因为内存的易失性,并不能简单的将数据存储从SSD转移到内存中,这将面临一次更多的、更彻底的并行数据库软件平台的重新设计

    存储引擎的关键技术点分析就是这些。接下来分析查询引擎。查询引擎因为它是面向计算的,已经发展得比较充分。典型的MPP和新型的SQL over Hadoop都大量借用了传统数据库的这些功能。比如基于成本的优化器、流水线、多版本的并发管理等。

    接下来是高可用。这里的高可用指节点失效的情况下,通过机制(一般是副本)屏蔽对数据库的影响。不包括为了保证数据安全所做的备份。容灾、双活可以视为远端高可用。

    不同的数据库有不同的副本策略。比如有的采用数据同步的方式,有的采用同步操作本身;有的几个副本都执行完才算成功,有的完成两个就可以,第三个可以异步完成,异步检查。

    不同的数据库有不同的副本分布。比如有的以节点为单元形成副本,有的以进程为单元形成副本从而形成了逻辑节点。逻辑节点的方式比较容易,这样一个物理节点的副本可以分散在数个物理节点之上,出现问题后的负荷也是得到了数个物理节点的分担。

    同样,不同的数据的高可用等级是不一样的。有的数据库出现故障以后,应用侧基本没有感知,故障恢复过程中也没有感知。有的数据会阻断当前应用,但是重新连接后马上又可以用了(秒级切换)。有的数据库需要等数据库重启一下以后,副本才生效。在并行数据库技术发展尚不成熟的时候,甚至有在故障情况下或故障恢复过程中不允许写数据,只能读的情况出现。这些在选择内存数据库的过程中都需要了解和测试。

    考大家一个问题。如果有一台24个节点的数据库,其中一台节点出现故障,这个时候应该启用副本吧。那么在数据不分布的情况下,这23个节点(带病工作状态)上执行的任务时间相比原来要延长多少?4%、10%还是100%?

    答案是取决于系统的负荷和不同的产品,不过有一点可以确定的是,超乎想象。这是一个我们的测试结果。24个节点退服一个的情况下,不同产品的读的性能下降和写的性能下降的情况。

    注意这不是满负荷(CPU BOUND或IO BOUND)的情况,这不是一个成比例的下降。100个节点和1000个节点会面临与此类似的情况,不能增加节点来解决这个问题。因此节点的退服影响很大,这和Hadoop非常不一样。具体的原因和解决办法可以参考我之前写的博客。

    简单的说产生这个问题的原因就在于Hash分布。Hash分布带来了极致的并行(鱼),同时破坏了存储和执行之间的透明性(熊掌),因此深度的绑定导致出现问题的节点的任务无法分散在所有节点,只能由备机所在的节点承担。

    同样影响的是线性扩展性,目前世界上最大的MPP生产集群是300个节点。而且大家都倾向用性能更好的胖节点来减少节点的数目。比如我们的设备就有24个SAS盘位。扩展的时候移动数据也是一个花费很大的开销。

    因为并行数据库是大数据基础设施中的一部分,所以与Hadoop的集成就变得很重要。我列举了一些典型的方式。比如作为MR的数据源或者目的地,通过InputFormat\OutputFormat像Hbase那样被MapReduce访问;或者通过连接器实现数据的双向互通;或者并行数据库将HDFS作为一个文件系统,在这种方式下不同的节点的数据写入HDFS的不同目录,在HDFS尽量提供数据本地化放置的时候甚至可以像HBase那样绕过DataNode的进程直接访问操作系统的文件块;以外部表又是另外一种方式,在这种方式下只能通过HDFS的接口来访问数据,没有数据本地化的可能,因为数据不是通过执行引擎写入的,而是本来就是HDFS上,其放置方式执行引擎一点也无法控制。其它的方式还有表函数以及在数据库上提供一个MR框架,现在已经很少使用。

    其它的关键技术点也很有意思,这些都很重要,今天时间有限就不一一展开了。

    小结一下。目前我们可以看到三类典型的并行数据库架构风格:

    最左侧是以Gbase8a、Vertica、GP为代表的典型的MPP数据库。数据采用Hash分片,存储引擎和执行引擎紧密耦合,数据完全的本地化,支持完整的SQL,基于成本进行SQL优化。

    最右侧是以Impala为代表的典型的SQL over HDFS。存储引擎HDFS与查询引擎完全透明,数据不是由查询引擎写入的,实际上它们就不叫执行引擎,大多只支持“查询”。因为不能控制存储,所以没有统计信息,大部分只能实现基于规则的SQL优化。

    存在一个中间的状态,请允许我用MPP over HDFS来命名它。以GP HAWG和Vertica刚推出的VIVE为代表。虽然它也利用HDFS,但是写入的数据均是通过它自己的存储引擎写入的,因此是要计算Hash的,有自己的文件格式和压缩格式,不同节点的文件写到不同节点的目录中,类似Hbase那样。当然也有完整的统计信息,因此可以实现基于成本的SQL优化。它通过HDFS的本地化机制部分实现了数据本地化。MPP节点(也就是执行节点)出现故障以后可以快速启动一个新的执行节点,因为执行节点并不带数据,当然这个时候要损失掉数据本地化的收益。这种中间方案的性能和扩展性也处于中间。

    比如最典型的中间方案就是HAWG。它基本上就是把GP DB的数据存储从本地磁盘的文件系统迁移到HDFS上,使用了一个自己扩展的HDFS接口(gphdfs,Vertica的VIVE使用的是webhdfs的接口)。典型的SQL over HDFS方案比如IBM的BigSQL。

    典型的MPP性能肯定比中间方案的MPP over HDFS高。Vertica自己的一个测试,大概是高一倍左右。我问过GP的测试结果与这个类似。

    三、并行数据库未来展望

    在我的实践中,我感受到了云计算给IT带来的颠覆,虽然云计算热炒已经过了,但是它已经润物细无声地改变了业态。我认为数据库也是这样,以后以云的方式提供的数据库会越来越多。无论是企业内部的私有云还是对外的公有云。比如AWS RedShift和Openstack Trove (DBaaS)。这给数据库软件带来的变化是它需要支持越来越大的集群,技术难度加大但经济性更好。这也要求要具备更好的管控能力。数据库软件需要越来越为大规模集群设计。

    因此我认为,在上述趋势的发展之下。并行数据库的软件模块或者叫组件的分工会越来越细化。以前只有主节点和数据节点两类。有的数据库找一些空的数据节点来作为装载节点。那么未来接入节点、协调节点、元数据节点、日志节点、安全节点、SQL解析和优化节点、数据装载和导出节点、数据节点可能会被单独分析出来(数据节点的对等性必须得到保护)。并且这些组件的实例均需要支持通过软件的方式灵活配置数量等,而不是写到代码之中。在架构设计之初就考虑并行、负载分担和可扩展等。组件之间通过Zookeeper之类的方式进行协调,实现高可用,松耦合,屏蔽内部细节。Gbase 8a就采用了Zookeeper协调的设计。

    在节点分工完成后,更加可以通过硬件的方式进行针对性的优化。比如像NameNode那样把元数据全部放入内存提供更好的性能。另外一些工作,甚至可以放到其它更加便宜,更加适合的大数据基础平台,比如MR和Spark之上进行运算。

    存储硬件的发展趋势以及对数据库软件的影响之前已经分析了,计算的硬件后续可能会随着分工的细化而并不采用一种。比如ARM也许适合某些计算要求不高的节点。

    更加重要的是网络,存储的瓶颈一旦通过电子盘和内存的方式解决,网络就变得很为关键。虽然典型的MPP架构对网络通常要求不高,但是一些特殊的场景,例如装载和非分布键查询。因此基于Infiniband的RDMA变得很有必要。

    之前已经反复提到一些已经发生或我认为即将发生的事情,都有一个原则。因为硬件性价比提升很快,不要用提升软件的复杂度的方法去省硬件。KISS法则提供了更好的性能、扩展性和高可用。另外,因为硬件环境真的是很复杂,因此如果不采用私有云或者公有云的话,那么一体机是对小规模购买者的一个好选择。

    这是我对新型并行数据库的一个构想。

    它通过快速的RAM实现计算和存储分离和透明(类似Hadoop)。因此具有高扩展、高可用的特性。保留了精确的数据划分(Hash)以实现高效的关系型操作,特别是多表JOIN比MR高效。这个时候是鱼有了,而且还是好的鱼。

    它的多个数据分区承载于数据节点上(类似region之于regionserver)。数据分区拥有一定的副本。通过一个由SSD实现的网络服务来快速保存快照和日志,以便所有副本失效后重建(数据分区足够小,分钟级载入)。这个时候熊掌有了,虽然不能做到按比例的性能下降,但是至少把带病工作的时间缩小到了分钟级别。

    另外由于只需要CPU和内存,数据节点可以软件的形式运行在VM、LXC上,可以通过Openstack、Docker、YARN或mesos进行分配和管理。这是另外的一个收益,这样并行数据库不需要独立的物理机集群了。完全可以构建在IaaS之上。

    展望企业级大数据平台的发展,虽然我们现在已经很好解决了软件定义的计算,使得计算框架可以构建在计算资源管理之上。但是并行数据库仍然要自己管理存储,因此存储无法打通。按照上述的设想,也许我们可以把存储完全打通,实现完美的软件定义存储,并构建在存储资源管理之上。使得企业级大数据平台架构更加简洁。解决混搭架构麻烦的是软件定义的架构

    小结一下今天的分享的主要内容:

    1、如有您有大量的结构化数据,并行数据库将是您大数据工作箱中不可或缺的部分。并行数据库最好能与其它大数据工具统一进行管理,例如安装、监控、运维、资源池申请与分配等。

    2、无论在公有云还是私有云,并行数据库可能会发展得越来越大,专业性更强,经济上的考虑也将变得不一样。

    3、天下武功,唯快不破。随着趋势的发展,内存可能会成为数据存取的主要发生地,将有效解决当前计算和存储紧密耦合的并行数据库难题。

    4、软件定义的架构是未来趋势。从设计上必须考虑灵活地配置各个组件的位置和数量,任何环节皆可以并行,各个组件间通过zookeeper之类软件实现高可用和松耦合。

    这是我作为一个并行数据库使用者的一些经验和体会,希望能对大家选择和使用并行数据库有所帮助。我作为使用者对于其中很多技术细节专研并不深刻,如有不正确的地方请帮我指正,期望能有更多的机会跟大家进行交流和学习。下面是我的联系方式。谢谢大家的聆听。

    展开全文
  • 选取了几个典型的分布式数据流系统与分布式消息队列系统进行系统分析,并总结了目前消息队列系统对数据流缓存系统的支持程度。最后对数据缓存技术进行了阐述,并分析了未来的数据流缓存系统的需求和研究方向
  • 本视频来源于Shusen Wang讲解的《分布式机器学习》,总共有三讲,内容和连接如下:并行计算机器学习(上)并行计算机器学习(下)联邦学习:技术角度的讲解这节课的内容是联邦学习。联邦学习是一种特殊的分布式...

    原文链接:https://zhuanlan.zhihu.com/p/114028503

    本视频来源于Shusen Wang讲解的《分布式机器学习》,总共有三讲,内容和连接如下:

    这节课的内容是联邦学习。联邦学习是一种特殊的分布式机器学习,是最近两年机器学习领域的一个大热门。联邦学习和传统分布式学习有什么区别呢?什么是Federated Averaging算法?联邦学习有哪些研究方向呢?我将从技术的角度进行解答。 这节课的主要内容:

    • 分布式机器学习
    • 联邦学习和传统分布式学习的区别
    • 联邦学习中的通信问题
    • Federated Averaging算法
    • 联邦学习中的隐私泄露和隐私保护
    • 联邦学习中的安全问题(拜占庭错误、data poisoning、model poisoning)
    • 总结
    <img src="https://pic3.zhimg.com/v2-56eb5d8aff7fa2e6d8b73eadaef14962_b.jpg" data-caption="" data-size="normal" data-rawwidth="1588" data-rawheight="652" class="origin_image zh-lightbox-thumb" width="1588" data-original="https://pic3.zhimg.com/v2-56eb5d8aff7fa2e6d8b73eadaef14962_r.jpg"/>

    联邦学习有很实际的应用,如移动端会产生数据,但是server,比如谷歌想要从用户那里的数据进行学习。那么一种显然的解决方法就是把数据收集起来,然后学习。但是,现实生活中有着一定的限制,可能处于法律要求或者用户拒绝上传属于,没有一个中心节点可以得到所有的数据,呢么我们该如何去学习模型呢?这个就叫联邦学习。

    <img src="https://pic4.zhimg.com/v2-5a2798d168e95340fb817295568aa710_b.jpg" data-caption="" data-size="normal" data-rawwidth="2466" data-rawheight="1378" class="origin_image zh-lightbox-thumb" width="2466" data-original="https://pic4.zhimg.com/v2-5a2798d168e95340fb817295568aa710_r.jpg"/>

    联邦学习和传统的分布式学习有什么区别呢,主要有以下四点:

    • 用户对于自己的设备和有着控制权。
    • Worker节点是不稳定的,比如手机可能突然就没电了,或者进入了电梯突然没信号了。
    • 通信代价往往比计算代价要高。
    • 分布在Worker节点上的数据并不是独立同分布的(not IID)。因此很多已有的减少通信次数的算法就不适用了。
    • 节点负载不平衡,有的设备数据多有的设备数据少。比如有的用户几天拍一张照片有的用户一天拍好多照片,这给建模带来了困难。如果给图片的权重一样,那么模型可能往往取决于拍图片多的用户,拍照少的用户就被忽略了。如果用户的权重相同,这样学出来的模型对拍照多的用户又不太好了。负载不平衡也给计算带来了挑战,数据少的用户可能一下子算了很多epoc了,数据多的用户还早着。这一点上,联邦学习不像传统的分布式学习可以做负载均衡,即将一个节点的数据转移到另一个节点。

    对于联邦学习,当下有这么几个研究热点:

    Research Direction 1: Communication Efficiency

    我们回顾一下并行梯度下降中(parallel gradient descent),第 [公式] 个worker执行了哪些任务

    1. 从server接收模型参数 [公式]
    2. 根据 [公式] 和本地数据计算梯度 [公式]
    3. [公式] 发送给server

    然后server接收了所有用户的 [公式] 之后,这么做:

    1. 接收 [公式]
    2. 计算:[公式]
    3. 做一次梯度下降,更新模型参数:[公式]
    4. 然后将新的参数发送给用户,等待用户数据重复执行下一轮迭代

    那么我们看一下 federated averaging algorithm,其可以用更少的通信次数达到收敛。

    <img src="https://pic3.zhimg.com/v2-64857be48efe48eba20e7c0b4bd4b1dd_b.jpg" data-caption="" data-size="normal" data-rawwidth="996" data-rawheight="778" class="origin_image zh-lightbox-thumb" width="996" data-original="https://pic3.zhimg.com/v2-64857be48efe48eba20e7c0b4bd4b1dd_r.jpg"/>

    一开始还是sever把参数 [公式] 发送给worker节点,但是worker和之前就不一样了:

    1. 接收参数 [公式]
    2. 迭代以下过程:
      1. 利用 [公式] 和本地数据计算梯度 [公式]
      2. 本地化更新:[公式]

    3. [公式] 发送给server

    然后server接收了全部的 [公式] 之后,这么更新

    1. 从用户那里接收 [公式]
    2. 用以下方程更新 [公式],这个新的模型就叫 [公式],下一轮迭代的时候再把这个新的 [公式] 发送给所有节点。
    <img src="https://pic3.zhimg.com/v2-16989b48dd7d39c8a98bdca55e14b1bf_b.jpg" data-caption="" data-size="normal" data-rawwidth="1478" data-rawheight="764" class="origin_image zh-lightbox-thumb" width="1478" data-original="https://pic3.zhimg.com/v2-16989b48dd7d39c8a98bdca55e14b1bf_r.jpg"/>

    我们把Federated Averaging和梯度下降对比一下,如果以communication为横轴,那么有上图,可见用相同次数的通信,Federated Averaging收敛的更快。两次通信之间Federated Averaging让worker节点做大量计算,以牺牲计算量为代价换取更小的通信次数。如果横轴以epochs为横轴,有以下结果:

    <img src="https://pic1.zhimg.com/v2-509eef385500ace0b62a38f26b553971_b.jpg" data-caption="" data-size="normal" data-rawwidth="2082" data-rawheight="1172" class="origin_image zh-lightbox-thumb" width="2082" data-original="https://pic1.zhimg.com/v2-509eef385500ace0b62a38f26b553971_r.jpg"/>

    我们可以看到相同次数的epochs,梯度下降的收敛更快。

    <img src="https://pic3.zhimg.com/v2-2c2894434ca568e3b49124207ba4429d_b.jpg" data-caption="" data-size="normal" data-rawwidth="1572" data-rawheight="866" class="origin_image zh-lightbox-thumb" width="1572" data-original="https://pic3.zhimg.com/v2-2c2894434ca568e3b49124207ba4429d_r.jpg"/>

    Federated Averaging算法首次由[1]提出,但是没有理论证明,论文[2]证明了Federated Averaging算法对于对同分布数据是收敛的,论文[3]首次证明了Federated Averaging算法对非独立同分布的数据也是收敛的,论文[4]和[3]得到了类似的结论,但是结果晚一点出来。

    <img src="https://pic2.zhimg.com/v2-8bfd173a2d45a3868862d0b4f1f66603_b.jpg" data-caption="" data-size="normal" data-rawwidth="1550" data-rawheight="754" class="origin_image zh-lightbox-thumb" width="1550" data-original="https://pic2.zhimg.com/v2-8bfd173a2d45a3868862d0b4f1f66603_r.jpg"/>

    减少通信次数是个大问题,减少通信次数并不是Federated Averagin这篇文章首次提出的,这里就列了一些文章,但是这些文章大都要求数据独立同分布,这就难以用到联邦学习中。[4]不要求数据独立同分布,但是不适用于深度学习,神经网络很难求对偶问题。

    Research Direction 2: Privacy

    <img src="https://pic2.zhimg.com/v2-cd59340ea97e37f768feb3ac414223b3_b.jpg" data-caption="" data-size="normal" data-rawwidth="1652" data-rawheight="920" class="origin_image zh-lightbox-thumb" width="1652" data-original="https://pic2.zhimg.com/v2-cd59340ea97e37f768feb3ac414223b3_r.jpg"/>

    联邦学习中,用户的数据是始终没有离开用户的,那么数据是否安全呢?我们注意到算梯度的过程中实际上就是对数据进行一个变化,将数据映射到梯度。

    <img src="https://picb.zhimg.com/v2-37fee4c20f47175a8cf33d82e77cc74e_b.jpg" data-caption="" data-size="normal" data-rawwidth="1570" data-rawheight="700" class="origin_image zh-lightbox-thumb" width="1570" data-original="https://picb.zhimg.com/v2-37fee4c20f47175a8cf33d82e77cc74e_r.jpg"/>

    虽然数据没有发出去,但是梯度是几乎包含数据所有信息的,所以一定程度上,可以通过梯度反推出数据的。

    <img src="https://pic2.zhimg.com/v2-dbc16c9c1a98520f250154366d5a78c4_b.jpg" data-caption="" data-size="normal" data-rawwidth="1600" data-rawheight="734" class="origin_image zh-lightbox-thumb" width="1600" data-original="https://pic2.zhimg.com/v2-dbc16c9c1a98520f250154366d5a78c4_r.jpg"/>

    论文[1]说如果一个学习的模型是有用的,那么其肯定泄露了训练数据的信息,当然这点事很显然的。[2]提出额Model Inversion方法可以根据模型反推出数据,但是攻击效果不太好,因为Model Inversion只能看到最后的参数,联邦学习中,我们可以看到每一轮的梯度都是知道的,那么可以反推出更多的信息。[1]和[3]就做了这样的事情,虽然不能完全反推出原始数据,但是可以推出很多的特征,比如用户是男是女。

    <img src="https://pic2.zhimg.com/v2-34755e641ed362c3e9d8d6315d85bc71_b.jpg" data-caption="" data-size="normal" data-rawwidth="1646" data-rawheight="600" class="origin_image zh-lightbox-thumb" width="1646" data-original="https://pic2.zhimg.com/v2-34755e641ed362c3e9d8d6315d85bc71_r.jpg"/>

    文章[1]的大致思路如上,将梯度作为输入特征,然后学习一个分类器。其根本原理就是梯度带有用户信息。那么有没有办法抵御这种攻击呢,当前的主流做法就是加噪声,比如 DP。

    <img src="https://picb.zhimg.com/v2-dadd58959bc0518dd16abb3465193bce_b.jpg" data-caption="" data-size="normal" data-rawwidth="1652" data-rawheight="756" class="origin_image zh-lightbox-thumb" width="1652" data-original="https://picb.zhimg.com/v2-dadd58959bc0518dd16abb3465193bce_r.jpg"/>

    通常是往梯度里面加噪声,但是实验效果并不理想,噪声大了的话,收敛速度就很慢,甚至学习过程进行不下去,因为目标函数不下降了。噪声小了的话隐私保护效果就不好,还是可以反推出用户数据。加噪声会导致测试准确率下降几个百分点,这在工业界是很难接受的,往往下降一个百分点会带来几十万的损失。

    Research Direction 3: Adversarial Robustness

    第三个研究热点让联邦学习可以抵御拜占庭错误和恶意攻击。简单说就是worker中出了叛徒,如何学到更好地模型。

    <img src="https://picb.zhimg.com/v2-1641d747eba8d1f6e103f0575452c21c_b.jpg" data-caption="" data-size="normal" data-rawwidth="2360" data-rawheight="1328" class="origin_image zh-lightbox-thumb" width="2360" data-original="https://picb.zhimg.com/v2-1641d747eba8d1f6e103f0575452c21c_r.jpg"/>

    [1] 提出了数据poisoning attack,[2]提出了模型poisoning 攻击。有了攻击自然有防御措施,这里就列了三种防御措施。很多方法都假设数据是独立同分布的,但这点现实生活并不满足。总而言之,攻击比较容易,防御比较困难,还没有真正有效的防御。

    <img src="https://pic2.zhimg.com/v2-fae2124344633f181eab6be6cf70e7dc_b.jpg" data-caption="" data-size="normal" data-rawwidth="1216" data-rawheight="482" class="origin_image zh-lightbox-thumb" width="1216" data-original="https://pic2.zhimg.com/v2-fae2124344633f181eab6be6cf70e7dc_r.jpg"/>

    总结一下,联邦学习是一种比较特殊的分布式学习,目标是让多个用户不共享数据前提下共同训练一个模型,联邦学习有着其特有的挑战,首先数据不是独立同分布,另一个是数据通信代价高。然后还讲了几个研究挑战点。


    欢迎关注公众号《差分隐私》

    weixin.qq.com/r/di4EHC- (二维码自动识别)

    展开全文
  • 前 言显然,未来对计算速度、系统可靠性和成本实效性的...第12章包括分布式设计在操作系统、文件系统、共享存储系统、数据库系统和异型处理中的应用,同时列出将来可能的研究方向。附录包括了DCDL中的常用符号列表。
  • Sparrow:分布式低延迟调度

    千次阅读 2020-06-05 23:24:42
    大型数据分析框架正在朝着缩短任务执行时间和提高并行度的方向发展来提供低延迟,任务调度器面临的主要挑战是在几百毫秒内完成高度并行的作业调度,这需要在合适的机器上每秒调度数百万个任务,同时提供毫秒级的延迟...

    1.摘要

    大型数据分析框架正在朝着缩短任务执行时间和提高并行度的方向发展来提供低延迟,任务调度器面临的主要挑战是在几百毫秒内完成高度并行的作业调度,这需要在合适的机器上每秒调度数百万个任务,同时提供毫秒级的延迟和高可用性。本文证明了去中心化、随机抽样方法可提供最佳性能,同时避免了中心化设计存在吞吐量和高可用的问题。本文在110台计算机集群上部署Sparrow,并证明Sparrow的性能与理想的调度程序的误差在12%以内。

    2.介绍

    当今的数据分析集群运行的时间越来越短,作业的任务越来越多。在对低延迟交互式数据处理的需求的刺激下,研究机构和同行业共同努力产生了一些框架(例如Dremel,Spark,Impala)可以在数千台机器上工作,或将数据存储在内存以秒级分析大量数据,如图1所示。预计这种趋势会继续推动开发针对次秒级响应时间的新一代框架响应时间进入100ms左右,这让新的强大的应用程序成为可能;例如,面向用户的服务在每个查询的基础上将能够运行复杂的并行计算,比如语言翻译和高度个性化的搜索。

    image.png

                                                                      图1:数据分析框架分析大量数据的延迟非常低

    调度由简短的次秒级任务组成的作业极具挑战,这些作业不仅是因为低延迟框架出现的,也有将长时间运行的批处理作业分解为大量短时间任务的原因。当任务以几百毫秒的速度运行时,调度决策必须有很高的吞吐量:一个由10000个16核机器组成的集群并运行100毫秒任务,每秒可能需要超过一百万个调度决策。调度延迟还必须非常低:对于100 ms的任务,超过几十毫秒的调度延迟(包括排队延迟)开销是无法接受的。最后,处理框架逼近交互式时间范围,并应用于面向用户的系统中,高可用性也是必要的,这些设计需求不同于传统的批处理框架。

    修改当前中心化调度程序来支持亚秒级并行任务面临艰巨的工程挑战,支持亚秒级任务需要处理比现有最快的调度程序(比如Mesos, YARN, SLURM)高两个数量级的吞吐量;通过单个节点调度和启动所有任务很难满足此设计要求。另外,要实现高可用性需要在亚秒级的时间内恢复大量状态。

    本文探讨了设计领域中的相反极端:建议从一组自动运行且没有中心化或逻辑中心化状态的机器进行调度。去中心化设计提供了非常优秀的扩展性和可用性,系统可以通过添加更多调度器来支持更多请求,如果调度器异常,则用户可以将请求定向到其他调度器。考虑到同时运行的调度程序可能会做出相互冲突的调度决策,因此去中心化设计的关键挑战是提供与中心化调度器可比的响应时间。

    本文提出了Sparrow,一种无状态的分布式调度器,它将Power of Two Choices负载均衡技术应用并行任务调度的领域。Power of Two Choices是通过探测两个随机服务器并将任务放置在队列较少的服务器上来调度每个任务。本文介绍三个方法,可以让Power of Two Choices在运行并行作业的集群有效果:

    批量抽样:对于并行作业,Power of Two Choices表现较差,因为作业的响应时间取决于最后完成任务的等待时间,而最后完成任务的等待时间在Power of Two Choices下仍然很高。批量抽样将多选方法(A Generalization of Multiple Choice Balls-into-Bins,)应用于并行作业调度领域来解决此问题。批量抽样不是将每个任务单独进行抽样,而是将m个任务放置在d*m个随机选择的worker中负载最少的worker上(d> 1)。本文通过分析证明,与Power of Two Choices不同,批量抽样的性能不会随着作业并行度的提高而降低。

    后期绑定:Power of Two Choices存在两个性能问题:1.服务器队列长度不能很好地表示等待时间;2.由于消息传递延迟,多个并行调度器可能会遇到竞争状况。后期绑定通过将任务延迟分配给节点,直到节点准备好运行任务来避免这些问题,并且与只做批次抽样相比,平均响应时间减少了多达45%。

    策略和约束:Sparrow在worker上使用多个队列来实现全局性策略,并支持分析框架需要的按作业和按任务放置的约束。无论是策略执行和约束处理用一个简单的理论模型都可以解决,但是两者在实际集群中都起着重要作用。

    本文将Sparrow部署在110台机器上的群集中以评估其性能。调度TPC-H查询时,Sparrow的响应时间与理想调度程序的差距在12%以内,调度中值排队延迟小于9ms,并在小于120ms的时间内从故障中恢复。Sparrow可为任务较短的作业提供较短的响应时间,即使任务数量要大3个数量级。尽管采用了去中心化设计,Sparrow仍保持合计(累加)的份额公平,同时隔离不同优先级的用户,这样恶意的低优先级用户最多可将高优先级作业的响应时间增加40%。仿真结果表明,随着群集增加到数以万计的CPU核,Sparrow表现依然良好。本文的结果表明,实现低延迟、并行的workload,使用Sparrow分布式调度可以作为替代中心化调度的一种可行的方案。

    3.设计目标

    本文针对低延迟应用程序的细粒度任务调度,与批处理workload相比,低延迟workload对调度的要求更高,因为批处理workload会用更多的时间获取资源,任务调度相对很少。为了支持由亚秒级任务组成的workload,调度程序必须提供毫秒级的调度延迟,并每秒支持数百万个任务调度决策。此外,由于低延迟框架可用于增强面向用户的服务的能力,低延迟workload的调度程序应该能够容忍故障。

    Sparrow提供细粒度的任务调度,这是对群集资源管理器功能的补充。Sparrow不会为每个任务启动新的进程,相反,Sparrow假定每台worker计算机上已经运行了一个运行时间很长的进程,因此Sparrow在启动任务时仅需要发送简短的任务描述(而不是大的二进制文件,比如执行任务的镜像)。这些执行程序进程可以在集群启动的时候启动,或者Sparrow与其他框架(比如传统的批处理处理框架)一起通过集群资源管理器(例如YARN, Mesos, Omega)分配资源。

    为了提供更高的调度吞吐量和更低的延迟,Sparrow在调度和权衡很多由尖端的中心化调度程序支持的复杂特性上也会做出近似。特别是,Sparrow不允许某些类型的放置约束(例如x用户任务不能和y用户任务运行在同一个机器),不支持bin packing(任务指定机器运行)和gang scheduling(作业的任务要么全调度要么全不调度)。

    Sparrow以易于扩展、最小化延迟并保持系统设计简单的方式支持少量特性,许多应用程序运行来自多个用户的低延迟查询,因此当总需求超过容量时,Sparrow会强制执行严格的优先级或加权份额公平。Sparrow还支持基本的作业放置约束,例如按任务的约束(例如输入数据在哪任务就在哪执行)和按作业的约束(所有任务必须放置在具有GPU的机器上)。这些特性类似于Hadoop MapReduce和Spark的调度器。

    4.基于抽样的并行作业调度

    传统的任务调度器维护着哪些worker上正在运行的任务的完整视图,并根据这个视图将任务放置到可用的worker上。Sparrow采取了截然不同的方法:多个调度器并行运行,并且调度器不维护有关集群负载的任何状态。为了调度作业的任务,调度器依赖从worker获取的瞬时负载信息。Sparrow的方法将现有的负载平衡技术扩展到并行作业调度的领域,并引入了后期绑定以提高性能。

    4.1术语和作业模型

    我们假设一个集群由执行任务的worker和将任务分配给worker的scheduler组成。作业job)包含m个任务,每个任务(task)分配给一个worker。作业可以由任何scheduler处理。worker在固定数量的槽位中运行任务;避免使用更复杂bin packing,因为这会增加设计的复杂性。如果并发的任务数量多于worker的槽位,将对新任务进行排队,直到现有任务释放足够的资源来运行新任务。本文使用等待时间(wait time)来描述从任务提交scheduler到任务开始执行的时间,使用服务时间(service time)来描述任务在worker上运行的时间。作业响应时间(job response time)描述了从作业提交到scheduler到最后一个任务完成执行的时间。本文使用延迟(delay)来描述由于调度和排队而导致的作业中的总延迟。通过计算作业响应时间和所有任务以零等待时间被调度的作业响应时间(相当于作业中任务最长的服务时间)之间的差值来计算延迟。

    在评估不同的调度方法时,假设每个作业都是能够一波任务运行。在实际集群中,当m大于分配给用户的槽位数时,作业可能会多波任务运行。对于多波作业,scheduler可以执行早期任务进而不影响作业响应时间。

    在评估调度技术时,假设采用单波作业模型,因为单波作业最能考验调度分布式调度方法:即使是单个延迟的任务也会影响作业的响应时间。当然,Sparrow也是可以处理多波工作的。

    4.2单任务抽样(per-task sampling)

    Sparrow的设计灵感来自Power of Two Choices的负载均衡技术,该技术使用无状态的随机方法可以缩短预期的任务等待时间。Power of Two Choices提出了对将任务随机分配给worker的简单改进:将每个任务放置在两个随机选择的worker负载最少的一个上。与使用随机放置相比,以这种方式分配任务指数级减少了等待时间。

    首先考虑将Power of Two Choices技术直接应用于并行作业调度,scheduler会为每个任务随机选择两台worker,并向每台worker发送一个探测消息(probe),探测消息是轻量级的RPC调用。每个worker都会用当前排队的任务数响应探测消息,然后scheduler将任务放在队列最短的worker上。scheduler对作业中的每个任务重复此过程,如图2所示。将Power of Two Choices技术的应用称为单任务抽样。

    image.png

                                                     图2:并行放置作业的两个任务,单任务抽样选择长度为1和3的队列

    与随机放置相比,单任务抽样可以提高性能,但与omniscient scheduler相比,其性能仍然差2倍甚至更多(omniscient scheduler基于worker完整的负载信息使用贪婪调度算法,将任务放在空闲的worker(如果有)上,否则使用FIFO排队)。直观地讲,单任务抽样的问题在于作业的响应时间取决于任何一个任务的最长等待时间,使平均作业响应时间大大高于(并且对最后完成任务特别敏感)平均任务响应时间。本文模拟了由10,000个4核计算机、网络往返时间为1ms组成的集群中单任务抽样和随机放置的情况。作业是Poisson process(最广泛的计数过程之一),每个作业包含100个任务。现实中作业的任务运行时间是以100ms为均值指数分布的,但是某些特殊的作业的任务的执行时间是相同的(使用这种分布可以给调度带来了最大的压力,当作业中的任务的持续时间不同时,较短的任务可以具有更长的等待时间而不会影响作业响应时间)。如图3所示,响应时间随着负载的增加而增加,这是因为scheduler成功找到空闲计算机放置任务的成功率较低。与随机放置相比,在80%的负载下,单任务抽样将性能提高了3倍以上,但响应时间仍然是omniscient scheduler所提供的响应时间的2.6倍以上。

    image.png

                                                图3:10000个4核计算机的模拟集群中运行100任务/作业的调度技术比较

    4.3批量抽样(batch sampling)

    批量抽样改进了单任务抽样,通过在特定作业内共享所有探测信息。单任务抽样一对探测请求可能运气不好抽样了两台负载率较高的机器(如图2中Task1那样),而另一对可能很幸运抽样到两个负载率较低的机器(如图2中Task2那样),有一个负载率最低的机器并没有使用。批量抽样汇总了针对作业所有任务探测的负载信息,并将作业的m个任务放置在所探测的所有工作机中负载最少的worker。在图2的示例中,单任务抽样将任务放置在长度为1和3的队列中,批量抽样将Task1和Task2都放置到了Task2抽样的worker上,如图4所示:

    image.png

                                                                       图4:批量抽样选择长度为 1 和 2 的队列

    要使用批量抽样进行调度,scheduler会随机选择d*m个worker(d≥1),scheduler将发送探测消息给每个d*m worker,与单任务抽样一样,每个worker都会答复排队任务的数量。scheduler将作业的m任务放在负载最少的m个worker。除非另有说明,否则本文默认d = 2。

    如图3所示,与单任务抽样相比,批量抽样可提高性能。在80%的负载下,批量抽样的响应时间是单任务抽样的响应时间的73%。尽管如此,批量抽样的响应时间仍比omniscient scheduler的响应时间差1.92倍。

    4.4基于抽样调度的问题

    由于两个问题,基于抽样的技术在高负载下的性能较差:1.scheduler根据worker上的队列长度放置任务,但是队列长度仅提供对等待时间的粗略预测。试想一个scheduler放置一个任务探测两个worker的情况,其中一个排队两个50ms任务,另一个排队一个300ms任务。scheduler会将任务放入只有一个任务排队的worker中即使该队列将导致300ms较长等待时间。尽管worker可以估计任务执行时间而不是队列长度来进行答复,但是准确预测任务执行时间却非常困难。2.几乎所有的任务执行时间估算都需要准确才能使这种技术有效,因为每个作业都包含许多并行任务,所有任务都必须放在等待时间短的机器上以确保良好的性能。

    抽样还受到竞争条件的困扰,在该竞争条件下,多个scheduler同时将任务放置在看起来负载较轻的worker上。试想两个不同的scheduler同时探测同一台空闲工作机w的情况,显而易见,两个scheduler都可能在w上放置任务。但是,放置在worker上的两个任务中只有一个会进入空队列。如果scheduler知道任务到达时w将不会处于空闲状态,则排队的任务可能会被放置到其他的队列中。

    4.5后期绑定

    Sparrow引入了后期绑定来解决上述问题,worker不会立即答复探测消息,而是在worker内部队列的末尾为任务保留位置。当此保留位置到达队列的头部时,worker将向scheduler发送RPC请求一个相应作业的任务。scheduler将作业的任务分配给前m个worker作为回复,回复其余(d − 1)m worker无任何操作,表明所有任务均已启动。通过这种方式,scheduler保证任务将被放置在被探测的worker上,并在最快的时间启动它们。对于任务执行时间呈指数分布、集群负载为80%时,后期绑定提供的响应时间是批量抽样的响应时间的55%,使响应时间与omniscient scheduler相比达到5%(4毫秒)之内(如图3所示)。

    后期绑定的缺点是,worker在向scheduler发送RPC请求新任务时处于空闲状态,当前我们知道的所有群集调度器权衡利弊都会做出这样的选择:scheduler会等待分配任务,直到worker发出信号说它有足够的可用资源来启动任务。与在worker上排队的任务相比,这种折衷会导致2%的效率损失。worker在请求任务时空闲的时间占比是  (d · RTT)/(t + d · RTT) (其中 d 表示每个任务的探测数,RTT 表示平均网络往返时间,t 表示平均任务服务时间)。在云服务器上部署未优化的网络栈,平均网络往返时间是 1 毫秒。我们预计最短的任务将在 100ms 内完成,并且调度程序将使用不超过 2 的探测比,最多导致 2% 的效率损失。对于本文的目标workload,这种取舍是值得的,如图 3 所示的结果(其中包含网络延迟)就说明了这一点。在网络延迟时间与任务运行时间比较相当的环境,后期绑定不会带来价值。

    4.6主动取消

    scheduler启动某个作业的所有任务后,可以通过以下两种方式之一来处理剩余的挂起的探测消息(作业的任务探测消息发给了worker1,worker2......workern,worker1,worker2.....workeri取走了所有任务,那么剩余的worker的探测消息就是挂起的):它可以主动向所有挂起的worker发送取消RPC,也可以等待worker请求任务并通过没有剩余未启动的任务来答复这些请求。我们使用模拟环境对使用主动取消的好处进行建模,发现主动取消在集群95%的负载下将中位响应时间降低了6%。在给定的负载ρ下,worker的忙碌时间超过了ρ的时间:他们花费ρ的时间来执行任务,但是他们花费额外的时间从scheduler中请求任务。通过使用1毫秒网络RTT进行取消,探测比率为2,平均任务时间为100毫秒,可以将worker的忙碌时间减少大约1%;因为当负载接近100%时响应时间接近无穷大,因此worker在忙碌时间上减少1%导致响应时间明显减少。如果worker在已经请求任务之后收到取消,则取消会导致其他RPC:在95%的负载下,取消会导致2%的额外RPC。我们认为,额外的RPC是提高性能的值得权衡的选择,并且Sparrow实现了主动取消。当网络延迟与任务执行时间的比率增加时,主动取消任务的帮助会更大,因此,随着任务执行时间的减少,主动取消将变得更加重要,而随着网络延迟的减少,主动取消的重要性将降低。

    5.调度策略与约束    

    Sparrow的目标是在去中心化的框架内支持少量有用策略,本节介绍支持的两种流行的调度策略:在哪个worker启动各个任务的约束,以及在资源充足时用户间隔离策略控制用户的相对性能。

    5.1放置约束处理

    Sparrow处理两种类型的约束,按作业和按任务的约束。数据并行框架通常需要此类约束,例如,在保存任务输入数据的磁盘或内存所在计算机上运行任务。如第2节所述,Sparrow不支持某些通用资源管理器支持的许多类型的约束(例如,作业间亲和)。

    按作业的约束(例如,所有任务都应在具有GPU的worker上运行)在Sparrow调度器很容易处理。Sparrow从满足约束的worker子集中随机选择d*m候选worker。一旦选择了要探测的d*m worker,调度便会按照前面描述的进行。

    Sparrow还处理按任务约束的作业,例如将任务限制为在输入数据所在的计算机上运行。将任务与输入数据放置在一起通常会减少响应时间,因为不需要通过网络传输数据。对于具有按任务约束的作业,每个任务约束不同造成可抽样的worker不同,因此Sparrow无法使用批量抽样来汇总作业中所有探测信息。相反,Sparrow使用单任务抽样,其中scheduler从要限制其运行的worker集合中选择两台worker来探测每个任务,并进行后期绑定。

    Sparrow对具有按任务约束的作业在每个任务抽样上实现了一个小的优化。与其对每个任务进行单独探测,Sparrow尽可能跨任务共享信息。例如假设一种情况,任务0被约束在机器A,B和C中运行,而任务1被约束在机器C,D和E中运行。假设scheduler检测了任务0的计算机A和B它们负载较重,对于任务1探测机器C和D都是空闲的。在这种情况下,即使C和D两台机器都作为任务1的探测对象,Sparrow也会将任务0放置在机器C上,将任务1放置在机器D上。

    尽管Sparrow不能对具有按任务约束的作业使用批量抽样,但是我们的分布式方法仍然为这些作业提供接近最佳响应时间,因为即使是中心化scheduler,对于放置每个任务的位置也只有很少的选择。具有按任务约束的作业仍可以使用后期绑定,因此可以确保scheduler将每个任务放置在将更早运行任务的两台探测计算机中的任何一台上。像HDFS这样的存储通常会数据会有三副本分别存储在三台不同的计算机上,因此读取输入数据的任务将被限制为在输入数据所在的三台计算机之一上运行。结果,即使是理想的omniscient scheduler,对于放置每个任务的位置也没有什么其他选择。

    5.2资源分配策略

    当对资源的总需求超过容量时,集群调度程序将根据特定策略分配资源。Sparrow支持两种类型的策略:严格优先级和加权份额公平。这些也是其他调度程序(包括Hadoop Map Reduce调度程序)提供的策略。

    许多群集共享策略简化为使用严格的优先级,Sparrow通过在worker上维护多个队列来支持此类策略。FIFO、最早deadline优先、为每个作业分配优先级以及优先运行最高优先级的作业。例如,以将任务deadline较早的作业分配给更高的优先级。集群操作者也可能希望直接分配优先级,例如将生产作业优先或者临时作业优先。为了支持这些策略,Sparrow在每个worker上为每个优先级维护一个队列。当资源变为空闲时,Sparrow会从优先级最高的非空队列中响应探测消息。此机制以简单性换取准确性作为代价:节点无需使用复杂的协议来交换有关正在等待调度的作业的信息,但是如果低优先级作业的探测消息到达没有高优先级作业的节点,则低优先级作业可以在高优先级作业之前运行。我们认为这是一个值得的取舍:此分布式机制为高优先级用户提供了良好的性能。当高优先级任务到达运行低优先级任务的worker时,Sparrow当前不支持抢占,未来会探索任务抢占。

    Sparrow还可以执行加权份额公平,每个worker为每个用户维护一个单独的队列,并对这些队列执行加权公平排队。该机制可提供预期的群集范围内的份额公平:使用相同worker的两个用户将获得与他们的权重成比例的份额,以此扩展,因此使用同一组机器的两个用户也将被分配与他们的权重成比例的份额。我们选择这种简单的机制是因为更精确的机制(例如Pisces)会增加相当大的复杂性,后续的章节会说明Sparrow的简单机制提供了近乎完美的份额公平。

    6.分析

    在研究实验评估之前,通过分析发现,在进行一些简化的假设后(不管任务执行时间的分布)批量抽样可达到接近最佳的性能。第4节证明了Sparrow的表现不错,但仅在一种特定的workload下,本节将这些结果推广到所有workload。本文还证明了通过单任务抽样,性能会随着作业中的任务数量增加呈指数下降,使其不适合并行workload。

    为了分析批量和单任务抽样的性能,本文检验了将所有任务放在空闲计算机上的可能性,或等效地提供零等待时间。与最佳调度程序相比,量化Sparrow的方法多久将作业交给空闲的worker就可以确定Sparrow的性能。

    为了进行此分析,本文做出一些简化的假设。本文假设网络延迟为零,服务器数量无限大,并且每个服务器一次运行一个任务。本文的实验评估显示了在没有这些假设的情况下的结果。

    n

    集群中服务器数量

    ρ

    负载

    m

    每个作业的任务数量

    d

    每个任务探测数量

    t

    平均任务服务时间

    ρn/(mt)

    平均请求到达率

                                                                                            表1:符号说明

    image.png

                                                                表2:三种不同的调度技术,作业等待时间为零的概率

    数学分析证实了第4章节中的结果,表明单抽样对并行作业的表现效果较差。将指定任务放置在空闲计算机上的概率是1减去所有探测消息命中繁忙计算机的概率:1-ρd(其中ρ表示集群负载,d表示探测比率,详情见表1)。作业中所有任务分配给空闲计算机的概率为(1-ρd)m(如表2所示),因为所有m组探测消息必须命中至少一台空闲计算机。这种可能性随着任务中任务的数量增加呈指数下降,这使得单任务抽样不适用于调度并行任务。图5说明了10个任务和100个任务的作业等待时间为零的概率,并且证明在20%的负载下,100个任务的作业经历零等待时间的可能性降至<2%。

     

    image.png

                                   图5:单核环境中使用随机放置、单任务抽样(d=2)和批量抽样(d=2)作业零等待时间的概率

    批量抽样比单任务采样可以在集群负载高得多的情况下将作业的所有任务放在空闲计算机上,可以推出,只要d≥1/(1-ρ),批量抽样就可以将所有m个任务放在空队列中。最重要的是,该表达式不取决于作业中的任务数(m)。图5展示了这种效果:对于10个任务和100个任务的作业,在50%的负载下零等待时间的概率从1降低到0。

    到目前为止的分析考虑了一次只能运行一个任务的机器,但是,当今的集群通常都是多核计算机。多核计算机明显提高了批量抽样的性能,假设一个模型,其中每个服务器可以同时运行c个任务。每次探测等于探测了c个处理单元上的负载,而不只是一个负载,这增加了找到运行每个任务的空闲处理单元的可能性。为了分析多核环境中的性能,本文做出两个简化的假设:首先,本文假设一个核处于空闲状态的概率与同一台机器上其他核是否处于空闲状态无关;其次,本文假设即使多个核处于空闲状态,scheduler也最多在每台计算机上放置1个任务(在空闲计算机上放置多个任务会加剧“淘金热效应”,在此情况下,许多scheduler会同时将任务放置在空闲计算机上)。基于这些假设,可以将表2中的ρ替换为ρc以获得图6所示的结果。与单核结果相比,这些结果得到了显著改善:对于每台机器4个内核,每个作业100个任务的批量抽样,批量抽样在负载高达79%的情况下可获得接近完美的性能(99.9%的作业零等待时间)。该结果表明,在一些简化的假设下,无论任务执行时间的分布如何,批量抽样都表现良好。

    image.png

                                                                  图6:在四核服务器系统中作业零等待时间的概率

    展开全文
  • 2.2 并行/分布式程序设计语言概述 2.3 并行性的表示 2.4 进程通信同步 2.5 远程过程调用 2.6 健壮性 第 3 章 分布式系统设计的形式方法 3.1 模型的介绍 3.1.1 状态机模型 3.1.2 佩特里网 3.2 因果相关...
  • 计算机研究方向前景

    2011-09-15 00:57:35
    本人平时喜欢编程,做应用开发,出于爱好想跨专业读计算机研究生,但是对计算机的方向及前景不是很了解,希望各位大牛,看看那些方向...03、并行与分布式计算及应用;04、操作系统与嵌入式软件;05、中间件技术。
  • 金海,男,博士,华中科技大学计算机科学与技术学院教授、博士生导师,主要研究方向并行与分布式计算、大数据处理、虚拟化技术、物联网技术、信息安全。 ...
  • 本文讲的是高性能计算在... 陈勇介绍说,大电网并行与分布式计算和数据处理基础平台系统是高性能计算在电网技术应用的一个方向。大电网并行与分布式计算和数据处理基础平台系统是电力系统分析与规划,大电网运行与...
  • 李晓明,男,北京大学教授、博士生导师,主要研究方向为搜索引擎、网络数据挖掘和并行与分布式系统。 ...
  • 包括实现和分析协同过滤算法、运行和学习分类算法、分布式Hadoop集群的搭建和基准测试、分布式Hbase集群的搭建和基准测试、实现一个基于、Mapreduce的并行算法、部署Hive并实现一个的数据操作等等,实际提升企业解决...
  • 介绍了上海交通大学并行与分布式系统研究所近几年来在虚拟化安全领域所做的一系列具有代表性的工作,包括利用虚拟化提供可信执行环境、虚拟机监控、域内隔离等一系列安全服务,以及对虚拟化环境的可信计算基和跨域...
  • 计算机研究方向

    千次阅读 2019-05-31 17:19:55
    计算机研究方向 1、计算机应用技术 计算机网络 实时计算机应用 CIMS 计算机图形学 并行计算 网络信息安全 数据库 情感计算 数据挖掘 分布式计算 知识工程 计算机视觉 自动推理 机器学习 草图理解 网络性能分析...
  • 计算机考研方向

    2020-07-29 16:34:39
    研究方向:计算机网络、实时计算机应用、CIMS、计算机图形学、并行计算、网络信息安全、数据库、情感计算、数据挖掘、分布式计算、知识工程、计算机视觉、自动推理、机器学习、草图理解、网络性能分析协议设计、...
  • 这是计算物理最相关的CS课程,计算物理方向很容易吃透作为项目写到简历上 这部分主要包括 多核计算 OpenMP SIMD 集群计算 MPI GPU计算 CUDA 分布式计算 MapReduce Spark 互联网主要重视分布式计算...
  • 计算机前沿研究方向

    千次阅读 2016-12-12 18:46:00
    计算机网络、实时计算机应用、CIMS、计算机图形学、并行计算、网络信息安全、数据库、情感计算、数据挖掘、分布式计算、知识工程、计算机视觉、自动推理、机器学习、草图理解、网络性能分析协议设计、网络管理...
  •  研究方向:计算机网络、实时计算机应用、CIMS、计算机图形学、并行计算、网络信息安全、数据库、情感计算、数据挖掘、分布式计算、知识工程、计算机视觉、自动推理、机器学习、草图理解、网络性能分析协议设计、...
  • 课程将系统讲授大数据的基本概念、大数据处理架构Hadoop、分布式文件系统HDFS、分布式数据库HBase、NoSQL数据库、云数据库、分布式并行编程模型MapReduce、流计算、图计算、数据可视化以及大数据在互联网、生物医学...
  • 一、专业概况 吉林大学是我国最早成立...081201计算机系统结构的主要研究方向: 01 分布式系统 02 高性能计算云计算 03 并行计算系统 04
  • 文章目录Introduction基础概念学习什么是超算什么是并行计算分布式计算与并行计算的区别线程进程 Introduction 刚接触高性能运算,学习方向有点乱,偶然在网上找到一篇博客: ASC18华农队长超算竞赛完整备战指南.,...
  • 另一方面,面对云化时代,无法从单机升级至并行抑或是分布式云计算支持。 而我们碰到的就是这样一个程序,程序以VC6+MFC构建,代码规模在100多万行至200万行之间,单机程序,根据功能不同分为不同功能方向的子软件...
  • 大家一起学Golang ——Go语言简介安装 go语言简介 Go语言是有google公司推出的一门编程语言,是开源,静态编程语言,语法简洁,天生支持并发。 2007年由Robert Griesemer, Rob Pike, Ken Thompson主持开发,又来...
  • 其技术点包括底层的硬件体系结构、相关的基础理论、大规模数据存储系统、分布式架构设计、各种不同应用场景下的差异化系统设计思路、机器学习数据挖掘并行算法以及层出不穷的新架构、新系统等。《大数据日知录:...

空空如也

空空如也

1 2 3 4
收藏数 62
精华内容 24
关键字:

并行与分布式方向