先日、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では新たなクライエント接続に対して専用スレッドを割り当てるといった古典的なモデルを採用しています。割当を実際に行うのはコネクションマネージャというNetwork Interfaceを監視するスレッドであり、OSによってlistenするインターフェイスが異なります。

マネージャは無駄に新たなスレッドを生む事を避けるために、接続に割り当てるスレッドがキャッシュに存在するかを調べます。役目を終えたスレッドはスレッドキャッシュに空きがあった場合にキャッシュされますが、ない場合は破棄されます。

スレッドキャッシング

スレッドキャッシュのサイズはthread_cache_sizeというシステム変数によって定められ、デフォルト値は0です。したがって、デフォルト設定のMySQLは新たな接続に対し新たなスレッドを生成し、接続が完了したらスレッドを破棄するという処理を繰り返します。thread_cache_size変数は起動時と運用中のどちらでも変更する事が可能です。

問題点

このモデルの問題点は当然ながら、スレッドの数がクライエント接続数に比例して増えるという事です。連続するスレッド生成と破棄のコストを考慮にいれると、効率のよい仕組みとは呼べません。さらにスレッド数（接続数）の増減に比例して消費するサーバ資源が増えてしまうので、個々のスレッドが持つスタック領域を抑えるという実装になっています。

MySQL 6.0.4からの仕組み

従来のモデルで問題視された多くの同時接続を円滑に処理するためにスレッドプーリングが採用されます（実装はされている）。コネクションマネージャは特定の接続にスレッドを割り当てるのではなく、完全にクライエントからのリクエストを受信した後に処理待ちのタスクキューに追加します。

サーバはサービススレッドのプールを管理し、処理待ちのリクエストをプール内の使用可能なスレッドに割り当てます。リクエスト処理の終えたスレッドは再び使用可能な状態となり、他リクエストの処理を行います。

ワーカスレッドたちはサーバの起動時に生成され、サーバプロセスが終了するまで生き続け、特定のコネクションに縛られません。また、プールのサイズは固定であるため、消費する資源がコネクション数に比例して増える事がありません。とまあ、典型的なプーリングモデルですね。

スレッドプーリングの弱点

多数のコンプレックス（多めの演算力とI/Oを伴う）クェリーが頻繁に発行される環境では、スレッド数の上限設定が仇になる場合があります。全スレッドが複数のクライエントからのリクエストを処理する場合、当然ながら新たなリクエストに対応する事ができず、サーバが固まってしまいます。この問題はスレッドプールの限界値を上げる事で対処する事が推奨されています。限界値はthread_pool_sizeというシステム変数により定めれており、これを起動時に指定する事で変更が可能です（デフォルト値は20）。

運用法や設定

スレッドプーリングはmemcachedで実績があるlibeventを使って実装されており、適用するにはconfigure時に--with-libeventを指定する必要があります。スレッドモデルの選択はサーバの起動時にthread_handlingシステム変数によって判別されます。デフォルトのスレッドマネージメントモデルは接続に対して専属のスレッドが割り当てられる “--thread_handling=one-thread-per-connection”モードです。スレッドプーリングを適用するには、--thread_handling=pool-of-threadsオプションでサーバを起動します。

Drizzleでは？

全てのソリューションやアルゴリズムにはユースケースによって必ず何らかの弱点が存在します。Drizzle Projectではサーバの軽量化と同時に、幅広い問題を柔軟に解決するためにMicroKernelアーキテクチャを採用しています。これはスレッドスケジュリングも例外ではなく、MySQLのスレッドマネージメントコードは完全にコアから抜き取られ、分離されています。

正確に述べると、MySQL内でいう、one-thread-per-connectionとpool-of-threadsの両モードのコードが完全にモジュール化されています。これは何が嬉しいかといいますと、まずmutexをコアから外部（モジュール）に押し出す事によってlock contentionの対応をサーバから分離できる事です（小人さんがロックレスなモジュールを書いてくれるかも！）。あとは、ソースコードがスマートに整理できるというところでしょうか。例えばスレッドプーリングってどうやって実装されているの？と気になった場合はまずプラグインのインターフェイスを見て、

#ifndef DRIZZLED_PLUGIN_SCHEDULING_H
#define DRIZZLED_PLUGIN_SCHEDULING_H
 
typedef struct scheduling_st
{
  bool is_used;
  uint32_t max_threads;
  bool (*init_new_connection_thread)(void);
  void (*add_connection)(Session *session);
  void (*post_kill_notification)(Session *session);
  bool (*end_thread)(Session *session, bool cache_thread);
} scheduling_st;
 
