> Consider a Redis-based cache: For future proofing you could introduce a sharding scheme that deterministically allocates keys based on cluster size. That would be operationally pretty complex. Not to mention also introduce complexity in edge case scenarios (e.g. your cluster size is transitioning).

This is implemented in Twemproxy and resizing the cluster is a known edge case for which Twitter developed Nighthawk (centralized shard placement).