标签:翻译

【译者注】因为时间原因,这篇论文没有翻译完,感觉有点吃力。有些句子自己也没有太理解。如果有大牛理解文章中code-path和doorway的意思,请在评论里不吝赐教。

【译者注】
Batching是指,将多个日志合并成单个消息进行发送;Batching可以有效的降低消息粒度带来的额外损耗,提升吞吐。但是过大Batching容易造成单请求的延迟过大,导致并发请求数过高,继而影响了吞吐和请求延迟。

【翻译开始】

Roy Friedman 计算机科学系,以色列理工学院,海法,以色列
Erez Hadad 分布式计算系统组,IBM海法研究实验室,海法,以色列

【摘要】

本文针对镜像服务器提出了两种新颖的通用自适应消息合并方案。这两种方案都不用考虑底层通讯协议。这两种方案可以根据当前通讯负载实时自动调整消息合并级别。系统不需要明确的监控与校准。另外,本文还给出了详细的性能测试结果。

第一章 简介
大多数发送消息的开销都与消息的大小没有关系。举例来说,网络(或者中间件)协议栈的报文头,触发与执行系统调用的开销,在硬件级别争取使用网络的机会。

同样的,有一些可计算的处理消息的开销,无论是在物理层、网络层、传输层、会话层或是应用层。分开来算,他们每一层的开销都是极小的。可是一旦将它们合起来,他们的开销大到无法忽略。另外,即使这些开销造成的延迟产生的影响好像是是可接受的,但是当系统负载达到吞吐量最大值,这些影响对系统性能产生坏作用。举个具体的例子来说,处理单条消息的时间是1ms,那么系统每秒发送的消息不能超过1000条(单核条件下)。类似的,如果一个应用消息体50字节,消息头100字节,那么网络带宽至少有三分之二浪费在消息头上,而不是消息体上。将多条短消息合并为一条长消息会将每条消息的开销进行分摊,因此可以增加系统带宽。所以,这种技术现在在基于网络的应用中非常常见。

应用批消息合并的一个重要问题就是怎么决定什么时候将消息合并。要取得一定的权衡就要考虑:平衡相对于单条消息的带宽增益、获得一个良好的网络与CPU使用率。意思就是,为了增加带宽,我们希望合并尽量多的消息到一起。可是为了发送一个较大的消息,我们需要将第一条消息延迟相当长的时间。同样的,如果应用产生消息的速度比较慢,合并进程会一直等待足够的消息来进行合并,网络与CPU可能会空闲下来。

一些批消息合并模式比较通用,但是一般不考虑底层通讯协议和应用的特殊特征。另外一些比较专用,意味着他们什么时候合并消息的决定基于操作环境的特殊情况。很清楚地看到,通用模式的好处就是提供了更好的模块性和更松的耦合性,也就是说符合模块化设计原则。但是,正是由于这个原因,通用模式可能达不到专用模式的使用效果。

很大程度上来说,已有的通用批交易合并模式可分为两类:基于数量的和基于时间的。基于数量的模式,仅当应用消息的数量积累到一定数值(或者消息的大小达到一个限额)后,合并后的消息才被发送。再说基于时间的合并模式,合并后的消息周期性被发送,当前一批被发送后,打包合并所有积累的消息。

基于数量的合并模式问题在于当应用产生的消息量比较少的时候,这种模式并不能增加吞吐量。同时系统具有足够的CPU和网络带宽。更糟糕的是,因为消息产生的慢,合并延迟会变得非常高。事实上,如果应用产生的数据都小于合并的阈值,消息合并也不保证能完成。

基于时间的合并模式有类似的问题。如果合并超时时间设置的过高,消息延迟也会变大。同时如果通讯比较少,并不能充分利用系统吞吐量。从另外一个方面讲,如果将超时时间设置过短,每次仅有少量消息被合并。

当然,可以结合基于数量的模式与基于时间的模式,也就是说,无论是消息数量积累够了,还是到超时时间了,哪个条件先达到就发送已合并的消息。可是,这样依然无法完全解决上面讨论的问题。一种明显的补偿方式,引入一种能根据实际通讯模式进行动态自适应的合并参数。确实有一些文章提出了自适应合并。采用的方法是利用一个组件不停地监控系统的通讯状况,调整消息合并数量阈值和消息合并超时时间来应对探针的检测到的行为。

