N10K 掲示板 Mojolicious::Lite app

半分ネタ半分本気のウェブ掲示スクリプトです。名前の通り 1 万件 (N10K) を越えるエントリを投稿・閲覧可能な掲示板です。データは平文のテキスト・ファイルに保存する作りで、掲示板としては、とてもシンプルでたいしたことないのですが、莫大なエントリを食わせても余裕で閲覧・投稿・削除をおこなえるのがポイントです。といっても、速度が落ちないからと調子に乗って食わせていくと、データ・ファイルのサイズが数百メガバイトに膨れ上がっていくので、128メガバイトの容量制限と10万件のエントリ数制限をかけています。

このスクリプトはコンセプト・スクリプトでありエラー処理が甘いため、インターネットで公開して使わないでください。ローカルマシンで遊ぶ程度にしておいてくれた方が書いた私も安心します。

投稿制限は、ホワイト・リストによる URL 制限と、行数を漢字60文字を一行分として文字数と改行数から計算し、30 行を越えると拒絶する行数制限をおこないます。なお、投稿頻度制限をテキスト・ファイルだけでおこなうと効率が悪すぎるので、今回はトークン・バケット・フィルタを組み込んでません*1

https://gist.github.com/tociyuki/9189068 n10k.pl v0.07 (トランザクション対応 & テスト記述に向けに調整)
https://gist.github.com/tociyuki/9189068/89473ed7ee32a0cc032d3782526bdadbf1f58697 n10k.pl v0.01

  1. 2014-02-25: ドメインホワイトリストによるチェックが働いてなかったバグを修正
  2. 2014-02-25: writable メソッドのバグにより投稿フォームが表示されないバグを修正

試すには、 Mojolicious::Lite と Digest::HMAC_SHA1 モジュールが必要です。

モデルのうち、追記型可変長レコードなデータ・ファイルと追記型固定長レコードなインデックス・ファイルを扱う部分を覚書しておきます。モデル部分は Mojo 非依存で書いてあり、他のウェブ・アプリケーション・フレームワークでも使うことができます。

やっていることは単純なことで、ポストした投稿内容を可変長レコードとしてデータ・ファイルの末尾にどんどん追記していきます。ただし、それだけでは閲覧性が悪いので、投稿ごとのエントリのファイル内の位置を固定長レコードでインデックス・ファイルに一緒に追加していきます。ポスト時点では、データ・ファイルもインデックス・ファイルも少量の追記をしていくだけで済むので、効率良く投稿を処理することができます。どちらのファイルもすべてテキスト・データであり、バイナリ数値を使っていません。排他制御のロックはデータ・ファイルに対して LOCK_EX をかけています。2つのファイルの更新をしているので、本来なら排他制御だけでなくエラー時にロールバックするトランザクション処理にしないとまずいのですが、手を抜いています*2

package N10k::PagedArray;
use Fcntl qw(:flock);
use Encode;

my $INTWIDTH = 16; # 固定長レコードの大きさ。"空白列数字列\n" となる

sub save {
    my($self, $h) = @_;
    return 'cannot write' if ! $self->writable;
    return $self->object->save($self, $h); # Entry の save に投稿制限判断をまかせる
}

sub put { # Entry の save から呼び出される
    my($self, $object) = @_;
    my($data, $index) = ($self->data_path, $self->index_path);
    my $already = -e $data;
    open my($dh), '>>', $data or die "set cannot open data '$data': $!\n";
    flock $dh, LOCK_EX or die "set cannot lock file '$data': $!\n";
    open my($xh), '>>', $index or die "set cannot open index '$index': $!\n";
    binmode $dh; binmode $xh;
    $already or print $dh "#BOARD1\n";
    my $rowid = tell $dh;
    $object = $object->new({%{$object}, 'rowid' => $rowid});
    my $s = encode_utf8($object->marshal_dump);
    my $w = $INTWIDTH - 1;
    printf $dh "%${w}d\n%s", length $s, $s;
    printf $xh "%${w}d\n", $rowid;
    close $xh;
    flock $dh, LOCK_UN;
    close $dh;
    return $object;
}

掲示板はページ単位の閲覧が基本です。ページの最初のエントリが先頭から何番目かはエントリの個数とページに入るエントリ数から数式で計算可能で、それにインデックス・ファイルのレコードサイズをかけた位置に seek して、固定長レコードを1つ読み出してやります。読み出した値はデータ・ファイルのエントリが格納されている位置ですから、データ・ファイルを seek して read でページ表示に必要な個数のレコードを読み取れます。このやりかたにより、データ・ファイルのどの位置に対しても、データ・ファイル・サイズに関係なく同じ速度でページ分のレコードを読み出すことが可能です。

