私は、アイテムがセットの一部である確率が非常に低いために最適化されたセットデータ構造を探しています。非常に低い確率で確率的に設定する
ユースケースはGnip/Twitter準拠のFirehoseで、毎秒約1,000件のイベントが発生します（これはTwitter全体からの削除です）。私たちはテーブルを持っています。記憶されたつぶやき（毎年その量だけ増えています）が1,000万と言いましょう。そして、アイテムが消防士に現れたら削除する必要があります。私は10万秒ごとにマッチがあると推測しています。
私はブルームフィルターを考えていましたが、おそらくいくつかはチェーンされていましたが、ヒットする可能性は非常に低いので、常にチェーン全体を通過する必要があります。
これに適したサブラインデータ構造はありますか？
問題は表示されません。ブルームフィルタをチェックしてツイートが保存されていることがわかったら、データストアのツイートを調べます。それがあれば削除します。それがなければ、あなたはそれを削除しません。
保存されたつぶやきは1,000万件あり、年間約1,000万回の増加が予想されます。したがって、ブルームフィルタを構築して、10億の容量を持ち、偽陽性の確率は0.1％になります。 Bloomfilter calculatorによれば、それには1.67ギガバイトがかかります。
「偽陽性」の数字は、フィルタに10億のキーが含まれていることを前提としています。フィルタの分布が非常に少ない場合、誤検出の可能性ははるかに低くなります。
1秒間に数千のつぶやきがあり、Bloomフィルタの偽陽性率が0.1％の場合、最悪の場合、1秒当たり1つの偽陽性の平均が得られます。だから1秒に1回、コードがデータベースにヒットして、そのツイートがあるかどうかを判断する必要があります。
しかし、それになるまでには長年かかるでしょう。既存のレコード数はわずか1,000万で、年間成長率は1千万であり、フィルターが10％も満杯になる10年前です。フィルタサイズを5億（860 MB）に落とした可能性もありますが、偽陽性のため大ヒットにはならないでしょう。
私は確率をあまり詳しく見ていない。それはバニラブルームフィルターのように聞こえるかもしれない。私はちょうど、「不可能な」ケースのために設計された別のデータ構造があるかどうか確認するつもりだと思った。あなたの答えをありがとう、私はそれを試してみましょう。 – Joe
Bloomフィルタは、メモリに収まると仮定して、細かくなければなりません。メモリに完全に収まらない場合は、this paperに記載されているソリューションの使用を検討してください。
さらに、少し余分なパフォーマンスを絞りたい場合はCuckoo Filterを使用できますが、オープンソースの実装を見つけるのは難しくなります。ここにはGoのものが1つあります。
ハッシュテーブルを使ってみましたか？ – TilmannZ
ハッシュテーブルのサイズは線形に増加しますが、これは避けようとしています。 – Joe