Design a prioritized log manager with eviction
Overview
This question evaluates system design and algorithmic competencies in bounded storage management, specifically prioritized eviction, recency-aware ordering, per-file and global capacity accounting, and choosing data structures that meet stated complexity targets.
Design a Log Store with Priority- and Recency-Aware Eviction
Context
You are designing an in-memory (or on-disk) log storage component. Each inserted log belongs to a file (fileId) and has a priority and a timestamp. Storage is bounded by a global capacity and optional per-file capacities. When capacity is exceeded, the system must automatically evict the "least important" logs first. Importance is defined by priority (higher = more important) and recency (newer = more important).
Requirements
-
Global capacity: The total number of stored log records across all files must not exceed
total_max. -
Automatic eviction:
addLog(fileId, record, priority, timestamp)must automatically evict when limits are exceeded. -
Eviction policy: When eviction is required, delete the least important records first. Importance considers:
- Priority (higher is more important), and
- Recency (newer is more important).
-
Limits: Support both per-file limits (optional
limit[fileId] = X) and a global limittotal_max. -
APIs and complexity targets:
- Provide APIs to add logs, query by file, and observe capacities.
- Target complexities: O(1) (or amortized O(1)) to identify a deletion candidate and O(log n) or better per insertion/eviction.
Deliverable
Describe your data model, data structures, eviction policy, algorithms, and trade-offs that meet the above requirements and complexities.
Solution
Login required