N.Katoh
typer_jp****@yahoo*****
2005年 3月 27日 (日) 13:58:21 JST
御無沙汰しております。加藤です。 以前はチョコチョコといじっていたりしたのですが、設置場所や時間的な事もあっ てFSwikiから離れていました。 が、ここ最近メーリングリストが活発になってきたので、コード書いたりデバッ グしたりはあまり出来そうにないのですが、つられて投稿してみます。 ＃すみません、かなり長いです。 さて、4.0に向けての話題でページ名のID化が出てきていました。 現状(3.x)の問題点として、 - ファイルシステムの制限に引っかかりやすい - URLが長くなる さらに利点としてですが、 On Tue, 22 Mar 2005 00:32:42 +0900 松本 正和 <matto****@chem*****> wrote: > 大賛成。うかつに題名を変えられないのは不便です。 これは、 - ページ名を変えてもURLが変わらない - ページリンクにIDが使える という事でしょうか？ 思いついた検討事項を挙げてみます。 - 英数字WikiNameの扱い - ID命名則の検討 - ID・ページ名のマッピング方法 - ID生成法の検討 - ID空間の大きさ - コリジョン時の処理方法 - Wiki書式への取り入れ - cgiリクエストへの両対応方法 重複する事項もありますがこんなところかなと。 * 英数字WikiNameの扱い 英数字WikiNameはそのままの方がなにかと便利だと思います。 この場合は次項の命名則で英数字WikiName＝IDとすれば良いわけですが、他の IDは被らない命名則としておかなくてはなりません。任意の英数字ページ名（小 文字のみとか）も同様でしょう。 ＃詳しくは次項で書きますが、対処は簡単です。 しかし、英数字ページ名はそのままとすると、ID化の利点の利点であるページ名 を変えてもIDは不変とする事により、ページ名を変えてもURLが変わらない、ID をリンクに使えばページ名を変えてもリンクが壊れないなどの恩恵に与れません。 * ID命名則の検討 前項のように任意の英数字ページ名と被らないIDを作るためには、例えば「IDは 必ず"_"で始まる」といったような命名則にすればよいと思います。この時使う 文字はURLエンコードされず、ページ名先頭で使われる事が少ない文字が好まし いでしょう。 RFCによるとエンコードせず安全に使う事のできる記号として"$-_.+!*'(),"が挙 げられていますが、手元のmozillaによるとエンコードされないのは"-_.*"でし た（だれかIEやopera、safariなどで確認してみてもらえませんか？）。このう ち一番ページ名として用いられないのは"*"でしょう。しかし、逆にいうとURL中 にでてくる文字としても一番自然ではないと思います。"_"はそこそこ自然です が先頭には使わないでしょう。 ただ、前項で英字WikiName、つまり「大文字で始まり…」というページのみその まま扱うとするならIDに関する制限が一気に緩和されて、たとえば「IDは必ず "id"の2文字で始まる」とする事もできます。 RFC参考：http://www.mars.dti.ne.jp/~torao/rfc/rfc1738-ja.txt ブラウザでの確認方法： GETメソッドの検索フォーム（具体的にはgoogle）に入力してURLを確認 * ID・ページ名のマッピング方法 マッピングを実質的に行なうのは永続化レイヤが妥当でしょう。 ページ名→ID変換はリンク作成時などで多く発生しますから速度重視となります。 この変換は、 - 対応表を使う - 数値演算により求める（ハッシュ法） が考えられます。対応表はページ数と共に速度が低下しますが、 - ページ数がそれほど多くない（数万ページとかは想定しなくてよいと思う） - ハッシュ法はコリジョンの問題があるため逆引き等が必要で、さほど効率が良 くないかも知れない - 永続化のバックエンドがRDBMの場合はこちらが便利 等があります。ハッシュ法の場合は変換速度がページ数の影響を受けにくいです が、 - コリジョン検出のためID→ページ名の変換が必要でこちらの影響を受ける - コリジョンが発生しだすと劇的に低下していく といったところでしょうか？ 逆のID→ページ名の変換は、ID生成に可逆変換が可能なタイプを選ばない限り永 続化が必須となります。こちらも対応表を使用する方法のほか、ページ属性の 一つとしてページ名を持たせるという方法もあります（重複検出や一覧の管理な どは当然必要ですが）。 いずれにしろこのあたりは効率も含めた永続化レイヤの実装の話でしょう。 * ID生成法の検討 IDの生成方法は - ハッシュ関数により生成 - ページ名とは無関係にユニークなID（シリアルID）を生成 - 可逆変換可能なIDを生成 があります。 ハッシュ関数についてざっと調べたところ、以下のような物があるようです。 参照：http://search.cpan.org/ - Digest::MD5 - String::CRC - String::CRC32 - Digest::CRC - Digest::Elf - Digest::Adler32 - Digest::JHash - Digest::ManberHash あと、こんなページもあります。 http://burtleburtle.net/bob/hash/doobs.html Digest::Perl::MD5は既に配布物にあり、また暗号化に使用されるようにコリジョ ン耐性は高いようですが、気になるのは実行速度です。こういった検索目的に使 うには役不足かも知れません。 String::CRC、String::CRC32、Digest::CRCは共にCRCを計算する物です。それな りに早く、コリジョン耐性も高いようです。 Digest::Elfは検索などで使われるメジャーな関数のようです。高速で、その割 にコリジョン耐性もあるようです。 その他もCPANにあった検索目的と思われる物です。 これらは一度コードを書いて速度やコリジョン耐性を実際に計ってみた方が良い かも知れません。 ハッシュ法は先に書いたようにコリジョンの問題を別にすればページ数が増えて も速度に与える影響が少ないという利点があります。しかし、コリジョン時にど うするかといった点で実装するデータ構造に工夫が必要になります。また、ペー ジ名からIDが決まりますのでページ名を代えてもID（URL）が変わらないという 実装ができなくなります。 シリアルID法はページ名とは無関係にIDを作って行く方法で、一番単純なのは最 新のIDを記録（永続化）しておき、それをインクリメントしてIDとする方法です。 コリジョンもありませんしページ名を変えてもID（URL）が変わらないという実 装ができます。ただ、ページ名→IDの対応表を管理してこれを使用していく必要 があるため、ページ数が増えると速度や使用メモりに影響してきます。大規模に なってくるとつらくなるかも知れません。 ＃どの程度が大規模か？ということもありますが(^^; この方法のもう一つの利点として次で挙げるID空間を途中で拡張する事が容易、 というより自動的に拡張できるため、（ほかの制限はありますが）いくらでも ページを増やせるという点があります。 あと、コリジョンはありませんが、新規作成時にコンフリクトしないようにきっ ちりとしたロック機構が必要だと思います。 可逆変換可能なIDを生成というのは、要は非ASCII文字をASCII化してしまうとい うもので、 - Convert::ASCII::Armor - MIME::Base64 といったものがあります。これだと100%演算で求められるのでページ数に依存せ ず、いまのURLエンコードを置き換えるだけで良いので簡単です。しかし、相変 わらずファイルシステムの制限は（緩くはなりますが）存在します。 Convert::ASCII::Armorについては概要しか見てないのでどんなものかは良くわ かりません。 MIME::Base64はFSwikiにも既に梱包されています。使われる文字は [A-Za-z0-9+/=]ですが、IDに使う場合は"+/"を"-*'に変えた変形Base64にすると 良いと思います（ID命名則の検討を参照、実際には"="は使われないですよね？）。 ここらあたりの話も永続化レイヤの実装の話なのでおいおい決めていけば良いで しょう。 * ID空間の大きさ ID空間の大きさ＝IDの（実効）文字数です。実際には識別のための文字が1-2文 字つく事になります。 IDはBase64エンコードとすると1文字64種6bitですから、2文字で12bit、4文字で 24bit、1677万色^Hページです。 ハッシュ法では途中でID空間を広げる場合、すべてのIDを付け直す（rehash）必 要があります。しかし、これだけの空間があればコリジョンのことを考えても十 分かなと思います。ただ、CRC32やELFなど32bitを生成するハッシュ関数が多い ので32bit分の6文字もありえますし、8bit削って丸めるのもありでしょう。 ＃でも決め打ちはしない法が良いでしょう。 * コリジョン時の処理方法 ハッシュ法を使う場合、必ずコリジョン時の対処法を考えておかなければなりま せん。一般的なのは、 - オープンアドレス法 - リンクリスト法 があります。 オープンアドレス法は、コリジョンが発生したらハッシュ値をインクリメンタル して、そこが空いていたらそこを使う、空いていなければさらにインクリメンタ ルするという方法です。 具体的には、製作時はコリジョンが発生したらIDをインクリメンタルして逆引き し、空いていたらそこを使う。検索時はハッシュ関数でIDを求めたら逆引きして ページ名を確認、違っていたらインクリメンタルして確認、一致していたらそれ が該当する。インクリメンタルの結果、空いていればそのページはない。といっ たところです。 リンクリスト法はコリジョンが発生したら、ポインタなどでリンクリストを作り、 同じハッシュ値に複数の値を保存できる様にする方法です。 今回の場合、同じIDに複数のページは保存できませんが、ページの付加情報とし てコリジョンの発生したページの保存先IDを記録しておくという方法があります。 ただ、その付加情報を保存してあるページを削除しても、その情報は保存してお くか、書かれているIDのページをもってくる（ただしURLが変わります）必要が あります。素直にオープンアドレス法を使った方が良いでしょう。 ただ、この方法は一種のシンボリックリンクを作る方法で、IDの有無に関わらず リンク情報を残せる様に作っておけばIDを変えずにページ名を変更できたり、エ イリアスが実現できたりします。 * Wiki書式への取り入れ 最後にこのIDをWiki書式へ取り入れるべきかいなかとう事があります。通常の ページリンクやincludeなどにIDを使用できるようにした場合、ページ名を変更 しても追従できます（というより必要ない）が、永続化レイヤを変えた場合にID が同一でないとマイグレーションでページ中のID書き換えが必要になります。ま た、永続化レイヤでIDが変わり得る実装（コリジョン時の処理方法：リンクリス ト法参照）は禁止しなければなりません。 とはいえ、永続化レイヤの変更は滅多にある事ではないし、IDが変わる事は（ IDですから！）避けるべき事でしょう。 * cgiリクエストへの両対応方法 URLにIDを用いる事により長いページ名でもURLが長くなりませんが、URLから ページ名がわからなくなります。また、InterWikiの事もありますので今までの ようにページ名での受け入れも残しておく方が賢明です。この場合、IDはcgiパ ラメータとしてnameにかえてidを用いるなどで対応できるでしょう。また、ペー ジ名としてIDと思われる文字列が渡され、それがページ名ではなかった（ページ が存在しなかった）場合はIDとみなして処理する方法もあります。 この時、通常のwiki内でのリンクをどちらにするかは設置オーナーが選択できる ようにしておいた方が良いと思います。そして、その場合でもページ名でのリン ク、IDでのリンクをそれぞれ簡単に取得できる仕組み（ヘッダかフッタにそうい ったリンクをつけておけるような、そういったリンクを作成するプラグインをつ けるなど）を持たせた方が親切でしょう。 その他として、cgiに単一のパラメータ（.../wiki.cgi?_foge）を渡された時は IDとしてそのページを表示するなどを行なえばURLの見ためがかなりすっきりし ます。 いささか長くなってしまいました。全体としてハッシュ法はなにかと考える事が 多く、また、意外と効率が良くないかもというのが感想です。あと、少なくとも 開発版ではコリジョンの状況などを調査できるようにして実際のところを確認し たり、リリース時にはrehashができるようにしてID長が変更できるようにしとく 必要もあるでしょう。 そんなわけでシリアルID法が良いかも知れません。ただ、単純にインクリメンタ ルするシリアルID法は芸がない（笑）かなと思うのでハッシュによりIDをもとめ て管理はシリアルID方式ってのが良いかも。 いずれにしろID化する場合はバックエンドはRDBMの方が便利そうです。 また、シンボリック的手法を実装するのはなにかと使い勝手が良さそうです。た だリンク切れにはご注意。 その他では、 - 英数字ページはIDなし／ID＝ページ名 - IDは"_"で始まり、[0-9A-Za-z*-]で4/6文字 - 通常のページ名に加えIDによるリンクを可能にする - IDを変えずにページ名を変更可能にするか？それはオプションか必須か？ - Wiki書式にIDを使用可能にするか？使用可能にするならその書式はどうするか？ - ID生成／管理アルゴリズムを統一するか？ -- 統一するとバックエンドの違う別の永続化レイヤへの移行が楽 -- 違うサイトでも同じページ名に同じIDがつく可能性が高い（ハッシュ法のみ） といったところでしょうか。 さてさて、以下はP.S.というか余談です。 ここまではcgi全体にわたりIDを主に使い必要なところだけページ名に変換とい う前提で書いてましたが、ファイルシステムの制限を回避する目的だけなら、い まの3.*でも永続化レイヤだけの変更で出来るんじゃないでしょうか？ 4.0でID化を行なうにしても3.*の永続化レイヤで閉じたID化を行なえば設計も含 めたバグフィクスや実際の統計をとったり出来ます。 また、ID化や管理のアルゴリズムが同じであれば、4.0への段階的移行手段とし て使えますから有用じゃないでしょうか？だれか挑戦してみません？ ＃と他力本願 では。 -- typer typer_jp****@yahoo***** Noboru Katoh typer****@chive*****
Fork