アーキテクチャの概要
This is the web version of our VLDB 2024 scientific paper. We also blogged about its background and journey, and recommend watching the VLDB 2024 presentation by ClickHouse CTO and creator, Alexey Milovidov:
ABSTRACT
過去数十年にわたり、保存および分析されるデータ量は指数関数的に増加しています。さまざまな産業や業界の企業は、このデータを利用して製品を改善し、パフォーマンスを評価し、ビジネス上重要な意思決定を行うようになっています。しかし、データ量がインターネットスケールに達するにつれて、企業は歴史的データと新データをコスト効率よくスケーラブルな方法で管理し、高い同時クエリ数とリアルタイムのレイテンシ(使用例に応じて1秒未満)を期待して分析する必要があります。
この論文では、ペタバイト級のデータセットに対して高性能な分析を行うために設計された人気のオープンソースOLAPデータベース、ClickHouseの概要を示します。そのストレージ層は、伝統的なログ構造マージ(LSM)ツリーに基づいたデータ形式と、バックグラウンドでの歴史的データの継続的な変換(例:集約、アーカイブ)のための新しい技術を組み合わせています。クエリは便利なSQLダイアレクトで書かれ、最先端のベクトル化クエリ実行エンジンによって処理され、オプションでコードコンパイルも可能です。ClickHouseは、クエリ内で無関係なデータを評価しないよう積極的にプルーニング技術を使用します。他のデータ管理システムは、テーブル関数、テーブルエンジン、またはデータベースエンジンレベルで統合できます。実世界のベンチマークは、ClickHouseが市場で最も高速な分析データベースの一つであることを示しています。
1 INTRODUCTION
この論文では、高パフォーマンスの分析クエリを行うために設計された列指向OLAPデータベースであるClickHouseについて説明します。ClickHouseは、2009年にWebスケールのログファイルデータ用のフィルターと集約演算子として開始され、2016年にオープンソース化されました。Figure 1は、この論文で説明されている主要な機能がClickHouseに導入された時期を示しています。
ClickHouseは、現代の分析データ管理の5つの主要な課題に対処するように設計されています:
-
高い取り込みレートの巨大データセット。Web分析、金融、eコマースのようなデータ駆動型アプリケーションは、巨大で常に増加するデータ量が特徴です。巨大データセットを処理するために、分析データベースは効率的なインデックス作成や圧縮戦略だけでなく、複数のノードにデータを分散させる(スケールアウト)能力を提供する必要があります。単一サーバーは数十テラバイトのストレージに制限されているため、最近のデータはリアルタイムインサイトに対して歴史的データよりも重要であることが多いです。その結果、分析データベースは高レートまたはバーストで新しいデータを取り込む能力を有し、さらに並行報告クエリを遅くせずに歴史的データを「重要度を下げる」(例:集約、アーカイブ)必要があります。
-
低レイテンシーでの多くの同時クエリ。クエリは一般に、アドホック(例:探索的データ分析)または再発(例:定期的なダッシュボードクエリ)に分類できます。用途がインタラクティブであればあるほど、クエリレイテンシーは低くなることが期待され、クエリ最適化および実行において課題を引き起こします。再発クエリは、作業負荷に応じてデータベースの物理的なレイアウトを調整する機会も提供します。そのため、データベースは頻繁なクエリを最適化できるプルーニング技術を提供すべきです。クエリの優先度に応じて、データベースは同時に多くのクエリが実行されていても、CPU、メモリ、ディスク、ネットワークI/Oなどの共有システムリソースへの平等または優先アクセスを保証する必要があります。
-
多様なデータストア、ストレージ場所、フォーマットの景観。既存のデータアーキテクチャと統合するために、現代の分析データベースは、いかなるシステム、場所、またはフォーマットであっても外部データを読み書きするために高い程度のオープン性を示す必要があります。
-
パフォーマンスイントロスペクションをサポートする便利なクエリ言語。OLAPデータベースの実際の使用は、追加の「ソフト」要件を持ちます。たとえば、ニッチなプログラミング言語の代わりに、ユーザーはしばしばネストされたデータ型と幅広い通常の、集約、およびウィンドウ関数を備えた表現豊かなSQLダイアレクトでデータベースとインターフェースすることを好みます。分析データベースは、システムや個別クエリのパフォーマンスをイントロスペクトするために洗練されたツールも提供する必要があります。
-
業界標準の堅牢性および多様な展開。一般的なハードウェアは信頼性が低いため、データベースはノードの障害に対して堅牢性を提供するためにデータ複製を行わなければなりません。また、データベースは古いラップトップから強力なサーバーまで、任意のハードウェアで稼働する必要があります。最後に、JVMベースのプログラムにおけるガベージコレクションのオーバーヘッドを回避し、ベアメタルパフォーマンス(例:SIMD)を可能にするために、理想的にはデータベースはターゲットプラットフォームのネイティブバイナリとして展開されるべきです。

