I am not familiar with the Go code, but in the Java version (Caffeine) this is handled by a per-entry state machine. The entry is written to the Map first and the policy work buffered for replaying. If the replay occurs out-of-order (e.g. context switch before appending causing removal=>add), then the entry's state guards against policy corruption. This may not be necessary in their case due to using a sampling policy and other differences.