質問とそれが適用される場面
すべてのキーに値と有効期限が設定されているインメモリキャッシュを実装してください。getは期限切れの値を絶対に返してはなりません。クロック、境界、クリーンアップ、容量、並行性、および計算量について説明してください。
Amazonは、ソフトウェア開発面接のトピックとしてデータ構造、アルゴリズム、コーディングを挙げており、知識の応用を重視しています。Redisは、残存有効期間や精度を含むTTLおよびEXPIREセマンティクスを文書化しています。LRUやLFUとは異なり、この問題は時間セマンティクスと有効期限のクリーンアップを中心としています。
面接官が見ているポイント
面接官は、明示的なTTL単位とクロック、正しい有効期限の境界、クリーンアップの選択、並行整合性、容量に関する動作、そして時間計算量と空間計算量を評価します。
回答前に確認すべき質問
- TTLは秒単位ですか、それともミリ秒単位ですか？0は即座に期限切れになりますか？
- クロックは単調増加（monotonic）ですか？
- 期限切れのエントリは即座に削除する必要がありますか？
- 最大容量やLRUポリシーはありますか？
- set、get、クリーンアップはどのように同期されますか？
- キーの更新によってTTLはリセットされますか？
- 永続化やプロセス間共有は必要ですか？
- クリーンアップ処理の作業量は制限（バウンド）される必要がありますか？
30秒の回答フレームワーク
「各キーの値と絶対的なexpiresAtをハッシュテーブルに保存します。getはまず単調クロックをチェックし、nowがexpiresAt以降である場合は削除してミス（miss）を返します。setは値とTTLを置き換えます。基本バージョンは遅延クリーンアップを使用し、償却計算量O(1)のgetとO(n)の空間計算量を持ちます。アクセス頻度の低いコールドエントリには、最小ヒープ（min-heap）または制限付きスキャンで対処します。ロックまたはシャーディングによってハッシュテーブルとクリーンアップの更新を保護します。テストではTTL 0、境界の一致、更新（refresh）、競合状態をカバーします。」
詳細な回答（ステップ・バイ・ステップ）
ステップ1：アイテムを定義する
valueとexpiresAtを保存します。TTLが無限になることはありません。すべてのパスでnow >= expiresAtという1つのルールを使用します。
ステップ2：getとsetを実装する
getはキーが存在しない場合にミスを返します。期限切れのキーの場合、ミスを返す前に削除を行います。setは絶対有効期限を計算し、クリーンアップ用のインデックスを更新します。
ステップ3：クロックを選択する
経過時間には単調クロックを使用し、ウォールクロック（壁時計時刻）の調整によってTTLが延長されないようにします。永続化やプロセス間の設計では、明示的な時間基準と精度が必要です。
ステップ4：クリーンアップ方式を選択する
遅延クリーンアップはシンプルですが、コールドキーがメモリを消費する可能性があります。最小ヒープは最も早い有効期限を先に取り出します。定期的なスキャンは作業量を制限しますが、削除が遅延する可能性があります。
| 戦略 | メリット | コスト |
|---|---|---|
| 遅延（Lazy） | シンプルで高速な読み取り | コールドキーが残る |
| 最小ヒープ（Min-heap） | 最も早い有効期限を優先 | 更新によってヒープ内に古いエントリが発生する |
| 定期スキャン | 1パスあたりの作業量が制限される | 削除が遅延する |
ステップ5：更新の並行安全性を確保する
set、get、delete、クリーンアップは、同じ値と有効期限で合意している必要があります。グローバルロック、読み取り/書き込みロック、またはシャードロックを使用します。ヒープとテーブルの更新は同時にアトミックである必要があります。
ステップ6：容量とTTLを分離する
TTLは容量を定義しません。上限に達した場合、LRU、ランダム立ち退き（eviction）、または書き込み拒否のいずれかを選択します。立ち退きは有効期限切れとは別に追跡します。
ステップ7：計算量と擬似コードを述べる
コアとなる境界条件は次のとおりです：
get(key):
item = table[key]
if item is absent: return MISS
if clock.now() >= item.expiresAt:
delete table[key]
return MISS
return item.value遅延getおよびsetは償却O(1)、空間計算量はO(n)です。ヒープクリーンアップの取り出しはO(log n)のコストがかかります。
ステップ8：境界条件をテストする
TTL 0、境界の一致、リフレッシュ、繰り返しのクリーンアップ、クロックの変更、並行get/set、容量による立ち退き、障害注入をテストします。テストではsleepを使用するのではなく、クロックを注入します。
高品質な回答例
「CacheItem(value, expiresAt)を定義し、ハッシュテーブルにアイテムを保存します。setはTTLを絶対有効期限に変換します。0は即座に期限切れであることを意味します。getは単調クロックをチェックし、ミスを返す前に削除を実行します。
最初のバージョンでは遅延クリーンアップを使用し、読み取りと書き込みを償却O(1)で行います。コールドキーが多い場合は、最小ヒープを追加します。各ヒープレコードにはバージョンを持たせ、クリーンアップ時に削除前にバージョンを検証することで、古いレコードが更新された値を削除しないようにします。シャードロックによってテーブルとヒープを保護します。テストでは境界の一致、リフレッシュ、繰り返しのクリーンアップ、競合、容量による立ち退きをカバーします。」
よくある間違い
- TTL 0や等しい場合の境界条件を未定義のままにする。
- 経過TTLにウォールクロック時間を使用する。
- バックグラウンドワーカーが実行されるまで、getが期限切れの値を返すことを許してしまう。
- リフレッシュ後の古いヒープレコードを無視する。
- TTLをLRU容量ポリシーとして扱う。
- 時間のかかるクリーンアップ中にグローバルロックを保持し続ける。
- 境界の競合状態をテストせず、ヒットとミスのみをテストする。
- 精度と計算量の説明を省略する。
フォローアップ質問と回答方法
フォローアップ1：なぜ絶対有効期限を使用するのですか？
比較ルールが1つで済み、クリーンアップ時にエントリを有効期限順に並べることができるからです。リフレッシュ時はexpiresAtを置き換えます。
フォローアップ2：ウォールクロックが逆戻りした場合はどうなりますか？
経過時間には単調クロックを使用します。永続的または分散キャッシュには、文書化された時間基準が必要です。
フォローアップ3：バックグラウンドスレッドはないが、コールドキーが多数ある場合は？
読み取りまたは書き込み時に、操作ごとに固定数のヒープ取り出しを行うなど制限付きのクリーンアップを実行し、一定の削除遅延を許容します。
フォローアップ4：ヒープとテーブルの一貫性をどのように維持しますか？
1つのロックまたはアトミックな操作を使用し、ヒープレコードにバージョンを持たせます。バージョンが一致している場合にのみ削除します。
フォローアップ5：容量に達した場合はどうなりますか？
まず期限切れのエントリを削除し、次に生存しているエントリに対して文書化された立ち退きポリシーを適用し、その理由を追跡します。
フォローアップ6：複数のプロセスで共有するにはどうすればよいですか？
インメモリキャッシュは単一プロセス用です。プロセス間での使用には、アトミックなTTL、クロック、および障害セマンティクスを備えた外部または分散ストアが必要です。