タグ

ブックマーク / fallabs.com (16)

  • 開発メモ: IndexDB: 転置インデックスのためのDB

    大震災の時分に何だが、Kyoto Cabinetベースで検索エンジンの核となる転置インデックスを作るのに適したDBを実装したという話。 転置インデックスとappend操作 多くの検索エンジンの核となる転置インデックスとは、検索語に一致する表現がどこに出てきたかという位置情報のリストを保持するものであり、検索語をキーとして位置情報リストを値とする連想配列である(転置インデックスを使わない検索エンジンもあるが)。この位置情報リストをposting listとか呼んだりするらしい。転置インデックスにもいくつか流儀があり、検索語をどのように切り分けるかで単語(分かち書き)方式とか文字N-gram方式とか呼ばれるものがあったりするが、いずれにせよ、小さいキーと、非常にでかい値を保持する連想配列を作ることには変わりない。 で、素朴に転置インデックスを作ろうとすると、検索対象の文書を解析しながら、得られ

    kgbu
    kgbu 2011/03/11
    インデックス作成の際のappendに関するバッファリングをうまいことしてくれるらしい
  • 開発メモ: Kyoto Cabinetのロック機構の改善

    Kyoto CabinetはIO負荷が高い場合にCPU負荷も高くなりがちだという指摘を受けて、それを解決すべくロック機構を見直したという話。 スロットロック ハッシュテーブルの操作はハッシュバケット毎に完全に独立して実行できるのが強みだ。ハッシュテーブルは計算量が有利なだけでなく、並列性にも優れるということ。実際には下層のファイルIOで実装依存の排他制御が行われることになるが、ハッシュ層だけ見れば理想的な並列性を備えている。ただし、同じバケットに連なるレコード群の操作は互いに依存関係があるので、それらは一括して排他制御してやる必要がある。となると、バケット毎にロックを用意するのが理想だが、実際にはメモリを節約するために、予め決めた数のロックを用意して、ここのロックに複数のバケットを割り当てる構成をとる。リソース空間をスロットに分けるというイメージから、これをスロットロックと呼ぼう。 スロッ

    kgbu
    kgbu 2011/02/13
    おー、どうやってCPUの使用率が下がったのか、具体的なところを掘りたくなるような記事だ。
  • 開発メモ: Kyoto TycoonでテーブルDBを実現する

    Kyoto Tycoonで、RDBMSのテーブルのように複数のコラムを持ったレコードを扱ったり、特定のコラムを対象にセカンダリインデックスを張ったりすることもできるという話。 テーブルDB Tokyo CabinetおよびTokyo Tyrantでは、テーブルDBという実装があった。最も率直なKVS(永続化連想配列)の実装としてお馴染みのTC/TTではあるが、valueに構造を持たせることによってマルチコラムを実現し、さらに更新処理にフックをかけてセカンダリインデックスを自動的に管理できるようにもしていた。結果として、「ドキュメント指向DB」とか「スキーマレスDB」とかいったような、ゆるふわな感じの用途で便利に使えるツールになっていると思う。 しかし、KyotoシリーズではテーブルDBは実装しない方針である。多機能すぎてメンテが大変だからだ。アプリケーション寄りの機能を提供するということは

    kgbu
    kgbu 2011/01/28
    ここまで書いてくれていると、これをscrapbookしとくだけで安心してしまいそうな自分が怖いwアトミックな操作についての実例も嬉しい、つかさすが。
  • 生活メモ: 就職することにした

    長らくニートだったが、就職先が決まったということで、代官山のレストランでと娘にお祝いしてもらった。うれしい。そして、新しい道に踏み出すという新鮮な気持ちが何とも心地よい。 2011年2月1日付けで、Googleに入社する。その経緯について記述しておく。個人的事情をわざわざ晒す必要もないのだが、お世話になっている皆様やOSS関連や個人事業関連で関わりのある方々への報告ということでキーを叩く。 経緯 昨年7月末に前職を辞して、自作のOSS製品のデュアルライセンス販売でっていくべく開発作業や事務作業を半年ほど行ってきた。しかし、地価と物価の高い東京という都市に子とともに暮らせる収入を継続して得ていくにはあまりにも頼りないビジネスモデルであるため、それを業にすることは断念した。 より正確に言えば、当初からOSSでっていけるとは思っていなかったので、ライセンス販売はに任せて俺は就職できる

    kgbu
    kgbu 2011/01/19
    生活の安定っつーことで、めでたい。
  • 開発メモ: もし自営業の男子プログラマがKVSで「ブログサービス」を書いたら

    Webサービスの典型例でありCMSの典型例であるブログサービス。それを実装するための指針が示せれば、その他のサービスを開発する際にも大いに参考になることだろう。 データ構造 単純なブログサービスのデータノードとしてKyoto Tycoonのサーバ群を用いることを想定する。ブログの個々の記事は以下の属性を持つものとする。 著者のユーザID(uint32) 投稿日時(uint32) 題名(text) 文(text) コメントリスト(シーケンス) 各コメントは、コメントした人のユーザIDと文からなる データノードに対する問い合わせは、「あるユーザの最新記事を降順で5件くれ」というのが典型である。「降順で」という順序に対する要求があるのでB+木を選択し、連想配列のキーは、ユーザIDと投稿日時を連結したものとする。単純化のために、各々を10桁の10進数文字列をコロンで区切って並べて、全体で21バ

    kgbu
    kgbu 2011/01/14
    マネージャベースのスケールアウトかー、AWS上にフレームワーク作ったら使う人はいるだろうな。新たなHerokuつーか、普通にブログサービス作るときにもコスト面で優位性出したければこういう方向もありかなぁ。
  • 開発メモ: スレーブエージェントによるKTからMySQL等へのレプリケーション

    Kyoto TycoonからRDBMS等の他製品に対してレプリケーションを行う方法について述べる。 カスタマイズ機能群の最後のパーツ 以下のイラストのように、Kyoto Tycoonには、カスタマイズ性を高めるための様々な機能が実装されている。 HTTPの既存プロトコル上で任意のデータベース操作処理を実現するための「スクリプト言語拡張」。ユーザ定義の任意のプロトコルで任意のデータベース操作処理を実現するための「プラガブルサーバ」。既存のデータベース操作指示に対して任意の処理を行うための「プラガブルデータベース」。これら3つの機能を使えば、KTのほぼ全ての機能の振る舞いをユーザ定義のものに差し替えることができる。かなり究極的なカスタマイズ性を既に備えていると言える。 今回加わったのは、KTの外部の別システムとKTを連携させるための機能である。KTで更新ログを有効にすると、KTのデータベースに

    kgbu
    kgbu 2010/12/23
    Rubyのサンプルあり。ピーク負荷の高いキャッシュサーバーのバックエンドに永続化用のDBを置く構成を取りたい場合に、なじみのあるDBMSを使えるのは結構大事かもしれん。ここまで楽しくいじれるDBは、かつて無かったかも
  • 開発メモ: memcachedプロトコルをKTにプラグインする

    高効率キャッシュサーバ兼データベースサーバであるKyoto Tycoonのネットワーク通信機構をプラグインで切り替えられるようにして、memcachedプロトコルにも対応したというお話。 プラガブルサーバ Apacheは、様々なモジュールを後付けのプラグインで組み込むことで、非常に柔軟に機能追加を行えるようになっている。MySQLもストレージエンジンをプラグインで切り替えられるようになっていて、非常に柔軟なソリューションが提供できるようになっている。そのようなプラグインできるモジュールをプラガブルモジュールと呼ぶことにしよう。 同じように、KTでもストレージエンジン(DBM層)をプラガブルモジュールにする予定ではあるが、今回はストレージエンジンの話ではない。逆に、ネットワーク層をプラガブルモジュールにしてしまうのだ。そうすると、任意のプロトコルでデータベースを操作できるようになる。 DBM

    kgbu
    kgbu 2010/12/12
    memcachedのレプリケーションや永続化の決め手なんじゃまいか。PHPのセッションサーバプラグインも欲しくなった。
  • Kyoto Cabinet: Kyoto Cabinet: a straightforward implementation of DBM

  • 開発メモ: MapReduce on Kyoto Cabinet

    Googleで実用化されHadoopで流行しているところの分散処理フレームワークMapReduceをKyoto Cabinetにおいても実現してみた。その解説。 ローカルなMapReduce MapReduceは多数のマシンが連携して分散処理を行うためのフレームワークなので、プロセス組み込みDBMであって分散など全く関係ない世界に生きているKCでMapReduceを実行して意味があるのだろうか。答えは、「あんまりない」である。それにもかかわらず実装したのは、何となく話題性がありそうだからってのが最大の理由なのだが、もうひとつ理由がある。 スクリプト言語で集計処理をやろうとすると、めっちゃメモリうしCPUパワーを使うわりに遅いからである。1000万件のソートってだけでスクリプト言語だと結構辛いからね。そこで、MapReduceフレームワークをC++で実装してmapとreduceだけをスクリ

    kgbu
    kgbu 2010/11/02
    スクリプト側でやるより高速だし効率もええよ。という話。KC側では分散はやってない。上位層でさらにreduceするなら分散可能だろうか<元データ分散は?気軽に試せてmap reduceに慣れる機会が増えるのはいいことかも。
  • Technical Memo: Memory Saving Associative Array by Kyoto Cabinet and MessagePack

    Kyoto Cabinet features on-memory database which can be used as associative array of strings. MessagePack is a binary-based efficient object serialization library. Combination of the two provides you associative array to contain generic objects. Space Efficiency of Kyoto Cabinet Let's suppose that we should manage 1 million simple records whose key and value are 10 bytes strings. The following is a

    kgbu
    kgbu 2010/10/26
    連想配列用途ならspaceは5分の1すか。この組み合わせで流行るとHDDベンダーさん以外の世の中は幸せかもしらん。
  • 開発メモ: 「OSSライセンス例外」の考察

    Kyoto CabinetはGPLv3と商用ライセンスのデュアルライセンスにして、プロプラな製品に組み込む際にはお金をいただくという事業をやっていこうと思っている。 GPLv3を採用したことで、プロプラ製品によるフリーライドを抑止する力が働くのは好都合なのだが、一方でどんどんフリーライドしてほしい他のOSS製品に対しても同様の抑止力が働いてしまうことがあり、ちょっと勿体ないなと思っている。 他のOSS製品にもっと気軽にKCを採用してもらいたい。具体的には、ネットワーク越しにアクセスする「データベースサーバ」的な製品に、もっとKCを採用してもらいたい。もっと具体的に言えば、kumofsとかROMAとかflareとかその他何たらクラウドとかに採用してもらえるようにしたい。それにあたって、ライセンス上のハードルを取り除きたい。 そこで、「OSS製品とKCをリンクする場合において、その製品をGPL

    kgbu
    kgbu 2010/10/19
    twitterで見ていた話、どうやってまとめようかとなやんでいた。大変ありがたい。
  • 開発メモ: HTTP記録機能付きプロクシによるレプリケーション

    HTTPプロクシに更新ログを取らせれば、HTTPベースのいかなるサービスの内部状態もレプリケーションできるんじゃないのか? という検討の過程を晒してみる。 背景 保守性の観点からKyoto Tycoon自体にはレプリケーション機能を持たせないことにしたが、実際のユースケースではレプリケーションが欲しくなることが多いこともわかっている。なので、外部機能によって何とかレプリケーションを実現したい今日この頃である。 KTにレプリケーションを実装しないもう一つの理由は、レプリケーションのための更新ログを記録するための処理がDBの更新処理よりも重いという末転倒なことになっているからである。更新ログはレコードそのものに対して冗長なのでwriteの量も多いし、シーケンシャルアクセスなのでディスクには優しいが、データが際限なく増えるのでそれでも重い処理になる。また、DBはレコード単位の整合性だけを確保す

    kgbu
    kgbu 2010/10/15
    すでにあると思っていても、そもそものはじめから考えていくのは楽しそうである。
  • 開発メモ: Kyoto Tycoonのプロトコル仕様

    TTではpure Ruby版とpure Perl版のクライアントライブラリを自分で実装していたが、KTでは各種pure実装は自分では書かないことにする。私はC++版のクライアントライブラリを作成しメンテナンスするが、その他の言語に関しては、その言語で生活していて腕に覚えのある方々にお任せしたい。その前提として、プロトコルを明らかにしておく必要がある。英文の仕様書を後で書くが、そのたたき台としてまずは日語で書いてみる。 ---- 概要 KTのサーバプログラム(ktserver)は、HTTPに基づいてクライアントと通信を行う。デフォルトのサービスポートは1978番だが、ユーザの設定によって変わることもある。サーバは、HTTP/1.0およびHTTP/1.1のリクエストを解釈することができ、それに対応するレスポンスを返す。 HTTP/1.1のリクエストにおいてContent-Typeヘッダの値が

    kgbu
    kgbu 2010/10/06
    自分の得意な言語でバインディングを作る練習に好適と思える。すぐ動きそうだし、使えるし。とか書く暇があったらやってみよう>俺。あと、動的リンクですらないからライセンスの自由度も高い。
  • 開発メモ: Kyoto Tycoonベータ版リリースすた

    ここのところ必死こいて作り込んでいたKyoto Tycoonだが、主要機能を実装しきって文書もそこそこ書けてきたので、ベータリリースということにした。プロジェクトページもちゃんと作ってある。 公式には英語の文書しか作らない方針なのだが、それだと国内ではなかなか使ってもらえないので、この場でチュートリアルを書いてみる。 Kyoto Tycoonとは プロセス組み込み軽量データベースライブラリであるKyoto Cabinetをネットワーク越しに利用できるようにするためのツールキットである。KCのデータベースを内部に持ったサーバプログラムと、それに接続してデータベースを操作するためのクライアントライブラリからなる。また、コマンドラインからサーバにアクセスするためのユーティリティもついてくるので、簡単に使い始められる。 製品コンセプトは、「永続的キャッシュサーバ」もしくは「memcachedの永続

    kgbu
    kgbu 2010/10/04
    読みやすいチュートリアル。これがあるからmemcachedではなくてこっちを使う、という人が居てもいいかもしれない。PHPのセッションストレージとか、これにしようかな。
  • 開発メモ: Kyoto Tycoonの設計 その参

    前回実装した「クライアントソケット」「サーバソケット」「ソケット監視装置」のAPI群に、さらに「スレッドプール内臓タスクキュー」を組み合わせて、「多重I/Oマルチスレッド汎用TCPサーバ」の機能を司るクラスを作ってみた。 スレッドプール内臓タスクキュー 整合性を保ちつつ並列処理を行うために、「タスクキュー」とか「ジョブキュー」とか呼ばれる仕組みがよく用いられる。次々と発生するタスクリストをキューに入れていくスレッドと、キューに入っているタスクを次々と取り出して処理するスレッドが登場するモデルだ。 Kyoto製品群においては、スレッドの抽象化はKyoto Cabinetが担当するので、スレッドプール内臓タスクキューの実装はKCにて行うことにする。具体的には、以下のAPIを定義する。 class TaskQueue { public: // タスクを表す内部クラス class Task { p

  • 開発メモ: Kyoto Tycoonの設計 その壱

    memcachedのように一時的なデータを高速に扱えながらもデータをファイル上に永続化できるサーバとして、「Kyoto Tycoon」という製品を開発することにした。もちろん、Kyoto Cabinetをストレージにしたネットワークサービスを提供するものである。実のところ、決まっているのはその点と名前だけで、設計は何も決まっていない。ここにあーだこーだ書きながら詰めていこう。 背景 先に明言すべきは、これはKyoto CabinetをストレージにしたTokyo Tyrant相当の製品ではない。TTはキャッシュサーバではないので、memcachedで言う所のexpireをサポートしていない。しかし、Kyoto Tycoonはキャッシュサーバとしての利便性を追求し、もちろんexpireをサポートするとともに、レプリケーションなどの重量級の機能は割愛する。 なぜこれを作るかという理由は大きく二つ

    kgbu
    kgbu 2010/08/21
    俺レベルだと、これ読むとmemcachedについて理解が深まってしまうw
  • 1