#endif /* DRIZZLED_PLUGIN_SCHEDULING_H */

モジュールの実装（drizzle/pluginディレクトリ以下）を覗くだけで、簡単に読む事ができます。例えばスレッドプーリングの実装だと以下のファイルをお好みのエディタで開くとよいでしょう：

$ vi drizzle/plugin/pool_of_threads/pool_of_threads.cc

とまあ、パッケージ内を比較的簡単に泳ぐ事ができ、システム改善を従来の設計よりも簡単にハックする事が可能です。

まとめ

MySQLのスレッドマネージメントの現在と今後、そして制限や弱点を調査し、メモを公開しました。また、MySQLが抱える、このドメインの問題に体するDrizzleのアプローチも共有し、lock contentionの対応をコアから押し出す利点を紹介しました。

今回のエントリーだけだとMicroKernelの詳しい設計やモジュールの事が全然わからん！と突っ込まれそうですが、そこまで書くと膨大なエントリーになりそうなので、また別の機会に紹介します。同時に今後もDrizzle Projectで面白かったり、嬉しいネタが出てきたらちょくちょく共有していきたいと思います。

朝晩冷えてきましたね。風邪など引いていませんでしょうか。さて、年末が近づいてくるこの時期に弊社のエンジニアが最も気になるのは、お正月。それも来年1月1日を迎えた瞬間です。

1日1日0時に何があるのでしょう？そう、mixiのサービスで最も日記が書き込まれるタイミングになるのです。個人的に「あけおめことよろアタック」と呼んでいます。今年は日記だけではなく、エコーでもメッセージが飛び交うことでしょう。この時期は携帯電話のキャリアでもさまざまな対策を行っていますが、ミクシィでも年末年始でもユーザの方に快適にサービス提供ができるように努めています

以下は昨年の年末年始の日記投稿数の推移です。青色が12/31から1/1、赤色が1/1から1/2になります

1/1の方が全体的に多いですが、特に年が変わる前後の投稿数は倍近くなっていることがわかります。この時に負荷により日記の投稿がしづらい状態になっていたので、もっと多くの日記が書かれていたと思われます。

日記の投稿でエラーが起きた原因は、日記のIDを生成するシステムの過負荷にあります。mixi日記では全体で1つの通し番号が付いていますが、このIDを生成するシステムに負荷が集中し、IDが取得できなくなり日記が書けないという状態が発生してしまっていました。

■ID Generatorの改善

そこで来年に向けて、まずはIDを生成するシステムの改善に手を付けました。
日記のID生成システム、「ID Generator」はMySQLのLAST_INSERT_ID()を利用して実装されており、以下のようなテーブルとスクリプトを用いています。

テーブル

create table idpot (
    id bigint unsigned
);

スクリプト

my $next_id;
my $rv  = $dbh->do('UPDATE id_pot SET id=LAST_INSERT_ID(id+1)');
if ($rv == 1) {
    $next_id = $dbh->{'mysql_insertid'};
}

この実装で通常のサービスで問題がでることはありませんが、正月明けのようなアクセスが特に集中する時には、この部分でMySQLがdead lockを引き起こしてしまいます。実は、この問題は既に去年の11月に当ブログで紹介させて頂いてます。dead lockはMySQLに接続するクライアント数が多くなると発生します。

mybenchを利用したテストでは、接続数が250を超えるとエラーが発生しテストが正常に終了しません。

(MySQL 5.0でテスト。クライアント数250では正確な数値は取得できず)

2008年でもこの問題について把握はしていましたが、クライアント数についての見積もりがあまく、dead lockが予測よりも速く発生してしまったため、日記が書けない事態が発生しました。そこで今年はID Generator自体に手を加えました。

ID GeneratorはMySQLへの接続本数を減らすことで改善を目指しました。具体的にはアプリケーションサーバから直接MySQLに接続するのではなく、専用のAPIサーバを置いて間接的に接続するようにしました。APIのサーバはmod_perlのhandlerとして構築をし、ApacheのMaxClientも1台あたり10程度としました。アプリケーションサーバからの接続はtcpのbacklogに積まれますので、MaxClientが少なくても処理が詰まったりしない限りは問題ありません。もしAPIからIDが取得できない場合は、アプリケーションサーバから直接MySQLを参照します。

