データをすべてファイル名扱いにして高速検索を実現? 187
ストーリー by mhatta
memcachedとかtmpfsとか… 部門より
memcachedとかtmpfsとか… 部門より
backslashdot 曰く、
ちなみに、この手法を応用(?)してどんなデータも圧縮率100%のファイル圧縮ツールを作った人もいます。ITproに、「既存のDB技術と一線を画し、高速検索を実現する」というふれこみのデータ検索技術が紹介されている。 HOWSという企業が開発した「ISSEI」というVisualBasicで開発されたシステムらしいのだが、 高速検索性を最優先とするために、OSの基本機能であるファイル名検索に目を付け、 そこで検索対象となるファイルに含まれるデータそのものを全て「ファイル名」として管理することにしたということだ。 ファイルに含まれるデータそのものを、62進数(アルファベット大小文字+数字で26*2+10=62ということか?)の文字列に変換し、それらをファイル名の集合体として別途管理するらしい。 確かにこの方法であれば、HDDのファイル本体にはアクセスすることがないとも言えるわけだが、 記事の最後にあるように「次はOSメーカーと共同開発し、ISSEIをOSの標準機能として盛り込みたい。最終的にはISSEI専用チップをメーカーと開発するのが目標だ」という方向が望まれるような、画期的技術と言ってよいものだろうか。
ファイル名を見ただけで (スコア:5, すばらしい洞察)
笑いどころ (スコア:5, おもしろおかしい)
なんという手作業
＞ISSEIはマイクロソフトの「VisualBasic」で開発した。
（中略）
＞処理の高速性を最優先し
(;｀･ω･)
＞最終的にはISSEI専用チップをメーカーと開発するのが目標だ
そこまでするなら、この手法を取っている意味が無くなるのでは･･･？
Re:笑いどころ (スコア:2, おもしろおかしい)
◆IZUMI162i6 [mailto]
一方MSは･･･ (スコア:5, おもしろおかしい)
･･･いや、しようとした。
それはCAS (スコア:5, 興味深い)
ahref=http://en.wikipedia.org/wiki/Content-addressable_storagerel=url2html-10207 [slashdot.jp]http://en.wikipedia.org/wiki/Content-addressable_storage>
そのものでございますな。『オブジェクト』と言う名のバイト列を見つけ出すのに、そいつが保持しているデータそのものを利用する、という。
# 普通は高速に検索するために「ファイル名」に相当する部分には
# ハッシュ値を使い、ファイル名そのものにデータを乗っけたりは
# しないものですが…
EMC の Centera とか、Tivoli Storage managerとか、
Linus の git とかも CAS の一種です。
CAS のいい所は、一度書いたら「データを変更できない」事。
データを変更しようとすると「別のファイル名」になってしまう。
…と言うわけで。多分この特許は通らないか、通るとしたらよほど
審査官が間抜けだと思います。日本語版にはまだ無いとはいえ、
ほぼ同案が Wikipedia に載っているんですから。
fjの教祖様
いっそのこと (スコア:4, 参考になる)
なんて論議もありましたっけ。
論者曰く、現在のCPUが直接管理できるメモリアドレスは十分に広大であるので、それをカバーできる大きさの、かつ速く不揮発の主記憶装置さえあれば、ファイルシステムなど不要であるという論議です。
# さて、現実性は。
Re:いっそのこと (スコア:1)
>それをカバーできる大きさの、かつ速く不揮発の主記憶装置さえあれば、ファイルシステムなど不要であるという論議です。
ファイルの便利なところは、情報にシステム上で一意な名前がつけられるところだと思うのです。
現在のOSのまま、ファイルシステムがなくなっちゃうとデータのやり取り手段を
なんとかしなくてはいけなくなりますね・・・・
# 名前の管理サービスみたいなものになるのかね？
Visual Basic 製ということは…… (スコア:4, すばらしい洞察)
Visual Basic 製と言う事は NTFS 上で利用する事になると思うのですが……。
肥大化した MFT によりディスク領域が圧迫され、しかも別途デフラグソフトを購入しないとデフラグが出来ない (OS 標準のデフラグは MFT の整理をしない) 物が出来上がったと言う事ですか。
RDB でもフルテキストインデックスとか、今時サポートしていない方がレアだと思うんですけどねぇ。
NTFS なら小さなファイルなら MFT に突っ込んじゃうのだし、それこそ Windows Desktop Search や Google Desktop Search と連動させてデータを小さなファイルとして保持させ、検索自体は WDS や GDS とかに任せた方が効率的なんじゃないかと思う。
多少データが増えたところで、単なるミラーリング & インデックス再生成程度で環境移行も出来ちゃうし。
つーかこれ、書庫ファイルでバックアップ取ろうにも zip とかじゃファイル名は圧縮されないから tar + gzip/bzip2 とかじゃないと悲惨だよね。NTFS 上に Unicode ファイル名で記録すると約 32,000 文字とか使えちゃうから、下手な fs 上じゃ展開できないんじゃない?
# 説明されたのに金を出した客の方がすごいと思う。
Re:Visual Basic 製ということは…… (スコア:5, 参考になる)
%temp%の中に大量に一時ファイルを作って後片付けしない行儀の悪いツールをデバッグしたことがありますが、場所が場所だけに何をやらせても遅くなってて大変でした。
署名スパムがウザい？アカウント作って非表示に設定すればスッキリさ。
NTFSでのファイル名のサーチって速いんだ (スコア:2)
幾ら工夫したとはいえ、RDBがファイルシステムに負けるのは信じられないですが。
[1] http://www.squid-cache.org/ [squid-cache.org]
[2] Ian Dowse, David Malone:
Recent Filesystem Optimisations in FreeBSD,
USENIX 2002 Annual Technical Conference, Freenix Track,
Pp. 245–258, June 10-15, 2002
NTFS (スコア:4, 興味深い)
苦肉の策なんじゃないかなあ（私なら50万円くらいでごにゃごにゃ）。
NTFSは検索は速いですけど追加と削除が遅いですね。
NTFSでハードリンク張りまくってバックアップとって、
いざ削除しようとしたら100万ファイルくらいの削除に2ヶ月かかりました。
マジで。
ネットワーク上では (スコア:3, 参考になる)
RFC1924 [ocn.ne.jp] （IPv6アドレスを文字で短く表現）の合わせ技で同じことが出来るかな？
どちらも4月1日発行モノ。
Re:ネットワーク上では (スコア:2, 興味深い)
この記事もプログラムの改修を最小限に押さえて高速化を図るのにOSが持っている効率的なアルゴリズムを活用したとかいう話ならわかるけど、何と言うかCTOがアルゴリズムとか知らない頭悪い人に見えてしまう。
data URI (スコア:1)
よーし，これですべてのデータがブックマークに入るぞ！
いや，ジョークRFCではなくて，これはちゃんと機能するものです．念のため．
屍体メモ [windy.cx]
これとちがう? (スコア:3, 興味深い)
Unix Magazine「インターフェイスの街角」
1999年11月号 「シグナチャを用いた超お手軽検索システム」
と根本的思想は一緒?なのかしら?
ストップウオッチ… (スコア:2, すばらしい洞察)
開発するほうも、それで満足してしまう顧客も、日経の記者も。
これで高速化できてしまうような質の社内システムとやらがはびこっているのが現実と言うことですか。
Re:ストップウオッチ… (スコア:2, 興味深い)
そういう契約だったのかしらん？
個人が満足してるならいいけど (スコア:3, おもしろおかしい)
Re:ストップウオッチ… (スコア:3, 参考になる)
ＯＳのファイル検索機能の不具合であって、うちでは対応できません、なんて事にならないかな。
ＯＳメーカー側もそんな目的外使用に対応してくれるかどうか。
Web2.0時代の技術らしい (スコア:2, おもしろおかしい)
＃素早く考えすぎたのだろう．
62進数… (スコア:2, 興味深い)
実際には、Base64は A-Za-z0-9+/を使うため、/をファイル名に使えないので、ファイル名への符号化には使えないんだが、
Imap4ではメールボックス名をファイル名に使っても問題ないように、
メールボックス名は/の代わりに,を使うUTF-7(UnicodeをBase64で表現する方式)の修正版 [www.lins.jp]で表現する仕様になってます。
#パスワード(というか復活の呪文的なもの)に「lとIと1」「Oとo」「9とQ」といった紛らわしい文字を使わないようにした37進数での符号化を使ったことがありますが、コードが無駄に複雑になってしまいました。
#もうちょっと減らして32進数にしとけばよかったと気付いた時のは後の祭り…
62進数エンコード (スコア:2, すばらしい洞察)
みんなナンダカンダ言ってるけど (スコア:2, 興味深い)
# 技術的には自慢できるようなもんはないがな。
みんな普通にやってることじゃ？ (スコア:2, 参考になる)
＃さすがに、見た目同じでデータ的に違うものは無理だけど。JPEGで再圧縮かけたやつとか。
あと、そのファイルの中から壁紙として使うものを、別のディレクトリにシンボリックリンクで集めたりしてますが、そのシンボリック名にMD5値を使っています。こっちは異なるディレクトリに中身の違う同名のファイルがあった場合への対策ですが。
ファイル名にファイルの内容を直接反映させたり結びつけたりなんて、普通にみんなやってることじゃないんですか？
技術というよりは (スコア:1, 興味深い)
Re:技術というよりは (スコア:3, 興味深い)
ところで言われているようにRDBって限界なのでしょうか？
Re:技術というよりは (スコア:3, 参考になる)
そもそも、構造化不十分な(あるいは、まったく構造化されていない)テキストデータを扱うような場合、それを二次元の表に格納しても、ほとんど得はありません。テキストファイルの中身をMS-Excelに貼り付けるようなもの。
たとえば、全文検索が目的なら、RDBより接尾辞木に格納した方がマシ。元々データ構造の目的が違うんだから。
ただ、既成のRDB製品はたくさんあって、RDB技術者がたくさんいるので、目的外使用だけどRBDが使われていて、それでも性能は上げなきゃいけないから、RDBにいろんなデータ構造(インデックス)をくっつけて誤魔化しています。
まあ、その誤魔化しは、そこそこ巧く行ってるので、まだまだRDBは限界とは言えないんじゃないかな。
Re:技術というよりは (スコア:2, おもしろおかしい)
Re:技術というよりは (スコア:2, おもしろおかしい)
Re:技術というよりは (スコア:2, おもしろおかしい)
あ、あれ、いつの間に年明けたんですか・・・？
20年くらい前に (スコア:1, 参考になる)
Re:20年くらい前に (スコア:2, 参考になる)
一言で説明すると (スコア:1)
ディスクの管理領域はメモリにキャッシュされている率が高く、そこをストレージ領域に使った場合は確かに高速にアクセスできるでしょう。オンメモリデータベースで難しい、不揮発性メモリとの同期の部分をOS任せにできるので実装も楽になるかな？でも、人に自慢げに話せる実装ではなく、恥ずかしくて人に言えない類の実装だと思うんだけどねぇ。
Re:一言で説明すると (スコア:3, すばらしい洞察)
いや，WindowsのIndex Serviceを使用していると，ファイル名による検索が
高速化されることに気がついて，それをRDBのかわりにつかった検索システムを
構築した，ということではないかと。
問題は，そのIndex Serviceの内部で使われている技術がRDBの技術そのもので
あることを知らずに，「DB技術の限界を超える」とかいってしまっているところ。
あれ (スコア:1)
Re:あれ (スコア:2, おもしろおかしい)
と呼ぶのは老化の始まりかもしれないですね・・・・
Re:あれ (スコア:1)
>Nemoは「初心者にとって階層フォルダ構造の概念は理解しにくい」という
>前提に立って開発されており、フォルダ分けせずに一カ所にまとめておいた
>ファイルに対し、タイムスタンプ、ファイルタイプ、ラベルなどの属性を
>使ってアクセスするという方法を提案しているようです。
ちょっと違ったなぁ。
Re:え？ (スコア:5, おもしろおかしい)
逆切れしてみる (スコア:1)
# 発想の転換といえば聞こえはいいが。
# 調子に乗ってハードディスクの中のデータを全部これで１００％圧縮しようとして、途中でハードディスクが一杯になってしまって？？？な人なんているのだろうか。
# 実行形式（EXEやCOM）を圧縮した後で、実行できないことに気付く奴はさすがにもう居ないとは思うが。
Re:逆切れしてみる (スコア:2, おもしろおかしい)
小学生の頃、雑誌付録のエロい(小学生基準なので今思うとお色気程度ですが)ゲームを
どうやって隠そうかと思い、大量のディレクトリを作って深いところにインストールしようとしたら
HDDが満タンに・・・。
そのときディレクトリもディスク容量食うんだってことに気付きました・・・。
Re:逆切れしてみる (スコア:3, 参考になる)
ディレクトリがフラグメンテーション起こした途端、ものすごいパフォーマンスダウンしやがったんですよ。
で、解決策は、予め全ファイルをサイズ０で作成しといて
（この時点でディレクトリは連続したクラスタを占有できる）
改めて各ファイルを上書き保存する、と。ああ懐かしい。
Re:安けりゃよい (スコア:5, 興味深い)
に尽きるのではないかと。
1) Security 上の問題がある。
普通なら「ファイルが open できなきゃ安全」なはずのデータが全部曝されている。何しろ、ファイル名を変更できればデータ変更は出来るわけですから。
2) PATH 名検索が死ぬほど遅いと思う。
例えば、データ中に "fjの教祖様" が入っているレコードが欲しければ、
"*fjの教祖様*" という PATH を探すことになるのだろう。が、
それは結局 O(n) の検索になるんじゃないのか?
完全一致ならば HASH とか NTFS の path 名が平衡木管理になっているのとかで
DBMSでindex を張った状態と同じになるのだろうが、任意の
「真ん中のデータ」が一致しているのを探すのに必要な処理は、
馬鹿正直なサーチぐらいしか実装されていないと思うんだ、NTFSには。
これは根本原理に問題があると言うことなので、救いがたい。
3) Transaction 処理ができないのでは…
いや、これは VB で書いている部分で頑張るのかもしれないが…。
重たそうだな。
4) で、実際のところ、ファイルを open して中身を検索して close して…を繰り返すのとどっちが早いのさ??!
ここで比較するべきなのは、ファイルを open/close する部分を
非同期 システムコールで実装して、同時に複数走らせた場合。
旧来の同期型 open/close だと一度に1つのファイルしか開けない/閉じれない
のでそこが重たくなるが…。うーむ。本当に早いか?? これ…
と言うわけで、大いに疑問だ。DBMSの事もファイルシステムの事も本質的に判っているとは思えない…。
fjの教祖様
画期的な (スコア:3, すばらしい洞察)
Re:安けりゃよい (スコア:2, 参考になる)
んー、どうでしょうね。
ACL でフォルダに対して適切な制限が与えられていれば、ディレクトリリストの一覧は取れません。
ただ、OS 側がインデックス化しているためインデックスの問い合わせ権限があると情報が取れる可能性はあり。
そこは Windows Index Search が頑張るところなので。
それは用途が違うからどうでもいいんです。
これって locate や find と grep のどっちが早いの? って話ですよ。
Re:安けりゃよい (スコア:2, すばらしい洞察)
Re:他の記事 (スコア:4, すばらしい洞察)
えー、本当かなぁ。
PostgreSQLでも MySQLでもインストールして、index まじめに張るだけジャン??
# そりゃ Oracle 入れればそういう金額になるけどさ。
ベースのソフトは無料だし、たかが数M entry に対して数百万もかけてチューンして良いなら、これぐらいの性能は普通に出ると思うんだが…。
fjの教祖様
Re:ntfsにバグがあったとしたら？ (スコア:2, 参考になる)
そんな制限ありませんよ。大文字と小文字を区別するようにパラメータ指定して作成すると同居できますが、大文字と小文字を区別するようにパラメータ指定して開かない限り片方しか開けなくなるので普通やらないだけです。
ついでにそのパラメータを指定すると予約デバイス名とかぶるファイル名も作成できます。もちろん同じパラメータを指定しない限り開けません。
Re:ntfsにバグがあったとしたら？ (スコア:3, 参考になる)
それは API で利用可能であるかどうかという意味での話であって、技術資料として出ている制限事項 [microsoft.com]とは別の話です。
"Do not use the following reserved device names for the name of a file:..." と "Do not assume case sensitivity. ..." の辺り。
どちらも「普通やらない」とか「普通に操作できない」とかではなく、制限事項に当てはまります。
Re:Ajax builderで一躍脚光を浴びるベンチャー企業だそうですよ (スコア:2, 参考になる)
アドバルーン大好きなのはいいけど、アドバルーンすら作れてないわー
MADO(QUOVIS) (スコア:2, 参考になる)
http://sdc.sun.co.jp/developers/spf/log/names.html#sa [sun.co.jp]
結構使われていたみたいなのですごいのかなと思ってました。