Version-based cache invalidation
TLDR: Our redis-cache is currently relying on active invalidation via DEL calls. This creates consistency issues during failover, and complicates scaling strategies. A version-based approach could provide better consistency guarantees and give us more options to scale.
Background
Our redis-cache is running at a high level of utilization. During bursts we often hit saturation (e.g. production#928 (closed), https://gitlab.com/gitlab-com/gl-infra/infrastructure/-/issues/9420).
There have been several proposals around scaling redis: &80, scalability#49, https://gitlab.com/gitlab-com/gl-infra/infrastructure/-/issues/9414.
One concern that came up around stale reads via read replicas (gitlab-org/gitlab!26801 (closed)) is regarding consistency. For many keys, we currently expect reads from the cache to be consistent and do not tolerate stale reads.
This already can cause issues after a redis failover. Since replication is asynchronous, we have no guarantee that a write was replicated. After a failover, we will quite likely get some stale reads.
It also makes scaling more difficult, because many scaling approaches may exhibit stale reads.
The main goal of this proposal is to increase our tolerance for stale reads in the caching layer, in order to give us more options for scaling.
Scaling
There are several directions we could take for scaling redis (&80).
Strategies include: functional partitioning (gitlab-org/gitlab-foss#64141 (moved)), consistent hashing ("distributed redis"), read replicas, clustering ("redis cluster").
For consistent hashing (scalability#49), we would get stale reads during resharding (when adding a new instance to the cluster).
For read replicas (https://gitlab.com/gitlab-com/gl-infra/infrastructure/-/issues/9414), we would get stale reads all the time.
Functional partitioning and clustering (via redis cluster) avoid such stale reads most of the time, but may still exhibit them during a failover or a network partition.
Version-based invalidation
The way we currently invalidate many caches is through active invalidation. This works by issuing a DEL command on the key we want to refresh.
There is another strategy that we could consider though: version-based invalidation.
This works by designating a non-cached resource to hold the current version. Every cache key related to that resource will then include the latest version.
Rails supports this via cache_key_with_version. By default, calling cache_key on any ActiveRecord object will return a string that contains the model name, the id, and updated_at. For exmple projects/102-20200326115637567901.
Whenever the parent resource changes, so does the cache key. Caches can be invalidated by bumping updated_at -- e.g. via ActiveRecord's touch method. That will change the cache key, and thus any following cache lookup will get (or populate) the new value.
This makes cache keys effectively immutable. Old keys can still be actively deleted, but it is also possible to let them be evicted by redis.
The main constraint for this approach is that there must be some non-cached resource that holds the current version. This uncached resource needs to be fetched every time before cache lookups can be made.
A concrete example
One of the main residents in the cache is RepositoryCache. It caches data from gitaly in redis, on a per-repo basis.
The keys look like this:
cache:gitlab:has_visible_content?:<repo-path>:<project-id>By including the project's updated_at column, it would look something like this:
cache:gitlab:has_visible_content?:<repo-path>:<project-id>:<updated_at>If we had a per-repository checksum of the root refs (essentially git for-each-ref | sha1sum, exposed via gitaly, possibly stored in postgres), we could invalidate only when the repo content changes.
cache:gitlab:has_visible_content?:<repo-path>:<project-id>:<repo-checksum>That checksum would need to be fetched uncached every time.
Challenges
The main cost here is that the resource holding the version must be uncached. For example, if we wanted to use this strategy for the RepositoryCache, we would need at least one uncached call to postgres or gitaly (depending on where we want to store the version). This could be too expensive with our current access patterns. Though chances are we're already going to the DB in most cases.
Another issue is that such a "parent" resource may not exist in all cases. We need to ensure that all actively invalidated keys have such a resource that can hold the version.
Another potential issue is reduced cache effectiveness and increased eviction pressure. Especially if we no longer actively delete keys, it might take a while for them to get evicted, in the mean time they occupy space in the cache.
Benefits
The main benefit is that this eliminates stale reads and other consistency issues.
With this approach, we no longer get stale reads after a redis failover. It also unlocks more scaling strategies, including consistent hashing and read replicas.
There may be additional challenges implement this on the application side, but I think it's definitely worth evaluating, as it would reduce the consistency requirements on our caching layer greatly.
Thanks to @robotmay for proposing this same idea during https://gitlab.com/gitlab-com/gl-infra/infrastructure/-/issues/9420.
cc @msmiley @andrewn @stanhu @jarv @engwan @ahmadsherif @mwasilewski-gitlab