APIの性能は「ab」を利用してテストしたところ、1台あたり2000req/s以上の性能がでています。簡単なDBのシミュレーションでも秒間数百の処理ができることも確認しています。

■最新情報DBへの書き込みを非同期に

ID Generatorを改善することで現在顕在化しているボトルネックの解消はできましたが、今年はもう一つ、次に問題になりそうなDBの改善にも取り組みました。mixiの日記DBは弊社でLevel2分散と読んでいるユーザパーティショニングを行っています。日記のDBはノードと呼ばれる日記を保存するDBと、マネージャーと呼ぶ、ユーザの日記がどのノードにあるかを管理するDBの２種類があります。ユーザの日記を表示する時にはマネージャーのDBに接続をし、ユーザIDから、どのノードに日記が保存されているのを問い合わせ、その結果得られたノードDBに再度接続をするようになっています。

ただし、この状態ではホームなどのマイミク最新日記を取得する場合に、全部のノードに1つ1つ接続をしてマイミクの最新の日記を検索しなればならないので、ノードとは別に最新日記のIDとタイトルだけを入れる最新情報DBを用意してあります。ちょうど1週間のデータを保存していますので、Weekly DBと呼んでいます。日記が投稿された際には、各ノードとWeekly DBの２カ所にデータを保存しています。

Weekly DBは負荷的な問題は現状ありませんが、1月1日のような日記が集中して書かれる瞬間では、書き込みが多くのアプリケーションサーバから一斉に行われるため、ボトルネックになることが予測されます。

そこでエコーでも用いたQ4MというMySQLのStorage Engineとして開発されているJob Queueのシステムを日記投稿にも投入しました。

書き込みを一旦Q4Mでキューイングし、表側の非同期にWeekly DBへと書き込んで行きます。日記の投稿が集中した場合、Weekly DBではDisk IOを分散することが難しいですが、Q4Mを用いる事でIOを時間軸で分散することができるのでWeekly DBへの負荷が集中し、サービスに影響が出てしまうのを防ぐ事ができます。また、Q4M自体の負荷が高まった場合は、単純に台数を増やす事で解決ができます。

Q4Mを導入した事でもう一つ耐障害性が高まった部分があります。Weekly DBにハードウェア障害が起きた場合にも最新日記をQ4M上に貯めておき、DBが復旧した時点であらためてDBに挿入していくことができます。これによってマイミクの最新日記をQ4M導入前よりも確実に届けることができます。

■まとめ

2009年1月1日にむけて2つの改善を行いました。1つはIDを生成するDB、もう一つは最新情報DBへの保存の非同期化です。2009年”は”ユーザの皆様の「あけおめことよろ」をすべて正常に受け付けることができると思います。来年1月1日に良い結果がでれば、またエンジニアブログで紹介したいと思います。

こんにちは。mixi開発部のyouheiです。
今回は先日8月4日にリリースした「エコー」について書きたいと思います。

■エコーとは

まずはエコーとはどういう機能かのご紹介ですが、プロモーションページがございますのでそちらをご覧いただければ幸いでございます。
http://mixi.jp/guide_echo.pl

いくつか抜粋しますと、

あなたの“今”を一言にしてみませんか？誰かに伝えたいこと、ひとりごと等、何でもOK！ 気軽な新コミュニケーション機能です。

たとえば、「今日はいい天気だな～」という、ひとりごとから、「お腹すいたー！誰かランチにいこうよ！」というメッセージ的な使い方まで、「エコー」の楽しみ方はあなた次第！

マイミクシィ同士で「エコー」を使うとホームにお互いの書きこみが表示されます。気になった書きこみには、返信することもできちゃいます。あなたがふと書きこんだ一言に、思わぬ返信があるかも！？

といった機能です。

当エンジニアブログではエコーの機能的な側面よりも、裏側はどうなっているのか、そのあたりをメインに書きたいと思います。

■基本はLevel2分散

mixiの分散アーキテクチャは今までにも様々な場で紹介させていただいておりますが、mixi社内では分散の方法を

• 「日記」「コミュニティ」など、機能ごとにDBを分割する垂直分散をLevel1分散
• さらにそれをユーザーごとに別のDBに分割する水平分散をLevel2分散

と呼んでいたりします。
今回のエコーも例によってLevel2の分散を行っています。
即ち、

• 各ユーザーのエコー投稿を貯め込むEcho Node DB
•  どのユーザーがどのノードに書かれているのかマッピングを管理するEcho Manager DB

基本的にはこの2つのDBを立てることでLevel2分散が実現できます。

