統合コンパクション戦略 (UCS)

戦略

読み取り増幅

レベル型

これは、べき乗をすべての下位レベルのファンファクターの積に置き換えることで、さまざまなファンファクターに簡単に一般化できます。

このシャーディングメカニズムは、コンパクション仕様とは無関係です。SSTable を分割するための選択肢はいくつかあります。

サイズのみで分割すると、開始位置が異なる個々の SSTable が生成されます。このように分割された SSTable を圧縮するには、レベル全体のトークン範囲を順番に圧縮するか、重複する SSTable により、必要以上に何度もデータを圧縮してコピーする必要があります。事前に定義された境界点を使用すると、トークン範囲の一部が入力が少なくなり、結果の SSTable の密度が歪む可能性があります。その場合、さらに分割が必要になる場合があります。ハイブリッドオプションでは、密度の歪みが発生する頻度は少なくなりますが、それでも発生する可能性があります。

これらの問題を回避し、コンパクション階層のすべてのレベルの同時コンパクションを可能にするために、UCS はすべてのコンパクションの境界点を事前に定義し、常にこれらのポイントで SSTable を分割します。境界の数は、入力 SSTable の密度と結果の SSTable の推定密度から決定されます。密度が大きくなるにつれて、境界の数は増加し、個々の SSTable のサイズを事前に定義されたターゲットの近くに維持します。指定されたベースカウントの 2 のべき乗の倍数を使用する、つまりシャードを中央で分割することで、特定の出力密度に適用される境界がすべての上位密度にも適用されるようになります。

2 つのシャーディングパラメータを設定できます。

すべてのコンパクションの開始時に、出力の密度 d は、SSTable の入力サイズ s とトークン範囲 v に基づいて推定されることを思い出してください。

ここで、v は入力 SSTable によってカバーされるトークン範囲の割合であり、0 から 1 の値です。v = 1 は、トークン範囲全体が入力 SSTable によってカバーされていることを意味し、v = 0 は、入力 SSTable がトークン範囲をカバーしていないことを意味します。

memtable から L0 への最初のフラッシュが発生すると、トークン範囲全体が memtable に含まれるため、v = 1 になります。後続のコンパクションでは、トークン範囲 v は、圧縮される SSTable によってカバーされるトークン範囲の割合です。

計算された出力の密度と、b と st の値を使用して、トークンスペースを分割するシャードの数 S を計算できます。

ここで、\(\lfloor x \rceil\) は、x を最も近い整数に丸めた値、つまり \(\lfloor x + 0.5 \rfloor\) を表します。したがって、2 番目のケースでは、密度はターゲットサイズで除算され、b の 2 のべき乗の倍数に丸められます。結果が 1 未満の場合、memtable は {2 \cdot b}、つまり b 個の L0 シャードに分割されるため、シャードの数はベースシャードカウントになります。

ただし、b シャードとそれ以上のシャードを切り替えるかどうかに影響を与える要因は、トークン範囲だけではありません（条件が 1 以上の場合）。memtable が非常に大きく、一度に数ギガバイトをフラッシュできる場合、d は st よりも桁違いに大きくなる可能性があり、L0 でも SSTable が複数のシャードに分割される可能性があります。逆に、memtable が小さい場合、条件が 1 未満の上位レベルの L0 では、d は st よりも小さいままである可能性があり、したがって、stem[b] シャードが存在します。

S - 1 個の境界が生成され、ローカルトークンスペースが S 個のシャードに均等に分割されます。ローカルトークンスペースを分割すると、これらの境界でコンパクションの結果が分割され、各シャードに個別の SSTable が形成されます。生成される SSTable のサイズは、\(s_{t}/\sqrt 2\) から \(s_{t} \cdot \sqrt 2\) の間になります。

たとえば、ターゲット SSTable サイズ st = 100MiB と b = 4 ベースシャードを使用してみましょう。sf = 200 MiB の入力 memtable がフラッシュされる場合、シャードの数を計算するための条件は次のとおりです。

最初のフラッシュでは v = 1 の値になるため、この計算の結果は 0.5 < 1 になります。結果が 1 未満であるため、ベースシャードカウントが使用され、memtable は約 50MiB ずつの 4 つの L0 シャードに分割されます。各シャードはトークンスペースの 1/4 に及びます。

例を続けると、次のレベルのコンパクションでは、4 つのシャードのうちの 1 つだけについて、これらの 50 MiB SSTable のうち 6 つを圧縮してみましょう。出力の推定密度は次のようになります。

入力 SSTable によってカバーされるトークン範囲の v 値として 1/4 を使用します。

分割の条件は次のとおりです。

したがって、シャードの数は次のように計算されます。

または、\(2^{\log_2 3}\) を、ローカルトークンスペース全体で \(2^2 \cdot 4\) シャードに丸め、トークンスペースの 1/4 をカバーするコンパクションを行います。上書きまたは削除がないと仮定すると、結果の SSTable のサイズは 75 MiB、トークンシェアは 1/16、密度は 1200 MiB になります。

このシャーディングスキームは簡単に拡張できます。現在実装されている拡張機能は 2 つあります。SSTable の増加と SSTable の最小サイズです。

まず、データセットのサイズが非常に大きくなると予想される場合について調べてみましょう。SSTable あたりのオーバーヘッドの問題を回避するために十分な大きさのターゲットサイズを事前に指定することを避けるために、`SSTtable growth` パラメータが実装されました。このパラメータは、密度増加のどの部分を SSTable サイズの増加に割り当てるかを決定し、シャード数の増加、つまり重複しない SSTable の増加を削減します。

