大量のリクエストを捌くWebサイトを構築するには、さまざまなノウハウがあります。例えばオライリーの書籍『ハイパフォーマンスWebサイト』では、クライアントに配信するコンテンツを最適化することでパフォーマンスの向上を図っています。今回は、Pythonを使って月間10億を超える（！）リクエストを捌いている、株式会社クロスリスティングの方に、そのノウハウの一部を寄稿していただきました。
また、本記事の内容はPython Hack-a-thon 2010.07でのプレゼンテーションを元にしています
自己紹介
現在、私はクロスリスティングという会社で、広告配信システムとか、その周辺の新規商品関連の研究開発をやっています。メインのプログラミング言語はPythonです。自社でのシステム開発は基本的に全てPythonを使っています。自分は研究開発的なポジションですが、技術チームが開発しているプロダクションシステムもほぼ100% Pythonで開発されています。
「Pythonはバイトコードインタプリタのランタイムで動作するので、（JITを含めて）ネイティブコードにコンパイルする言語に比べて、実効速度の点で不利でありハイトラフィックなWebサービスの実装言語として向かないのではないか」という話を良く聞きます。今回は、Pythonで構築されているWeb広告配信サーバと、その周辺ツールについて、すこし紹介できればと思っています。
広告配信システムとログ処理
私がいま務めているクロスリスティングという会社は、検索連動型広告というネット広告の配信をしています。検索連動型広告は「リスティング広告」とも呼ばれていて、会社の名前はそこから取っています。
「検索連動型広告」という言葉を聞きなれない方もいるかと思いますが、例をあげるとGoogleのAdWords広告とか、Yahooスポンサードサーチが有名です。
Webを検索すると、検索結果の上の部分にいくつかの広告リンクが表示されます。あの部分がリスティング広告枠と呼ばれているもので、ユーザの入力したキーワードにマッチしたものを、広告配信システムが選択して表示しているわけです。
検索連動型広告は、多くの場合クリック課金です。つまり検索したユーザが広告をクリックすると、その広告ごとに設定された料金が広告主に課金されます。料金は、広告主が自分で設定しますが、同じ検索ワードに対して複数の広告主が存在した場合、設定された料金や、クリック率や、その他の検索結果との親和性とか、その他の色々な指標を用いて生成したスコア値を使って評価して、より高評価のものが選択され表示されます。
広告主は、広告効果を最大化したいので「どんな検索ワードに広告を出すと効果的か」「クリック単価はどの程度にすべきか」等を検討するために、入稿した広告ごとの詳細なレポートが必要です。また、広告スペースを提供しているメディア（ポータルサイト等）は、自社の検索サービスによって得られる収益がどのようになっているかを確認する必要があります。また、私のいる会社のような配信事業者は、「どのようなユーザに対して、どのような基準で広告を選択するのがもっとも良いか」といった問題に取り組むための分析用データが必要です。
これらのデータは全てログデータから生成されます。我々の会社はGoogleやYahooと比較して小さい会社ですが、検索連動型広告分野では国内で3番手にいて、それなりのリクエスト量があります。だいたい1ヶ月で10億超のリクエストが来て、どのメディアでどんな検索がされたか、どの広告がユーザに提示されたか、そのうちのどれがクリックされたか、クリックされた時の状況などが全て記録されます。このくらいの量になってくると、集計や分析のために、ログデータをRDBMSに入れてSQLベースで処理するのも、なかなか面倒なレベルになってくるので、ちょっとした工夫をしています。
鴨射ちにバズーカ砲はいらない
Google、Yahoo、mixi、Facebook等の超巨大サイトの場合、ユーザの行動履歴データは膨大な量になるでしょうが、我々のシステムでは、検索が1日あたり数千万件単位、表示される広告の数は検索のおよそ数倍、クリックは数十万件単位、識別しているユーザ数は、だいたい一千万弱という規模です。
このくらいの量のデータは、ちょっとした検索や集計を行いたい場合に、最近はやりのHadoopとかHiveといった分散系システムを持ち出して、ノードマシンに投資するには微妙なラインです。また日々増えていくデータをアーカイブしながら、それをそのまま利用したいという要望もあるので、RDBMSで全部やるというのも無理がありそうという、なんとも悩ましい規模感なわけです。
あまり大きな会社ではないので、サーバマシンへの投資は節約したいですし、「戦車にバズーカ砲で挑む」というような規模でもないので、小回りが効いて使い勝手のいい「鴨射ち散弾銃」をこしらえて問題を解決しています。
ログデータというのは、一度生成されると以後変化が無いという性質があります。お客さんへの請求や、メディアサイトへの収益分配の基本となるデータなので、変更があっては困ります。日常的に行うちょっとした分析や、状況の確認等に使っている「鴨射ち散弾銃」は、このログデータの静的な性質を利用して、コンパクトに仕立てています。逆に言うと、随時更新される動的な対象には全くもって向いていないということでもあります。
CDBを使う
CDBをご存知ですか？ CDBはConstant DataBaseの略語で、qmailや djbdnsで有名なDaniel J. Bernstein氏の開発した、Unix系OSでは昔からよく使われているDBM系と言われるデータベースです。Key - Valueの単純なマップを提供するDBで、基本的なコンセプトは最近流行のKVSと同じです。ただしサーバがいて、ネットワーク越しにアクセスするものではなく、プログラムにライブラリとして組み込んで、ローカルファイルをストレージとしてデータの入出力を行います。ちょうどクライアントサーバ型のRDBMSとSQLiteのような関係です。GDBMやBerkeley DBなどの実装が有名で良く使われており、TokyoCabinetなど日本発の高速＆高機能なシステムもあります。
そのような中でCDBを選択したのにはちゃんとした理由があります。
- CDBはその名のとおりConstantなDBです。
- CDBは作成フェーズと参照フェーズに分かれています。
- 作成が完了した後に、DB内に格納されているエントリの修正、追加、削除はできません。
- そのかわり作成、参照は超速いです。
- 生成されるストレージファイルが比較的コンパクトです。
- 1つのキーに対して複数の値を設定可能です。
という特徴が、静的なログ処理には向いています。作成フェーズと参照フェーズに分かれているという部分は実行例を見るのがよいでしょう。ここでは CDB-0.75、Python 2.6.5、 python-cdb-0.34（http://pilcrow.madison.wi.us/#pycdb）をつかっています。
# -*- coding: utf-8 -*-
import sys
import time
import random
import hashlib
import cdb
def printExecTime(target_function):
def caller(*args, **kw):
print("Start : %s" % target_function.__name__)
start_time = time.time()
result = target_function(*args, **kw)
print("End : %8.4f secs" % (time.time() - start_time))
return result
return caller
@printExecTime
def addRecords(cdb_builder):
for i in xrange(1000000):
cdb_builder.add(str(i),
hashlib.sha1("%s%s" % (time.time(),
random.random())).hexdigest())
@printExecTime
def finalize(cdb_builder):
cdb_builder.finish()
@printExecTime
def sequentialReadTest(cdb_reader):
for i in xrange(1000000):
value = cdb_reader.get(str(i))
@printExecTime
def randomReadTest(cdb_reader):
for i in xrange(1000000):
value = cdb_reader.get(str(random.randint(0, 1000000)))
@printExecTime
def iterationTest(cdb_reader):
key = cdb_reader.firstkey()
while key is not None:
value = cdb_reader.getall(key)
# do something...
key = cdb_reader.nextkey()
def main():
cdb_file_name = "/tmp/test.cdb"
tmp_file_name = "/tmp/test.cdb.tmp"
builder = cdb.cdbmake(cdb_file_name, tmp_file_name)
addRecords(builder)
finalize(builder)
del builder
reader = cdb.init(cdb_file_name)
sequentialReadTest(reader)
randomReadTest(reader)
iterationTest(reader)
if __name__ == "__main__":
main()
目の前にあるワークステーションとして使っているマシンでの実行結果はこのようになりました。
ransui@capella$ python cdbexample.py
Start : addRecords
End : 6.9454 secs
Start : finalize
End : 0.8811 secs
Start : sequentialReadTest
End : 0.7764 secs
Start : randomReadTest
End : 3.4778 secs
Start : iterationTest
End : 1.4590 secs
バックグラウンドで色々動かしているマシンなので、最高速は出ていませんが100万エントリの操作スピードとしてはまずまずでしょうか。ちなみにこの時のCDBファイルのサイズは67MBほどでした。
このソースコードを見て分かることは、CDBの生成と参照が完全に分離されているということです。データを追加したら最後にfinish()メソッドを呼びます。このメソッドが最終的なCDBファイルをディスク上に生成します。生成が完了したら、生成用オブジェクトはもはや不要です。なぜならCDBはいったん生成したデータの修正はできないためです。
上の例では値へのアクセスはcdb_reader.get(KEY)のようにメソッド呼び出しを使っていますが、cdb_reader[KEY]のように辞書風にアクセスすることもできます。イテレーションは最初のキーを取得してから、次々とキーを取り出していくスタイルになっています。Pythonのイテレーションプロトコルに対応するためには、__iter__とか__next__メソッドを定義したクラスでラップしてしまったり、yieldを使ってジェネレータにしてしまうのもいいでしょう。
CDBの特徴のうち、1つのキーに複数の値を割り当てられるという性質は、色々な目的に使える便利な機能です。数え上げと簡単な検索の例を見てみましょう。
例題:
あるログファイルがあって、以下のようなフィールドがTABで区切られている。
Column No. 内容 0 ユーザID 1 時刻情報 (hh:mm:ss 形式の文字列) 2 検索語 このファイルはログデータからあるプログラムによって毎日1ファイルずつアーカイブサーバ上に作成される。ディスク領域を節約するためにファイルはbzip2形式で圧縮されているこのような条件下で、ログを処理して以下のようなデータを得たい。
- ユーザIDのバリエーション数の正確な値
- ある特定のユーザIDを指定して、そのユーザが何回検索したか、また検索語は何であったか。
ファイルは全体で1200万行あり、ユーザIDのバリエーションは100万種類くらいと見積もられている。検索語の平均長は400bytesである。ファイルはbzip2圧縮された状態のまま取り扱いたい。ディスク容量を節約したいのでインデックスファイルは巨大化させたくない。
このような場合、ユーザIDをキーにしたKey-Valueマップを作ればOKということは分かります。単純にKeyをユーザIDとして、時刻情報と検索語をValueとしたCDBデータベースを構築してしまえば問題は解決できますが、これだと容量の大半を占める検索語をデータベースに取り込んでしまっています。
CDBはコンパクトなストレージファイルを生成するといっても、検索のためのオーバーヘッドがありますから、データそのものをCDBに入れてしまっては、ディスク容量を節約するためにデータファイル自体をbzip2圧縮している意味がなくなってしまいます。
問題のポイントは、ユーザIDが指定されたときに、実データを素早く参照できればOKという部分と、実データファイルは更新されないという点です。これを踏まえてちょっとしたプログラムを書いてみます。
# -*- coding: utf-8 -*-
import sys
import os.path
import bz2
import cdb
class BZ2Index(object):
def __init__(self, target_file_name=None, key_column=0):
self.target_file_name = target_bz2_file_name
self.index_file_name = "%s.cdb" % os.path.splitext(target_file_name, ".bz2")[0]
self.key_column = key_column
def buildIndex(self):
cdb_builder = cdb.cdbmake(self.index_file_name,
self.index_file_name + ".tmp")
pos = 0
archive_file = bz2.BZ2File(self.target_file_name, "r")
for line in archive_file:
key = line.strip().split("\t")[self.key_column]
cdb_builder.add(key, str(pos))
pos = target_file.tell()
cdb_builder.finish()
del cdb_builder
archive_file.close()
def openIndex(self):
self.cdb_reader = cdb.init(self.index_file_name)
self.archive_file = bz2.BZ2File(self.target_file_name, "r")
def getRecords(self, key):
result = list()
for position in (int(pos) for pos in self.cdb_reader.getall(key)):
self.archive_file.seek(position, 0)
result.append(self.archive_file.readline())
return result
このクラスはbzip2圧縮されたTSVファイルに索引をつけて、指定したキーに対応する実データを取得する機能を提供します。インデックスであるCDBには、キーに対応する値として、実データファイル先頭からのオフセット値を格納します。こうすることで、インデックスには整数(文字列化されていますが)のみが格納されるので、コンパクトに仕上がります。
データを読み出す場合は、インデックスをキーでひくと実データのオフセット位置のリストが返ってくるので、それぞれについてseekして1行読み出します。ISAMに似ていますが、実データの編成は固定長レコードではなく、行指向となっています。
CDBは1つのキーに対して、複数のaddがあると値の置き換えではなく追加として処理し、getallメソッドを使うことで複数の値をリストとして取り出すことができます。この性質をうまく使えばキーのユニーク化や、数え上げを手軽に処理できます。わざわざRDBMSやKVSなどのクライアントサーバシステムを準備しなくても、こんな単純な仕組みと少ない道具建てでそれなりにこなせるものです。もっともより本格的な分析とかになれば話は別です。戦車を相手にするときは迷わずバズーカ砲を使いましょう。