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
ちゃんと重みに基づいて分散された。
いつか、バランシング処理を書く機会があったら、使ってみようかな。