TL;DR: XNUMX 年前、私は新しいサーバー監視ツールのアイデアを携えて Google を退職しました。 通常は分離されている機能を XNUMX つのサービスに結合するというアイデア 収集 ログ分析、メトリクス収集、 アラート そしてダッシュボード。 原則の XNUMX つは、サービスは真のサービスでなければならないということです。 速い、簡単でインタラクティブな楽しいエクスペリエンスを DevOps に提供します。 これには、予算内に収まりながら、数ギガバイトのデータ セットを数分の一で処理する必要があります。 既存のログ管理ツールは遅くて扱いにくいことが多いため、ユーザーに新しいエクスペリエンスを提供するツールを賢く設計するという、大きな課題に直面していました。

この記事では、Scalyr が昔ながらの方法、つまり強引なアプローチを適用し、不要なレイヤーを削除し、複雑なデータ構造を回避することで、この問題をどのように解決したかについて説明します。 これらの教訓を独自のエンジニアリング上の問題に適用できます。

オールドスクールパワー

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

重要な洞察は、最新のプロセッサは単純で単純な操作において実際に非常に高速であるということでした。 これは、I/O 速度とネットワーク操作に依存する複雑な多層システムでは見落とされがちですが、そのようなシステムは今日では非常に一般的です。 そこで私たちは、層や余分な破片を最小限に抑えるデザインを開発しました。 複数のプロセッサとサーバーを並列に使用すると、検索速度は 1 秒あたり XNUMX TB に達します。

この記事の重要なポイント:

• ブルート フォース サーチは、現実世界の大規模な問題を解決するための実行可能なアプローチです。
• ブルート フォースは設計手法であり、労力を必要としないソリューションではありません。 他の手法と同様に、一部の問題には他の手法よりも適しており、実装がうまくいかない場合もあれば、うまく実装される場合もあります。
• ブルートフォースは特に達成に適しています 安定した そうです。
• ブルート フォースを効果的に使用するには、コードを最適化し、適切なタイミングで十分なリソースを適用する必要があります。 これは、サーバーにユーザー以外の負荷が高く、ユーザーの操作が依然として優先されている場合に適しています。
• パフォーマンスは、内部ループのアルゴリズムだけではなく、システム全体の設計に依存します。

(この記事では、メモリ内のデータの検索について説明します。ほとんどの場合、ユーザーがログ検索を実行すると、Scalyr サーバーはそのログをすでにキャッシュしています。次の記事では、キャッシュされていないログの検索について説明します。同じ原則が適用されます: 効率的なコード、ブルート フォース大規模な計算リソースを使用します)。

ブルートフォース方式

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

私は Google でこのアプローチを使用しましたが、うまくいきました。 しかし、Scalyr ではログをバイトごとに検索します。

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

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

本当の困難は、言葉を探していないときに起こります。 ボットからのトラフィックの量を確認したいとします。 最初に考えられるのは、ログで「ボット」という単語を検索することです。 これにより、Googlebot、Bingbot などのボットを見つけることができます。 ただし、ここでの「ボット」は単語ではなく、その一部です。 インデックスで「ボット」を検索すると、「Googlebot」という単語を含む投稿は見つかりません。 索引内のすべての単語をチェックし、見つかったキーワードを索引内でスキャンすると、検索速度が大幅に低下します。 その結果、一部のログ プログラムでは部分語検索が許可されないか、または (せいぜい) パフォーマンスが低下する特殊な構文が許可されます。 これは避けたいと思っています。

もう一つの問題は句読点です。 すべてのリクエストを検索しますか? 50.168.29.7? 次のようなデバッグログはどうなるでしょうか? [error]? 通常、下付き文字は句読点をスキップします。

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

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

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

一方、各検索は大量の計算能力を消費する可能性があります。 ユーザーは独自のクエリの高速検索を高く評価していますが、そのようなクエリが実行されることは比較的まれです。 ダッシュボードなどの一般的な検索クエリでは、特別なテクニックを使用します (次の記事で説明します)。 他のリクエストは頻度が低いため、一度に複数のリクエストを処理する必要があることはほとんどありません。 しかし、これはサーバーが忙しくないという意味ではありません。サーバーは、新しいメッセージの受信、分析、圧縮、アラートの評価、古いデータの圧縮などの作業で忙しいのです。 したがって、クエリの実行に使用できるプロセッサがかなり大量に供給されています。

ブルートフォースは、ブルート問題（そして大量のフォース）がある場合に機能します。

ブルート フォースは、小さな内部ループによる単純な問題に最も効果的です。 多くの場合、内部ループを最適化して非常に高速に実行できます。 コードが複雑な場合、それを最適化することは非常に困難になります。

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

これは実際のコードの簡略化されたバージョンです。 ただし、ここでも、複数のオブジェクトの配置、データのコピー、関数呼び出しが表示されます。 JVM は関数呼び出しの最適化と一時的なオブジェクトの割り当てに非常に優れているため、このコードは期待以上にうまく機能しました。 テスト中、顧客はそれを非常にうまく使用しました。 しかし、最終的にはそれを次のレベルに引き上げました。

(なぜログを直接操作するのではなく、4K ページ、テキスト、メタデータを含むこの形式でメッセージを保存するのか疑問に思われるかもしれません。理由はたくさんありますが、要約すると、Scalyr エンジンは内部的には分散データベースに似ているという事実に帰着します。ファイル システム。テキスト検索は、ログ解析後のマージンで DBMS スタイルのフィルターと組み合わせられることがよくあります。一度に何千ものログを同時に検索できますが、単純なテキスト ファイルは、トランザクション、レプリケート、分散データ管理には適していません)。

