Concurrent Caching at Google

MapMaker is Google’s premier data structure for in-memory caching on the JVM. This presentation will cover lock amortization as a simpler alternative to techniques such as lock-free and elimination-based data structures. We’ll describe how amortized analysis can be used to avoid lock contention and how it is leveraged to support expiration, soft/weak reference collection, and bounded caches.