■Level2分散が仇になる点

ところがLevel2分散をすると逆に実装しづらくなる機能として、「みんなのエコー」という機能があります。これは、自分や自分のマイミクたちの発言をタイムライン上で一気に見れるページなのですが、この機能を実装するにあたっては、複数のDBにデータを分散するLevel2分散では、一度データを収集した後でそれを並び替える、という工程が発生しコストがかかってしまうため逆に仇となってしまいます。
同様な機能のページとしては「マイミクシィ最新日記」等のページもそうです。

■Recent DB

これらのページを実現するにあたって、Echoでは「Recent DB」と呼ぶものを用意しています。
このDBはその名の通り、最近のみなさんの書き込みを貯め込むDBで、すべてのユーザーの発言が集約されています。
「すべてのユーザーの発言」という表現をするとデータ量が肥大化しそうに感じますが、その点においてはプロモーションページにも明記していますが、「みんなのエコー」ページに表示される書きこみは直近2日分のみという仕様なのでそれほど膨らむことはありません。

また、すべてのユーザーが「みんなのエコー」のページを表示する度にこのDBにアクセスしてくるためreadの負荷が高そうにも感じますが、その点についてはMySQLのレプリケーションを利用しSlaveを多数用意するという通常の方法をとることで単純にスケールアウトできるため、それほど問題になることはありません。
また、断トツに高いページビューのhome.plですが、こちらに表示されている最新エコー5件のRead負荷についてはmemcachedから取得しているため、こちらも負荷対策が出来ています。

問題は、このRecent DBへのWriteの負荷です。
MySQLのレプリケーションは基本的にはWriteはMaster1台に行う必要があります。
そしてこのDBはすべてのユーザーの発言時にWriteされるDBです。
ここがスケールアウトしづらいポイントとなり、高負荷時にはボトルネックとなりやすいポイントになります。
特にお正月の「明けましておめでとうー！」書き込み時などは負荷が非常に高い状態になります。

■Q4Mでのピーク負荷平滑化

前述の問題は日記等でも同様ですが、投稿量で考えると圧倒的にエコーの方が高くなると予想されるため、エコーでは高負荷時でもRecent DBへのWriteがボトルネックとならないように、本エンジニアブログにも何度も登場しています弊社運用チームのkazeburoや、タンポポ開発チーム（という名前のチームが実際に存在するのです）のエンジニアと議論の結果、Q4Mを導入し高負荷に耐えられうる構成にしてみようということになりました。

Q4Mについては、MySQL5.1のプラガブルストレージエンジンの1つで、サイボウズ・ラボ株式会社の奥一穂氏が開発されています。

Q4M (Queue for MySQL) は MySQL 5.1 のプラガブル・ストレージ・エンジンとして動作するメッセージキューであり、堅牢・高速・柔軟であるよう設計されています。昨年12月遅くに開発が開始され、まだ非常に原始的ですが、かなり高速に動作します。

http://labs.cybozu.co.jp/blog/kazuho/archives/2008/01/q4m.php より抜粋

エコーではこのQ4Mをバッファリングする機構として導入することにより、Recent DBの能力を超えてしまうようなWrite負荷が発生した場合でも、一度Q4M上にキューイングされ、その後コンスタントにRecent DBへ伝播していくようにして、ピーク負荷を平滑化することができるような構成にしました。

■エコーシステム構成

結果、エコーのシステム構成図は下記のようになりました。

※実際のサーバー数は図のとおりではありません

キュー反映スクリプトからRecent DB （Master)への接続数は、今後、キューのたまり具合やRecent DBの負荷を見つつ、数を調整していきたいと思っています。

■まとめ

今回のエコーでは負荷対策として、日記のように各投稿に対して一意なidを発行する採番部分を排除し、member_idとpost_timeで一意キーとするなどして負荷の集中を避ける等の細かな工夫も随所にしていますが、Q4Mを導入してみたというところが新たな試みとして一番大きな点です。まだQ4Mが本領発揮するほどの負荷は発生していないのですが、引き続き高負荷時のQ4Mの働きに注目していきたいと思います。

Q4Mは非常に有用かつ興味深いストレージエンジンだと思いますので皆さん是非試されてみてはいかがと思います。

最後に、素晴らしいエンジンを 開発下さった奥一穂氏に改めてお礼申し上げます。