Figure 1: ClickHouseのタイムライン。
2 ARCHITECTURE

Figure 2: ClickHouseデータベースエンジンの高レベルアーキテクチャ。
Figure 2に示されるように、ClickHouseエンジンは、クエリ処理層(4節で説明)、ストレージ層(3節)、および統合層(5節)という3つの主要な層に分かれています。また、アクセス層がユーザーセッションとアプリケーションとの通信をさまざまなプロトコル経由で管理します。スレッド処理、キャッシング、ロールベースのアクセス制御、バックアップ、および継続的監視のための直交コンポーネントがあります。ClickHouseは、依存関係のない単一の静的リンクされたバイナリとしてC++で構築されています。
クエリ処理は、受信クエリの解析、論理プランと物理プランの構築および最適化、そして実行の従来のパラダイムに従っています。ClickHouseは、MonetDB/X100に似たベクトル化実行モデルを使用し、この組み合わせで機会主義的なコードコンパイルを行います。クエリは、機能が豊富なSQLダイアレクト、PRQL、またはKustoのKQLで書くことができます。
ストレージ層は、テーブルデータのフォーマットと場所をカプセル化するさまざまなテーブルエンジンで構成されています。テーブルエンジンは3つのカテゴリに分かれます。最初のカテゴリは、ClickHouseでの主要な永続フォーマットを表すMergeTreeファミリーのテーブルエンジンです。LSMツリーに基づくアイデアを基に、テーブルは水平にソートされたパーツに分割され、バックグラウンドプロセスによって継続的にマージされます。個々のMergeTreeテーブルエンジンは、入力パーツから行をどのようにマージするかで異なります。たとえば、古くなった場合には行を集約したり置き換えたりすることができます。
2番目のカテゴリは、クエリ実行を高速化または分散させるための特定目的のテーブルエンジンです。このカテゴリには、辞書と呼ばれるメモリ内キー値テーブルエンジンが含まれています。辞書は、内部または外部データソースに対して定期的に実行されるクエリの結果をキャッシュします。これにより、データの古さをある程度許容できるシナリオでのアクセスレイテンシーが大幅に削減されます。特定目的のテーブルエンジンの他の例には、一時的なテーブル用に使用される純粋なメモリ内エンジンや、透明なデータシャーディング用の分散テーブルエンジンがあります(下記を参照)。
テーブルエンジンの3番目のカテゴリは、リレーショナルデータベース(例:PostgreSQL、MySQL)、パブリッシュ/サブスクライブシステム(例:Kafka、RabbitMQ [24])、またはキー/値ストア(例:Redis)との双方向データ交換用の仮想テーブルエンジンです。仮想エンジンは、データレイク(例:Iceberg、DeltaLake、Hudi [36])やオブジェクトストレージ内のファイル(例:AWS S3、Google GCP)とも相互作用できます。
ClickHouseは、スケーラビリティと可用性のために、複数のクラスターノードにわたるテーブルのシャーディングと複製をサポートしています。シャーディングは、シャーディング式によってテーブルをテーブルシャードのセットに分割します。個々のシャードは相互に独立したテーブルであり、通常は異なるノードに配置されます。クライアントは、シャードを直接読み書きでき、つまりそれらを別個のテーブルとして扱うこともできますし、すべてのテーブルシャードのグローバルビューを提供する分散特殊テーブルエンジンを使用することもできます。シャーディングの主な目的は、個々のノードの容量を超えるデータセットを処理することです(通常、数十テラバイトのデータ)。シャーディングの別の使用法は、テーブルの読み書き負荷を複数のノードに分散させること、つまり負荷分散です。そのため、シャードはノード障害に対する耐障害性のために複製されることができます。この目的のために、各Merge-Treeテーブルエンジンには、その対応するReplicatedMergeTreeエンジンがあり、Raftコンセンサスに基づくマルチマスターコーディネーション方式を使用します [59](C++で書かれたApache Zookeeperのドロップイン置き換えであるKeeperによって実装)を使用하여、常に設定可能な数のレプリカを各シャードに持つことを保証します。セクション3.6では、レプリケーションメカニズムについて詳しく説明します。例として、Figure 2は、2つのノードに複製された2つのシャードを持つテーブルを示しています。
最後に、ClickHouseデータベースエンジンは、オンプレミス、クラウド、スタンドアロン、またはプロセス内モードで運用できます。オンプレミスモードでは、ユーザーはClickHouseを単一サーバーまたはシャーディングおよび/または複製を持つマルチノードクラスタとしてローカルにセットアップします。クライアントは、ネイティブ、MySQLの、PostgreSQLのバイナリワイヤプロトコル、またはHTTP REST APIを介してデータベースと通信します。クラウドモードは、完全に管理され、自動スケーリングするDBaaSオファリングであるClickHouse Cloudによって表されます。この論文はオンプレミスモードに焦点を当てていますが、次回の publication でClickHouse Cloudのアーキテクチャを説明する予定です。スタンドアロンモードは、ClickHouseをファイルの分析と変換のためのコマンドラインユーティリティに変え、catやgrepのようなUnixツールのSQLベースの代替手段を提供します。このモードは事前の設定を必要とせず、単一のサーバーに制限されます。最近、Jupyterノートブック[37]のようなインタラクティブなデータ分析の使用例のために、chDBと呼ばれるプロセス内モードが開発されました[15]。DuckDB[67]からインスピレーションを得たchDBは、ClickHouseをホストプロセスに高性能OLAPエンジンとして組み込みます。その他のモードと比較して、データベースエンジンとアプリケーション間で、同じアドレス空間で実行されるため、データソースと結果データを効率的に渡すことができます。
3 STORAGE LAYER
このセクションでは、ClickHouseのネイティブストレージフォーマットとしてのMergeTree*テーブルエンジンについて説明します。ディスク上の表現を説明し、ClickHouseにおける3つのデータプルーニング技術について議論します。その後、同時挿入に影響を与えることなくデータを継続的に変換するマージ戦略を紹介します。最後に、更新と削除、データ重複排除、データ複製、ACID準拠がどのように実装されているかを説明します。
3.1 On-Disk Format
MergeTree*テーブルエンジン内の各テーブルは、不変のテーブルパーツのコレクションとして整理されます。行のセットがテーブルに挿入されると、パーツが作成されます。パーツは、その内容を解釈するために中央カタログへの追加の検索なしに必要なすべてのメタデータを含むという点で自己完結しています。テーブルごとのパーツの数を少なく保つために、バックグラウンドマージジョブは定期的に複数の小さなパーツをより大きなパーツに統合し、設定可能なパーツサイズ(デフォルトでは150 GB)に達するまで続けます。パーツはテーブルの主キー列によってソートされているため(3.2節を参照)、効率的なk方向マージソートがマージに使用されます。元のパーツは非アクティブとしてマークされ、その参照カウントがゼロに減少すると最終的に削除されます。すなわち、他のクエリがそれらから読み取ることはありません。
行は、2つのモードで挿入できます。:同期挿入モードでは、各INSERTステートメントが新しいパーツを作成し、それをテーブルに追加します。マージのオーバーヘッドを最小化するために、データベースクライアントはトゥプルを一度に20,000行など一括で挿入することを推奨されています。しかし、データがリアルタイムで分析されるべきである場合、クライアント側のバッチ処理によって引き起こされる遅延はしばしば受け入れられないものです。たとえば、可視性の使用例は、数千の監視エージェントがイベントやメトリクスデータを継続的に小さな量で送信することを含みます。このようなシナリオでは、ClickHouseが同じテーブルへの複数の受信INSERTから行をバッファリングし、バッファサイズが設定可能な閾値を超えるか、タイムアウトが切れるまで新しいパーツを作成しない非同期挿入モードを利用できます。

