liveBook · Manning

Probabilistic increment

As explained in The Coder Cafe

Probabilistic increment is an approximate counting technique that randomly samples increment operations and compensates sampled updates with a larger increment.

A popular post can turn its like counter into a hot database row: many requests try to update the same counter, creating contention and slowing writes. Probabilistic increment reduces those writes by accepting an approximate count instead of recording every like individually. section 6.11.1

Choose a number N. For each like, update the counter by N with probability 1/N; otherwise, make no database update. Each request contributes one like on average, but only 1/N requests issue the SQL update. The stored count can differ from the true count at any moment. section 6.11.1 section 6.15

One write in ten

With N = 10, each like has a one-in-ten chance of adding 10 to the counter. Across 100 likes, the expected increase is 100, not a guaranteed increase of 100. The benefit is fewer writes to the contested row. section 6.11.1 section 6.15

// /like/{post_id} handler
function like(postID string) {
  if randomInt(N) == 0 {
    increment(postID, N)
  }
}

The request-handler sketch shows the decision point: draw a random number, and issue an increment of N only when the draw selects the request. section 6.11.1

Use this trade-off where approximate counts are acceptable, especially for popular posts. A quiet post may display an odd count because a single sampled update adds N at once. Choose N carefully; it can increase with the current like count as a post becomes more popular. Larger savings in writes come with less precision in the displayed count. section 6.11.1

How The Coder Cafe covers it

How deep it goes
Works through a SQL-backed like counter and randomized handler, then discusses choosing N; does not quantify error bounds.
Examples
Uses a post's likes table, a SQL counter update, and a request handler that writes only when randomly selected.
What it assumes
Assumes basic familiarity with SQL updates and request handlers while illustrating the sampling rule through a like counter.
What you can do after
Apply it via a sampled SQL update to reduce hot-row writes when an approximate like count is acceptable.
How it connects
Connects randomized algorithms with hot rows, database contention, approximate counting, and latency management in distributed systems.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of The Coder Cafe. The section links point to the parts of the book it draws on.