Sender: katsu@FLAGSHIP.katsu.watanabe.name Newsgroups: fj.chat,fj.comp.programming Followup-To: fj.comp.programming Subject: rehash of dbm References: <3991827news.pl@rananim.ie.u-ryukyu.ac.jp> <3991847news.pl@rananim.ie.u-ryukyu.ac.jp> From: WATANABE Katsuhiro Date: 05 Jul 2005 14:10:11 +0900 Message-ID: Organization: An individual person. User-Agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.3 MIME-Version: 1.0 Content-Type: text/plain; charset=iso-2022-jp Lines: 128 Xref: FLAGSHIP mine:485 あまりのフォローアップの遅さが議論の妨げになっていたら ごめんなさい。少し勉強して出直してきました。 dbm や gdbm や Berkeley DB など、永続性を備えた hash 表 (external hashing)の性能に関して、データ数が多い(>10^6) 領域での話です。 記事 <3991827news.pl@rananim.ie.u-ryukyu.ac.jp> で kono@ie.u-ryukyu.ac.jp (Shinji KONO) さんいはく > hash だと、rehash されちゃうと破綻します。最初にhashの > 大きさを指定できれば良いんですけどね。 今の dbm ファミリでは、破綻というほど酷いことにはなりません。 実は、rehash で天地創造的に表を作り直すような実装は廃れて しまっています。一部分を split(分割・詳細化)することで 徐々に表を広げていく実装の方が一般的です。 記事 <3991847news.pl@rananim.ie.u-ryukyu.ac.jp> で kono@ie.u-ryukyu.ac.jp (Shinji KONO) さんいはく > rehash は、table をallocation して、全部hashし直して > 元のtableをdeallocate するっていう手順ですよね。これは > 重いです。メモリネックです。 初期の dbm や ndbm はそうでした [XMLDB] [SDBM]。しかし、 sdbm 以降、現在の gdbm や Berkeley DB の hash では、 そうした手順はとりません。これらは、表の部分的な拡張に 備えた Dynamic hashing という類のアルゴリズムを採用して います。いっときに集中して全体を hash しなおすのは 避けるように考えてあります。 Dynamic hashing には何種類かあるのですが、それらを dbm ファミリのデザインと対応付けて示すと、以下のように なります。 sdbm : 狭義の Dynamic hashing [DYNAMIC] gdbm : Extendible hashing [INDEX] Berkeley DB : Linear hashing [INDEX] なお、Linear hashing には興味深い別名があって、 Incremental hashing とも呼ばれます。 多分古い dbm, ndbm も含め、表の拡張は pair の詰った bucket を "split" することで行います。address 範囲が増える分は、 hash 関数自体は変えず addressing に用いる bit 数を増やして 対応します。最初は LSB 4bit を使い、混んできたら 5bit を 使うという具合です。今まで 1101 の bucket に入っていた データは、01101 と 11101 の bucket へと split して振り分け られます。 Dynamic hashing では、split は表の一部に留めて楽をします。 すると bucket の粒度が一様になりませんが、それでも hash 値 からの addressing が困難にならないためには bucket をどう 整列したらよいのでしょう?ここがバリエーションになります。 狭義 Dynamic は trie 辞書、Extensible は一段階の間接表、 Linear では表中で split を進める順番をあらかじめ都合よく 固定しておくことで解決しています。詳細は参考文献をどうぞ。 参考文献 [XMLDB] "Open Source XML Database Toolkit" Liam R. E. Quin ISBN 0-471-37522-5 http://www.holoweb.net/~liam/xmldb/ から、Chapter 12: Dynamic Hashing: dbm の中の "How ndbm Works" の節の中の要点: XMLDB> hash 値の下位の数ビットを pair 保存用ブロックの XMLDB> アドレスとする。ブロック内に pair を追加する余裕が XMLDB> なければ、用いる下位ビット数を +1 して表を広げる。 XMLDB> これは非常に遅い。なぜなら key を全部調べ、新しい XMLDB> ブロックへデータを移動しなければならないから。 上の引用の原文は以下の URL で参照することができる。 http://www.holoweb.net/~liam/ftp/xmldb/p3-nonrelational/p3-ch12-dynamic-hashing.doc ただし Word 形式のファイルが読めない人は、代替として Google に変換をお願いすることができる。 http://www.google.com/search?q=cache:L-6784SYbWUJ:www.holoweb.net/~liam/ftp/xmldb/p3-nonrelational/p3-ch12-dynamic-hashing.doc&hl=ja [SDBM] "sdbm - Substitute DBM or Berkeley ndbm for Every UN*X Made Simple" Ozan (oz) Yigit http://search.cpan.org/src/NWCLARK/perl-5.8.7/ext/SDBM_File/sdbm/README 要点1: SDBM> dbm, ndbm は、insert の時に空きがないとデータの SDBM> ページ群を split しようとして帰ってこなくなる SDBM> ことがある。sdbm では worst case に対する備えが SDBM> してあって、そのようなことは起きない。 要点2: SDBM> 3つのアルゴリズム(Dynamic, Linear, Extensible) SDBM> をプロトタイプし、sdbm では Larson の記事にある SDBM> "Dynamic Hashing" を採用した。 [INDEX] "Database Management Systems" Raghu Ramakrishnan and Johannes Gehrke ISBN: 0-07-246563-8 http://www.cs.wisc.edu/~dbbook/ から、この本に付随する Lecture 用スライド "Hash-Based Indexes" http://www.cs.wisc.edu/~dbbook/openAccess/thirdEdition/slides/slides3ed-english/Ch11_Hash_Index.pdf は Linear hashing と Extendible hasing をわかりやすく 説明している。 [DYNAMIC] "Dynamic Hashing" Course materials for COMP201 class Victoria Univ. of Welington Mengjie Zhang http://www.mcs.vuw.ac.nz/courses/COMP201/2004T1/Handouts/LectureNotes/part2-lec06.pdf http://www.mcs.vuw.ac.nz/courses/COMP201/2004T1/Handouts/LectureNotes/part2-lec07.pdf 狭義の Dynamic hashing では、hash 表を trie 辞書で 管理している。表に混んできた部分が出たら、そこで trie の枝を分岐させればよい。 -- 渡邊克宏 http://katsu.watanabe.name