重力ブロック崩しとオセロ

その他

はてなのアルバイト応募用に過去に作った作品を探してたんですが、公開できそうだったものを二つ公開しました。

balls - 重力ブロック崩し

重力や空気抵抗などが存在するブロック崩しです。重力、空気抵抗、衝突の撃力などを運動方程式に入れて得られた加速度を近似的に積分することで物理法則をシミュレートしています。2002、2003年頃にFLASH/ActionScriptで作成したものを2007年にリメイク。

テキストファイルにブロックの配置を記述するだけで簡単にステージを自作できます。

http://www.koherent.org/balls/

koherent reversi

ただのオセロリバーシです。それほど強くないですが、一番強いアルゴリズムを選択すると常人では勝てないくらいの強さにはなってます。2003年頃にJava Appletで作成。

http://www.koherent.org/reversi/

雑感

まさかこれらを作ってからもう6年も経っているなんて・・・。

はてなパーカー

はてなパーカー欲しい！ブラックが欲しい！

はてなパーカー欲しい！とは - はてなキーワード

追記型MVCCで機能するB-treeによるインデックス

Koherent_DB

PerlShellKoherent::DBのインデックスがとりあえず機能するようになりました。

最初実装していた手法が正しく動作しないことに、かなり実装が進んでから気付いたのでずいぶん時間がかかってしまいました。単純なB-treeなら実装が簡単ですが、どうやって追記型MVCCと共存させ、トランザクションをサポートするかに苦労しました。

パフォーマンス

適当にしか計測してないですが、1件当たり80B（内データ部は50B）程度の小さめのデータで試したところ、インデックス付き（PKのみ）の書き込みが5〜6ms/件、100万件からのインデックス検索を用いた読み込みが5〜6ms/件程度でした。CPUがCore 2 Duo 1.8GHz、メモリが2.5GB、SATAのディスクのマシンを用いて計測しました。

今回計測したのはStandaloneモードという、常駐するDBサーバを用いずアクセスの度に設定等を読み込んで動作するモードです。ミューテックスがロックファイルで実現されていたり、1件書き込む度にインデックス情報を読み直したり（他プロセスがインデックスを作成しているかもしれないので）と、大量のディスクアクセスが発生しており、Pure Perlということも考えるとまあこんなもんかなという気がしています。プロファイラ*1で見てもディスクI/O関連のオーバーヘッドが大きいみたいなので、Client/Serverモードではもう少し高速化できると思います。

追記型MVCCインデックス

当初はインデックスのタプルもテーブルのタプル同様xminやxmaxを用いて管理しようと考えていました。しかし、この方法は実装が複雑な上に機能しないことに気付き、数日を無駄にした後にボツになりました。

具体的には次のような方法です。B-treeに1件データを挿入・削除する度に新しいノードを作成し、そのノードには一つ前の過去ノードへのポインタも記述しておきます。あるノードにアクセスするときは最新ノードから順にxmin・xmaxを検証し、現行トランザクションから可視なノードを拾い上げます。ノードは削除されることなく追記されるので、他トランザクションで削除されたけれどもコミットされていないノードを読み取ることもできます。

しかし、よく考えてみるとこの方法は機能しません。追記型MVCCでテーブルがうまく機能するのはデータごとにタプルが独立しているからです。インデックスの場合は、例えば枝数が100ほどあるB-treeを用いると、1件のデータの更新によって100件ものデータがロックされ他トランザクションから更新することができなくなってしまいます。さらに悪いことに、B-treeではノード挿入・削除時にノードが分割・統合されそれが親ノードへと伝播していくケースがあります。もし根ノードまで更新が伝播した場合、1件の更新・削除が他トランザクションからのあらゆるデータの更新・削除（同じく分割・統合が伝播する場合）を妨げる可能性があるということです。これではさすがに使い物になりません。

テーブルの全タプルを格納したB-tree

とはいえ、単純なB-treeでインデックスを実装するわけにはいきません。例えば、データ削除時にインデックスのB-treeからもデータを削除してしまうとコミット前に他トランザクションからもデータが見えなくなってしまいます。PerlShellKoherent::DBはトランザクションの分離レベルとしてSERIALIZABLEのみをサポートするため、このようなDIRTY READを許容するわけにはいきません。また、ロールバックをどう実装するのかという問題もあります。このように、単純なB-treeではトランザクションを扱うことができません。

そこで考えたのが、削除されたものも含めてすべてのテーブルのタプル（へのポインタ）を格納したB-treeを作成するという方法です*2。この方法は非常にシンプルなものです。データ削除時には何も行わず挿入時のみB-treeにデータを格納します。B-treeから検索するときはレンジスキャンを行い、範囲内のタプルの中からそのトランザクションで可視のもののみを拾い上げます。ただし、ノードが分割される際には元のノードを上書きするのではなく新たに2個のノードを追加する必要があります。これは、更新と参照が同時に行われた際にノード分割による参照データの欠如を防ぐための処置です。あるノードのデータは追記されるのみで削除されないため、更新と参照の同時実行が可能になるのです。

