分散への考察その２−Entity分割方式

全点数を一つのインスタンスに格納するのではなく、適当な点数の範囲毎にインスタンスを分けて分散させるアイデアです。
今回試しに実装したものは0〜10万点の範囲で作成していますが、これを4096点毎に25個のインスタンスに分けて実装したのが↓です。
http://tetz-lab.appspot.com/ranking/?trn=gtx&type=divided

ランキング計算にかかる時間は初回は600〜900ミリ秒程度、2回目以降は70〜150ミリ秒程度でした。更新は80〜150ミリ秒程度。Entityが小さくなった分、若干更新が早いみたいです。

しかしこの方式だと特定の点数に負荷が集中するとスケールしないので、Entityへの負荷が高まってきたらそのEntityを分散カウンタ方式で分割する、といった対処も考えた方がよさそうです。

分散への考察その１−分散カウンタ方式

スケールするカウンタの実装として、「分散カウンタ」というのが知られています。
appengineでは更新処理に比べてgetがとても早いので、カウンタ用のEntityを複数個用意して、
　・更新はランダムに選んだどれか一つに対して実施
　・カウンタの値は全部parallel getして合計値を計算
とすることで、高速かつスケールするカウンタが実現できる、というものです。

上にも書きましたが、この実装ではEntity1個でやっているので、この考え方がほとんどそのまま使えます。
実際に実装したのがこちらです。
http://tetz-lab.appspot.com/ranking/?type=sharding

id:bluerabbitさんの、
http://d.hatena.ne.jp/bluerabbit/20091226/1261756546
を参考にさせていただきました。ありがとうございました。m(__)m

ランキング計算にかかる時間は初回は800〜1300ミリ秒程度と少々遅いものの、2回目以降は70〜200ミリ秒程度とそれ程変わらない速度が出ています。parallel getって早いんですね。
更新はEntity一つの場合とほとんど変わらない値が出てました。

ランキング計算以外も実現できる？

id:koherentさんがajn8向けに作成されたスライドを見ながら、同じことができるか考えてみました。
http://www.slideshare.net/koher/skiplists20100604

• P.36　リストの要素数･･･一番上の階層の保持する人数。O(1)で計算可能。
• P.37　要素番号による検索･･･要するに「○位の人は何点」。ランキング計算同様、O(log 16 (X))で計算可能。
• P.39　総和・平均･･･同様に、配列と一緒に格納された要素の総和を保持すれば可能。一番上のLayerから取得すれば良いので、O(1)でOK。
• P.40　範囲に対する集約･･･同様に実現可能。
• P.41　最大・最小・中央値･･･要素数番目・0番目・要素数/2番目の検索として実現可能。全部O(log 16 (X))。
• P.42　キー値以外の集約･･･これも同様に配列と一緒に保持すれば可能。
• P.43　キー値以外の最大・最小･･･これも同様にやれば多分可能そうですね。

という訳で、集計関係はほぼ同じ事が実現できそうです。

その他、Pagingは一応無理すれば条件付きで実現できそうなんですが･･･これに関しては無理やりな感じが否めないので、割愛します。

Skiplistと比べると…

このデータ構造はSkiplistと比べて、汎用性がありません。
扱うのが整数値の点数なら問題ないですが、例えばこれが小数値だと途端に難しくなります。
特に文字列を扱うのは多分無理でしょう。
Skiplistなら任意ソート条件が扱えるんですが、こちらは使用できる条件がかなり限定されます。

まあでも、その限定された条件なら高速に動作しますし、速度がデータ件数に依存しないって特長もあるんで、使いどころはそれなりにあるんじゃないかとは思います。

Google App Engineのランキング問題

Google App Engineで何かと話題になってたランキング問題。
appengine ja night #8(ajn8)に参加された方ならご存知のように、既にid:koherentさんがSkiplistというアルゴリズムを使って解決しています。
参考：http://d.hatena.ne.jp/koherent/20100425/1272176872

そのほかにも、id:bufferingsさんの実装例もあります。
参考：http://d.hatena.ne.jp/bufferings/20100225/1267121912

id:bufferingsさんのとほぼ同じアイデアを自分でも思いついてたんで、ちょっとslim3使って実装してみました。
http://tetz-lab.appspot.com/ranking/
事前に乱数で10万件の点数データを入れてあります。
って、何を今更な感じなんですが、せっかく思いついて実装までしちゃったので、日記に残しておきます。

ロジックを簡単に説明します。
まず、

