algorithm - ログ ファイルで正確な行を見つける方法

Question

大きなログ ファイルがある場合、何十億行にもなります。ファイルには、IP アドレスのようないくつかの列があります: xxx.xxx.xxx.xxx.

を見つけたい場合のように、正確な1行をすばやく見つけるにはどうすればよいですか123.123.123.123。

素朴な行ごとの検索は遅すぎるようです。

Answer 1

他に必要な情報 (ファイルがソートされている場合の日付範囲など) がない場合は、行ごとの検索が最適なオプションです。これは、行単位で読む必要があるという意味ではありません。また、エントリが最近のものであることがわかっているため、逆方向に検索する方が効率的かもしれません。

一般的なアプローチ (後方検索の場合) は次のとおりです。

バッファを宣言します。一度にファイルのチャンクをできるだけ早くこのバッファに読み込みます (できれば、バッファリング/キャッシュなしで直接読み込むことができる低レベルのオペレーティング システム コールを使用します)。

したがって、ファイルの末尾からバッファーのサイズを引いた値までシークし、そのバイト数を読み取ります。

ここで、バッファを前方検索して最初の改行文字を探します。このオフセットは部分的な行を表すため、後で覚えておいてください。次の行から、文字列を探してバッファの最後まで前方検索します。特定の列にある必要があるが、他の列にその値が含まれる可能性がある場合は、解析を行う必要があります。

ここで、ファイルを逆方向​​に検索し続けます。最後に読み取った位置から、改行文字を検索したときに見つかったチャンク サイズとオフセットを差し引いた位置までシークします。さて、あなたはもう一度読んでください。必要に応じて、その部分的な行をバッファーの最後に移動して読み取るバイト数を減らすことができますが、チャンクが十分に大きい場合は大きな違いはありません。

そして、ファイルの先頭に到達するまで続行します。もちろん、読み取るバイト数がチャンク サイズよりも小さい場合 (つまり、最初の行を無視しない場合) は特殊なケースです。全体を検索したくないのは明らかなので、ファイルの先頭に到達しないと思います。

つまり、値がどこにあるのかわからない場合のアプローチです。順序付けについて何らかの考えがある場合は、もちろん、おそらく二分探索を実行したいと思うでしょう。その場合、より小さなチャンク サイズを使用できます (少なくとも行全体をキャッチするのに十分です)。

Answer 2

ファイルの規則性を検索してそれを利用する必要がありますが、それを除けば、プロセッサが多い場合は、ファイルをセクションに分割して並行して検索できます-I / Oがボトルネックにならないと仮定します。