ぐらめぬ・ぜぷつぇんのはてダ(2007 to 2011)

2007年～2011年ごろまで はてなダイアリー に書いてた記事を引っ越してきました。

Dataオブジェクトのテストケースがまとまらないっっ・・・！！

YakiBiki

うううぅぅ・・・まとまらないよぅ。何がまとまらないかって、閲覧時の処理をどうするかがまとまらない。
少なくとも次のフィールドは、ソートあるいはフィルタ対象になる。
owner, acl, thread, category, modified_at, created_at, name
このうち、acl/thread/categoryについては

acl_id1,id|id|id|...
acl_id2,id|id|id|...
...

みたいな形式のIDXファイルを用意して手動で引ける、範疇だ。レコード数が。基点となるACL/THREAD/CATEGORY自体の数が数万のオーダーには達しない。良くて数百。THREADは数千まで行くかな？でも、力業のリニア検索でどうにかできなくはないレベル。
問題は残りの、owner/modified_at/created_at/nameで。
まあ、nameは

name,id(|id...)
name, ...
...

形式のファイルにして、さすがにリニアは面倒くさいので、二分探索でサーチできる。
created_atについても、これは基本的にはレコードのappendしか発生しない。deleteはあるが、updateは発生しない。ので、これもnameと同様の形式で二分探索できる。っつーか、時刻系はinsertの方が良いなぁ。
ownerが面倒くさい。

owner_id,id|id|id|...
...

形式にすると、"id|..."以降が数百、数千のオーダーになる。explode()もさすがにきついだろう。
逃げ道としては、file()でさっくり読み込めるようにowner_idをファイル名に埋め込み、中身はidをEOLでjoinしただけにするのがベターか。

一番厄介なのがmodified_at。これ、どうするよ。これ、1:1じゃないんだもの。ID1のバージョン1は時刻Aに更新されて、バージョン2は時刻Bに更新されていた。

ID1,バージョン1,時刻A
ID1,バージョン2,時刻B

ってなるのか？うーん・・・何だかなぁ。


memoriesの時もそうだったけど、基本的に次のような検索条件で一覧を引っ張ってくる。

  • ログインしていて、所有者であれば全て取得。
  • 現在のユーザーで読み出し許可になっているACLの一覧を取得し、その中のACL IDにヒットすれば取得。
  • カテゴリ絞り込みが指定されていれば、指定されたカテゴリの分だけ、AND/ORで取得。
  • 文字列検索が指定されていれば、nameで検索。ワイルドカード対応？させると二分探索使えなくなるな。
  • 年・月・日くらいまで指定。

これでそれぞれ取ってきたIDから重複値を取り除き（或いはAND/OR処理で絞り込み）、さらにそこから次のどちらかでソートする。

  • 更新日付で「ソート」。デフォルトは更新日の新しい順。
  • 作成日付で「ソート」。バージョン更新にかかわらず作成日で見つけたい場合に使用。

うーん・・・これ、普通にSQLで組んでいても厄介な処理だよな。・・・いや、待てよ・・・？ACLのIDはCache_Liteが効くだろう。ACLのエントリ自体の数が少ないし、そもそもACLの更新はあまり発生しない。となると、所有者とACLの条件は必須として。ざっとSQLのWHEREを作るとこうなるんじゃないか？

select * from yb_data where 
    owner = 'owner id' and 
    acl in ('acl_id1', 'acl_id2', ...) and 
    (
        category in ('category_id1', 'category_id2', ...) or
        name like '%search_needle%' or
        created_at = '2007-01-01' or 
        modified_at = '2007-01-01'
    )
    order by modified_at/created_at asc/desc

微妙すぎる。IN句とか。あと、IN句自体はOR演算的なので、CategoryのANDを取るとなるとロジック的に相当きつくなるはず。distinctがどこかで出てきそう。さらにmodified_atがあるから、バージョン情報がどこかで結合されるはず。
とどのつまり、何かしらの「一覧取得専用の」テンポラリテーブル、あるいはVIEWになるのではなかろうか。

今進もうとしている道と一緒じゃねぇか・・・？

SQLの場合どうなるのかを想像した為に見えてきたものがあるにはある。Dataオブジェクトの一覧はあまりに特殊性が高くて、あっという間に迷路に迷い込んでしまう。ファイルストアであろうと、RDBMSにストアしようと。
つまり、後回しだ。

find_all()自体はDataクラスにはまだ実装しないことにしよう。この調子だと、Dataクラスの取り扱う実体データファイルの一覧を取り出すような処理はWebフロント側では発生しないような気がする。ext2/3系での1ディレクトリあたり1万 - 1.5万ファイルのリミットを抑える為、partisionSize()を導入したので、実際のディレクトリレイアウトはこんな感じになるし。

