WriteGuards: Distributed Storage Support for Strongly Consistent Caches

This paper presents a set of in-process and remote distributed caches for datacenter environments, CLINK and CRINK respectively, that provide linearizable reads entirely from memory without contacting storage. These caches remain loosely coupled to the storage layer and achieve high performance, scale, and availability by cooperating with auto-sharders and by tracking consistency metadata at the granularity of key ranges rather than individual keys. To our knowledge, CLINK is the first distributed linked cache that delivers scalable, linearizable reads from memory while remaining loosely coupled with storage.

At the heart of these caches is a lightweight storage primitive called WriteGuards that can be easily added to a distributed store. WriteGuards prevent a subtle race we call the delayed-writes anomaly arising during changes in ownership of key ranges. Each write carries a small fencing value tied to the current owner, and the storage system checks this value to reject delayed writes. WriteGuards apply to key ranges instead of individual keys for scalability, add only a conditional check on the write path, and require no coordination on reads.

We implemented our cache designs on TiDB. The inprocess cache CLINK cuts tail read latency by three orders of magnitude, and the remote cache CRINK reduces it by 2.2 -2.4× relative to direct storage access and existing strongly consistent remote caches.