メモリに全部は載らないファイル

一言でいうと

「すべて読み込んでリストに入れる」は、ファイルが小さいときにしか成り立たない設計であり、その前提が崩れたかどうかは、上限をかけてみて初めてわかります。

なぜ必要なのか

顧客が1か月分のイベントログを送ってきました。ノートPCではうまく動いていたスクリプトが、Podで落ちます。ログには何もなく、プロセスだけが消えています。

原因は、たいてい1行です。lines = open(path).read().splitlines()のように、ファイルをまるごとメモリに載せるコードです。この行は、小さなファイルではより短く、より速くさえあるので、最初に書くときには疑う理由がありません。そして、ファイルが大きくなるかどうかは、私たちではなく顧客が決めます。

もっと困るのは、この失敗が静かだという点です。コンテナがメモリの上限を超えると、カーネルがプロセスを殺します。Pythonの例外処理はその死を捕まえられず、標準出力には何も残りません。翌朝に見えるのは、「ジョブが終わっていない」ということだけです。

どう動くのか

設計の基準は1つです。どの時点でも、手に持っているものがいくつあるかです。

集計は1行で足ります。件数・合計・最小・最大は、いま読んだ1行さえあれば更新できます。ファイルが10倍になっても、メモリはそのままです。Pythonのファイルオブジェクトをそのまま繰り返せば、1行ずつ読まれます。readlines()やread()を呼んだ瞬間、その性質は失われます。

上位N個はN個で足ります。全体をソートして先頭を切ると、全体がメモリに載りますが、サイズNの最小ヒープを置いて、新しい値がヒープの一番下より大きいときだけ押し込めば、手に持つのは常にN個です。heapqのheappushpopが、この動作を一度に行います。

ユニークな値を数えるのは違います。1行ずつ読んでも、「すでに見た値」を覚えておく必要があるので、メモリが値の種類数に比例します。地域コード17個を数えるのと、セッションID50万個を数えるのは、同じストリーミングのコードでも、メモリがまったく違います。そのため、ユニークな値を数える設計で最初に尋ねるのは、ファイルサイズではなく種類数です。

ソートは分けて行います。外部ソートは昔からある方法です。入る分だけ読んでソートし、一時ファイルに書き(分割・ソート)、そのファイルたちから1行ずつ取り出しながらまとめます(マージ)。マージの段階で手に持つのは、ファイルごとに1行ずつだけです。Pythonでは、heapq.mergeがこのまとめ作業を行ってくれます。Unixのsortも同じことをします。POSIX sortは、一時ファイルを使うことを前提に規定されており、GNUの実装では、-Sでバッファーサイズを、-Tで一時ディレクトリを決めます。一時領域が足りなければ、ソートは失敗します。

現場での姿

1つ目に、「動かしてみたらできましたよ」を証明として使います。その言葉は、そのときそのファイルでできたという意味です。証明は、上限をかけて通ることです。Linuxには、プロセスが確保できるアドレス空間の上限があり、Pythonでは、resourceモジュールのsetrlimitでRLIMIT_ASを設定します。上限の下で、ストリーミング版は通り、まるごと読み込む版はMemoryErrorで落ちます。この2つの終了コードは、文章10行よりも優れています。

2つ目に、中間成果物を積み上げて検証します。「ソートがうまくいったか見るために」、原本と結果を両方読み込んでリストにして比べると、ストリーミングでソートした意味がなくなります。代わりに、順序に依存しないフィンガープリントを、流しながら計算します。行ごとにハッシュを出してすべて足せば(オーバーフローは捨てます)、順序が違っても同じ値が出て、行が1つでも欠けたり重なったりすると違う値になります。合計と件数も一緒に見れば十分です。

3つ目に、一時領域を忘れます。外部ソートは、メモリをディスクに移す取引です。Podの一時ディスクは6Giで、その場所も共有して使います。チャンクファイルを消さなければ、ソートの途中でディスクが先にいっぱいになります。

4つ目に、チャンクサイズを勘で決めます。チャンクが大きすぎるとメモリで落ち、小さすぎるとファイルハンドルが数百個になってマージが遅くなります。チャンクサイズは、「この程度なら確実に入る」を、上限の試験で確認して決めます。

実務で本当に大切なこと

手に持つものの個数で設計します。ファイルサイズではなく、同時に生きているオブジェクトの数が基準です。
上限をかけて証明します。合格と失敗が終了コードとして残れば、次の人は聞き直しません。
ユニークな値を数えるときは、種類数をまず尋ねます。ストリーミングという言葉は、メモリが一定という意味ではありません。
検証もストリーミングで行います。順序に依存しないフィンガープリントと件数と合計で十分です。

次のラボですること

30万行のイベントログを自分で作り、1行ずつ読んで集計するツールを作ります。ヒープで上位N件だけを保持し、ユニークな値を数えるときの最大メモリが、値の種類数によってどう変わるかを自分で測ります。そのあと、メモリの上限をかけて、ストリーミング版とまるごと読み込む版を並べて実行し、終了コードで違いを残し、外部ソートで大きなファイルをソートしたあと、順序に依存しないフィンガープリントで、1行も失っていないことを証明します。採点ツールは、自分が作ったファイルを上限の下で、作成したツールで実行して、答えを照合します。