Alert Deduplication with Flap Suppression

1. Background Knowledge

In observability systems, alert flapping occurs when an alert rapidly transitions between firing and resolved states due to transient issues, causing notification fatigue. To mitigate this, monitoring systems implement dampening or cooldown mechanisms: after a notification is sent for a specific alert key, subsequent notifications for that same key are suppressed until a configurable time window (cooldown) has elapsed.

This problem models a simplified version of that logic. Each alert is identified by a unique key (e.g., "db", "api"). Events arrive in non-decreasing time order. A notification is triggered only when an alert transitions into the firing state from a non-firing state, and the time since the last notification for that key is at least cooldown seconds. Transitions to resolved never generate notifications, and repeated firing events while already in the firing state are ignored.

The core data structure needed is a per-key state tracker that remembers two things: (1) whether the alert is currently firing, and (2) the timestamp of the last notification sent for that key. This is a classic state machine problem where each key independently tracks its own lifecycle.

2. Algorithm Approach

Use a hash map (dictionary) keyed by alert key, storing a tuple of (current_state, last_notification_time). Process each event sequentially:

• If the event state is resolved, update the key's state to resolved and continue.
• If the event state is firing:
• If the key is not currently firing (i.e., it was resolved or unseen), this is a valid transition into firing. Check whether time - last_notification_time >= cooldown. If yes, increment the notification count and update last_notification_time to the current time. Then set the key's state to firing.
• If the key is already firing, do nothing (no duplicate notification).

This is a single-pass, O(n) streaming algorithm with no need for sorting or complex data structures.

3. Step-by-Step Strategy

1. Initialize an empty dictionary state_map and a counter count = 0.
2. Iterate over each (key, state, time) in events:

• Retrieve the current state and last notification time for key from state_map. Use defaults: state = "resolved", last_notif = -infinity (or a very small number) if the key hasn't been seen.
• If state == "resolved":
• Update state_map[key] to ("resolved", last_notif).
• If state == "firing":
• If the stored state is not "firing" (meaning we are transitioning into firing):
• Check if time - last_notif >= cooldown.
• If the condition holds, increment count and set last_notif = time.
• Update state_map[key] to ("firing", last_notif).

3. Return count.

# Pseudocode sketch
for key, state, time in events:
 cur_state, last_notif = state_map.get(key, ("resolved", float("-inf")))
 if state == "firing" and cur_state != "firing":
 if time - last_notif >= cooldown:
 count += 1
 last_notif = time
 state_map[key] = (state, last_notif)

4. Common Pitfalls

• Forgetting to update state on resolved events: If you skip updating the state when an alert resolves, the next firing event will incorrectly appear as a duplicate and be suppressed.
• **Using > instead of **>=****: The cooldown condition is "at least cooldown seconds have passed," so the comparison must be time - last_notif >= cooldown, not strictly greater than.
• Not handling unseen keys: A key that appears for the first time should be treated as if it was previously resolved with no prior notification. Using a default of float("-inf") for last_notif ensures the first firing always passes the cooldown check.
• Updating last_notif even when no notification is sent: Only update last_notif when a notification is actually sent. If the cooldown hasn't elapsed, the old last_notif must be preserved so that a later event can still trigger a notification.
• Assuming events are strictly increasing in time: The problem states non-decreasing, so multiple events can share the same timestamp. Your logic should handle this naturally since the state transitions are still well-defined.

5. Time & Space Complexity

• Time Complexity: $O(n)$, where $n$ is the number of events. Each event is processed exactly once with $O(1)$ dictionary lookups and updates.
• Space Complexity: $O(k)$, where $k$ is the number of distinct alert keys. In the worst case, every event has a unique key, so $k = n$. The dictionary stores one entry per distinct key.