今後の予定

Client/Serverモードの実装やPODの作成なども行いたいのですが、とりあえずStandaloneモードだけでも動作するようになったので簡単なサンプルコードとモジュールをダウンロードできる形にして近日中に公開したいと思います。まだ実装しないといけない機能もあるので、目安は1週間程度でしょうか。

まとめ

インデックスの実装が完了し、動作するようになりました。近日中にPerlShellKoherent::DBを公開したいと思います。

インデックスのパフォーマンスを調べるために簡単なベンチマークをとってみたところ、100万件からの検索が平均5〜6ms程度で行えることがわかりました。これは、現在実装できているStandaloneモードでの結果であり、Client/Serverモードではより高速に動作すると思われます。

インデックスの実装に関しては、削除データも含めテーブルの全タプルを格納したB-treeを作成し、タプルの可視性判断はタプルに任せるという手法を用いました。

*1:Devel::NYTProfを使ったのですが、あまりの素晴らしさに感動しました。どこがボトルネックになっているのかをソースコード上で見ることができ、その呼び出し元をたどったり呼び出し元ごとの実行時間を見たりすることもできるので非常に対策を立てやすいです。今回も簡単に動作速度を3倍程度まで向上させることができました。

*2:もしかすると、DBの世界ではこういう手法は常識的なものかもしれませんが。

実装状況報告: Standaloneモードでの動作確認とトランザクションのサポート

Koherent_DB

このところ実装に注力してブログの更新が滞ってしまっていましたが、PerlShellKoherent::DBがとりあえず動くようにはなりました。

当初の予定に加えて次の機能を実装することにしました。

現状では、Standaloneモードかつインデックスなしの環境にて、一応動作確認ができました。

Standaloneモードの実装

レンタルサーバ等では、独自にDBサーバを立ち上げてプロセスを走りっぱなしにできないことが多いと思います。そのような環境でも動作するようにという理由で、Client/Serverモードに加えてファイルのような感覚でopen/closeできるStandaloneモードを実装することにしました。

StandaloneモードとClient/Serverモードで処理を共通化するために、処理の異なる部分は抽象化して扱いました。例えばStandaloneモードで用いるスレッド間用のミューテックスとClient/Serverモードで用いるプロセス間用のミューテックスを抽象化してMutexクラスを作成し、それを継承したProcessMutexクラスとThreadMutexクラスを実装するなどしました。両モードで適切に動作するためのクラス設計（Client/Serverモードでは一つしか存在しないものが、Standaloneモードは同時に複数プロセスで複数存在する場合にうなく対処するなど）に少々わずらわされました。

トランザクションの実装

トランザクションの分離レベルは、SQLでいうところのSERIALIZABLEオンリーで実装しています。SERIALIZABLEのみのサポートでも、4段階の分離レベルの上位レベルは下位レベルを包括する*1ので仕様上は問題ありません*2。

SAVEPOINTおよびROLLBAK TOはトランザクションの入れ子で対応することにしたので、ROLLBACK TO (SAVEPOINT)をどう実装するかに書いたようなトランザクションとコマンドの両方のコミットログを作るのではなく、XIDに対応したコミットログのみを作成しています。なお、現状ではSAVEPOINT/ROLLBACK TOは実装できていません。

現状と今後

今後は、下記の順に実装を進めようと思います。括弧内は実装完了の予定時期です。

  • インデックス（10月末〜11月上旬）
  • Client/Serverモード（11月上旬）
  • デッドロックの対処（検知 or タイムアウト）（11月中旬）
  • SAVEPOINT/ROLLBACK TO（11月中旬）

どうやら、はてなに応募するのは11月中旬以降になってしまいそうです・・・。

テストの様子

どんな感じで動いているのか雰囲気だけでも伝わればと思い、実行しているテストの一部（Standaloneデータベースを使って、主にトランザクション周りをチェックしているテスト）を公開します。現状でこのテストは通っています。穴だらけな上に異常系のテストがまったくない*3ので、もっとテストも改良しなければいけませんが・・・。

use Test::More tests => 59;
use File::Path qw(rmtree);
use Koherent::DB::StandaloneDatabase;

use constant DATABASE_DIRPATH => 't/02.database';

##### initialize #####
my $test_name;

# 前回作成したテスト用データベースを削除
&rmtree(DATABASE_DIRPATH);

