Redisの重複排除の3つの手法のまとめ

前文

この記事では、ユニークなカウントを達成するためにRedisの3つの方法を紹介し、この記事では、SETに基づいて、ビットに基づいて、HyperLogLogに基づいて3つの方法を説明し、友人のニーズは、以下を参照してくださいすることができます。

ユニークカウントは、Webシステムにおいて非常に一般的な機能であり、例えば、1日あたりのユニークビジター数（またはUV数）をカウントする必要があるWebサイトなどが挙げられます。このカウント問題は一般的ですが、解決は非常に複雑になります。第一に、必要なカウントの量が大きくなること、例えば大規模サイトでは一日に数百万の訪問者があり、これはかなり大量のデータです。第二に、カウントの次元を拡張することが望ましいことが多く、例えば一日の UV に加えて、週や月の UV を知ることが必要で、これは計算を非常に複雑にしています。

リレーショナルデータベースに格納されたシステムでは、ユニークカウントを実現する方法はselect count(distinct <item_id>) で、これは非常にシンプルだが、この文はデータが多い場合、実行に非常に時間がかかる。リレーショナルデータベースのもう一つの問題は、データの挿入もあまりパフォーマンスが高くないということです。

Redisはこの種のカウントの問題をうまく解決し、リレーショナル・データベースより高速で消費リソースも少なく、さらに3種類の方法を提供しています。

1. セットベース

Redisのセットは、一意なデータのセットを保存したり、ある要素がセット内に存在するかどうかを素早く判断したり、セット内の要素数を素早く数えたり、セットを新しいセットにマージしたりするために使用されます。関係するコマンドは次のとおりです。

コピーコード コードは以下の通りです。

SISMEMBER key member # Determine if member exists
SADD key member # Add member to the collection
SCARD key # Get the number of elements in the collection 

セットベースのアプローチは、シンプルで効率的、正確で適用範囲が広く、理解しやすいのですが、リソース消費量が多く（もちろんリレーショナルデータベースよりは少ない）、要素数が多い場合（例えば数億個）には恐ろしいほどのメモリを消費するという欠点があります。

2. ビットベース

Redisのビットは、要素の存在情報をビット1または0によって保存するセットメモリと比較して、高度に圧縮されたカウントを実現することができます。 例えば、あるWebサイトのユニークビジターをカウントするには、ビットのオフセットとしてuser_idを使い、それを1にセットして訪問を示し、1MBの容量を使って、800万以上のユーザーからの1日分の訪問を保存することが可能です。関係するコマンドは以下の通りです。

コピーコード コードは以下の通りです。

SETBIT key offset value # Set the bit information
GETBIT key offset # Get bit information
BITCOUNT key [start end] # Count
BITOP operation destkey key [key ...]  # Bitmap merge 

ビットベースのアプローチは、setよりもはるかに少ないスペースで済みますが、要素をビットオフセットに単純にマッピングする必要があり、より狭くなります。また、消費するスペースは最大オフセットに依存し、カウント値とは無関係で、最大オフセットが大きい場合は、大きなスペースが必要になることがあります。

3. HyperLogLogをベースとした

非常に大量のデータに対して正確なユニークカウントを実現するのは難しいが、近似値であれば計算科学には多くの効率的なアルゴリズムがあり、その中でもHyperLogLog Countingは、わずか12k程度のメモリで数億のユニークカウントを実現し、誤差は1％程度と非常に有名なものである。関係するコマンドは次の通りである。

コピーコード コードは以下の通りです。

PFADD key element [element ...]  # Add element
PFCOUNT key [key ...]   # Count

このカウント方法は本当にすごいもので、私も完全に理解できていないので、興味のある方は関連記事を掘り下げてみてください。

redisが提供する3つのユニークなカウント方法は、それぞれ長所と短所があり、様々な状況でのカウントの要求に適切に応えることができます。

4. ブルームフィルタをベースにしたもの

BloomFilterは、ビットマップのような、あるいはビットセットのようなデータ構造を用いてデータを格納する。ビット配列を用いて集合を簡潔に表現し、ある要素が集合内に既に存在するかどうかを迅速に判断する。BloomFilterの精度は100%ではないが、パラメータの数、使用するハッシュ関数の数、ビット配列の大きさを調整することでエラー率を下げることが可能である。これを調整することでエラー率を0に近づけることができ、ほとんどのシナリオで十分な性能を発揮する。

redisでブルームフィルタを利用するには、以下のプラグインをインストールする必要があります。 redisプラグインbloom-filterのcentosへのインストール

概要

Redisの重複排除の3種類の方法についての説明は以上です。Redisの重複排除の方法については、Script Houseの過去の記事を検索するか、以下の記事を引き続きご覧ください。