Squidを検索する度に最初に表示される画像検索の結果に吹き出しそうになる開発部・システム運用グループの長野です。前回のロングテールな画像配信のその2ということで、実際の画像配信システムについて書かせて頂きます。

■プロフィール画像の配信について

前回紹介しましたが、mixiにおいてプロフィール写真を設定を設定しているユーザ数は全体の約70%、1,000万人の方が設定をされています。現在配信をしているプロフィール画像のサイズは180×180、76×76、40×40と３サイズあり、合計3,000万以上のファイル数になっています。また、もっともよく使われる76×76のサイズ1,000万件において、1日にアクセスされる画像の数は800万ファイル以上、うち97%が30回以下と非常に広範囲に渡ってアクセスされています。そのため大量の画像を配信できる仕組みが必要になります。

■配信システムの全体像

プロフィール画像の配信システムの全体像です。

画像の保存の部分から説明していきたいと思います。

■ストレージ層

edit_photoの画面や携帯メールからプロフィール画像をアップロードすると、アプリケーションサーバから変換（サイズの変更）と転送を行うサーバへ画像が渡されます。画像を変換するライブラリはメモリを多く使うことが多いのでWeb画面とは別のサーバで変換を行っています。
画像を変換を行った後、配信兼ストレージサーバにコピーされます。ストレージサーバはバックアップと負荷分散を目的に2台1組で構成されており、画像のアップロードは必ず2台へ行われます。
どのグループに保存されるのかは、画像のファイル名の番号の剰余によって決まります。もしストレージサーバに障害がおきて保存が出来なかった場合には、ファイル名を変更して別のサーバに保存をします。

実はこの変換の時には180×180のサイズしか作成していません。あとのサイズは配信時にオンザフライで生成しています。これでファイル数を一気に1/3まで減らす事ができます。ディスクIOのコストは画像の変換にかかるCPUのコストよりも高いと考えています。

■Reverse Proxy層

今度はもっとも外側のサーバです。プロフィール画像へのリクエストはまずこのサーバで受ける事になります。これはmod_proxy(mod_proxy_balancer)とmod_rewriteなどを組み込んだApacheです。

RewriteRule ^/photo/member/([0-9]+/[0-9]+/[0-9]+_[0-9]+)([sm]).jpg$　￥
     balancer://balancer/photo/member/$1$2.jpg [P,L]
RewriteRule ^/photo/member/([0-9]+/[0-9]+/[0-9]+_[0-9]+).jpg$ ￥
    balancer://director/photo/member/$1.jpg   [P,L]

76×76と40×40の画像はbalancerに、180×180の大きな画像はdirectorにそれぞれproxyされます。balancerは次に紹介するSquidサーバになり、directorはSquidサーバ群の下にあるサーバになります。180×180の画像についてはアクセスは比較的少ないのでSquidによるキャッシュ層を通さずに配信しています。

■Squid層

Squid層は2つのレイヤーに分かれます。Squidによるcacheサーバとそれを分散するbalancerレイヤーの２つです。

最初に紹介しましたが、プロフィール画像は非常に広範囲なURI、1,000万以上の画像にアクセスがあり、これらを高速に配信するためには画像データをメモリに載せる必要があります。Squidにキャッシュさせる画像のサイズのうちの１つ、76×76の容量の平均は約2.7KBになるので、必要なメモリは最低27GB以上のメモリが必要になります。1台のサーバ（最近のメモリの値段から言えば不可能ではないですが)ではメモリが足りないので、キャッシュデータを複数のサーバに分散していく必要があります。そこで利用したのがSquidに備わっているCARP(Cache Array Routing Protocol)という機能です。

*参考資料

carp.txt
http://icp.ircache.net/carp.txt

Cache Array Routing Protocol and Microsoft Proxy Server version 2.0
http://www.microsoft.com/technet/archive/proxy/prxcarp.mspx?mfr=true