• 点数ごとにその点数を取った人数を格納する領域を用意する。
• その領域をサイズ16の配列に格納する。点数の下位4ビットが配列へのindexとして使用される。
• その上位4ビットをindexとして持つ配列に、上記の配列を格納する。この配列では格納された全配列の保持された人数の合計値を保持する。
• さらに上位4ビット･･･(繰り返し)

というデータ構造を作ります。
69,533点(16進数で10F9D)を例に考えると、下の図みたいな感じの構造です。

ランキングを計算するときには、赤い矢印で示したより高い点数の領域に格納された人数の合計値を計算し、最後に+1すればOKです。
今回の実装では、全Layerの配列をまとめて一つのEntityに保存しているので、getは一回で済みます。
ちなみに、もし配列毎にEntityを分けても、ランキング計算・更新処理ともに一番上Layerには必ずアクセスする必要があるので、分散させることはできません。分散に関しては後述。

ランキング計算にかかる時間は初回は600〜1000ミリ秒程度、2回目以降は70〜120ミリ秒程度でした。
2回目以降が早いのは、多分Datastore側にキャッシュされるからかな？(spin upは計算時間に入れてないから、関係ないはず。)
頻繁にアクセスがある場合には、70〜120ミリ秒で処理できる、ということになりそうです。
更新は120〜200ミリ秒程度かかっています。

この方式のアルゴリズムの速度は、Skiplistと違って点数の件数には影響を受けず、点数の取りうる範囲に影響を受けます。
点数が取りうる値が0〜Xだとすると、アルゴリズムの速度は、
　　O(log 16 (X))
になるんじゃないかと思います(多分)。

JavaでもRubyみたいなMap(Hash)のリテラルが欲しい！

と思って考えてみました。

Javaで適当なMap作るときって、

Map<String, String> map = new HashMap<String, String>();
map.put("tako", "octopus");
map.put("ika", "squid");
map.put("namako", "sea cucumber");

ってな感じじゃないですか？

RubyとかだとMap(RubyだとHash)のリテラルがあるんで、

hash = {"tako" => "octopus", "ika" => "squid", "namako" => "sea cucumber"}

と書けて楽です。
ScalaにもOGNLにもこんな感じの記法があるので是非Javaにもって思うんですが、ないんですよね…。

で、この前もうちょっと楽に書けないかと思って、こんなクラスを作ってみました。

public final class ColUtil {

	public static class FluentMap<K, V> extends LinkedHashMap<K, V> {

		public FluentMap<K, V> p(K key, V value) {
			this.put(key, value);
			return this;
		}
	}

	public static FluentMap<Object, Object> $m(Object key, Object value) {
		return new FluentMap<Object, Object>().p(key, value);
	}

	public static FluentMap<String, Object> $m_so(String key, Object value) {
		return new FluentMap<String, Object>().p(key, value);
	}

	public static FluentMap<String, String> $m_ss(String key, String value) {
		return new FluentMap<String, String>().p(key, value);
	}
}

使い方はこんな感じ。

import static com.tetz42.util.ColUtil.*;
　　　　　　：
	// ↑と同じ例
	Map<String, String> map = $m_ss("tako", "octopus").p("ika", "squid")
		.p("namako", "sea cucumber");

	// その他のメソッドの使用例
	Map<Object, Object> map1 = $m("key1", "value1").p(0, 99);
	Map<String, Object> map2 = $m_so("One", 1).p("Two", 2)
		.p("Threee", new RuntimeException());
　　　　　　：

リテラルっぽさを出したかったので、各staticメソッドの先頭に「$」つけてます。
なお、FluentMapをLinkedHashMapから継承させてるのは、書いた順番を保持したいケースもありそうに思ったからです。
OGNLもデフォルトでLinkedHashMapらしいですし。

Map版のほかにList版とSet版も作ったんですが、予想つくと思うんでソースは省略します。

Listの要素がMapになっている例

Rubyだと、

list = [
  {"name" => "John",  "sex" => "male"},
  {"name" => "Linda", "sex" => "female"},
  {"name" => "Taro",  "sex" => "2 times per week"} ]

と書けます。

で、今回のColUtilを使うとこんな感じです。

import static com.tetz42.util.ColUtil.*;
import com.tetz42.util.ColUtil.FluentList;
　　　　　　：
	// このメソッドを作成する必要あり！
	public static FluentList<Map<String, String>> $lm(Map<String, String> map) {
		return new FluentList<Map<String, String>>().a(map);
	}
