狠狠撸

狠狠撸Share a Scribd company logo

碍尝补产勉强会#6　発表资料

?
?
Suguru Oho
Suguru Oho

BZip2を途中から解凍できるようにした。 それで、並列に解凍とか データの条件抽出とかを色々工夫してみた KLab勉強会#6での発表内容 http://dsas.blog.klab.org/archives/cat_50030786.html

1 of 32
圧縮されたログファイルの活用ツール お前は今までに解凍したログファイルの数をおぼえているのか？！ Klab勉強会#6 KLab株式会社　開発部8グループ Engineering Manager 於保　俊 1
自己紹介 ● 於保　俊（おほ　すぐる）です ● Twitter：ohomagic ● 転職して1年半ちょっと経ちました ● 大学院で環境学→測量会社→KLab ● 専攻は自然科学（生態学?地学）と地理学?地理情 報システム ● PHP、Java　（その他も少し） ● 何かを作ることが大好きです ● KLabでは、ソーシャルゲームの開発?運用をしてき ました 2
今日のお話 ● KLabでは、Apacheのログをbzip2で圧縮して保存 しています ● 解凍コストが高いです ● 例えば、特定の時間帯のログだとか ● 例えば、特定のユーザーの検索だとか ● 問い合わせとかで、すぐに見たい場合があるけど、 一旦全解凍が必要（bzcatでも全解凍してる） ● ということで、なるべく解凍する量を少なく、色々で きるツールを作ってみました 3
この後の話との関連 ● ここでの話は、通常業務で発生するログの処理を、 いかに高速かつ軽量に行えるかという話です ● 他アプリとの連携も含めて、大規模に蓄積?分析す る話は、後ほどの高田の発表でどうぞ。 4
碍尝补产のログ収集の仕组み 5
ログファイルの実態 ● 某案件 ● １時間分づつ分割して圧縮している ● 平均ファイルサイズ　60MByte ● 最大ファイルサイズ　100MByte超 ● 解凍すると　およそ1.5GByte 6
きっかけ！？ ● bzip2の解凍は、時間かかるし、場合によっては ワークスペース食うし大変 →カジュアルにやらなきゃいけないけど、 規模によってはカジュアルにしにくい ● 欲しいのってログの一部 →「途中から解凍できないかな？」 7
叠窜颈辫2のファイル形式を见てみよう .magic:16 = 'BZ' signature/magic number .version:8 = 'h' for Bzip2 ('H'uffman coding), '0' for Bzip1 (deprecated) ● ヘッダ　BZhX .hundred_k_blocksize:8 = '1'..'9' block-size 100 kB-900 kB -------------------------------------------------------------------------------------------------------- ● ブロックのチャンク .compressed_magic:48 .crc:32 = 0x314159265359 (BCD (pi)) = checksum for this block .randomised:1 = 0=>normal, 1=>randomised (deprecated) ● ブロックの開始さえわ .origPtr:24 = starting pointer into BWT for after untransform かれば、ブロックごとに .huffman_used_map:16 .huffman_used_bitmaps:0..256 = bitmap, of ranges of 16 bytes, present/not present = bitmap, of symbols used, present/not present 独立で解凍できる (multiples of 16) .huffman_groups:3 = 2..6 number of different Huffman tables in use .selectors_used:15 = number of times that the Huffman tables are swapped (each 50 bytes) *.selector_list:1..6 = zero-terminated bit runs (0..62) of MTF'ed Huffman table (*selectors_used) .start_huffman_length:5 = 0..20 starting bit length for Huffman deltas *.delta_bit_length:1..40 = 0=>next symbol; 1=>alter length { 1=>decrement length; 0=>increment length } (*(symbols+2)*groups) .contents:2..∞ = Huffman encoded data stream until end of block .eos_magic:48 = 0x177245385090 (BCD sqrt(pi)) .crc:32 = checksum for whole stream .padding:0..7 = align to whole byte http://en.wikipedia.org/wiki/Bzip2 8
ヘッダの探索 {0x31, 0x41, 0x59, 0x26, 0x53}, {0x62, 0x82, 0xB2, 0x4C, 0xA6}, ● 3141592653を検索す {0xC5, 0x05, 0x64, 0x99, 0x4D}, ればいいんじゃない？ {0x8A, 0x0A, 0xC9, 0x32, 0x9A}, {0x14, 0x15, 0x92, 0x65, 0x35}, {0x28, 0x2B, 0x24, 0xCA, 0x6B}, ● ハフマン符号化されて {0x50, 0x56, 0x49, 0x94, 0xD6}, るから無理（バイトの開 {0xA0, 0xAC, 0x93, 0x29, 0xAC} 3 1 4 1 5 9 2 6 5 3 始位置が不定） 0000 0011000101000001010110010010011001010011 6 2 8 2 B 2 4 C A 6 0000 0110001010000010101100100100110010100110 C 5 0 5 6 4 9 9 4 D 0000 1100010100000101011001001001100101001101 8 A 0 A C 9 3 2 9 A ● それなら??? 0001 1000101000001010110010010011001010011010 1 4 1 5 9 2 6 5 3 5 0011 0001010000010101100100100110010100110101 ● ビットシフトされた8パ 2 8 2 B 2 4 C A 6 B 0110 0010100000101011001001001100101001101011 5 0 5 6 4 9 9 4 D 6 ターンのビットパターン 1100 0101000001010110010010011001010011010110 A 0 A C 9 3 2 9 A C を検索する 1000 1010000010101100100100110010100110101100 9
解凍ライブラリ ● Apache Commons Compress を使うことに 10
解冻ストリームの改造 Org.apache.commons.compres public BZip2CompressorInputStream(final InputStream in) throws ● IOException { s.compressors.bzip2.BZip2Com 　　　　　↓ public BZip2PartedCompressorInputStream(final InputStream in,int pressorInputStream　を使用 bsBuff,int bsLive,int blockSize100k, boolean serialMode) throws IOException { ● 前のブロックから引き endBlock(); 継ぐ情報をコンストラク initBlock(); SetupBlock(); タで与えられるようにす 　　　　　　↓ endBlock(); る if(serialMode){ initBlock(); ● ブロックの終わりで止 setupBlock(); } else { まるようにする complete(); } 11
前のブロックから引継ぐ情報？ ● ハフマン符号で、バッ ファに入っているビット 3 1 4 1 5 9 2 6 5 3 0000 0011000101000001010110010010011001010011 6 2 8 2 B 2 4 C A 6 列と何ビット目を読んで 0000 0110001010000010101100100100110010100110 C 5 0 5 6 4 9 9 4 D るかの0~7までの数字 0000 1100010100000101011001001001100101001101 8 A 0 A C 9 3 2 9 A 0001 1000101000001010110010010011001010011010 1 4 1 5 9 2 6 5 3 5 0011 0001010000010101100100100110010100110101 2 8 2 B 2 4 C A 6 B 0110 0010100000101011001001001100101001101011 5 0 5 6 4 9 9 4 D 6 1100 0101000001010110010010011001010011010110 A 0 A C 9 3 2 9 A C 1000 1010000010101100100100110010100110101100 12
豆知識 ● Bzip2recoverコマンドの紹介 ● Bzip2ファイルが壊れていた時に、正常な部分だけ むりやり解凍できるコマンドです ● ブロック単位で解凍されて、シリアルナンバーのつ いたファイル群が生成されます ● デバッグで使いました 13
とりあえず並列化してみた ● ファイルから単一スレッドで読み込む ● ブロック探索して、ブロックを見つけたら切り出し、 解凍キューに登録 ● 解凍スレッドが並列に解凍処理 ● 解凍したデータを書き出しキューにため ● 結合して書き出し ● 　ここまで6時間くらい　クイックハック！！ ● 　ついでに社内で表彰されました。ベストテクノロ ジー賞獲得！！ 14
結果 ● 全コア使いきって頑張ってる ● 速くなった　8192ms→3576ms 15
pbzip2の紹介 ● 並列bzip2 ● http://compression.ca/pbzip2/ ● 他にも並列実装はあるようです 16
さてここから本题 17
ログの調査で多いこと ● ある時間のログの抽出 ● あるユーザーのログの抽出 ● あるキーワードでのログの抽出 18
ある時間帯のログの抽出 ● 「二分検索でブロック探索」 ● ブロックを見つけたら先頭の２行だけ解凍 ● 解凍したログの１行分の時間を見て二分探索 ● 分割サイズがしきい値以下なら、そこから終了時 間まで解凍＆出力 ● 命名「BzBinSearch」 19
デモ 20
結果 $ time bzcat tsubasa.app.2011-12-01_22.bz2 | grep 22:30:00 > testlog2.log real 1m2.744s user 0m56.996s sys 0m2.124s $ time bzbinsearch 2011-12-01_22:30:00 2011-12-01_22:30:01 tsubasa.app.2011-12-01_22.bz2 > testlog1.log real 0m4.220s user 0m3.156s sys 0m0.924s 21
あるユーザーのログの抽出 ● あらかじめ、インデックスを作っておく ● ブロックのマップ ブロックのNo.　何バイト目から始まるか　解凍に必要な情報 ● あるユーザーIDがどのブロックに含まれるか 　　ユーザーID　ブロックNo.の羅列 ● 検索時はその情報を見て、必要最小限のブロック だけ解凍 ● 運用としては、ログ集約の際に同じバッチでイン デックスを作成する 22
デモ 23
結果 $time bzcat tsubasa.app.2012-04-01_23.bz2 | grep opensocial_viewer_id=38527024 real 1m13.775s user 1m13.621s sys 0m1.904s $time bzusersearch tsubasa.app.2012-04-01_23.bz2 38527024 real 0m6.166s user 0m13.829s sys 0m0.796s 24
あるキーワードの検索 ● 細かいブロック単位で解凍できることをいいことに なんちゃって分散処理してみた ● 手元のBZip2ファイル（ブロックインデックス作成済 み）をブロック単位で配信するWebサーバーを作成 Nettyを使った　　サーバーがブロックNo.を保持し、リクエスト ごとに違うブロックを送出 ● DSASのリモートシェル機能（mtnexec）を利用 ● 手元でブロックサーバーを起ち上げる→mtnexec でcurlでサーバーからブロック取得→パイプで bunzip→パイプでgrep→標準出力に書き出された ものをmtnexecで集約 25 ● 命名「mtnDP（MoTtaiNai Distributed Processing）」
図に表すと 26
デモ 27
結果 $ bzcat tsubasa.app.2011-12-01_12.bz2 | grep CardStack real 1m13.547s user 1m13.121s sys 0m1.640s $ time mtnexec -Ri -P 10 'for a in $(seq 1 200); do curl http://w112:56818/ | bunzip2 | grep CardStack; done' ::: $(seq 1 10) 1> testmtnexec.log 2> testmtnerror.log real 0m25.474s user 0m0.160s sys 0m1.284s 28
プログラムはこちら（予定） ● KLabのgithubアカウントで公開予定 ● https://github.com/KLab 29
まとめ ● こんなことできました！！ ● これでbzip2がもっと使いやすくなるはず 30
ご清聴ありがとうございました 31
质疑応答 32

More Related Content

碍尝补产勉强会#6　発表资料

  • 1. 圧縮されたログファイルの活用ツール お前は今までに解凍したログファイルの数をおぼえているのか？！ Klab勉強会#6 KLab株式会社　開発部8グループ Engineering Manager 於保　俊 1
  • 2. 自己紹介 ● 於保　俊（おほ　すぐる）です ● Twitter：ohomagic ● 転職して1年半ちょっと経ちました ● 大学院で環境学→測量会社→KLab ● 専攻は自然科学（生態学?地学）と地理学?地理情 報システム ● PHP、Java　（その他も少し） ● 何かを作ることが大好きです ● KLabでは、ソーシャルゲームの開発?運用をしてき ました 2
  • 3. 今日のお話 ● KLabでは、Apacheのログをbzip2で圧縮して保存 しています ● 解凍コストが高いです ● 例えば、特定の時間帯のログだとか ● 例えば、特定のユーザーの検索だとか ● 問い合わせとかで、すぐに見たい場合があるけど、 一旦全解凍が必要（bzcatでも全解凍してる） ● ということで、なるべく解凍する量を少なく、色々で きるツールを作ってみました 3
  • 4. この後の話との関連 ● ここでの話は、通常業務で発生するログの処理を、 いかに高速かつ軽量に行えるかという話です ● 他アプリとの連携も含めて、大規模に蓄積?分析す る話は、後ほどの高田の発表でどうぞ。 4
  • 6. ログファイルの実態 ● 某案件 ● １時間分づつ分割して圧縮している ● 平均ファイルサイズ　60MByte ● 最大ファイルサイズ　100MByte超 ● 解凍すると　およそ1.5GByte 6
  • 7. きっかけ！？ ● bzip2の解凍は、時間かかるし、場合によっては ワークスペース食うし大変 →カジュアルにやらなきゃいけないけど、 規模によってはカジュアルにしにくい ● 欲しいのってログの一部 →「途中から解凍できないかな？」 7
  • 8. 叠窜颈辫2のファイル形式を见てみよう .magic:16 = 'BZ' signature/magic number .version:8 = 'h' for Bzip2 ('H'uffman coding), '0' for Bzip1 (deprecated) ● ヘッダ　BZhX .hundred_k_blocksize:8 = '1'..'9' block-size 100 kB-900 kB -------------------------------------------------------------------------------------------------------- ● ブロックのチャンク .compressed_magic:48 .crc:32 = 0x314159265359 (BCD (pi)) = checksum for this block .randomised:1 = 0=>normal, 1=>randomised (deprecated) ● ブロックの開始さえわ .origPtr:24 = starting pointer into BWT for after untransform かれば、ブロックごとに .huffman_used_map:16 .huffman_used_bitmaps:0..256 = bitmap, of ranges of 16 bytes, present/not present = bitmap, of symbols used, present/not present 独立で解凍できる (multiples of 16) .huffman_groups:3 = 2..6 number of different Huffman tables in use .selectors_used:15 = number of times that the Huffman tables are swapped (each 50 bytes) *.selector_list:1..6 = zero-terminated bit runs (0..62) of MTF'ed Huffman table (*selectors_used) .start_huffman_length:5 = 0..20 starting bit length for Huffman deltas *.delta_bit_length:1..40 = 0=>next symbol; 1=>alter length { 1=>decrement length; 0=>increment length } (*(symbols+2)*groups) .contents:2..∞ = Huffman encoded data stream until end of block .eos_magic:48 = 0x177245385090 (BCD sqrt(pi)) .crc:32 = checksum for whole stream .padding:0..7 = align to whole byte http://en.wikipedia.org/wiki/Bzip2 8
  • 9. ヘッダの探索 {0x31, 0x41, 0x59, 0x26, 0x53}, {0x62, 0x82, 0xB2, 0x4C, 0xA6}, ● 3141592653を検索す {0xC5, 0x05, 0x64, 0x99, 0x4D}, ればいいんじゃない？ {0x8A, 0x0A, 0xC9, 0x32, 0x9A}, {0x14, 0x15, 0x92, 0x65, 0x35}, {0x28, 0x2B, 0x24, 0xCA, 0x6B}, ● ハフマン符号化されて {0x50, 0x56, 0x49, 0x94, 0xD6}, るから無理（バイトの開 {0xA0, 0xAC, 0x93, 0x29, 0xAC} 3 1 4 1 5 9 2 6 5 3 始位置が不定） 0000 0011000101000001010110010010011001010011 6 2 8 2 B 2 4 C A 6 0000 0110001010000010101100100100110010100110 C 5 0 5 6 4 9 9 4 D 0000 1100010100000101011001001001100101001101 8 A 0 A C 9 3 2 9 A ● それなら??? 0001 1000101000001010110010010011001010011010 1 4 1 5 9 2 6 5 3 5 0011 0001010000010101100100100110010100110101 ● ビットシフトされた8パ 2 8 2 B 2 4 C A 6 B 0110 0010100000101011001001001100101001101011 5 0 5 6 4 9 9 4 D 6 ターンのビットパターン 1100 0101000001010110010010011001010011010110 A 0 A C 9 3 2 9 A C を検索する 1000 1010000010101100100100110010100110101100 9
  • 10. 解凍ライブラリ ● Apache Commons Compress を使うことに 10
  • 11. 解冻ストリームの改造 Org.apache.commons.compres public BZip2CompressorInputStream(final InputStream in) throws ● IOException { s.compressors.bzip2.BZip2Com 　　　　　↓ public BZip2PartedCompressorInputStream(final InputStream in,int pressorInputStream　を使用 bsBuff,int bsLive,int blockSize100k, boolean serialMode) throws IOException { ● 前のブロックから引き endBlock(); 継ぐ情報をコンストラク initBlock(); SetupBlock(); タで与えられるようにす 　　　　　　↓ endBlock(); る if(serialMode){ initBlock(); ● ブロックの終わりで止 setupBlock(); } else { まるようにする complete(); } 11
  • 12. 前のブロックから引継ぐ情報？ ● ハフマン符号で、バッ ファに入っているビット 3 1 4 1 5 9 2 6 5 3 0000 0011000101000001010110010010011001010011 6 2 8 2 B 2 4 C A 6 列と何ビット目を読んで 0000 0110001010000010101100100100110010100110 C 5 0 5 6 4 9 9 4 D るかの0~7までの数字 0000 1100010100000101011001001001100101001101 8 A 0 A C 9 3 2 9 A 0001 1000101000001010110010010011001010011010 1 4 1 5 9 2 6 5 3 5 0011 0001010000010101100100100110010100110101 2 8 2 B 2 4 C A 6 B 0110 0010100000101011001001001100101001101011 5 0 5 6 4 9 9 4 D 6 1100 0101000001010110010010011001010011010110 A 0 A C 9 3 2 9 A C 1000 1010000010101100100100110010100110101100 12
  • 13. 豆知識 ● Bzip2recoverコマンドの紹介 ● Bzip2ファイルが壊れていた時に、正常な部分だけ むりやり解凍できるコマンドです ● ブロック単位で解凍されて、シリアルナンバーのつ いたファイル群が生成されます ● デバッグで使いました 13
  • 14. とりあえず並列化してみた ● ファイルから単一スレッドで読み込む ● ブロック探索して、ブロックを見つけたら切り出し、 解凍キューに登録 ● 解凍スレッドが並列に解凍処理 ● 解凍したデータを書き出しキューにため ● 結合して書き出し ● 　ここまで6時間くらい　クイックハック！！ ● 　ついでに社内で表彰されました。ベストテクノロ ジー賞獲得！！ 14
  • 15. 結果 ● 全コア使いきって頑張ってる ● 速くなった　8192ms→3576ms 15
  • 16. pbzip2の紹介 ● 並列bzip2 ● http://compression.ca/pbzip2/ ● 他にも並列実装はあるようです 16
  • 18. ログの調査で多いこと ● ある時間のログの抽出 ● あるユーザーのログの抽出 ● あるキーワードでのログの抽出 18
  • 19. ある時間帯のログの抽出 ● 「二分検索でブロック探索」 ● ブロックを見つけたら先頭の２行だけ解凍 ● 解凍したログの１行分の時間を見て二分探索 ● 分割サイズがしきい値以下なら、そこから終了時 間まで解凍＆出力 ● 命名「BzBinSearch」 19
  • 20. デモ 20
  • 21. 結果 $ time bzcat tsubasa.app.2011-12-01_22.bz2 | grep 22:30:00 > testlog2.log real 1m2.744s user 0m56.996s sys 0m2.124s $ time bzbinsearch 2011-12-01_22:30:00 2011-12-01_22:30:01 tsubasa.app.2011-12-01_22.bz2 > testlog1.log real 0m4.220s user 0m3.156s sys 0m0.924s 21
  • 22. あるユーザーのログの抽出 ● あらかじめ、インデックスを作っておく ● ブロックのマップ ブロックのNo.　何バイト目から始まるか　解凍に必要な情報 ● あるユーザーIDがどのブロックに含まれるか 　　ユーザーID　ブロックNo.の羅列 ● 検索時はその情報を見て、必要最小限のブロック だけ解凍 ● 運用としては、ログ集約の際に同じバッチでイン デックスを作成する 22
  • 23. デモ 23
  • 24. 結果 $time bzcat tsubasa.app.2012-04-01_23.bz2 | grep opensocial_viewer_id=38527024 real 1m13.775s user 1m13.621s sys 0m1.904s $time bzusersearch tsubasa.app.2012-04-01_23.bz2 38527024 real 0m6.166s user 0m13.829s sys 0m0.796s 24
  • 25. あるキーワードの検索 ● 細かいブロック単位で解凍できることをいいことに なんちゃって分散処理してみた ● 手元のBZip2ファイル（ブロックインデックス作成済 み）をブロック単位で配信するWebサーバーを作成 Nettyを使った　　サーバーがブロックNo.を保持し、リクエスト ごとに違うブロックを送出 ● DSASのリモートシェル機能（mtnexec）を利用 ● 手元でブロックサーバーを起ち上げる→mtnexec でcurlでサーバーからブロック取得→パイプで bunzip→パイプでgrep→標準出力に書き出された ものをmtnexecで集約 25 ● 命名「mtnDP（MoTtaiNai Distributed Processing）」
  • 27. デモ 27
  • 28. 結果 $ bzcat tsubasa.app.2011-12-01_12.bz2 | grep CardStack real 1m13.547s user 1m13.121s sys 0m1.640s $ time mtnexec -Ri -P 10 'for a in $(seq 1 200); do curl http://w112:56818/ | bunzip2 | grep CardStack; done' ::: $(seq 1 10) 1> testmtnexec.log 2> testmtnerror.log real 0m25.474s user 0m0.160s sys 0m1.284s 28
  • 29. プログラムはこちら（予定） ● KLabのgithubアカウントで公開予定 ● https://github.com/KLab 29
  • 30. まとめ ● こんなことできました！！ ● これでbzip2がもっと使いやすくなるはず 30