CARPはmemcached界隈で話題になるConsistent-Hashingと考え方は似ていて、URIとcacheサーバのhash値を組み合わせてアクセスするサーバを決定します。サーバの追加や障害時の切り離しを行っても大幅なキャッシュの組み替えが発生しないという特徴もあります。詳しく知りたい方は上のURLやsquidディストリビューション中ののsrc/carp.cソースコードを参考にされるといいと思います。
SquidでCARPを利用する場合は、squid.confにおいて、cache_peerにcarpと指定します。Squidの制限としてキャッシュを横に並べるsiblingモードでCARPを利用する事ができないため、Squidが2段構成になります。

http_port 80 vhost vport
cache_peer 192.168.1.11 parent 80 0 no-query no-digest carp proxy-only weight=1
cache_peer 192.168.1.12 parent 80 0 no-query no-digest carp proxy-only weight=1
cache_peer 192.168.1.13 parent 80 0 no-query no-digest carp proxy-only weight=1
cache_peer 192.168.1.14 parent 80 0 no-query no-digest carp proxy-only weight=1

balancerとなるSquidサーバではcache等はせずproxyだけの機能で利用しています。上の設定では192.168.1.11〜14がcacheサーバとなりcarpアルゴリズムにてproxyしています。Apacheのmod_proxy_balancerでもbalaceの方式をモジュールで追加することができるので、こちらも研究しています。

CacheサーバとなるSquidでは、cache_dirとしてCOSSを利用しています。COSSは大きな単一ファイルにキャッシュデータを保存する形式で以前からSquidにあるufsやdiskdと比較して格段に性能が高く、効率のよいキャッシュを構築できます。

cache_dir coss /var/spool/squid/coss 8000 block-size=512 max-size=500000
cache_swap_log /var/spool/squid/%s 

http_port 80 vport
cache_peer 192.168.1.15 parent 80 0 no-query no-digest round-robin originserver
cache_peer 192.168.1.16 parent 80 0 no-query no-digest round-robin originserver

cacheサーバから再び、cache_peerでストレージサーバの上にあるdirectorサーバ(192.168.1.15と16)を指定しています。round-robinオプションを指定する事で負荷分散と冗長化も可能です。

■director層

最後の層になるdirectorですが、これは通常のApacheです。mod_proxy(mod_proxy_balaner)とmod_rewriteが組み込まれています。Reverse ProxyやSquidのcacheサーバからリクエストを受けて、そのURIから画像ファイル名の剰余を求め、正しいストレージサーバへproxyします。

この層を置かずに、reverse proxyやSquidのcache層から直接にストレージサーバへ接続を行う事もできますが、Squidやインターネットに接するサーバの設定を極力シンプルに保つためにこのような構成になっています。ストレージサーバの障害時にはこのdirectorサーバの設定を変更するだけなど影響を極小化するのにも役にたちます。

■まとめ

2回に分けてロングテールな画像配信という事で、mixiのプロフィール画像の配信について紹介してきました。画像の配信についてあまり気にされること多くはないと思いますが、裏側には様々な工夫があります。今回紹介してきた3,000万ファイル以上あり、広範囲にアクセスされるプロフィール画像の配信システムも、何度かの試行錯誤を経験した上でApacheやSquidなどのオープンソースソフトウェアを利用して高速でかつ、安定している仕組みを作り上げられています。
また機会があれば今回紹介しなかった画像配信についても紹介したい思います。

朝7時30分に起きて駒沢公園をジョギングすること10日目のmikioです。だいぶ体が軽くなってきて、そろそろ体型にも変化が出てくるかなと期待する毎日です。さて、以前の記事で予告した通り、Tokyo Dystopiaを使ったmixi内の検索機能をインディーズ機能としてリリースしました。「かんたん友人検索」という名のとおり、mixiの登録ユーザを対象として友人や知人を簡単に検索する機能です。操作を簡潔にしながらも、マイミクシィのつながりなどを使って検索精度を高めているのが特徴です。

