Great question! I will try to answer this one without too much implementation details. First of all, cache items can be evicted and are not durable, which is

Great question! I will try to answer this one without too much implementation details. First of all, cache items can be evicted and are not durable, which is just a fact. But that doesn't mean we can't track progress (in terms of "time" or "logical time"/"order" in distributed system terms). The social graph is sharded (not surprisingly). We can keep progress of each cache host per shard, which is just a map kept in memory, which doesn't get evicted. I hope this answers your question.