精华内容
下载资源
问答
  • poi推荐,论文Where to Go Next A Spatio-Temporal的英文原文、我自己翻译中文和总结
  • MapReduce论文中文翻译

    千次阅读 2015-03-18 11:34:45
    MapReduce论文中文翻译

    原文地址:
    http://labs.google.com/papers/mapreduce.html

    译者: alex

    摘要

    MapReduce是一个编程模型,也是一个处理和生成超大数据集的算法模型的相关实现。用户首先创建一个Map函数处理一个基于key/value pair的数据集合,输出中间的基于key/value pair的数据集合;然后再创建一个Reduce函数用来合并所有的具有相同中间key值的中间value值。现实世界中有很多满足上述处理模型的例子,本论文将详细描述这个模型。

    MapReduce架构的程序能够在大量的普通配置的计算机上实现并行化处理。这个系统在运行时只关心:如何分割输入数据,在大量计算机组成的集群上的调度,集群中计算机的错误处理,管理集群中计算机之间必要的通信。采用MapReduce架构可以使那些没有并行计算和分布式处理系统开发经验的程序员有效利用分布式系统的丰富资源。

    我们的MapReduce实现运行在规模可以灵活调整的由普通机器组成的集群上:一个典型的MapReduce计算往往由几千台机器组成、处理以TB计算的数据。程序员发现这个系统非常好用:已经实现了数以百计的MapReduce程序,在Google的集群上,每天都有1000多个MapReduce程序在执行。

    介绍

    在过去的5年里,包括本文作者在内的Google的很多程序员,为了处理海量的原始数据,已经实现了数以百计的、专用的计算方法。这些计算方法用来处理大量的原始数据,比如,文档抓取(类似网络爬虫的程序)、Web请求日志等等;也为了计算处理各种类型的衍生数据,比如倒排索引、Web文档的图结构的各种表示形势、每台主机上网络爬虫抓取的页面数量的汇总、每天被请求的最多的查询的集合等等。大多数这样的数据处理运算在概念上很容易理解。然而由于输入的数据量巨大,因此要想在可接受的时间内完成运算,只有将这些计算分布在成百上千的主机上。如何处理并行计算、如何分发数据、如何处理错误?所有这些问题综合在一起,需要大量的代码处理,因此也使得原本简单的运算变得难以处理。

    为了解决上述复杂的问题,我们设计一个新的抽象模型,使用这个抽象模型,我们只要表述我们想要执行的简单运算即可,而不必关心并行计算、容错、数据分布、负载均衡等复杂的细节,这些问题都被封装在了一个库里面。设计这个抽象模型的灵感来自Lisp和许多其他函数式语言的Map和Reduce的原语。我们意识到我们大多数的运算都包含这样的操作:在输入数据的“逻辑”记录上应用Map操作得出一个中间key/value pair集合,然后在所有具有相同key值的value值上应用Reduce操作,从而达到合并中间的数据,得到一个想要的结果的目的。使用MapReduce模型,再结合用户实现的Map和Reduce函数,我们就可以非常容易的实现大规模并行化计算;通过MapReduce模型自带的“再次执行”(re-execution)功能,也提供了初级的容灾实现方案。

    这个工作(实现一个MapReduce框架模型)的主要贡献是通过简单的接口来实现自动的并行化和大规模的分布式计算,通过使用MapReduce模型接口实现在大量普通的PC机上高性能计算。

    第二部分描述基本的编程模型和一些使用案例。第三部分描述了一个经过裁剪的、适合我们的基于集群的计算环境的MapReduce实现。第四部分描述我们认为在MapReduce编程模型中一些实用的技巧。第五部分对于各种不同的任务,测量我们MapReduce实现的性能。第六部分揭示了在Google内部如何使用MapReduce作为基础重写我们的索引系统产品,包括其它一些使用MapReduce的经验。第七部分讨论相关的和未来的工作。

    编程模型

    MapReduce编程模型的原理是:利用一个输入key/value pair集合来产生一个输出的key/value pair集合。MapReduce库的用户用两个函数表达这个计算:Map和Reduce。

    用户自定义的Map函数接受一个输入的key/value pair值,然后产生一个中间key/value pair值的集合。MapReduce库把所有具有相同中间key值I的中间value值集合在一起后传递给reduce函数。

    用户自定义的Reduce函数接受一个中间key的值I和相关的一个value值的集合。Reduce函数合并这些value值,形成一个较小的value值的集合。一般的,每次Reduce函数调用只产生0或1个输出value值。通常我们通过一个迭代器把中间value值提供给Reduce函数,这样我们就可以处理无法全部放入内存中的大量的value值的集合。

    例子

    例如,计算一个大的文档集合中每个单词出现的次数,下面是伪代码段:

    map(String key, String value):
        // key: document name
        // value: document contents
        for each word w in value:
            EmitIntermediate(w, “1″);
    reduce(String key, Iterator values):
        // key: a word
        // values: a list of counts
        int result = 0;
        for each v in values:
            result += ParseInt(v);
        Emit(AsString(result));

    Map函数输出文档中的每个词、以及这个词的出现次数(在这个简单的例子里就是1)。Reduce函数把Map函数产生的每一个特定的词的计数累加起来。

    另外,用户编写代码,使用输入和输出文件的名字、可选的调节参数来完成一个符合MapReduce模型规范的对象,然后调用MapReduce函数,并把这个规范对象传递给它。用户的代码和MapReduce库链接在一起(用C++实现)。附录A包含了这个实例的全部程序代码。

    类型

    尽管在前面例子的伪代码中使用了以字符串表示的输入输出值,但是在概念上,用户定义的Map和Reduce函数都有相关联的类型:

    map(k1,v1) ->list(k2,v2)
    reduce(k2,list(v2)) ->list(v2)

    比如,输入的key和value值与输出的key和value值在类型上推导的域不同。此外,中间key和value值与输出key和value值在类型上推导的域相同。
    (alex注:原文中这个domain的含义不是很清楚,我参考Hadoop、KFS等实现,map和reduce都使用了泛型,因此,我把domain翻译成类型推导的域)。
    我们的C++中使用字符串类型作为用户自定义函数的输入输出,用户在自己的代码中对字符串进行适当的类型转换。

    更多的例子

    这里还有一些有趣的简单例子,可以很容易的使用MapReduce模型来表示:

    • 分布式的Grep:Map函数输出匹配某个模式的一行,Reduce函数是一个恒等函数,即把中间数据复制到输出。
    • 计算URL访问频率:Map函数处理日志中web页面请求的记录,然后输出(URL,1)。Reduce函数把相同URL的value值都累加起来,产生(URL,记录总数)结果。
    • 倒转网络链接图:Map函数在源页面(source)中搜索所有的链接目标(target)并输出为(target,source)。Reduce函数把给定链接目标(target)的链接组合成一个列表,输出(target,list(source))。
    • 每个主机的检索词向量:检索词向量用一个(词,频率)列表来概述出现在文档或文档集中的最重要的一些词。Map函数为每一个输入文档输出(主机名,检索词向量),其中主机名来自文档的URL。Reduce函数接收给定主机的所有文档的检索词向量,并把这些检索词向量加在一起,丢弃掉低频的检索词,输出一个最终的(主机名,检索词向量)。
    • 倒排索引:Map函数分析每个文档输出一个(词,文档号)的列表,Reduce函数的输入是一个给定词的所有(词,文档号),排序所有的文档号,输出(词,list(文档号))。所有的输出集合形成一个简单的倒排索引,它以一种简单的算法跟踪词在文档中的位置。
    • 分布式排序:Map函数从每个记录提取key,输出(key,record)。Reduce函数不改变任何的值。这个运算依赖分区机制(在4.1描述)和排序属性(在4.2描述)。

    实现

    MapReduce模型可以有多种不同的实现方式。如何正确选择取决于具体的环境。例如,一种实现方式适用于小型的共享内存方式的机器,另外一种实现方式则适用于大型NUMA架构的多处理器的主机,而有的实现方式更适合大型的网络连接集群。
    本章节描述一个适用于Google内部广泛使用的运算环境的实现:用以太网交换机连接、由普通PC机组成的大型集群。在我们的环境里包括:

    • x86架构、运行Linux操作系统、双处理器、2-4GB内存的机器。
    • 普通的网络硬件设备,每个机器的带宽为百兆或者千兆,但是远小于网络的平均带宽的一半。 (alex注:这里需要网络专家解释一下了)
    • 集群中包含成百上千的机器,因此,机器故障是常态。
    • 存储为廉价的内置IDE硬盘。一个内部分布式文件系统用来管理存储在这些磁盘上的数据。文件系统通过数据复制来在不可靠的硬件上保证数据的可靠性和有效性。
    • 用户提交工作(job)给调度系统。每个工作(job)都包含一系列的任务(task),调度系统将这些任务调度到集群中多台可用的机器上。

    执行概括

    通过将Map调用的输入数据自动分割为M个数据片段的集合,Map调用被分布到多台机器上执行。输入的数据片段能够在不同的机器上并行处理。使用分区函数将Map调用产生的中间key值分成R个不同分区(例如,hash(key) mod R),Reduce调用也被分布到多台机器上执行。分区数量(R)和分区函数由用户来指定。
    这里写图片描述
    图1展示了我们的MapReduce实现中操作的全部流程。当用户调用MapReduce函数时,将发生下面的一系列动作(下面的序号和图1中的序号一一对应):

    • 用户程序首先调用的MapReduce库将输入文件分成M个数据片度,每个数据片段的大小一般从 16MB到64MB(可以通过可选的参数来控制每个数据片段的大小)。然后用户程序在机群中创建大量的程序副本。 (alex:copies of the program还真难翻译)
    • 这些程序副本中的有一个特殊的程序–master。副本中其它的程序都是worker程序,由master分配任务。有M个Map任务和R个Reduce任务将被分配,master将一个Map任务或Reduce任务分配给一个空闲的worker。
    • 被分配了map任务的worker程序读取相关的输入数据片段,从输入的数据片段中解析出key/value pair,然后把key/value pair传递给用户自定义的Map函数,由Map函数生成并输出的中间key/value pair,并缓存在内存中。
    • 缓存中的key/value pair通过分区函数分成R个区域,之后周期性的写入到本地磁盘上。缓存的key/value pair在本地磁盘上的存储位置将被回传给master,由master负责把这些存储位置再传送给Reduce worker。
    • 当Reduce worker程序接收到master程序发来的数据存储位置信息后,使用RPC从Map worker所在主机的磁盘上读取这些缓存数据。当Reduce worker读取了所有的中间数据后,通过对key进行排序后使得具有相同key值的数据聚合在一起。由于许多不同的key值会映射到相同的Reduce任务上,因此必须进行排序。如果中间数据太大无法在内存中完成排序,那么就要在外部进行排序。
    • Reduce worker程序遍历排序后的中间数据,对于每一个唯一的中间key值,Reduce worker程序将这个key值和它相关的中间value值的集合传递给用户自定义的Reduce函数。Reduce函数的输出被追加到所属分区的输出文件。
    • 当所有的Map和Reduce任务都完成之后,master唤醒用户程序。在这个时候,在用户程序里的对MapReduce调用才返回。

    在成功完成任务之后,MapReduce的输出存放在R个输出文件中(对应每个Reduce任务产生一个输出文件,文件名由用户指定)。一般情况下,用户不需要将这R个输出文件合并成一个文件–他们经常把这些文件作为另外一个MapReduce的输入,或者在另外一个可以处理多个分割文件的分布式应用中使用。

    Master数据结构

    Master持有一些数据结构,它存储每一个Map和Reduce任务的状态(空闲、工作中或完成),以及Worker机器(非空闲任务的机器)的标识。

    Master就像一个数据管道,中间文件存储区域的位置信息通过这个管道从Map传递到Reduce。因此,对于每个已经完成的Map任务,master存储了Map任务产生的R个中间文件存储区域的大小和位置。当Map任务完成时,Master接收到位置和大小的更新信息,这些信息被逐步递增的推送给那些正在工作的Reduce任务。

    容错

    因为MapReduce库的设计初衷是使用由成百上千的机器组成的集群来处理超大规模的数据,所以,这个库必须要能很好的处理机器故障。

    worker故障

    master周期性的ping每个worker。如果在一个约定的时间范围内没有收到worker返回的信息,master将把这个worker标记为失效。所有由这个失效的worker完成的Map任务被重设为初始的空闲状态,之后这些任务就可以被安排给其他的worker。同样的,worker失效时正在运行的Map或Reduce任务也将被重新置为空闲状态,等待重新调度。

    当worker故障时,由于已经完成的Map任务的输出存储在这台机器上,Map任务的输出已不可访问了,因此必须重新执行。而已经完成的Reduce任务的输出存储在全局文件系统上,因此不需要再次执行。

    当一个Map任务首先被worker A执行,之后由于worker A失效了又被调度到worker B执行,这个“重新执行”的动作会被通知给所有执行Reduce任务的worker。任何还没有从worker A读取数据的Reduce任务将从worker B读取数据。

    MapReduce可以处理大规模worker失效的情况。比如,在一个MapReduce操作执行期间,在正在运行的集群上进行网络维护引起80台机器在几分钟内不可访问了,MapReduce master只需要简单的再次执行那些不可访问的worker完成的工作,之后继续执行未完成的任务,直到最终完成这个MapReduce操作。

    master失败

    一个简单的解决办法是让master周期性的将上面描述的数据结构(alex注:指3.2节)的写入磁盘,即检查点(checkpoint)。如果这个master任务失效了,可以从最后一个检查点(checkpoint)开始启动另一个master进程。然而,由于只有一个master进程,master失效后再恢复是比较麻烦的,因此我们现在的实现是如果master失效,就中止MapReduce运算。客户可以检查到这个状态,并且可以根据需要重新执行MapReduce操作。

    在失效方面的处理机制

    (alex注:原文为”semantics in the presence of failures”)
    当用户提供的Map和Reduce操作是输入确定性函数(即相同的输入产生相同的输出)时,我们的分布式实现在任何情况下的输出都和所有程序没有出现任何错误、顺序的执行产生的输出是一样的。

    我们依赖对Map和Reduce任务的输出是原子提交的来完成这个特性。每个工作中的任务把它的输出写到私有的临时文件中。每个Reduce任务生成一个这样的文件,而每个Map任务则生成R个这样的文件(一个Reduce任务对应一个文件)。当一个Map任务完成的时,worker发送一个包含R个临时文件名的完成消息给master。如果master从一个已经完成的Map任务再次接收到到一个完成消息,master将忽略这个消息;否则,master将这R个文件的名字记录在数据结构里。

    当Reduce任务完成时,Reduce worker进程以原子的方式把临时文件重命名为最终的输出文件。如果同一个Reduce任务在多台机器上执行,针对同一个最终的输出文件将有多个重命名操作执行。我们依赖底层文件系统提供的重命名操作的原子性来保证最终的文件系统状态仅仅包含一个Reduce任务产生的数据。

    使用MapReduce模型的程序员可以很容易的理解他们程序的行为,因为我们绝大多数的Map和Reduce操作是确定性的,而且存在这样的一个事实:我们的失效处理机制等价于一个顺序的执行的操作。当Map或/和Reduce操作是不确定性的时候,我们提供虽然较弱但是依然合理的处理机制。当使用非确定操作的时候,一个Reduce任务R1的输出等价于一个非确定性程序顺序执行产生时的输出。但是,另一个Reduce任务R2的输出也许符合一个不同的非确定顺序程序执行产生的R2的输出。

    考虑Map任务M和Reduce任务R1、R2的情况。我们设定e(Ri)是Ri已经提交的执行过程(有且仅有一个这样的执行过程)。当e(R1)读取了由M一次执行产生的输出,而e(R2)读取了由M的另一次执行产生的输出,导致了较弱的失效处理。

    存储位置

    在我们的计算运行环境中,网络带宽是一个相当匮乏的资源。我们通过尽量把输入数据(由GFS管理)存储在集群中机器的本地磁盘上来节省网络带宽。GFS把每个文件按64MB一个Block分隔,每个Block保存在多台机器上,环境中就存放了多份拷贝(一般是3个拷贝)。MapReduce的master在调度Map任务时会考虑输入文件的位置信息,尽量将一个Map任务调度在包含相关输入数据拷贝的机器上执行;如果上述努力失败了,master将尝试在保存有输入数据拷贝的机器附近的机器上执行Map任务(例如,分配到一个和包含输入数据的机器在一个switch里的worker机器上执行)。当在一个足够大的cluster集群上运行大型MapReduce操作的时候,大部分的输入数据都能从本地机器读取,因此消耗非常少的网络带宽。

    任务粒度

    如前所述,我们把Map拆分成了M个片段、把Reduce拆分成R个片段执行。理想情况下,M和R应当比集群中worker的机器数量要多得多。在每台worker机器都执行大量的不同任务能够提高集群的动态的负载均衡能力,并且能够加快故障恢复的速度:失效机器上执行的大量Map任务都可以分布到所有其他的worker机器上去执行。

    但是实际上,在我们的具体实现中对M和R的取值都有一定的客观限制,因为master必须执行O(M+R)次调度,并且在内存中保存O(M*R)个状态(对影响内存使用的因素还是比较小的:O(M*R)块状态,大概每对Map任务/Reduce任务1个字节就可以了)。

    更进一步,R值通常是由用户指定的,因为每个Reduce任务最终都会生成一个独立的输出文件。实际使用时我们也倾向于选择合适的M值,以使得每一个独立任务都是处理大约16M到64M的输入数据(这样,上面描写的输入数据本地存储优化策略才最有效),另外,我们把R值设置为我们想使用的worker机器数量的小的倍数。我们通常会用这样的比例来执行MapReduce:M=200000,R=5000,使用2000台worker机器。

    备用任务

    影响一个MapReduce的总执行时间最通常的因素是“落伍者”:在运算过程中,如果有一台机器花了很长的时间才完成最后几个Map或Reduce任务,导致MapReduce操作总的执行时间超过预期。出现“落伍者”的原因非常多。比如:如果一个机器的硬盘出了问题,在读取的时候要经常的进行读取纠错操作,导致读取数据的速度从30M/s降低到1M/s。如果cluster的调度系统在这台机器上又调度了其他的任务,由于CPU、内存、本地硬盘和网络带宽等竞争因素的存在,导致执行MapReduce代码的执行效率更加缓慢。我们最近遇到的一个问题是由于机器的初始化代码有bug,导致关闭了的处理器的缓存:在这些机器上执行任务的性能和正常情况相差上百倍。

    我们有一个通用的机制来减少“落伍者”出现的情况。当一个MapReduce操作接近完成的时候,master调度备用(backup)任务进程来执行剩下的、处于处理中状态(in-progress)的任务。无论是最初的执行进程、还是备用(backup)任务进程完成了任务,我们都把这个任务标记成为已经完成。我们调优了这个机制,通常只会占用比正常操作多几个百分点的计算资源。我们发现采用这样的机制对于减少超大MapReduce操作的总处理时间效果显著。例如,在5.3节描述的排序任务,在关闭掉备用任务的情况下要多花44%的时间完成排序任务。

    技巧

    虽然简单的Map和Reduce函数提供的基本功能已经能够满足大部分的计算需要,我们还是发掘出了一些有价值的扩展功能。本节将描述这些扩展功能。

    分区函数

    MapReduce的使用者通常会指定Reduce任务和Reduce任务输出文件的数量(R)。我们在中间key上使用分区函数来对数据进行分区,之后再输入到后续任务执行进程。一个缺省的分区函数是使用hash方法(比如,hash(key) mod R)进行分区。hash方法能产生非常平衡的分区。然而,有的时候,其它的一些分区函数对key值进行的分区将非常有用。比如,输出的key值是URLs,我们希望每个主机的所有条目保持在同一个输出文件中。为了支持类似的情况,MapReduce库的用户需要提供专门的分区函数。例如,使用“hash(Hostname(urlkey)) mod R”作为分区函数就可以把所有来自同一个主机的URLs保存在同一个输出文件中。

    顺序保证

    我们确保在给定的分区中,中间key/value pair数据的处理顺序是按照key值增量顺序处理的。这样的顺序保证对每个分成生成一个有序的输出文件,这对于需要对输出文件按key值随机存取的应用非常有意义,对在排序输出的数据集也很有帮助。

    Combiner函数

    在某些情况下,Map函数产生的中间key值的重复数据会占很大的比重,并且,用户自定义的Reduce函数满足结合律和交换律。在2.1节的词数统计程序是个很好的例子。由于词频率倾向于一个zipf分布(齐夫分布),每个Map任务将产生成千上万个这样的记录the,1.所有的这些记录将通过网络被发送到一个单独的Reduce任务,然后由这个Reduce任务把所有这些记录累加起来产生一个数字。我们允许用户指定一个可选的combiner函数,combiner函数首先在本地将这些记录进行一次合并,然后将合并的结果再通过网络发送出去。

    Combiner函数在每台执行Map任务的机器上都会被执行一次。一般情况下,Combiner和Reduce函数是一样的。Combiner函数和Reduce函数之间唯一的区别是MapReduce库怎样控制函数的输出。Reduce函数的输出被保存在最终的输出文件里,而Combiner函数的输出被写到中间文件里,然后被发送给Reduce任务。

    部分的合并中间结果可以显著的提高一些MapReduce操作的速度。附录A包含一个使用combiner函数的例子。

    输入和输出的类型

    MapReduce库支持几种不同的格式的输入数据。比如,文本模式的输入数据的每一行被视为是一个key/value pair。key是文件的偏移量,value是那一行的内容。另外一种常见的格式是以key进行排序来存储的key/value pair的序列。每种输入类型的实现都必须能够把输入数据分割成数据片段,该数据片段能够由单独的Map任务来进行后续处理(例如,文本模式的范围分割必须确保仅仅在每行的边界进行范围分割)。虽然大多数MapReduce的使用者仅仅使用很少的预定义输入类型就满足要求了,但是使用者依然可以通过提供一个简单的Reader接口实现就能够支持一个新的输入类型。

    Reader并非一定要从文件中读取数据,比如,我们可以很容易的实现一个从数据库里读记录的Reader,或者从内存中的数据结构读取数据的Reader。
    类似的,我们提供了一些预定义的输出数据的类型,通过这些预定义类型能够产生不同格式的数据。用户采用类似添加新的输入数据类型的方式增加新的输出类型。

    副作用

    在某些情况下,MapReduce的使用者发现,如果在Map和/或Reduce操作过程中增加辅助的输出文件会比较省事。我们依靠程序writer把这种“副作用”变成原子的和幂等的(alex注:幂等的指一个总是产生相同结果的数学运算)。通常应用程序首先把输出结果写到一个临时文件中,在输出全部数据之后,在使用系统级的原子操作rename重新命名这个临时文件。

    如果一个任务产生了多个输出文件,我们没有提供类似两阶段提交的原子操作支持这种情况。因此,对于会产生多个输出文件、并且对于跨文件有一致性要求的任务,都必须是确定性的任务。但是在实际应用过程中,这个限制还没有给我们带来过麻烦。

    跳过损坏的记录

    有时候,用户程序中的bug导致Map或者Reduce函数在处理某些记录的时候crash掉,MapReduce操作无法顺利完成。惯常的做法是修复bug后再次执行MapReduce操作,但是,有时候找出这些bug并修复它们不是一件容易的事情;这些bug也许是在第三方库里边,而我们手头没有这些库的源代码。而且在很多时候,忽略一些有问题的记录也是可以接受的,比如在一个巨大的数据集上进行统计分析的时候。我们提供了一种执行模式,在这种模式下,为了保证保证整个处理能继续进行,MapReduce会检测哪些记录导致确定性的crash,并且跳过这些记录不处理。

    每个worker进程都设置了信号处理函数捕获内存段异常(segmentation violation)和总线错误(bus error)。在执行Map或者Reduce操作之前,MapReduce库通过全局变量保存记录序号。如果用户程序触发了一个系统信号,消息处理函数将用“最后一口气”通过UDP包向master发送处理的最后一条记录的序号。当master看到在处理某条特定记录不止失败一次时,master就标志着条记录需要被跳过,并且在下次重新执行相关的Map或者Reduce任务的时候跳过这条记录。

    本地执行

    调试Map和Reduce函数的bug是非常困难的,因为实际执行操作时不但是分布在系统中执行的,而且通常是在好几千台计算机上执行,具体的执行位置是由master进行动态调度的,这又大大增加了调试的难度。为了简化调试、profile和小规模测试,我们开发了一套MapReduce库的本地实现版本,通过使用本地版本的MapReduce库,MapReduce操作在本地计算机上顺序的执行。用户可以控制MapReduce操作的执行,可以把操作限制到特定的Map任务上。用户通过设定特别的标志来在本地执行他们的程序,之后就可以很容易的使用本地调试和测试工具(比如gdb)。

    状态信息

    master使用嵌入式的HTTP服务器(如Jetty)显示一组状态信息页面,用户可以监控各种执行状态。状态信息页面显示了包括计算执行的进度,比如已经完成了多少任务、有多少任务正在处理、输入的字节数、中间数据的字节数、输出的字节数、处理百分比等等。页面还包含了指向每个任务的stderr和stdout文件的链接。用户根据这些数据预测计算需要执行大约多长时间、是否需要增加额外的计算资源。这些页面也可以用来分析什么时候计算执行的比预期的要慢。

    另外,处于最顶层的状态页面显示了哪些worker失效了,以及他们失效的时候正在运行的Map和Reduce任务。这些信息对于调试用户代码中的bug很有帮助。

    计数器

    MapReduce库使用计数器统计不同事件发生次数。比如,用户可能想统计已经处理了多少个单词、已经索引的多少篇German文档等等。

    为了使用这个特性,用户在程序中创建一个命名的计数器对象,在Map和Reduce函数中相应的增加计数器的值。例如:

    Counter* uppercase;
    uppercase = GetCounter(“uppercase”);
    map(String name, String contents):
     for each word w in contents:
      if (IsCapitalized(w)):
       uppercase->Increment();
      EmitIntermediate(w, “1″);

    这些计数器的值周期性的从各个单独的worker机器上传递给master(附加在ping的应答包中传递)。master把执行成功的Map和Reduce任务的计数器值进行累计,当MapReduce操作完成之后,返回给用户代码。

    计数器当前的值也会显示在master的状态页面上,这样用户就可以看到当前计算的进度。当累加计数器的值的时候,master要检查重复运行的Map或者Reduce任务,避免重复累加(之前提到的备用任务和失效后重新执行任务这两种情况会导致相同的任务被多次执行)。

    有些计数器的值是由MapReduce库自动维持的,比如已经处理的输入的key/value pair的数量、输出的key/value pair的数量等等。

    计数器机制对于MapReduce操作的完整性检查非常有用。比如,在某些MapReduce操作中,用户需要确保输出的key value pair精确的等于输入的key value pair,或者处理的German文档数量在处理的整个文档数量中属于合理范围。

    性能

    本节我们用在一个大型集群上运行的两个计算来衡量MapReduce的性能。一个计算在大约1TB的数据中进行特定的模式匹配,另一个计算对大约1TB的数据进行排序。

    这两个程序在大量的使用MapReduce的实际应用中是非常典型的 — 一类是对数据格式进行转换,从一种表现形式转换为另外一种表现形式;另一类是从海量数据中抽取少部分的用户感兴趣的数据。

    集群配置

    所有这些程序都运行在一个大约由1800台机器构成的集群上。每台机器配置2个2G主频、支持超线程的Intel Xeon处理器,4GB的物理内存,两个160GB的IDE硬盘和一个千兆以太网卡。这些机器部署在一个两层的树形交换网络中,在root节点大概有100-200GBPS的传输带宽。所有这些机器都采用相同的部署(对等部署),因此任意两点之间的网络来回时间小于1毫秒。

    在4GB内存里,大概有1-1.5G用于运行在集群上的其他任务。测试程序在周末下午开始执行,这时主机的CPU、磁盘和网络基本上处于空闲状态。

    GREP

    这个分布式的grep程序需要扫描大概10的10次方个由100个字节组成的记录,查找出现概率较小的3个字符的模式(这个模式在92337个记录中出现)。输入数据被拆分成大约64M的Block(M=15000),整个输出数据存放在一个文件中(R=1)。
    这里写图片描述
    图2显示了这个运算随时间的处理过程。其中Y轴表示输入数据的处理速度。处理速度随着参与MapReduce计算的机器数量的增加而增加,当1764台worker参与计算的时,处理速度达到了30GB/s。当Map任务结束的时候,即在计算开始后80秒,输入的处理速度降到0。整个计算过程从开始到结束一共花了大概150秒。这包括了大约一分钟的初始启动阶段。初始启动阶段消耗的时间包括了是把这个程序传送到各个worker机器上的时间、等待GFS文件系统打开1000个输入文件集合的时间、获取相关的文件本地位置优化信息的时间。

    排序

    排序程序处理10的10次方个100个字节组成的记录(大概1TB的数据)。这个程序模仿TeraSort benchmark[10]。

    排序程序由不到50行代码组成。只有三行的Map函数从文本行中解析出10个字节的key值作为排序的key,并且把这个key和原始文本行作为中间的key/value pair值输出。我们使用了一个内置的恒等函数作为Reduce操作函数。这个函数把中间的key/value pair值不作任何改变输出。最终排序结果输出到两路复制的GFS文件系统(也就是说,程序输出2TB的数据)。

    如前所述,输入数据被分成64MB的Block(M=15000)。我们把排序后的输出结果分区后存储到4000个文件(R=4000)。分区函数使用key的原始字节来把数据分区到R个片段中。

    在这个benchmark测试中,我们使用的分区函数知道key的分区情况。通常对于排序程序来说,我们会增加一个预处理的MapReduce操作用于采样key值的分布情况,通过采样的数据来计算对最终排序处理的分区点。
    这里写图片描述
    图三(a)显示了这个排序程序的正常执行过程。左上的图显示了输入数据读取的速度。数据读取速度峰值会达到13GB/s,并且所有Map任务完成之后,即大约200秒之后迅速滑落到0。值得注意的是,排序程序输入数据读取速度小于分布式grep程序。这是因为排序程序的Map任务花了大约一半的处理时间和I/O带宽把中间输出结果写到本地硬盘。相应的分布式grep程序的中间结果输出几乎可以忽略不计。

    左边中间的图显示了中间数据从Map任务发送到Reduce任务的网络速度。这个过程从第一个Map任务完成之后就开始缓慢启动了。图示的第一个高峰是启动了第一批大概1700个Reduce任务(整个MapReduce分布到大概1700台机器上,每台机器1次最多执行1个Reduce任务)。排序程序运行大约300秒后,第一批启动的Reduce任务有些完成了,我们开始执行剩下的Reduce任务。所有的处理在大约600秒后结束。

    左下图表示Reduce任务把排序后的数据写到最终的输出文件的速度。在第一个排序阶段结束和数据开始写入磁盘之间有一个小的延时,这是因为worker机器正在忙于排序中间数据。磁盘写入速度在2-4GB/s持续一段时间。输出数据写入磁盘大约持续850秒。计入初始启动部分的时间,整个运算消耗了891秒。这个速度和TeraSort benchmark[18]的最高纪录1057秒相差不多。

    还有一些值得注意的现象:输入数据的读取速度比排序速度和输出数据写入磁盘速度要高不少,这是因为我们的输入数据本地化优化策略起了作用 — 绝大部分数据都是从本地硬盘读取的,从而节省了网络带宽。排序速度比输出数据写入到磁盘的速度快,这是因为输出数据写了两份(我们使用了2路的GFS文件系统,写入复制节点的原因是为了保证数据可靠性和可用性)。我们把输出数据写入到两个复制节点的原因是因为这是底层文件系统的保证数据可靠性和可用性的实现机制。如果底层文件系统使用类似容错编码[14](erasure coding)的方式而不是复制的方式保证数据的可靠性和可用性,那么在输出数据写入磁盘的时候,就可以降低网络带宽的使用。

    高效的backup任务

    图三(b)显示了关闭了备用任务后排序程序执行情况。执行的过程和图3(a)很相似,除了输出数据写磁盘的动作在时间上拖了一个很长的尾巴,而且在这段时间里,几乎没有什么写入动作。在960秒后,只有5个Reduce任务没有完成。这些拖后腿的任务又执行了300秒才完成。整个计算消耗了1283秒,多了44%的执行时间。

    失效的机器

    在图三(c)中演示的排序程序执行的过程中,我们在程序开始后几分钟有意的kill了1746个worker中的200个。集群底层的调度立刻在这些机器上重新开始新的worker处理进程(因为只是worker机器上的处理进程被kill了,机器本身还在工作)。

    图三(c)显示出了一个“负”的输入数据读取速度,这是因为一些已经完成的Map任务丢失了(由于相应的执行Map任务的worker进程被kill了),需要重新执行这些任务。相关Map任务很快就被重新执行了。整个运算在933秒内完成,包括了初始启动时间(只比正常执行多消耗了5%的时间)。

    经验

    我们在2003年1月完成了第一个版本的MapReduce库,在2003年8月的版本有了显著的增强,这包括了输入数据本地优化、worker机器之间的动态负载均衡等等。从那以后,我们惊喜的发现,MapReduce库能广泛应用于我们日常工作中遇到的各类问题。它现在在Google内部各个领域得到广泛应用,包括:

    • 大规模机器学习问题
    • Google News和Froogle产品的集群问题
    • 从公众查询产品(比如Google的Zeitgeist)的报告中抽取数据。
    • 从大量的新应用和新产品的网页中提取有用信息(比如,从大量的位置搜索网页中抽取地理位置信息)。
    • 大规模的图形计算。
      这里写图片描述
      图四显示了在我们的源代码管理系统中,随着时间推移,独立的MapReduce程序数量的显著增加。从2003年早些时候的0个增长到2004年9月份的差不多900个不同的程序。MapReduce的成功取决于采用MapReduce库能够在不到半个小时时间内写出一个简单的程序,这个简单的程序能够在上千台机器的组成的集群上做大规模并发处理,这极大的加快了开发和原形设计的周期。另外,采用MapReduce库,可以让完全没有分布式和/或并行系统开发经验的程序员很容易的利用大量的资源,开发出分布式和/或并行处理的应用。

    在每个任务结束的时候,MapReduce库统计计算资源的使用状况。在表1,我们列出了2004年8月份MapReduce运行的任务所占用的相关资源。

    大规模索引

    到目前为止,MapReduce最成功的应用就是重写了Google网络搜索服务所使用到的index系统。索引系统的输入数据是网络爬虫抓取回来的海量的文档,这些文档数据都保存在GFS文件系统里。这些文档原始内容(alex注:raw contents,我认为就是网页中的剔除html标记后的内容、pdf和word等有格式文档中提取的文本内容等)的大小超过了20TB。索引程序是通过一系列的MapReduce操作(大约5到10次)来建立索引。使用MapReduce(替换上一个特别设计的、分布式处理的索引程序)带来这些好处:

    • 实现索引部分的代码简单、小巧、容易理解,因为对于容错、分布式以及并行计算的处理都是MapReduce库提供的。比如,使用MapReduce库,计算的代码行数从原来的3800行C++代码减少到大概700行代码。
    • MapReduce库的性能已经足够好了,因此我们可以把在概念上不相关的计算步骤分开处理,而不是混在一起以期减少数据传递的额外消耗。概念上不相关的计算步骤的隔离也使得我们可以很容易改变索引处理方式。比如,对之前的索引系统的一个小更改可能要耗费好几个月的时间,但是在使用MapReduce的新系统上,这样的更改只需要花几天时间就可以了。
    • 索引系统的操作管理更容易了。因为由机器失效、机器处理速度缓慢、以及网络的瞬间阻塞等引起的绝大部分问题都已经由MapReduce库解决了,不再需要操作人员的介入了。另外,我们可以通过在索引系统集群中增加机器的简单方法提高整体处理性能。

    相关工作

    很多系统都提供了严格的编程模式,并且通过对编程的严格限制来实现并行计算。例如,一个结合函数可以通过把N个元素的数组的前缀在N个处理器上使用并行前缀算法,在log N的时间内计算完[6,9,13](alex注:完全没有明白作者在说啥,具体参考相关6、9、13文档)。MapReduce可以看作是我们结合在真实环境下处理海量数据的经验,对这些经典模型进行简化和萃取的成果。更加值得骄傲的是,我们还实现了基于上千台处理器的集群的容错处理。相比而言,大部分并发处理系统都只在小规模的集群上实现,并且把容错处理交给了程序员。

    Bulk Synchronous Programming[17]和一些MPI原语[11]提供了更高级别的并行处理抽象,可以更容易写出并行处理的程序。MapReduce和这些系统的关键不同之处在于,MapReduce利用限制性编程模式实现了用户程序的自动并发处理,并且提供了透明的容错处理。

    我们数据本地优化策略的灵感来源于active disks[12,15]等技术,在active disks中,计算任务是尽量推送到数据存储的节点处理(alex注:即靠近数据源处理),这样就减少了网络和IO子系统的吞吐量。我们在挂载几个硬盘的普通机器上执行我们的运算,而不是在磁盘处理器上执行我们的工作,但是达到的目的一样的。

    我们的备用任务机制和Charlotte System[3]提出的eager调度机制比较类似。Eager调度机制的一个缺点是如果一个任务反复失效,那么整个计算就不能完成。我们通过忽略引起故障的记录的方式在某种程度上解决了这个问题。

    MapReduce的实现依赖于一个内部的集群管理系统,这个集群管理系统负责在一个超大的、共享机器的集群上分布和运行用户任务。虽然这个不是本论文的重点,但是有必要提一下,这个集群管理系统在理念上和其它系统,如Condor[16]是一样。

    MapReduce库的排序机制和NOW-Sort[1]的操作上很类似。读取输入源的机器(map workers)把待排序的数据进行分区后,发送到R个Reduce worker中的一个进行处理。每个Reduce worker在本地对数据进行排序(尽可能在内存中排序)。当然,NOW-Sort没有给用户自定义的Map和Reduce函数的机会,因此不具备MapReduce库广泛的实用性。

    River[2]提供了一个编程模型:处理进程通过分布式队列传送数据的方式进行互相通讯。和MapReduce类似,River系统尝试在不对等的硬件环境下,或者在系统颠簸的情况下也能提供近似平均的性能。River是通过精心调度硬盘和网络的通讯来平衡任务的完成时间。MapReduce库采用了其它的方法。通过对编程模型进行限制,MapReduce框架把问题分解成为大量的“小”任务。这些任务在可用的worker集群上动态的调度,这样快速的worker就可以执行更多的任务。通过对编程模型进行限制,我们可用在工作接近完成的时候调度备用任务,缩短在硬件配置不均衡的情况下缩小整个操作完成的时间(比如有的机器性能差、或者机器被某些操作阻塞了)。

    BAD-FS[5]采用了和MapReduce完全不同的编程模式,它是面向广域网(alex注:wide-area network)的。不过,这两个系统有两个基础功能很类似。(1)两个系统采用重新执行的方式来防止由于失效导致的数据丢失。(2)两个都使用数据本地化调度策略,减少网络通讯的数据量。

    TACC[7]是一个用于简化构造高可用性网络服务的系统。和MapReduce一样,它也依靠重新执行机制来实现的容错处理。

    结束语

    MapReduce编程模型在Google内部成功应用于多个领域。我们把这种成功归结为几个方面:首先,由于MapReduce封装了并行处理、容错处理、数据本地化优化、负载均衡等等技术难点的细节,这使得MapReduce库易于使用。即便对于完全没有并行或者分布式系统开发经验的程序员而言;其次,大量不同类型的问题都可以通过MapReduce简单的解决。比如,MapReduce用于生成Google的网络搜索服务所需要的数据、用来排序、用来数据挖掘、用于机器学习,以及很多其它的系统;第三,我们实现了一个在数千台计算机组成的大型集群上灵活部署运行的MapReduce。这个实现使得有效利用这些丰富的计算资源变得非常简单,因此也适合用来解决Google遇到的其他很多需要大量计算的问题。

    我们也从MapReduce开发过程中学到了不少东西。首先,约束编程模式使得并行和分布式计算非常容易,也易于构造容错的计算环境;其次,网络带宽是稀有资源。大量的系统优化是针对减少网络传输量为目的的:本地优化策略使大量的数据从本地磁盘读取,中间文件写入本地磁盘、并且只写一份中间文件也节约了网络带宽;第三,多次执行相同的任务可以减少性能缓慢的机器带来的负面影响(alex注:即硬件配置的不平衡),同时解决了由于机器失效导致的数据丢失问题。

    感谢

    (alex注:还是原汁原味的感谢词比较好,这个就不翻译了)Josh Levenberg has been instrumental in revising and extending the user-level MapReduce API with a number of new features based on his experience with using MapReduce and other people’s suggestions for enhancements. MapReduce reads its input from and writes its output to the Google File System [8]. We would like to thank Mohit Aron, Howard Gobioff, Markus Gutschke, David Kramer, Shun-Tak Leung, and Josh Redstone for their work in developing GFS. We would also like to thank Percy Liang and Olcan Sercinoglu for their work in developing the cluster management system used by MapReduce. Mike Burrows, Wilson Hsieh, Josh Levenberg, Sharon Perl, Rob Pike, and Debby Wallach provided helpful comments on earlier drafts of this paper.The anonymous OSDI reviewers, and our shepherd, Eric Brewer, provided many useful suggestions of areas where the paper could be improved. Finally, we thank all the users of MapReduce within Google’s engineering organization for providing helpful feedback, suggestions, and bug reports.
    10、参考资料
    [1] Andrea C. Arpaci-Dusseau, Remzi H. Arpaci-Dusseau,David E. Culler, Joseph M. Hellerstein, and David A. Patterson.High-performance sorting on networks of workstations.In Proceedings of the 1997 ACM SIGMOD InternationalConference on Management of Data, Tucson,Arizona, May 1997.
    [2] Remzi H. Arpaci-Dusseau, Eric Anderson, NoahTreuhaft, David E. Culler, Joseph M. Hellerstein, David Patterson, and Kathy Yelick. Cluster I/O with River:Making the fast case common. In Proceedings of the Sixth Workshop on Input/Output in Parallel and Distributed Systems (IOPADS ’99), pages 10.22, Atlanta, Georgia, May 1999.
    [3] Arash Baratloo, Mehmet Karaul, Zvi Kedem, and Peter Wyckoff. Charlotte: Metacomputing on the web. In Proceedings of the 9th International Conference on Parallel and Distributed Computing Systems, 1996. [4] Luiz A. Barroso, Jeffrey Dean, and Urs H¨olzle. Web search for a planet: The Google cluster architecture. IEEE Micro, 23(2):22.28, April 2003.
    [5] John Bent, Douglas Thain, Andrea C.Arpaci-Dusseau, Remzi H. Arpaci-Dusseau, and Miron Livny. Explicit control in a batch-aware distributed file system. In Proceedings of the 1st USENIX Symposium on Networked Systems Design and Implementation NSDI, March 2004.
    [6] Guy E. Blelloch. Scans as primitive parallel operations.IEEE Transactions on Computers, C-38(11), November 1989.
    [7] Armando Fox, Steven D. Gribble, Yatin Chawathe, Eric A. Brewer, and Paul Gauthier. Cluster-based scalable network services. In Proceedings of the 16th ACM Symposium on Operating System Principles, pages 78. 91, Saint-Malo, France, 1997.
    [8] Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung. The Google file system. In 19th Symposium on Operating Systems Principles, pages 29.43, Lake George, New York, 2003. To appear in OSDI 2004 12
    [9] S. Gorlatch. Systematic efficient parallelization of scan and other list homomorphisms. In L. Bouge, P. Fraigniaud, A. Mignotte, and Y. Robert, editors, Euro-Par’96. Parallel Processing, Lecture Notes in Computer Science 1124, pages 401.408. Springer-Verlag, 1996.
    [10] Jim Gray. Sort benchmark home page. http://research.microsoft.com/barc/SortBenchmark/.
    [11] William Gropp, Ewing Lusk, and Anthony Skjellum. Using MPI: Portable Parallel Programming with the Message-Passing Interface. MIT Press, Cambridge, MA, 1999.
    [12] L. Huston, R. Sukthankar, R.Wickremesinghe, M. Satyanarayanan, G. R. Ganger, E. Riedel, and A. Ailamaki. Diamond: A storage architecture for early discard in interactive search. In Proceedings of the 2004 USENIX File and Storage Technologies FAST Conference, April 2004.
    [13] Richard E. Ladner and Michael J. Fischer. Parallel prefix computation. Journal of the ACM, 27(4):831.838, 1980.
    [14] Michael O. Rabin. Efficient dispersal of information for security, load balancing and fault tolerance. Journal of the ACM, 36(2):335.348, 1989.
    [15] Erik Riedel, Christos Faloutsos, Garth A. Gibson, and David Nagle. Active disks for large-scale data processing. IEEE Computer, pages 68.74, June 2001.
    [16] Douglas Thain, Todd Tannenbaum, and Miron Livny. Distributed computing in practice: The Condor experience. Concurrency and Computation: Practice and Experience, 2004.
    [17] L. G. Valiant. A bridging model for parallel computation. Communications of the ACM, 33(8):103.111, 1997.
    [18] Jim Wyllie. Spsort: How to sort a terabyte quickly. http://alme1.almaden.ibm.com/cs/spsort.pdf.

    附录A、单词频率统计

    本节包含了一个完整的程序,用于统计在一组命令行指定的输入文件中,每一个不同的单词出现频率。

    #include “mapreduce/mapreduce.h”
    // User’s map function
    class WordCounter : public Mapper {
     public:
      virtual void Map(const MapInput& input) {
       const string& text = input.value();
       const int n = text.size();
       for (int i = 0; i < n; ) {
        // Skip past leading whitespace
        while ((i < n) && isspace(text[i]))
         i++;
       // Find word end
       int start = i;
       while ((i < n) && !isspace(text[i]))
        i++;
       if (start < i)
        Emit(text.substr(start,i-start),”1″);
      }
     }
    };
    REGISTER_MAPPER(WordCounter);
    // User’s reduce function
    class Adder : public Reducer {
     virtual void Reduce(ReduceInput* input) {
      // Iterate over all entries with the
      // same key and add the values
      int64 value = 0;
      while (!input->done()) {
       value += StringToInt(input->value());
       input->NextValue();
      }
      // Emit sum for input->key()
      Emit(IntToString(value));
     }
    };
    REGISTER_REDUCER(Adder);
    int main(int argc, char** argv) {
     ParseCommandLineFlags(argc, argv);
    
     MapReduceSpecification spec;
    
     // Store list of input files into “spec”
     for (int i = 1; i < argc; i++) {
      MapReduceInput* input = spec.add_input();
      input->set_format(“text”);
      input->set_filepattern(argv[i]);
      input->set_mapper_class(“WordCounter”);
     }
     // Specify the output files:
     // /gfs/test/freq-00000-of-00100
     // /gfs/test/freq-00001-of-00100
     // …
     MapReduceOutput* out = spec.output();
     out->set_filebase(“/gfs/test/freq”);
     out->set_num_tasks(100);
     out->set_format(“text”);
     out->set_reducer_class(“Adder”);
    
     // Optional: do partial sums within map
     // tasks to save network bandwidth
     out->set_combiner_class(“Adder”);
     // Tuning parameters: use at most 2000
     // machines and 100 MB of memory per task
     spec.set_machines(2000);
     spec.set_map_megabytes(100);
     spec.set_reduce_megabytes(100);
    
     // Now run it
     MapReduceResult result;
     if (!MapReduce(spec, &result)) abort();
    
     // Done: ‘result’ structure contains info
     // about counters, time taken, number of
     // machines used, etc.
     return 0;
    }
    展开全文
  • BBR论文中文翻译

    千次阅读 多人点赞 2019-03-31 10:34:42
    BBR 论文中文翻译(原文:BBR: Congestion-Based Congestion Control) 译者:林佳烁 邮件:15622383059@163.com Github仓库:https://github.com/yue2388253/BBR-Translation Measureing bottleneck bandwidth and ...

    BBR 论文中文翻译(原文:BBR: Congestion-Based Congestion Control)

    译者:林佳烁 邮件:15622383059@163.com Github仓库:https://github.com/yue2388253/BBR-Translation

    Measureing bottleneck bandwidth and round-trip propagation time

    因为各种原因,今天的互联网并不能像我们所期望的那样很好地传输数据。世界上大部分蜂窝网络用户都会经历几秒乃至几分钟的时延;在公共局域如机场和会议厅等,WIFI质量经常是非常差的。物理和气候学者想要与全球范围内的合作者传输千兆字节级别的数据,但可能会发现他们精心准备的Gbps级别的底层网络在洲际传输中只能达到Mbps级别。

    这些问题之所以会发生,是因为在80年代设计TCP拥塞控制的时候,TCP将丢包作为“拥塞”的信号。在那个年代,这个假设确实是正确的,但这是因为受限于技术原因。而当网卡的速率从Mbps级别进化为Gbps级别,内存从KB级别进化到GB级别之后,丢包与拥塞的关系变得不那么紧密了。

    今天的这些TCP拥塞控制算法,包括至今为止最好的算法CUBIC,都是基于丢包的。他们是造成这些问题的主要元凶。当瓶颈链路的缓存较大时,这些基于丢包的拥塞控制算法流填满了缓存,造成了bufferbloat。当瓶颈链路的缓存较小时,这些算法会又将丢包作为发生拥塞的信号,从而降低速率导致了较低的吞吐量。为了解决这些问题,必须提出一种不是基于丢包的拥塞控制算法,这需要设计者对网络拥塞是如何并且在哪里产生的有非常深刻的理解。

    Congestion and Bottlenecks

    在一个TCP连接中,每个传输方向都存在一个最慢的链路,或者说瓶颈链路(bottleneck)。

    Bottleneck很重要!这是因为:

    1. 它决定了该连接的最大传输速率(举个例子:如果高速公路上的某一段路发生了车祸,将会导致该道上的车速降低至那一段路的车速)。

    2. 它是造成队列的元凶!因为只有一个链路的离开速率大于它的到达速率,队列才会缩短。对于一个尽力传输最大速率的连接来说,因为其他的链路速率都比bottleneck大,所以最后会造成bottleneck的队列。

    无论一个TCP连接需要穿越多少链路,也无论这些链路的速率各自是多少,从TCP的角度来说,一个及其复杂的路径的行为终究跟一条与它拥有相同RTT和bottleneck速率的简单链路一样。这两个参数,RTprop(Round-trip propagation time)和BtlBw(bottleneck bandwidth),决定了传输的性能。(打个比方,如果将一条网络路径类比为一个管道,RTprop就是管道的长度,BtlBw就是管道中最短的半径。)

    图1展示了RTT和发送速率与发送数据大小的关系。图中的蓝线受到了RTprop的约束,绿线受到BtlBw约束,红线受到瓶颈链路的缓存约束。注意阴影区域的部分是不可达的,因为这会至少违反一项约束。这三种约束形成了3不同的区域,分别为app-limited,bandwidth-limited,buffer-limited。在三种区域,流的行为是完全不同的。

    图1

    图1 发送速率和RTT vs 在外数据

    当没有足够的数据来填满管道时,RTprop决定了流的行为;当有足够的数据填满时,那就变成了BtlBw来决定。这两条约束交汇在点inflight=BtlBw*RTprop,也就是管道的BDP(带宽与时延的乘积)。当管道被填满时,那些超过的部分(inflight-BDP)就会在瓶颈链路中制造了一个队列,从而导致了RTT的增大,如图1所示。当数据继续增加直到填满了缓存时,多余的报文就会被丢弃了。拥塞就是发生在BDP点的右边,而拥塞控制算法就是来控制流的平均工作点离BDP点有多远。

    基于丢包的拥塞控制算法工作在bandwidth-limited区域的右边界区域,尽管这种算法可以达到最大的传输速率,但是它是以高延迟和高丢包率作为代价的。在存储介质较为的时候,缓存大小只比BDP大一点,此时这种算法的时延并不会很高。然而,当存储介质变得便宜之后,交换机的缓存大小已经是ISP链路BDP的很多很多倍了,这导致了bufferbloat,从而导致了RTT从毫秒级升到了秒级。

    工作在bandwidth-limited区域的左边界比工作在有边界好。在1979年Leonard Kleinrock就展示了,无论是对流自身而言,或是对整个网络来说,工作在左边界是最优点,这个点在实现最大传输速率的同时,保持了低时延和低丢包。不幸的是,当时Jeffrey M.Jaffe也同时证明了不可能存在一个分布式算法可以收敛到这个边界点。这使得学术研究不再尝试去设计可以工作在该边界点的分布式算法。

    我们谷歌工作组每天花了大量的时间来查看从世界各地发来的TCP报文头部,从而对流的行为机制有了很深的了解。我们通常首先计算出流最重要的两个参数,RTprop和BtlBw,这两个参数都可以从trace中推断出来。这表明Jaffe的结论可能不再适用。他当时做出这个结论是因为测量具有模糊性(例如,RTT的增加有可能是因为流的路径改变了,也有可能是瓶颈链路的带宽减少了,也有可能是因为别的流竞争而导致队列等等)。尽管不可能在单次测量中得到非常可靠的值,但是一个持续时间较长的连接会告诉你很多信息,从中或许可以设法来估计得到一个可靠的值。

    使用最近在控制领域中提出的鲁棒伺服环来对这些观测结果进行处理,可以设计出一种分布式拥塞控制协议。该协议可以针对真实的拥塞进行反应,而不是基于丢包或者短暂的队列时延的,它可以大概率收敛到Kleinrock的最优边界点。因此这推动了我们近三年的研究——如何基于这两个观测参数bottleneck带宽及RTT(这就是BBR缩写的来源,bottleneck bandwidth and round-trip propagation time)来设计拥塞控制算法。

    Characterizing the bottleneck

    当一个连接满足以下两个条件时,它可以在达到最高的吞吐量的同时保持最低时延:

    1. 速率平衡:瓶颈带宽的数据到达速率与BtlBw相等;

    2. 填满管道:所有的在外数据(inflight data)与BDP(带宽与时延的乘积)相等

    其中,第一个约束保证了瓶颈带宽可以得到100%利用。而第二个约束保证了流有足够的数据来填满瓶颈链路而且同时不会溢出(排队)。第一个条件本身并无法保证路径中不存在队列,它只能保证流的速率不发生改变(例如,考虑一个连接在一开始就发送了10个报文到一个BDP只有5个网络中,并且接下来一直保持瓶颈速率发送。这样子会导致在一开始就填满了管道,并且制造了5个报文的队列,并且这个队列永远不会被消灭)。相似地,full pipe条件也不能保证链路中没有队列。比如,一个TCP连接可以以burst方式发送BDP数量的报文,若该连接每次发二分之一BDP,并且发两次,此时full pipe条件得到满足了,然而网络中的平均队列长度是BDP/4。为了最小化网络中的队列长度,唯一的方式是同时满足以上两个条件。

    然而,BtlBw和RTprop可能是动态变化的,所以我们需要实时地对它们进行估计。目前TCP为了检测丢包,必须实时地跟踪RTT的大小。在任意的时间t,
    RTTt=RTpropt+ηt RTT_t = RT_{prop_t} + \eta_t

    其中,最后一项表示“噪声”。造成噪声的因素主要有:链路队列,接收方的时延ACK配置,ACK聚合等因素等待。RTprop是路径的物理特性,并且只有路径变化才会改变。由于一般来说路径变化的时间尺度远远大于RTprop,所以RTprop可以由以下公式进行估计:

    RTprop^=RTprop+min(ηt)=min(RTTt) t[TWR,T] \widehat {RT_{prop}} = RT_{prop} + min(\eta_t) = min(RTT_t) \space \forall t \in [T -W_R, T]

    即,在一个时间窗口中对RTT取最小值。一般将该窗口大小设置为几十秒至几分钟。

    然而,bottleneck bandwidth的估计不像RTT那样方便,没有一种TCP spec要求实现算法来跟踪估计bottleneck带宽,但是,我们可以通过跟踪发送速率来估计bottleneck带宽。当发送方收到一个ACK报文时,它可以计算出该报文的RTT,并且从发出报文到收到ack报文这段时间的data Inflight。这段时间内的平均发送速率就可以以此计算出来:deliveryRate = delta delivered/ delta t。这个计算出的速率必定小于bottleneck速率(因为delta delivered是确定的,但是delta t会较大)。因此,BtwBw可以根据以下公式进行估计。
    BtlBw^=max(deliveryRatet) t[TWB,T] \widehat{BtlBw} = max(deliveryRate_t) \space \forall t \in [T-W_B, T]
    其中,时间窗口大小的值一般为6~10个RTT。

    TCP必须记录每个报文的离开时间从而计算RTT。BBR必须额外记录已经发送的数据大小,使得在收到每一个ACK之后,计算RTT及发送速率的值,最后得到RTprop和BtlBw的估计值。

    值得注意的是,这两个值是完全独立的:RTprop可以发生变化然而保持bottleneck不变(比如发生路由变化),或者BtlBw可以变化而路径不变(比如无线链路速率发生变化)。(This independence is why both constraints have to be known to match sending behavior to delivery path.)如图1所示,只有在BDP的左边,才能观测到RTprop,并且只有在BDP的右边才能观测到BtlBw,他们遵循了一个不确定性原则:当其中一个可以被观测的时候,另外一个并不能。直觉地,这是因为为了观测出管道的容量,必须填满管道,而这会创造出一个队列从而无法观测到管道的长度。例如,一个使用request/response协议的应用可能永远不会发送足够的数据来填满管道,并且观测到BtlBw。一个持续几个小时的大文件传输应用可能永远处在bandwidth-limited区域,而仅仅在第一个报文中的RTT采集到RTprop。这种不确定性机制意味着,在信息变得不明确的时候,必须要有机制来从当前的工作状态中学习到这两个值的其中一个,并且进入对应的工作区来重新学习这两个值。

    Matching the packet flow to the delivery path

    BBR核心算法包含两大部分:

    • 当收到一个ACK报文时:

    每一个ACK提供了一个新的RTT和新的发送速率估计,BBR将以此为根据来更新RTprop和BtlBw。

    function onAck(packet)
    	rtt = now - packet.sendtime
    	update_min_filter(RTpropFilter, rtt) 
    	delivered += packet.size 
    	delivered_time = now 
    	deliveryRate = (delivered - packet.delivered) 
    				   /(now - packet.delivered_time)
    	if (deliveryRate > BtlBwFilter.currentMax 
    		|| ! packet.app_limited) 
    		update_max_filter(BtlBwFilter, 
    						  deliveryRate)
    	if (app_limited_until > 0) 
    		app_limited_until - = packet.size
    

    伪代码中的if语句是对上一段所讲的不确定性进行估计的:发送方可能受限于应用,发送数据太少,而并没有将管道填满。当发送方采取的协议是request/response类时,这种现象是非常常见的。当没有数据可以发送时,BBR会将对应的带宽估计标志为是应用限制的(见下文伪代码中的send())。这里的算法是为了决定流应该采集哪些数据,而避免采集那些被应用限制的而不是被网络限制的采集数据。BtlBw是发送速率的上界,所以如果计算出的发送速率大于当前所估计的BtlBw值,那么这表示这个估计值太小了(无论该发送速率是否是应用限制的),我们都应该更新它。否则,那些被应用限制的采集数据将会被丢弃。(如图1所示,在app-limited区域中,deliveryRate低估了BtlBw。这些if判断避免BBR低估了BtlBw而导致发送低速率)。

    • 当发送数据时

    为了使得bottleneck链路的报文到达速率和报文离开速率相等,BBR必须进行packet paced。BBR的发送速率必须与bottleneck的速率相等,这意味着BBR的实现需要pacing的支持——pacing_rate是BBR的一个主要控制参数!第二个参数,cwnd_gain,将inflight控制为比BDP稍大一些,从而处理常见的网络机制和接收方机制(参见后文Dealyed and Stretched ACKs)。TCP发送的时候做的事大概如下列伪代码所示(在Linux中,可以使用FQ/pacing qdisc来发送数据,这可以使得BBR在与几千个低速率的paced流在千兆链路上很好地共存,并且使用FQ这种机制也不会额外造成CPU的负担)。

    function send(packet)
    	bdp = BtlBwFilter.currentMax * RTpropFilter.currentMin
    	if (inflight >= cwnd_gain * bdp) // wait for ack or timeout 
    		return
    	if (now >= nextSendTime) 
    		packet = nextPacketToSend() 
    		if (! packet) 
    			app_limited_until = inflight 
    			return
    		packet.app_limited = (app_limited_until > 0)
    		packet.sendtime = now 
    		packet.delivered = delivered
    		packet.delivered_time = delivered_time 
    		ship(packet) 
    		nextSendTime = now + packet.size / (pacing_gain * BtlBwFilter.currentMax)
    	timerCallbackAt(send, nextSendTime)
    

    Steady-state behavior

    BBR的发送速率和发送数量完全就是一个关于BtlBw和RTprop的函数,所以BBR应该小心地估计这两个值。这创造了一种新型的闭环控制,如图2所示。图2显示了一个10Mbps,40ms的流在700ms中的RTT(蓝线),inflight(绿线)和发送速率(红线)变化过程。注意图中在发送速率上方的灰线是BtlBw最大化滤波器的状态。图中产生的三角形形状是因为BBR的pacing_gain周期性的变化产生的,因为BBR必须以此来探测BtlBw是否提高了。图中展示了该增益值在一个周期不同时间的变化和其影响的数据变化。

    BBR将它的大部分时间的在外发送数据都保持为一个BDP大小,并且发送速率保持在估计得BtlBw值,这将会最小化时延。但是这会把网络中的瓶颈链路移动到BBR发送方本身,所以BBR无法察觉BtlBw是否上升了。所以,BBR周期性的在一个RTprop时间内将pacing_gain设为一个大于1的值,这将会增加发送速率和在外报文。如果BtlBw没有改变,那么这意味着BBR在网络中制造了队列,增大了RTT,而deliveryRate仍然没有改变。(这个队列将会在下个RTprop周期被BBR使用小于1的pacing_gain来消除)。如果BtlBw增大了,那么deliveryRate增大了,并且BBR会立即更新BtlBw的估计值,从而增大了发送速率。通过这种机制,BBR可以以指数速度非常快地收敛到瓶颈链路。如图3显示的,我们在1条10Mbps,40ms的流在20s稳定运行之后将BtlBw提高了1倍(20Mbps),然后在第40s又将BtlBw恢复至20Mbps。

    图2 RTT(蓝线),在外数据(绿线)和发送速率(红线)细节

    (BBR is a simple instance of a Max-plus control system, a new approach to control based on nonstandard algebra.12 This approach allows the adaptation rate [controlled by the max gain] to be independent of the queue growth [controlled by the average gain]. Applied to this problem, it results in a simple, implicit control loop where the adaptation to physical constraint changes is automatically handled by the filters representing those constraints. A conventional control system would require multiple loops connected by a complex state machine to accomplish the same result.)

    Single BBR flow Startup behavior

    现有的TCP实现使用基于事件的算法来对事件如启动、关闭、丢包恢复(loss recovery)进行处理,这需要非常多的代码。BBR使用前文提到的代码(见Matching the Packet Flow to the Delivery Path一章)来应对一切。BBR通过一系列异步“状态”来处理事件,这些“状态”是根据一张包含多个固定增益和退出条件的表来定义的。BBR大多时候都出于ProbeBW阶状态(见Steady-state Behavior一章)。在连接启动的时候,BBR使用了Startup和Drain状态(见图4)。为了处理大小范围超过12个数量级的带宽,Startup对BtlBw进行二乘查找,它使用2/ln2的增益来对发送速率翻倍。这将会在log_2BDP的RTT时间内确定BtlBw的值,但会制造最多2个BDP的队列。一单Startup找到了BtlBw,BBR转变为Drain状态,该状态使用了Startup增益的倒数来消耗队列。消耗完队列之后,BBR进入ProbeBW阶段来维持1个BDP的在外数据。

    在这里插入图片描述

    图3 带宽变化<\center>

    图4展示了1个10Mbps,40ms的BBR流在一开始的1秒内,发送方(绿线)和接收方(蓝线)的过程。红线表示的是同样条件下的CUBIC发送。垂直的灰线表示了BBR状态的转换。下方图片展示了两种连接的RTT在这段时间的变化。注意,只有收到了ACK(蓝线)之后才能确定出RTT,所以在时间上有点偏移。图中标注了BBR何时学习到RTT和如何反应。

    在这里插入图片描述

    图4 10Mbps、40ms链路上BBR流的第一秒

    图4的下图展现了BBR和CUBIC行为的巨大不同。他们的初始行为都是相似的,但是BBR可以完全地消耗掉它启动阶段产生的队列,而CUBIC并不能。CUBIC没有一个路径模型来告诉它应该发送多少报文,所以CUBIC一直在缓慢地增加他的在外报文,直到瓶颈链路缓存填满而丢包、或者接收方的缓存(TCP接受窗口)满了。

    图5展示了在图4中展示的BBR和CUBIC流在开始8秒的行为。CUBIC(红线)填满了缓存之后,周期性地在70%~100%的带宽范围内波动。然而BBR(绿线)在启动过程结束后,就非常稳定地运行,并且不会产生任何队列。

    在这里插入图片描述

    图5 在10Mbps、40ms链路上的BBR流和CUBIC流的前8秒对比

    Multiple BBR flows sharing a bottleneck

    图6展示了在一个100Mbps、10ms的瓶颈链路上共享的多个BBR流是如何收敛到公平值的。他们之所以会减小带宽是因为他们进入了ProbeRTT阶段,使得他们快速地收敛。

    ProbeBW机制(见图2)会使得大流会让渡带宽给小流,最终使得每个流都学习到自己的fair share。尽管后发送者可能会因为别的流暂时地创造了队列,而高估了RTprop,从而导致不公平性,但最终都会在几个ProbeBW周期内收敛到公平值。

    为了得到真实的RTprop值,一个流会使用ProbeRTT状态来将自己的工作点移动到BDP的左边:当好几秒内都没有更新RTprop时,BBR进入ProbeRTT状态,这会使得inflight在至少一个RTT内降低为4个报文,然后BBR再重新进入正常阶段。大流进入ProbeRTT阶段会消耗队列中的许多报文,所以会让其他的流学习到一个更小的RTprop值。这会同时让他们的RTprop估计值过期,并同时一起进入ProbeRTT阶段。这会更快地消耗掉队列中的报文,并使得更多的流学习到一个新的RTprop值并一直循环。这个分布式的合作机制是实现公平性和稳定性的重点!

    在这里插入图片描述

    图6 共享同一个瓶颈链路的5个BBR流的吞吐量

    BBR可以使得多个流共享一个链路而不会造成队列,而基于丢包的拥塞控制算法会造成队列周期性地增长然后再溢出,导致了高时延和丢包。

    Google B4 WAN deployment experience

    谷歌B4网络是一个使用商业交换机的高速广域网。在这个网络中,丢包经常是因为这些只有少量缓存的交换机没办法缓存大量突发性的报文。在2015年谷歌开始将B4的生产流量从CUBIC换成BBR。在这个过程中没有出现任何问题,一切都很顺利。直到2016年,所有B4的TCP流量都使用BBR。图7展示了做这种改变的一个原因:BBR的吞吐量能够稳定地维持在CUBIC的2到25倍。我们本来期望能够提高得更多,但是最终发现75%的BBR连接都被内核的TCP接收缓存限制了,这是因为网络运维组故意将缓存设成比较低的值(8MB)来避免CUBIC发送太多的inflight。手动地在一条从美国到欧洲的路径上的接收缓存调高,会立即将BBR的吞吐量提高至2Gbps,然而CUBIC还是维持在15Mbps(Mathis语言可以达到133倍的提高)。

    在这里插入图片描述

    图7 BBR的吞吐量相对CUBIC的吞吐量提高比例

    图7展示了BBR相比CUBIC的吞吐量提升,子图显示的是吞吐量的CDF(累积分布函数)。图中的数据来源于一个探测服务,该探测服务每分钟都会打开一个BBR连接和一个CUBIC连接到远端数据中心,然后传输8MB数据。这些连接包括了B4的很多路径,如在北美、欧洲、亚洲之间或者在洲内传输路径等等。

    BBR不再使用丢包作为拥塞信号是我们的一大贡献!为了达到最大带宽,现有的基于丢包的拥塞控制算法需要丢包率小于BDP的倒数的平方(例如,在1Gbps/100ms的链路上,丢包率需要小于三千万分之一)。图八比较了BBR和CUBIC在不同丢包率的吞吐量。可以看到,CUBIC很受丢包影响,而BBR的影响并不大。当BBR的丢包率接近ProbeBW的增益时,估计到实际BtlBw的概率急剧下降,这导致了BBR低估了BtlBw。

    图8展示了在一条100Mbps,100ms的链路上,BBR和CUBIC在60秒内的吞吐量与随机丢包率(从0.001%~50%)的关系。在丢包率只有0.1%的时候,CUBIC的吞吐量就已经下降了10倍,并且在丢包率为1%的时候就几乎炸了。而理论上的最大吞吐量是链路速率乘以(1-丢包率)。BBR在丢包率为5%以下时还能基本维持在最大吞吐量附近,在15%丢包率的时候虽然有所下降但还是不错。

    YOUTUBE edge deployment experience

    我们将BBR部署在Google.com和YouTube的视频服务器上。我们随机挑选一部分用户来使用CUBIC或BBR来进行实验。使用BBR算法的playback基本上在所有的YouTube的QoE参数上都有所显著提高,这可能是因为BBR的行为是更加一致的并且是可预测的。由于YouTube已经能很好地自适应将视频传输速率调节到BtlBw之下来避免bufferbloat和重缓存,所以BBR在吞吐量上只比CUBIC提高了一点点。尽管如此,在全世界范围内,BBR将RTT中位数平均降低了53%,而这个数值在发展中国家是80%。图9统计了在一星期中,在五大洲的超过2亿YouTube的playback连接中,BBR的RTT中位数相对于CUBIC的提高幅度。

    在这里插入图片描述

    图8 BBC和CUBIC的吞吐量与丢包率的关系

    在全球范围内的70亿互联网移动终端中,超过一半设备使用8至114kbps的2.G系统。因为基于丢包的拥塞控制算法填满buffer的特点,这些连接已经暴露了太多太多的问题。他们的bottleneck链路一般情况下都是无线终端与基站之间的链路。图10展示了使用BBR和使用CUBIC在基站与用户终端见的延迟的对比。其中的水平线标志了一个很严重的结果:TCP在连接建立阶段没有办法忍受太长的RTT时延,在该阶段,TCP等待SYN的时延是一个与操作系统相关的timeout。当移动设备在接收大量的数据而此时的基站缓存又足够大时,在基站的队列耗尽之前,移动终端将没有办法打开新的连接到互联网!(这是因为移动终端等到花儿都谢了都没有等到SYN ACK)

    在这里插入图片描述

    图9 BBR的RTT中位数相比CUBIC的提高比例

    图10展示了在稳定状态下,在一个具有8个BBR(绿线)或CUBIC流(红线)的128Kbps,40ms的链路上,RTT中位数与链路缓存大小的关系。由图中可以看到,无论链路缓存如何变化,BBR都可以保持队列为空。而由于CUBIC总会把缓存填满,所以CUBIC的曲线随着缓存的增大而线性增长。
    在这里插入图片描述

    图10 稳定状态下RTT中位数随着链路缓存大小的变化

    Mobile cellular adaptive bandwidth

    蜂窝系统对每一个用户使用一个队列来统计报文数量,并以此为根据来评估用户的需求带宽,从而自适应调整每个用户的带宽。早期我们为了不创造太深的队列,调整了BBR,但是这导致了连接速率非常慢。提高ProbeBW的pacing_gain会创造较长的队列,但会减少低速连接的数量。从这里我们学到了,BBR可能对某些网络太过仁慈了!目前我们将BtlBw的增益设置为1.25,经过测试,BBR不会在任何一种网络中输给CUBIC了!

    Delayed and stretched acks

    蜂窝、WiFi以及有限宽带网络经常会将ACK进行延时或者聚合。当BBR将带宽控制为1个BDP时,这种行为可能会导致吞吐量不够高。可以将ProbeBW的cwnd_gain提高为2从而允许BBR持续地以估计的速率平滑地发送数据,即使ACK被延时了1个RTT。这可以很好地避免BBR产生低吞吐量。

    Token-bucket policers

    早期我们将BBR部署在YouTube的时候,我们就发现了全球范围内大多数ISP都会使用令牌桶策略将流量进行限速。

    大多数情况下,在连接的开始阶段,bucket都是满的,所以BBR可以学习到网络的Btlbw,然而一旦bucket空了,所有发送速率大于bucket补充速率(该速率远小于BtlBw)的报文都会被丢弃。最终BBR会学习这个新的发送速率,然而ProbeBW仍然会导致持续丢包。为了避免浪费带宽,为了降低这些丢包带来的时延,我们为BBR添加了一个流量管控检测模块和一个显式的流量管控模块。我们也正在寻找更好的办法来降低这种流量管控带来的影响。

    Competition with loss-based congestion control

    无论竞争流的拥塞控制算法是BBR还是其他基于丢包的算法,BBR都能最终收敛到一个公平值。即使基于丢包的算法会将缓存填满,ProbeBW仍然会鲁棒地将BtlBw估计为公平值,ProbeRTT仍会估计到一个较高的RTProp来保持公平性。然而,有时候,路由器的缓存太大,大小超过了几个BDP,这会使得持续时间较长的基于丢包的竞争流填满了队列,而得到了一个较大的份额。未来的研究方向包括如何降低这种流的影响!

    Conclusion

    重新对拥塞控制进行思考会带来很大的好处。BBR并不是基于事件如丢包、或者发生缓存等,这些事件并没有跟拥塞发生非常紧密的联系。BBR起源于Kleinrock关于拥塞的模型,它工作在那个最优点上。通过异步观测估计时延和带宽,BBR绕过了那个不确定魔咒,即时延和带宽没办法同时被估计。我们使用了控制和估计理论最近几年的发展,设计了一个简单的分布式控制环,它可以近似地工作在最优点,在完全利用网络带宽的同时并不会制造长的队列。目前开源的Linux内核TCP已经集成了谷歌的BBR实现,关于更多的细节,请查看附录。

    我们将BBR部署在谷歌的B4骨干网,它的吞吐量相比CUBIC提高了几个数量级。我们也将BBR部署在谷歌和YouTube的Web服务器上,它减小了五大洲的传输时延,特别是在发展中地区。BBR仅工作在发送端,它无需对协议、接收方、网络作任何修改,这使得它非常容易部署。BBR只关心RTT和数据传输速率,所以它能够被部署在大多数的传输层协议上。

    联系我们:https://googlegroups.com/d/forum/bbr-dev

    Acknowledgments

    The authors are grateful to Len Kleinrock for pointing out the right way to do congestion control. We are indebted to Larry Brakmo for pioneering work on Vegas2 and New Vegas congestion control that presaged many elements of BBR, and for advice and guidance during BBR’s early development. We would also like to thank Eric Dumazet, Nandita Dukkipati, Jana Iyengar, Ian Swett, M. Fitz Nowlan, David Wetherall, Leonidas Kontothanassis, Amin Vahdat, and the Google BwE and YouTube infrastructure teams for their invaluable help and support.

    References

    1. Abrahamsson, M. 2015. TCP ACK suppression. IETF AQM mailing list; https://www.ietf.org/mail-archive/web/aqm/urrent/msg01480.html.

    2. Brakmo, L. S., Peterson, L.L. 1995. TCP Vegas: end-to-end congestion avoidance on a global Internet. IEEE Journal on Selected Areas in Communications 13(8): 1465–1480.

    3. Chakravorty, R., Cartwright, J., Pratt, I. 2002. Practical experience with TCP over GPRS. In IEEE GLOBECOM.

    4. Corbet, J. 2013. TSO sizing and the FQ scheduler. LWN. net; https://lwn.net/Articles/564978/.

    5. Ericsson. 2015 Ericsson Mobility Report (June); https:// www.ericsson.com/res/docs/2015/ericsson-mobility- report-june-2015.pdf.

    6. ESnet. Application tuning to optimize international astronomy workflow from NERSC to LFI-DPC at INAF- OATs; http://fasterdata.es.net/data-transfer-tools/case- studies/nersc-astronomy/.

    7. Flach, T., Papageorge, P., Terzis, A., Pedrosa, L., Cheng, Y., Karim, T., Katz-Bassett, E., Govindan, R. 2016. An Internet-wide analysis of traffic policing. In ACM SIGCOMM: 468–482.

    8. Gail, R., Kleinrock, L. 1981. An invariant property of computer network power. In Conference Record, International Conference on Communications: 63.1.1- 63.1.5.

    9. Gettys, J., Nichols, K. 2011. Bufferbloat: dark buffers in the Internet. acmqueue 9(11); http://queue.acm.org/ detail.cfm?id=2071893.

    10. Ha, S., Rhee, I. 2011. Taming the elephants: new TCP slow start. Computer Networks 55(9): 2092–2110.

    11. Ha, S., Rhee, I., Xu, L. 2008. CUBIC: a new TCP-friendly high-speed TCP variant. ACM SIGOPS Operating Systems Review 42(5): 64–74.

    12. Heidergott, B., Olsder, G. J., Van Der Woude, J. 2014. Max Plus at Work: Modeling and Analysis of Synchronized Systems: a Course on Max-Plus Algebra and its Applications. Princeton University Press.

    13. Jacobson, V. 1988. Congestion avoidance and control. ACM SIGCOMM Computer Communication Review 18(4): 314–329.

    14. Jaffe, J. 1981. Flow control power is nondecentralizable. IEEE Transactions on Communications 29(9): 1301–1306.

    15. Jain, S., Kumar, A., Mandal, S., Ong, J., Poutievski, L., Singh, A., Venkata, S., Wanderer, J., Zhou, J., Zhu, M.,et al. 2013. B4: experience with a globally-deployed software defined WAN. ACM SIGCOMM Computer Communication Review 43(4): 3–14.

    16. Kleinrock, L. 1979. Power and deterministic rules of thumb for probabilistic problems in computer communications. In Conference Record, International Conference on Communications: 43.1.1-43.1.10.

    17. Mathis, M., Semke, J., Mahdavi, J., Ott, T. 1997. The macroscopic behavior of the TCP congestion avoidance algorithm. ACM SIGCOMM Computer Communication Review 27(3): 67–82.

    18. Wikipedia. GPRS core network serving GPRS support node; https://en.wikipedia.org/wiki/GPRS_core_ network#Serving_GPRS_support_node_.28SGSN.29.

    Related Articles

    Appendix - Detailed Description

    A state machine for sequential probing

    pacing_gain用于控制相对于BtlBw的数据发送速率,它是BBR的关键!当pacing_gain大于1时,它增加了在外报文数量,减少了数据到达间隔时间,在图1中,它将工作点右移了。当pacing_gain小于1时,它的效果刚好相反,它将工作点往左移。

    BBR使用pacing_gain来实现一个简单的异步探测状态机,它不停地探测高可用带宽和低时延。(没有必要去探测带宽是否变低了,因为BtlBw滤波器会自动地做这件事:当一个估计值迟迟没有更新时,它就会丢弃掉这个值重新估计带宽了。类似地,RTprop滤波器也会自动地丢掉过时的估计值)。

    如果链路带宽提高了,BBR必须发送得快一些来发现它。相似地,如果实际的往返传播时延变化了,从而改变了BDP,因此BBBR必须将发少一些,使得在外传输报文数量低于BDP从而估计新的RTprop值。因此,为了发现这些动态变化,唯一的办法就是做探测:发快点来检测BtlBw是否提高,发慢点来检测RTprop是否降低。做这些探测的频率、强度、持续时间和结构都取决于已知(在startup和稳定状态)和发送应用的行为(断续的或持续的)。

    Steady-state behavior

    BBR大多数的时间都处于ProbeBW状态,它使用一种名为gain cycling的方法来探测带宽,从而取得较高的吞吐量,较低的队列实验,并且最终收敛到一个公平带宽值。使用这个方法,BBR周期性地调整pacing_gain值。它使用一个有八个阶段的周期,值分别为:5/4,3/4,1,1,1,1,1,1。每个阶段一般持续时间为估计的RTprop值。这种设计使得BBR首先使用一个大于1的pacing_gain值来探测高可用带宽,并在下一阶段使用一个低于1的值来消耗队列,然后接下来都稳定工作在值为1的阶段。因为ProbeBW旨在调整平均发送速率与可用带宽相等来保持对网络的高利用率,并且同时不制造一个长队列,所以该增益值的平均值为1。注意,尽管pacing_gain的值随着时间变化,但是cwnd_gain的值并不变化,它保持为2,这是因为ACK会被时延(详见章节Delayed and Stretched Acks)。

    而且,为了提高公平性,并且在多个BBR流共享同一个瓶颈链路的时候能保持队列较短,BBR随机挑选一个值来作为gain cycling周期的开始值来进入ProbeBW状态(除了3/4)。为什么3/4不能被挑选为初始值呢?因为3/4是为了消耗在它之前的那个5/4产生的队列。当BBR从Drain状态或ProbeRTT状态进入ProbeBW状态时,并不需要消耗队列。使用3/4只会使得在该阶段,链路的利用率为3/4,而不是1。既然3/4没有好处只有坏处,我们干嘛还要使用它呢?

    多个BBR流可以周期地进入ProbeRTT状态从而消耗掉瓶颈链路的队列。当BBR的状态不是ProbeRTT时,只要RTProp估计值一段时间内(超过10秒)没有得到更新(如,得到一个更低的RTT观测值),那么BBR就会进入ProbeRTT状态,并且将cwnd值减小为一个非常小的值(4个包)。在保持这个非常小的cwnd值运行至少200ms和一个往返时间后,BBR离开ProbeRTT状态,进入Startup或者ProbeBW阶段(这取决于它对当前管道是否为满的评估)。

    我们将BBR设计为将绝大多数的时间(约98%)处于ProbeBW阶段,并且其余的时间处于ProbeRTT阶段。ProbeRTT会至少持续200ms来适应不同的RTT,这对整个BBR流的性能惩罚已经足够小了(大约在2%,200ms/10ms)。)对于流量变化或路由变化来说,RTprop滤波器的窗口大小(10s)足够小,它可以快速收敛。另一方面对于那些交互性的应用(如网页浏览、RPC、视频传输等)来说,这个窗口大小是足够大的,它可以允许这些应用在一小段时间内传输很少的数据,而且可以消耗掉这段瓶颈链路的队列。由于RTprop滤波器会时常更新值,所以BBR并不必经常进入ProbeRTT阶段。通过这种方式,典型地,当多个大流持续地在整个RTprop窗口内发送大量报文时,BBR只需要受到2%的惩罚。

    Startup behavior

    当一个BBR流开始启动的时候,它开始它的第一个异步探测过程。网络链路的带宽范围非常大(10^12),从几个位每秒到100kMb每秒。为了在这个这么大的范围内学习到BtlBw,BBR的查找是幂次的。这可以非常快地在确定BtlBw的值(在log_2BDP时间内),但这会在最后一步时制造出2BDP的队列。在BBR的Startup阶段后,Drain阶段会消耗掉这些队列。

    一开始,Startup以幂次方增加发送速率,每次将它乘以2。为了平滑地快速地进行这个探测的过程,在Startup阶段,BBR的pacing_gain和cwnd_gain被设为2/ln2,这个值是可以使得发送速率每次乘2的最小值。一旦管道满了,cmwd_gain会保证队列的长度不超过(cwnd_gain-1)*BDP。

    当BBR处于Startup状态时,若BtlBw估计值在一段时间内不变,那么BBR判断当前管道已满。如果它注意到在几个(3)往返时间内,当它尝试对发送速率进行翻倍并没有引起很大的提升(低于25%),那么它判断它已经到达了BtlBw,所以BBR会离开Startup状态,然后进入Drain阶段。之所以BBR要等待3个往返时间,是因为它要确保BtlBw估计值不发生改变不是因为接收方的接收窗口导致的。BBR等待3个往返时间使得接收方可以调节接收窗口,从而使得BBR发送方可以察觉到BtlBw可以更高:在第一个往返中,接收方窗口自动调节的算法会将接收窗口增大;第二个往返中,发送方将该接收窗口填满;所以,第三个往返中,发送方可以取得更高的发送速率估计值。我们通过YouTube的实验数据来验证了这个阈值(3个往返)。

    BBR的Drain状态旨在快速消耗掉Startup状态产生的队列,它是通过将pacing_gain的大小设为其在Startup状态时的大小的倒数来实现的,这会在一个往返时间内就消耗完队列。当在外数据大小与估计的BDP值相等时,这意味着BBR已经将网络中的队列清空了,并且此时的管道仍然是满的。此时BBR离开Drain状态,进入ProbeBW状态。

    注意,BBR的Startup阶段和CUBIC的慢启动都是以指数探测瓶颈带宽,它们都在每个往返将发送速率翻倍。然而它们是不同的。首先,BBR在发现可用带宽这方面更加鲁棒,因为它并不是根据丢包或者时延的增加(如CUBIC的Hystart)来离开Startup状态的。第二,BBR平滑地加速它的发送速率,而CUBIC在每一次往返都是突发地发送数据,然后在接下来一段时间内就不发了(就算设置了pacing也一样)。图4展示了BBR和CUBIC在每次收到ack的在外报文数量和RTT。

    Reacting to transients

    网络路径和网络流量都可能会发生突然变化。为了平滑地、鲁棒地处理这些变化,并且降低在这些情况下的丢包,BBR使用一些列策略在实现它的核心模型。首先,BBR的在外数据目标是cwnd_gain与BDP的乘积,而BBR的cwnd是小心地增大的,cwnd每次增大的大小都不会超过被确认的数据。其次,当发生重传超时时,这意味着发送端会认为所有的在外报文都被丢弃了,BBR保守地将cwnd减小为1,并且仅发送1个报文(就像CUBIC等那些基于丢包的拥塞控制算法一样)。最后,当发送方发现丢包,但此时仍存在在外数据时,在第一个往返时,BBR会暂时地将发送速率减小为当前的发送速率;在第二个往返以及之后,它会确保发送速率不会超过当前发送速率的两倍。当BBR遇到流量管控或者与其他的流竞争一个缓存只有一个BDP的链路时,这会显著地降低暂时的丢包。

    The authors are members of Google’s make-tcp-fast project, whose goal is to evolve Internet transport via fundamental research and open source software. Project contributions include TFO (TCP Fast Open), TLP (Tail Loss Probe), RACK loss recovery, fq/pacing, and a large fraction of the git commits to the Linux kernel TCP code for the past five years.

    最后,向大牛致敬吧!

    展开全文
  • <p>select student.sname , score.num from score inner join student on score.student_id = student.sid inner join course on...where course.cname = "物理" and score.num = 100</p>
  • peewee 中文翻译文档

    千次阅读 2017-06-19 12:57:33
    peewee 中文翻译文档                   翻译:黑洞       Release 2.4.0   始译于:2017.06.16     目录 peewee 中文翻译文档.... 1 目 录.... 3 1. 产品概述.... ...

     

     

     

     

     

     

     

     

     

     

     

     

    peewee 中文翻译文档

     

     

     

     

     

     

     

     

     

    翻译:黑洞

     

     

     

    Release 2.4.0

     

    始译于:2017.06.16


     


     

    peewee 中文翻译文档.... 1

    目 录.... 3

    1. 产品概述.... 4

    1.1 产品名称... 4

    1.1 产品用途... 4

    1.2 产品构成... 4

     


     

    1.     安装和测试

    大多数用户更愿意采用简单的方式来安装最新版本的peewee程序, 程序托管在PyPI上:

    pip install peewee

     

    1.1 使用 git进行安装

    本项目托管在地址 https://github.com/coleifer/peewee上,用户可以使用git进行安装。

     

    git clone https://github.com/coleifer/peewee.git

    cd peewee

    python setup.py install

     

    注意: 在某些系统上你可能需要使用:sudo python setup.py install 去安装peewee全系统环境

     

    1.2 进行测试

             你可以使用如下命令对你的安装结果进行测试:

    python setup.py test

    # 或者使用测试runner程序

    python runtests.py

    你可以使用runtests.py 脚本测试特定的功能或者特定的数据库驱动. 默认情况下测试套件的运行使用的是SQLite数据库,playhouse扩展测试不会运行。要查看可用的测试运行器选项,请使用:

    python runtests.py --help

     

    2.     快速开始

    2.1 进行测试

    本文档提供了一个简短而高层次概述的Peewee主要特点描述。本指南将涵盖:

    •模型定义

    •存储数据

    •检索数据

     

     

    注意:如果你想要更多的干货,这里有一个更加深入的教程:创建一个“推特”风格的Web应用程序通过使用Peewee和Flask框架。

     

    我强烈建议打开交互式shell会话运行代码,这样你才能感受到输入查询的过程。

     

    2.2 模型定义

    每一个模型类将直接映射到某一个数据库表,每个字段将映射到该表上的某一列,每一个模型实例对应于表中的某一行。

    from peewee import *

    db= SqliteDatabase(’people.db’)

    classPerson(Model):

    name = CharField()

    birthday = DateField()

    is_relative = BooleanField()

     

    class Meta:

    database = db # This model uses the"people.db" database.

     

    Peewee中有许多字段类型适合存储各种类型的数据。Peewee将会处理python和数据库之间的值转换的问题,这样您就可以在代码中使用Python类型而不必担心了。

    当我们使用外键建立模型之间的关系时,Peewee很容易做到

    class Pet(Model):

    owner = ForeignKeyField(Person,related_name=’pets’)

    name = CharField()

    animal_type = CharField()

     

    classMeta:

    database = db # this model uses the peopledatabase

     

    现在我们有了模型,让我们创建数据库中的表来存储数据。一下命令将创建带有适当的列、索引、序列和外键约束的表:

     

    >>> db.create_tables([Person, Pet])

     

    2.2 存储数据

    让我们开始人工填充一些数据到数据库。我们将使用save()和create()方法添加更新Person的记录。

     

    >>> fromdatetimeimport date

    >>>uncle_bob = Person(name=’Bob’, birthday=date(1960, 1, 15), is_relative=True)

    >>>uncle_bob.save() # bob is now stored in the database

     

     

    注意:当你调用save()方法的时候,将会返回改变后的行数。

     

    你也可以通过调用create()方法添加一个人,它会返回一个模型实例:

     

    >>>grandma = Person.create(name=’Grandma’,birthday=date(1935, 3, 1), is_relative=True)

    >>>herb = Person.create(name=’Herb’, birthday=date(1950, 5, 5), is_relative=False)

     

    更新、修改模型的实例并调用save()方法使更改生效。在这里,我们将改变Grandma的名字然后将更改后的数据保存到数据库中。

     

    >>>grandma.name = ’Grandma L.’

    >>>grandma.save() # Update grandma’s name in the database.

    1

     

    现在我们已经在数据库中存储了3个人。让我们给他们一些宠物。Grandma不喜欢房子里的动物,所以她不会有,但Herb是一个动物爱好者:

     

    >>>bob_kitty = Pet.create(owner=uncle_bob, name=’Kitty’,animal_type=’cat’)

    >>>herb_fido = Pet.create(owner=herb, name=’Fido’,animal_type=’dog’)

    >>>herb_mittens = Pet.create(owner=herb, name=’Mittens’,animal_type=’cat’)

    >>>herb_mittens_jr = Pet.create(owner=herb, name=’Mittens Jr’,animal_type=’cat’)

     

    经过很长一段时间的生活后,Mittens生病恶心而且死了。我们需要把它从数据库中删除:

     

    >>>herb_mittens.delete_instance() # he had a great life

    1

     

     

    注意:返回数是删除的行数。

     

    Bob的叔叔决定,太多的动物已经在Herb家死了,所以他接收了Fido:

     

    >>>herb_fido.owner = uncle_bob

    >>>herb_fido.save()

    >>>bob_fido = herb_fido # rename our variable for clarity

     

    2.2 检索数据

    我们的数据库的真正实力是允许我们通过查询检索数据。关系数据库对于即席查询是优秀的。

    2.2.1 查询单个记录

    让我们从数据库中检索Grandma的记录。若要从数据库获得单个记录,请使用:

    SelectQuery.get()方法。

    >>>grandma = Person.select().where(Person.name == ’GrandmaL.’).get()

     

    我们还可以使用等效Model.get()方法:

    >>>grandma = Person.get(Person.name == ’Grandma L.’)

     

    2.2.1 查询多个记录

    让我们列出数据库中所有的人:

    >>> for person in Person.select():

    ...             print person.name, person.is_relative

    ...

    Bob True

    Grandma L. True

    Herb False

     

    让我们列出数据库中所有的猫和其主人:

    >>>query = Pet.select().where(Pet.animal_type == ’cat’)

    >>> for pet in query:

    ... print pet.name,pet.owner.name

    ...

    Kitty Bob

    Mittens Jr Herb

     

    在之前的查询中存在一个大问题:因为我们是访问pet.owner.name而且在我们原来的查询中我们没有选择这个值,peewee将要执行一个查询来检索宠物的主人。这行为被称为N + 1,通常应该避免。

    我们可以通过选择宠物和人并添加连接来避免额外的查询。

    >>>query = (Pet

    ...                       .select(Pet, Person)

    ..                         .join(Person)

    ...                       .where(Pet.animal_type ==’cat’))

    >>> for pet in query:

    ...             print pet.name, pet.owner.name

    ...

    Kitty Bob

    Mittens Jr Herb

     

    让我们获取所以Bob的宠物:

    >>> for pet inPet.select().join(Person).where(Person.name == ’Bob’):

    ...             print pet.name

    ...

    Kitty

    Fido

     

    我们可以在这里做另一件很酷的事来得到Bob的宠物。既然我们已经有一个对象来代表鲍伯,我们可以这么做:

     

    >>> for pet in Pet.select().where(Pet.owner== uncle_bob):

    ...             print pet.name

     

    通过添加一个order_by()条款让我们确保这些都是按字母顺序排序:

     

    >>> for pet in Pet.select().where(Pet.owner== uncle_bob).order_by(Pet.name):

    ...             print pet.name

    ...

    Fido

    Kitty

     

    让我们从小到老列出所有人:

    >>> for person inPerson.select().order_by(Person.birthday.desc()):

    ...             print person.name

    ...

    Bob

    Herb

    Grandma L.

     

    现在让我们列出所有的人和一些关于他们宠物的信息:

    >>> for person in Person.select():

    ...             print person.name, person.pets.count(), ’pets’

    ...             for pet in person.pets:

    ...                                print ’ ’, pet.name,pet.animal_type

    ...

    Bob 2 pets

    Kitty cat

    Fido dog

    Grandma L. 0pets

    Herb 1 pets

    Mittens Jr cat

     

    我们再次遇到了一个典型的n + 1查询行为示例。我们可以通过执行JOIN来避免这种情况。

    汇总记录

    >>>subquery = Pet.select(fn.COUNT(Pet.id)).where(Pet.owner == Person.id).

    >>>query = (Person

    ...                        .select(Person, Pet,subquery.alias(’pet_count’))

    ...                       .join(Pet,JOIN_LEFT_OUTER)

    ...                       .order_by(Person.name))

    >>> forperson in query.aggregate_rows(): # Note the ‘aggregate_rows()‘ call.

    ...               print person.name,person.pet_count, ’pets’

    ...               for pet in person.pets:

    ...                       print ’   ’, pet.name, pet.animal_type

    ...

    Bob 2 pets

    Kitty cat

    Fido dog

    Grandma L. 0pets

    Herb 1 pets

    Mittens Jr cat

     

    即使我们创建的查询分开,只有一个查询的实际执行。

    最后,让我们做一个复杂的例子。让我们把所有的生日都找回来:

    •1940岁之前(祖母)

    •1959后(鲍勃)

     

     

     

     

    展开全文
  • 最近学习UE4的使用,发现这篇官方文档没有中文翻译,就想着翻译一下给大家参考参考吧。由于水平有限,里面一些翻译掺杂了我个人的理解,如果有任何问题欢迎提出,我会及时修改的~同时这里需要声明一点,官方的中文...



    近学习UE4的使用,发现这篇官方文档没有中文翻译,就想着翻译一下给大家参考参考吧。由于水平有限,里面一些翻译掺杂了我个人的理解,如果有任何问题欢迎提出,我会及时修改的~同时这里需要声明一点,官方的中文文档已经有很久没有更新(当前文档的版本应该是4.7以前的),如果需要的话,我可能会将当前的英文官方文档(当前是4.9版本)翻译出来。

    AnimMontage(动画剪辑:蒙太奇)


    Overview(综述

    AnimMontages (or just Montages for short) are a multipurpose tool that allows for a wide variety of animation effects, primarily related to exposing animation controls within code or Blueprint. It can also be used to create a wide variety of animation effects including intelligent loops of animation, logic-based animation switching, root motion handling, and much more.

    动画剪辑系统(简称Montage)是一种通用的工具,他可以将多种动画效果(Animation)传递给那些用代码或者蓝图所实现的动画控制器。他也可以被用来创建诸如动画的智能循环,基于逻辑的动画转换,根节点运动处理等等各种各样的动画(Animation)。(注:Montage即蒙太奇,法语是“剪接”的意思。现在普遍指一种表现电影的拍摄手法,表示对电影镜头的组合运用)

    ---------------------------------------------------------------------------------------------------------------------------------------------------------------------

    AnimMontages are animation assets that can be created and exist within the Content Browser. These assets can then be plugged directly into the AnimGraph in run-time and you can modify any state of it. For example, you can jump to different sections or you can re-link different sections. This is mostly for code driven animations or one-off animations such as melee attacks, allowing you to control triggers, stop when you want, or change state (looping or non-looping) between (see the image below).

    动画剪辑是一个动画集合,可以在内容浏览器被创建并保存。这些集合可以实时的直接插入到*动画编辑图AnimGraph 中并且你可以任意的修改他的状态。例如,你可以切换不同的动画部分并且重新链接他们。动画剪辑大量应用于代码控制的动画或者一次性的动画。例如,格斗攻击动画,需要你来控制触发器,按照你的意愿随时停止或者改变状态(是否循环)。(参考下面的图片)

    Montage_Screen2.png

    The image above is a melee attack with 3 sections [start, loop, and end]. When the player left-clicks, it triggers the start section by default when you ask to play the montage. Now the middle section is set to loop. When the start is done, it will transition to loop, and will loop there forever. If the player lets the mouse button go, it will stop, but you do not want to stop right away since the animation will pop in the middle of the loop. You would like to relink the loop to the end, where it will then transition out to the end and finish the animation.

    上面的图片展示了一个拥有三部分的攻击动画 [开始,循环,结束]。当玩家点击鼠标左键时,就会在你调用动画剪辑 的时候默认触发开始的动画部分。现在我们看到中间部分是被设置为循环的。当开始动画播放结束后,就会过度到中间的循环部分并一直循环下去。如果玩家释放了鼠标左键,循环就会停止。但是你应该不想让动画在播放到一半的时候就突然中断。你可能更想让循环部分播放后再链接到结束动画部分,这样就可以让中间部分渐渐的淡入结尾部分并完成整套动作的播放。(注:这样看起来效果更好)

    ----------------------------------------------------------------------------------------------------------------------------------------------------------------

    Some additional uses for Montages include:

    • The ability to play an animation from within an AnimBlueprint's EventGraph.

    • Chaining together a complex sequence of animations that you want to think of as a single animation.

    • Looping only a specific portion of animation or animations based on code or Blueprint script.

    • Handling event-based switching of multiple animations based on code or Blueprint script.

    • Proper handling of Root Motion for your characters.

    • The ability to assign complex animation sequences to named slots that can be switched between in code or Blueprints.

    • Precise switching between various AnimSequences based on code or Blueprint script.

    一些针对动画剪辑的其他用法:

    • 可以使用蓝图的事件图(EventGraph)来控制播放动画

    • 把多个不同的动画序列链接成一个单独的动画

    • 通过蓝图或代码,局部的循环播放一个或多个动画的特定部分

    • 通过蓝图或代码,处理基于事件的多种复杂动画的切换

    • 恰当的处理“操作对象”的根节点动作

    • 把复杂的动画序列分配给不同的被命名的插槽(注:理解为序列中的任意位置都可以定义一个插槽)

    • 通过蓝图或代码,精确的把不同的动画序列连接到一起

    -----------------------------------------------------------------------------------------------------------------------------------------------------------------

    So, as you can see, there are a lot of different things you can do with Montages. This can easily make Montages seem overwhelming as a system. However, if you really boil it down, the key point of Montages is to expose animation controls to code or Blueprints. Nearly everything else the system can do follows from that single point.

    An example of an Animation Montage applied to a character can also be seen on the Animation Content Examples page under section 1.5.

     所以,我们就会发现,在动画剪辑中我们可以自由地去做很多事情。这使动画剪辑理所当然的成为一个出色的系统。当然,如果非要去总结一下的话,动画剪辑系统就是把所有的动画展示给我们的代码和蓝图,从而让我们能自由的控制。就凭这一点,我们几乎就可以做出一切我们想要的效果。

         想尝试动画剪辑如何运用到角色身上的话也可以参考例子 Animation Content Examples 的1.5章节。
    ----------------------------------------------------------------------------------------------------------------------------------------------------------------

    System Caveats(系统说明)

    There are a few details to keep in mind regarding AnimMontages:

    • Only one Montage can play back at a time. If you start playing a second one, it will stop the first.

    • At this time, root motion is replicated across the server. However the AnimMontage is not. That means that users utilizing root motion will need to make sure they are replicating the state of the AnimMontage across the network. (Position, play rate, etc.).

    关于动画剪辑系统有几点需要说明一下:

    • 同一时刻只能播放一个Montage(注:为了叙述简洁,后面一些地方直接使用英文)动画。如果你开启了另一个Montage动画,第一个就会停止。
    • 动画播放的一刻,根节点的动作将会被复制到服务器上,但是动画剪辑的内容不会被复制。这也就是说,用户执行根节点动作时需要确保动画剪辑的状态通过网络传输到服务器或者其他玩家客户端(如坐标,玩家状态等)。(注:如果客户端服务器状态不统一,会导致二者计算结果不同,游戏的效果也就不同)

    ----------------------------------------------------------------------------------------------------------------------------------------------------------------

    Montage Properties(动画剪辑的特性)

    The following is a breakdown of the AnimMontage asset properties. These are available in Persona when looking at a Montage, and can also be accessed by right-clicking on a Montage within the Content Browser and choosing Properties from the context menu.

    下面图片是动画剪辑自身属性的分类展示。这些属性可以在打开角色视图(注:包括骨骼,Mesh,动作等文件)的动画剪辑中看到,当然你也可以在文件浏览器中通过右击一个动画剪辑文件并选择属性菜单来查看。

    MontageProperties.png

    Montage Properties(动画剪辑属性)

    Montage

    Blend In Time

    混合切入时间

    This is an amount of time at the beginning of Montage playback during which the character will blend in from its current pose.

    这是在Montage动画开始播放时,从当前动作状态过度到新动作所消耗的时间。(注:该时间为0,则没有过度;时间越大,新动作越不明显,当超过一定值时,几乎没有变化)

    Blend Out Time

    混合切出时间

    This is an amount of time at the end of Montage playback during which the character will blend back to its original pose.

    这是在Montage动画结束播放前,动作切换到原始状态所消耗的时间。

    Root Motion(根节点动作)

    Enable Root Motion Translation

    可以编辑根节点位移变换

    Enables handling of root motion translation, cancelling out any translation applied to the root so that it can then be applied back to the character's collision capsule. Please see 根骨骼运动 for more details.

    (勾选的话)可以编辑处理根节点的动作(位移)变换,(不勾选)取消任何对根节点的位移操作。这样就可以决定是否使人物使用角色本身的碰撞胶囊。想查看更多细节请参考根骨骼运动

    Enable Root Motion Rotation

    可以编辑根节点的旋转变换

    Enables handling of root motion rotation, cancelling out any rotation applied to the root so that it can then be applied back to the character's collision capsule. Please see 根骨骼运动 for more details.

    勾选的话可以编辑处理根节点的动作(角度)变换,(不勾选)取消任何对根节点的旋转操作。这样就可以决定是否使人物使用角色本身的碰撞胶囊。想查看更多细节请参考根骨骼运动

    Additive Settings(附加设置)

    Preview Base Pose

    预览基本动作

    Sets a base preview pose used for additive Blend Spaces.

    为附加的动作混合窗口设置一个基本动作的预览。(注:其实就是你这个Montage的一个动画预览,默认的为空显示的就是你编辑后的结果,所以一般不用设置)

    Animation(动画)

    Rate Scale

    比率

    A multiplier value for how fast the Montage will play back. Default is 1.0.

    一个因数值来表示Montage动画播放的速率,默认为1。

    Skeleton

    骨骼

    Contains the skeleton associated with this Montage. Cannot be changed in the editor

    .包含了和Montage动画相关的骨骼。在编辑器里面不能修改

    Montage UI(动画剪辑系统UI)

    When looking at a Montage in Persona, it is useful to know what each area is and what it does:

    当我们在角色窗口查看动画剪辑系统时,很有必要去知道每一块区域是做什么的:

    MontageUI.png

    1. Montage Area                剪辑Montage)区域

    2. Sections Area                片段(Section)区域

    3. Element Timing Area   元素时间(Element Timing)区域(当前中文文档也就是4.7版本以前没有该项)

    4. Notifies Area                  通知(Notifies)区域

    5. Curves Area                   曲线(Curves)区域


    Montage Area(剪辑区域)

    The Montage Area breaks down like so:

    动画剪辑区域分解示意图如下:(后面会解释为什么只有两个部分)

    MontageArea.png

    1. Section Track - Shows any Sections that have been defined for this Montage. Sections can be dragged to different positions along the timeline with the left mouse button.

    2. Slot Track - Shows the current Slot, along with the Slot name on the right. This Slot may be filled with as many animations as you desire; they will be played back in order. Notice that multiple animations will have alternating positions in the Slot Track - top, then bottom, then top again, and so on. This is to help you differentiate between different animations.

    3. Branch Point Track - Shows any Branch Points that have been defined for this Montage. Branch Points can be dragged to different positions along the timeline with the left mouse button.

    You may have as many Slot Tracks as you like within a single Montage, each with their own name and containing their own unique animations. However, you may only have one Section Track and one Branch Point track for each Montage.

    1. 片段轨道 - 显示所有为Montage动画所定义的动画片段。这些片段可以用鼠标左键拖到时间轴的任意位置上。
    2. 插槽轨道 - 显示当前的插槽并且在插槽右边显示其名称。这个插槽轨道可以按你的意愿插入任意数量的动画。他们会按照时间轴的顺序播放。需要注意不同的动画需要交替的出现在插槽轨迹上,就是按照第一个在上,第二个在下,第三个又在上的顺序交替。这会帮助你区分不同的动画片段。
    3. 分支点轨道 - 显示所有为Montage动画定义的分支点。分支点可以被鼠标左键拖到时间轴上的任意位置。(已经移至Notifier的一个属性选项里面)
                        你会有你所期望的任意数量的插槽轨道,每一个都有自己的名字并且包含自己特有的动画。但是,在一个Montage动画里面你只能拥有一个片段(section)轨道和一个分支点轨道。

    (注:这里很多朋友可能有疑问,因为我们根本找不到Branch Point Track这个轨道。我在4.8.3版本里面就已经没有这个轨道了,而在比较早的版本(可能是4.5以前)是有的。原因是中文的官方文档没有及时更新,而英文的版本已经去除了Branch Point Track轨道,但是Branch Point的功能仍然是有的,在添加Notifier时,这个消息的Event属性——Montage Tick Type里可以选择到Branch,所以想使用这个功能的朋友可以使用Notifies来代替,并改变这个属性。

    关于一般的Notifier与Branch的区别:Notifier是异步的,不能很及时的响应,想要在某一帧的上直接改变动作不能使用Notifier。这时候可以使用Branch来及时的响应。

    --------------------------------------------------------------------------------------------------------------------------------------------------------------------

    Sections(片段)

    Montage Sections provide a way to break a Slot up into multiple portions of animation. Each Section has a name and location in the Slot's timeline. Using the name, you can either jump directly to a particular Section or queue it to play next, when the current segment is complete. In Blueprint, you can query the current Section, jump to a Section, or set the next Section that will play.

    It may help to think of Sections like songs on a music playlist, with Slots being the albums. Just like with many modern media players, you can choose which song will play next when the current one finishes, or just jump to the one you want to hear right now.

    Sections are created by right-clicking on the Section track and choosing New Montage Section.

    Montage动画系统的片段轨道提供了一种可以打破正常 插槽播放顺序 的方式。每一个片段有一个名字并且处于插槽时间轴的一个位置。用这个名字,你可以在当前动画部分播放完成后直接跳到一个指定的片段或队列并接着播放。在蓝图中,你可以查询当前的片段,切换到任意一个片段,或是设置下一个需要播放的片段。

    让我们打个比方,片段就像一个音乐播放列表的歌曲一样,每一个插槽轨道就是一个专辑,里面有很多的现代流行歌手的歌。当一首歌结束时,你可以选择下一首播放什么或者直接跳到你想听的那一首歌来播放。

    点击鼠标右键在片段轨道上选择新建新的剪辑片段New Montage Section就可以创建一个片段了

    --------------------------------------------------------------------------------------------------------------------------------------------------------------------

    Slots(插槽)

    Within a Montage, a Slot is just a single track that can hold any number of animations. You can name this Slot, and then blend to those specific animations by calling the Slot name. A great example is having a character with a weapon reload animation. You may have different versions of the reload for when the player is standing, crouching, and lying prone. So long as all 3 of the animations used the same timing, you could place each one within a separate Slot in your Montage; the Slots could be named StandingCrouching, and Prone. In your Animation Blueprint's AnimGraph, you can use the Slot node to determine which one you want to play based on your character's current state. When they are standing, you can use the result of the animation in the Standing Slot. When they are prone, you can see the result of the ProneSlot.

    It is an important point to keep in mind that although much of your Montage control will take place in the Animation Blueprint's Event Graph, Slots are actually handled within the Anim Graph. This is done by way of the Slot node, which simply takes in the name for a Slot. By positioning this node at a strategic point along your AnimGraph's execution, you can have multiple Montages that utilize the same Slot name.

    在动画剪辑中,插槽就是一条可以容纳无数动画的存储轨道。你可以命名每个插槽轨道,并且通过轨道的名称来调用之前选定的融合到一起的动画序列。举一个合适的例子,假设你有一个角色需要执行为武器重装弹药的动画。同一个动作可能会有很多不同的版本,比如在站立时,蹲着时,匍匐时都有所差别。只要三个动画用同样的使用同样长度的时间,你就可以在Montage系统里把他们分别放在单独的插槽轨道里。这几个轨道可以分别命名为站立,蹲下,匍匐。然后在你的动画蓝图的角色状态图(AnimGraph)中,你可以根据你人物角色的当前状态决定使用你的插槽轨道。当角色站立时,就可以使用站立的插槽轨道。当他匍匐时,就可以使用匍匐插槽轨道来播放匍匐的更换弹药的动作。

    有一点很重要,我们要知道虽然大部分的Montage动画控制会在蓝图的事件图中进行,但是插槽部分却是被AnimGraph所控制的。这部分功能通过带有名字的插槽节点来控制实现。将一个插槽节点放在一个有战略意义的位置上来执行,你就可以利用相同的插槽节点创造出丰富的动画剪辑效果。

    -------------------------------------------------------------------------------------------------------------------------------------------------------------------

    下面的Branch Point在4.7以后的引擎中已经去除,所以这里不再翻译了

    Branch Points

    Branch Points allow you to create events that coincide with animation playback. These Branch Point Events can be used in code or Blueprint to cause other things to happen, but specifically, Branch Points are useful for switching to other animation Sections within a Montage.

    If you are already familiar with Animation Notifies, you may notice a strong similarity between the two systems, as they both expose events that can be leveraged in script. The key difference is that Notifies are asynchronous, while Branch Points are synchronous. What this means to the end user is that Branch Points come with a much higher degree of precision for where they will take place along the animation timeline.

    High precision is important when you need to jump to a specific animation at a very precise moment in time. While you could use a Notify to do the same job, the asynchronous nature of Notifies means that the Notify Event could be fired at the incorrect animation frame, which can lead to hitches and jumps in your motion.

    Due to their synchronous nature and the precision resulting from it, Branch Points are more performance expensive than Notifies. You should only use them when an event must be fired at a precise moment along the animation timeline, such as jumping directly to another animation that matches up frame-to-frame. If being off by a frame - or some percentage of one - is not important, you should use Notifies instead.

    -------------------------------------------------------------------------------------------------------------------------------------------------------------------

    Sections Area(片段区域)

    The Sections area is where you can establish relationships between the Sections you define in the Montage Area. For instance, you may want a certain Section of animation - or group of Sections - to play in a specific sequence, or even loop.

    在片段区域,你可以根据Montage系统区域定义不同的片段来创建不同的剪辑动画关系。例如,你可能需要一个特定的片段动画,或是一组动画来按顺序或者循环播放。

    SectionsArea.png

    1. Create Default and Clear Buttons - Create Default creates default associations between all Sections, stringing them together one after the other. Clear wipes out all associations.

    2. Section Buttons - In this area, you will see a button for each of the Sections you define in the Montage area. By choosing an existing Section and then clicking the one of these buttons, you associate the Section for that button with the selected track. For instance, in the image above, we have associated Swing2 with Swing1. The order actually goes Swing1Swing2, and then Swing1 again, which causes a loop. See the Looping section below for details.

    3. Section Association Tracks - This is where you can visualize and preview the relationships between animation Sections. By clicking on the Preview buttons, you can see the result of each individual track, or click the Preview All Sections button and see all Sections play back one after the other.


    1. 创建默认清除按钮 - 创建默认按钮创建按照所有片段的默认顺序接连的将各个动画片段排成一个序列。清除键则将他们完全分开,不在有任何联系。
    2. 片段按钮 - 这这个区域,你将会看到你在剪辑区域定义的所有片段。选择下面第3部分的一个轨道上存在的片度并接着点击区域2其中的一个按钮,你就可以把区域2的片段添加到下面的轨道上。例如,在上面的图片里,我们把Swing2连接到Swing1上。这个顺序就变成了Swing1,Swing2,Swing1,Swing2这样循环的播放下去。关于循环的细节,下面一段会继续阐述。
    3. 片段关系逻辑轨道 - 在这个区域,你可以看到并预览所有动画片段的执行关系。点击预览按钮,你就可以看到每个独立轨道的的播放效果。也点击预览所有,查看所有片段的循环播放。
       (注:暂时我的理解是,对于区域3的每一个section,只有第一条的轨道才是角色真正运行的动画序列。上面的Montage区域目的就是为了给每一个动作定义一个section从而可以在Section区域自由的控制Montage的播放顺序。)

    -------------------------------------------------------------------------------------------------------------------------------------------------------------------


    Looping(循环)

    Sections can be set up to loop indefinitely, which is extremely useful for any action that you need to repeat. By associating the same Section more than once in a Section Association Track, you cause that association to run in a loop. The section will turn blue to show this. As an example, consider an animation in which a character is reloading a shotgun, one shell at a time. You could take just the section in which the character inserts a shell, and loop it. Then, by using Notifies, you could create Notify Events in Blueprint that increment the ammo count each time the animation plays through. Once that count reaches a set number (full ammo), you could then switch to an animation of the character closing the receiver and returning to idle.

    片段可以被设置为无限循环的播放,这无疑对你想要重复的动作是非常有用的。通过在轨道上把同一个片段添加两次,你就可以得到一个循环。如果进入循环状态,这个动画片段的颜色就会变成蓝色。举个例子,假设一个角色正在给枪或者炮弹装填弹药。你可以只选择这一动画部分插入到装弹的状态并且循环播放。之后,通过动画通知功能(下面有讲解),你可以在蓝图中创建响应信息的事件在每次装弹时增加这个弹药的数量并多次播放这个动作。一旦弹药到达一定数量(满弹药),你就能停止接收消息切换到平时的待机状态。

    -------------------------------------------------------------------------------------------------------------------------------------------------------------------


    Notifies Area(动画通知区域)

    NotifiesArea.png

    动画通知(简称AnimNotifies或通知)使得动画相关的程序员可以设置在动画序列的特定点处发生的事件。通知通常用于这样的特效,比如走动时的脚步声、跑动动画或在动画中产生一个粒子特效。然而,它有很多种不同的用途,因为您可以使用自定义的通知类型来扩展该系统,从而满足任何类型游戏的需求。

    For more information, see 动画通知 (通知).

    Curves Area

    CurvesArea.png

    曲线提供了在动画正在播放过程中改变材质参数或顶点变形目标的方法。 其工作流程非常简单,只需要您简单地指定您要修改的资源(一个材质或顶点变形目标),相应地命名该曲线,然后调整动画播放期间的关键帧的值。

    For more information, see 动画曲线.


    Montage Practical Example(动画剪辑系统使用实例)

    In this example, we want to have a character that can freely run in all directions, with an attack animation that only plays on the upper body. This attack will have multiple animations that could take place during its course. This is a perfect way to show the assembly of a Montage, as well as how to control it in the Event Graph and blend into it within the AnimGraph.

    在这个例子中,我们想创建一个可以向各个方向自由移动的角色,这个角色还可以在上半身播放一个攻击的动画。这个攻击动作包含多个可以在执行过程中播放的动画。这是一个能非常完美地展现Montage动画系统功能的方式,同时也可以展示如何在事件图控制它,以及如何在AnimGraph中将Montage与其他动画混合播放。

    -------------------------------------------------------------------------------------------------------------------------------------------------------------------


    However, there are few things we have set up in advance:

    • We already have a State Machine defining locomotion. This is just like the one used in the Third Person Project Template.

    • We have several animations provided by an artist that we would like to string together to make the Montage.

    • We have created a Character Blueprint Class that we can get input information from.

      • For this example: an IsAttacking Boolean that is set to TRUE when the Left Mouse Button is pressed and set to FALSE when it is  released.

    不过,在开始之前我们要提前做好几点准备工作:

    • 已经建立了一个行动的状态机。这个状态机与第三人称游戏模板工程的状态机一样。
    • 已经有了美术人士提供的相关的可以加入Montage系统的动画素材。(注:UE4一般使用FBX文件)
    • 已经创建了角色蓝图来接收输入信息。 
                  ○ 例如:创建一个名为是否攻击(ISAttacking)的布尔变量,当点击鼠标左键时设置为哦true,松开时设置为false。


    CharacterBlueprint.png

    Creating the Montage(创建动画剪辑)

    Making a Montage is as easy as right-clicking in the Content Browser and choosing Animation > Animation Montage. You can also right-click on an existing Animation Sequence and choose Create Montage from the context menu. This will automatically create a new Montage with the selected AnimSequence already set up in the default Slot.

    创建一个Montage动画系统很容易。只要在内容浏览器右键鼠标选择 动画->动画剪辑Animation > Animation Montage)就创建成功了。你也可以在内容菜单里一个存在的动画序列上右键鼠标并选择创建Montage动画剪辑(Create Montage。这样就会以这个动画作为默认的动画插槽创建一个新的Montage动画剪辑。

    MakeMontage.png

    Montage Setup(动画剪辑的创建)

    Our first order of business was to name our Slot. We only need one in this Montage, and since we want our attack to only affect the upper body, the name Upper Body seemed perfect. We then drag/dropped the animations we would need into this slot. The animations we have do the following:

    • Right-to-left hammer swing

    • Left-to-right hammer swing

    • Go from the end of the right-to-left swing back to Idle

    • Go from the end of the left-to-right swing back to Idle

    The two swinging animations both end on the same pose as the other begins. This means that the two animations can play back to back in a loop and the character will seamlessly swing the hammer back and forth.

    While order is not extremely important, having the first two animations at the beginning and back to back will simplify things later.


    我们第一件要做的事情就是给插槽(Slot)命名。在一个动画剪辑中,一般只需要有一个插槽,而且既然我们想让这个Montage只影响角色的上半身,不妨就把这个插槽命名为UpperBody吧。之后,把我们需要的动画拖到这个插槽里面。需要的动画有下面4个:

    • 从右向左挥动锤子
    • 从左向右挥动锤子
    • 从右向左挥动锤子结束动作(衔接到待机状态)

    • 从左向右挥动锤子结束动作(衔接到待机状态)

           这两个挥动的动画会在一个结束时播放另一个。这就意味着这两个动画可以循环交替的播放下去,看起来就行角色在不停的反复进行挥动锤子

    其实顺序并不是很重要,不过使前两个动画在序列的开始并挨在一起就会让后面的操作简单不少。

    MontageSetup.png

    Section Creation(片段创建)

    Our next step is to section out the animations in our Montage so that we can query them and call them up when needed in our Blueprint code. This is as easy as right-clicking and choosing Add New Montage Section while clicking on the Section Track at the top of the Montage Area.

    We used fairly straightforward names for each Section. Note that we replaced the Default section that came along with the Montage (made a new one and deleted the Default by right-clicking and choosing Delete Montage Section). You can drag these Sections along the Section Track if you need to, and you will notice that they snap a bit at the boundary between two animation segments when you release the mouse. Use this to your advantage.

    下一步操作就是给每个动画制作片段,这样我们在蓝图或代码中就可以方便的查询与使用他们。步骤也很简单,在片段那条轨道上(Montage区域的最上面)右键鼠标选择添加Montage片段(Add New Montage Section)。

    我们直接给每个片段命名。注意要把之前创建Montage的默认片段给替换掉。(创建一个新的片段并且右击默认片段选择删除片段)你可以在轨道上随意的拖动这些片段而且如果你在两个动画衔的接位置松开,他们会自动对其。好好利用这点。

    AddNewSections.png

    Defining Section Relationships(给片段确定关系)

    Now that our Sections are created, we can now define any special relationships between them using the Sections Area. For instance, we can define a relationship between the Swing1 and Swing2 sections so that they play back to back in a loop. This is very useful for us. We start by clicking the Clear button to wipe out any default relationships. Then it is just a matter of selecting the track with Swing1 in it, and clicking the green button labeled Swing2 near the top of the Sections Area. This will remove the Swing2 track and add Swing2 to the Swing1 track.

    一旦我们的片段都已经创建好了,我们就可以在片段区域给他们随意的定义关系。比如,我们可以定义一个联系让Swing1和Swing2循环交替的播放。这对我们来说非常有用。点击清除按钮可以擦除我们定义的任何关系。操作很简单,就是在轨道上点击Swing1,然后在片段顶部区域点击绿色的Swing2按钮。这样就会把Swing2轨道移除,并把Swing2片段移动到Swing1轨道的后面。

    Swing2Track.png

    If we repeat the process, clicking the new Swing2 segment and then clicking the Swing1 button, the system detects that you are creating a loop and the track turns blue. This means that the Swing1 and Swing2 segments are considered a looping Section. They will play back to back, repeating indefinitely.

    如果想重复某一个动作,点击第一个轨道上刚刚创建的Swing2片段然后在点击区域上方的Swing1按钮,系统就会认为你正在创建一个循环,并且这个循环的片段部分就会变成蓝色。这就意味着Swing1和Swing2片段想成为一个循环。他们就会一直的重复播放下去。

    LoopingTracks.png

    -------------------------------------------------------------------------------------------------------------------------------------------------------------------

    下面的Branch Point在4.7以后的引擎中已经去除,所以这里不再翻译了

    Setting Up Branch Points

    We will now set up some Branch Points to test whether to continue with the loop or jump to one of two possible endings for our attack animation. All we have to do is right-click in the Branch Point Track and choose New Branch Point. We chose the names Swing_1_Endand Swing_2_End for our Branch Points. We also zoomed very closely in with the mouse wheel to make sure that each one fires right at the last possible moment of its corresponding section. This means it is placed very slightly to the left of the border between the two.

    BranchPointsSetUp.png

    A similar system could be set up in which you use Notifies instead of Branch Points, but they would need to fire a little earlier along the timeline, and your Animation Blueprint Event Graph would be queuing the appropriate ending animation using the Montage Set Next Section node, rather than doing a direct switch with the Montage Jump to Section node, as we will be doing. Doing it with Notifies would be slightly cheaper on performance, as Notifies are asynchronous. Our example is academic, but we wanted to make sure to mention the other method, as well.

    -------------------------------------------------------------------------------------------------------------------------------------------------------------------


    Setting Up the AnimGraph(设置动画图)

    At this point, our Montage is all set up. We now need to establish our AnimGraph so that it can read in the result of our Montage. This is a pretty simple process, but it does cause us to have to think carefully about how we proceed. Our AnimGraph starts off looking something like this, where we are only seeing the result of our State Machine:

    现在,我们的Montage动画已经建立好了。我们接下来需要创建我们动画图(AnimGraph)好让他去把Montage动画融入到我们的这个人物的动作里。这一步很简单,但是他会提醒我们去仔细思考一下我们的流程是什么样的。动画图一开始的效果是下图所示的样子,我们只能看到状态机所展示的结果。

    StateMachineResult.png

    We only want the Montage to play back from the Spine_01 bone (the waist) up, so we will be using a Layered Blend per Bone node. We add a Blend Pose to it set the weight to 1. We also associate this Blend Pose with Spine_01 in the properties for the node. We then bring in a Slot node and set it to UpperBody, the name of our slot. But now we run into a problem:

    因为我们现在只想Montage动画从Spine_01骨骼(腰部)开始播放,所以需要一个名为 骨骼层混合(Layered Blend per Bone) 的节点。给混合动作0(Blend Pose 0)设置比重为1。同时我们也把混合动作设置绑定到Spine_01骨骼上。之后引入一个插槽节点并设置为UpperBody(我们之前所命名的Slot)。然而,你会发现,现在出现了一个问题:

    SlotAndBlend.png

    The Slot node needs a Source connection to fall back on once the Montage is done playing. Without it, the character will return to the T-pose from the waist up after the Montage completes. However, we cannot connect the State Machine to both the Base Pose of the Layered Blend per Bone as well as the Source for the Slot node. The solution? Use a Cache node! We can store the result of the State Machine into a Cache node, and then create Cached Pose nodes to connect to both our required inputs. This is somewhat similar to storing the result of the State Machine into a variable so you can use it in multiple places. For this example, we named the Cache LocoCache.

    一旦Montage动画执行完成,这个插槽节点需要一个动作来源来恢复之前的动作。没有这个动作来源,角色在Montage动画执行完毕后就会回到最开始的T型姿态的样子(注:就是模型最原始的无任何动作的状态)。然而,我们不能把状态机的节点同时链接到插槽节点(Slot)骨骼层混合节点(Layered Blend per Bone。那么如何解决这个问题呢?答案是使用一个缓存节点Cache )。我们可以暂时把状态机的结果存储为一个变量,这样你就可以在各个地方重复的使用了。举例来说,我们把这个节点命名为动作缓存LocoCache),按照下图的样子使用。

    CachedLocomotion.png

    Our AnimGraph is done. As soon as the UpperBody Slot node receives data from any AnimMontage (you can use any Montage, so long as it has a Slot named UpperBody), it will blend it in. As soon as it is no longer receiving data, it will fall back on the result of the State Machine.

    现在我们的动画图已经完成了。一旦UpperBody插槽节点收到了Montage动画发送的任何消息(你可以使用任何你创建的Montage,只要他有一个叫做UpperBody的插槽就可以),他就会执行混合动画。如果停止接收消息,角色就会恢复状态机里的动画状态。

    -------------------------------------------------------------------------------------------------------------------------------------------------------------------

    Setting Up the Event Graph(设置事件图)

    Our Event Graph setup is very basic. Using the Event Blueprint Update Animation node and dragging off the out pin of a Get Player Character node, we can Cast To our Character Blueprint (MyCharacter in this example) to access the variables and functions from that Blueprint (see Blueprint Communications for more info on communicating between Blueprints).

    事件图的设置非常重要。使用蓝图动画更新事件(Event Blueprint Update Animation) 节点作为开始并创建一个获取玩家角色(Get Player Character的节点,我们就可以把角色蓝图强制转换为我们自定义的角色(这里我们定义的角色名为MyCharacter)同时获取角色里面定义的变量和方法(想获取更多关于蓝图交互的信息请看Blueprint Communications章节)。

    The first thing we do is check if the IsAttacking variable from our Character Blueprint is TRUE and if it is, we then check if the Montage is already playing. If the Montage is playing, we do not want to play it again; however if it is not playing, then we play the Montage. This prevents the system from restarting the animation in the middle of playback, which would look bad.

    Dragging off the IsAttacking node which extends from the Cast To node, we see if the mouse button is still down, and if not, we jump to the appropriate ending animation, depending on which half of the loop is playing. Creating the Branch Point Events is done by right-clickingand choosing the appropriate event under Add Montage Branching Point Event.

    我们要做的第一件事接收检查一下我们角色蓝图中的IsAttacking变量是否是正确的,如果是true的话再检查一下Montage动画是否正在播放。如果是,就不需要再去播放一遍;如果没有在播放,那么就让他去播放。这样可以防止动画从Montage播放到一半的时候直接切换到开头并再次播放动画。

    EndLoopEventGraph.png

    And that is it! If we compile, we will now see that the character continues to swing as long as the mouse button is down, and performs an intelligent end animation when the mouse button is released!

    那么一切都已经搞定了。如果我们开始编译,我们就会看到角色随着鼠标按钮的按下不断的挥舞着他的锤子并且在鼠标按钮放下时播放结束动画作为衔接!


    展开全文
  • vue中文翻译拼音组件 @ alidrus / vue-simple-inline-translation (@alidrus/vue-simple-inline-translation) A Vue component that simplifies the way text is translated: by translating it inline. Vue组件可...
  • 本文是目录,每条目录有两部分内容:英文+中文(仅已翻译的有); 其英文附有原来链接;中文附有中文文章链接。 Cython - an overview Installing Cython Building Cython code Building a Cython module ...
  • 敢死队中文翻译

    千次阅读 2012-02-20 19:38:46
    1 18 00:05:01,568 --> 00:05:03,297 00:05:01,568 --> 00:05:03,297 Don't shoot me. 别开枪   2 19 00:05:03,770 --> 00:05:05,397 00:05:03,770 --> 00:05:05,397 ...00:05:05,739 -
  • Spark官方文档 - 中文翻译

    千次阅读 2016-07-06 18:16:02
    Spark官方文档 - 中文翻译
  • ØMQ中文翻译文档

    千次阅读 2019-08-26 13:48:14
    英语原文链接 翻译文档已上传到本人GitHub,目前只翻译了一部分,很多都是直译(英语一般==),欢迎一起来翻译~ 如果您需要转载,请注明出处。 ØMQ - The Guide [Table of Contents](javascript:
  • Spring Data Jpa 中文翻译文档

    千次阅读 2018-07-26 20:02:03
    Spring Data Jpa 中文翻译文档 标签(空格分隔): JPA Spring Spring Data JPA - 参考文档 Oliver Gierke Thomas Darimont Christoph Strobl Mark Paluch 杰伊布莱恩特 版本 2.1.0.M3,2018-05-17 ©2008...
  • 中文乱码 unknown column in 'where clause'

    千次阅读 2016-04-11 23:34:38
    来自:...例如,其中college为中文时,加引号不会出现乱码,不加引号会出现乱码:String hql="from JobInfo where coll
  • Kryo官方文档-中文翻译

    万次阅读 2017-05-31 20:59:32
    Kryo作为一个优秀的Java序列化方案,在网上能找到不少测评,但未见系统的中文入门或说明文档。官方文档是最好的学习文档。虽然英文不差,但啃下来毕竟没母语来的舒服。这里抽出时间做些翻译,以方便大家查阅。为阅读...
  • svn 错误 以及 中文翻译

    千次阅读 2013-09-03 09:59:28
    比较长,如何查找不方便的话,用查找“CTRL+F”吧     ...# Simplified Chinese translation for subversion package # This file is distributed under the same license as the subversion package. ...
  • kali工具中文翻译

    千次阅读 2017-02-14 09:39:56
    nc 瑞士军刀 [v1.10-41] 使用格式: nc [-参数] 主机名 端口[s] [端口] … 侦听入站: nc -l -p 端口[-参数] [主机名] [端口] 参数选项: -c shell commands as `-e’;...-e filename program to exec after conn
  • Elasticsearch Reference 5.5 中文翻译1

    千次阅读 2017-08-17 17:26:25
    Elasticsearch Reference文档的中文翻译,非外文系,希望可以给初学Elasticsearch的人带去帮助 版本5.5 开始翻译时间2017年8月14日 文档参考地址:...
  • Physics Bodies(中文翻译)—UE4官方文档

    万次阅读 2016-04-06 23:04:17
    If false, will be 'fixed' (ie kinematic) and move where it is told. 如果勾选,则实体会开启物理模拟。如果不勾选,实体将会固定住并且会移动到你所指定的位置。 Mass in KG 质量 KG为单位...
  • Python 标准库 BaseHTTPServer 中文翻译

    千次阅读 2015-07-16 14:06:00
    Python 标准库 BaseHTTPServer 中文翻译。 注意: BaseHTTPServer模块在Python3中已被合并到http.server,当转换你的资源为Python3时https://docs.python.org/2/glossary.html#term-to3“>2to3工具将自动适配导入。 ...
  • C# EasyHook2.5 中文翻译

    千次阅读 2011-09-09 02:43:08
    在网上找到一遍中英文的教程(但是很多地方中文翻译好),现在也正需要学习它,看英文资料有时候会更实在,所以边学边继续帮忙翻译吧。由于本人水平有限,如果翻译有问题请及时指出以方便其他英文不太好的朋友学习...
  • PHP ADODB 1.99版手册中文翻译

    千次阅读 2007-08-10 16:02:00
    PHP ADODB 1.99版手册中文翻译 感谢记事 PHP ADODB 1.99版手册中文翻译 翻译作者:Tripc 修正作者:heiye
  • Selenium Documentation 中文翻译

    千次阅读 2011-08-02 15:39:09
    Selenium 用户手册 Translator: Chip Date: 2011-08-01 INDEX 1 __init__(self, host, port, browserStartCommand,
  • rfc-3227中文翻译

    千次阅读 2006-07-20 21:07:00
    译者:孙达(ntbbc@hotmail.com)发布:networkmanager.blogchina.com译文发布时间:2004-12-8版权:本中文翻译文档版权归作者所有。可以用于非商业用途自由转载,但必须保留 本文档的翻译及版权信息。 Network ...
  • Pointnet++中文翻译

    千次阅读 多人点赞 2018-12-26 17:24:05
    where , j=1,…,C     4.实验 数据集我们评估四个数据集,从2D对象(MNIST [11]),3D对象(ModelNet40 [31]刚性对象,SHREC15 [12]非刚性对象)到真实3D场景(ScanNet [5])。 对象分类通过准确性进行...
  • Learning Spark: Lightning-Fast Big Data Analysis 中文翻译行为纯属个人对于Spark的兴趣,仅供学习。 如果我的翻译行为侵犯您的版权,请您告知,我将停止对此书的开源翻译。 Translation the book of Learning ...
  • 链接:https://github.com/code98/Swift3.0Swift3.0Swift 3.0 Preview 1更新内容中文翻译 http://www.liangkun.info前言随着WWDC 2016的召开,苹果正式发布了Swift 3.0 Preview 1,这是苹果Swift3语言的首个稳定...
  • tcpdf开发文档(中文翻译版)

    千次阅读 2018-07-18 18:34:09
    这个是英文翻译版,我看过作者的文档其实不太友善或者不方便阅读,不如wiki方便 后面补充一些,结构性文档翻译 这是一部官方网站文档,剩余大部分都是开发的时候和网络总结来的 项目官网:https://tcpdf.org/ ...
  • $subquery = (new Query) ->select([new Expression(1)]) ->from('tree') ->where(['parent_id' => 1, 'id' => new Expression('tree.parent_id']));...where(['or', 'parent_id = 1', $subquery])

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 17,929
精华内容 7,171
关键字:

where的中文翻译