Store number of uses and last used timestamp for each entry.
This has a performance overhead of around 5-7% but it allows us to identify and delete least recently or most seldomly used entries.