シンプルにした

見た目として最も大きな特徴は、従来の友人検索よりも入力フィールドの数を減らしたことです。従来では「姓」「名」「ニックネーム」「性別」「年齢（下限）」「年齢（上限）」「血液型」「現住所（都道府県）」「現住所（市区町村）」「出身地（都道府県）」「出身地（市区町村）」「趣味」「職業」「キーワード」「写真」と15個もの入力フィールドを提示するものでした。これでは、どこに何を入力すれば適切に検索できるかよくわかりません。友人検索を最もよく使うのはmixiに登録したての人達なのですが、そういう初心者の人達にこんなにたくさんの選択肢を提供するのは、正直言って、あまり良い設計とは言えないと思います。

そこで、かんたん友人検索では、入力フィールドを思い切って一つにしてしまいました。これなら、キーワードを入れて「検索」ボタンを押すだけで、迷う余地が一切ありませんね。ここで検索すると、「姓」「名」「ニックネーム」の全てを対象とした検索が実行されます。

検索結果は従来と変わらず、該当するユーザのニックネームや写真や紹介文が表示されます。

名前検索を統合した理由

従来の検索で「姓」「名」「ニックネーム」を分けていた機構も、mixiのユーザ数がまだ10万人やそこらで、ほとんどのユーザが本名を開示していた時代には期待通りに機能していました。しかし、1500万人超のサイトに成長した現在では、本名の代わりに、「わかる人にだけわかる」ような文字列を名前として登録する人が増えてきました。友達に呼ばれるニックネームや好きな映画のキャラクター名などを使っている人もいます。その方が、「これで検索すれば自分にたどり着けるよ」と人に説明するためのキーワードとして有効だという判断もあるのかもしれません。

そうなると、例えば、姓:”ルパン”、名前:”三世”、ニックネーム:”lupin” という人を従来の検索機能で探す場合には困ったことになります。「そういえばあいつ “ルパン” って名前でmixiやってるって言ってたけど、姓と名とニックネームのどれに指定すればいいかわからん」といったことになります。探す側としては “ルパン” が姓なのか名なのかニックネームなのかはどうでもいいことなので、それらの区分ごとに何回も検索をしてイラっとさせられるよりも、一回の入力で一気に検索できた方が幸せですよね。検索項目を統合したおかげでヒット数が増加して適合率が下がってしまう心配はありますが、この問題に対しては後述するスコアリングの改善で対処しています。

検索オプション

従来の検索でも性別や年齢などの属性で検索結果を絞り込むことができていましたが、実際にそれが使われるケースは多くありませんでした。探したいユーザが必ずしもその性別や年齢などのプロフィールを公開しているとは限らないので、検索条件として指定するとかえってうまく探せないことが多いからでしょう。とはいえ、一般的過ぎる名前を使っているユーザの検索結果を絞り込むのには有用であることもないとは言いきれないので、機能としては残すことにしました。

「よく使う機能はデフォルトにして、あまり使わない機能はオプションにする」というユーザインターフェイスの定石を踏襲し、あまり使わない機能である属性絞り込みは「検索オプション」という別ページに分離することにしました。Googleなどでもこのような構成はお馴染みのことと思います。

検索オプションでは、「名前（姓・名・ニックネーム）」だけでなく、名前と自己紹介文を統合した全文検索もできるようにしています。また、「性別」「年齢」「現住所」「出身地」による絞り込みは従来の検索機能から引き継いで持たせています。「血液型」「趣味」「職業」はほとんど使われていないし、実際に有用だとも思わないので、廃止しました。

適合度順表示

従来の検索では、検索結果は、mixiへの登録日の新しい順（実際にはIDの降順）で並べられていました。これもmixiの規模が小さかった時代の名残りで、今や新規登録ユーザだというだけで日記を閲覧したりマイミクシィ申請をしたりする興味の対象になるわけではありません。

