October 21, 2010

Compressing URLs in your Webapp, for size and speed

Last year I had a chance to talk about the internals of our service: Pathtraq at Percona Performance Conference (slides), in which I described the methods we use to compress the URLs in our database to below 40% of the original size, however had not released the source code since then.  I am sorry for the delay, but have finally uploaded the code to

It is generally considered difficult to achieve high ratio for compressing short texts.  This is due to the fact that most compression algorithms are adaptive, i.e., short texts reach their end before the compressors learn how to encode them efficiently.

Our approach uses an algorithm known as "static PPM (prediction by partial matching)", that uses a pre-built table for compressing tables.

By using static PPM it is possible to achieve high compression ratio against hostnames or domains (e.g. "www" or "com") or English words that occasionally appear in paths or query parameters (e.g. "search").  And even in case of compressing unknown words in URLs the method works fairly well by utilizing the lower-order probability prediction tables for syllable-level compression.

The repository includes the source code of the compressor / decompressor (the core of the compressor; an optimized range coder using SSE, based on the work by Daisuke Okanohara, is actually git submoduleed from, Perl scripts for building compression tables, a small URL corpus for building and evaluating compression tables, and source code of a MySQL plugin that can be used to compress / decompress URLs using SQL.

By following the instructions in the README you will be able to build the compressor that compresses the URLs in the corpus to 30.5% in average, and use it in your MySQL database to store URLs more efficiently.  And one more thing, the benefit is not only for space efficiency.  Since the compressor is designed so that prefix search can be performed without actually decompressing them, in some cases your query becomes faster if you store the URLs in compressed form :-)

June 29, 2010

Q4M 0.9.4 released

I have just uploaded Q4M (Queue for MySQL) 0.9.4 to  There has been no bug fixes since 0.9.3, the only change is the newly added function queue_compact(table_name) that can be used to trigger table compaction manually.

If you were looking for a way to control queue compaction timing, it would be worth considering upgrading to 0.9.4.

For more information of what compaction is, please refer to my last entry on Q4M describing concurrent compaction.

April 26, 2010

MySQL and the XFS stack overflow problem

I have heard that there have been talks at MySQL UC on running MySQL (InnoDB) on top of XFS for better write concurrency than ext3.

Last weekend I had a chance to discuss on Twitter the xfs stack overflow problem (that became apparent this month, on x86_64 systems with 8k stack) and how it would affect (if any) MySQL servers.  If I understand correctly, the problem is that stack overflow might occur when a dirty page needs to be paged-out to xfs.

The conclusion was that for stability of MySQL running on xfs:

  1. xfs should not be used on top of LVM or any other MD (i.e. software RAID, etc.)
  2. xfs volumes should only contain ibdata files (that are accessed using O_DIRECT) so that the files on xfs would never exist as dirty pages within the OS


March 25, 2010

Q4M 0.9.3 prerelease (with support for "concurrent compaction")

Q4M (Queue for MySQL) periodically performs an operation called "compaction", which is sort of a garbage collection, that collects empty space from a queue file and returns to the OS.

The pitfall that exists until now was that during compaction, all operation on the queue table was being blocked.

My opinion was (is) that it is not a serious problem for most users, since the time required for compaction will be small in most cases (the time depends on the number (and size) of the rows alive on the queue table, and the number of the rows alive will be mostly small).

But for usecases where fast response is a requirement, I have added a "queue_use_concurrent_compaction" option to Q4M in the 0.9.3 prerelease.  When the variable is set to one in my.cnf, INSERTs will not be blocked during compaction.  Another configuration variable queue_concurrent_compaction_interval is also available to fine-tune response time of INSERTs during compaction.  The response of INSERTs during compaction will become faster as you set the variable smaller, although the compaction will become slower as a side effect.

# enable / disable concurrent compaction (0: disabled (default), 1: enabled)

# handle INSERTs for every N bytes of data is compacted (default: 1048576)

If you are already using Q4M without any problems, I recommend sticking to the version you are using, since the stability of Q4M might have degraded due to the introduction of the feature.

