Sep 13, 2004

MT3でなぜエントリの追加に時間がかかるようになるのか

Ogawa::Buzz: Movable Type 3.0の Individual Entry Archiveの命名方式の問題点の落ち穂拾いで、私の好きそうなネタです。

気が付いている人がいるかどうかは分かりませんが、MT3では使っているうちに、徐々にRebuildに要する時間が増大するのはもちろんですが、1エントリの追加にかかる時間も増大します。一般的に言って、増大する度合いがエントリ数に比例する程度なら問題ありませんが、エントリ数の2乗、3乗に比例するようだと速度低下が目に付くようになります。

これは以前も述べたmake_unique_basenameという手続きが原因で起きます。

MT::Util::make_unique_basenameは新しいエントリを作るたびに必ず1回呼び出され、そのエントリのbasenameを決定します。このmake_unique_basenameは以下のような手続きからなっています。

sub make_unique_basename {
    my ($entry) = @_;
    my $blog = $entry->blog;
    my $title = $entry->title;
    unless ($title) {
        if (my $text = $entry->text) {
            $title = MT::Util::first_n_words($text, 5);
        }
        $title = 'Post' unless $title;
    }
    my $base = substr(MT::Util::dirify($title), 0, 15);
    $base =~ s/^_+//;
    $base =~ s/_+$//;
    $base = 'post' if $base eq '';
    my $i = 1;
    my $base_copy = $base;
    
    while (MT::Entry->count({ blog_id => $blog->id,
                              basename => $base })) {
        $base = $base_copy . '_' . $i++;
    }
    $base;
}

この手続きをおおまかに説明すると、まずタイトルもしくは本文をdirifyした文字列の最長15文字を取り出します。次にこの文字列をbasenameに持つエントリがないかどうかを、「SELECT COUNT(*) FROM mt_entry WHERE basename=...」の戻り値が、0(=マッチするエントリなし)か、0でないか(=マッチするエントリあり)かによって判定します。

マッチするエントリがあれば、文字列に「_1」を付加して再度SELECT COUNT(*)を実行します。これを「_2」、「_3」、…と繰り返し、マッチするエントリがない状態になったらそれをベースネームとして返します。

例えば、このBlogではタイトルがすべて日本語からなるエントリが400個あります。これらのエントリのbasenameはpost, post_1, post_2, ..., post_399と付けられているわけです。次にすべて日本語からなるタイトルを持つエントリを作ったとすると、401回SELECT COUNT(*)を実行して初めてpost_400というbasenameが付けられるわけです。

少し形式的な書き方をすると、エントリ数をNとすると、一回のインデックススキャン(SELECT COUNT(*))の処理時間は最良でO(1)、平均でO(log N)、一回のmake_unique_basenameはこのシーケンススキャンをO(N)回(※)行います。したがって、エントリを1個追加するのに要する時間はO(N log N)となります。Acceptableかどうかはギリギリというところでしょう。念のためこれはMySQL, PostgreSQLの場合であり、BerkeleyDBではO(N2)になる可能性があります。

※ 私のBlogで約900個のエントリ中、約400個が日本語のみからなるエントリでした。これは平均的な日本人がBlogにおいて日本語のみのエントリを作成する度合いが平均的にNに比例することを示す十分な(十分以上の?)根拠となります。一方で英語国民に関してはこのようなことは起こらず、O(1)となることが予想されます。

どうしてもO(N)にしたければ以下のようなコード(正確な動作はオリジナルと異なります)にすればよいわけですが、普段たいていO(1)で済んでいた英語国民には不幸になります。というかこっちはこっちで重い操作をやっていて、試しに書いてみたというだけのものです。お使いの環境によっては高速化されるとは限りません。

sub make_unique_basename {
    my ($entry) = @_;
    my $blog = $entry->blog;
    my $title = $entry->title;
    unless ($title) {
        if (my $text = $entry->text) {
            if (MT::ConfigMgr->instance->DefaultLanguage eq 'ja') {
                $title = MT::I18N::first_n_text($text, 10);
            } else {
                $title = MT::Util::first_n_words($text, 5);
            }
        }
        $title = 'Post' unless $title;
    }
    my $base = substr(MT::Util::dirify($title), 0, 15);
    $base =~ s/^_+//;
    $base =~ s/_+$//;
    $base = 'post' if $base eq '';
    my @bnames = grep {/^$base(\_[0-9]+)?$/} map {$_->basename}
                        MT::Entry->load({ blog_id => $blog->id });
    return $base unless @bnames;
    my $max = -1;
    foreach my $bname (@bnames) {
        my $bidx = ($bname =~ /$base\_(.*)/) ? $1 : 0;
        $max = $bidx if $max < $bidx;
    }
    return $base . '_' . ++$max;
}

よくある質問とその答え

Q1. 「個別のアーカイブへのリンクに以前の形式(id)を利用」したり、アーカイブファイルの形式を指定すれば、この問題を回避できますか?

A1. できません。エントリを追加した際にmake_unique_basenameが必ず呼ばれてしまいます。回避するとすれば、make_unique_basenameの定義を書き換えるか、プラグインなどで上書きする必要があります。

Q2. そんなに遅くなった気がしないのですが?

A2. ここで述べている問題は「下書き」状態でエントリを保存するのにかかる時間、あるいはエクスポートデータのインポートにかかる時間、に関するものだと考えてもらった方が直感に合っています。make_unique_basenameはそのエントリが「下書き」にしろ「公開」にしろ最初に保存されたときに一回だけ呼び出されるのですから。

もっともエントリの追加と同時に公開+再構築を行う場合などは、make_unique_basenameの処理時間は一般に無視できるかもしれません。なぜなら再構築はテンプレートの解釈やファイルI/Oを伴うもっとずっと重い操作ですから。しかし、再構築の処理オーダーがO(N)であるのなら、いずれmake_unique_basenameの処理オーバーヘッドが顕在化することも予想できます。

About Me

My Photo

つくばで働く研究者

Total Pageviews

Amazon

Copyright 2012 Ogawa::Buzz | Powered by Blogger
Design by Web2feel | Blogger Template by NewBloggerThemes.com