You know when you update your data. Therefore, you invalidate your cache when you update your data.

Timestamps help alot if you're paranoid, also.