On the other hand if you were having problems with the issue or planning to use Q4M for a new application, I recommend using this release.  Have fun!  And if you find any problems, please send stacktraces to me :-)

January 22, 2010

Q4M 0.9.2 prerelease avaiable fixing data corruption on 32bit systems

Thanks to a user of Q4M, I have found a bug that would likely lead to data corruption on 32bit versions of Q4M.  64bit versions are unaffected.

Q4M by default uses mmap(2) to read from data files.  On 32bit systems, it tries to map max. 1GB per each table into memory using mmap.  When mmap fails to map memory due to low memory, Q4M falls back to file I/O to read the data.

However there was a bug in handling the response from mmap, that led to reading corrupt data from database files when mmap(2) failed after the size of the underlying file was grown / shrunk by Q4M.  And since Q4M writes back the corrupt data into the database file when rows are being consumed, the bug will likely destroy the database files.

I have fixed the bug and have uploaded Q4M 0.9.2, into the prerelease directory at  Source tarball and prebuilt binaries for MySQL 5.1.42 for 32bit linux are available.

If you are using 32bit versions of Q4M, I highly recommend either to update to 0.9.2 or switch to 64bit versions if possible.

BTW in 0.9.2 release, I also changed the maximum mmap size per table from 1GB to 256MB, to lower the possiblity of low memory.  However this countermeasure might not be sufficient in some cases, i.e. databases having many Q4M tables or if other storage engines also used a lot of memory.  I am considering of just disabling the use of mmap(2) on 32bit systems in future releases.  If you have any comments on this, please let me know.

January 20, 2010

Building a highly configurable, easy-to-maintain backup solution for LVM-based VMs and MySQL databases

Motives and the Features

For the servers running in our new network, I was in need for a highly configurable, but easy-to-use backup solution that can take online backups of VMs and MySQL databases running multiple storage engines.

Since my colleagues are all researchers or programmers but there are no dedicated engineers for managing our system, I decided to write a set of command line scripts to accomplish the task instead of using an existing, highly-configurable but time-taking-to-learn backup solutions, like Amanda.

And what I have come up with now is a backup solution with following characteristics, let me introduce them.

  • a central backup server able to take backup of other servers over SSH using public-key authentication
  • no need to install backup agents into each server
  • LVM snapshot-based online, incremental backups (capable of taking online backups of LVM-based VMs)
  • taking online backups of MySQL databases running mulitple storage engines with sophisticated lock control
  • no configuration files, only use crontab and shell-scripts

The solution consists of two tools, blockdiff (kazuho's blockdiff at master - GitHub), and cronlog script of kaztools (kazuho's kaztools at master - GitHub).


Blockdiff is a set of scripts for taking block-based diffs of files or volumes on a local machine or on remote machines over the network using SSH.  The script below takes online backup of three LVM volumes from three servers.  In the form below, a full backup will be taken once a month, and incremetal backups will be taken during every month.
#! /bin/bash

export YEARMONTH=`date '+%Y%m'`

# backup a LVM volume (using snapshot) at /dev/pv/lv on srv00
blockdiff_backup /var/backup/srv00-pv-lv-$YEARMONTH ssh_lvm_dump --gzip \
  root@srv00 /dev/pv/lv \
  || exit $?

# backup another LVM volume on an another server
blockdiff_backup /var/backup/srv01-pv-lv-$YEARMONTH ssh_lvm_dump --gzip \
  root@srv01 /dev/pv/lv \
  || exit $?

# backup a MySQL database stored on volume /dev/pv/lv on server db00
  LVCREATE_PREFIX='mysqllock --host=db00 --user=root --password=XXXX' \
  blockdiff_backup /var/backup/db00-pv-lv-$YEARMONTH ssh_lvm_dump --gzip \
  root@db00 /dev/pv/lv \
  || exit $?

