この方法で、有効期限付きのデータを保存するプロセスを作成したいと考えています (有効期限データの形式は変更できます: タイムスタンプ、日付オブジェクト、タイムデルタなど) 。
タイマーを使用して、有効期限が切れたデータを定期的にデポップしたいと考えています。
有効期限のある何千もの要素を取得した場合、迅速な挿入、発見、および削除を行うには、どのようなデータ構造を使用すればよいでしょうか?
私の最初の考えは、UTC タイムスタンプとheapqueueを使用することです。パフォーマンスはかなり良いですが、それでも O(log(n)) であるため、アイテムの数とともに増加します。
これらの操作を O(1) で提供するために、redis / memcache は何をしますか?
基本的に、組み合わせる必要がある 2 つのアプローチがあります - ヒット アンド ミス + すべてのデータのクリーンアップ (「オフライン」の方法で - 要求中ではありません)。
メモリ上で
Memcache は、有効期限が切れたときにキーを削除しません。これは、O(1) 操作時間を保証しながら削除することはできないためです。代わりに、有効期限は、キーが古くなったと見なされるまでの期間を示す方法です。GET が実行されると、Memcache はキーの有効期限がまだ有効かどうかを確認してから返します。
レディス上
Redis キーは、パッシブな方法とアクティブな方法の 2 つの方法で期限切れになります。一部のクライアントがキーにアクセスしようとしたときにキーがアクティブに期限切れになり、キーがタイムアウトになっていることがわかります。もちろん、二度とアクセスされない期限切れのキーがあるため、これでは十分ではありません。とにかく、このキーは期限切れにする必要があるため、Redis は定期的に、有効期限が設定されたキーの中でランダムにいくつかのキーをテストします。すでに期限切れになっているすべてのキーは、キースペースから削除されます。
補足 - 確率論的アプローチ万歳
有効期限のあるデータを順番に挿入していますか？その場合、ヒープキューは線形キューよりも遅くなり、挿入するのに O(1)、ポップするのに O(1) になります。