(partisionSize = 100に設定した場合)
.../data/
         100/ .. ID1 - ID100までのデータが保存される。
         200/ ... ID101 - ID200までのデータ
         ...

これを全部走査して、例えばaclや、modified_atでソートする？馬鹿らしい。数百 - 数千エントリを超えた辺りで、リニアに増えてきた速度遅延が体感速度にはっきりと引っ掛かってしまうだろう。

恐らくエントリの追加・更新・削除のタイミングで、一覧を生成する為の各種INDEXファイルを更新する。Webフロントに於いては、一覧を取得する場合はそれらINDEXからID群を取り出し、適宜検索条件に基づき絞り込む事になるだろう。間違っても、直接data/ディレクトリを全スキャンするような事には・・・したく、ないなぁ。
そしてその処理はどこでなされるか、と言うと・・・うーん。Daoの、上、かなぁ。

あんまりたとえ話は使いたくないのだけれど。
例えば、今まで作ったUser/Group/Acl/Category、あと多分将来的に作る予定のThreadとかは、一冊の「台帳」として表現できる。なので、Daoの中に台帳の個々のページをピンポイントで処理するメソッドと、台帳全体を総ざらえするメソッドの二つを入れてきた。前者はcreate/update/delete/find_by_idメソッド。後者は、find_all/find_by_ownerメソッド。
ところが、Dataについては台帳として表現できなくなってしまっている。単純な話、数千は当たり前、下手すれば個人が利用しただけでも万のオーダーにエントリ数が行ってしまうはずなのだ。これは実感としてあって、自分自身、旧memoriesには既に千件に手が届く数のエントリが入っている。しかもこれは、ファイルや画像が記事エントリに添付されているため、YakiBikiに移すとその分かさが増える。さらに入社以来、可能な範囲で回収してきた diary.txt 。これ、ほぼ毎日記している為（なぜってほら、出社・退社時間をあとで勤怠表につけるから！）、まぁざっと300日 x 4年分で 1200件。で、一日の内に平均して2つのエントリがあるとすれば、2400件。さらにGlamenv-SeptzenのPukiWikiや、Nifty時代のコンテンツ合わせれば200件程度エントリが追加される。そこにはてなダイアリが加わるので、まぁちょっと大目に見て500件。

1,000(旧memories) + 2,400(diary.txt) + 500(現行コンテンツ) = 3,900

「現状のエントリ」を合わせただけで千のオーダーは簡単に突破する。一日1エントリを書いていくだけでも、3年で1000エントリ。更に言うと、旧memoriesを踏まえた上でのmemoriesの着想以降、memoriesがまだ現存しなかった故に「書けなかった」損失分が相当ある。
というか、その時の為に取っておいた雑誌が結構ある。切り抜きとか。これがどさっと入ってくると・・・。
やっぱ、アクティブなユーザーであれば数年で万のオーダー行っちゃうよね。

なので、やっぱり、全スキャンはむしろ「禁止行為」にすら思えるのです。

たとえ話に話を戻すと、この時点で「一冊の台帳」という概念は破綻する。同じスケールで操作できるのは、１エントリに対してのみとなるだろう。つまり、台帳に閉じられたレコード群ではなく、方々に散らばったカード群となる。
例えばそこには「更新日付でカードを並び替えた『棚』」があるのだ。
「カテゴリで並び替えた棚」、「名前で並び替えた棚」、「ACLで並び替えた棚」などがあるのだ。
司書は、注文された検索条件で各棚から、該当するIDが書かれた紙切れを収拾し、AND/OR処理する。この時点では各IDの中身は未知。
出揃ったところで、実際の台帳を管理している倉庫に持って行く。倉庫番は、ID群をみて、直接倉庫から台帳を引っ張り出してデータを書き写し、司書に戻す。

よろしい。この例えが適切かどうかの判別は必要だろうが、やはり「操作のスケール」という観点から見た場合、主体は1つ以上になるだろう。また台帳自体に変更が発生した場合、倉庫番・・・になるかどうか分からないが、まず原本台帳を更新し、その後、旧台帳の情報に基づき各棚を整理する。

オッケー。ソフトウェアを使わない場合のシステムを想像した結果、やはりこの規模になると「注文された検索条件に応じてIDを収拾する操作」と、「個別のIDの中身を操作する」処理は分かれる。

以上のような思考に基づき、迷ってはいたが・・・しかしコレばっかりは見過ごすわけにはいかなかったので。とどのつまり、Daoレベルには一覧取得処理は実装しない事とする。また、各種INDEXファイルの更新処理も実装しない。それは上のレイヤーで実装されるだろう。多分。

まぁ自分以外の多くの人々にYakiBikiが行き渡る頃には、その辺りの性能問題は攻略されていることを信じたいけど。