開発メモ: UTF-8とUCS-4の変換メモ
UTF-8とUCS-4の相互変換をC/C++で書いた時のメモ。たぶんまた自分で読むので。 背景 文字のちょっとした正規化などの処理をしたいがiconvやICUなどの巨大なライブラリは使いたくないということがたまにある。嚴密な文字列処理をしたい場合にはそれらのライブラリを使った方が安全だし確実であることは言うまでもないが、ちょっとしたユーティリティを作るのにはちょっとオーバースペックである。 一方で、UTF-8文字列に対してはASCII用正規表現ライブラリを使えば検索や置換などの大抵の操作ができるので、自分でゴリゴリと変換処理を書かなければいけないことはあんまりない。 ただ、たまに自分で書きたくなることもある。ヨーロッパ系言語のアクセント記号を外したり、半角片仮名を全角片仮名にしたり、漢字の異体字表記を常用漢字に統一したりといった処理を一気にやりたい場合とか。そんな場合、各文字が可変長バイト
開発メモ: KVSとシグナル機構でジョブキューを実現する
いわゆるkey-value storeを使っている際に、レコードの挿入もしくは更新を検知して即座に何らかの処理を行いたくなることはないだろうか。俺はあんまりないけど、結構そういう質問が来るので、きっと巷にはそういう要求があるのだろう。Kyoto Cabinetでそれを実現してみた。 ジョブキュー もうちょい具体的な例を挙げると、ジョブキューである。ここで、「foo」という名前のタスクを考えてみる。読み出し側（ワーカ）は、適当な名前をつけた条件変数を常に監視していて、そこにシグナルが飛んできたら即座にレコードを取得して処理を行いたい。しかし、「一定の間隔毎にレコードの検索を繰返して発見したら処理を行う」というポーリングスタイルにはしたくない。操作にどうしてもタイムラグが出るし、ポーリングのための無駄なトラフィックが発生するからだ。 シグナル待機処理と該当レコードの取得処理を行う擬似コードは以
開発メモ: IndexDB: 転置インデックスのためのDB
大震災の時分に何だが、Kyoto Cabinetベースで検索エンジンの核となる転置インデックスを作るのに適したDBを実装したという話。 転置インデックスとappend操作 多くの検索エンジンの核となる転置インデックスとは、検索語に一致する表現がどこに出てきたかという位置情報のリストを保持するものであり、検索語をキーとして位置情報リストを値とする連想配列である（転置インデックスを使わない検索エンジンもあるが）。この位置情報リストをposting listとか呼んだりするらしい。転置インデックスにもいくつか流儀があり、検索語をどのように切り分けるかで単語（分かち書き）方式とか文字N-gram方式とか呼ばれるものがあったりするが、いずれにせよ、小さいキーと、非常にでかい値を保持する連想配列を作ることには変わりない。 で、素朴に転置インデックスを作ろうとすると、検索対象の文書を解析しながら、得られ
開発メモ: Kyoto Cabinetのロック機構の改善
Kyoto CabinetはIO負荷が高い場合にCPU負荷も高くなりがちだという指摘を受けて、それを解決すべくロック機構を見直したという話。 スロットロック ハッシュテーブルの操作はハッシュバケット毎に完全に独立して実行できるのが強みだ。ハッシュテーブルは計算量が有利なだけでなく、並列性にも優れるということ。実際には下層のファイル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をした場合にはその時点で両者の待ち合わせが発生してしまうのだが、それをしな
開発メモ: KT-RDBMS間レプリケーションのTIPS
KT-MySQLレプリケーションの具体例 Kyoto TycoonからMySQLなどのRDBMSに対してレプリケーションを行うための設定や運用方法について説明する。 スレーブエージェントの構成 以前の記事に書いたように、KTのスレーブエージェントを用いると、RDBMS等の外部システムに対して非同期レプリケーションができるようになる。KTをライトスルーキャッシュのように用いると、後段のRDBMSの負荷を効果的に下げることができる。 KTのレプリケーションにおけるスレーブは、デュアルマスタ構成における更新ログの循環を防ぐために、自分のサーバIDと異なるデータのみを取得するようになっている。スレーブがマスタに接続した際には、「自分のサーバIDはXだが、それ以外のサーバIDのログのみをくれ」というクエリを投げるわけだ。したがって、スレーブエージェントがマスタに接続する際にも、マスタのサーバID以外
開発メモ: Kyoto Tycoon普及大作戦
手前味噌だが、Kyoto CabinetおよびKyoto Tycoonは、かなりいけてるソフトウェアに仕上がっている。されど、いまいち普及していないのが現状である。よって、今後は普及活動を本格化させる。 まずはKyoto Tycoonを普及させたい。Web屋さんがみんな大好きなmemcachedのユースケースをほぼ100%カバーしていて、機能性や空間効率でのアドバンテージを提供できるので、お勧めしやすい。memcachedプロトコルのプラガブルサーバを使えば、ユーザの既存のWebアプリケーションに一切手を加えることなく、KTをインストールしてサーバを再起動するだけで乗り換えが済む。非常にわかりやすい筋書きだ。 memcachedを置き換えるだけでなく、ファイルDBによる永続化によって新たな価値を提供することができる。さらに、レプリケーションなどのHA機能群によって、その価値を補強することが
開発メモ: Kyoto Tycoonのバイナリプロトコル
Kyoto Tycoonをバイナリプロトコルで通信できるようにして、時間効率を向上させられるようにしたという話。 HTTPの位置づけ Kyoto Tycoonの売り文句の一つは、HTTPで通信して手軽に使えるということである。HTTPは素晴らしい。大抵の言語にHTTPを喋る便利なライブラリが付属しているので、専用のクライアントライブラリを作らなくてもKyoto Tycoonをすぐに使い始められる。データの内容が人間の目で見て判別できるので、デバッグも拡張もしやすい。ロードバランサなどのHTTP用の仕組みを流用して多彩なアーキテクチャを構成できる。 しかし、そのような汎用性の半面、HTTPは非常に冗長なプロトコルになっている。DBMのネットワークインターフェイスとして利用して小さいレコードの授受を行うということを前提とすると、本質的な処理内容に関わるデータは送受信されるデータの半分以下、下手
開発メモ: memcachedとKyoto Tycoonの空間効率
Kyoto CabinetおよびKyoto Tycoonに新たに導入された「StashDB」を使うとmemcachedよりも空間効率を向上させられるという話。 StashDBとは 前回の記事で説明したように、Kyoto CabinetではローカルMapReduceのキャッシュとしてTinyHashMapというクラスを実装して省メモリ化を図っている。丁寧にシリアライズしてデータを詰めていくとかなりメモリを節約できるものなのだ。 同じ構造をDBMのインターフェイスにしたのがStashDBである。ProtoHashDB, ProtoTreeDB, CacheDB, GrassDB, HashDB, TreeDB, DirDB, ForestDBに続く第9番目のDBMということになる。もちろん、マルチスレッドセーフにして、レコード単位の粒度でロックを施して一貫性を確保し、VisitorやCurso
開発メモ: MapReduce on Kyoto Cabinet
Googleで実用化されHadoopで流行しているところの分散処理フレームワークMapReduceをKyoto Cabinetにおいても実現してみた。その解説。 ローカルなMapReduce MapReduceは多数のマシンが連携して分散処理を行うためのフレームワークなので、プロセス組み込みDBMであって分散など全く関係ない世界に生きているKCでMapReduceを実行して意味があるのだろうか。答えは、「あんまりない」である。それにもかかわらず実装したのは、何となく話題性がありそうだからってのが最大の理由なのだが、もうひとつ理由がある。 スクリプト言語で集計処理をやろうとすると、めっちゃメモリ食うしCPUパワーを使うわりに遅いからである。1000万件のソートってだけでスクリプト言語だと結構辛いからね。そこで、MapReduceフレームワークをC++で実装してmapとreduceだけをスクリ
開発メモ: HTTP記録機能付きプロクシによるレプリケーション
HTTPプロクシに更新ログを取らせれば、HTTPベースのいかなるサービスの内部状態もレプリケーションできるんじゃないのか？ という検討の過程を晒してみる。 背景 保守性の観点からKyoto Tycoon自体にはレプリケーション機能を持たせないことにしたが、実際のユースケースではレプリケーションが欲しくなることが多いこともわかっている。なので、外部機能によって何とかレプリケーションを実現したい今日この頃である。 KTにレプリケーションを実装しないもう一つの理由は、レプリケーションのための更新ログを記録するための処理がDBの更新処理よりも重いという本末転倒なことになっているからである。更新ログはレコードそのものに対して冗長なのでwriteの量も多いし、シーケンシャルアクセスなのでディスクには優しいが、データが際限なく増えるのでそれでも重い処理になる。また、DBはレコード単位の整合性だけを確保す
開発メモ: 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&
Tokyo Cabinet: a modern implementation of DBM
BTW, do you know Tkrzw? Actually, it is more powerful and convenient library than Tokyo Cabinet. At this distance of time, Tkrzw surpasses Tokyo Cabinet in every aspects. I strongly recommend you to use Tkrzw. Overview Tokyo Cabinet is a library of routines for managing a database. The database is a simple data file containing records, each is a pair of a key and a value. Every key and value is se
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
