Performing cache invalidation is disclosed, including: receiving an invalidation request to invalidate one or more invalidated cache entries at a cache storage: determining whether an invalidation pattern included in the invalidation request matches an invalidation pattern associated with an existing invalidation entry of an invalidation data structure; in the event that the invalidation pattern included in the invalidation request matches the invalidation pattern associated with the existing invalidation entry of the invalidation data structure, updating the existing invalidation entry with an invalidation timestamp included in the invalidation request, and in the event that the invalidation pattern included in the invalidation request does not match invalidation patterns associated with existing invalidation entries of the invalidation data structure, generating a new invalidation entry in the invalidation data structure with the invalidation pattern and the invalidation timestamp included in the invalidation request.