データベースの動的デフラグ - mixi engineer blog
ノートPCの冷却ファンがうるさいのを対処しようとしてWebで調べたら、そのファンの設計者が「静音性へのこだわり」を語ったページにたどり着いて複雑な心境のmikioです。今回は、Tokyo Cabinet（TC）の最新バージョンで実装された動的デフラグ機能について長々と説明します。 断片化とデフラグ 任意のサイズのデータを管理する記憶装置においては、利用可能領域の断片化（fragmentation）の問題が常につきまといます。ファイルシステム上で任意のサイズのファイルを管理する際にも、データベースファイル内で任意のサイズのレコードを管理する際にも、C言語のmalloc/free関数群でメモリの管理をする際にも、様々なレイヤで断片化が起きうるのです。なぜなら、データを削除もしくは移動した際の空き領域を再利用するにあたって、その領域と同じサイズのデータが常に入ってくるとは限らないからです。特にデ
LSH (Locality Sensitive Hashing) を用いた類似インスタンスペアの抽出 - mixi engineer blog
GW 中の長距離移動のために体調が優れない takahi-i です. 今回は巨大なデータをマイニングする一つの技術として LSH (Localtiy Sensitive Hashing) を紹介させていただきます. LSH とは LSH は大量なデータから類似度が高いインスタンスのペアを高速に抽出してくれるアルゴリズムです. ここでインスタンスはデータ集合の一つの要素を表します. たとえば扱うデータが E-コマースサイトの購買ログであれば, インスタンスは各ユーザですし, 画像データ集合であれば, インスタンスは個々の画像データです. LSH の詳しい解説については以下のサイトがあります. Wikipedia のエントリ LSH に関する論文がまとめられているページ 本稿ではE-コマースサイトの購買履歴データを基に LSH の機能について述べてゆきます. 以下のような E-コマースサイトの
DBMによるテーブルデータベース その四 - mixi engineer blog
コアライブラリを一生懸命書くとユーティリティやバインディングなどの周辺機能がおろそかになり、逆も然りで、工数割り当てのジレンマが歯がゆいmikioです。今回は余談として、Tokyo Cabinetのテーブルデータベース（TCTDB）を作る途中で思いついた更新機能と性能検証について述べます。 アトミックな更新 再び TCTDBで好評だったっぽいアトミックな更新機能をその他のデータベースでも実装してみました。例えばハッシュデータベース（TCHDB）では以下の関数が提供されます。 typedef void *(*TCPDPROC)(const void *vbuf, int vsiz, int *sp, void *op); bool tchdbputproc(TCHDB *hdb, const void *kbuf, int ksiz, const char *vbuf, int vsiz,
PerlとRubyで省メモリなハッシュを使おう - mixi engineer blog
サボっていた早朝ジョギング＠駒沢公園を再開して2週間たち、やっと抜かれる数より抜く数の方が増えてきたmikioです。今回は、PerlやRubyのハッシュの代用としてTokyo Cabinetを使うことでメモリ使用量を激減させられることを説明します。 抽象データベースAPI Tokyo Cabinetには抽象データベースという機構があり、先日、そのPerlとRubyのバインディングをリリースしました。それを使うと、各種言語のハッシュとほぼ同じような共通したインターフェイスで、以下のデータ構造を利用することができます。 オンメモリハッシュ：各種言語に標準のハッシュと同じく、メモリ上でkey/valueの関係を表現する。 オンメモリツリー：メモリ上の二分探索木としてkey/valueの関係を表現する。 ファイルハッシュ：いわゆるDBMとして、ファイル上でkey/valueの関係を表現する。 ファ
Bayesian Setsによる関連文書検索システムStupa - mixi engineer blog
都会よりも田舎が好きなfujisawaです。Bayesian Setsというアルゴリズムを使って、関連する文書を高速・高精度に検索できるシステムを作成しましたので、そのご紹介をさせていただきます。 Bayesian Setsとは Bayesian Setsはいくつかアイテムを入力すると、それを補完するようなアイテムを返してくれるアルゴリズムです。原著論文の先頭に"Inspired by Google Sets"と書かれているように、Google Setsを参考にして作成されています。実際にどのような出力が得られるか、Google Setsに以下の表のクエリを検索して試してみますと、 クエリ 出力 apple, banana chocolate, strawberry, vanilla, cherry, ... apple, macintosh software, windows, mac,
検索クエリログからのスペル訂正辞書の自動生成 - mixi engineer blog
先月ハワイに行ってきてオルオルな （ハワイ語で '楽しい' という意味） 気分の takahi-i です。最近ログデータの有効活用が話題になっていますが、検索エンジンが出力する検索クエリログを使用してどんなことができるのかについて紹介させていただきます。 検索クエリログ 検索クエリログ (以下検索ログ) は検索エンジンを使用するユーザから発行された検索の履歴を保存したファイルです。検索ログのフォーマットは使用する検索エンジンや Web サーバによって異なります。さらにまた検索ログが含む情報にも差異があることが考えられますが、本稿では検索ログは解析を行う上で重要な三つの要素を含むと仮定します。三つの要素とはユーザ ID （もしくは IP アドレス）、クエリ文、そしてクエリが検索エンジンに処理された時間です。以下検索ログの一例を載せます。 ユーザID クエリ文 クエリ発行時 438904 Su
オレオレ検索窓を設置しよう - mixi engineer blog
まだピクミン2をクリアしてないのでケジメ的に新作ゲームを買えないmikioです。今回は、Tokyo Cabinetを使って激烈簡単に特定サイトの専用の検索機能を設置する方法について説明します。クローリングから検索までを10分くらいの作業で可能にします。 特定サイトの検索エンジン Web全体の検索機能を作るのは、途方もない技術力と設備を持っているGoogleやMicrosoftなどのビッグプレーヤでないと難しいのが現実です。でも、自分が気に入っているいくつかのサイトを対象とした検索エンジンを作るのであれば個人だってできます。また、インターネットから手が届かないイントラネットのコンテンツの検索機能は自分達で手がけないと構築できません。 ということで、企業用の検索システムが数多く売られていますし、LuceneやGroongaやHyper Estraierなどのオープンソース製品も世に多数存在しま
3行でできる超お手軽全文検索 - mixi engineer blog
梅雨。部屋干しした洗濯物による異臭騒ぎに苦しむmikioです。今回は、Tokyo Cabinetのテーブルデータベースで超お手軽に全文検索をする方法について説明します。 使い方 テーブルデータベースについてまずおさらいしておきましょう。PerlやRubyのハッシュのようにコラム名とその値を関連づけた構造を、主キーを識別子として保存するデータベースです。例えばRubyからデータを保存するに以下のように行います。データベースであることをほとんど意識させないというのが素敵ポイントです。APIはCでもPerlでもRubyでもほとんど同じなので、言語にかかわらず同じようにレコードを操作できます。 require 'tokyocabinet' include TokyoCabinet # データベースを開く tdb = TDB::new tdb.open("casket", TDB::OWRITER
DBMによるテーブルデータベース - mixi engineer blog
正月早々インフルエンザにかかって寝込んだmikioです。電車に乗る時や繁華街などに出る時はマスク着用が必須ですね。さて今回は、Tokyo Cabinetで実装したテーブル方式のデータベースについて紹介します。意外にどうして強力な機能なので、このネタは連載することを予告します。 テーブルデータベースとは 簡単に言えば、リレーショナルデータベースのテーブルのように、複数の列からなるレコードを格納できるデータベースです。SQLや表結合などの複雑な機能はサポートしませんが、そのぶん高速に動作します。つまり、DBMの速度で動くリレーショナル風データベースです（厳密にはリレーショナルデータベースではありません）。 TCの基本となるハッシュデータベースは、単純なkey/value型のデータベースであり、つまりキーにも値にもスカラ（数値や文字列などの特に構造を持たない単一の値）しか格納することはできません
Tokyo Tyrantによるリアルタイム検索 - mixi engineer blog
どうぶつの森にハマって、たぬきち商店が早終いする関係で退勤時間もめっさ早くなったmikioです。今回は、Tokyo TyrantのキャッシュとLua拡張を使って超お手軽にリアルタイム検索システムを作る方法について述べます。 ユースケース 高い頻度で更新されるWeb上のテキストをリアルタイムに検索したいと思ったことはありませんか？ mixi日記や各種のブログサービスやRSSリーダなどで扱う大量のコンテンツを安価かつ簡単に検索したいと思ったことはありませんか？ 私は結構あります。要件を箇条書きすると以下のような感じでしょうか。 最新データの合計100万件くらいを検索できればよく、古いデータは自動的に消えてほしい。 ただし、更新はリアルタイムにして、書いた瞬間に検索結果に反映されてほしい。 サーバ1台で更新1000qpsおよび検索100qpsは処理したい。 再現率よりも精度とリアルタイム性を重視
mixi Engineers’ Blog » 圧縮データベースを使おう
チャリンコ通勤による滝のような汗で、朝からTシャツがシースルーになってしまうmikioです。さて今回は、Tokyo Cabinet（TC）のデータベースを各種のアルゴリズムで圧縮して利用する方法についてご紹介します。 圧縮B+木 B+木とは、比較関数の値による順序が近いレコード群を単一のページにまとめ、各ページにB木（multiway balanced treeの略であり、二分木（binary tree）とは違います）の索引を張ったものです。理論的にはレコードの探索も更新も O(log n) の時間計算量で行え、内部ノード（B木）の操作をキャッシュすると実質的には O(1) の時間計算量で探索や更新が行えるという、かなり安定した性能を備えるデータ構造です。その上、レコードが一定の順序に基づいて並べられているので、数値の範囲検索や文字列の前方一致検索が高速に行えたり、カーソルによって順序に基
Tokyo TyrantによるHAハッシュDBサーバの構築 - mixi engineer blog
来年のバレンタインデーに、正確には「2009-02-14T08:31:30+09:00」に、UNIX時間が「1234567890」を迎えることを発見してちょっと嬉しいmikioです。さて、今回は高効率ハッシュデータベースサーバTokyo Tyrantを用いてHAハッシュデータベースを構築する手法についてご紹介します。ちょっと難しいし非常に長い内容なのですが、最後までお付き合いくださいませ。 可用性と保全性 HA（High Availability：高可用性）とは、可用性（Availability）が高いことです。それでは説明になっていないので詳しく言い替えますと、システムに障害が起きにくくすることと、たとえ障害が起きたとしてもできるだけ迅速に復旧できるようにすることです。データベース系のシステムはユーザのデータを管理するという中核的役割を担うため、可用性を高めることは最も重要な課題となりま
mixi Engineers’ Blog » OpenSSLの暗号文をJava/Perl/Rubyで開く
秘密鍵やプライベートな情報などを秘匿するためにパスワードでデータを暗号化・復号したい場合があります。このとき、暗号化と復号するアプリケーションが同じであれば簡単ですが、例えばCで暗号化してJava、Perl、Rubyで復号するといった風に異なるプラットフォームで暗号データをやりとりする場合には、いくつか気 をつけなければいけないポイントがあります。 OpenSSLによる暗号化 OpenSSLはWebサーバのSSL/TLSサポートに利用されますが、その他にも付属しているopensslコマンドから基本的な暗号アルゴリズムを利用できます。次のような簡単なコマンドで、パスワードを使ってデータを暗号化したり復号したりすることができます: $ echo 'Hello World!' | openssl enc -e -aes-128-cbc > cipher.txt enter aes-128-cbc
mixi Engineers’ Blog » memcachedのストレージ層をmodularにしてみた
前回に続いてまたmemcachedの話をしたいと思います。今回は改造編です。 ハッシュデータベースサーバなどの実装でmemcachedライクなものを書くのも良いですが、以前からmemcached自体のストレージをmodularにできたら面白いかも？と思っていたので実験的にmemcachedを改造してみました（memcached-1.2.4がベース）。 とりあえず名前はmemcached modularの略でmmcmodと名づけて、mikioさんのTokyo Cabinetをストレージとして使うモジュール（厳密にいうと共有ライブラリ）を書きました。ソースコードは後日CodeReposの方に上げますがとりあえずこの記事で公開します。ちなみに新しいプロダクトを作る気はなくて、最終的にpatchを作ることが目的です。 で、話を続けると今回の改造を簡単にビジュアライズするとこんな感じです： 図のmm
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