Figure 3: MergeTree*-エンジンテーブルの挿入とマージ。
Figure 3は、MergeTree*-エンジンテーブルへの4つの同期および2つの非同期挿入を示しています。2つのマージは、アクティブなパーツの数を最初の5つから2つに減らしました。
LSMツリー [58] とそのさまざまなデータベースでの実装 [13, 26, 56] では、ClickHouseはすべてのパーツを平等に扱い、階層に配置することはありません。その結果、マージはもはや同じレベルのパーツに限られません。これは、パーツの暗黙の時間的順序を放棄することも意味し、トゥームストーンに基づかない他の更新および削除のメカニズムが必要になります(3.4節を参照)。ClickHouseは挿入をディスクに直接書き込みますが、他のLSMツリーベースのストアは通常、先行書き込みログを使用します(3.7節を参照)。
パーツはディスク上のディレクトリに対応し、各列用に1つのファイルを含みます。最適化として、小さなパーツ(デフォルトでは10MB未満)の列は、読み書きの空間的局所性を向上させるために、単一のファイルに連続して保存されます。パーツの行はさらに8192レコードのグループ、すなわちグラニュールに論理的に分割されます。グラニュールは、ClickHouseのスキャンおよびインデックスルックアップ演算子が処理する最小の不可分なデータユニットを表します。ただし、ディスク上のデータの読み書きはグラニュールレベルではなく、カラム内の隣接するグラニュールを結合したブロックのグラニュラリティで行われます。新しいブロックは、設定可能なバイトサイズ(デフォルトは1MB)に基づいて形成され、すなわち、ブロック内のグラニュールの数は変動し、列のデータ型と分布に依存します。さらに、ブロックはそのサイズとI/Oコストを削減するために圧縮されます。ClickHouseはデフォルトでLZ4 [75] を一般的な圧縮アルゴリズムとして使用しますが、ユーザーは浮動小数点データ用のGorilla [63] やFPC [12]のような特殊なコーデックも指定できます。圧縮アルゴリズムはチェインされることもあります。たとえば、数値の論理的冗長性を最初にデルタコーディング [23]を使用して削減し、その後で重い圧縮を行い、最後にAESコーデックを使用してデータを暗号化することが可能です。ブロックは、ディスクからメモリに読み込まれるときにリアルタイムで解凍されます。圧縮にもかかわらず、ClickHouseは各列に対して、各グラニュールIDをカラムファイル内のその圧縮ブロックのオフセットおよび非圧縮ブロック内のグラニュールのオフセットに関連付けるマッピングも保存します。
列はさらに辞書エンコード [2, 77, 81] されたり、Nullableを持つ内部ビットマップを追加したりすることができます。LowCardinality(T)は、元のカラムの値を整数IDで置き換え、ユニークな値が少ないデータのストレージオーバーヘッドを大幅に削減します。Nullable(T) は、カラム T に対して、カラム値が NULL であるかどうかを表す内部ビットマップを追加します。
最後に、テーブルは任意のパーティショニング式を使用して範囲、ハッシュ、またはラウンドロビンでパーティショニングできます。パーティションプルーニングを有効にするために、ClickHouseは、各パーティションの最小値と最大値をパーティショニング式の形式で追加で保存します。ユーザーは、ハイパーログログ [30] やt-digest [28] 統計のような高度なカラム統計を任意で作成し、基数推定も提供できます。
3.2 Data Pruning
ほとんどの使用例では、ペタバイトのデータをスキャンして単一のクエリに応答することは非常に遅くコストがかかります。ClickHouseは、検索中の大多数の行をスキップすることを可能にする3つのデータプルーニング技術をサポートしており、それによってクエリを大幅に高速化することができます。
最初に、ユーザーはテーブルに主キーインデックスを定義できます。主キー列は、各パーツ内の行のソート順を決定します。つまり、インデックスはローカルにクラスタ化されたものになります。ClickHouseは、各グラニュールの最初の行の主キー列値からそのグラニュールIDへのマッピングを、各パーツのために追加でも保存します。すなわち、インデックスはスパースです [31]。生成されるデータ構造は通常メモリ内に完全に保持できるほど小さく、たとえば810万行をインデックスするにはわずか1000エントリが必要です。主キーの主な目的は、順次スキャンの代わりにバイナリ検索を使用して、頻繁にフィルタされるカラムに対する等号および範囲述語を評価することです(4.4節を参照)。ローカルソートはさらにパーツのマージやクエリ最適化にも活用されることができ、並べ替え列の接頭辞を形成する主キー列があれば、物理的実行プランからソート演算子を削除することができます。
Figure 4は、ページインプレッション統計のテーブルの主キーインデックスをEventTime列に示しています。クエリ内の範囲述語に一致するグラニュールは、EventTimeを順次スキャンする代わりに、主キーインデックスをバイナリ検索することで見つけることができます。