ここしばらく、水面下でBrian Akerを代表とするMySQL/SUNのエンジニアたちや、業界のオープンソースハッカーたちとMySQLをスリムダウンさせたマイクロカーネルRDBMSを開発していたのですが、本日アナウンスされたので、日本語でご紹介させていただきたいと思います。

Drizzleとは？

Drizzleとは必要のないものは一切存在しない、最低限でパフォーマンス重視な「MySQLよりシンプルで、軽く、安定して、高速な」 MySQLのforkです。マイクロカーネルアーキテクチャを採用したので、必要のないものは後付けできる構成です。こういった目標もあり、現在、Drizzleの開発チームはMySQLをドラスティックにリファクタリングしています。

コミュニティベースのプロジェクト

Drizzleで大事な事は、Drizzleはコミュニティベースのプロジェクトであるという事です。Montyのブログエントリーでも語られていますが、Drizzleでは、MySQLに長年存在していた致命的なバグが迅速に直されたり、プロダクトの進化を待たずとも、パッチやアイデアを誰でも貢献できます。したがって、Drizzleの開発はBazaarなどのオープンソースソフトウェアを使って行われており、LaunchpadやFreenodeなどの公開されている場所で行われています。

MySQLの替わりではない

一つ明確にしておかなければならないポイントは、DrizzleはMySQLの替わりになるプロダクトではありません。Drizzleのターゲットはとても限られた、RDBMSのカスタマイズを必要とする中～大規模なウェブアプリケーションです。

例えば、中～大規模で使われるMySQLは、memcachedと同様、セキュアな環境で運用されると仮定されます。したがって、安全であるという割り切りで、ユーザ名とパスワードをシンプルに, “hoge”と”hoge”に設定したとします。この場合、運用者としてはユーザ名とパスワードに意味はありませんが、MySQLの内部では、適当なクレデンシャルでも、ACL関連のロックが適用され、パフォーマンスを影響する要素となります。また、Query Cacheに関しても、個人レベルのデータベースでは効果的ですが、アプリケーションの規模が少し大きくなると意味を成さないコンポーネントとなります。

中～大規模なアプリケーションの開発者たちは、これらの機能をカスタマイズしたいと思ったり、実際に自社用にカスタマイズしています。こういうった人たちの仕事を楽にするためにDrizzleがあるのであって、一般的な場面で使うRDBMSとしては、MySQLが正しい選択だと思います。

マイクロカーネル アーキテクチャ

ウェブ業界で働く方で、最近のMySQLには使うことのない機能が多々あると感じる方は少なくないと思われます。Drizzleでは取り急ぎ、Stored Procedures, Triggers, Prepared Statements, Views, Query Cache, Event Scheduler, ACL, UNIX Socketをサーバから取り外しました。替わりに、私達はこれらのコンポーネントをプラガブルにするマイクロカーネルなアーキテクチャを目指します。

マイクロカーネルなら、Query Cacheをmemcachedのプールで代用してデータベースサーバたちに共通のキャッシュを共有させる事も可能になります。

オープンソースのライブラリを積極的に使う

MySQLは現状、歴史的経緯によって自社製のライブラリを使って実装されています（my_*系)。ですが、自分たちだけで開発するよりは、これらのライブラリをglib、libxml2、libpcreなどのオープンソースコミュニティによって開発・メンテナンスされているものに置き換える事によって、不都合やパフォーマンス改善を迅速、かつ高いクオリティを維持する事が可能です。したがって、私たちは実績のあるオープンソースのライブラリを積極的に使おうという結論に至りました。

ダウンロードしたい！

Drizzleは絶賛開発中で、リリースの日程も未定ですので、リンク経由でダウンロードできるパッケージはありません。ですが、先ほど説明したようにDrizzleは公開されたリポジトリを使って開発しているので、bzrの使い方を少し覚えたらソースを入手できます。以下がLaunchpadのプロジェクトページへのリンクです：

• https://launchpad.net/drizzle

ちなみにbzrでは、trunkからbranchを切るのは、”bzr branch 親” だけで出来ます。

まとめ

今回はMySQLの中の人たちや、ウェブ業界のエンジニアたちが望む、ウェブに優れたRDBMの開発プロジェクトをご紹介させて頂きました。Drizzleが完成すると、デベロッパーはApacheの様に様々なプラグインを書いて、ある程度、「自分仕様」なRDBMSを構築することが可能になります。

後はDrizzleのＦＡＱを読んで頂けたらな、と思います。

こんにちは、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);

といったクエリを発行しインクリメントしていき、最新のidはSELECTするのではなくUPDATE時のMySQL応答パケットに含まれるmysql_insertidを参照します。