2 番目の拡張機能は、最小サイズに達した場合に条件付きで分割する、固定数のシャードを使用した動作モードです。`minimum SSTable size` を定義することで、分割によって提供された最小値よりも小さい SSTable が生成される場合は常に、ベースシャードカウントを削減できます。

ユーザー定義のシャーディングパラメータは 4 つあります。

特定の密度 d に対するシャードの数 S は、次のように計算されます。

これらのパラメータの便利な組み合わせをいくつか示します。

コンパクション戦略は、クエリの読み取り増幅を最小限に抑えることを目的としています。読み取り増幅は、任意のキーで重複する SSTable の数によって定義されます。コンパクションが遅い状況で最高の効率を得るために、可能な選択肢の中から重複が最も多いコンパクションバケットが選択されます。複数の選択肢がある場合は、各レベル内で均一かつランダムに 1 つを選択します。レベル間では、同じ量の作業に対してトークンスペースの大部分をカバーすることが想定されるため、最も低いレベルが優先されます。

持続的な負荷の下では、このメカニズムにより、従来の戦略では発生する可能性があった一部のレベルでの SSTable の蓄積を防ぎます。古い戦略では、すべてのリソースが L0 によって消費され、SSTable が L1 に蓄積される可能性がありました。UCS を使用すると、コンパクションが常に割り当てられたしきい値とファンファクターよりも多くの SSTable を使用する定常状態が実現し、維持できる最小の重複に基づいて階層化された階層が維持されます。

UCS の動作原理では、メジャーコンパクションは、（推移的に）重複するすべての SSTable を一緒にコンパクションする操作であり、出力は予想される結果の密度に適したシャード境界で分割されます。

言い換えれば、メジャーコンパクションは \(b\) 個の同時コンパクションを実行し、それぞれが各ベースシャードに含まれるすべての SSTable を含みます。結果は、シャードに含まれるデータの合計サイズに応じて数が決まるシャード境界で分割されます。

STCS は UCS と非常によく似ています。ただし、STCS は、サイズの事前定義されたバンディングを使用するのではなく、同じようなサイズの SSTable を探すことによってバケット/レベルを定義します。したがって、STCS は、サイズが大きく異なる SSTable にまたがる奇妙なバケットの選択になる可能性があります。UCS の選択はより安定しており、予測可能です。

STCS は、あるバケットに少なくとも min_threshold 個の SSTable が見つかったときにコンパクションをトリガーし、そのバケットから一度に min_threshold 個から max_threshold 個の SSTable をコンパクションします。min_threshold は UCS の \(t = f = w + 2\) に相当します。UCS は、非常に多数の SSTable でもコンパクションが効率的であるため、上限を削除します。

UCS は密度測定を使用して結果を分割し、SSTable のサイズとコンパクションの時間を短く抑えます。レベル内では、UCS はしきい値に達したかどうかを判断するときに重複する SSTable のみを考慮し、重複しない SSTable のセットを個別にコンパクションします。

バケット内で SSTable を選択する選択肢が複数ある場合、STCS はサイズでグループ化しますが、UCS はタイムスタンプでグループ化します。そのため、STCS は時間順序が簡単に失われ、テーブル全体の有効期限が切れにくくなります。UCS は時間順序とテーブル全体の有効期限を効率的に追跡します。UCS はテーブル全体の有効期限を適用できるため、この機能は有効期限付きの時系列データにも役立ちます。

LCS は UCS と比較して動作が大きく異なるように見えます。ただし、実際には、2 つの戦略は非常によく似ています。

LCS はレベルごとに複数の SSTable を使用して、小さな固定サイズの重複しない SSTable のソート済み実行を形成します。そのため、増加するレベルの物理 SSTable は、サイズではなく数（fanout_size 倍）が増加します。このようにして、LCS は空間増幅を削減し、コンパクション時間を短縮します。レベルの実行の合計サイズが予想よりも大きい場合、階層の次のレベルから重複するものとコンパクションする SSTable を選択します。最終的に、次のレベルのサイズがサイズ制限を超えると、より高いレベルの操作がトリガーされます。

UCS では、増加するレベルの SSTable はファンアウトファクター \(f\) によって密度が増加します。2 番目に重複する SSTable がシャーディングされたレベルにある場合、コンパクションがトリガーされます。UCS はそのレベルで重複するバケットをコンパクションし、結果はほとんどの場合そのレベルにもなります。しかし最終的には、データは次のレベルに十分なサイズに達します。データが均等に分散されている場合、UCS と LCS は同様に動作し、コンパクションは同じタイムフレームでトリガーされます。

2 つのアプローチは非常に似た効果をもたらします。UCS には、コンパクションが他のレベルに影響を与えることができないという追加の利点があります。LCS では、L0 から L1 へのコンパクションにより、同時 L1 から L2 へのコンパクションが妨げられる可能性があり、これは unfortunate な状況です。UCS では、SSTable は階層型 UCS に簡単に切り替えたり、異なるパラメーター設定で変更したりできるように構築されています。

LCS SSTable はサイズに基づいているため分割位置が異なるため、LCS が次のレベルでコンパクションする SSTable を選択すると、部分的にのみ重複する SSTable が含まれます。その結果、SSTable は厳密に必要な回数よりも頻繁にコンパクションされる可能性があります。

UCS は、特定のトークン境界でシャーディングすることにより、空間増幅の問題に対処します。LCS は固定サイズに基づいて SSTable を分割し、境界は通常次のレベルの SSTable 内に収まるため、必要以上に頻繁にコンパクションが開始されます。したがって、UCS は厳密な書き込み増幅制御に役立ちます。これらの境界により、低密度 SSTable のスパンと正確に一致する高密度 SSTable を効率的に選択できます。