Production Monitoring

A Bloom filter that is overloaded does not crash and does not log an error. It keeps answering, only with more false positives, until every lookup is a MAYBE and the expensive check behind it runs on every request. After this lesson your program reports a filter's health the way an operator needs it: how full it is, how many keys it really holds, what error rate it should have, what error rate it actually has, and whether to rebuild.

Four cheap signals

1. load = n_added / capacity. It is the fraction of the planned n that has been used. Above 1.0 the filter was sized for the wrong n. It counts every ADD, so duplicates inflate it.
2. fill = bits set / m. At the optimal k and exactly the planned n, the fill is about 0.5 (that is what the optimal k means). Clearly above that, the filter is past its design point. Fill ignores duplicates, because adding a key twice sets no new bits.
3. theoretical FP = (1 - e^(-k*n_added/m))^k, the formula from the false-positive lesson at the number of adds so far.
4. actual FP, measured: periodically look up keys you know were never added (use a reserved prefix) and count how often the answer is MAYBE. Compare against the target. A hit counts only if the filter wrongly said MAYBE.

Fill also gives a count that is immune to duplicates. Solving fill = 1 - e^(-k*n/m) for n gives

estimated distinct keys = -(m / k) * ln(1 - fill)

(FULL if fill is 1, where the logarithm is undefined). If n_added is far above the estimate, callers are re-adding the same keys.

A worked example

A filter sized for 50 keys at 0.02: m = 408, k = 6. As keys are added (and 400 never-added keys are probed each time):

Fill passes about 0.5 right at capacity. Past capacity the error rate climbs fast: the theoretical rate here is 0.4965 at 150 adds, many times the target.

A health rule

A filter is healthy when load <= 1.0 and, once at least 10 probes have run, actual FP <= 2 * target. Otherwise report DEGRADED with the reasons: OVER_CAPACITY when the load is above 1.0, FP_TOO_HIGH when there are at least 10 probes and the measured rate is more than twice the target. Fewer than 10 probes is too little data to judge a rate, so it never triggers FP_TOO_HIGH. Even with 10 or more probes the measured rate is noisy, which is why the rule allows a factor of 2 before it complains.

When and how to rebuild

• Load above 1.0: schedule a rebuild at a larger n during quiet hours.
• Measured FP above target at normal load: suspect the hash (skewed or adversarial keys) and switch to a stronger or keyed one.
• Rebuild without downtime: keep two filters, write to both, and swap reads once the new one is warm; or version the filters and let readers prefer the newest. A scalable filter avoids rebuilds at the price of memory.

Common mistakes

• Counting a probe as a hit when the filter says NO. A hit is a MAYBE for a key that was never added.
• Dividing by zero in ACTUAL_FP before any probe; the answer is 0.0000.
• Judging the rate on fewer than 10 probes.
• Treating n_added as the number of distinct keys. Duplicates raise load but not fill.
• Using >= where the rule says >: a filter loaded to exactly its capacity is healthy.

Your exercise

The starter creates the filter and handles ADD. You implement PROBE, the five gauges (LOAD, FILL, ACTUAL_FP, THEORETICAL_FP, ESTIMATE) and HEALTHY.