上記のような内容をベンチマークテストのために同時接続を増やしながらテストしていると、350を超えたあたりで

ERROR 1213 (40001): Deadlock found when trying to get lock

というエラーが発生するという事態に遭遇しました（350という具体的な数値はハードウェアの性能などで変動すると思います）。ちなみに試験環境のOSやMySQLのバージョンは簡単ですが下記のような感じです。

• MySQL-5.0.45
• Linux-2.6.22

まずはWebで検索してみる

筆者の英語力不足という説もありますが、なかなか「コレ！」というものが見つけられませんでした。

パラメータやSQL文等を色々試してみる

• 1カラムしかないのが逆に良くないのかと思い、主キーカラムを追加しWhere句で指定　→　変化なし
• autocommitなのが良くないのかと思い、start transaction(またはbegin)とcommitを発行する　→　変化なし
• トランザクション分離レベルをserializableに変えてみる　→　変化なし
• innodb_table_locksパラメータを0にしてみる　→　変化なし

他にもいくつか試しました。また、それらを組み合わせてみたりもしましたが解決しません。なので、ソースを読んでみることにします。

静的デバッグ

MySQLのソースの取得・展開は済んでおり、ソース群のトップディレクトリにいるものとします。
エラー番号は1213と分かっているので、ヘッダファイルに対してgrepをかけてみます。

% find ./ -name \\*.h | xargs grep -rn 1213
./include/mysqld_error.h:217:#define ER_LOCK_DEADLOCK 1213
./include/mysqld_ername.h:216:{ "ER_LOCK_DEADLOCK", 1213 },

となるので、今度はER_LOCK_DEADLOCKを参照しているところを探してみます。

% global -r ER_LOCK_DEADLOCK
include/sql_state.h
libmysqld/handler.cc
libmysqld/lock.cc
sql/handler.cc
sql/lock.cc
sql/slave.cc

./sql/handler.cc か ./sql/lock.cc あたりが怪しそうです。そしてどちらを見てみても、

case HA_ERR_LOCK_DEADLOCK:
    textno=ER_LOCK_DEADLOCK;

となっているため、実際にはストレージエンジンレイヤーより HA_ERR_LOCK_DEADLOCK が返却された場合に前述のエラーが返却されるのであろうと予想がつきます（定数もファイル名もHA_(ha_)から始まるのは大体ストレージエンジンレイヤーです）。

というわけでinnodb関連のファイルで上記定数を使用しているところを探してみます。

% global -rx HA_ERR_LOCK_DEADLOCK
～略～
HA_ERR_LOCK_DEADLOCK  462 sql/ha_innodb.cc  return(HA_ERR_LOCK_DEADLOCK);
～略～

おそらくこのあたりであろうと思われます。というわけで実際に動かしながらのデバッグに移ります。

動的デバッグ

gdbやddd等を使って上記付近の場所にブレークポイントをはってみます。今回は458行目にはりました。