监控方式的解决方案存在一些问题:第一,监控行为本身增加了系统负载。第二,都是基于过去的情况调整合并参数,所以在通讯情况发生改变与合并线程做出反应之间存在一定延迟。如果通讯状况频繁发生改变,这种问题会更突出。因为基于监控的解决方案总是在实际的通讯状况之前落后一段时间。

在本文中我们提出了两种新颖的通用的自适应合并原理,别名***adaptive batching***(AB)和***timed adaptive batching***(TAB),他们能自动并且及时对通讯模式进行调整合并级别,不需要任何监控程序。这些模式是通用的,在于他们并不关心任何底层通讯协议,也不关心应用产生消息的速度。但是,两种模式针对复制服务器(或类似的分布式应用),也就是一个服务器必须广播每一个消息给所有其他的服务器。此外,对于AB模型来说,我们也假设重复的请求是由多个并发线程产生的(但是TAB模型不需要)。

我们还给出了两种模式下的详细性能测试,并且和基于数量的合并模式、基于时间的合并模式惊醒了对比。测试与对比是在FTS环境下进行了,FTS是我们开发一歌复制服务解决方案。

第二章 自适应合并
我们的自适应合并解决方案面向复制服务器及类似的分布式应用。通常我们假设有一些请求消息需要广播的模型。每一个请求都由一个单独的线程发起。每一个这样的线程先执行一些其他代码,比如创建或者准备发起求求,接下来调用cast()方法,也就是将当前请求加到当前合并消息中的原语。跟着合并进程细节后面,一个合并并发送的事件被不时地触发,触发发送并且重置当前批消息的动作。正如我们稍后介绍的,对多线程应用的假设只是适用于AB模型,不适用于TAB模型,TAB模型是真正的通用模型。

2.1 简单的自适应合并
正如图1表示的那样,AB程序是这么运行的:每一个线程在调用cast()函数前都执行一段公共代码。这段代码路径的一部分终止于cast()数,我们叫他doorway。在doorway的开始部分entry code用来注册一个在doorway内部执行的线程,例如,增加doorway的计数器。类似的,exit code用来注销执行的线程,比如减少doorway计数器。AB模型这样使用doorway:将doorway entry code植入cast()调用之前的一些位置。cast()函数本身作为exit code。如果一个线程正在执行cast,在注销自身并且将自己的请求加到合并消息之后,如果发现没有其他线程也在doorway中,那么这个线程就会触发一个发送事件。

AB模型的直观感受是,仅当多个请求满足cast原语的“紧挨着”特征,他们才应该被包含在同一个批消息中。意思就是这些线程在调用cast的时候,他们的请求时间挨的非常近。doorway就像一个天然的近距离传感器:一个线程穿过doorway的时间要求就是一个超时阈值。一段时间之内没有其他线程进入doorway,这一批消息就被打包并发送。因为可以说接下来的线程所发送的消息离加入当前这一批的消息中还太远。doorway的长度可用来控制程序的敏感度:长doorway比短doorway产生更长的消息,在低客户端负载的时候。因为这样就变得另外一个线程尽量在当前线程退出doorway前进入doorway。注意,自适应算法的本质可支持任何的doorway长度,正如后面我们会阐述的。

2.2 TAB模型
AB模型有一些缺点。第一,这种模式不能找到一种通用的代码路径作为doorway。一种足够长的通用代码路径不如部署多种具有同样entry/exit,不同code-lenth的程序。另外,AB模型需求仔细的代码分析和代码修正,来确定各种线程确实经过了entry/exit code。第二,AB doorway的长度以粗糙的指令粒度进行计算,导致很难精确地计算长度,因为它既是代码也是平台相关的。第三,doorway的长度受code-path长度的制约。最后,实现AB模型需要多线程处理模式,因为doorway需要探测独立执行的上下文的增长。

以上问题都被另外一种叫做TAB的模型解决了。TAB和AB最关键的不同点在于TAB使用了一个定时器而不是code-path作为doorway.这个定时器在一个线程想要调用cast的时候进行重置(再次说明应用级别的cast方法仅仅是线程想要广播消息的一个指示,并不是真正发送消息)。如果定时器超时了,这一批合并的消息就会被真正的发送出去(这种方式和AB中一个线程离开了doorway并且没有其他线程在doorway中的方式类似)。

