開発メモ: 辞書検索システムを作ろう （実装編）
永続連想配列の一実装であるKyoto Cabinetを用いた辞書検索システム（仮称：kcdict）の機能について前回の記事で説明した。今回は辞書検索システムの内部の実装について紹介する。 データベースの構造 デフォルトでは検索語の前方一致検索を行うので、前方一致検索が高速に行えるデータ構造が求められる。辞書順の比較関数を使ったB+木はまさにその目的に叶うので、それを採用する。 辞書データには同じ検索語を持つ複数のエントリが存在するという、いわゆる重複キー状態が発生するが、KCのB+木は重複キーを許さない実装になっている。そのため、検索語の末尾に識別用の文字列を連結して、各々のエントリのユニーク性を確保する。同一検索語のエントリ同士の順序をユーザが操作できるようにするためにもこの識別用文字列は利用される。各々のエントリにはユーザが任意の数値を付与することができるようになっており、同一検索語の
開発メモ: 辞書検索システムを作ろう （機能編）
英和辞書や和英辞書などの辞書データは、検索文字列をキーとして使って、その値である説明文を取得するための連想配列である。Kyoto Cabinetを使うと非常に簡単に辞書検索システムを実装できることを2回に渡って示したい。これを読めば、英辞郎やWordNetのデータを使って自分の好みの辞書検索システムを簡単に作れるようになるはずだ。第1回目は、辞書検索システムの仕様策定と実際の機能について説明する。 デモ WordNetを使った英英辞書の検索システムを設置したので、まずは使ってみて欲しい。前方一致検索や完全一致検索はもちろん、曖昧検索や正規表現検索もできるスグレモノである。そして、早い。このサーバは、さくらVPSの一番安いプランで動作させているのだが、それでも大抵の動作がほぼ一瞬で完了するのがおわかりいただけるだろう。 http://fallabs.com/kyotocabinet/dict
開発メモ: プレーンテキストデータベースとMapReduce
お手軽な並列処理のフレームワークとしてKyoto CabinetのMapReduce機能をお勧めしまくっている最近のFAL Labsである。今回はプレーンテキストファイルを使ってMapReduceを動かす方法について説明する。 MapReduceの入出力 MapReduceのmapper関数は、key-valueのペアを入力とするので、いわゆるkey-value storeであるDBMを入力として利用するのは率直なアイデアと言えるだろう。しかし、mapper関数に渡す入力はキー毎に整理されている必要はなく、実際には入力データはバイト列の集合でありさえすれば何でもよい。例えば、改行区切りのプレーンテキストファイルでもよい。mapperに渡すデータを作るためにわざわざDBM形式のデータを作らなきゃならないなんて面倒くさい。 とはいえ、KCのMapReduceはDBM形式のデータを前提として実装
開発メモ: memcachedメッセージキューの詳しい使い方
memcachedプロトコルでメッセージキューが実現できるという話を前回したが、今回はその具体的な使用方法を解説してみる。 サーバを起動する まずはサーバを起動しないと始まらない。典型的には以下のコマンドで立ち上げるとよい。 $ ktserver -th 1 -ls \ -plsv /usr/local/libexec/ktplugservmemc.so \ -plex 'port=11211#tout=30#thnum=16#opts=fq#qtout=10' \ 'casket.kct#ktopts=p' 「-th 1」でメインサーバのスレッド数を1にしている。最新版からはデフォルトで16スレッドを立てるのだが、アプリ側からはメインのサーバにはアクセスしないだろうから、1個あればよい。「-ls」はログレベルをSYSTEMに設定。「-plsv ...」では、memachedプラガブルサー
開発メモ: memcachedプロトコルでメッセージキューを実現する
前回の記事にて、Kyoto Tycoonでメッセージキューを実現する方法について述べた。今回は、それを実運用にて使いやすくするための諸機能について説明する。みんな大好きなmemcachedプロトコルでメッセージキューを実現してみよう。 ジョブキューとメッセージキュー どうでもいい話ではあるが、ジョブキューおよびメッセージキューという用語はよく混同して使ってしまう。俺定義では、ジョブキューは「ジョブ管理機能」という目的をたまたまキュー構造に基づいて実装しているものであり、メッセージキューはキュー構造に基づく非同期メッセージング機構であって用途は特に限定しない。つまりメッセージキューをジョブキューを実装するのに使うこともあるが、それ以外の用途にもメッセージキューは使われる。またジョブキューをメッセージキューに基づかないで同期的に実装することもできる。 きっと偉い学者さんがどこかでちゃんとした定
開発メモ: Kyoto Cabinetのロック機構の改善
Kyoto CabinetはIO負荷が高い場合にCPU負荷も高くなりがちだという指摘を受けて、それを解決すべくロック機構を見直したという話。 スロットロック ハッシュテーブルの操作はハッシュバケット毎に完全に独立して実行できるのが強みだ。ハッシュテーブルは計算量が有利なだけでなく、並列性にも優れるということ。実際には下層のファイルIOで実装依存の排他制御が行われることになるが、ハッシュ層だけ見れば理想的な並列性を備えている。ただし、同じバケットに連なるレコード群の操作は互いに依存関係があるので、それらは一括して排他制御してやる必要がある。となると、バケット毎にロックを用意するのが理想だが、実際にはメモリを節約するために、予め決めた数のロックを用意して、ここのロックに複数のバケットを割り当てる構成をとる。リソース空間をスロットに分けるというイメージから、これをスロットロックと呼ぼう。 スロッ
開発メモ: Kyoto TycoonでテーブルDBを実現する
Kyoto Tycoonで、RDBMSのテーブルのように複数のコラムを持ったレコードを扱ったり、特定のコラムを対象にセカンダリインデックスを張ったりすることもできるという話。 テーブルDB Tokyo CabinetおよびTokyo Tyrantでは、テーブルDBという実装があった。最も率直なKVS（永続化連想配列）の実装としてお馴染みのTC/TTではあるが、valueに構造を持たせることによってマルチコラムを実現し、さらに更新処理にフックをかけてセカンダリインデックスを自動的に管理できるようにもしていた。結果として、「ドキュメント指向DB」とか「スキーマレスDB」とかいったような、ゆるふわな感じの用途で便利に使えるツールになっていると思う。 しかし、KyotoシリーズではテーブルDBは実装しない方針である。多機能すぎてメンテが大変だからだ。アプリケーション寄りの機能を提供するということは
開発メモ: スナップショットを使ったレプリケーション管理
前回述べた自動スナップショット機能は、今後は「バックグラウンドスナップショット」と呼ぶことにする。今回は、それを使ってオンメモリデータベースサーバのレプリケーションを簡単に管理する方法について解説する。 レプリケーションの基本 KTのレプリケーション機構は、マスタサーバが自分のDBに対する更新ログを記録しておき、それをスレーブサーバが吸い出して自分のDBに対して適用することで、二つのDBの状態を同期させるという機構である。更新ログを吸い出す際には、「既にどこまでの更新ログを読んだか」というタイムスタンプを管理して、レプリケーションを停止したり再開したりできるようにしている。 障害対応や負荷増大への対応などで、スレーブサーバを増設する際には、直近のバックアップのDBファイルと、それを作成した瞬間のタイムスタンプを記録したRTSファイルをスレーブのマシンに設置してから、サーバを起動する。そうす
開発メモ: オンメモリDB＋スナップショットで爆速永続キャッシュ
Kyoto Tycoonに自動スナップショット機能が実装され、オンメモリDBでも永続化できるによになり、高速性と永続性を両立できるようになったよという話 自動スナップショットとは 「永続化したキャッシュサーバ」としてのコンセプトを掲げるKyoto Tycoonだが、それはメモリ上でなくファイル上でデータベースを表現するからである。今回の自動スナップショットによる永続化は、それとは異なる。オンメモリDBの中にあるレコードを定期的にファイルに書き出すことで永続化するのだ。 ファイルDBの場合、データベース内のレコードは常にファイルに書かれている。よって、サーバプロセスを再起動してもレコードは消えない。その代償として、ファイル上で更新された領域をディスクに書き込むためのIO処理にかかるオーバーヘッドが無視できない。ファイルシステムのページキャッシュによって緩和されるとはいえ、IO処理がランダムア
生活メモ: 就職することにした
長らくニートだったが、就職先が決まったということで、代官山のレストランで妻と娘にお祝いしてもらった。うれしい。そして、新しい道に踏み出すという新鮮な気持ちが何とも心地よい。 2011年2月1日付けで、Googleに入社する。その経緯について記述しておく。個人的事情をわざわざ晒す必要もないのだが、お世話になっている皆様やOSS関連や個人事業関連で関わりのある方々への報告ということでキーを叩く。 経緯 昨年7月末に前職を辞して、自作のOSS製品のデュアルライセンス販売で食っていくべく開発作業や事務作業を半年ほど行ってきた。しかし、地価と物価の高い東京という都市に妻子とともに暮らせる収入を継続して得ていくにはあまりにも頼りないビジネスモデルであるため、それを本業にすることは断念した。 より正確に言えば、当初からOSSで食っていけるとは思っていなかったので、ライセンス販売は妻に任せて俺は就職できる
開発メモ: もし自営業の男子プログラマがKVSで「ブログサービス」を書いたら
Webサービスの典型例でありCMSの典型例であるブログサービス。それを実装するための指針が示せれば、その他のサービスを開発する際にも大いに参考になることだろう。 データ構造 単純なブログサービスのデータノードとしてKyoto Tycoonのサーバ群を用いることを想定する。ブログの個々の記事は以下の属性を持つものとする。 著者のユーザID（uint32） 投稿日時（uint32） 題名（text） 本文（text） コメントリスト（シーケンス） 各コメントは、コメントした人のユーザIDと本文からなる データノードに対する問い合わせは、「あるユーザの最新記事を降順で5件くれ」というのが典型である。「降順で」という順序に対する要求があるのでB+木を選択し、連想配列のキーは、ユーザIDと投稿日時を連結したものとする。単純化のために、各々を10桁の10進数文字列をコロンで区切って並べて、全体で21バ
開発メモ: DBサーバのnoreplyオプションによる高速化
Kyoto Tycoonやmemcachedにてnoreplyオプションを使ってパフォーマンスを上げる話。 noreplyの功罪 DBに対する更新操作はその成否を真偽値などとして呼出側に返すのが通常であるが、それを省略することでパフォーマンスを上げることができる。memcachedではnoreplyオプションとして知られている。KTの最新版からは、memcachedプラグインと独自バイナリプロトコルでもnoreplyオプションをサポートすることにした。 noreplyを有効にするとなぜ高速化するのか。クライアントはクエリをsendしただけで、recvをせずに次の処理に移れるからだ。sendシステムコールに渡したデータはカーネルが非同期に処理するので、カーネルとアプリケーションは並列に処理を進めることができる。recvをした場合にはその時点で両者の待ち合わせが発生してしまうのだが、それをしな
開発メモ: 高負荷タイムスタンプDBの運用法
Tokyo Tyrantでmixiのアクセスタイムスタンプを管理しているという話を結構前に書いたわけだが、その用途でKyoto Tycoonをより効率的に使うための話。似たようなタイムスタンプ関係のユースケースで参考になると思う。 アクセスタイムスタンプ mixiにおいては、全てのユーザの直近のアクセス時間を記録し、「最終ログイン」と名づけて提示している。名前に反して、最後にログイン操作をした時間ではなく、「mixi.jpにおいてログインしないと見られないいずれかのページを最後に見た時間」を提示する機能である。したがって、全ユーザの全ページ遷移に伴ってデータベースに更新クエリが走るという重量級の仕様になっている。 ただ更新クエリが多いだけならユーザIDに基づいてサーバを水平分散させればよさそうだが、マイミクシィ一覧ページで集合演算が必要になるあたりが凶悪な仕様である。つまり、あるユーザのマ
開発メモ: KTのプラガブルデータベース
Kyoto Tycoonのストレージ層もプラガブルにして、任意のストレージエンジンを利用できるようにした。 背景 みんな大好きMySQLの利点の一つとして、ストレージエンジンがプラガブルであることが挙げられる。InnoDBやMyISAMやその他のエンジンを、システム全体の機能要件や性能要件に合わせて使い分けられるということだ。既存のエンジンから選択するだけでなく、自分で新しいエンジンを実装して組み込むこともできる。 KTでもMySQLと同じように複数のストレージエンジンを使い分けることができるように従来からなっているが、ユーザ独自のエンジンを組み込むことはまだできなかった。今回、ストレージ層をプラガブルモジュールにすることで、ユーザ独自のエンジンを組み込めるようになった。この仕組みをプラガブルデータベースと呼ぶことにする。 CSVファイルにデータを入れる「CSVデータベース」や、OpenO
開発メモ: Kyoto Tycoon普及大作戦
手前味噌だが、Kyoto CabinetおよびKyoto Tycoonは、かなりいけてるソフトウェアに仕上がっている。されど、いまいち普及していないのが現状である。よって、今後は普及活動を本格化させる。 まずはKyoto Tycoonを普及させたい。Web屋さんがみんな大好きなmemcachedのユースケースをほぼ100%カバーしていて、機能性や空間効率でのアドバンテージを提供できるので、お勧めしやすい。memcachedプロトコルのプラガブルサーバを使えば、ユーザの既存のWebアプリケーションに一切手を加えることなく、KTをインストールしてサーバを再起動するだけで乗り換えが済む。非常にわかりやすい筋書きだ。 memcachedを置き換えるだけでなく、ファイルDBによる永続化によって新たな価値を提供することができる。さらに、レプリケーションなどのHA機能群によって、その価値を補強することが
開発メモ: Kyoto Tycoonベータ版リリースすた
ここのところ必死こいて作り込んでいたKyoto Tycoonだが、主要機能を実装しきって文書もそこそこ書けてきたので、ベータリリースということにした。プロジェクトページもちゃんと作ってある。 公式には英語の文書しか作らない方針なのだが、それだと国内ではなかなか使ってもらえないので、この場でチュートリアルを書いてみる。 Kyoto Tycoonとは プロセス組み込み軽量データベースライブラリであるKyoto Cabinetをネットワーク越しに利用できるようにするためのツールキットである。KCのデータベースを内部に持ったサーバプログラムと、それに接続してデータベースを操作するためのクライアントライブラリからなる。また、コマンドラインからサーバにアクセスするためのユーティリティもついてくるので、簡単に使い始められる。 製品コンセプトは、「永続的キャッシュサーバ」もしくは「memcachedの永続
開発メモ: 50行のC++コードでWebサーバを実装する
「Kyoto Tycoonの設計 その四」改め、50行でWebサーバを書く方法を解説する。前回実装した「多重I/Oマルチスレッド汎用TCPサーバ」の上にHTTPの処理を行う層をつけて、「多重I/Oマルチスレッド汎用HTTPサーバ」を司るクラスを実装してみたので、それを使ってちょちょいとやる。 URLクラス HTTPと言えばURLが使えないと意味がない。URLは単なる文字列として扱ってもよいのだが、様々なシーンで分解や加工が必要になり、その処理はなにげに複雑で面倒なので、予めクラスとして導出しておいた方がよいだろう。 class URL { public: // 文字列のURLを解析して内部構造を作る void set_expression(const std::string& expr); // スキーム要素を設定する void set_scheme(const std::string&
開発メモ: KCで各種圧縮アルゴリズムを使う
QDBMでもTCでも各種の圧縮アルゴリズムをDBに適用できるようにしているが、KCでも任意の圧縮アルゴリズムを後付けで組み込んで利用できるようになっている。その使い方と性能について紹介する。 圧縮アルゴリズムのプラグイン CacheDB、GrassDB、HashDB、TreeDB、DirDB、ForestDBのいずれも、tune_optionsおよびtune_compressorの2つのメソッドがある。tune_options(BasicDB::TCOMPRESS) とするとデータベースの圧縮が有効になり、デフォルトではZLIBの生フォーマットが適用されるようになる。任意の圧縮アルゴリズムを適用するには、さらにtune_compressorでCompressorクラスを継承して作った派生クラスのオブジェクトを登録する。Compressorクラスはcompressメソッドとdecompres
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
