いくつかの特定の要件を備えた単純なキャッシュ構造が必要です(Pythonで、しかしそれは実際には問題ではありません):
- 最大数百万の小さなオブジェクト (平均で 100 バイト)
- 速度が鍵です (プットと取得の両方)。操作時間は約数マイクロ秒であると予想されます
- これにアクセスするスレッドは 1 つだけです。したがって、すべてをメモリ内に置くことができます (永続性は必要ありません)。
- キーは MD5 ハッシュです (重要な場合)
- 有効期限があり、キャッシュにはグローバルです。すべてのキーは、最初に配置された時間から数えて、有効期限後にキャッシュから削除する必要があります
さて、ポイントは有効期限を実装する方法です-他のすべては単純な辞書を使用して実行できるためです。最も単純な解決策 - すべてのデータを定期的に反復し、期限切れのキーを削除する - は、キャッシュ全体を長時間ロックする可能性があります。クリーンアップ プロセスごとにデータの一部を反復処理することで改善される可能性がありますが、それでも時間がかかります (または十分な速さでクリーンアップされません)。また、キーを 1 つずつ削除するのは CPU の浪費のように見えます。バッチで削除できるためです (有効期限が切れた直後に削除する必要はありません。期限切れのキーをもう少し長く保持するために、余分な RAM を用意できます)。
取得中にキーをチェックするだけでは十分ではありません (ただし、有効期限が切れたキーを返さないようにするために行う必要があります)。
その問題に対するほとんどの回答はmemcachedを使用することを提案していますが、特に参照によって辞書に入れることができるオブジェクトを保持しているため、これはCPUの浪費になると思いますが、memcachedを使用すると、それらを(逆)シリアル化する必要があります。
これを実装する方法についていくつかのアイデアがあります: データをタイム スライスに分割し、実際には複数の辞書を持ちます。たとえば、有効期限が 60 秒の場合、(最大で) 4 つの辞書があり、20 秒ごとに新しい辞書が追加されます。キーが配置され、4 番目のキーが削除されます。ここでは、60 秒以上前にキーが追加されます。これにより、検索時間が 1 つではなく 4 つの辞書で検索する必要がありますが、クリーニングが非常に高速になります (また、RAM の使用量が 33% 増加しました)。
最後に質問です。より良い解決策はありますか? それとも、私が間違っていて、言及された解決策 (キーを 1 つずつ削除する) のいくつかがより良く、より高速になるのでしょうか? 車輪の再発明はしたくありませんが、ネットで良い解決策が見つかりませんでした。