mixi Engineers’ Blog » 圧縮データベースを使おう
チャリンコ通勤による滝のような汗で、朝からTシャツがシースルーになってしまうmikioです。さて今回は、Tokyo Cabinet（TC）のデータベースを各種のアルゴリズムで圧縮して利用する方法についてご紹介します。 圧縮B+木 B+木とは、比較関数の値による順序が近いレコード群を単一のページにまとめ、各ページにB木（multiway balanced treeの略であり、二分木（binary tree）とは違います）の索引を張ったものです。理論的にはレコードの探索も更新も O(log n) の時間計算量で行え、内部ノード（B木）の操作をキャッシュすると実質的には O(1) の時間計算量で探索や更新が行えるという、かなり安定した性能を備えるデータ構造です。その上、レコードが一定の順序に基づいて並べられているので、数値の範囲検索や文字列の前方一致検索が高速に行えたり、カーソルによって順序に基
Kyoto Cabinet 1.0.0リリース！ - mixi engineer blog
夏が近づくとウキウキしてくるmikioです。昨日ついにリリースされたKyoto Cabinet 1.0について今回は報告します。 1.0の位置づけ コミュニティ毎や製品毎にバージョン番号割り当ての方針は異なるわけですが、私の個人的なポリシーでは、1.0には特別な意味があります。すなわち、0.xのバージョンはbeta版的な位置づけで、「実サービスに使うのはちょっと待った方がいいですよ」ということを意味します。一方で、1.xはstable版的な位置づけで、「よろしければ実サービスでも使ってみてください」ということを意味します。私がstable版に設定する原則を以下に列挙します。 安定稼働を至上命題とする（バグがあればその修正を最優先する） APIを変更しない（変更するとしても後方互換性を維持する） DBファイルのフォーマットを変更しない（変更するとしても後方互換性を維持する） なるべく機能追加
京都収納棚：DBMの率直な壱実装 - mixi engineer blog
飲み屋に行くとかなりの確率で荷物を忘れて帰るmikioです。さて、今回はここ2ヶ月ほどで急ピッチで開発した軽量データベースライブラリ「Kyoto Cabinet」について紹介します。 開発の動機 以前から軽量データベースライブラリとしてご好評いただいているTokyo Cabinetですが、DBMとして必要十分な機能と性能を備えていてなかなか良いものだと自負しております。ただ、開発を進める中でいくつか不満な点があったのも事実です。端的に言えば、全てC言語で記述して、標準ライブラリ（とzlib/bzip2）以外の機能は全て自作しているので、最適化がしやすい反面、メンテナンスの難易度が高くなってしまっているというのが不満です。 そこで、多少性能が悪くなってもいいから、私自身としてお気楽に開発およびメンテナンスができて、移植性も高いような実装を作ってみようと思い立ったのが昨年10月頃。様々な検討を
mixi大規模障害について - mixi engineer blog
こんにちは。システム本部技術部たんぽぽGの森本です 先日のmixi大規模障害についてのブログです。 はじめにお断りしておきますが、弊社CTOがtwitterで公開した以上の情報はまだ得られておりません。 twitterでは書ききれなかった細部を補足してみたいと思います 現状判明しているのは以下の点です memcachedに大量の接続・切断を行うとmemcachedプロセスが突然終了することがある memcachedには異常時に終了するフローもあるが、同時に出力されるはずのエラーログは出ていなかった coreも出力されていなかった テスト環境にて追試を行ったところ、なんどか再現させることができましたが、確実に発生する条件は未だ不明です。 障害時の memcachedのバージョンは1.4.4, libeventのバージョンは1.3bです memcached の起動オプションは以下のとおり ./
軽量データクラスタリングツールbayon - mixi engineer blog
逆転検事を先日クリアして、久しぶりに逆転裁判1〜3をやり直そうか迷い中のfujisawaです。シンプルなデータクラスタリングツールを作成しましたので、そのご紹介をさせていただきます。 クラスタリングとは クラスタリングとは、対象のデータ集合中で似ているもの同士をまとめて、いくつかのグループにデータ集合を分割することです。データマイニングや統計分析などでよく利用され、データ集合の傾向を調べたいときなどに役に立ちます。 例えば下図の例ですと、当初はデータがゴチャゴチャと混ざっていてよく分からなかったのですが、クラスタリングすることで、実際は3つのグループのデータのみから構成されていることが分かります。 様々なクラスタリング手法がこれまでに提案されていますが、有名なところではK-means法などが挙げられます。ここでは詳細については触れませんが、クラスタリングについてより詳しく知りたい方は以下の
DBMによるテーブルデータベース その五 - mixi engineer blog
ついに発売されたスト4のコンシューマ機版をやりたくてしょうがないけど筐体を買ってもらえないので、駅前のゲーム屋のディスプレー前で垂涎するばかりのmikioです。今回は連載の最終回で、各種スクリプト言語を使ってお手軽にテーブルデータベースを操作する方法について説明します。 TokyoCabinet::TDB まずは、TCのPerlバインディングとRubyバインディングの最新版を入手してください。それぞれテーブルデータベースを扱うための TokyoCabinet::TDB というクラスが加わっています。以下のようなIDLによるガイドラインに準拠したインターフェイスが提供されますので、使い方は言語にかかわらず同じようになるはずです。 module TokyoCabinet { interface TDB { boolean open(in string path, in long omode);
MySQLのInnoDBでのデッドロック - mixi engineer blog
こんにちは、mixi開発部にてアプリケーション開発をしていますyouheiです。 今回は、MySQL-5.0.45のInnoDBで連番を管理するテーブルのパフォーマンス測定をしていたのですが、その際に少し変わったデッドロック問題に遭遇しましたので、そのあたりをネタとして書いてみたいと思います。 まずは、今回使用したデータベースのスキーマは下記のようなものです。 CREATE TABLE num ( id bigint unsigned NOT NULL default '0' ) Engine=InnoDB; AUTO_INCREMENTは使用していません。 そこに1レコードだけ登録します。 INSERT INTO num (id) values (1); そして実際連番を取得する際には、 UPDATE num SET id = LAST_INSERT_ID(id+1); といったクエリを
mixi Engineers’ Blog » 最適化しよう？
当エンジニアブログを私物化していると専らの評判のmikioです。ブログを書かないと死んでしまう病に冒されているのでしかたないですね。個人ブログ時代よりもわかりやすくする努力はしているんですけどね。さて、今回はソースコードの最適化による高速化について述べます。 ベンチマークテスト TCはQDBMや他のDBMより高速であるという主張をしたいのですが、その根拠としてベンチマークテストの結果が必要となります。そこで、データベースに100万レコードを格納する処理と、そうして作ったデータベースから全てのレコードを探索する処理の時間を、各DBMで計測してみました（TCのパッケージのbrosというディレクトリにテストコードが入っています）。実行環境は、Thinkpad T60（Intel(R) Core2 CPU T7200 @ 2.00GHz）上のLinux version 2.6.16です。 ハッシュ
MySQLに対するDrizzleの答え #1 スレッド管理編 - mixi engineer blog
先日、Drizzleのスレッド管理を担うコアの一部分がモジュール化され、勉強がてらMySQLのスレッド管理の設計を調べてみました。その時のメモ（だから文が少し固いかも）と、Drizzleでの戦略を今回のエントリーで公開します。 最後のDrizzleでは？セクションまではプログラミングの教科書に載っている様な典型的なセオリを述べているだけなので、MySQLのインターナルに詳しい方は最後まで飛ばした方が良いかもしれません。 ちなみにソースはMySQL 5.1とMySQL 6.0のドキュメントです http://dev.mysql.com/doc/refman/6.0/en/connection-threads.html http://dev.mysql.com/doc/refman/5.1/en/connection-threads.html 現在の仕組みと制限 現在のMySQLでは新たなクラ
各種マップ実装の性能比較 - mixi engineer blog
今回は小ネタのmikioです。key/valueのレコードを高速に格納・参照・削除する仕組みが連想配列とかマップとか呼ばれて親しまれていますが、Tokyo Cabinetのオンメモリマップの性能をC++の各種実装と比較してみました。 以下の実装を対象として、100万レコードの格納と検索にかかる時間を計測します。キーと値は各8バイトの文字列とします。 Tokyo Cabientのオンメモリマップ（TCMAP） STL（C++の標準テンプレートライブラリ）のmapとmulti mapとset GNU拡張テンプレートのハッシュマップ Googleのdense hashおよびsparse hash テストコードはこちらに挙げておきます。具体的な操作としては、マップオブジェクトを生成し、バケット配列の要素数をレコード数と同じにチューニングし、ループを回してレコード群を格納します。なお、STLのマップ
mixi Engineers’ Blog » mixiのスモールワールド性の検証
初めまして、mixi開発部のfujisawaです。 マイミクシィの友人関係を使って、mixiのスモールワールド性について調べましたので、その結果について書きたいと思います。 スモールワールド性とは スモールワールド性とは、人間関係のネットワークなどでよく見られる性質で、文字通り「世間は狭い(It's a small world!)」ということを表しています。「知り合いを6人介するだけで、世界中の人々と間接的につながることができる」という『6次の隔たり(Six Degrees of Separations)』という言葉でもよく知られています。 一般にスモールワールドは以下の特徴を持っています。 誰に対しても少ない人数を介するだけで到達できる(平均距離が小さい) 自分の友人同士が友人関係にあることが多い(クラスタ性が高い) 1の距離とは、ネットワーク中のノードをたどった回数、すなわち友人を介し
DBMによるデータベースサーバ - mixi engineer blog
DSのスターフォックスというゲームにはまりまくりのmikioです。最近社内外で「俺ストレージサーバ」を作るのが流行っているようなので私も参戦してみました。今回はDBMのネットワーク層をほぼスクラッチで作った話をします。 Tokyo Tyrant Tokyo Tyrant（以下TT）はTokyo Cabinet（以下TC）をラップしてネットワーク越しに操作できるようにするツールです。キャビネット（内閣）を傀儡にするタイラント（僭主）ということで名付けました。ダウンロードはこちら。 TCは高性能なDBMで、マルチスレッドモデルで高い並列性を実現していますが、逆にマルチプロセスモデルだとファイルロックがかかるので並列性が低くなってしまいます。つまり、書き込みモードでデータベースにアクセスしているプロセスがいると、その間は他のプロセスがデータベースに接続しようとするとブロックされることになります。
mixi Engineers’ Blog » libmemcachedで快速キャッシュ生活
みんな大好きなmemcached。今日はBrian AkerのC言語用クライエントライブラリについて書きたいと思います。日本語の情報がとても少なく、ドキュメンテーションも英語だけという事で興味はあるけど手をつけていないという方のお役に立てれたらなと思います。 本題の前に why libmemcached? 既にlibmemcacheが存在するのに何故、libmemcached？かと言うと理由の一つは最近libmemcacheの開発が止まったからです。本家ではそれが理由でlibmemcacheではなくlibmemcachedを推奨してますね。又、効率的なメモリ使用、Consistent Hashing、様々なハッシュアルゴリズム、新しいオペレータに対応している等という宣伝文句があります。apr_memcacheというライブラリも存在しますが自分は使った事がないためノーコメント。 ただ、推奨さ
mixi Engineers’ Blog » 新RSS Crawlerの裏側
このブログでは初めましての長野雅広(kazeburo)です。mixi開発部・運用グループでアプリケーションの運用を担当しています。 12月12日よりmixiのRSSのCrawlerが改善され、外部ブログの反映が今までと比べ格段にはやくなっているのに気付かれた方も多いかと思います。この改善されたRSS Crawlerの裏側について書きたいと思います 以前のCrawlerについて 以前のCrawlerは cronからbrokerと呼ばれるプログラムを起動 brokerはmember DBから全件、idをincrementしながら取得し、外部ブログが設定されていればcrawlerを起動(fork) crawlerはRSSを取得しDBに格納して終了 このような設計になっていました。 この設計の問題として、member DBを全件走査するという無駄な動作と、一件一件crawlerを起動するためオーバ
mixi Engineers’ Blog » Facebook Platformを使ってみた
今日は米SNSのFacebookが提供している開発者向けのFacebook Platformに関して語ろうかと思います。もちろん、軽く使い方やサンプルコードなども紹介します。もともとは息抜きに遊び感覚で触ってみたのですが面白くて興奮気味になってしまいました。 そもそもFacebook Platformとは？ Facebook（以後、FB）の持つSNSならではの巨大ソーシャルグラフを利用した第三者のウェブアプリケーション開発を実現した基盤（プラットフォーム）の事です。このプラットフォームを使って開発されたアプリケーションを使っていないFBユーザはいないと言える程、熱い代物です。数多くの有名なウェブ系企業もオフィシャルFBアプリをリリースして参戦してたりしてます。 アプリケーションのスクリプトはFBのサーバでホストするのではなく、開発者側のサーバでホストします。アプリケーションに対するリクエス
mixi Engineers’ Blog » Inside Tokyo Cabinet その五
先日、MySQL Conferenceという催しに行ってきました。そこでMySQLの開発者のBrian Aker氏およびMichael Widenius氏と話をする機会があったのですが、やっぱしトップランナー達と議論するのは刺激になるなぁと思ったmikioです（その時の資料）。さて、一連の連載も今回が感動の最終回で、TCの性能上の蘊蓄をお届けいたします。 なぜdynamic hashingを使わないか Brianさん達とTCの実装についても少し議論したのですが、その際にdynamic hashingをなぜ使わないのかと問われました。その背景として、TCやQDBMではハッシュのバケット数（＝格納するレコード数を予測してその数倍に設定すべき値）をデータベース作成時に指定しなければならないという問題があります。バケット数が大きすぎると空間効率が劣化し、小さすぎると時間効率が劣化するというトレード
mixi Engineers’ Blog » Inside Tokyo Cabinet その四
涼しさに夏の終わりを感じてなんだか寂しくなるも、新しいオフィスから見えるパノラマの空の高さに癒されているmikioです。秋は気が変わりやすいこともあり、今回は唐突にDBMの並列性についての考察を記してみます。 並列性って何? 最近はマルチコアのプロセッサが当り前になってきて、そのパワーを100%引き出すために、並列性をできるだけ高めることが求められるようになってきました。それについて考える前に、まずは用語の整理をしておきましょうか。 並行性 : 二つ以上のタスクを一緒に進めること。必ずしも同時に処理を行うとは限らず、Aを少しやってからBを少しやって、それからまたAを少しやって、またBをやって...といった、いわゆるタイムシェアリングで実現してもよい雰囲気。 並列性 : 二つ以上のタスクを同時に進めること。タスクを複数のマシンに割り当てたり、複数のCPUに割り当てたり、CPU内の複数のコアに
Inside Tokyo Cabinet その参 - mixi engineer blog
この連載のように小難しい記事が続くと、読者の皆さんだけでなく執筆陣まで引いてしまうのではないかと心配しているmikioです。いやいや、いいんです。ハッキングから夜のオカズまでバラエティに富んだブログを目指すべく、私は私なりの記事を、たとえマイノリティ向けだとしても臆さず書いてゆくのです。今回はTCの実装の詳細についてお届けします。 QDBMとどう違うの? QDBMもTCと同様にDBMの一実装で、小さくて速くて使いやすいをモットーに作りはじめて、それなりに目標を達成できたと自負しているプロダクトです。しかし、今思えばいろいろと気に入らない点がいくつかありました。TCはそれを克服すべく一から書き直したものです。具体的には以下の点が違います。 空間効率の向上 : データベースファイルのサイズがもっと小さい 時間効率の向上 : 読み書きにかかる時間がもっと短い 耐障害性の向上 : データベースファ
Inside Tokyo Cabinet その壱 - mixi engineer blog
約半年間の沈黙を破ってOSSの世界に戻ってきつつあるmikioです。先日、Tokyo Cabinet（以下「TC」と呼びます）というデータベースライブラリをリリースしました。今回から数回に分けて、TCの設計と苦労話について連載してみます。 DBMとは TCは、いわゆるDBMの系譜のデータベースライブラリで、単純なハッシュテーブルをファイル上で永続化するだけの機能を提供します。DBMはAT&Tの古代UNIXの時代から受け継がれる伝統芸能なのですが、私はそういう枯れた技術が大好きなのです。 プログラマの皆さんは、PerlやRubyではハッシュ（連想配列）と呼ばれ、JavaやC++ではmapと呼ばれるような、何らかのキーに関連づけてなんらかの値を記録するデータ構造って実によく使いますよね。例えばmixiでは、ユーザアカウントに関連する情報（名前とかニックネームとか）は、ユーザIDをキーにしたハッ
mixi Engineers’ Blog » スマートな分散で快適キャッシュライフ
今日は以前のエントリーで書くと述べたConsistent Hashingに関して語らせて頂こうかと思います。ただしConsistent Hashingはセミナーやカンファレンスなどでかなり語られていると思いますので、コンセプトに関しては深入りせず、実用性に着目したいと思います。 問題定義 分散されたキャッシュ環境において、典型的なレコードを適切なノードに格納するソリューションはkeyのハッシュ値に対しmodulo演算を行い、その結果を基にノードを選出する事です。ただし、このソリューションはいうまでもなく、ノード数が変わるとキャッシュミスの嵐が生じます。つまり実世界のソリューションとしては力不足です。 ウェブサイトのキャッシュシステムの基本はキャッシュがヒットしなかったらデータベースにリクエストを発行し、レコードが存在したらキャッシュしてクライエントに返すという流れです。ここで問題なのが一瞬
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
