# jzhao.xyz


.
\_.
/


# Idempotence

Last updated May 5, 2022

How do we avoid cases where losing an ACK could lead to users doing an action multiple times (e.g. pressing the like button)?

Idempotence!

$f$ is idempotent if $f(x) = f(f(x))$

For example

• Not idempotent: $f(likeCount) = likeCount + 1$
• Idempotent: $f(likeSet) = likeSet \cup {userID}$

Idempotent requests can be retried without deduplication.

However, this isn’t perfect when there are other actors/actions that intermix. For example, $f(f(x))= f(x)$ but $f(g(f(x))) \neq g(x)$ (e.g. liking, unliking, then liking is not the same as unliking!)

To somewhat fix this, use tombstones and record logical timestamp for when events happen

• Then, we can reconcile replicas by propagating the record with the latest timestamp and discard the records with earlier timestamps
• Then, to fix concurrent writes by different clients
• Last writer wins (LWW): resolve conflicts using a logical clock that gives total ordering (e.g. Lamport clock)
• Multi-value register (give all options to let user/algorithm above resolve it): use a Vector clock, $v_2$ replaces $v_1$ if $t_2 > t_1$; preserve both ${v_1, v_2}$ if $t_1 \parallel t_2$