# データベースおよびデータベースオブジェクトの作成
Koherent::DB::StandaloneDatabase->create(DATABASE_DIRPATH);
my $database = Koherent::DB::StandaloneDatabase->new(DATABASE_DIRPATH);

# テーブルの作成
$database->create_table('members');
$database->create_table('groups');

my $member_array = [
{
    member_id => 1011,
    first_name => 'Yusuke',
    family_name => 'Nakata',
    age => 22,
    sex => 0,
    group_id => 1,
},
{
    member_id => 1234,
    first_name => 'Saki',
    family_name => 'Yamashita',
    age => 17,
    sex => 1,
    group_id => 2,
},
{
    member_id => 1999,
    first_name => 'Takashi',
    family_name => 'Miyagawa',
    age => 18,
    sex => 0,
    group_id => 2,
},
{
    member_id => 2112,
    first_name => 'Nana',
    family_name => 'Ishida',
    age => 21,
    sex => 1,
    group_id => 1,
},
{
    member_id => 2345,
    first_name => 'Chika',
    family_name => 'Yamazaki',
    age => 19,
    sex => 1,
    group_id => 1,
},
];

my $new_member = {
    member_id => 2555,
    first_name => 'Akira',
    family_name => 'Tanioka',
    age => 22,
    sex => 0,
    group_id => 1,
};

my $group_array = [
{
    group_id => 1,
    group_name => '大学生',
},
{
    group_id => 2,
    group_name => '高校生',
},
];

my $new_group = {
    group_id => 2,
    group_name => '中学生',
};

my $members = $database->table('members');
my $member;
my $groups = $database->table('groups');
my $iterator;

# データの挿入
$members->insert($member_array);
$members->insert($new_member);
$groups->insert($group_array);

##### iterate #####
$test_name = 'iterate';

$iterator = $members->order_by('member_id')->iterator;

$member = $iterator->next;
is($member->{'member_id'}, 1011, $test_name);
$member = $iterator->next;
is($member->{'member_id'}, 1234, $test_name);
$member = $iterator->next;
is($member->{'member_id'}, 1999, $test_name);
$member = $iterator->next;
is($member->{'member_id'}, 2112, $test_name);
$member = $iterator->next;
is($member->{'member_id'}, 2345, $test_name);
$member = $iterator->next;
is($member->{'member_id'}, 2555, $test_name);
$member = $iterator->next;
ok(!$member, $test_name); # end iterating

##### update #####
$test_name = 'update';

$members->update(sub{$_[0]->{'age'}++}); # 新学年
$iterator = $members->order_by('member_id')->iterator;

$member = $iterator->next;
is($member->{'age'}, 23, $test_name);
$member = $iterator->next;
is($member->{'age'}, 18, $test_name);
$member = $iterator->next;
is($member->{'age'}, 19, $test_name);
$member = $iterator->next;
is($member->{'age'}, 22, $test_name);
$member = $iterator->next;
is($member->{'age'}, 20, $test_name);
$member = $iterator->next;
is($member->{'age'}, 23, $test_name);
$member = $iterator->next;
ok(!$member, $test_name);

##### where and update/delete #####
$test_name = 'where and update/delete';

$members->where(sub{$_[0]->{'age'} > 22})->delete; # 卒業
$members->where(sub{$_[0]->{'age'} == 19})
->update(sub{$_[0]->{'group_id'} = 1}); # 進学
$iterator = $members->order_by('member_id')->iterator;

$member = $iterator->next;
is($member->{'group_id'}, 2, $test_name);
$member = $iterator->next;
is($member->{'group_id'}, 1, $test_name);
$member = $iterator->next;
is($member->{'group_id'}, 1, $test_name);
$member = $iterator->next;
is($member->{'group_id'}, 1, $test_name);
$member = $iterator->next;
ok(!$member, $test_name);

##### transaction #####
$test_name = 'transaction';

$database->begin;
$members->where(sub{$_[0]->{'member_id'} == 1999})->delete; # 退学処分
is($members->count, 3, $test_name);
$database->rollback; # 手続きミス
is($members->count, 4, $test_name);

