TL; DR：4年前、Googleに新しいサーバー監視ツールのアイデアを残しました。 アイデアは、ログの収集と分析、メトリックの収集、 アラート、およびダッシュボードの通常分離された機能を1つのサービスに結合することでした。 原則の1つ-サービスは非常に高速で、開発者に簡単でインタラクティブな楽しい仕事を提供する必要があります。 これには、予算を超えることなく、数ギガバイトのデータセットを瞬時に処理する必要があります。 ログを操作するための既存のツールは、多くの場合、遅くて不器用です。そのため、ユーザーに仕事から新しい感覚を与えるツールを正しく開発するという良いタスクに直面しました。



この記事では、Scalyrがオールドスクールな手法、ブルートフォースアプローチ、冗長レイヤーの排除、複雑なデータ構造の回避を適用してこの問題を解決した方法について説明します。 これらのレッスンを独自のエンジニアリングタスクに適用できます。

古い学校の強さ

通常、ログ分析は検索から始まります。特定のテンプレートに一致するすべてのメッセージを検索します。 Scalyrでは、これらは多くのサーバーからの数十または数百ギガバイトのログです。 原則として、最新のアプローチでは、検索用に最適化された複雑なデータ構造を構築する必要があります。 もちろん、私はこれをグーグルで見ました。彼らはそのようなことでかなり良いです。 しかし、私たちははるかに大まかなアプローチ、つまりログの線形スキャンに落ち着きました。 そしてそれはうまくいきました-私たちは、競合他社よりも桁違いに速い検索を備えたインターフェースを提供します（最後のアニメーションを参照）。



重要な洞察は、最新のプロセッサは単純で簡単な操作で非常に高速であることです。 これは、I / O速度とネットワーク操作に依存する複雑な多層システムでは簡単に見過ごされがちであり、そのようなシステムは今日非常に一般的です。 そのため、レイヤーの数と余分なゴミを最小限に抑える設計を開発しました。 複数のプロセッサとサーバーを並列に使用すると、検索速度は1 TB /秒に達します。



この記事の主な調査結果：

• ラフ検索は、実際の大規模な問題を解決するための実行可能なアプローチです。
  
  
• ブルートフォースは設計手法であり、仕事からの解放ではありません。 他の手法よりも、一部の問題の方が他の手法よりも優れており、実装が不十分または適切な場合があります。
  
  
• ブルートフォースは、 安定したパフォーマンスに特に適しています。
  
  
• ブルートフォースを効果的に使用するには、コードの最適化と十分なリソースのタイムリーな使用が必要です。 サーバーに負荷がかかり、ユーザーに関係なく、ユーザー操作が優先される場合に適しています。
  
  
• パフォーマンスは、内部ループアルゴリズムだけでなく、システム全体の設計に依存します。

（この記事では、メモリ内のデータを検索する方法について説明します。ほとんどの場合、ユーザーがログを検索すると、Scalyrサーバーは既にそれらをキャッシュします。リソース）。

ブルートフォース法

従来、大きなデータセットでの検索はキーワードインデックスを使用して行われていました。 サーバーログに適用される場合、これはログ内の各一意の単語を検索することを意味します。 単語ごとに、すべての包含のリストを作成する必要があります。 これにより、たとえば「error」、「firefox」、「transaction_16851951」など、この単語が含まれるすべてのメッセージを簡単に見つけることができます。インデックスを参照してください。



Googleでこのアプローチを使用し、うまく機能しました。 しかし、Scalyrでは、バイト単位でログを調べます。



なんで？ 抽象アルゴリズムの観点から見ると、キーワードインデックスは粗検索よりもはるかに効果的です。 ただし、アルゴリズムを販売するのではなく、パフォーマンスを販売します。 また、パフォーマンスはアルゴリズムだけでなく、システムエンジニアリングでもあります。 データの量、検索の種類、利用可能なハードウェア、ソフトウェアコンテキストなど、すべてを考慮する必要があります。 特定の問題では、インデックスよりも「grep」のようなオプションの方が優れていると判断しました。



インデックスは優れていますが、制限があります。 1つの単語を見つけるのは簡単です。 しかし、「googlebot」や「404」などのいくつかの単語を含むメッセージを見つけることは、すでにはるかに複雑です。 「キャッチされていない例外」などのフレーズを検索するには、その単語を含むすべてのメッセージを記録するだけでなく、単語の特定の場所も記録する、より面倒なインデックスが必要です。



本当に難しいのは、言葉を探していないときです。 ボットからのトラフィック量を確認するとします。 最初の考えは、「bot」という単語のログを検索することです。 そのため、Googlebot、Bingbot、その他多くのボットが見つかります。 しかし、ここでの「ボット」は言葉ではなく、その一部です。 インデックスで「bot」を検索した場合、「Googlebot」という単語を含むメッセージは見つかりません。 インデックス内のすべての単語をチェックし、見つかったキーワードのインデックスをスキャンすると、検索速度が大幅に低下します。 その結果、ログを操作するための一部のプログラムでは、単語の一部を検索できなかったり、（せいぜい）パフォーマンスが低下した特殊な構文を使用できません。 これを避けたいです。



