mhattaによる
2008年01月21日 7時30分の掲載
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]
Free or not Free, that is the question.
親コメント
一方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が直接管理できるメモリアドレスは十分に広大であるので、それをカバーできる大きさの、かつ速く不揮発の主記憶装置さえあれば、ファイルシステムなど不要であるという論議です。
# さて、現実性は。
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がアルゴリズムとか知らない頭悪い人に見えてしまう。
親コメント
これとちがう? (スコア: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, おもしろおかしい)
と呼ぶのは老化の始まりかもしれないですね・・・・
親コメント
1兆件 (スコア:1, 参考になる)
人月が安いだけじゃね？ (スコア:1)
この人がいくらの給与をもらってるか知りませんが、この仕事を3ヶ月で3人くらいだとして9人月。
一人50万の給与だとして、450万円。
で、それの×10として4500万。そのように計算すると↑の数字はけっこう普通。
（ちょっと過剰に見積もりすぎな気もするけど）
多分この会社は人月の計算がおかしいか、見積もり時の倍率が過剰に低いんじゃないかなぁ。
エンジニアを安売りしているだけの気がする。
メンテナンスコストとか含まれてないだろうなぁ。
賛同はACで。反論はIDで。カルマボーナスはチキン。
安けりゃよい (スコア:1, 興味深い)
・あるメーカーは数千万円
・HOWSは数百万
の回答があったので、同じことが出来るのであれば安いほうがよいから発注した
というのがクライアント側のアクションでは。
そして、この方法がうまくいったら数千万円コストダウンできて万歳と。
詳しい見積もりしようが分からないので何とも言えないかもしれないけど、この方法の欠点ってどこにあるのでしょう。
・Microsoftが推奨してない：でも問題なく動いてるから
・Windowsのバージョンアップ or アップデートに対応できない：そんなこと普通では
・スケーラビリティがない：普通の方法に比べて1桁安いので、仕様追加してもそんなに高くつかないだろう
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, すばらしい洞察)
親コメント
Ajax builderで一躍脚光を浴びるベンチャー企業だそうですよ (スコア:1)
Re:Ajax builderで一躍脚光を浴びるベンチャー企業だそうですよ (スコア:2, 参考になる)
アドバルーン大好きなのはいいけど、アドバルーンすら作れてないわー
親コメント
MADO(QUOVIS) (スコア:2, 参考になる)
http://sdc.sun.co.jp/developers/spf/log/names.html#sa [sun.co.jp]
結構使われていたみたいなのですごいのかなと思ってました。
親コメント
InterSystems Caché® (スコア:1)
リレーショナル・データベースよりも高速にSQLを実行する、高パフォーマンスなオブジェクトデータベース [intersystems.co.jp]
って何なんだろう、という疑問を持ったまま、忘却の彼方に追いやっていたのだった。
ほんとにこれは何だったんだろう?
BFS... (スコア:1)
BFS (Be File System) について教えてください。 [haiku-talkers.net]
ファイル名以外にも自由にAttribute/Keyを設定できたりQueryで検索したりできるし＞BFS
「日本の廃道 [the-orj.org]」やってます。
やってみた (スコア:1)
使用言語：最近成長の Python 2.5.1 (Windows XP)
日本国憲法英語版 [kantei.go.jp]に出てくる単語が、UNIX(Solaris 9)から持ってきた /usr/dict/words に含まれるかどうかを検索。
辞書(25143語) -> ファイル作成 に 14.484 秒
日本国憲法英語版 (約5000語) の単語検索に、0.297秒
ちなみに、リストで検索（線形）すると 4.328秒なので、これより速いが、ディクショナリ（ハッシュ）を作って検索すると、0.063秒。
ファイル入出力があるので、遅くなるのはあたりまえだが、元記事で、100万件のインデックスをファイルで作るのは、時間がかかってたまらんと思う。
馬鹿なことをやって時間をつぶしてしまった。（ネタも終ってるので、読む人少ないだろうし）
Re:え？ (スコア:5, おもしろおかしい)
親コメント
Re:逆切れしてみる (スコア:2, おもしろおかしい)
小学生の頃、雑誌付録のエロい(小学生基準なので今思うとお色気程度ですが)ゲームを
どうやって隠そうかと思い、大量のディレクトリを作って深いところにインストールしようとしたら
HDDが満タンに・・・。
そのときディレクトリもディスク容量食うんだってことに気付きました・・・。
親コメント
Re:逆切れしてみる (スコア:3, 参考になる)
ディレクトリがフラグメンテーション起こした途端、ものすごいパフォーマンスダウンしやがったんですよ。
で、解決策は、予め全ファイルをサイズ０で作成しといて
（この時点でディレクトリは連続したクラスタを占有できる）
改めて各ファイルを上書き保存する、と。ああ懐かしい。
親コメント
XML DB などと比べての発言なんだろうか (スコア:1)
っていうコメントがありますが，Web2.0のどこに関係するのかとか，センサネットワークだったら取れる情報はほぼ定型なんだからそれこそRDBでいいんじゃないのかなとか，半定型だったとしてもXML DBを組み合わせた方がデータの利活用がしやすいんじゃないのかなとか反論したくなります．とはいえ実際にセンサネットワークに携わったことがないのでなにかISSEIだとぴったりなことがあるのかもしれませんが．
ペーストビン [windy.cx]
親コメント
Re:他の記事 (スコア:4, すばらしい洞察)
えー、本当かなぁ。
PostgreSQLでも MySQLでもインストールして、index まじめに張るだけジャン??
# そりゃ Oracle 入れればそういう金額になるけどさ。
ベースのソフトは無料だし、たかが数M entry に対して数百万もかけてチューンして良いなら、これぐらいの性能は普通に出ると思うんだが…。
fjの教祖様
親コメント
Re:え？ (スコア:1)
だよね！ 0バイトになるってことは 100% じゃないもんね！
# 圧縮率って、100MB->1MB が 100%なの？
親コメント
Re:ntfsにバグがあったとしたら？ (スコア:1, 参考になる)
もしも、データの特性（1件あたりの大きさや件数）からクラスタサイズやMFT予約領域のチューニングをしたりしてるなら、「NTFSの特殊用途のための運用技術｣として認めてもいいような気がしないでもない。
親コメント
Re:ntfsにバグがあったとしたら？ (スコア:1)
それは CreateFile (要は open) のパラメータに大文字/小文字を同一視しないというパラメータを設定していないから (標準は同等扱い) というだけですよ。
ただ、制限上大文字と小文字が違うだけのファイル名は同一ディレクトリに存在できない、というのもありますが。
あと、一応 (file ID)_(分割したデータのハッシュ) という形を取ってるようなので、デバイスファイル名 (con とか prn とか) とかぶる事はないでしょうね。
親コメント
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:で、実際のところ (スコア:1, 参考になる)
照合は100MB/sなんでディスクのシリアルアクセス速度に近い。というわけで
レコードサイズとか照合方法は知らんけどリニアスキャンなら早い。
でも、インデックス使うのなら（普通のDB）別に普通の速度。
今回のはインデックスというより検索キーが確定すると即アドレス（パス）が
取れるという構成らしいので、そもそもスキャンという処理はないんじゃ？
単にパス辿る時のエントリルックアップ時間だけだろう。
親コメント