A system performing client-side caching of data in a deduplication backup system by maintaining an Adaptive Replacement Cache (ARC) to pre-populate cached data and flush incrementals of the cached data in a client coupled to a backup server in the system. The system maintains cache consistency among clients by a time-to-live (TTL) measurement associated with each entry in a respective client cache, and a retry on stale entry mechanism to signal from the server when a cache entry is stale in a client due to change of a corresponding cache entry in another client. The ARC cache keeps track of both frequently used and recently used pages, and a recent eviction history for both the frequently used and recently used pages.