当初、このようなコードは総当たり的な最適化にはあまり適していないと思われました。 「本当の仕事」 String.indexOf() CPU プロファイルを支配することさえありませんでした。 つまり、この方法だけを最適化しても大きな効果は得られません。

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

このバージョンはビュー上で直接動作します raw byte[] 4K ページ全体ですべてのメッセージを一度に検索します。

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

実際の検索アルゴリズムは以下に基づいています。 レオニード・ヴォルニツキーの素晴らしいアイデア。 これは Boyer-Moore アルゴリズムに似ており、各ステップで検索文字列の長さをほぼスキップします。 主な違いは、誤った一致を最小限に抑えるために一度に XNUMX バイトをチェックすることです。

私たちの実装では、検索ごとに 64K のルックアップ テーブルを作成する必要がありますが、検索するギガバイトのデータに比べれば大したことはありません。 内部ループは、単一コア上で 1,25 秒あたり数ギガバイトを処理します。 実際には、安定したパフォーマンスは各コアで XNUMX 秒あたり約 XNUMX GB ですが、改善の余地があります。 内部ループの外側のオーバーヘッドの一部を削除することは可能であり、Java ではなく C で内部ループを実験する予定です。

私たちは武力を行使します

ログ検索は「大まかに」実装できると説明しましたが、どの程度の「能力」があるのでしょうか? かなりたくさん。

1コア: 正しく使用すると、最新のプロセッサのシングル コアはそれ自体で非常に強力です。

8コア: 現在、それぞれ 1.4 コア (2.4 スレッド) を備えた Amazon hi8xlarge および i16xlarge SSD サーバーで実行しています。 前述したように、これらのコアは通常、バックグラウンド操作でビジー状態です。 ユーザーが検索を実行すると、バックグラウンド操作が一時停止され、8 つのコアすべてが検索のために解放されます。 通常、検索は一瞬で完了し、その後バックグラウンド作業が再開されます (スロットリング プログラムにより、大量の検索クエリが重要なバックグラウンド作業に干渉しないことが保証されます)。

16コア: 信頼性を確保するために、サーバーをマスター/スレーブ グループに編成します。 各マスターには 16 つの SSD と XNUMX つの EBS サーバーが配下にあります。 メイン サーバーがクラッシュすると、SSD サーバーがすぐに代わりを務めます。 ほとんどの場合、マスターとスレーブは正常に動作するため、各データ ブロックは XNUMX つの異なるサーバーで検索できます (EBS スレーブ サーバーのプロセッサは弱いため、考慮していません)。 タスクをそれらの間で分割するので、合計 XNUMX 個のコアが利用可能になります。

多くのコア: 近い将来、すべてのサーバーが重要なリクエストの処理にすべて参加するような方法で、サーバー間でデータを分散する予定です。 どのコアも動作します。 [注記： 私たちは計画を実行し、検索速度を 1 TB/s に向上させました。記事の最後にある注を参照してください。].

シンプルさが信頼性を保証します

ブルート フォース手法のもう XNUMX つの利点は、パフォーマンスがかなり安定していることです。 通常、検索は問題やデータセットの詳細にはあまり敏感ではありません (それが「粗い」と呼ばれる理由だと思います)。

キーワード インデックスは、信じられないほど高速に結果を生成する場合もあれば、そうでない場合もあります。 「customer_50」という用語がちょうど 5987235982 回出現する XNUMX GB のログがあるとします。 この用語の検索は、インデックスから直接 XNUMX つの場所をカウントし、即座に完了します。 ただし、複雑なワイルドカード検索では何千ものキーワードをスキャンする必要があり、長い時間がかかります。

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

ブルート フォース手法の単純さは、そのパフォーマンスが理論上の最大値に近いことを意味します。 予期しないディスクの過負荷、ロックの競合、ポインターの追跡、その他の何千もの失敗の理由に対する選択肢は少なくなります。 先週、最もビジーなサーバー上で Scalyr ユーザーによって行われたリクエストを調べてみました。 リクエストは14件ありました。 そのうちちょうど 000 件に 99 秒以上かかりました。 111% は XNUMX ミリ秒以内に完了しました (ログ分析ツールを使用したことがない場合は、信じてください: これは速い).

サービスを使いやすくするには、安定した信頼性の高いパフォーマンスが重要です。 定期的に遅延が発生すると、ユーザーは信頼性が低いと認識し、使用することに消極的になります。

ログ検索の実行中

以下は、Scalyr 検索の動作を示す短いアニメーションです。 私たちは、すべてのパブリック Github リポジトリにすべてのイベントをインポートするデモ アカウントを持っています。 このデモでは、600 週間分のデータ、つまり約 XNUMX MB の生ログを調べます。

このビデオは、特別な準備をすることなく、私のデスクトップ (サーバーから約 5000 キロメートル離れた場所) でライブ録画されました。 あなたが目にするパフォーマンスは主に次のようなものによるものです Webクライアントの最適化、高速で信頼性の高いバックエンドも備えています。 「読み込み中」インジケーターが表示されずに一時停止がある場合は、私がこれから押そうとしている内容を読み取ることができるように一時停止しています。

結論

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

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

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

編集： 過去数年間のパフォーマンスの向上を反映して、タイトルとテキストが「20 GB/秒での検索」から「1 TB/秒での検索」に変更されました。 この速度の向上は主に、増加する顧客ベースに対応するために現在設置している EC2 サーバーの種類と数の変更によるものです。 業務効率をさらに劇的に向上させる変更が間もなく行われる予定で、それを共有するのが待ちきれません。

出所： habr.com