DSのスターフォックスというゲームにはまりまくりのmikioです。最近社内外で「俺ストレージサーバ」を作るのが流行っているようなので私も参戦してみました。今回はDBMのネットワーク層をほぼスクラッチで作った話をします。 Tokyo Tyrant Tokyo Tyrant（以下TT）はTokyo Cabinet（以下TC）をラップしてネットワーク越しに操作できるようにするツールです。キャビネット（内閣）を傀儡にするタイラント（僭主）ということで名付けました。ダウンロードはこちら。 TCは高性能なDBMで、マルチスレッドモデルで高い並列性を実現していますが、逆にマルチプロセスモデルだとファイルロックがかかるので並列性が低くなってしまいます。つまり、書き込みモードでデータベースにアクセスしているプロセスがいると、その間は他のプロセスがデータベースに接続しようとするとブロックされることになります。

来年のバレンタインデーに、正確には「2009-02-14T08:31:30+09:00」に、UNIX時間が「1234567890」を迎えることを発見してちょっと嬉しいmikioです。さて、今回は高効率ハッシュデータベースサーバTokyo Tyrantを用いてHAハッシュデータベースを構築する手法についてご紹介します。ちょっと難しいし非常に長い内容なのですが、最後までお付き合いくださいませ。 可用性と保全性 HA（High Availability：高可用性）とは、可用性（Availability）が高いことです。それでは説明になっていないので詳しく言い替えますと、システムに障害が起きにくくすることと、たとえ障害が起きたとしてもできるだけ迅速に復旧できるようにすることです。データベース系のシステムはユーザのデータを管理するという中核的役割を担うため、可用性を高めることは最も重要な課題となりま

先日、MySQL Conferenceという催しに行ってきました。そこでMySQLの開発者のBrian Aker氏およびMichael Widenius氏と話をする機会があったのですが、やっぱしトップランナー達と議論するのは刺激になるなぁと思ったmikioです（その時の資料）。さて、一連の連載も今回が感動の最終回で、TCの性能上の蘊蓄をお届けいたします。 なぜdynamic hashingを使わないか Brianさん達とTCの実装についても少し議論したのですが、その際にdynamic hashingをなぜ使わないのかと問われました。その背景として、TCやQDBMではハッシュのバケット数（＝格納するレコード数を予測してその数倍に設定すべき値）をデータベース作成時に指定しなければならないという問題があります。バケット数が大きすぎると空間効率が劣化し、小さすぎると時間効率が劣化するというトレード

涼しさに夏の終わりを感じてなんだか寂しくなるも、新しいオフィスから見えるパノラマの空の高さに癒されているmikioです。秋は気が変わりやすいこともあり、今回は唐突にDBMの並列性についての考察を記してみます。 並列性って何? 最近はマルチコアのプロセッサが当り前になってきて、そのパワーを100%引き出すために、並列性をできるだけ高めることが求められるようになってきました。それについて考える前に、まずは用語の整理をしておきましょうか。 並行性 : 二つ以上のタスクを一緒に進めること。必ずしも同時に処理を行うとは限らず、Aを少しやってからBを少しやって、それからまたAを少しやって、またBをやって...といった、いわゆるタイムシェアリングで実現してもよい雰囲気。 並列性 : 二つ以上のタスクを同時に進めること。タスクを複数のマシンに割り当てたり、複数のCPUに割り当てたり、CPU内の複数のコアに

この連載のように小難しい記事が続くと、読者の皆さんだけでなく執筆陣まで引いてしまうのではないかと心配しているmikioです。いやいや、いいんです。ハッキングから夜のオカズまでバラエティに富んだブログを目指すべく、私は私なりの記事を、たとえマイノリティ向けだとしても臆さず書いてゆくのです。今回はTCの実装の詳細についてお届けします。 QDBMとどう違うの? QDBMもTCと同様にDBMの一実装で、小さくて速くて使いやすいをモットーに作りはじめて、それなりに目標を達成できたと自負しているプロダクトです。しかし、今思えばいろいろと気に入らない点がいくつかありました。TCはそれを克服すべく一から書き直したものです。具体的には以下の点が違います。 空間効率の向上 : データベースファイルのサイズがもっと小さい 時間効率の向上 : 読み書きにかかる時間がもっと短い 耐障害性の向上 : データベースファ