友人検索を使う動機は、自分の友人・知人を探して、日記を読んだりメッセージのやりとりをしたりマイミクシィ申請をしたりすることでしょう。あるいは、知らない人であっても、何か共通の話題を持った人に出会ってコミュニケーションを始めることでしょう。

となると、検索操作を行っている人となるべく共通点が多い人を優先的に表示するのが妥当だと考えられます。そこで、自分の住所や出身地が一致するユーザや年齢が近いユーザはポイントを上げるようなスコアシステムを導入しました（もちろん、全体公開されている属性のみを使っています）。また、ログイン時間が近くてコミュニケーションがとりやすい状態にあるユーザもスコアを上げるようにしました。

さらに、マイミクシィのつながりを解析して、自分からのホップ数（自分は0、直接のマイミクは1、マイミクのマイミクは2、マイミクのマイミクのマイミクは3、…）が低いユーザ、すなわち自分と友人ネットワーク的に近いユーザほどスコアが上がるようにもしました。これによって、たとえ「佐藤」「鈴木」「山田」といった一般的な名字で検索したとしても、知人が先頭もしくは1ページ目に表示されてすぐ見つけられる確率は格段に上昇したと思います。Googleにおけるページランクのようなアプローチをmixi上で実装した感じでしょうか。アルゴリズムの基本的な考えかたはマイミクシィレコメンドとほぼ同じですが、今回はオンデマンドで計算していることと3ホップ以上も対象に計算しているところが違います。

同級生を探してみよう

まず、かんたん友人検索の検索オプションページを開いてください。そこで、検索キーワードの欄の右側のリストボックスで「名前と自己紹介」を選択してください。そして、自分のキーワード入力欄に自分が通っていた中学校や高校などの名前を入れて、「検索する」ボタンを押してください（年齢などの条件は入れない方が探しやすいです）。以下のように二つの単語を「||」で区切る（前後に空白が必要）といわゆるOR検索をすることもできます。

所沢高校 || 所沢高等学校

そうすると、人によっては、いきなり1ページ目に同級生が出てくるかもしれません。何ページか見ればおそらく何人か出てくると思います。もし該当数が多すぎるようならば、自分の年齢の前後1年くらいを指定して絞り込んでみてもよいでしょう。同級生が見つかったらその人とマイミクになってみてもよいでしょう。そうすると、しばらくするとそのマイミクシィ関係が加味されて、さらに同級生が見つけやすくなります。

ギークな技術者の皆様の中には、同級生なんて興味ないという方もいると思います。そんなあなたは、業界用語を使って友人・知人を探してみましょう。例えば以下のような条件はどうでしょう（もちろん、表示される検索結果は人によって異なります）。

• perl || ruby || python || java || scheme || haskell
• unix || linux || bsd || debian || ubuntu || fedora || vine
• オープンソース || “open source” || フリーソフトウェア || “free software”
• wiiばんごう || wii番号

I ♥ インディーズ機能

かんたん友人検索はインディーズ機能としてリリースしました。特にバックエンド（検索エンジンやデータマイニングエンジンやストレージエンジンなど）の研究開発工程を含んだプロジェクトは開発者自身がイニシアティブをとって進めないと明後日の方向に進みがちなわけですが、インディーズ機能として開発できたおかげで今回はかなりうまく仕上がったと思っています。大人の事情によりトップケージからの誘導枠がとても地味になってしまったインディーズ機能ですが、逆境にめげず今後とも模索を続けていこうと思います。

まとめ

「かんたん友人検索」の特徴について説明しました。ユーザインターフェイスをシンプルにして、絞り込むことよりも並び替えをうまくすることで、目的のユーザを探しやすくしています。技術的には、レコメンドと検索の統合を試みたという意味で面白いものになっていると思います。