# 2 connections
{
    my $database2 = Koherent::DB::StandaloneDatabase->new(DATABASE_DIRPATH);
    my $members2 = $database2->table('members');
    my $groups2 = $database2->table('groups');
    my $new_member2 = {
        member_id => 2828,
        first_name => 'Yusuke',
        family_name => 'Nanami',
        age => 19,
        sex => 0,
        group_id => 1,
    };

    ##### dirty read (insert - rollback) #####
    $test_name = 'dirty read (insert - rollback)';

    $database2->begin;
    $members2->insert($new_member2); # 外部入学
    
    is($members->count, 4, $test_name);
    is($members2->count, 5, $test_name);

    $members2->insert($new_member); # 手続きミス

    is($members->count, 4, $test_name);
    is($members2->count, 6, $test_name);

    $database2->rollback;

    is($members->count, 4, $test_name);
    is($members2->count, 4, $test_name);

    ##### dirty read (insert - commit) #####
    $test_name = 'dirty read (insert - commit)';

    $database2->begin;
    $members2->insert($new_member2); # 外部入学

    is($members->count, 4, $test_name);
    is($members2->count, 5, $test_name);

    $database2->commit;

    is($members->count, 5, $test_name);
    is($members2->count, 5, $test_name);

    ##### dirty read (delete - commit) #####
    $test_name = 'dirty read (delete - commit)';

    $database2->begin;
    $members2->where(sub{$_[0]->{'member_id'} == 1999})->delete; # 退学処分

    is($members->count, 5, $test_name);
    is($members2->count, 4, $test_name);

    $database2->commit;

    is($members->count, 4, $test_name);
    is($members2->count, 4, $test_name);

    ##### phantom read #####
    $test_name = 'phantom read';

    $database->begin;
    $groups->insert($new_group); # 中等部設立

    $database2->begin;

    # dirty read
    is($groups->count, 3, $test_name);
    is($groups2->count, 2, $test_name);

    $members->insert({
            member_id => 3000,
            first_name => 'Yuki',
            family_name => 'Nanami',
            age => 12,
            sex => 1,
            group_id => 3,
        }); # 中等部入学

    # dirty read
    is($members->count, 5, $test_name);
    is($members2->count, 4, $test_name);

    $members->update(sub{
            my $member = shift;

            $member->{'age'}++;

            $member->{'group_id'} = 1 if &is_college_student($member);
            $member->{'group_id'} = 2 if &is_high_school_student($member);
            $member->{'group_id'} = 3 if &is_junior_high_school_student($member);
        }); # 新学年 & 進学
    $members->where(\&graduated)->delete; # 卒業

    # dirty read
    is($members->where(sub{$_[0]->{'member_id'} == 1234})
        ->row->{'age'}, 19, $test_name);
    is($members->where(sub{$_[0]->{'member_id'} == 1234})
        ->row->{'group_id'}, 1, $test_name);
    is($members2->where(sub{$_[0]->{'member_id'} == 1234})
        ->row->{'age'}, 18, $test_name);
    is($members2->where(sub{$_[0]->{'member_id'} == 1234})
        ->row->{'group_id'}, 2, $test_name);

    $iterator = $members2->where(sub{$_[0]->{'group_id'} == 1})->order_by(sub{
            my $member1 = shift;
            my $member2 = shift;

            ($member1->{'sex'} <=> $member2->{'sex'}) * 2
            + ($member1->{'member_id'} <=> $member2->{'member_id'});
        })->iterator; # 大学生のメンバーを男性/女性別にmember_id順に取得
    $member = $iterator->next;
    is($member->{'member_id'}, 2828, $test_name);
    $member = $iterator->next;
    is($member->{'member_id'}, 2112, $test_name);
    $member = $iterator->next;
    is($member->{'member_id'}, 2345, $test_name);
    $member = $iterator->next;
    ok(!$member, $test_name);

    $database->commit;

    # unrepeatable read
    is($groups2->count, 2, $test_name);
    is($members2->count, 4, $test_name);
    is($members2->where(sub{$_[0]->{'member_id'} == 1234})
        ->row->{'age'}, 18, $test_name);
    is($members2->where(sub{$_[0]->{'member_id'} == 1234})
        ->row->{'group_id'}, 2, $test_name);

    # phantom read
    $iterator = $members2->where(sub{$_[0]->{'group_id'} == 1})->order_by(sub{
            my $member1 = shift;
            my $member2 = shift;

            ($member1->{'sex'} <=> $member2->{'sex'}) * 2
            + ($member1->{'member_id'} <=> $member2->{'member_id'});
        })->iterator; # 大学生のメンバーを男性/女性別にmember_id順に取得
    $member = $iterator->next;
    is($member->{'member_id'}, 2828, $test_name);
    $member = $iterator->next;
    is($member->{'member_id'}, 2112, $test_name);
    $member = $iterator->next;
    is($member->{'member_id'}, 2345, $test_name);
    $member = $iterator->next;
    ok(!$member, $test_name);

    $members2->insert({
            member_id => 3333,
            first_name => 'Ai',
            family_name => 'Sasaki',
            age => 16,
            sex => 0,
            group_id => 2,
        }); # 高等部入学

    ok(!$members->where(sub{$_[0]->{'member_id'} == 3333})->exists, $test_name);
    ok($members2->where(sub{$_[0]->{'member_id'} == 3333})->exists, $test_name);

    $database2->rollback; # 不正発覚・入学取消

    ok(!$members->where(sub{$_[0]->{'member_id'} == 3333})->exists, $test_name);
    ok(!$members2->where(sub{$_[0]->{'member_id'} == 3333})->exists, $test_name);

    $database2->close;
}

