> I don't understand is why his data structure for finding the least-recently-used item wasn't just a linked list Because he is not talking about expiring the

> I don't understand is why his data structure for finding the least-recently-used item wasn't just a linked list Because he is not talking about expiring the Least Recently Used item, but to expire the items whose "cache time" has expired. That is, when you add a new item to the cache, you add it with some lifetime (e.g.: an integer). Then you have some clock (another integer) and what Varnish wants to do is expire all items whose lifetime is lower than the current clock. With a (doubly-)linked list you would have to traverse the list on insertion to place the item in the correct spot...