453     } else if (error == (int) DB_DEADLOCK) {
454         /* Since we rolled back the whole transaction, we must
455         tell it also to MySQL so that MySQL knows to empty the
456         cached binlog for this transaction */
457
458         if (thd) {
459             ha_rollback(thd);
460         }
461
462         return(HA_ERR_LOCK_DEADLOCK);

そして高負荷をかけてみて引っかかるのを待ちます。しばらく待ってみると…見事ひっかかりました！下記がその際のbacktraceです（引数の値やライブラリのパス等は伏せさせていただいてます）。

(gdb) bt
#0  convert_error_code_to_mysql at ha_innodb.cc:458
#1  0x0829656a in ha_innobase::index_read at ha_innodb.cc:3852
#2  0x08293143 in ha_innobase::index_first at ha_innodb.cc:4083
#3  0x08295ec8 in ha_innobase::rnd_next at ha_innodb.cc:4177
#4  0x08280bf3 in rr_sequential at records.cc:295
#5  0x0823ce9f in mysql_update at sql_update.cc:460
#6  0x081c61ac in mysql_execute_command at sql_parse.cc:3465
#7  0x081cb975 in mysql_parse at sql_parse.cc:6097
#8  0x081cdc2a in dispatch_command at sql_parse.cc:1812
#9  0x081cf08f in do_command at sql_parse.cc:1586
#10 0x081d0018 in handle_one_connection at sql_parse.cc:1197
#11 0x005e045b in start_thread ()
#12 0x004c223e in clone ()

正常時は#0のconvert_error_code_to_mysqlは通らないのですが、#1のha_innobase::index_read() は通るようなので、どうやらこの中でデッドロックか正常か分かれるようです。というわけで実行を一時中断して再度ソースコードに戻ります。ha_innobase::index_read() のリターン周辺をみてみると、

3836     ret = row_search_for_mysql((byte*) buf, mode, prebuilt, match_mode, 0);
3837
3838     innodb_srv_conc_exit_innodb(prebuilt->trx);
3839
3840     if (ret == DB_SUCCESS) {
3841         error = 0;
3842         table->status = 0;
3843
3844     } else if (ret == DB_RECORD_NOT_FOUND) {
3845         error = HA_ERR_KEY_NOT_FOUND;
3846         table->status = STATUS_NOT_FOUND;
3847
3848     } else if (ret == DB_END_OF_INDEX) {
3849         error = HA_ERR_KEY_NOT_FOUND;
3850         table->status = STATUS_NOT_FOUND;
3851     } else {
3852         error = convert_error_code_to_mysql((int) ret, user_thd);
3853         table->status = STATUS_NOT_FOUND;
3854     }

となっており、retの値、すなわち row_search_for_mysql()の戻り値により正常かデッドロックか分かれているようです。なので、row_search_for_mysql() を追ってみます。

% global -x row_search_for_mysql
row_search_for_mysql 3041 innobase/row/row0sel.c row_search_for_mysql(

内容は、

3040 ulint
3041 row_search_for_mysql(
3042 /*=================*/
3043                              /* out: DB_SUCCESS,
3044                              DB_RECORD_NOT_FOUND,
3045                              DB_END_OF_INDEX, DB_DEADLOCK,
3046                              DB_LOCK_TABLE_FULL, DB_CORRUPTION,
3047                              or DB_TOO_BIG_RECORD */
3048   byte*           buf,       /* in/out: buffer for the fetched
3049                              row in the MySQL format */
3050   ulint           mode,      /* in: search mode PAGE_CUR_L, ... */
3051   row_prebuilt_t* prebuilt,  /* in: prebuilt struct for the
3052                              table handle; this contains the info
3053                              of search_tuple, index; if search
3054                              tuple contains 0 fields then we
3055                              position the cursor at the start or
3056                              the end of the index, depending on
3057                              'mode' */
3058   ulint       match_mode,    /* in: 0 or ROW_SEL_EXACT or
3059                              ROW_SEL_EXACT_PREFIX */
3060   ulint       direction)     /* in: 0 or ROW_SEL_NEXT or
3061                              ROW_SEL_PREV; NOTE: if this is != 0,
3062                              then prebuilt must have a pcur
3063                              with stored position! In opening of a
3064                              cursor 'direction' should be 0. */
3065 {

というように DB_DEADLOCK を返却することがあるようなのですが、このファイル内にはDB_DEADLOCKという定数は現れません。なので、内部で何かの関数を呼び、そのreturnがDB_DEADLOCKで、それをそのままreturnしているのではないかと予想します。
なので、DB_DEADLOCKをreturnしてそうなところを探してみます。

% global -rx DB_DEADLOCK innobase/
DB_DEADLOCK  1850 innobase/lock/lock0lock.c return(DB_DEADLOCK);
DB_DEADLOCK  3557 innobase/lock/lock0lock.c return(DB_DEADLOCK);
DB_DEADLOCK   519 innobase/row/row0mysql.c  } else if (err == DB_DEADLOCK
DB_DEADLOCK  1420 innobase/srv/srv0srv.c    trx->error_state = DB_DEADLOCK;
DB_DEADLOCK  1514 innobase/srv/srv0srv.c    trx->error_state = DB_DEADLOCK;
DB_DEADLOCK   453 libmysqld/ha_innodb.cc    } else if (error == (int) DB_DEADLOCK) {
DB_DEADLOCK   453 sql/ha_innodb.cc          } else if (error == (int) DB_DEADLOCK) {

先頭2つが怪しそうです。見てみると、1850行目と3557行目を見てみると、両方とも lock_deadlock_occurs() の戻り値が真であればDB_DEADLOCKを返却するようです。なので lock_deadlock_occurs() の内部を更に追ってみます。

3190   ret = lock_deadlock_recursive(trx, trx, lock, &cost, 0);
3191
3192   if (ret == LOCK_VICTIM_IS_OTHER) {
3193     /* We chose some other trx as a victim: retry if there still
3194     is a deadlock */
3195
3196     goto retry;
3197   }
3198
3199   if (ret == LOCK_VICTIM_IS_START) {
3200     if (lock_get_type(lock) & LOCK_TABLE) {
3201       table = lock->un_member.tab_lock.table;
3202       index = NULL;
3203     } else {
3204       index = lock->index;
3205       table = index->table;
3206     }
3207
3208     lock_deadlock_found = TRUE;
3209
3210     fputs("*** WE ROLL BACK TRANSACTION (2)n",
3211       lock_latest_err_file);
3212
3213     return(TRUE);
3214   }

というわけで、lock_deadlock_recursive()のreturnがLOCK_VICTIM_IS_STARTの場合に真が返るようです。
少々疲れてきましたがさらに追います。以下が、lock_deadlock_recursive() の戻り値がLOCK_VICTIM_IS_START になる条件です。

3351                 if (too_far) {
3352
3353                     fputs("TOO DEEP OR LONG SEARCH"
3354                           " IN THE LOCK TABLE"
3355                           " WAITS-FOR GRAPHn", ef);
3356
3357                     return(LOCK_VICTIM_IS_START);
3358                 }
3359
3360                 if (ut_dulint_cmp(wait_lock->trx->undo_no,
3361                             start->undo_no) >= 0) {
3362                     /* Our recursion starting point
3363                     transaction is 'smaller', let us
3364                     choose 'start' as the victim and roll
3365                     back it */
3366
3367                     return(LOCK_VICTIM_IS_START);
3368                 }

いよいよ大詰めな感じです。ここで再度デバッガを使ってみましたところ、どうやらtoo_farフラグが立っているようで、3357行目のほうに引っかかります。too_farは、

3293             ibool   too_far
3294                 = depth > LOCK_MAX_DEPTH_IN_DEADLOCK_CHECK
3295                 || *cost > LOCK_MAX_N_STEPS_IN_DEADLOCK_CHECK;

のようです。depthは本関数の引数で与えられ、再帰呼び出しの直前にインクリメントされる値です。また、これら2つの定数は同ファイルにて下記のように定義されています。

46 /* Restricts the length of search we will do in the waits-for
47 graph of transactions */
48 #define LOCK_MAX_N_STEPS_IN_DEADLOCK_CHECK 1000000
49
50 /* Restricts the recursion depth of the search we will do in the waits-for
51 graph of transactions */
52 #define LOCK_MAX_DEPTH_IN_DEADLOCK_CHECK 200

too_farフラグが立った時、結局どちらの制限にひっかかっていたかというと、LOCK_MAX_DEPTH_IN_DEADLOCK_CHECK のほうでした。

ここまで分かってから再度Webを検索してみるといとも簡単に見つかりました。
http://bugs.mysql.com/bug.php?id=12588 （リンク先はMySQL AB社のサイトです）

どうやらbug fixとして5.0.13以降で追加された定数・ロジックのようです。
高負荷時にロックが増加した際、デッドロック検出のための再帰呼び出しの深さが深くなりすぎてスタックを消費していきデーモンごと落ちてしまう、という問題を解決するために追加したようです。

まとめ

と、ここまで分かると次に気になるのは、この値をもう少し増やしてみたらどうだろうか、というところです。

ですが、結論からいいますと、サーバーのハードのスペックにもよりますが、今回の検証用環境では多少の増加は出来ましたが、さらに負荷を上昇させていくとロック待ち時間が増加し、その結果innodb_lock_wait_timeoutに引っかかり始めました。じゃあinnodb_lock_wait_timeoutも増加させればいいじゃないか、と考えもしましたが、ただ実際にはそれによりパフォーマンスが向上するわけではなく、「90秒や120秒待てばデッドロック扱いもタイムアウト扱いもせずSQLが完了します」というのは、MySQL的にはエラーでなくとも実際のシステム的にはエラーも同然ですのであまり意味がないのではないかと判断しました。というわけで、現在mysqldを動作させる一般的なハードウェア上では200という数字はそれなりに適切な値なのではないかと思いました。

ちなみにMyISAMではこのような問題は起こらず、パフォーマンスも良好な結果でした。システムの要件にもよりますが、MyISAMに変更しても問題ない場合はそちらも検討されるのも良いかと思います。

デッドロックになるはずのないSQL文でデッドロックだとエラーメッセージが返却された場合にこのような例もあったなということを思い出していただけると幸いです。