予定を立てた途端にやりたくなくなる症候群に堪えて連載を続けるmikioです（こんな私でもエアーマンくらいは倒せます）。前回はDBMの基本について説明しましたが、それを忠実に実装しても実際には使いものにはならないことにも触れました。今回は、実用的なDBMに進化すべく、Tokyo Cabinet（およびその前身のQDBM）で考えた工夫についてお話します。 ハッシュ関数についてもう少し 前回の記事に関して、「ハッシュ関数はビットシフト使って実装した方が早いよ」という旨のお便りをいただきました（ありがとうございます）。まさにその通りで、乗算命令（ここではimull）より左シフト命令（ここではsall）の方が速いみたいです（Intelの資料によると、mulが15から18で、salが4とのこと）。しかし、DBMの場合はファイルI/Oにかかる時間が支配的になるというのが重要な点です。したがって、ハッシュ

約半年間の沈黙を破ってOSSの世界に戻ってきつつあるmikioです。先日、Tokyo Cabinet（以下「TC」と呼びます）というデータベースライブラリをリリースしました。今回から数回に分けて、TCの設計と苦労話について連載してみます。 DBMとは TCは、いわゆるDBMの系譜のデータベースライブラリで、単純なハッシュテーブルをファイル上で永続化するだけの機能を提供します。DBMはAT&Tの古代UNIXの時代から受け継がれる伝統芸能なのですが、私はそういう枯れた技術が大好きなのです。 プログラマの皆さんは、PerlやRubyではハッシュ（連想配列）と呼ばれ、JavaやC++ではmapと呼ばれるような、何らかのキーに関連づけてなんらかの値を記録するデータ構造って実によく使いますよね。例えばmixiでは、ユーザアカウントに関連する情報（名前とかニックネームとか）は、ユーザIDをキーにしたハッ

GoogleのFellowであるJeffrey Dean氏のWSDM'09における講演"Challenges in Building Large-Scale Information Retrieval Systems"のスライドの翻訳の第3回です。Googleの検索システムの10年間の進化の軌跡が紹介されており、今回は2004年から2007年ぐらいまでの検索システムの紹介とインデックスの符号化方式、検索精度を向上させるための実験環境についての紹介となります。個人的には分岐処理を徹底的に排除したGoogleの最新の符号化方式が興味深かったです。イタリック体で一部解説・感想をいれています。翻訳は素人なので詳しくは元の資料を参照してください。 第1回：Google WSDM'09講演翻訳：大規模な情報検索システム構築における課題（１） - llameradaの日記 第2回：Google WSDM

GoogleのFellowであるJeffrey Dean氏のWSDM'09における講演"Challenges in Building Large-Scale Information Retrieval Systems"のスライドを翻訳してみました。Googleの検索システムの10年間の進化の軌跡が紹介されており、興味深い話が満載です。個人的にはディスクの外周部と内周部を使い分けている話がツボでした。なお、イタリック体で一部解説・感想をいれています。翻訳は素人なので詳しくは元の資料を参照してください。 スライドの入手元：Jeffrey Dean – Google AI 検索システムに取り組む理由 チャレンジングなサイエンスとエンジリアニングのブレンド 多くの魅力的な未解決な問題が存在する。 CS（コンピュータサイエンス）の多数の領域にまたがる。 アーキテクチャ、分散システム、アルゴリズム、圧

CNETの記事にてGoogleのサーバーが公開されています。 Google uncloaks once-secret server | Business Tech - CNET News マザーボードにVGAポートがない サーバにバッテリー内蔵(Distributed on-board UPS) HDDや電源のマウントが意外とマジックテープ PUEがすごい ネットワーク機器もバッテリ内蔵 LANポートは一つ 電源からのケーブル数が少ない などなど興味深い点がいろいろあります。 せっかくなので、記事を読むついでに写真からサイズを（だいたい）推測してみました。大きいと感じるか、小さいと感じるか、どうでしょうか。個人的には、大きさ以外に、バッテリと電源の位置関係も気になっています。 ボードはE-ATXっぽいですね。 記事中に高さは3.5inchと書いてあるので、実際は88mmくらいかも。

Tech Industry Google uncloaks once-secret server Unusually, the search giant designs its own servers. For the first time, Google unveils one publicly, showing a surprise built-in battery. Google for the first time showed off its server design. (Click to enlarge) Stephen Shankland/CNET Updated at 4:08 p.m. PDT April 1 with further details about Google's data center efficiency and shipping container