有趣的是,AB模型允许当前批最后一个线程到来并且没有任何其他线程在doorway中时立即发送当前批消息。在TAB模型中,从另一个方面来看,最后一个线程之后计时器还有等待一段时间,从而迫使一个最小的非零额外延迟,即使一个批消息中只有一个消息。但是,TAB计时器允许定义一个实现无关的doorway长度。最后,不像AB模型,基于计时器的实现也能用来单线程基于事件的情形。

请注意TAB模式也明显的不同于基于超时的模式,即使他们都用计时器出发一个发送消息的动作。基于超时的模式发送消息的频率是固定的,无论消息产生的速率。这样能保证消息发送的进度但是同样会引入前面所说的程序僵化的问题。TAB的定时器,根据doorway的时长参数,只有当后面的消息离得足够远时候,才将前面的消息进行打包发送。这样,TAB适配消息发生速度与合并发送速度,但是也仅仅提供一定概率的进度保证,正如第六章阐述的那样。

 

 

我的翻译 技术杂谈

两军问题是计算机领域的一个思想实验,用来阐述在一个不可靠的通信链路上试图通过通信以达成一致是存在缺陷的和困难的。这个问题和更有名的“拜占庭将军问题”有关(译者注:拜占庭将军问题很早就被提出,但是没有普及,后来为了普及,采用故事的方式来说明问题,并命名为拜占庭将军问题),并且经常出现在计算机网络课程的开头(特别是由于解释传输控制协议中的TCP协议并不能保证通信两端状态的一致性)。不过两军问题适用于任何有可能通信失败情况下的两点通信。在认知逻辑上一个重要概念是,两军问题强调了常识的重要性。也有些学者称之为“两军悖论”、“两军难题”、“协同攻击问题“等。两军问题是在计算机通信领域首个被证明无解的问题(译者注:据说量子通信可能会解决此问题),由此也可推论出,随机通信失败条件下的“拜占庭将军问题”也同样无解。

[定义]

两支军队,分别由两个将军领导,正在准备攻击一个坚固的城市。两支军队都驻扎在城市旁边的两个不同的山谷里。两军之间隔着第三个山谷,两个将军想要通讯的唯一方法就是穿过第三个山谷传送信件。问题是,第三个山谷被城市的守卫军占据,并且经此传送的信件可能会被守卫军截获。

虽然两个将军商量好要同时对城市发起攻击,但是他们没有约定特定的攻击时间。为了保证取胜,他们必须同时发起攻击,否则任何单独发起攻击的军队都有可能全军覆没。他们必须互相通信来决定一个同时攻击时间,并且同意在那个时间发起攻击。两个将军彼此之间要知道另一个将军知道自己同意了作战计划。(译者注:A同意了作战计划,A将同意作战计划的信发给B,A将军要知道:B知道了A同意了作战计划。)因为返回来的信件和送出去的信件一样容易丢失,未来大量的消息必须保持一致性。

这个思想实验致力于考虑两军怎么做才能达成一致。在最简单的情况下,其中一个将军作为领导人,决定着发起攻击的时间,他必须将这个时间准确无误地通知另外一个将军。现在的问题是提出一种两个将军可以使用的算法。这个算法包含发送和接收处理消息,并正确地做出决定和推断:

没问题,我们会在约定的时间同时发起攻击。

考虑到两个将军达成同时攻击的约定非常简单(例如,每一个成功发出去的信件,必须有一个成功的返回)。两军问题的微妙之处在于,对于上面的情形,不可能设计出一种能安全使用的算法。

220px-2-generals-svg

军队位置图。A1和A2军队需要通信,但是他们的信息有可能被B军队拦截。

 

[问题描述]

A将军可以先发送一个消息:八月4日9点发起攻击。但是,一旦消息发送出去,A将军并不知道B是否收到了这个消息。这种不确定性使得A将军攻击之前非常犹豫,因为有独自发起攻击的危险。