別の問題は句読点です。 50.168.29.7



からのすべてのリクエストを見つけたいですか？ [error]



を含むログのデバッグはどうですか？ インデックスは通常、句読点をスキップします。



最後に、エンジニアは強力なツールが大好きで、問題は正規表現でしか解決できない場合があります。 キーワードインデックスはこれにはあまり適していません。



さらに、インデックスは複雑です。 各メッセージは、いくつかのキーワードリストに追加する必要があります。 これらのリストは、常に検索しやすい形式で保管する必要があります。 フレーズ、単語の断片、または正規表現を含むクエリは、複数のリストを含む操作に変換する必要があり、結果をスキャンして結合して結果セットを取得する必要があります。 大規模なマルチユーザーサービスのコンテキストでは、この複雑さにより、アルゴリズムの分析時に目に見えないパフォーマンスの問題が発生します。



キーワードインデックスも多くのスペースを占有し、ログ管理システムの主なコスト項目はストレージです。



一方、各検索には多くの処理能力を費やすことができます。 私たちのユーザーは、ユニークなクエリに対して高速検索を重視していますが、そのようなクエリは比較的まれです。 典型的な検索クエリ、たとえばダッシュボードでは、特別なテクニックを使用します（次の記事で説明します）。 他のクエリは非常にまれなので、一度に複数のクエリを処理する必要はほとんどありません。 ただし、これは、サーバーがビジーではないことを意味するものではありません。新しいメッセージの受信、分析、圧縮、アラートの評価、古いデータの圧縮などの作業でビジーです。 したがって、要求を処理するために使用できるプロセッサがかなり大量に提供されています。

ブルートフォースは、ブルートフォースの問題（および多くの力）がある場合に機能します

ブルートフォースは、小さな内部ループを持つ単純なタスクで最適に機能します。 多くの場合、非常に高速で動作するように内部ループを最適化できます。 コードが複雑な場合、最適化するのははるかに困難です。



最初、検索コードにはかなり大きな内部ループがありました。 メッセージを4Kページに保存します。 各ページには、いくつかのメッセージ（UTF-8）と各メッセージのメタデータが含まれています。 メタデータは、値の長さ、内部メッセージID、およびその他のフィールドがエンコードされる構造です。 検索ループは次のようになりました。







これは、実際のコードと比較して単純化されたオプションです。 しかし、ここでもいくつかのオブジェクトの配置、データコピー、関数呼び出しを見ることができます。 JVMは、関数呼び出しを非常に適切に最適化し、一時オブジェクトを割り当てます。したがって、このコードは、私たちが値するよりもうまく機能しました。 テスト中、クライアントは非常にうまく使用しました。 しかし、最終的に、私たちは新しいレベルに移動しました。



（ログを直接操作するのではなく、4Kページ、テキスト、メタデータを含むこの形式でメッセージを保存する理由を尋ねることができます。内部Scalyrエンジンが分散データベースに似ているのには多くの理由がありますファイルシステムテキスト検索は、多くの場合、ログ解析後のフィールドでDBMSスタイルフィルターと組み合わされます。数千のログを同時に検索できます。また、単純なテキストファイルは、 データ）。



当初、このようなコードはブルートフォース法による最適化にはあまり適していなかったようです。 String.indexOf()



の「実際のジョブ」は、CPUプロファイルを支配しませんでした。 つまり、この方法のみを最適化しても大きな効果はありません。



そのため、各ページの先頭にメタデータを保存し、UTF-8のすべてのメッセージのテキストはもう一方の端にパックされています。 これを利用して、ページ全体の検索ループを一度に書き直しました。







このバージョンは、 raw byte[]



ビューで直接動作し、4Kページ全体で一度にすべてのメッセージを検索します。



これは、ブルートフォース用に最適化する方がはるかに簡単です。 内部検索サイクルは、メッセージごとにではなく、4Kページ全体に対して同時に呼び出されます。 データのコピー、オブジェクトの選択はありません。 また、メタデータを使用したより複雑な操作は、メッセージごとではなく、肯定的な結果でのみ呼び出されます。 したがって、大量のオーバーヘッドを排除し、残りの負荷は小さな内部検索サイクルに集中します。これは、さらなる最適化に適しています。



実際の検索アルゴリズムは、Leonid Volnitskyの素晴らしいアイデアに基づいています。 これは、各ステップで検索文字列の長さをほぼスキップするというボイヤー・ムーアアルゴリズムに似ています。 主な違いは、一度に2バイトをチェックして、誤った一致を最小限に抑えることです。



実装では、検索ごとに64Kのルックアップテーブルを作成する必要がありますが、これは、探しているギガバイトのデータと比較するとナンセンスです。 内側のループは、単一のコアで毎秒数ギガバイトを処理します。 実際には、安定したパフォーマンスは各コアで約1.25 GB /秒であり、改善の可能性があります。 内側のループの外側のオーバーヘッドをいくらか取り除くことができます。Javaの代わりにCで内側のループを試す予定です。

