ストレージアタッチ型インデックス (SAI) の概念

SAI は、追加のインメモリ表現を作成するのではなく、フラッシュしきい値に達したときに Memtable インデックスの内容を直接ディスクにフラッシュします。これは、Memtable インデックスが用語/値でソートされ、次に主キーでソートされるため可能です。フラッシュが発生すると、SSTable が書き込まれる際に、SAI はインデックス付きの列ごとに新しい SSTable インデックスを書き込みます。

フラッシュ操作は 2 フェーズのプロセスです。最初のフェーズでは、行が新しい SSTable に書き込まれます。各行に対して、行 ID が生成され、3 つのインデックスコンポーネントが作成されます。コンポーネントは次のとおりです。

最初のコンポーネントファイルと 2 番目のコンポーネントファイルの内容は、その序数が行 ID に対応する圧縮配列です。

2 番目のフェーズでは、すべての行が新しい SSTable に書き込まれ、共有 SSTable レベルのインデックスコンポーネントが完了した後、SAI はインデックス付きの列ごとにインデックス化作業を開始します。具体的には、2 番目のフェーズで、SAI は Memtable インデックスを反復処理して、用語とそれらのトークンでソートされた行 ID のペアを生成します。このイテレータは、最初のフェーズで構築された一時的なマッピング構造を使用して、主キーを行 ID に変換します。次に、用語イテレータ（投稿付き）は、インデックス付きの要素が文字列列か数値列かによって、個別の書き込みコンポーネントに渡されます。

文字列の場合、SAI インデックスライターは各用語を反復処理し、最初にその投稿をディスクに書き込み、次に、オンディスクのバイト順序トライにある新しいエントリ（用語自体用）のペイロードとして、それらの投稿のオフセットを記録します。数値の場合、SAI は数値インデックスの書き込みを 2 つのステップに分離します。

用語はバランスのとれた kd ツリーライターに渡され、kd ツリーがディスクに書き込まれます。ツリーの葉ブロックが書き込まれると、その投稿は一時的にメモリに記録されます。次に、それらの一時的な投稿を使用して、葉とインデックスノードのさまざまなレベルでオンディスクの投稿が構築されます。

列インデックスのフラッシュが完了すると、成功を示す特別な空のマーカーファイルがフラグ付けされます。この手順は、起動時と増分再構築操作で使用され、次の場合に区別されます。

その後、SAIは列に対してフラッシュされたMemtableインデックスの数をカウントするカウンタを増分し、秒あたりにフラッシュされたセルの数をヒストグラムに追加します。

Apache Cassandraはコンパクションを使用してSSTableをマージすることを思い出してください。コンパクションは、各一意の行のすべてのバージョンを収集し、SSTableから各行の列の最新バージョン（タイムスタンプによる）を使用して、1つの完全な行を組み立てます。マージプロセスは、各SSTable内でパーティションキーによって行がソートされており、マージプロセスがランダムI/Oを使用しないため、パフォーマンスに優れています。各行の新しいバージョンは新しいSSTableに書き込まれます。古いバージョンと、削除の準備ができた行は、古いSSTableに残され、保留中の読み込みが完了すると削除されます。

SAIの場合、コンパクションがトリガーされると、各インデックスグループはSSTable Flush Observerを作成し、新しく圧縮されたデータからすべての添付された列インデックスをそれぞれのSSTableライターインスタンスに書き込むプロセスを調整します。Memtableフラッシュ（インデックス付きの用語は既にソートされている）とは異なり、コンパクション中にマージされたデータを反復処理する際、SAIはインデックス付きの値とその行IDをバッファリングし、トークン順に追加します。

使用可能なヒープリソースを使い果たすなどの問題を回避するために、SAIは累積セグメントバッファを使用します。これは、独自の計算を使用してディスクに同期的にフラッシュされます。次に、各セグメントはセグメント行IDの**オフセット**を記録し、セグメント行ID（SSTable行ID - セグメント行IDオフセット）のみを保存します。SAIは、すべてのセグメントを書き直すコストを回避し、パーティション制限クエリとページング範囲クエリの費用を削減するために、セグメントを同じファイルに同期的にフラッシュします。これは、検索範囲を縮小するためです。

列ごとのインデックス付きポスティング、SSTableオフセット、SSTableパーティションからのオンディスクレイアウト

実際のセグメントフラッシュプロセスは、Memtableフラッシュと非常によく似ています。ただし、バッファリングされた用語は、それぞれのタイプ固有のオンディスク構造にポスティングと共に書き込む前にソートされます。特定のインデックスのコンパクションの最後に、特別な空のマーカーファイルにフラグが立てられて成功を示し、セグメントの数がSAIメトリクスに記録されます。グローバルインデックスメトリクスを参照してください。

コンパクションタスク全体が完了すると、SAIはトランザクション中に追加および削除されたSSTableを含むSSTableリスト変更通知を受信します。SSTableコンテキストマネージャーとインデックスビューマネージャーは、古いSSTableインデックスを新しいSSTableインデックスとアトミックに置き換える役割を担います。この時点で、新しいSSTableインデックスがクエリで使用できるようになります。