为了让A将军放心,B将军可能要发送一个确认的返回信息给A将军:“我收到了你消息,我会在八月4日9点发起攻击”。可是,这个给A将军的确认消息也面临着被守卫军截获的可能,B将军也犹豫了,如果A将军没有收到确认信息,那么A将军很有可能停止此次攻击。

[证明]

带有特定消息数量的确定性协议。

因为协议是确定性的的,假设有一个固定数量消息的队列,一些消息成功发送了,另一些失败了。假设两个将军有一个明确的攻击目标。

考虑最后一条消息成功送达。如果最后一条消息没有成功送达,至少有一个将军(很有可能是接收这条消息的将军)估计会不进行攻击。从最后一条消息发送者的角度出发,已发送的和已送达的消息队列顺序和预想的一致,并且包含所有已发送的消息。

因为协议是确定性的,最后一个发送消息的将军依然决定发起攻击。这样会形成如下情形:这个协议让一个将军发起攻击,另一个将军不发起攻击。这个情形与这个协议能解决两军问题的假设相矛盾。

不确定性和变长协议

一个带有变长消息的不确定性协议就像一个有限的森林,每个叶子或者分支(节点)代表一个被发现的相当于特定点的实例。

森林的根节点标记着第一条合适的消息。由根节点衍生出来的分支节点标记着合适的下一条消息。叶子节点代表发送了最后一条消息的实例。在发送任何消息之前,这个协议就是一棵空树。

假设有一个不确定性协议可以解决两军问题。那么,根据之前确定性协议的场景和分析,可以从一棵树去掉所有叶子节点,得到另外一棵树。也就是说,确定性协议一定也可以解决两军问题。

因为不确定性协议是有限的,由此可推断一棵代表空树的协议,也可以解决两军问题。很显然这是扯淡。所以不存在一个不确定性协议可以解决两军问题。

[工程方法]

一个解决两军问题实际可行的办法就是接受而非试图去消除通信信道的不可靠性,但是要将这种不可靠性降低到可以接受的程度。例如,A将军可以送出100个信使,并预期所有信使被抓的可能性是极低的。用了这种方法,A将军无论如何都会发起攻击,B将军只要收到一个信使的信,也会发起攻击。

一个类似的方法是,A将军发起一连串消息,B将军对每一个消息都返回一个应答消息。两个将军对每个返回的消息都感觉是充分的。

但是正如证明里看到的那样,无法确定攻击是协调一致的。没有一种可用的算法(比如收到4个消息)一定能防止只有一个将军发起攻击。

同样的,A将军可以给每一个发送的信息编号,从1到n。这种方法可以让B将军了解信道的可靠性,并且发送适当数量的返回信息来保证至少有一条信息会被收到。如果这个信道是可靠的,一条消息足够了,其他的消息都没什么用了。最后一条消息和第一条消息一样容易丢失。

假设每发送一个消息并被拦截时,将军将会牺牲一批士兵,那么我们可以设计这样一种算法,使得用最少的消息通信换取协同攻击的最大化确认。为了达到这个目的,发送方使用停止发送信息的方式表示已收到至少一次确认信息并承诺发起攻击。假设每个消息通过危险区需要1分钟,发送方收到确认信息后沉默200分钟,这样可以既不用牺牲更多的士兵又能达到高可靠的协同可信度。也就是说,只有当接收方没有收到攻击时间时发送方才会继续发送消息。发送方沉默200分钟后,接收方将得出以下结论:一种可能是连续200个消息都被敌方截获(显然概率极低);另一种可能是对方已收到我的确认信息也相信我将发起攻击,对方也将发动攻击。

[历史]

两军问题及其无解性证明1975年被E. A. Akkoyunlu、K. Ekanadham和R. V. Huber首次提出。发表在《网络通信设计的约束与权衡》一文中。它在73页的开头用来描述两个匪徒团伙之间的通信。

1978年,Jim Gray在《数据库操作系统笔记》的465页,将这个问题命名为“两军问题”。这个引用被普遍地认为是最早的两军问题的定义和无解证明,但是正如上一段说的,其实他们早就被发表了。

译者注:

翻译原文是维基百科条目:Two General’s Problem

https://en.wikipedia.org/wiki/Two_Generals%27_Problem

本人水平有限,有问题的地方,欢迎大家批评指正。

我的翻译 技术杂谈