ninxit.blog

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

Request Counting アルゴリズムとは

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

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

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

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

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

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