The backup command of the last volume uses mysqllock command included in blockdiff to keep "FLUSH TABLES WITH WRITE LOCK" running while taking a snapshot of the LVM volume on which the database files exist.  It is also possible to implement other kinds of locks so as not to issue the "FLUSH TABLES WITH WRITE LOCK" while long-running queries are in execution.  Since the flush statement blocks other queries until all of the already running queries complete, issuing the flush query when long-running queries exist will lead to the database not responding to other queries for a certain amount of time.

Crontab and the cronlog script

The backup script is invoked by cron via cronlog, a script that logs the output of the executed task, as well as controlling the output passed to cron so that an alert mail will be sent when the backup script fails.  It uses setlock command of daemontools for holding an exclusive lock while running the backup script (and to alert the administrator on when failing to acquire the lock).

Crontab script
5 3 * * * cd /var/backup && exec setlock -nX /tmp/backup.lock cronlog -l /var/backup/backup.log -t -- ./ 2>&1

This is all that needs to be set up to backup LVM volumes including MySQL databases.  Output of the log will be like the following.

[Sat Jan  9 03:05:02 2010] backup-srv starting: ./
[Sat Jan  9 03:05:02 2010] creating snapshot...
[Sat Jan  9 03:05:07 2010]   Logical volume "lvm_dump" created
[Sat Jan  9 03:05:07 2010] running: ssh_blockdiff_dump --gzip "root@srv00" "/dev/pv/lv"...
[Sat Jan  9 03:19:22 2010] removing snapshot /dev/pv/lvm_dump...
[Sat Jan  9 03:19:23 2010]   Logical volume "lvm_dump" successfully removed
[Sat Jan  9 03:19:23 2010] backup completed successfully
[Sat Jan  9 03:35:56 2010] creating snapshot...
[Sat Jan  9 03:35:56 2010] issuing lock statement: FLUSH TABLES WITH READ LOCK
[Sat Jan  9 03:36:00 2010]   Logical volume "lvm_dump" created
[Sat Jan  9 03:36:00 2010] issuing unlock statement: UNLOCK TABLES
[Sat Jan  9 03:36:00 2010] running: bin/ssh_blockdiff_dump --gzip "root@db00" "/dev/pv/lv"...
[Sat Jan  9 04:18:44 2010] removing snapshot /dev/pv/lvm_dump...
[Sat Jan  9 04:18:46 2010]   Logical volume "lvm_dump" successfully removed
[Sat Jan  9 04:18:46 2010] backup completed successfully
[Sat Jan  9 04:18:46 2010] command exited with code:0

The files in the backup directory will be like below.  The .gz files contain the backup data, and .md5 files contain per-block checksums used for taking incremental or differential backups.

The backup files
% ls -l db00-pv-lv-201001*
-rw-r--r-- 1 backup backup 50289166539 2010-01-01 05:35 db00-pv-lv-201001.1.gz
-rw-r--r-- 1 backup backup   131072004 2010-01-01 05:35 db00-pv-lv-201001.1.md5
-rw-r--r-- 1 backup backup 10914423057 2010-01-02 04:32 db00-pv-lv-201001.2.gz
-rw-r--r-- 1 backup backup   131072004 2010-01-02 04:32 db00-pv-lv-201001.2.md5
-rw-r--r-- 1 backup backup 13648250036 2010-01-03 04:33 db00-pv-lv-201001.3.gz
-rw-r--r-- 1 backup backup   131072004 2010-01-03 04:34 db00-pv-lv-201001.3.md5
-rw-r--r-- 1 backup backup           3 2010-01-18 04:34 db00-pv-lv-201001.ver

For more information, please read the source code and the accompanying documentation.


As can be seen, this is a powerful backup solution that can be built up with minimum setup. It will work well if you work in a small number of experienced engineers, while it might not be suitable for large-scale deployments with many admins.  If you are interested, please give it a try.  I am looking forward to your ideas and / or suggestions.

PS. The blockdiff_merge command can be used to restore the backups.

January 18, 2010

