reduce bucket tail latency with 2 map rotation - #101
Conversation
Sorry, something went wrong.
| b.mu.RLock() | ||
| s.EntriesCount += uint64(len(b.m)) | ||
| entriesCount := len(b.m) + len(b.mPrev) - b.mPrevEntriesMask | ||
| s.EntriesCount += uint64(entriesCount) |
There was a problem hiding this comment.
With this change, len(b.m) + len(b.mPrev) - b.mPrevEntriesMask becomes more like a "proxy" to the actual entry count with some level of over estimation. This is because len(b.mPrev) may contain entries that have been overwritten by the entries in the b.m, but the keys in the b.mPrev may not be removed.
The alternative is to iterate through the map to get an accurate count, but that will be detrimental to the performance when UpdateStats is called.
Open to feedback on this.
Sorry, something went wrong.
| b.gen++ | ||
| } | ||
| needClean = true | ||
| b.mPrev = b.m |
There was a problem hiding this comment.
this is the main change to address the tail latency:
in the Set(), we don't mark needClean and call cleanLocked() later on - because cleanLocked() is heavy. Instead, we swap the map and we are done. This means during the Get() calls we need to check both maps for a key's presence.
Sorry, something went wrong.
| if (gen+1 == bGen || gen == maxGen && bGen == 1) && idx >= bIdx || gen == bGen && idx < bIdx { | ||
| bmNew[k] = v | ||
| } | ||
| bmPrev := b.mPrev |
There was a problem hiding this comment.
a summary of the change in the cleanLocked()
- iterate through b.m and b.mPrev, find out the total no. of live items.
- create a new map with capacity equals to #1.
- iterate through b.m and b.mPrev, fill up the map created in #2 with live items items from these 2 maps.
- set b.m to the new map.
Sorry, something went wrong.
Summary
Replace synchronous hash-map cleanup during bucket generation update (when chunks are full) with 2 rotating maps to improve the tail latency.
Previously, Set called cleanLocked whenever a bucket’s chunks are full. cleanLocked scanned the bucket index, allocated a replacement map, and copied the live entries while holding the write lock. The resulting pause scaled with the no. of entries in the bucket. It blocked both reads and writes to that bucket. This caused bad tail latency for read requests, especially when the no. of entries is high.
The proposed implementation maintains 2 maps:
When the chunk ring wraps at gen+1, the maps rotate in O(1):
This removes the full-map scan and reconstruction from the Set hot path (in other words, Set need not to call cleanLocked anymore, we only need cleanLocked before Save). In the benchmark below, average new-gen write latency decreases from 3ms ms to 258 ns - this is over 10,000x lower.
The trade-off is that Get may need to check two maps - m then mPrev - when an entry is not found in m. This may result in slightly higher read latency. Based on the benchmark below, which shows the write latency of the same generation, we can proxy that the read-latency degradation is less than 15%.
Benchmark
Apple M4 Max
Go 1.24.13.
Benchmark run prior to this change
Benchmark run with this change