sub find_page {
    my($self, $page) = @_; # $page in 1 .. $self->count_page
    my($offset, $limit) = $self->range_page($page);
    my($data, $index) = ($self->data_path, $self->index_path);
    open my($dh), '<', $data or return [];
    flock $dh, LOCK_SH or die "set cannot lock file '$data': $!\n";
    open my($xh), '<', $index or die "set cannot open index '$index': $!\n";
    binmode $dh; binmode $xh;
    seek $xh, $INTWIDTH * $offset, 0;
    read $xh, my($addr), $INTWIDTH - 1;
    close $xh;
    seek $dh, $addr, 0;
    my $a = [];
    while (@{$a} < $limit && ! eof($dh)) {
        read $dh, my($n), $INTWIDTH;
        chomp $n;
        read $dh, my($row), $n;
        my $got = $self->object->marshal_load(decode_utf8($row));
        next if $got->rowid == 0;
        push @{$a}, $got;
    }
    return $a;
}

この掲示板では、エントリ識別子にデータ・ファイル内のレコード格納位置を利用しており、識別子からエントリを閲覧することもできます。ここで、ブラウザから渡された識別子が格納位置でない可能性があることを考慮して、識別子ですぐにデータ・ファイルを seek するのではなく、インデックス・ファイルから識別子を検索できるかどうかをまず調べます。このとき、投稿時の追記の仕組みからインデックス・ファイルには昇順で識別子が格納されているため、バイナリ・サーチを利用することができます。バイナリ・サーチ時も seek & read で格納されている識別子を読み出して、ブラウザが指定した識別子との比較をおこないます。一致した識別子が見つかれば、データ・ファイルから seek & read してレコードを読み出します。

sub find {
    my($self, $rowid) = @_;
    my $got;
    my($data, $index) = ($self->data_path, $self->index_path);
    open my($dh), '<', $data or return $got;
    flock $dh, LOCK_SH or die "set cannot lock file '$data': $!\n";
    open my($xh), '<', $index or die "set cannot open index '$index': $!\n";
    binmode $dh; binmode $xh;
    my($b, $addr) = $self->search_index($xh, $rowid);
    close $xh;
    if ($addr == $rowid) {
        seek $dh, $rowid, 0;
        read $dh, my($n), $INTWIDTH;
        chomp $n;
        read $dh, my($row), $n;
        $got = $self->object->marshal_load(decode_utf8($row));
    }
    flock $dh, LOCK_UN;
    close $dh;
    return $got;
}

sub search_index {
    my($self, $xh, $rowid) = @_;
    use integer;
    my $n = (stat $xh)[7] / $INTWIDTH;
    my($b, $d) = (0, $n);
    while ($b < $d) {
        my $u = ($b + $d) / 2;
        seek $xh, $u * $INTWIDTH, 0;
        read $xh, my($addr), $INTWIDTH - 1;
        my $cp = $rowid <=> $addr;
        if ($cp < 0) {
            $d = $u;
        }
        elsif ($cp > 0) {
            $b = $u + 1;
        }
        else {
            return ($u, $addr);
        }
    }
    return ($b, 0);
}

ページ分割では、最古のエントリを 1 ページ目に配置し、最新のエントリが最後のページに含まれるようにページ番号をふっています。ただし、最後のページはトップページなので特別扱いをしてあり、ここには指定個数のエントリを割り当てるようにしています。割付きれないエントリは最後のページの一つ前のページでつじつまをあわせます。

sub range_page {
    my($self, $page) = @_;
    my $p = $page - 1;
    my $m = $self->count; # 総エントリ数 (stat $self->index_path)[7] / $INTWIDTH
    my $ntop = $self->config->{'top_entries'};
    my $n = $self->config->{'per_page'};
    return (0, $m) if $m <= $ntop;
    $m -= $ntop;
    my $count = int(($m + $n - 1) / $n);
    return ($m, $ntop) if $page < 0 || $p >= $count;
    my $addr = $p * $n;
    my $size = min($m - $addr, $n);
    return ($addr, $size);
}

sub count_page { # 総ページ数
    my($self) = @_;
    my $m = $self->count;
    my $ntop = $self->config->{'top_entries'};
    my $n = $self->config->{'per_page'};
    return 1 if $m <= $ntop;
    $m -= $ntop;
    return int(($m + $n - 1) / $n) + 1;
}

逆にエントリ識別子からページ番号を求めるには、インデックス・ファイルからのバイナリ・サーチを使って最古からの順番を求めます。エントリの順番が求まれば、後は割り算をするだけです。