$database->close;

sub is_junior_high_school_student{
    my $member = shift;
    $member->{'age'} >= 13 && $member->{'age'} < 16;
}

sub is_high_school_student{
    my $member = shift;
    $member->{'age'} >= 16 && $member->{'age'} < 19;
}

sub is_college_student{
    my $member = shift;
    $member->{'age'} >= 19 && $member->{'age'} < 23;
}

sub graduated{
    my $member = shift;
    $member->{'age'} >= 23;
}

まとめ

Standaloneモードにてひとまず動作しトランザクションも機能するようになりました。今後はインデックスやClient/Serverモードの実装などを順次行う予定です。

*1:13.2. トランザクションの分離より引用「リードアンコミッティドレベルを選択した時、実際にはリードコミッティドになり、リピータブルリードを選択した時、実際にはシリアライザブルになります。このように実際の隔離レベルは選択したレベルより厳密になることがあります。これは標準SQLでも許されています。この4つの隔離レベルについては、発生してはならない事象のみが定義され、発生しなければならない事象は定義されていません。」

*2:パフォーマンス上は問題があるかもしれませんが。

*3:ただし、これはStandaloneDatabaseのテストなのでwhereやorder_byなどのメソッドのテストは別途行っています。

limitメソッドとLimitedViewクラスの実装

Koherent_DB

limitメソッドは、SQLのLIMITやOFFSET*1相当の機能を実現するためのメソッドです。今回は、limitメソッドとそれを実現するLimitedViewクラスの実装について書きます。

例で使用するテーブル

これまで同様、次のようなテーブルがあるものとして話を進めます。

members: メンバーを格納したテーブル
member_id family_name first_name age sex group_id
1011 中田 祐輔 22 0 1
1234 山下 沙希 17 1 2
1999 宮川 崇 18 0 2
2112 石田 菜々 21 1 1
2345 山崎 千佳 19 1 1
PerlShellKoherent::DBでのテーブルの取得

次のようにして、$membersがTableオブジェクトを事前に保持しているものとします。

my $members = $database->table('members');

limitメソッドの実装

SELECTのAPI(2) 様々なSELECT文への対応に書いたように、検索結果のリミット（件数制限）やオフセットを行うには、limitメソッドを用いて次のようにします。

SELECT * FROM members LIMIT 3;
SELECT * FROM members LIMIT 2, 3; -- LIMIT 3 OFFSET 2

my $result;
$result = $members->limit(3);
$result = $members->limit(2, 3); # LIMIT 3 OFFSET 2

また、LIMITやOFFSETはORDER BYと共に用いられることが多いですが、これは次のようになります。

SELECT * FROM members ORDER BY first_name LIMIT 1, 2;

$result = $members->order_by('first_name')->limit(1, 2);

whereメソッドやorder_byメソッドと違いコード・リファレンスを渡す必要もないため、limitメソッドの実装は単純です。気をつけなければならないのは、与えられた引数が一つかそれより多いかで第1引数がリミットを表すかオフセットを表すかを決定しなければならない点のみです（第1引数がオフセット、第2引数がリミットという順はMySQLのLIMITに倣いました）。limitメソッドは、それを実現するViewクラス（のサブクラス）であるLimitedViewクラスのインスタンスを返します。

コードを書くと次のようになります。例によって関係ない部分は省略しています。

package Koherent::DB::View;

# 省略

use Koherent::DB::LimitedView;

# 省略

sub limit{
    my $self = shift;

    my $limit;
    my $offset;

    croak 'No arguments.' if @_ < 1;

    if(@_ == 1){
        # 第1引数のみ与えられた場合はLIMITのみ
        $limit = shift;
        $offset = 0;
    }else{
        # 引数が2個以上の場合は第1引数はOFFSET、第2引数がLIMIT（第3引数以降は無視）
        ($offset, $limit) = @_;
        croak "OFFSET is undefined." unless defined($offset);
    }
    croak "LIMIT if undefined." unless defined($limit);

    Koherent::DB::LimitedView->new($self, $offset, $limit);
}

# 省略

limitメソッドではオフセットのみを設定することができないのでoffsetメソッドも実装します。なお、LimitedViewクラスのコンストラクタに第2引数を渡さなかった場合はオフセットのみを行うLimitedViewオブジェクトが生成されるものとします。

# 省略

sub offset{
    my $self = shift;
    my $offset = shift;

    croak "OFFSET is undefined." unless defined($offset);;

    Koherent::DB::LimitedView->new($self, $offset);
}

