0

この方法で、有効期限付きのデータを保存するプロセスを作成したいと考えています (有効期限データの形式は変更できます: タイムスタンプ、日付オブジェクト、タイムデルタなど) 。

タイマーを使用して、有効期限が切れたデータを定期的にデポップしたいと考えています。

有効期限のある何千もの要素を取得した場合、迅速な挿入、発見、および削除を行うには、どのようなデータ構造を使用すればよいでしょうか?

私の最初の考えは、UTC タイムスタンプとheapqueueを使用することです。パフォーマンスはかなり良いですが、それでも O(log(n)) であるため、アイテムの数とともに増加します。

これらの操作を O(1) で提供するために、redis / memcache は何をしますか?

4

2 に答える 2

2

基本的に、組み合わせる必要がある 2 つのアプローチがあります - ヒット アンド ミス + すべてのデータのクリーンアップ (「オフライン」の方法で - 要求中ではありません)。

メモリ上で

Memcache は、有効期限が切れたときにキーを削除しません。これは、O(1) 操作時間を保証しながら削除することはできないためです。代わりに、有効期限は、キーが古くなったと見なされるまでの期間を示す方法です。GET が実行されると、Memcache はキーの有効期限がまだ有効かどうかを確認してから返します。

レディス上

Redis キーは、パッシブな方法とアクティブな方法の 2 つの方法で期限切れになります。一部のクライアントがキーにアクセスしようとしたときにキーがアクティブに期限切れになり、キーがタイムアウトになっていることがわかります。もちろん、二度とアクセスされない期限切れのキーがあるため、これでは十分ではありません。とにかく、このキーは期限切れにする必要があるため、Redis は定期的に、有効期限が設定されたキーの中でランダムにいくつかのキーをテストします。すでに期限切れになっているすべてのキーは、キースペースから削除されます。

補足 - 確率論的アプローチ万歳

memcacheredisに関するリファレンスは次のとおりです。

于 2013-02-28T09:14:41.867 に答える
0

有効期限のあるデータを順番に挿入していますか?その場合、ヒープキューは線形キューよりも遅くなり、挿入するのに O(1)、ポップするのに O(1) になります。

于 2013-03-01T02:41:09.207 に答える