sub index_page {
    my($self, $rowid) = @_;
    my $m = $self->count;
    my $ntop = $self->config->{'top_entries'};
    my $n = $self->config->{'per_page'};
    return 1 if $m <= $ntop;
    $m -= $ntop;
    my $count = int(($m + $n - 1) / $n);
    my($data, $index) = ($self->data_path, $self->index_path);
    open my($dh), '<', $data or return $count + 1;
    flock $dh, LOCK_SH or die "set cannot lock file '$data': $!\n";
    open my($xh), '<', $index or die "set cannot open index '$index': $!\n";
    binmode $dh; binmode $xh;
    my($i) = $self->search_index($xh, $rowid);
    close $xh;
    flock $dh, LOCK_UN;
    close $dh;
    return $count + 1 if $i >= $m;
    return int($i / $n) + 1;
}

エントリの削除は、 /del を GET して、エントリ識別子と config に crypt して設定したパスワードをフィールドにいれておこなうようにしています。 エントリの削除は、インデックス・ファイルのレコードを削除して、データ・ファイルのレコードに空白を上書きします*3。インデックス・ファイルからのレコード削除は、単純にファイルの内容をずらしているだけで、ここが最も効率が悪い部分です*4。削除するとデータ・ファイルに隙間が開いたままになりますけど、間を詰めませんし再利用もしません。

sub del {
    my($self, $rowid) = @_;
    my $old;
    my($data, $index) = ($self->data_path, $self->index_path);
    open my($dh), '+<', $data or die "set cannot open data '$data': $!\n";
    flock $dh, LOCK_SH or die "set cannot lock file '$data': $!\n";
    open my($xh), '+<', $index or die "set cannot open index '$index': $!\n";
    binmode $dh; binmode $xh;
    my($b, $addr) = $self->search_index($xh, $rowid);
    if ($addr == $rowid) {
        my $xsize = (stat $xh)[7];
        my $p = ($b + 1) * $INTWIDTH;
        my $q = $b * $INTWIDTH;
        my $buf_size = 8192;
        while ($p < $xsize) {
            seek $xh, $p, 0;
            my $ngot = read $xh, my($buf), $buf_size or last;
            seek $xh, $q, 0;
            print $xh $buf;
            last if $ngot < $buf_size;
            $p += $buf_size;
            $q += $buf_size;
        }
        truncate $xh, $xsize - $INTWIDTH;
    }
    close $xh;
    if ($addr == $rowid) {
        seek $dh, $rowid, 0;
        read $dh, my($n), $INTWIDTH;
        chomp $n;
        read $dh, my($oldrow), $n;
        $old = $self->object->marshal_load(decode_utf8($oldrow));
        my $new = $old->new({%{$old}, 'rowid' => 0})->clean;
        my $row = (substr encode_utf8($new->marshal_dump) . (q( ) x $n), 0, $n - 1) . "\n";
        seek $dh, $rowid + $INTWIDTH, 0;
        print $dh $row;
    }
    flock $dh, LOCK_UN;
    close $dh;
    return $old;
}

試しに、各行に 59 文字の「あ」を埋めたものを 29 行分にヘッダを追加した 30 行のテキストを 200 件登録した場合と 2 万件登録した場合で、ページ閲覧速度をチェックしてみたところ、ほとんど変わりませんでした。 2 万件の場合に、無作為にページを閲覧してみても、速度差はありませんでした。2 万件のエントリからの削除ではインデックス・ファイルの書き直し量が最も多い先頭のエントリを削除してみても、追記よりやや遅いぐらいで、心配したほどの速度低下はないようです。なお、このときのインデックス・ファイルの大きさは約 300 キロバイトで、データ・ファイルの大きさは約 100 メガバイトでした。

*1:リモートアドレスからハッシュの剰余項を求めたものをレコード番号に使い、固定長レコードのファイルでトークン・バケットを扱えば良いのかもしれません。ハッシュの剰余項の衝突が起きても気にせずに同じレコードでフィルタリングするなら、ハッシュ・マップのレコード数を固定できるので、リハッシュ不要で済むでしょうし。

*2:追記ロールバックは、追記前のデータとインデックス両方のファイルサイズに truncate するだけで良いので実装は楽です。面倒なのは削除処理のロールバックです。

*3:上書きせず、レコードに削除済みのマークをつけるだけの方が良いかもしれません。

*4:さらに言えば、インデックス・ファイルを直接書き直しているので、ロールバックをやりにくくしています。まじめに作るなら、一時ファイルにインデックス・ファイルを再編成して、データ・ファイルでレコード削除に成功した後に差し替えるべきでしょう。