  Distributed, transactional storage systems scale by sharding data across
servers. However, workload-induced hotspots result in contention, leading to
higher abort rates and performance degradation.
  We present KAIROS, a transactional key-value storage system that leverages
client-side inter-transaction caching and sharded transaction validation to
balance the dynamic load and alleviate workload-induced hotspots in the system.
KAIROS utilizes precise synchronized clocks to implement self-invalidating
leases for cache consistency and avoids the overhead and potential hotspots due
to maintaining sharing lists or sending invalidations.
  Experiments show that inter-transaction caching alone provides 2.35x the
throughput of a baseline system with only intra-transaction caching; adding
sharded validation further improves the throughput by a factor of 3.1 over
baseline. We also show that lease-based caching can operate at a 30% higher
scale while providing 1.46x the throughput of the state-of-the-art explicit
invalidation-based caching.