blockdiff を使ったお手軽ホットバックアップ環境の構築 (Linux, MySQL, etc.)

 一昨日に開催された hbstudy #7 にバックアップの話を聞きに行ってきました。Amanda を中心にした話で、とても勉強になりました。が、設定がめんどくさそうだなぁ、とも。自分の需要にはあわない感じでした。

 勉強会が終わったあとで、自作のバックアップスクリプト blockdiff に関する話を何人かの方とさせていただいたのですが、思いのほか反応が良かったので、あらためて紹介したいと思います。

 blockdiff は、一言でいうと、パーティションやデータベースのデータファイルの差分バックアップツールです。rsnapshot に似ていますが、rsnapshot ではデータベースのホットバックアップ不可能です。逆に blockdiff はディレクトリ単位でのバックアップには対応していないかわり、ファイルシステムやデータベースを、一貫性を保ちつつ実質無停止で差分バックアップすることができます

 blockdiff の具体的な特徴は以下のとおりです。

  • 設定ファイルが不要
  • 複雑な設定がありません。コマンドライン (あるいは crontab) で、適当な引数をつけてバックアップコマンドを呼び出すだけの簡単インターフェイスです。コマンドラインで動作を制御するため、(ホットバックアップを含む) 様々なバックアップロジックを組むことも可能です。

  • バックアップを取るサーバにソフトウェアのインストールが不要
  • ssh 経由でリモートサーバのバックアップを取ることができます。サーバにバックアップソフトウェアをインストールする必要はありません (バックアップを取るために必要なプログラムは自動的に送り込まれます) 注1

  • フルバックアップと増分バックアップに対応
  • フルバックアップと増分バックアップに対応しています。また、下位レイヤのスクリプト (blockdiff_dump) を直接実行すれば、差分バックアップも可能です。

  • ファイル単位、あるいは LVM スナップショットを使ったバックアップが可能
  • ファイル単位のバックアップと、LVM スナップショットを使ったホットバックアップに対応しています。

  • MySQL のホットバックアップが可能
  • 同梱の mysqllock コマンドと組み合わせることで、LVM スナップショットを使った MySQL データベースのホットバックアップが可能です。PostgreSQL については確認はしていませんが、ロックコマンドを使わなくてもバックアップが取れるんじゃないかと思います。

  • LVM ベースの VM のホットバックアップが可能
  • LVM ベースの仮想ディスクを用いた Xen の DomU のホットバックアップが可能です注2。私は使っていないので試していませんが、KVM の仮想マシンについても同等のことが可能だと思われます。LVM ベースではない VM についても、スナップショット機構によってはホットバックアップが可能だと思われます。

 blockdiff を使った LVM ボリュームのバックアップ方法については Kazuho@Cybozu Labs: リモートからXenのDomUとかLVMやファイルを差分バックアップするスクリプトを書いた で触れたので、ここでは MySQL データベースをホットバックアップする場合の設定を紹介したいと思います。前提として、MySQL のデータが LVM ボリューム上に保存されている必要があります。


#! /bin/bash

export BLOCKSIZE=16834
export LVCREATE_PREFIX="mysqllock --host=db-host --user=root --password=XXX"
export YEARMONTH=`date '+%Y%m'`

blockdiff_backup /var/backup/db-backup-$YEARMONTH bin/ssh_lvm_dump --gzip \
  root@db-host /dev/mapper/logical_volume_of_mysql


  • バックアップのブロックサイズを InnoDB のブロックサイズである 16KB に設定
  • スナップショットを取る瞬間に mysqllock コマンドを使って FLUSH TABLES WITH READ LOCK を使うことで、MyISAM テーブル等の一貫性のあるバックアップを実現
  • 1ヶ月毎にフルバックアップ。それ以内は増分バックアップ

 バックアップスクリプトを実行すると、最初に db-backup-YYYYMM.1.gz, db-backup-YYYYMM.1.md5, db_backup-YYYYMM.ver という3つのファイルが作成されます。YYYYMM.1.gz がバックアップデータ、YYYYMM1.md5 がブロック単位のチェックサム情報です。次に実行すると YYYYMM.2.* が、その次は YYYYMM.3.* が、という形で増分バックアップが増えていきます。最新のバックアップの番号は .ver ファイルが記憶しているので、バックアップが途中で失敗しても問題ありません。次回バックアップ時に壊れたバックアップファイルが上書きされます。

