# μSlope: High Compression and Fast Search on Semi-Structured Logs > [!abstract] 概要(Abstract の日本語訳) > インターネット規模のサービスは大量のログを生成する。こうしたログは JSON のような半構造化フォーマットで出力されることが増えている。Uber では、半構造化ログデータの量は一日あたり 10PB を超えることがある。これらを保存・分析するコストは法外に高い。その結果、ログは数日間しか検索可能な状態に保たれていない。 > > 本論文は µSlope を提案する。µSlope は半構造化ログデータを可逆圧縮し、完全な解凍を行わずに検索できるシステムである。µSlope はスキーマ構造を簡潔に表現し、レコードごとに埋め込むのではなく、データセットごとに一度だけこの表現を保持する。さらに µSlope は、同じスキーマ構造を持つレコードを同じテーブルにグループ化することで半構造化データを「構造化」し、各テーブルを整った構造にする。評価の結果、µSlope は 21.9:1 から 186.8:1 の圧縮率を達成し、これは既存のあらゆる半構造化データ管理システム(SSDMS)よりも少なくとも数倍高い。圧縮率は Zstandard の 2.34 倍にも達し、検索速度は他の SSDMS の 5.77 倍である。 ## 論文情報 - タイトル: µSlope: High Compression and Fast Search on Semi-Structured Logs - 著者: [[Rui Wang (YScope)]]、[[Devin Gibson]]、[[Kirk Rodrigues]]、[[Yu Luo (University of Toronto)]]、[[Yun Zhang (Uber)]]、[[Kaibo Wang]]、[[Yupeng Fu]]、[[Ting Chen (Uber)]]、[[Ding Yuan]] - 所属: [[YScope]]、[[Uber]]、[[University of Toronto]] - 媒体: 18th USENIX Symposium on Operating Systems Design and Implementation(OSDI '24)、2024年7月10〜12日、Santa Clara, CA - コード: https://github.com/y-scope/clp ## 概要 µSlope は Uber の実運用ログ管理で生じた「半構造化ログのスキーマ多様性」という課題に対処する archival SSDMS(半構造化データ管理システム)である。スキーマ構造をレコードから切り離して一度だけ保持する Merged Parse Tree(MPT)と Schema Map、スキーマ単位でレコードをグループ化するカラム指向の Encoded Record Table(ERT)、そしてスキーマメタデータを活用してクエリを早期に絞り込む検索アルゴリズムの3つの新規設計により、既存 SSDMS を上回る圧縮率と検索速度を両立する。 ## 問題設定 - 入力: JSON など木構造を持つ半構造化ログレコードの集合。レコードごとにスキーマ(キー名と値の型の組)が異なりうる。 - 出力: 可逆圧縮されたアーカイブと、それに対する完全解凍なしの検索(KQL クエリ)。 - 前提: Uber では半構造化ログが一日あたり 10PB(週 60PB)を超える規模で生成される。これは SSDMS の主要評価対象であった Twitter データ(一日 140GB 相当)の 70,000 倍以上の規模である。既存の RDBMS 拡張や SSDMS は、レコードごとにスキーマ構造を保持するため、レコード数に比例してスキーマメタデータが肥大化し、これが圧縮率のボトルネックになる。 ### Uber の半構造化ログのキャラクタリゼーション調査(§3) 著者らは Uber から収集した 16 データセットと公開ソフトウェア 5 種、計 21 データセット(1データセットあたり最大 100 万レコード)、および Uber の実クエリログ(20 日間・23,091 件、うち 7,665 件がユニーク)を分析し、µSlope の設計判断の根拠とした。 - **スキーマとキーの多様性**: 全データセットでユニークスキーマ数の中央値は 40、ユニークキー数の中央値は 138。最も多様な LogE でも 6,176 種類のスキーマにとどまる一方、平均するとデータセットあたり 25,000 レコードが同じスキーマを共有しており、大きな反復性が存在する。21 データセット中 18 個でユニークキー数がスキーマ数を上回っており、スキーマの多様性はキーの組み合わせ爆発ではなく個々のキーの多様性に起因することが示される(Figure 4)。 **Figure 4: 各データセットのユニークスキーマ数とキー数** ![[_attachments/osdi24-wang-rui/fig04-schema-key-counts.png]] (Figure 4. LogA〜LogP と公開データセット(Spark・MongoDB・CockroachDB・Elasticsearch・PostgreSQL)について、ユニークスキーマ数(青)とユニークキー数(赤)を対数軸で比較。多くのデータセットでキー数がスキーマ数を上回る。) key frequency(KF、あるキーを含むレコード数 ÷ 全レコード数)の分布を LogE で見ると、KF=1.0(全レコードに出現)のキーが 21 個ある一方、83.0% のキーは KF<0.1 のロングテールを成す。前者はロギングライブラリが一律に付与する `timestamp`・`level` のようなキー、後者はプログラムの内部状態を記述する多様なデータ構造や、UUID・パス名をキー名に使うケースに対応する(Figure 5)。 **Figure 5: LogE における KF 分布** ![[_attachments/osdi24-wang-rui/fig05-kf-distribution.png]] (Figure 5. LogE の 704 個のキーを KF(key frequency)の降順に並べたグラフ(対数軸)。一部のキーは KF=1.0 で全レコードに出現し、大多数は KF が急減するロングテールを成す。) - **値の型構成と反復性**: 値の型別内訳では、平均で 70.8% が単語文字列(variable)、10.8% がオブジェクト(ネストしたキーへの非葉ノード)、真偽値・浮動小数点・null はそれぞれ 1.74%・1.21%・0.22% と少ない。配列は 0.79% とさらに少なく、ユニーククエリの 0.4% しか配列フィールドを明示的に検索していない。1 レコードあたり平均 1.6 個のログテキストキー、4.0 個の整数フィールドを持つ。単語文字列(variable)の反復率(全変数値数 ÷ ユニーク変数値数)は中央値 37.8、平均 58.2 で、最大 433.4(LogD)、最小でも 9.29(LogC)に達し、辞書による重複排除が効果的であることを示す(Figure 6)。クエリの平均は 3.450 個のフィルタを含み、うち 2.663 個が変数フィルタである。また、ユニーククエリの 29% はどのスキーマ構造にもマッチせず値のスキャンなしに返せる。 **Figure 6: 1レコードあたりの平均キー数(値の型別内訳)と変数の反復率** ![[_attachments/osdi24-wang-rui/fig06-value-type-breakdown.png]] (Figure 6. 各データセットについて、1レコードあたりの平均キー数を int・float・variable・log-text・bool・null・array・object の8種類に色分けして積み上げた棒グラフ(左軸)と、変数値の反復率(右軸、対数軸)。variable(単語文字列)が大部分を占め、反復率はほぼ全データセットで 10〜100 の範囲にある。) ## 提案手法 - **アーキテクチャ**: 取り込み時に各レコードをパースしてスキーマを抽出し、Merged Parse Tree(MPT)と Schema Map という2つのデータ構造でスキーマメタデータを追跡する。値は型ごとに符号化され、辞書 + Encoded Record Table(ERT)に格納される。バッファが一定サイズに達すると Zstandard で圧縮してアーカイブとして永続化する(Figure 7)。 **Figure 7: µSlope のアーキテクチャ** ![[_attachments/osdi24-wang-rui/fig07-architecture.png]] (Figure 7. 半構造化ログは Parsing & Encoding を経て Merged Parse Tree と Schema Map に変換される。値は Variable Dictionary・Log Type Dictionaries・Timestamp Dictionary に格納され、スキーマごとの Encoded Record Table にまとめられて Archive として圧縮される。検索時は Archive に対して直接 Search が行われる。) - **Merged Parse Tree(MPT)とスキーマ表現**: MPT は §2.1 で定義される merged schema tree(MST)を一般化したもので、以下の4点が異なる。(1) キー名がランダム(UUID・ファイルパスなど)で非反復的な場合、複数の稀なキーを匿名の unnamed node にまとめてメタデータの肥大化を防ぐ。(2) 逆に値が高い反復性を持つ場合(例: application-name キーの値が常に同じ)、その値自体を MPT ノードに含めることができる。(3) キー・バリュー構造を持つ文字列(ログテキスト内の `latency=35, status=OK` のようなパターン)の構造を捉え、子ノードとして表現できる。(4) タイムスタンプ・単語文字列(variable)・ログテキストという、文字列型をより細かく区別して保持する。Figure 1・2 は例示レコードとそのマージ後のスキーマ木を示す。 **Figure 1: 2つの例示ログレコードとそのスキーマ木** ![[_attachments/osdi24-wang-rui/fig01-schema-trees.png]] (Figure 1. 2つの JSON ログレコード(共に `level`・`message`・`timestamp` などを持つが `serviceA`/`serviceB` や `request` の型が異なる)と、それぞれに対応するスキーマ木。ノードはキー名と値の型(`str`・`obj` など)の組で構成される。) **Figure 2: 2レコードのマージ済みスキーマ木** ![[_attachments/osdi24-wang-rui/fig02-merged-schema-tree.png]] (Figure 2. Figure 1 の2つのスキーマ木をノード ID 0〜11 で統合した merged schema tree(MST)。同一のキー名・値型を持つノード(`level:str` など)は1つに統合され、`request:str`(ノード11)のように片方にしか存在しないキーはそのまま残る。) 比較として、既存 SSDMS の MongoDB は BSON(Binary JSON)という簡潔なバイナリ形式でスキーマ構造をレコードに埋め込んで保持する(Figure 3)。これはレコード指向の格納しかできず、圧縮率・検索速度の両方でボトルネックになる。 **Figure 3: `{“hello”: “world”}` の BSON 表現** ![[_attachments/osdi24-wang-rui/fig03-bson-representation.png]] (Figure 3. BSON はサイズ・値型・キー名・値そのものをバイナリ列としてレコードに直接埋め込む。µSlope の MPT/Schema Map のようにスキーマ情報を切り離して一度だけ保持する設計ではない。) - **Schema Map と Encoded Record Table(ERT)**: Schema Map は各一意なスキーマを、MPT の葉ノード ID のリストとしてハッシュマップに保持する。これによりスキーマ構造はデータセット全体で一度だけ保持され、実測でスキーマメタデータのサイズは圧縮後データ全体の 0.0001% 未満になる。µSlope はスキーマごとに1つの ERT を用意し、そのスキーマを持つレコードだけを格納する。各テーブルはすべてのレコードが同じキー・同じ型を持つため完全に構造化されており、カラム指向で圧縮できる。値は型ごとに異なる符号化を受ける: タイムスタンプはタイムスタンプ辞書 ID と Unix エポック時刻の2列、単語文字列(variable)は変数辞書 ID、ログテキストはログタイプ辞書 ID + 変数列のリスト、整数・浮動小数点数・真偽値はバイナリでそのまま符号化される(Figure 8)。 **Figure 8: µSlope によるログレコードの符号化** ![[_attachments/osdi24-wang-rui/fig08-encoding-example.png]] (Figure 8. Figure 1 の2レコードに対する辞書と Encoded Record Table の内容。Log Type Dictionary の `L0` はログテキストのテンプレート、Timestamp Dictionary の `T0` はタイムスタンプの書式、Variable Dictionary の `V0`〜`V6` は単語文字列の実値を保持する。Schema 0 / Schema 1 の Encoded Record Table は、MPT ノード ID を列として値を格納する。) - **クエリ処理アルゴリズム**: µSlope は KQL(Kibana Query Language)をクエリ言語として採用する。クエリはまず抽象構文木(AST)に変換され、(1) キー解決(ワイルドカードキー・多相型の解決、OR 展開)、(2) スキーマ解決(AND の子ノードすべてを含むスキーマが存在するかを MPT ノード ID の積集合で判定し、存在しなければ false propagation でその部分木を除去)、(3) 文字列辞書上の検索(ログタイプ・変数・タイムスタンプの各辞書に対して検索し、ヒットしなければ早期終了)、(4) 残った AST が指す ERT のカラムだけを解凍・スキャンする、という段階的な絞り込みを経る(Figure 9)。アーカイブ単位のタイムスタンプ範囲インデックスも併用し、クエリの時間範囲と重ならないアーカイブはスキップする。 **Figure 9: クエリ処理の例** ![[_attachments/osdi24-wang-rui/fig09-query-processing.png]] (Figure 9. クエリ `*.traceID: abc-xyz AND error: *404` が Initial AST → キー解決後 → スキーマ解決後 と段階的に変換される様子。スキーマ解決の段階で、ノード5と10が同一スキーマに存在しないため `AND<empty>` の部分木が false propagation により除去(赤い鋏の図示)される。) - **実装上の工夫**: JSON パースには simdjson を使用し、CLP のログパーサを拡張してログテキストからキー・バリューペアを抽出する。スキーマごとに専用のバイトコードを生成するカスタム JSON シリアライザを実装しており、動的オブジェクトの走査を伴う一般的な JSON シリアライザより数倍高速だとされる。ERT は単一ファイルに連結して格納し、メタデータファイルで各 ERT の位置とレコード数を管理することで I/O オーバーヘッドを削減する。レコードの元の順序は、各 ERT に順序を保持する専用カラムを追加することで維持する(タイムスタンプは重複しうるため順序保存には使えない)。C++ で約 18k 行の実装。 ## 新規性 既存 SSDMS(MongoDB の BSON、PostgreSQL の jsonb、Oracle の OSON、Steed の merged schema tree、Scuba の行指向圧縮、Sinew・JSON Tiles のハイブリッド RDBMS 拡張)はいずれもレコードごとにスキーマ構造を保持するため、レコード数に比例してスキーマメタデータが増大し、それが圧縮率のボトルネックになる(§2.2)。µSlope はスキーマ構造をレコードの値から完全に切り離し、データセット全体で一度だけ Schema Map として保持する点が根本的に異なる。また、Uber のログでは 21 データセット中 18 個で一意なキー数がスキーマ数より多く、スキーマの多様性はキーの組み合わせ爆発ではなく個々のキーの多様性に起因するという特徴づけ(§3)に基づき、非反復キーの匿名化(unnamed node)という Uber のログに特化した設計を導入している。既存の不構造化ログ圧縮ツール CLP・LogGrep は半構造化データのキー・バリュー構造を扱えず、フィールド単位の絞り込みが困難という制約があるのに対し、µSlope はスキーマメタデータによる論理的な AND/OR フィルタリングと早期終了を実現する。 ## 実験設定 - **実験環境**: 単一スレッド実験は Intel Xeon E5-2630v3、128GB DDR4 メモリの Linux サーバ上で実施し、圧縮/非圧縮ログは MooseFS(分散ファイルシステム、7200RPM SATA HDD)に格納。スケーラビリティ評価は 8 コンテナ(各 96 コア、2TB ネットワーク接続 SSD、32GB RAM)で実施。 - **データセット**: Uber から収集した 16 種類のログデータセット(LogA〜LogP)と、公開ソフトウェア(Apache Spark、MongoDB、CockroachDB、Elasticsearch、PostgreSQL)から HiBench・YCSB ベンチマークで生成した5データセット、計 21 データセット(Table 1)。各データセットは最大 100 万レコードに制限。スケーラビリティ評価では Uber の実運用ログ 434TB(1,378 データセット)および LogF の 26.2TB サブセットを使用。 **Table 1: 実験で使用したログデータセット** ![[_attachments/osdi24-wang-rui/table01-datasets.png]] (Table 1. Uber Logs(LogA〜LogP、16件、30〜103GB)と Public Logs(Spark・MongoDB・CockroachDB・elasticsearch・PostgreSQL、5件)の非圧縮サイズとレコード数。) - **比較対象**: CLP 0.0.2、MongoDB 6.0.5、PostgreSQL 15.2、ClickHouse 23.3.1.2823(pair-wise array・single JSON string・JSON 型の3設定)、Elasticsearch 8.6.2、Zstandard 1.4.9、XZ Utils(LZMA)5.2.2。いずれも外部インデックスなしの公平な比較条件で評価。ClickHouse-JSON は 21 データセット中 10 個、Elasticsearch は 9 個しか取り込めなかった(同名キーで異なる型を持つフィールドを扱えないため)。 - **評価指標**: 圧縮率(非圧縮サイズ/圧縮サイズ)、取り込み速度(MB/s)、クエリレイテンシ(秒、OS バッファキャッシュをクリアしたアーカイブ検索を想定)。クエリセット(Table 2)は Uber の実クエリログ(23,091 件中 7,665 件がユニーク)から代表的な 15 クエリを選定。 **Table 2: 実験で使用したクエリ** ![[_attachments/osdi24-wang-rui/table02-queries.png]] (Table 2. LogF 向け(A〜D)・LogO 向け(E〜I)・MongoDB 向け(J〜O)のクエリ。`...` は実際の値の匿名化を表す。) ## 実験結果 - **圧縮率**: µSlope は全 21 データセットで最高の圧縮率を達成し、平均 68.1:1(21.9:1〜186.8:1)。ClickHouse-String の 2.75 倍、ClickHouse-Pairwise Array の 2.62 倍、ClickHouse-JSON の 1.34 倍、MongoDB の 6.10 倍、PostgreSQL の 16.50 倍、Elasticsearch の 15.71 倍。Zstandard・LZMA・CLP に対してもそれぞれ 2.34 倍・1.70 倍・1.50 倍(Figure 10)。LogP を例に取ると、710MB の圧縮データのうち MPT と Schema Map は合計 5.5KB(3.6KB+1.9KB)に過ぎず、辞書が 26.3%、残り 73.7% が ERT のカラムである。 **Figure 10: µSlope と他ツールの圧縮率比較** ![[_attachments/osdi24-wang-rui/fig10-compression-ratio-comparison.png]] (Figure 10. 21 データセットに対する µSlope・CLP・Zstandard・LZMA・ClickHouse(3設定)・MongoDB・PostgreSQL・Elasticsearch の圧縮率。"×" はそのツールがデータセットを取り込めなかったことを示す。MongoDB データセットで µSlope は 186.78 の圧縮率に達する。) - **取り込み速度**: µSlope の取り込み速度は ClickHouse-String・ClickHouse-Pairwise Array より遅い(これらは JSON をパースしないか、トップレベルのみパースするため)が、全フィールドを完全にパースする他のツールより高速で、ClickHouse-JSON・MongoDB・PostgreSQL・Elasticsearch をそれぞれ 19.3%・186.7%・419.8%・1127.3% 上回り、LZMA も 814.8% 上回る(Figure 11)。 **Figure 11: 平均取り込み速度(対数スケール)** ![[_attachments/osdi24-wang-rui/fig11-ingestion-speed.png]] (Figure 11. µSlope・CLP・Zstandard・LZMA・ClickHouse(3設定)・MongoDB・PostgreSQL・Elasticsearch の平均取り込み速度(MB/s、対数軸)。Zstandard・ClickHouse-String が最速、µSlope は中位。) - **検索性能**: 15 クエリ中 14 クエリで µSlope が全ツールを上回り、平均で ClickHouse-Pairwise Array の 2.47 倍、PostgreSQL の 8.09 倍、MongoDB の 6.74 倍高速(Figure 12)。特に Query J(キー存在チェック)では他ツールより 116 倍以上高速。これはスキーマメタデータの参照だけで該当スキーマを絞り込めるためで、Query J では MPT・Schema Map・ERT の検索が全クエリ時間のわずか 5.5% に過ぎず、73.0% は辞書のロードが占める。Query B(全フィールドを対象にした UUID 検索)では µSlope は全 ERT を解凍・走査する必要があるため ClickHouse-String・ClickHouse-Pairwise Array より遅い。 **Figure 12: µSlope と他ツールのクエリレイテンシ** ![[_attachments/osdi24-wang-rui/fig12-query-latency-comparison.png]] (Figure 12. クエリ A〜O に対する µSlope・ClickHouse-String・ClickHouse-Pairwise Array・MongoDB・PostgreSQL のレイテンシ(秒、対数軸)。Query J・L・N・O のような、マッチするスキーマ数が少ないクエリで µSlope が際立って高速。) - **合成データによる境界評価**: 20 フィールド・670K レコード・1GB のログを、UUID を用いてスキーマ反復性 P(べき乗則分布、0<P≤1)と変数値の反復率(1・10・100・1000)を変えて 28 通り生成。全条件で µSlope は Zstandard を上回るが、P が 0 に近づく(全レコードが一意なスキーマを持つ)極端なケースでは、小さな ERT が大量に生じ、それぞれ別の Zstandard ストリームで圧縮されるオーバーヘッドにより圧縮率が顕著に低下する(Figure 13)。needle-in-haystack クエリ(固定 UUID を検索)のレイテンシも、P が 0 に近い領域で小さなテーブルの大量ロードにより顕著に悪化する(Figure 14)。 **Figure 13: 合成ログにおける µSlope と Zstandard の圧縮率比較** ![[_attachments/osdi24-wang-rui/fig13-synthetic-compression-ratio.png]] (Figure 13. スキーマ反復性 P に対する圧縮率。凡例のカッコ内数値は変数値の反復率(1・10・100・1000)。反復率が高いほど、また P が大きいほど圧縮率が高い。) **Figure 14: 合成ログにおける needle-in-haystack ワイルドカードクエリのレイテンシ** ![[_attachments/osdi24-wang-rui/fig14-synthetic-query-latency.png]] (Figure 14. P が 0 に近い領域でクエリレイテンシが顕著に悪化する。反復率が低いほど変数辞書が肥大化し、解凍前のロードに定数オーバーヘッドが生じる。) - **実運用スケール**: Uber の実運用ログ 434TB・1,378 データセットで平均圧縮率 30.5:1(Figure 15)。圧縮率が低い外れ値は base64 エンコードされたバイナリデータや UUID など非反復的なランダムデータを多く含む。LogF の 26.2TB サブセットに対する検索スケーラビリティ評価では、8 コンテナ・2,155 アーカイブに対して 4〜32 ワーカー/コンテナで実行し、16 ワーカーまではよくスケールするが、32 ワーカーではデータセット内のスキュー(特定アーカイブへの結果集中や、同一コンテナへのマッチングアーカイブの偏り)により頭打ちになる(Figure 16)。 **Figure 15: Uber 実運用ログ 1,378 データセットの圧縮率分布** ![[_attachments/osdi24-wang-rui/fig15-compression-ratio-distribution.png]] (Figure 15. 1,378 データセットの圧縮率を昇順に並べた分布。中央付近は 30〜60 程度で安定し、上位数% は 100 を超える。) **Figure 16: µSlope のクエリ完了時間と応答時間のスケーラビリティ** ![[_attachments/osdi24-wang-rui/fig16-scalability.png]] (Figure 16. クエリ A・B・C・D・E・G(マッチレコード数を括弧内に付記)に対する、4・8・16・32 ワーカー/コンテナでの完了時間(赤)と応答時間(青)。全クエリが 16 ワーカーまでは良好にスケールする。) ## 考察 µSlope の効率性はログの反復性(スキーマの反復性・変数値の反復性)に強く依存する。実運用データでは大半のデータセットで高い反復性が観測され(§3 のキャラクタリゼーション調査では中央値でデータセットあたり 40 種類のユニークスキーマ、変数値の反復率は中央値 37.8)、この前提のもとで µSlope は既存 SSDMS を大きく上回る。逆に、合成データによる境界評価が示す通り、スキーマや値がほぼすべて一意な非反復的なログでは、小さな ERT・辞書のオーバーヘッドが顕著になり、優位性が薄れる。29% のクエリがスキーマメタデータの参照だけで解決できるという実測(§3)は、スキーマ構造を値から切り離す設計判断を直接裏付ける。 ## 強み / 弱点・課題 - **強み**: スキーマメタデータをレコードから分離し一度だけ保持することで、既存 SSDMS を上回る圧縮率(平均 68.1:1)と検索速度(ClickHouse 比 2.47 倍)を同時に達成する。ユーザーによるスキーマ注釈が不要で、動的スキーマを自動的に扱う。圧縮・検索ともにアーカイブ単位で embarrassingly parallel。 - **弱点・課題(論文が明記するもの)**: (1) 追記専用の archival SSDMS であり、更新・削除には非対応。(2) スキーマ構造や値がほぼ一意なログ(反復性が低い)では高い圧縮率を達成できない。(3) term search・field search・wildcard search・range search はサポートするが join のような複雑なクエリには非対応。(4) 全件スキャンかつ大量の結果を生成するクエリでは優位性が薄れる。(5) 現在の実装は各テーブルを個別の Zstandard ストリームに圧縮するため、小さいテーブルが多いと圧縮・解凍のオーバーヘッドが大きい(将来的に複数の小テーブルの結合や大テーブルのカラム単位分割を計画中と明記)。(6) インデックスレス設計のため、Elasticsearch のようなインデックスベースの検索ツールほどは高速でない場合がある。