# 省略

ただし、limitメソッドとoffsetメソッドを組み合わせて使うと効率が悪いので、リミットとオフセットの両方を設定する際はlimitメソッド一つで済ませるべきですす。

# 悪い例
$result = $members->limit(2)->offset(3);
# 良い例
$result = $members->limit(3, 2);

LimitedViewクラスの実装

LimitedViewクラスは、基本的にLimitedViewIteratorクラスに処理を丸投げするだけです。ConditionedViewクラスやOrderedViewクラス同様LimitedViewクラスもViewクラスを継承しているため、limitの戻り値であるLimitedViewオブジェクトに対してwhere、order_by、limit、offsetなどのメソッドを呼び出すことができます。

LimitedViewクラスのコードは次のようになります。

package Koherent::DB::LimitedView;

# 省略

use base qw(Koherent::DB::View);
use Koherent::DB::LimitedViewIterator;

sub new{
    my $class = shift;
    my $view = shift;
    my $offset = shift;
    my $limit = shift;

    my $self = $class->SUPER::new;
    $self->{'view'} = $view;
    $self->{'offset'} = $offset;
    $self->{'limit'} = $limit;

    $self;
}

sub iterator{
    my $self = shift;

    Koherent::DB::LimitedViewIterator->new($self);
}

# 省略

LimitedViewIteratorクラスの実装

リミットやオフセットの処理はLimitedViewIteratorクラスで実現します。

リミットとオフセットの処理は単純です。limitメソッドの呼び出し元のViewオブジェクトからイテレータを取得し、初めにオフセットで設定された行数分だけ取得結果を捨てます。その後リミットで設定された行数分のみ結果を返します。具体的には、nextメソッドが呼び出された回数を変数に記録しておき、それがリミットで設定された回数以上になると値を返さないようにします。

LimitedViewIteratorクラスの実装上気をつけなければならないことは、リミットで指定した行数分だけのデータを呼び出した時点で、元のイテレータにも終了を通知しなければならないということです。例えば、元のイテレータがファイルからデータを読み出している場合、limitメソッドでデータ取得が打ち切られると元のイテレータはファイルを開きっぱなしになってしまいます。

このようなケースに適切に対処するために、ViewIteratorクラスにはendメソッドを用意しています（ViewIteratorクラスのデストラクタでもendメソッドが呼ばれる仕組みになっています）。endメソッドの処理はクラスによって異なりますが、LimitedViewIteratorクラスでは元イテレータのendメソッドを呼び出し、データ読み出しの終了を通知します。

LimitedViewIteratorクラスのコードは次のようになります。

package Koherent::DB::LimitedViewIterator;

# 省略

use base qw(Koherent::DB::ViewIterator);

sub new{
    my $class = shift;
    my $view = shift;

    my $original_iterator = $view->{'view'}->iterator;
    my $offset = $view->{'offset'};

    # 最初の$offset行分をスキップ
    if(defined($offset)){
        for(1..$offset){
            last unless $original_iterator->next;
        }
    }

    my $self = {
        view => $view,
        original_iterator => $original_iterator,
        # 何行読み出したかのカウント
        count => 0,
    };

    bless $self, $class;
}

sub next{
    my $self = shift;

    # 読み出し終了済の場合は値を返さない。
    return if $self->{'ended'};

    my $original_iterator = $self->{'original_iterator'};
    my $count = $self->{'count'};
    my $limit = $self->{'view'}->{'limit'};

    $self->{'count'} = ++$count;

    if(!defined($limit) || $count <= $limit){
        # $limitが設定されていないか
        # まだ$limit行分データを読み出していない場合のみ
        # 次の行を読み出して返す。
        $original_iterator->next;
    }else{
        # 読み出しを終了
        $self->end;
        return;
    }
}

sub end{
    my $self = shift;

    return if $self->{'ended'};

    # 読み出し終了済のフラグを設定
    $self->{'ended'} = 1;

    # limitメソッド呼び出し元Viewオブジェクトのイテレータに
    # 終了を通知する。
    my $original_iterator = $self->{'original_iterator'};
    $original_iterator->end if $original_iterator;
}

# 省略

まとめ

SQLのLIMITおよびOFFSETに相当するlimitメソッドおよびoffsetメソッドを実装しました。

whereメソッド同様、limitメソッド（とoffsetメソッド）、LimitedViewクラス、LimitedViewIteratorクラスをセットで実装しました。limitメソッドをorder_byメソッドとセットで使用することによって、任意の順序でソートされたデータの、任意の位置から任意の位置までを取得することが可能となりました。