力を加える

ログ検索は「大まかに」実装できると話しましたが、どれだけの「パワー」を持っているのでしょうか？ たくさん。



1コア ：正しく使用すると、最新のプロセッサの1つのコア自体が非常に強力になります。



8コア ：現在、Amazon hi1.4xlargeおよびi2.4xlarge SSDサーバーに取り組んでおり、それぞれに8コア（16スレッド）があります。 前述のように、通常、これらのカーネルはバックグラウンド操作で忙しいです。 ユーザーが検索を実行すると、バックグラウンド操作が一時停止され、8つのコアすべてが検索用に解放されます。 通常、検索は一瞬で完了し、その後バックグラウンド作業が再開されます（コントローラープログラムは、検索クエリの集中が重要なバックグラウンド作業を妨げないようにします）。



16コア ：信頼性のために、サーバーをマスター/スレーブグループに編成します。 各マスターには、1つのSSDサーバーと1つのEBS従属があります。 メインサーバーがクラッシュした場合、SSD上のサーバーがすぐにその場所を占めます。 ほとんどの場合、マスターとスレーブは正常に機能するため、各データブロックは2つの異なるサーバーで検索可能です（スレーブEBSサーバーのプロセッサは弱いため、考慮しません）。 合計16コアを使用できるように、タスクをそれらの間で分割します。



多くのコア ：近い将来、サーバー間でデータを配布し、サーバーがすべての重要な要求の処理に参加するようにします。 各コアが動作します。 [注： 計画を実装し、検索速度を1 TB / sに増やしました 。 記事の最後にある注を参照してください ]。

シンプルさが信頼性を提供

ブルートフォースのもう1つの利点は、比較的安定したパフォーマンスです。 原則として、検索はタスクとデータセットの詳細にあまり敏感ではありません（それが「失礼」と呼ばれる理由です）。



キーワードインデックスは、信じられないほど高速な結果を生成する場合がありますが、そうでない場合もあります。 「customer_5987235982」という用語が正確に3回出現する50 GBのログがあるとします。 この用語による検索では、インデックスから直接3つの場所がカウントされ、即座に終了します。 しかし、複雑なワイルドカード検索では、数千のキーワードをスキャンすることができ、多くの時間がかかります。



一方、クエリのブルートフォース検索は、ほぼ同じ速度で実行されます。 長い単語の検索は優れていますが、1文字の検索でも十分に高速です。



総当たり方式のシンプルさは、その生産性が理論上の最大値に近いことを意味します。 予期しないディスクの過負荷、ロックの競合、ポインターチェイス、およびその他の何千もの失敗の理由に対するオプションが少なくなっています。 先週、最も忙しいサーバーでScalyrユーザーが行ったリクエストを見ました。 14,000件のリクエストがありました。 そのうち8つは1秒以上かかりました。 99％が111ミリ秒以内に完了しました（ログ分析ツールを使用していない場合は、信じてください： これは高速です ）。



安定した信頼できるパフォーマンスは、サービスを使用する利便性にとって重要です。 定期的に速度が低下する場合、ユーザーは信頼性が低いと認識し、使用することに消極的です。

アクションのログ検索

以下に、Scalyrの検索の動作を示す小さなアニメーションを示します。 デモアカウントがあり、すべてのパブリックGithubリポジトリのすべてのイベントをインポートします。 このデモでは、1週間のデータ、約600 MBの生ログを調べます。



ビデオは、特別な準備なしで、デスクトップ（サーバーから約5000キロメートル）でライブ録画されました。 表示されるパフォーマンスは、主にWebクライアントの最適化と高速で信頼性の高いバックエンドによるものです。 「読み込み中」インジケータのない一時停止があるときはいつでも、クリックするものを読むために一時停止します。

結論として

大量のデータを処理する場合、適切なアルゴリズムを選択することが重要ですが、「良い」とは「派手な」という意味ではありません。 実際にコードがどのように機能するかを考えてください。 現実の世界で非常に重要になる可能性のあるいくつかの要因は、アルゴリズムの理論的分析から外れます。 単純なアルゴリズムは最適化が容易で、境界線の状況でより安定しています。



また、コードが実行されるコンテキストも考慮してください。 この場合、バックグラウンドタスクを管理するのに十分な強力なサーバーが必要です。 ユーザーが比較的まれに検索を開始することはないため、各検索を完了するために必要な短期間、サーバーのグループ全体を借りることができます。



ブルートフォースを使用して、一連のログに対して迅速で信頼性の高い柔軟な検索を実装しました。 これらのアイデアがあなたのプロジェクトに役立つことを願っています。



編集： 過去数年間のパフォーマンスの向上を反映して、タイトルとテキストが「毎秒20 GBで検索」から「毎秒1 TBで検索」に変更されました。 この速度の向上は、主に、増加した顧客ベースに対応するために今日上げているEC2サーバーのタイプと数の変更によるものです。 近い将来、仕事の効率がさらに急激に向上するような変化が予想されます。それについて話す機会を楽しみにしています。