现在的位置: 首页 > 综合 > 正文

均衡算法

2013年10月31日 ⁄ 综合 ⁄ 共 1795字 ⁄ 字号 评论关闭

 最近公司要我写一个彩信发送程序,因为我们有多个彩信提供商提供给我们发送通道,而且每个提供商的通道质量也不同,所以在开发时就必须考虑为发送程序编写一个均衡策略,来分配各种请求,网上查了很多,发现绝大部分均衡策略都不太适合,于是决定自己制定一个策略标准。

 

首先我们看看我们有什么,现在有2个供应商提供给我们发送彩消息的通道,其中一家较大的通道提供商质量最好,速度最快,另一家就慢很多。因为彩信数量较大,业务部门希望可以合理的分配资源,在保证发送质量的前提下让2个通道提供商都有东西可以发送。我们提供给业务部门2个方案建议都被否决。

 

方案1:

用速度较快的通道作为主力通道。仅在主通道满时才考虑使用速度较慢的副通道。在讨论时这个方案被否决,因为这个方案有一个比较明显的缺陷,因为主力通道性能相当好,很可能发生永远都走不到副通道的情况,或者副通道利用率相当低,所有的压力都压在了主通道上。

 

方案2:

循环使用2个通道供应商,这个方案也被否决,因为这样做法就等于在浪费速度较快通道的资源,速度较快的通道原本还有空间进行发送,但却必须等待。

 

最后我设计了现在这个算法,也就是我现在主要讲的方法,我叫他“变种贪婪算法”,可能描述不太恰当,因为这个算法灵感来自于贪婪算法,但有不是完全的贪婪算法。

 

在讲这个算法前我们先讲一个故事,从前在一座岛上有一群猴子,猴子喜欢吃香蕉,但是这个岛上没有,只有在大陆上才有,大陆与小岛当中有3座桥相连,但是这3座桥大小不一,有的可以并排走4只猴子,有的只能走一只,到吃饭的时候,猴子们都涌向最大的那个桥因为桥大走的最快,因为这座桥最多同时只能走4只猴子,这样导致了桥都堵塞了,而且久而久之最大的桥因为一直被很多众多猴子走没有机会修缮最终坍塌了。有什么办法即可以让猴子快速的通过又可以让每座桥都有机会修缮呢?

 

为了解决这个问题,我们给每座桥都设立一个最多能走过猴子的极限,比如最大的那座桥极限是100只猴子,超过他就要关一关维护一下。这个时候猴子们就只能走其他2个较小的桥。这样每到桥的极限桥都有机会休息一下可是,但是这又带来了另一个问题,大家知道猴子很脆弱,俄不起啊!如果较大桥关闭,猴子都去走小桥因为猴子太多桥又小,很多已经很俄的猴子可能还没等到过桥就俄死拉!我们要爱护动物啊!怎么能让猴子随便就俄死!为了解决这个问题,我们不得不给猴子也加上一个饥饿指数!猴子的饥饿指数在每次检查等待时都会减1,一直到减为0为止。饥饿指数还没有到0的时候表示猴子还不至于俄死,可以继续等,并且将它的饥饿指数减1,当减到0的时候表示这个猴子已经俄到极点了!必须马上让它过桥!这个时候我会检测任何可以通过的桥(包括那个已经被关闭的较大的桥),只要能走立刻让它过!

从上面那个故事我们可以看到,这个方法解决每座桥都被合理使用不会将压力都压在某座桥上,也保证了猴子可以安需走不同的桥而不会被俄死。

 

回到程序上,程序分成线程管理对象,由它来分配各个请求到底使用什么通道来发送,通道对象(也就是故事里的桥),它有一个属性记录最大能通过数量(桥最多走过几只猴子就必须维护),和同时发送的数量(桥最多能同时走多少只猴子)。还有就是发送对象(也就是猴子),它包含了一个等待事件(猴子的饥饿指数)。

 

执行过程:

1.       通道管理对象在得到新的请求后,首先去检查等待池里有没有已经“俄的不行的猴子”,有的话就立刻循环所有的通道找到能用的(非忙即“当前发送数<最大同时发送数”和非休眠即“通道总发送数<最大能通过数”)的通道立刻发送。

2.       调用当前通道指针指向的通道,如果它非忙非休眠,就让他去等待池中取一条数据,如果它当前状态为“忙”就调用等待池中所有的等待记录使其等待指数减1。如果当前通道通过数量已满(即已经走过足够的猴子了)那么通道指针就+1指向下一个通道,并且将前一个通道初始化并进入休眠后等待下次调用。

3.       如果某个通道在发送时发送错误,这个通道立刻就会被设置为赌赛即将“通道总发送数=最大能通过数”让这个通道休眠,这条记录被反回等待池中并被初始化,让其他通道去试试。保证出错时也能发送。

 

实际上从上面看我们就明白这个其实就是贪婪算法中让你吃到饱,但是又不同于贪婪算法,因为它必须考虑两面即桥和猴子都有优先级。希望我的算法可以给大家一定建议,如果有什么改进建议也希望大家留言。

抱歉!评论已关闭.