Figure 4: 主キーインデックスを使用したフィルターの評価。
第二に、ユーザーはテーブルのプロジェクションを作成できます。つまり、異なる主キーでソートされた同じ行を含むテーブルの代替バージョンです [71]。プロジェクションは、メインテーブルの主キーとは異なる列でフィルタリングするクエリのスピードを向上させることができますが、挿入、マージ、スペース消費に対するオーバーヘッドが増加します。デフォルトでは、プロジェクションはメインテーブルに新しく挿入されたパーツからのみ遅延的にポピュレートされますが、ユーザーがプロジェクションをすべて具現化しない限り、既存のパーツからは取得されません。クエリオプティマイザは、メインテーブルまたはプロジェクションからの読み取りを、推定されたI/Oコストに基づいて選択します。パーツのプロジェクションが存在しない場合、クエリの実行は対応するメインテーブルパーツにフォールバックします。
第三に、スキッピングインデックスはプロジェクションに対する軽量の代替手段を提供します。スキッピングインデックスのアイデアは、複数の連続するグラニュールのレベルでの小さなメタデータを保存し、不必要な行をスキャンするのを防ぐことです。スキッピングインデックスは、任意のインデックス式に対して作成され、設定可能なグラニュラリティ、つまりスキッピングインデックスブロック内のグラニュール数を使用できます。利用可能なスキッピングインデックスタイプには以下が含まれます:1. 最小-最大インデックス [51]、各インデックスブロックのインデックス式の最小値と最大値を保存します。このインデックスタイプは、絶対範囲が小さいローカルクラスタデータに適しています、例:緩くソートされたデータ。2. セットインデックスは、設定可能な数のユニークなインデックスブロック値を保存します。これらのインデックスは、小さなローカル基数のデータ、つまり「クランプされている」値で使用するのが最良です。3. ブルームフィルタインデックス [9] は、行、トークン、またはn-グラム値のために構築され、設定可能な誤検知率を持ちます。これらのインデックスはテキスト検索 [73] をサポートしますが、最小-最大およびセットインデックスとは異なり、範囲や否定述語に使用することはできません。
3.3 Merge-time Data Transformation
ビジネスインテリジェンスや可視化の使用例では、常に高いレートまたはバーストで生成されるデータを処理する必要があります。また、最近生成されたデータは通常、歴史的データよりも意味のあるリアルタイムインサイトのためにより関連性が高いです。このような使用例では、データベースは高いデータ取り込みレートを維持しながら集約やデータの老化といった技術を用いて歴史的データのボリュームを継続的に削減する必要があります。ClickHouseは、さまざまなマージ戦略を用いて既存データの継続的な増分変換を可能にします。マージ時のデータ変換はINSERTステートメントのパフォーマンスを損なうことはありませんが、テーブルに不要な(例:古いまたは非集約)値が決して含まれないことを保証することはできません。必要に応じて、すべてのマージ時変換は、SELECTステートメントでFINALキーワードを指定することによりクエリ時間に適用できます。
置換マージは、各トゥプルの含まれるパーツの作成タイムスタンプに基づいて、最も最近挿入されたバージョンのみを保持します。古いバージョンは削除されます。トゥプルは、同じ主キー列値を持つ場合には等価と見なされます。どのトゥプルが保持されるかを明示的に制御するために、比較のための特別なバージョン列を指定することも可能です。置換マージは、通常頻繁に更新される使用例でのマージ時更新メカニズムとして、または挿入時データ重複排除の代替手段(3.5節を参照)として一般的に使用されます。
集約マージは、同じ主キー列値を持つ行を集約行にまとめます。非主キー列は、要約値を保持する部分集約状態でなければなりません。2つの部分集約状態、例えばavg()のための合計とカウントは、新しい部分集約状態に結合されます。集約マージは、通常のテーブルよりもマテリアライズドビューに使用されます。マテリアライズドビューは、ソーステーブルに対する変換クエリに基づいてポピュレートされます。ClickHouseは、他のデータベースとは異なり、ソーステーブルの全内容でマテリアライズドビューを定期的に更新することはありません。むしろ、マテリアライズドビューは新しいパーツがソーステーブルに挿入されるときに変換クエリの結果で増分的に更新されます。
Figure 5は、ページインプレッション統計のテーブルに定義されたマテリアライズドビューを示しています。ソーステーブルに挿入された新しいパーツについて、変換クエリは地域ごとに最大および平均レイテンシーを計算し、その結果をマテリアライズドビューに挿入します。集約関数avg()およびmax()は、実際の結果の代わりに部分集約状態を返します。マテリアライズドビューに対して定義された集約マージは、異なるパーツの部分集約状態を継続的に結合します。最終的な結果を得るために、ユーザーはマテリアライズドビュー内の部分集約状態をavg() および max() で consolidation します。