*1:正確には、MySQLやPostgreSQLのLIMITやOFFSETです。標準SQLでは最近になってLIMIT、OFFSET相当の構文が定義されたようですが、現時点で一般的ではありません。

恒常的なディスクアクセスへの対処

その他

最近、PCを起動しているだけでも絶え間なくディスクアクセスが行われており気になっていました（Windows XP SP3での話です）。調べてみたところ、JQS(Java Quick Starter)が原因のようだとわかりました。

JQSの停止方法（Windows XP、Windows 2000）

まずはJQSの無効化方法を書きます（というか引用します）。

Java Quick Starter を無効にする手順

1. 「スタート」をクリックします。
2. 「コントロールパネル」をクリックします。
3. 「Java コントロールパネル」のアイコンをダブルクリックします。
4. 「Java コントロールパネル」の「詳細」ダブをクリックします。
5. 「その他」まで移動し、ツリーを展開します。
6. 「Java Quick Starter」のチェックボックスをオフにします。
7. 「了解」をクリックし、コンピュータを再起動します。

Java Quick Starter (JQS) とは ?JQS を実行する利点は何ですか ?

調査内容

JQSがあやしそうだと思った経緯をメモしておきます。

  1. どのプロセスがディスクアクセスしているのかを調べるために、Process Minitorをインストール。
  2. Process MonitorでFile System Activityを表示したところ、jqs.exeが大量に表示される。
  3. 上記の「Java Quick Starter を無効にする手順」を実施。
  4. 大量のディスクアクセスがなくなる。

ということで、どうやら僕の場合はJQSがずっとディスクアクセスを続けていたようです。Javaを起動することなんてあまりないですし*1、ディスクアクセスがずっと続くのはディスクによくなさそうなので、JQSは停止することにしました。

まとめ

継続的なディスクアクセスの原因はJQSのようでした。JQSを停止しても困らなさそうだったので停止するとディスクアクセスもなくなりました。

*1:一番得意な言語の現状としては少し悲しいですが・・・。

ROLLBACK TO (SAVEPOINT)をどう実装するか

Koherent_DB 検討事項

これまで書いてきた記事は実装のほぼ固まったものについて解説する形のものが多かったですが、それらとは区別し、現在検討中のことについて検討事項のカテゴリーで書きたいと思います。今回は、ROLLBACK TO（およびSAVEPOINT）の実装について書きます。

なお、僕は追記型MVCCについては聞きかじった程度ですし、PostgreSQLのソースを読んだこともないので、大部分を想像（妄想？）で補って実装しようとしています。ここに書かれている手法が実際役に立つかどうかは怪しいので、何かに利用したり誰かに話したりする際にはご注意下さい。

ROLLBACKの実装

PostgreSQLに倣って、トランザクションIDをxid、あるタプルが見えるトランザクションの範囲をxminおよびxmaxで表します（xmin <= xid < xmaxのときそのタプルは可視となります）。

xmin xmax firld1 field2 ...
500 505 aa bbb ...
505 508 aa ccc ...
508 bb ddd ...

上記のようなデータがあり、3行目のタプルがコミットされていないとします（つまり、xid = 508のトランザクションを実行中です）。ここでこのトランザクションをロールバックした場合、各タプルの状態はこのままでコミットログにxid = 508がABORTEDと記録されます。

