Back
+35 XP
Concept

Module 40 Capstone: Memory-Bounded Priority Task Queue

Ingestion queues must schedule urgent work while strictly capping memory footprint. The Bounded Priority Task Queue combines min-heap ordering with set-based deduplication and capacity bounds. When saturated, it either sheds low-priority incoming work or evicts the least urgent pending task 🧠⛰️🏆.

python
import heapq

class PriorityBuffer:
    def __init__(self, limit=2):
        self.limit = limit
        self.q = []

    def push(self, prio, name):
        if len(self.q) < self.limit:
            heapq.heappush(self.q, (prio, name))
            return True
        return False

buf = PriorityBuffer(2)
buf.push(1, "health_check")
print("Enqueued:", buf.q)

# 30. Module 40 Capstone: Memory-Bounded Priority Task Queue Allowing queues to grow without memory bounds is the single most common vulnerability in asynchronous job processors like Celery or background worker pools. A sudden surge of 1,000,000 requests fills memory, triggers garbage collection pauses, and crashes the entire backend 🛑. ```python # The Bounded Priority Invariant: # Urgency Metric: Lower Number = Higher Urgency (1 = Emergency, 100 = Low) # # Heap at Capacity (size = 3): # [(1, "charge_card"), (5, "ship_item"), (20, "analytics_ping")] # # Incoming: (50, "newsletter_email") -> 50 > 20 -> REJECT IMMEDIATELY (Load Shedding!) # Incoming: (2, "fraud_check") -> 2 < 20 -> EVICT (20, "analytics_ping"), ADMIT (2, "fraud_check")! ``` ### The Architectural Blueprint 1. **O(1) Deduplication Set**: Maintain an in-memory set of active task IDs to prevent re-enqueueing duplicate requests during network retries. 2. **Priority Inversion Defense**: Always ensure the most critical customer-facing transactions jump straight to the front of the line. 3. **Hard Memory Ceilings**: Never exceed `capacity`. Saturated servers must shed low-value work before system performance collapses 🧠⛰️🏆! --- ### Interactive Pop-Quiz 🧠 #### Why must a production task queue enforce a hard capacity limit in memory rather than letting the heap grow indefinitely? - [ ] Unbounded queues consume RAM during traffic spikes, eventually triggering Linux OOM process termination and dropping all tasks 🛑 - [ ] Because heapq cannot store more than 100 elements - [ ] Because Python integers overflow after 1,000 pushes - [ ] Operating systems automatically throttle CPU speed on large heaps --- ### Practical Challenge 🎯 Implement `BoundedPriorityQueue(capacity: int)` with `push(priority: int, task_id: str) -> bool` and `pop() -> tuple[int, str]`. Reject duplicate `task_id` values. When capacity is reached, only accept an incoming task if its urgency (`priority`, where lower number = higher urgency) outranks the worst task currently in the heap (evicting the worst task); otherwise reject it. Verify admissions, rejections, and pop ordering. Print results. <details> <summary>Solution</summary> ```python import heapq class BoundedPriorityQueue: def __init__(self, capacity: int): self.capacity = capacity self.heap = [] self.task_ids = set() def push(self, priority: int, task_id: str) -> bool: if task_id in self.task_ids: return False if len(self.heap) >= self.capacity: worst_idx = max(range(len(self.heap)), key=lambda i: self.heap[i][0]) worst_prio, worst_id = self.heap[worst_idx] if priority < worst_prio: self.task_ids.remove(worst_id) self.heap[worst_idx] = (priority, task_id) self.task_ids.add(task_id) heapq.heapify(self.heap) return True return False heapq.heappush(self.heap, (priority, task_id)) self.task_ids.add(task_id) return True def pop(self) -> tuple[int, str]: if not self.heap: raise IndexError("Empty queue") prio, tid = heapq.heappop(self.heap) self.task_ids.remove(tid) return prio, tid def size(self) -> int: return len(self.heap) bpq = BoundedPriorityQueue(capacity=3) assert bpq.push(10, "job_medium") is True assert bpq.push(20, "job_low") is True assert bpq.push(5, "job_high") is True assert bpq.size() == 3 # Reject lower urgency assert bpq.push(30, "job_junk") is False # Admit higher urgency (1 outranks 20) assert bpq.push(1, "job_critical") is True assert bpq.size() == 3 order = [bpq.pop() for _ in range(3)] assert order == [(1, "job_critical"), (5, "job_high"), (10, "job_medium")] print(f"BoundedPriorityQueue verified: {order}") ``` </details>

Checkpoint

Why must a production task queue enforce a hard capacity limit in memory rather than letting the heap grow indefinitely? 🧠

Practice

Implement `BoundedPriorityQueue(capacity: int)` with `push(priority: int, task_id: str) -> bool` and `pop() -> tuple[int, str]`. Reject duplicate `task_id` values. When capacity is reached, only accept an incoming task if its urgency (`priority`, where lower number = higher urgency) outranks the worst task currently in the heap (evicting the worst task); otherwise reject it. Verify admissions, rejections, and pop ordering. Print results. 🎯

Terminal
01
Tap code blocks below to assemble
Available Blocks