% ls -l db-backup-201001*
-rw-r--r-- 1 backup backup 50289166539 2010-01-01 05:35 db-backup-201001.1.gz
-rw-r--r-- 1 backup backup   131072004 2010-01-01 05:35 db-backup-201001.1.md5
-rw-r--r-- 1 backup backup 10914423057 2010-01-02 04:32 db-backup-201001.2.gz
-rw-r--r-- 1 backup backup   131072004 2010-01-02 04:32 db-backup-201001.2.md5
-rw-r--r-- 1 backup backup 13648250036 2010-01-03 04:33 db-backup-201001.3.gz
-rw-r--r-- 1 backup backup   131072004 2010-01-03 04:34 db-backup-201001.3.md5
-rw-r--r-- 1 backup backup           3 2010-01-18 04:34 db-backup-201001.ver

 バックアップスクリプトが正しく動作することを確認したら、crontab を設定して毎日バックアップを取るようにします。

0 4 * * * setlock -nX /var/backup/backup.lock cronlog -l /var/backup/backup.log -t -- /var/backup/ 2>&1

 ここでは、daemontools の setlock コマンドを使って万が一の重複起動を抑止しています。また、kaztools の cronlog コマンドを使うことで、バックアップの進捗をログに保存しつつ、バックアップが失敗した場合は cron 経由でアラートメールが送信されるようになっています。

 ちなみに、バックアップのログ (backup.log) は、毎日次のような感じで追記されていきます。データベースの停止期間 (アプリケーションからのクエリがロックされる期間) は 03:35:56 から 03:36:00 までの4秒間であり、実質無停止でのバックアップができていることがわかります。

