Design a Bounded Log Management System with O(1) Victim Selection
Context
You are designing an in-memory log buffer that ingests log entries and must never exceed a configured capacity (total_max). Each log has:
-
id (unique)
-
timestamp (arrival time; assume non-decreasing or we treat arrival time separately from event time)
-
importance (integer; lower means less important)
-
payload (opaque)
When the buffer is full and a new log arrives, the system should automatically evict logs to stay within capacity, preferring to remove the least important logs; ties are broken by oldest timestamp.
Requirements
-
Maintain total number of logs ≤ total_max at all times.
-
On insert, automatically delete logs to make room, preferring:
-
Lowest importance first, and if there’s a tie,
-
Oldest by arrival timestamp.
-
Locate the next log to delete in O(1) time (e.g., via a time-ordered deque and a min-priority heap). Overall update/eviction cost can exceed O(1) due to necessary re-indexing.
Deliverables
-
Describe the core data structures and how they interact.
-
Specify insertion and eviction algorithms and their time/memory complexity.
-
Include assumptions, tie-breaking rules, and handling of out-of-order timestamps.
-
Provide concise pseudocode for key operations.