次に、xid = 509でデータを参照する場合を考えます。2行目のタプルはxmin <= xidですがxmax = 508なのでxid < xmaxが成り立たず、本来xid = 509のトランザクションからは見えません。しかしコミットログを調べるとxid = 508はABORTEDと記録されているのでxmaxを無視して可視とします(xid = 505に関してはコミットログがCOMMITEDなのでxminは有効です*1）。3行目のタプルはxmin = 508なので本来可視ですが、2行目と同様xid = 508はABORTEDなのでxminを無効とし、このタプルを無視します。

このデータをさらに更新する場合を考えてみます。xid = 510で更新するとすると、本来であれば3行目のxmaxを510に設定するところですが、xid = 508はABORTEDなのでこれを無視し、もう一つ前の2行目のタプルのxmaxを更新します。この結果、下記のようになります。これをxid = 510以降で参照すると、4行目だけが可視となります。

xmin xmax firld1 field2 ...
500 505 aa bbb ...
505 510 aa ccc ...
508 bb ddd ...
510 cc ddd ...

以上のようにして、ROLLBACKを実現できます。

ROLLBACK TOの実装

トランザクション内ではxidの代わりにcid（コマンドID）が用います。例えば、次のようなデータを考えます（cidにとってのcmin、cmaxはxidにとってのxmin、xmaxに対応します）。

xmin xmax cmin cmax firld1 field2 ...
500 500 1 3 aa bbb ...
500 500 3 7 aa ccc ...
500 7 bb ddd ...

2行目の状態（cid = 3）に対してSAVEPOINTを作成しているとします。このとき、ROLLBACK TOでその状態まで戻すにはどうすればよいでしょうか。コマンドID版のコミットログがあれば同じように動作するように思えます（以下、便宜的にコマンドID版のコミットログをコマンドコミットログ、従来のトランザクションのコミットログをトランザクションコミットログと呼びます）。ROLLBACK TOでSAVEPOINTまで戻すためには、cid = 4, 5, 6, 7のコマンドコミットログをABORTEDにします。このトランザクションがコミットされた後に他トランザクションからこのデータを参照する場合を考えてみましょう。2行目のタプルを参照する際にはxid = 500, cid = 7のコマンドコミットログがABORTEDになっているため、cmaxを無視してこのタプルを可視とします。同様に、3行目のタプルは無視されます。

このようにして、コマンドコミットログというものを導入することによって、ROLLBACk TOも実現できそうです。

コミットログの実装

トランザクションコミットログは、一つのファイルに記録することができます。IN_PROGRESS、COMMITED、ABORTEDの3状態は2ビットで表現することができるため、あるxidに対応したログを、ファイルのxid * 2ビット目から2ビットに記録することでランダムアクセスが可能となります。しかし、コマンドコミットログはトランザクションごとに複数存在します。トランザクションコミットログのように単純にはいきません。

最初に思いつくのはトランザクションの数だけコマンドコミットログのファイルを作成することです。しかし、一つのトランザクションのコマンドコミットログがディスクブロックの大部分を埋めるほど長くなることはまれだと思うので、この方法ではディスクの使用効率が悪すぎます。また、キャッシュの観点からも非効率です。

とはいえ、コマンドコミットログの長さは固定長ではないため、すべてのコマンドコミットログを一つのファイルにべた書きしたのではランダムアクセスすることができません。これを解決するために、ログファイルとは別にインデックスファイルを作成する方法が考えられます。

インデックスファイルには、あるトランザクションのコマンドコミットログがログファイルの何バイト目から始まるかを記録します。例えば、xid = 500, cid = 7のコマンドコミットログを参照する場合を考えます。まず、インデックスファイルから、xid = 500の位置を引きます。位置が8バイトで記録されているとする*2と、8 * 500バイト目から8バイトを読み出します。この読み出した8バイトの値がログファイル上での位置を表します。コマンドコミットログではIN_PROGRESSとCOMMITEDを区別する必要がないので（トランザクションコミットログを見ればわかるため）、1ビットで状態を表すことができます。今、仮に読み出した値が（10進数で）54321だったとすると、cid = 7のコマンドコミットログを読み出すには、ログファイルの54321 * 8 + 7ビット目を見れば良いことになります。

考察

インデックスファイルとログファイルに分離することでランダムアクセス可能なコマンドコミットログを実現し、ROLLBACK TOとSAVEPOINTが実装可能になるのではないかと思います。しかし、コマンドコミットログのようなものの存在は聞いたことがありませんし、そんなものがなくてもROLLBACK TOやSAVEPOINTを実現できるのかもしれません。他の良い方法や、PostgreSQLでの実装方法をご存知の方がいらっしゃれば教えていただければ幸いです。

また、そもそもROLLBACK TOとSAVEPOINTを実現する必要があるのか、ということも悩んでいます。ROLLBACKだけであればコマンドコミットログは不要になるため実装は簡単になります。

まとめ

トランザクションIDごとのコミットログだけでなく、コマンドIDごとのコミットログ（というよりアボートログ？）を用いることで、ROLLBACK TOを実現することができそうです。しかし、僕が知らないだけで、より機知のより良い方法が存在する可能性は多分にあります。また、そもそもROLLBACK TOを実現する必要があるかについても検討中です。

*1:簡略化のためにスナップショットの話は省略しています。

*2:4 bytes = 32 bitsでは4GBまでしか表せないので大きなテーブルでは問題が起こりそうですが、8 bytes = 64 bitsなら16EBまで扱えるので問題にはならないでしょう。

方針変更について

Koherent_DB

PerlShellKoherent::DBの作成についての方針を一部変更します。

Pure PerlのRDBMSを作るで、次のように書きました。

  • 10月上〜中旬くらいまでにある程度形にする。
  • まずはMyISAMのような、トランザクションなし、テーブルロックで動作するものを作る。

これらを、次のように変更したいと思います。

  • 10月中に動くものを作る（目標）。
  • 追記型MVCCっぽいことをして、トランザクションをサポートする。

トランザクションをサポートしないDBを作ってもあまり意味がないと思ったので方針転換です。

完成時期の延期は実装が遅れていることもありますが、トランザクション対応のための期間ということで。