Figure 5: マテリアライズドビューにおける集約マージ。
TTL(有効期限)マージは歴史的データの老化を提供します。削除や集約マージとは異なり、TTLマージは一度に1つのパーツのみを処理します。TTLマージは、トリガーとアクションのルールによって定義されます。トリガーは、各行に対してタイムスタンプを計算する式であり、 TTLマージが実行される時点と比較されます。この機能により、ユーザーは行の粒度でアクションを制御できますが、すべての行が指定された条件を満たすかどうかを確認し、全体のパーツに対してアクションを実行するのが十分とされます。考えられるアクションには、1. パーツを別のボリュームに移動(例:より安価で遅いストレージ)する、2. パーツを再圧縮する(例:より重いコーデックを使用)、3. パーツを削除する、4. ロールアップ(つまり、行をグルーピングキーおよび集約関数を使用して集約する)があります。
例として、Listing 1.のログテーブル定義を考えます。ClickHouseは、タイムスタンプ列の値が1週間以上前のパーツを遅いが安価なS3オブジェクトストレージに移動します。
Listing 1: 1週間後にパーツをオブジェクトストレージに移動。
3.4 Updates and Deletes
MergeTree*テーブルエンジンの設計は、パンのみのワークロードを優遇しますが、一部の使用例では、たまに既存データを変更する必要があります(例えば、規制遵守のため)。更新または削除データに対する2つのアプローチがあり、どちらも並行挿入をブロックしません。
変異は、テーブルのすべてのパーツをその場で書き換えます。テーブル(削除)またはカラム(更新)が一時的にサイズを2倍にするのを防ぐために、この操作は非原子的であり、並行的なSELECTステートメントは変異したパーツと未変異のパーツを読み取る可能性があります。変異は、操作の終わりにデータが物理的に変更されることを保証します。しかし、削除変異は依然として高価であり、すべてのパーツ内のすべてのカラムを書き換えます。
代わりに、軽量削除は、行が削除されたかどうかを示す内部ビットマップカラムのみを更新します。ClickHouseは、削除された行を結果から除外するために、SELECTクエリに追加のフィルターをビットマップカラムに追加します。削除された行は、指定されていない未来の時点での通常のマージによってのみ物理的に削除されます。列の数に応じて、軽量削除は変異よりもはるかに高速になる可能性がありますが、SELECTは遅くなります。
同じテーブルに対して行われる更新と削除操作は、論理的な競合を避けるためにまれで直列化されることが期待されます。
3.5 Idempotent Inserts
実際に頻繁に発生する問題は、クライアントがデータをテーブルに挿入するためにサーバーに送信した後に接続タイムアウトをどのように処理すべきかということです。この場合、クライアントはデータが正常に挿入されたのかどうかを区別するのが難しくなります。この問題は、クライアントからサーバーへデータを再送信し、主キーまたは一意性制約に依存して重複した挿入を拒否することによって伝統的に解決されます。データベースは、バイナリツリー [39, 68]、ラジックスツリー [45]、またはハッシュテーブル [29] に基づくインデックス構造を迅速に使用して、必要なポイントルックアップを実行します。これらのデータ構造はすべてのトゥプルをインデックスしているため、大規模データセットと高い取り込み率に対して、そのスペースと更新のオーバーヘッドは高くなります。
ClickHouseは、各挿入が最終的にパーツを作成するという事実に基づいたより軽量な代替手段を提供します。具体的には、サーバーは最後に挿入されたN個のパーツ(例:N=100)のハッシュを保持し、既知のハッシュを持つパーツの再挿入を無視します。複製されていないテーブルと複製テーブルのハッシュは、それぞれKeeperにローカルに保存されます。その結果、挿入は冪等になります。つまり、クライアントはタイムアウト後に同じバッチの行を再送信し、サーバーが重複排除に対応していると仮定できます。重複除去プロセスのより良い制御のために、クライアントはオプションでパートハッシュとして機能する挿入トークンを提供できます。ハッシュベースの重複除去は新しい行をハッシュするに伴うオーバーヘッドを伴いますが、ハッシュを保存して比較するコストは無視できるものです。