開発メモ: IndexDB: 転置インデックスのためのDB
大震災の時分に何だが、Kyoto Cabinetベースで検索エンジンの核となる転置インデックスを作るのに適したDBを実装したという話。 転置インデックスとappend操作 多くの検索エンジンの核となる転置インデックスとは、検索語に一致する表現がどこに出てきたかという位置情報のリストを保持するものであり、検索語をキーとして位置情報リストを値とする連想配列である（転置インデックスを使わない検索エンジンもあるが）。この位置情報リストをposting listとか呼んだりするらしい。転置インデックスにもいくつか流儀があり、検索語をどのように切り分けるかで単語（分かち書き）方式とか文字N-gram方式とか呼ばれるものがあったりするが、いずれにせよ、小さいキーと、非常にでかい値を保持する連想配列を作ることには変わりない。 で、素朴に転置インデックスを作ろうとすると、検索対象の文書を解析しながら、得られ
開発メモ: Kyoto Cabinetのロック機構の改善
Kyoto CabinetはIO負荷が高い場合にCPU負荷も高くなりがちだという指摘を受けて、それを解決すべくロック機構を見直したという話。 スロットロック ハッシュテーブルの操作はハッシュバケット毎に完全に独立して実行できるのが強みだ。ハッシュテーブルは計算量が有利なだけでなく、並列性にも優れるということ。実際には下層のファイルIOで実装依存の排他制御が行われることになるが、ハッシュ層だけ見れば理想的な並列性を備えている。ただし、同じバケットに連なるレコード群の操作は互いに依存関係があるので、それらは一括して排他制御してやる必要がある。となると、バケット毎にロックを用意するのが理想だが、実際にはメモリを節約するために、予め決めた数のロックを用意して、ここのロックに複数のバケットを割り当てる構成をとる。リソース空間をスロットに分けるというイメージから、これをスロットロックと呼ぼう。 スロッ
開発メモ: MapReduce on Kyoto Cabinet
Googleで実用化されHadoopで流行しているところの分散処理フレームワークMapReduceをKyoto Cabinetにおいても実現してみた。その解説。 ローカルなMapReduce MapReduceは多数のマシンが連携して分散処理を行うためのフレームワークなので、プロセス組み込みDBMであって分散など全く関係ない世界に生きているKCでMapReduceを実行して意味があるのだろうか。答えは、「あんまりない」である。それにもかかわらず実装したのは、何となく話題性がありそうだからってのが最大の理由なのだが、もうひとつ理由がある。 スクリプト言語で集計処理をやろうとすると、めっちゃメモリ食うしCPUパワーを使うわりに遅いからである。1000万件のソートってだけでスクリプト言語だと結構辛いからね。そこで、MapReduceフレームワークをC++で実装してmapとreduceだけをスクリ
はじめてのRuby(Rack)挑戦記録 - クリティカルスピード開発日誌
5:07 おはようございます。 今日は今までやろうやろうと思って放置していたRubyに初挑戦します。 perl使いなので書き方や考え方がperlに偏っているかもしれませんがご了承下さい。 5:10 まずはRubyのインストール sudo apt-get install librack-ruby 5:13 hello world 参考にしたのはこのページ http://route477.net/d/?date=20080716 mkdir rack cd rack vi criticalspeed.rb rbというのはperlでいうところのpmなのだろうか？ →plのようなものらしい(by IRC) criticalspeed.rb require 'rubygems' require 'rack' class CriticalSpeed def call(env) [200, {"Cont
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Kyoto Cabinet: Kyoto Cabinet: a straightforward implementation of DBM
