再帰的なツリーハッシュ

再帰的なツリーハッシュ プラットフォームG 宮崎泰輔

今日の話

ディレクトリ同士の比較を高速にやりたい

ディレクトリ同士の比較の背景 物件データをDBから抽出して検索エンジンに入れるために データを変換している Feeder というバッチが存在する プログラムの変更により、生成されたデータに差分が無いことを 実データで確認したい

課題 - 生成される物件データは、数百GBある - 2つの結果を比較するために、同じサーバーにデータを生成すると 1TBを超える 別のサーバーで生成したら、比較のために数百GBを別サーバーに コピーしないといけない - ファイル数が数百万ファイルある - 1ファイル10msとしても、直列に比較すると、100万ファイルで 10000秒 => 2.7時間かかる - バッチの実行がそれなりに時間がかかる - バッチを直列に動かしたくない

課題に対するアイデア ディレクトリのハッシュを再帰的に計算して、 そのハッシュ情報だけをサーバー間でコピーして比較すればよい その前に考えていた案: git commitして、gitのtree objectのハッシュ値を比較する => gitはファイルをハッシュ化して .git/objects 以下に保存するので、 圧縮するとはいえかなりでかい => 必要な容量が倍になる

アイデアの詳細 ディレクトリのハッシュを計算したい ファイルだったら、ファイルのハッシュを計算する ディレクトリのエントリにディレクトリがあれば、再帰的に計算する ディレクトリのハッシュを計算する際はエントリの情報をファイル名でソートし、 並べたテキストのハッシュをディレクトリのハッシュとする

実際の構造

実際の構造

構造 Gitの構造を真似ている 同じ点 - ファイルのハッシュをobject-idとしてファイル名に使用している 違う点 - Gitはファイルをblobオブジェクトとして保存している - Gitはコミット情報をcommitオブジェクトとして保存している - Gitはファイルをzlibで圧縮している - Gitはsha1を使用しているが、mtlはmd5を使用している

作ったもの Markle Tree Likeということで mtl というものを作りました https://github.com/imishinist/mtl 今ある機能 - treeを作る(local build) - treeを表示する(print-tree)

• https://github.com/imishinist/mtl

作る上で苦労したこと - 依存関係があるので再帰的な処理が並列化しづらい - ハッシュの計算がとにかく遅い - perfをとってみたところ、80%くらいmd5:computeが使用してる - I/Oが多すぎる - すべてのファイルのハッシュを計算するため、全部読む - 並列化したら、作りが悪いのかめっちゃメモリ使う - 32GBのマシンがスワップしてる ハッシュ計算のために、ファイルを読むので、ファイルキャッシュも めっちゃ使う - ベンチマークしづらい - 大量のファイルを生成する必要がある & 容量けっこう食う (100GB)

作る上で苦労したこと 依存関係があるので再帰的な処理が並列化しづらい A B E F G C D H I Aのハッシュを計算するには、B,C,Dのハッシュが全て必要 Bのハッシュを計算するには、E,F,Gのハッシュが必要、、、 J

作る上で苦労したこと 普通に再帰でやれば実装はできる しかし、それでは直列にしか動かないので遅い 依存関係を解消するような順番に並び替えたらどうか？ EFGBHCIJDA A B E F G C D H I J

作る上で苦労したこと 並び替えたものをうまい具合に並列処理するアルゴリズムを 思いつけなかった 今は下の階層を取り出して並列にハッシュ計算して、次は上に という方法で並列化した 3. 1階層目 A B E F G C D H I 2. 2階層目 J 1. 3階層目

作る上で苦労したこと 今の作りだと、上位階層のどの計算の時にどのファイルを使うか わからないので HashMapに上位階層のパスをキーとして、ファイルのハッシュ情報を 詰めて、再帰的に上に向かって処理するようにしている。 なので、すべてのファイルパスをコピーしてHashMapに入れており、 メモリが爆発しているんじゃないか？と思っている

これからの予定 - 対象ファイルのフィルタがハードコードされているので、 オプションで変更したい - 今は、print-treeした結果同士をdiff取ることでしか差分が見れないので index同士を直接diffできるようにしたい - 1000万ファイルあっても動くようにしたい - ディレクトリの数は10万くらいを想定 - さらに高速化したい