Correct way to delete elements from a ConcurrentDictionary with a predicate

I have written a caching wrapper class for ConcurrentDictionary. Basically it has a timer that checks if items are expired and removes them. Since ConcurrentDictionary does not have RemoveAll method that takes a predicate as a parameter, it has to decide which ones are expired first, then remove them. The problem is an item can be unexpired (it may have sliding expiration and it is accessed) before it is removed. I have to do something to make sure my code is correct.

Here's the current implementation:

private void CheckExpiredItems(object sender, ElapsedEventArgs e)
{
    _timer.Stop();
    IEnumerable expiredItemKeys = _cachedItems.Where(item => item.Value.IsExpired)
                                                    .Select(item => item.Key)
                                                    .ToList();

    foreach (TKey expiredItemKey in expiredItemKeys)
    {
        ICacheItem expiredItem;
        if (_cachedItems.TryRemove(expiredItemKey, out expiredItem))
        {
            if (expiredItem.IsExpired)
            {
                expiredItem.Expire();
            }
            else
            {
                _cachedItems.TryAdd(expiredItemKey, expiredItem);
            }
        }
    }
    _timer.Start();
}

It removes the expired items one by one while checking they are still expired. If it is not expired, it is added back only if there isn't a new item with the same key. However I'm still not sure if this code is correct. I would appreciate a few suggestions. If you want to take a look at the rest, it is on GitHub.

I know it's not a direct answer to your question, but I'm trying to get to the roots of the problem rather than giving correct answer to issue caused by potential misuse...

In your code what you are actually trying to do is to write a cache with time-based expiration of items. Even though ConcurrentDictionary is thread-safe, it's not quite appropriate structure for frequent element scans like you do. Moreover, in your code you remove items, then add them back in case when they have been updated in the middle. It causes side effects for other threads that may try to read the value in-between.

Correct solution would be to use a proper data structure. If by any chance you are using .NET 4.0 or later .NET has already provided you with proper solution - MemoryCache class, otherwise I would recommend creating a lock-based class that maintains 2 indexes for entries - a Dictionary for storing key-value pairs, and a SortedList for storing expiration timestamp-key mapping. In this case you'll always know upfront when the next expiration will happen so timer can be set to specific TimeSpan, and you don't have to scan through all cache entries to find expired ones.

StackExchange Code Review Q#26488, answer score: 9