クエリが提示されると、SAIコーディネーターが最初に実行するアクションは、1つ以上のインデックスを活用するために、最も選択的なインデックスを特定することです。最も選択的なインデックスとは、推定結果行計算から最も低い値を返すことによって、フィルタリング空間と最終的な結果の数を最も積極的に絞り込むインデックスです。複数のSAIインデックスが存在する場合（つまり、各SAIインデックスが異なる列に基づいているが、クエリが複数の列を含む場合）、最初にどのSAIインデックスが選択されるかは問題ではありません。

読み取り操作に最適なインデックスが選択されると、そのインデックスは読み取りコマンドに埋め込まれ、分散範囲読み取り装置に入力されます。分散範囲読み取りは、トークン順に1回以上のラウンドでApache Cassandraクラスタにクエリを実行します。SAIコーディネーターは、ローカルデータとクエリ制限に基づいて範囲ごとの行数である**同時実行ファクター**を推定し、接触する範囲の数を決定します。各ラウンドで、同時実行ファクターは、並列にクエリされるレプリカの数を決定します。

最初のラウンドが始まる前に、SAIはステップ1としてここに示す独自の計算を介して初期の同時実行ファクターを推定します。

初期の同時実行ファクターが確立されると、範囲読み取りが開始されます。

ステップ2で、SAIコーディネーターは同時実行ファクターに基づいて必要な範囲に並列でリクエストを送信します。ステップ3で、SAIコーディネーターはリクエストされたレプリカからの応答を待ちます。ステップ4で、SAIコーディネーターは結果を収集し、返された行とクエリ制限に基づいて同時実行ファクターを再計算します。

各ラウンドの完了時に、制限に達していない場合、既に読み取られた結果の形状を考慮して同時実行ファクターが調整されます。最初のラウンドから結果が返されない場合、同時実行ファクターは、残りのトークン範囲の最小計算と同時実行ファクターの最大計算にすぐに増やされます。結果が返された場合、同時実行ファクターが更新されます。クエリ制限が満たされるまで、SAIはステップ2、3、4を繰り返します。

インデックスに障害が発生したレプリカにクエリを実行するのを回避するために、各ノードはゴシップを介して独自のローカルインデックスステータスをピアに伝播します。コーディネーターでは、読み取りリクエストは、リクエストで使用されているクエリ不可能なインデックスを含むレプリカをフィルタリングします。ほとんどの場合、2回目のレプリカクエリで必要なすべての結果が返されます。レプリカ間の結果の分布が非常に不均衡な場合、さらにラウンドが必要になる場合があります。

レプリカがSAIコーディネーターからトークン範囲読み取りリクエストを受信すると、ローカルインデックスクエリが開始されます。SAIはクエリプランを介してインデックス検索インターフェースを実装しており、単一クエリですべての利用可能なSAI列インデックスにアクセスできます。

クエリプランは、読み取りコマンドを介して渡された式の分析を実行します。SAIは、指定された列のクエリ句を満たすために使用するインデックスを決定します。列式がインデックスとペアリングされると、クエリコントローラーによって各列インデックスのアクティブなSSTableインデックスのビューが取得されます。進行中のクエリで使用されているインデックスファイルがコンパクションによって削除されるのを回避するために、クエリコントローラーはインデックスファイルを読み取る前に、クエリのトークン範囲と交差するインデックスファイルのSSTableへの参照を取得しようと試み、読み取りリクエストが完了するとそれらを解放します。

この時点で、各列インデックスから一致をストリーミングするためのトークンフローが作成されます。それらのフローと、それらがどのようにマージされるかを決定するブール論理は、オペレーションにまとめられ、クエリプランコンポーネントに返されます。

SAIクエリエンジンは、SAIが個々のSSTableインデックスと列インデックス全体の両方から一致するパーティションのストリームを非同期的に反復処理、スキップ、マージする方法を定義するトークンフローフレームワークを中心に展開されています。SAIは、Cassandraリングトークン内のパーティション一致のコンテナを表すトークンを使用します。

反復処理は、3つの操作の中で最も単純なものです。具体的には、ポスティングの反復処理には、チャンクキャッシュを介した行IDへのシーケンシャルディスクアクセスが含まれ、これを使用してリングトークンとパーティションキーオフセット情報をルックアップします。

トークンスキップは、前のページング境界から継続する場合、またはトークン交差中により大きなトークンが見つかった場合に、一致しないトークンをスキップするために使用されます。

個々の列インデックス（例：age = 44）の例を考えてみましょう。生成されるフローは、すべてのMemtableインデックスとすべてのSSTableインデックスの和集合です。

クエリに複数のインデックス式（例：WHERE age=44 AND state='CA'）がANDクエリ演算子で接続されている場合、インデックス式の結果は交差され、すべてのインデックス式に一致するパーティションキーが返されます。

インデックス検索後、SAIはパーティションキーのフローを公開します。SAIは、パーティションキーごとに単一のパーティション読み取り操作を実行し、指定されたパーティション内の行を返します。行がマテリアライズされると、SAIはフィルタツリーを使用して別のフィルタリングラウンドを適用します。SAIは、次の点を解決するために、この後続のフィルタリングステップを実行します。