[Sat Jan  9 03:05:02 2010] backup-srv starting: /var/backup/
[Sat Jan  9 03:05:02 2010] creating snapshot...
[Sat Jan  9 03:05:07 2010]   Logical volume "lvm_dump" created
[Sat Jan  9 03:05:07 2010] running: bin/ssh_blockdiff_dump --gzip "root@db-host" "/dev/db/lvm_dump"...
[Sat Jan  9 03:19:22 2010] removing snapshot /dev/db/lvm_dump...
[Sat Jan  9 03:19:23 2010]   Logical volume "lvm_dump" successfully removed
[Sat Jan  9 03:19:23 2010] backup completed successfully
[Sat Jan  9 03:19:23 2010] creating snapshot...
[Sat Jan  9 03:35:56 2010] issuing lock statement: FLUSH TABLES WITH READ LOCK
[Sat Jan  9 03:36:00 2010]   Logical volume "lvm_dump" created
[Sat Jan  9 03:36:00 2010] issuing unlock statement: UNLOCK TABLES
[Sat Jan  9 03:36:00 2010] running: bin/ssh_blockdiff_dump --gzip "root@db-host" "/dev/x25m.1/lvm_dump"...
[Sat Jan  9 04:18:44 2010] removing snapshot /dev/x25m.1/lvm_dump...
[Sat Jan  9 04:18:46 2010]   Logical volume "lvm_dump" successfully removed
[Sat Jan  9 04:18:46 2010] backup completed successfully
[Sat Jan  9 04:18:46 2010] command exited with code:0

 このように、blockdiff を使うことで VM 単位のバックアップだけでなく、データベースのホットバックアップも簡単に取ることができます。パストラックでは、これらバックアップスクリプトに処理を追加し、バックアップ中は統計処理を抑止するといったことも行っています。

 blockdiff や kaztools は、いずれも私の github リポジトリ ( からダウンロードして perl Makefile.PL && make all test && make install でインストール可能です。あるいは nopan がインストールされていれば、nopan と1コマンドでインストールすることができます。いずれもパストラックで実際に運用しているツール群ですが、興味のある方は (at your own risk で) お試しあれ。

注1: バックアップを取るサーバに Perl 5.8 以降がインストールされている必要があります。また、公開鍵認証を用いて SSH ログインできる必要があります
注2: XenServer のスナップショット機能とは併用できません

January 06, 2010

Q4M 0.9 released

Q4M 0.9 is now available from, along with prebuilt binaries for MySQL 5.1.42 (running on linux and Mac OS X 10.5).

The release fixes a deadlock issue under high load.  Thank you to the users for sending the necessary information to resolve the issue.

If you still find any deadlocks or stability problems of Q4M, please send stacktraces of all threads (by attaching gdb to mysqld and executing "thread apply all bt").

December 14, 2009

Comparing InnoDB performance on HDD, SSD, in-memory

The chart shows benchmark results taken using sysbench.  Rough understanding would be that (for this scenario) the performance ratio is HDD:SSD:in-memory = 1:10:50.

transactions/sec. read/write reqs./sec.
buffer_pool=8M, HDD 19.93 378.59
buffer_pool=8M, SSD (Intel X25-M) 207.70 3946.29
buffer_pool=2048M, HDD 998.82 18977.51


The benchmark was taken using MySQL 5.1.41 using innodb_plugin running on linux 2.6.31/x86_64 (Ubuntu 9.10 server).  Options passed to sysbench were: --test=oltp --db-driver=mysql --mysql-table-engine=innodb --oltp-table-size=1000000 --mysql-user=root --mysql-db=test --oltp-table-name=test_t --num-threads=20 .  My.cnf was set as follows.

innodb_read_io_threads=4           # set to 10 for X25-M
innodb_flush_log_at_trx_commit=2   # sufficient for our task

December 03, 2009


 MySQLを使っていると書込みロックをかけてバックアップを取る、ってのは一般的だと思います。実際、標準添付の mysqlhotcopy や Xtrabackup もそういうことをやっています。


 特にボリュームレベルのスナップショット機能を使ってバックアップを取る場合、スナップショットを取るためのコマンドは環境(LVM とか XenServer とか VMware ESXi とか...)によって異なるので、ロック管理とバックアップコマンドは疎結合にしておきたい。と思ったので、書くことにしました。というか、疎結合なのを探すより書いたほうが早かった。コードはこちら↓。

kazuho's blockdiff at master - GitHub

 使い方は、以下のとおり。setlock 風のインターフェイスなので、慣れている人には簡単だと思います。

% mysqllock --help
Usage: ./mysqllock [options] cmd
Options: --user=db_user    username (default: current user)
         --password=pass   password (default: none)
         --host=db_host    db host (default:
         --port=db_port    db port (default: 3306)
         --db=db_name      database name (default: "mysql")
         --before=stmt     statement to execute before running the command
                           (default: "FLUSH TABLES WITH READ LOCK")
         --after=stmt      statement to execute after running the command
                           (default: "UNLOCK TABLES")

 自作のバックアップツール(Kazuho@Cybozu Labs: リモートからXenのDomUとかLVMやファイルを差分バックアップするスクリプトを書いた)も、1行パッチをあてるだけで、テーブルロックをした状態でスナップショットを取ってから、バックアップを取れるようになりました。こんな感じで。

% SNAPSHOT_SIZE=5G BLOCKSIZE=65536 LVCREATE_PREFIX='bin/mysqllock --host=mysqld.local --user=root --password=XXXXXXXX'  bin/blockdiff_backup backup-name bin/ssh_lvm_dump -z root@mysqld.local /dev/XXXXXXXX/XXXXXXXX
creating snapshot...
issuing lock statement: FLUSH TABLES WITH READ LOCK
  Logical volume "lvm_dump" created
issuing unlock statement: UNLOCK TABLES
running: bin/ssh_blockdiff_dump -z "root@mysqld.local" "/dev/XXXXXXXX/lvm_dump"...
removing snapshot /dev/XXXXXXXX/lvm_dump...
  Logical volume "lvm_dump" successfully removed
backup completed successfully


参考: Kazuho@Cybozu Labs: setlock を使って cron をぶんまわす方法