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<TKey> expiredItemKeys = _cachedItems.Where(item => item.Value.IsExpired)
.Select(item => item.Key)
.ToList();

foreach (TKey expiredItemKey in expiredItemKeys)
{
ICacheItem<TValue> expiredItem;
if (_cachedItems.TryRemove(expiredItemKey, out expiredItem))
{
if (expiredItem.IsExpired)
{
expiredItem.Expire();
}
else
{
}
}
}
_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.

• At current time, you not need create separate key expiration storage, because ConcurrentDictionary enumerator is safe to use concurrently with reads and writes to the dictionary. – ZOXEXIVO Jul 31 '18 at 14:05
• There is a small problem in maintaining one indexing with timestamp-key mapping with SortedList. There is a high probability that 2 or more items can get added at the same time-fraction & it would end up in only adding 1 and skipping the others (as sorted list will not allow duplicate key). – HishHash Aug 22 '18 at 16:09
• In the comment marked as Answer "recommended maintaining 2 indexes for entries - a Dictionary for storing key-value pairs, and a SortedList for storing expiration timestamp-key mapping. SortedList<DateTime, ActualKey>" If 2 Items are added at the same time with the exact milliseconds, then only one Time would get added to the TimeStamp sorted list. How can this be solved? – HishHash Aug 22 '18 at 20:27
• As I mentioned in the response, you should use locks to avoid concurrent modifications. The behaviour of the SortedList during concurrent modifications is not defined (docs.microsoft.com/en-us/dotnet/api/…). But my solution with 2 indexes is only relevant if you're on .NET 3.5 or earlier, which I hope is not the case. – almaz Aug 23 '18 at 17:08
• @almaz, below is how my add method looks like. "timeKeyCollection" is the SortedList. In the main program when I try to add elements in an for-loop (1000 items), it throws an exception saying that an Element with the same Key already exists. public void Add(T1 key, T2 value) { this.collection.TryAdd(key, value); lock (syncRoot) { timeKeyCollection.Add(DateTime.Now, key); } } To avoid this, I added a sleep interval to avoid this exception. Now when I simulate insertion of 1000 numbers it take more time & the increase is also quite significant & not acceptable. – HishHash Aug 24 '18 at 19:04

First of all I'd suggest to remove expired business-logic from UI event handler (looks like CheckExpiredItems method belongs to some UI class).

If you are focusing on some concurrent logic you can create your own collection class, having inner member of ConcurrentDictionary type. Then you can explicitly implement RemoveExpiredItems method and create unit-tests or even integration tests, covering the desired functionality (for example you can emulate mult-threaded environment and check if your collection removes only expired items and correctly restores unexpired ones).

I just had to do something similar today. Take a look at this.

If your ICacheItem<TValue> can have value semantics then you can just use the approach above to do something similar to this:

foreach (var p in collection)
{
if (p.Value.Expired())
{
if (!collection.TryRemove(p))
{
log.Debug("Did not remove item because it was changed.");
}
}
}


Indeed in my tests the log message was printed from time to time. Note that the value semantics are important. I overrode Equals for my class.

protected by Malachi♦Aug 24 '18 at 21:35

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).