Request Counting アルゴリズム

GREEエンジニアブログのグリーの大規模分散ストレージ戦略(nanofs) Vol.2を見ていて、Apache の Request Counting ってなんぞやと思ったので、調べたメモ。

Request Counting アルゴリズムとは

Apache の mod_proxy_balancer モジュールに組み込まれているロードバランサのスケジューラアルゴリズムの1つ。

やってきたリクエストが、各ワーカーにちゃんと分担されるようにというか詳細は、こちら

リンク先に擬似コードが示されていたので、試しにいくつかの言語で実装してみた。

lbfactor が重み、lbstatus が優先度みたいなものっぽい。

Python

#!/usr/bin/env python  
  
class Worker(object):  
    def __init__(self, name, factor):  
        self.name = name  
        self.lbfactor = factor  
        self.lbstatus = 0  
        self.debug_count = 0  
  
def request_counting(workers):  
    """Request Counting Algorithm"""  
    candidate = None  
    total_factor = 0  
      
    for worker in workers:  
        worker.lbstatus += worker.lbfactor  
        total_factor += worker.lbfactor  
        if not candidate or worker.lbstatus > candidate.lbstatus:  
            candidate = worker  
      
    candidate.lbstatus -= total_factor  
    return candidate  
      
if __name__ == "__main__":  
    workers = [Worker('A', 70),   
               Worker('B', 30)]  
      
    for i in xrange(10):  
        worker = request_counting(workers)  
        print "(%s) %s" % (worker.name, ", ".join(["%3d" % w.lbstatus for w in workers]))  
        worker.debug_count += 1  
          
    for worker in workers:  
        print "%s:%3d" % (worker.name, worker.debug_count)  

Perl

#!/usr/bin/env perl  
use strict;  
use warnings;  
  
{  
    package Worker;  
      
    sub new{  
        my $pkg = shift;  
        my %hash = (  
            name => shift,  
            lbfactor => shift,  
            lbstatus => 0,  
            debug_count => 0,  
        );  
        return bless \%hash, $pkg;  
    }  
}  
  
package main;  
  
sub request_counting{  
    my $candidate = undef;  
    my $total_factor = 0;  
    my $workers = shift;  
      
    foreach my $worker (@$workers){  
        $worker->{lbstatus} += $worker->{lbfactor};  
        $total_factor += $worker->{lbfactor};  
        if(!defined($candidate) or $worker->{lbstatus} > $candidate->{lbstatus}){  
            $candidate = $worker;  
        }  
    }  
   
    $candidate->{lbstatus} -= $total_factor;  
    return $candidate;  
}  
  
my @workers = (Worker->new('A', 70),  
               Worker->new('B', 30));  
  
for(my $i = 0; $i < 10; $i++){  
    my $worker = request_counting(\@workers);  
      
    my $debug_str = "";  
    foreach my $tmp (@workers){  
        $debug_str .= ($debug_str eq "") ? "" : ", ";  
        $debug_str .= sprintf("%3d", $tmp->{lbstatus});  
    }  
    printf("(%s) %s\n", $worker->{name}, $debug_str);  
    $worker->{debug_count}++;  
}  
  
foreach my $worker (@workers){  
    printf("%s:%3d\n", $worker->{name}, $worker->{debug_count});  
}  

Ruby

#!/usr/bin/env ruby  
  
class Worker  
    def initialize(name, lbfactor)  
        @name = name  
        @lbfactor = lbfactor  
        @lbstatus = 0  
        @debug_count = 0  
    end  
      
    def get_name()  
        return @name  
    end  
      
    def get_lbfactor()  
        return @lbfactor  
    end  
      
    def add_lbstatus(lbstatus)  
        @lbstatus += lbstatus  
    end  
    def sub_lbstatus(lbstatus)  
        @lbstatus -= lbstatus  
    end  
    def get_lbstatus()  
        return @lbstatus  
    end  
      
    def incl_debug_count()  
        @debug_count += 1  
    end  
    def get_debug_count()  
        return @debug_count  
    end  
end  
  
def request_counting(workers)  
    candidate = nil  
    total_factor = 0  
      
    for worker in workers:  
        worker.add_lbstatus(worker.get_lbfactor)  
        total_factor += worker.get_lbfactor  
        if not candidate or worker.get_lbstatus > candidate.get_lbstatus:  
            candidate = worker  
        end  
    end  
   
    candidate.sub_lbstatus(total_factor)  
    return candidate  
end  
  
workers = [Worker.new('A', 70),  
           Worker.new('B', 30)]  
  
for i in 1..10  
    worker = request_counting(workers)  
      
    debug_str = ""  
    for tmp in workers  
        debug_str += (debug_str == "") ? "" : ", "  
        debug_str += sprintf("%3d", tmp.get_lbstatus)  
    end  
    printf("(%s) %s\n", worker.get_name, debug_str)  
    worker.incl_debug_count  
end  
  
for worker in workers  
    printf("%s:%3d\n", worker.get_name, worker.get_debug_count)  
end  

結果

(A) -30,  30  
(B)  40, -40  
(A)  10, -10  
(A) -20,  20  
(A) -50,  50  
(B)  20, -20  
(A) -10,  10  
(A) -40,  40  
(B)  30, -30  
(A)   0,   0  
A:  7  
B:  3  

ちゃんと重みに基づいて分散された。

いつか、バランシング処理を書く機会があったら、使ってみようかな。