【翻译】Adaptive Batching for Replicated Servers

【译者注】因为时间原因,这篇论文没有翻译完,感觉有点吃力。有些句子自己也没有太理解。如果有大牛理解文章中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适配消息发生速度与合并发送速度,但是也仅仅提供一定概率的进度保证,正如第六章阐述的那样。

 

 

版权声明:除标明转载的文章外皆为原创文章
转载请注明: 转载自Liudroid的博客,作者:Liudroid
本文链接地址: 【翻译】Adaptive Batching for Replicated Servers

Be First to Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注