　　　　　　：
		List<Map<String, String>> list = 
			$lm($m_ss("name", "John" ).p("sex", "male"))
			 .a($m_ss("name", "Linda").p("sex", "female"))
			 .a($m_ss("name", "Taro" ).p("sex", "2 times per week"));
　　　　　　：

まとめ

うーん、多少は似せれたんじゃないかとは思うんですけど、やっぱ元からリテラルが存在している言語と比べると見劣りしますね…。
それでも、最後の例を通常どおりのJavaの書き方した場合の長さを考えるとそれなりに有用な気がしてるんですけど、どうでしょうかね？

Slim3でDIコンテナっぽくテストする方法

2週間ほど前に、急遽SAStruts+Seasar2+S2JDBCの現場のヘルプに呼ばれました。
ところがテツさん、Seasar2はおろかDIコンテナ自体やったことなくて、大急ぎで勉強する羽目になりまして。
今も勉強しながら作業しているんですが、そんな中ふと「あれ、Slim3でもDIっぽく作れるのでは…？」という考えが浮かんできました。

思い立ったら早速検証！

まずは、DI(Dependency Injection)についてのおさらい

例えばとあるメソッドを

public int getCount(){
    Foo foo = new Foo();
    Bar bar = new Bar();
    return foo.getCount() + bar.getCount();
}

みたいに作ると、Foo#getCount()はDatastoreにアクセスしていて、Bar#getCount()はURLフェッチを使用している、なんてことになると事前準備が大変でテストが面倒くさい。

だから、

@Resource
protected Foo foo;
@Resource
protected Bar bar;

public int getCount(){
    return foo.getCount() + bar.getCount();
}

みたいに作っておけば、フィールドのfoo・barをモックに入れ替えられるので、テストがやりやすくなります。
※ 「@Resource」は、Seasar2に自動的に正しいインスタンスを注入させるためのアノテーション
(って、勉強してわずか２週間のクセにえらそうですが･･)

Slim3の「service」で実現する方法

さて、まずはSlim3のservice(controllerとmodelの間の、おもにビジネスロジック書くところ)でやってみます。
と言ってもserviceはPOJOなので、DIコンテナを使わずにDIっぽいことをやるための一般的な話になります。

初期化メソッド(↓ではsetUp)を用意して、インスタンスの注入は全部そこでやります。
こんな感じ。

public class FooService {
    
    protected User usr;
    protected BarService barService;

    public FooService setUp(User usr) {
        this.usr = usr;
        this.barService = new BarService();
        return this;
    }

    public Profile getProfile() {
        return Datastore.get(Profile.class, Datastore.createKey(
            Profile.class,
            usr.getEmail()));
    }
    
    public int getCount(){
        return barService.getCount() % 100;
    }
}

setUpがthisを返却しているのは、呼び出し元が

fooService = new FooService().setUp(usr);

と書けるようにするためです。

テストはこんな感じになります。

    @Test
    public void getProfile() throws Exception {
        
        // Mockを注入
        service.usr = new User("wifeofhiromi@gmail.com", "gmail.com");
        
        // テスト
        Profile profile = service.getProfile();
        assertThat(profile.getName(), is("Iyo"));
        assertThat(profile.getSex(), is(Profile.FEMALE));
        assertThat(profile.getAge(), is(16));
    }
    
    @Test
    public void getCount() throws Exception {
        
        // Mockを注入
        service.barService = new BarService(){
            @Override
            public int getCount(){
                return 242;
            }
        };
        
        // テスト
        assertThat(service.getCount(), is(42));
    }

getCountの「Mockを注入」の部分は匿名インナークラスを使用しています。Mockのためにいちいちクラス作るの面倒だからね。
世の中にはMock生成用のライブラリとかもあるのですが、ここでは説明を簡単にするため割愛します。(※ウソです。単に使い方知らないだけです･･･。)

「Controller」で実現する方法

Slim3向けの話はここから！

http://sites.google.com/site/slim3documentja/documents/slim3-controller/run
を見るとわかるとおり、Controllerでは事前処理を行うsetUpメソッドが用意されています。
このsetUpでインスタンスの注入をやればイケそうですが、そう簡単ではありません。

ControllerはPOJOではなく、JUnitでテストするときにも「tester」というControllerTesterクラスのインタンスをヘルパーとして使い、擬似的なrequestを送信する形でテストします。

        tester.start("/dicon/");

この一文で、リクエスト受信 ⇒ Controller生成 ⇒ setUp ⇒ run ⇒ tearDownまで一気に実行してしまいます。
なのでserviceでやったようにMockを注入するのは簡単ではありません。
で、今回考えた手は、

