Disk Quota Enforcer & Eviction Engine
Local disk caches and temporary upload buffers quickly consume available filesystem capacity without strict quota controls. A quota enforcer tracks total allocated bytes across files, evicting least-recently-used (LRU) files to maintain a safe headroom target when thresholds are breached.
# LRU file eviction:
while current_bytes + new_file_bytes > max_quota:
oldest_file = min(files.values(), key=lambda f: f.atime)
os.remove(oldest_file.path)
# Disk Quota Enforcer & Eviction Engine When building an image-resizing proxy, CDN cache, or temporary report generator, saving files to disk without an active eviction loop will crash your machine the moment a traffic spike fills the drive. 🛑💾 A **Quota Eviction Engine** continuously manages capacity: 1. Tracks each cached file's size and access timestamp (`atime`). 2. When inserting a new file would push total usage over `max_bytes`, don't just evict 1 file (which would cause eviction thrashing on the very next request!). 3. Evict the **Least Recently Used (LRU)** files until total disk usage drops down to a comfortable **target headroom** (e.g. 80% of `max_bytes`), ensuring multiple subsequent writes can proceed without immediately triggering eviction again. ```python # Evicting until target headroom: target_bytes = int(max_bytes * 0.8) while current_usage + incoming_size > max_bytes and store: lru_key = min(store, key=lambda k: store[k]["atime"]) current_usage -= store[lru_key]["size"] del store[lru_key] ``` ## Pop Quiz Why should an eviction engine evict down to a target headroom (e.g. 80% capacity) rather than evicting just enough for the current write? - [ ] It avoids thrashing the eviction routine on every single subsequent write under high concurrency. - [ ] The Linux kernel only updates file access times when free space exceeds 20%. - [ ] Operating systems refuse to delete files unless at least 15% of inode space is cleared. - [ ] To allow SSD flash translation layers to execute garbage collection in real time. ## Real-World Challenge Implement `QuotaEvictionEngine(max_bytes: int, target_free_ratio: float = 0.2)`: - `put(name: str, data: bytes)`: Saves file. If capacity is exceeded, evict LRU entries until usage is $\le \text{max\_bytes} \times (1 - \text{target\_free\_ratio})$. - `get(name: str) -> bytes`: Returns data and updates access timestamp. Raises `KeyError` if absent. - `current_usage -> int`: Returns current total stored bytes. <details> <summary>Solution</summary> ```python import time class QuotaEvictionEngine: def __init__(self, max_bytes: int, target_free_ratio: float = 0.2): self.max_bytes = max_bytes self.target_threshold = int(max_bytes * (1.0 - target_free_ratio)) self._store = {} # name -> {"size": int, "data": bytes, "atime": float} self._current_bytes = 0 @property def current_usage(self) -> int: return self._current_bytes def put(self, name: str, data: bytes): size = len(data) if size > self.max_bytes: raise ValueError(f"File size {size} exceeds total maximum quota {self.max_bytes}") # If updating existing entry, subtract its previous size if name in self._store: self._current_bytes -= self._store[name]["size"] # Evict LRU entries until enough headroom is cleared while (self._current_bytes + size > self.max_bytes) and self._store: # Find entry with lowest access timestamp lru_key = min(self._store.keys(), key=lambda k: self._store[k]["atime"]) self._current_bytes -= self._store[lru_key]["size"] del self._store[lru_key] self._store[name] = { "size": size, "data": bytes(data), "atime": time.time() } self._current_bytes += size def get(self, name: str) -> bytes: if name not in self._store: raise KeyError(f"File '{name}' not found") self._store[name]["atime"] = time.time() return self._store[name]["data"] # Verification engine = QuotaEvictionEngine(max_bytes=100, target_free_ratio=0.2) # Insert 3 files of 30 bytes each (Total: 90 <= 100) engine.put("doc_A", b"A" * 30) time.sleep(0.001) engine.put("doc_B", b"B" * 30) time.sleep(0.001) engine.put("doc_C", b"C" * 30) assert engine.current_usage == 90 # Touch doc_A to make doc_B the oldest engine.get("doc_A") time.sleep(0.001) # Adding doc_D (30 bytes): 90 + 30 = 120 > 100 -> evicts doc_B (the LRU entry) engine.put("doc_D", b"D" * 30) assert "doc_B" not in engine._store assert "doc_A" in engine._store assert "doc_C" in engine._store assert "doc_D" in engine._store ``` </details>