この機能、単純なようで、裏では結構な工夫を重ねて実現しています。分散処理によって検索や絞り込みを高速化するのはもちろん、検索結果のパーソナライズをオンデマンド（0.01秒程度のレイテンシ）で実現するための工夫も重要です。実装の詳細について書き始めるとものすごく長くなってしまいますので、それは次回の記事にとっておこうと思います。続きを読みたい方は、わっふ（ry

開発部・システム運用グループの長野です。最近は「サーバ／インフラを支える技術」を読みながら通勤しています。今回はmixiの画像配信について書かせて頂きたいと思います。1回目は画像配信の課題について説明させて頂きます。

■画像配信の種類

これまで画像の配信は大きく分けて2種類あると考え、システムを構築してきました。1つは１ファイルあたりへのアクセスが非常に多くなりますが、ファイル数が少ないもの。もう一つはファイル数が膨大になる代わりに、１つのファイルへのアクセスは少ないものになります。

前者はmixiの中で使われるロゴ画像やメニューの画像等のページ部品、また広告画像や絵文字画像になり、後者はユーザがアップロードする日記やアルバムの画像にあたります。ページの部品の画像はファイル数はそれほど多くないものの、サーバへのアクセス数が最大で秒間に数万リクエストにもなります。逆にアルバムや日記の画像は全体で数億以上のファイルがありますが、画像へのアクセスは該当する日記やアルバムを閲覧したユーザからのみになり、1つのファイルへのアクセスは少なくなります。

従来はこの2つの考え方で配信サーバを用意してきましたが、mixiへのアクセスが多くなるとこれらの配信方法だけでは対応ができない種類の画像がでてきました。それはユーザがアップロードをし、アクセスが多く、ファイル数も多いプロフィール画像やコミュニティのロゴ画像になります。

ここでは数が多くアクセスも多いプロフィール画像の配信について紹介します。

■プロフィール画像の配信

mixiのプロフィール画像は、プロフィールページで表示される180px x 180px、マイミク一覧やコミュニティのメンバー一覧で利用される76px x 76pxのサイズが従来から使われてきましたが、現在、エコーのリリースに合わせて新しく用意された40px x 40pxを加えて3種類の画像があります。このプロフィール画像を設定しているユーザ数は1,500万ユーザの約70%になり、約1,000万ユーザの方が設定されています。ここで単純にファイル数だけを計算すると1,000万人のユーザが大中小3つの画像を持つ事になるので、延べファイル数は3,000万にもなります。

このプロフィール画像へのうち76×76のサイズ(1000万ファイル)へのリクエストについて調査したところ、次回に紹介する配信システムのproxyサーバ4台のうち1台へのアクセスは1日で5,000万回以上記録されていました。この5,000万回のリクエストの中でアクセスされるユニークな画像は、800万ファイルあり、全体の70%以上のファイルへ1日でアクセスされていることが分かりました。

さらに詳しく画像毎のアクセス数を調査した結果が以下になります

このproxyサーバに対して、1日を通して1回のみアクセスされた画像は200万件になり、全体のリクエストに占める割合は4%、2回から10回アクセスされる画像は500万件でリクエスト数では2,000万以上になります。
合計のリクエスト数では、1件あたりのリクエスト回数が30回以下の画像でアクセス数の8割を占め、ファイル数の割合では97%にもなります。所謂、2割のオブジェクトの通信が8割を占めるというような、2:8の法則には全くなっておらず、偏りが少なく多くのファイルにリクエストが分散されることが分かります。縦軸にリクエスト数をとり、リクエスト数を多い順に画像をグラフ上においていくと以下の様になります。

非常に尾の長いロングテールなグラフになります。リクエストが30回以下、97%の画像が尾の部分になり、全体の80%以上のアクセスを占めています。

■まとめ

プロフィール画像の配信では非常に長いロングテールの尾の部分である、大量の画像を配信できるシステムが必要になります。実際のシステムについての解説は次回にさせていただきたいと思います。

こんにちは。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は非常に有用かつ興味深いストレージエンジンだと思いますので皆さん是非試されてみてはいかがと思います。

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