1. Controller#setUpにはserviceでやったみたいに、普通にインスタンスの注入を実装
2. テストクラスでは、テスト対象のController#setUpでMockを注入させるようオーバーライドしたものを生成
3. testerでのController生成処理もオーバーライドし、↑で生成したものを返却させる

というものです。

たとえば、テスト対象のControllerがこんな感じだとします。

public class IndexController extends Controller {

    protected FooService fooService;

    @Override
    protected Navigation setUp() {
        User usr = UserServiceFactory.getUserService().getCurrentUser();
        fooService = new FooService().setUp(usr);
        return null;
    }

    @Override
    public Navigation run() throws Exception {
        requestScope("name", fooService.getProfile().getName());
        requestScope("count", fooService.getCount());
        return forward("index.jsp");
    }

}

すると、テストクラスはこんな感じになります。

public class IndexControllerTest extends ControllerTestCase {

    @Test
    public void run() throws Exception {

        // Mockを注入
        TestUtil.setMockController(tester, new IndexController() {
            @Override
            protected Navigation setUp() {
                this.fooService = new FooService() {
                    @Override
                    public Profile getProfile() {
                        Profile profile = new Profile();
                        profile.setName("tetz42");
                        return profile;
                    }

                    @Override
                    public int getCount() {
                        return 42;
                    }
                };
                return null;
            }
        });

        // テスト
        tester.start("/dicon/");
        IndexController controller = tester.getController();
        assertThat(controller, is(notNullValue()));
        assertThat(tester.isRedirect(), is(false));
        assertThat(tester.getDestinationPath(), is("/dicon/index.jsp"));
        assertThat(tester.asString("name"), is("tetz42"));
        assertThat(tester.asInteger("count"), is(42));
    }
}

IndexController#setUpをオーバーライドして、その中でFooServiceのMockを注入しています。
TestUtilってのは今回このために作ったクラスで、ソースは↓です。

public final class TestUtil {

    public static void setMockController(ControllerTester tester,
            final Controller mock) throws NoSuchFieldException {
        FrontController frontController = new FrontController() {
            @Override
            protected Controller createController(String path) {
                return mock;
            }
        };
        TestUtil.copyFields(
            tester.frontController,
            frontController,
            "charset",
            "bundleName",
            "defaultLocale",
            "defaultTimeZone",
            "servletContext",
            "servletContextSet",
            "rootPackageName");
        tester.frontController = frontController;
    }

    public static void copyFields(Object src, Object dst, String... fieldNames)
            throws NoSuchFieldException {
        for (String fieldName : fieldNames) {
            copyField(src, dst, fieldName);
        }
    }

    @SuppressWarnings("unchecked")
    public static void copyField(Object src, Object dst, String fieldName)
            throws NoSuchFieldException {
        Class clazz = src.getClass();
        while (clazz != null) {
            try {
                Field field = clazz.getDeclaredField(fieldName);
                field.setAccessible(true);
                Object value = field.get(src);
                field.set(dst, value);
                return;
            } catch (Exception e) {
                clazz = clazz.getSuperclass();
            }
        }
        throw new NoSuchFieldException(src.getClass().getSimpleName()
            + " has no "
            + fieldName);
    }
}

「匿名インナークラスの中から、finalのローカル変数にアクセスできる」という少々マイナーな仕様を利用している箇所があるんで、ご注意を。
リクエストのURLとかrootPackageとかからControllerを生成するメソッドの、FrontController#createControllerをオーバーライドして、パラメタで受け取ったControllerを返却する偽FrontControllerを生成しています。
その後は、本物から必要なフィールドをコピーして、本物と入れ替えています。

さて…

これで、最初に自分がやりたいと思っていたことはおおよそ実現できたました。
なんかもっと良いやり方があるような気もしてるんだけど･･･、今後の研究課題とします。

ちなみに、TestUtilの偽FrontController生成部分は、こうした方が良い気がしてきました。

        FrontController frontController = new FrontController() {
            @Override
            protected Controller createController(String path) {
            	Controller original = super.createController(path);
            	if( !original.class.isInstance(mock) ){
    	        	throw new RuntimeException("Oh, no!");
            	}
                return mock;
            }
        };

こうすればオーバーライドしてしまっても、「リクエストのURLとかrootPackageとかから生成されたController」が正しいものであることの検証できるしね。

3/31 ソースにミスを見つけたので、修正