Introduction
The .NET generic Dictionary collection class has a unique key constraint. Consider you want to store 'Author Name' and 'Articles' in the generic Dictionary collection class. First, when you add "Bob", "Article_Good_One", the item gets added to the Dictionary. When you add "Bob", "Article_Good_Second", you will get an exception. This is because of the unique key constraint of the Dictionary class. The Dictionary class refuses to accept the same key Bob again, as it requires the keys to be unique.
The Dictionary class is designed for high performance searches. When you want such high performance searches with the ability to add multiple values for the same key, the MultiMap collection class described below can be used. This MultiMap collection class is type safe, thread safe, and thread aware. This also supports enumerating the collection in one thread while another thread modifies the collection!
We all know the emphasis on concurrent programming as linear processor speed growth is limited (or has stopped) in the past years. Parallel programming is a hot topic. A concurrent collection is a collection that can be safely used (enumerated, added, deleted, modified) across multiple threads. This MultiMap is one such concurrent collection.
How would you like to read?
It is best to read the article sequentially. However, not everyone is in the same situation. So here is a brief guideline to get what you are looking for quickly:
- (0) If you are looking for a plain MultiMap with *no* multi threading or concurrency capability, click the link: MultiKeyDictionary.
- (1) If you are curious - why concurrent enumeration is desirable, read 'Reference 1' or section 'Applied Multi-Map'.
- (2) If you are a geek and just would like to know the different concurrency problems addressed, jump to the section 'Addressing Concurrency concerns'.
- (3) If you have read Part I of this article and are wondering what's new, then please scroll down to the 'Points of interest' section.
What is a MultiMap collection?
The desire to add more than one value for a key is the basis for the MultiMap collection. However, this is also a concurrent collection. The picture below gives a brief overview of a MultiMap collection.
Above said in mind, MultiMap is a type safe, thread-safe, thread-aware generic collection class in C#.
Motivating sample: Simply speaking, MultiMap is required to overcome the below limitation of the Dictionary collection class:
static void Main(string[] args)
{
Dictionary<string, string> PersonData =
new Dictionary<string, string>();
PersonData.Add("Alice", "Home: 123-456-7890");
PersonData.Add("Alice", "Home: 456-123-8099");
}
Using the code
Here are the steps to follow before using the collection class:
Step 1: In Visual Studio 2005 or 2008, right click 'References' in Solution Explorer.
Step 2: Click 'Add Reference' and browse to MultiMap.dll downloaded from the above link (the first line of this article).
Now, let's see how to use the code.
- Use-case 1: How to declare and add elements to this collection class:
static void Main(string[] args)
using System;
using BK.Util;
namespace ConsoleTest
{
class Program
{
static void Main(string[] args)
{
MultimapBK<string, string> multiMapCollection =
new MultimapBK<string, string>();
multiMapCollection.Add("Alice", "Home: 333-222-9999");
multiMapCollection.Add("Alice", "Office: 222-211-9999");
multiMapCollection.Add("Alice", "Cell: 111-112-9999");
}
}
}
The first line creates a new collection object. Lines 2, 3, and 4 add elements to this collection. Note that the Key (Alice) is the same in all the three additions.
- Use-case 2: How to read elements back from this collection class:
using BK.Util;
using System;
using BK.Util;
namespace ConsoleTest
{
class Program
{
static void Main(string[] args)
{
MultimapBK<string, string> multiMapCollection =
new MultimapBK<string, string>();
multiMapCollection.Add("Alice", "Home: 333-222-9999");
multiMapCollection.Add("Alice", "Office: 222-211-9999");
multiMapCollection.Add("Alice", "Cell: 111-112-9999");
MultimapBK<string, string>.MultimapEnum enumMultiMapItems =
multiMapCollection.GetEnumerator();
while (enumMultiMapItems.MoveNext())
{
while (enumMultiMapItems.Current.Value.MoveNext())
{
System.Console.WriteLine("Key = {0}; Value = {1}",
enumMultiMapItems.Current.Key,
enumMultiMapItems.Current.Value.Current);
}
}
}
}
}
Lines 1, 2, 3, 4 create and initialize the collection. Line 5 gets the enumerator to enumerate through each element in the collection. Line 7, again. uses MoveNext() to read each value for the specified Key (Alice).
- Use-case 3: How to quickly search-locate an individual item from the collection and display all the values:
using System;
using BK.Util;
namespace ConsoleTest
{
class Program
{
static void Main(string[] args)
{
MultimapBK<string, string> multiMapCollection =
new MultimapBK<string, string>();
multiMapCollection.Add("Alice", "Home: 333-222-9999");
multiMapCollection.Add("Alice", "Office: 222-211-9999");
multiMapCollection.Add("Bob", "Home: 111-112-9999");
multiMapCollection.Add("Bob", "Office: 121-112-9999");
string SearchKey = "Bob";
string ValueRet = multiMapCollection.GetFirstItem(SearchKey);
while (ValueRet != null)
{
System.Console.WriteLine("Key = {0}; Value = {1}", SearchKey, ValueRet);
ValueRet = multiMapCollection.GetNextItem(SearchKey);
}
}
}
}
Code explanation inline.
Applied Multi-Map
MultiMap has been used in the below projects:
- (0) COMET based Grid control for ASP.NET web apps - Click here.
- (1) Multi-client COMET Grid control for ASP.NET web apps - Click here.
Explanation of the MultiMap collection design
If you are just planning to use this collection class, you may skip this section. However, if you are curious to look at how this class was designed, you may continue reading further.
The internal data structure used:
The basic data structure inside the MultiMap collection class is:
As stated in the above picture, Dictionary<Key, List<Value>> is the data structure that holds multiple values for the same key.
Threading scenario 1:
As always, the collection class is locked for addition, modification, and deletion for thread safety. This creates a minor (probably in micro seconds) overhead, but gives great flexibility to the users of this class. Hence, the users of this collection class need not worry about thread safety, synchronization etc.
Consider a thread (Thread 1) reading values of the 5th Key (element) of this collection. Now, another thread (Thread 2) removes this from the collection. The next read by (Thread 1) should return null. This is achieved by locking the internal data structure.
Threading scenario 2:
The next scenario is Thread Awareness. Consider two different threads enumerating the same key, which has 100 values as shown in the picture below:
Now, consider 'Thread 1' reads 5 values for Key_5 when 'Thread 2' is instantiated to read the same Key. Now, the next call to the MultiMap's GetCurrentItem method needs to know which value to return, i.e., the 6th value (for Thread 1) or the 0th value (for Thread 2). To determine this, MultiMap stores Thread Details in a separate collection. It retrieves this value to understand what was read last by which thread. Using this Thread Details, the MultiMap collection will be able to return the right item for the right thread. Multiple threads executing the code below will yield the right results:
while (enumDict.MoveNext())
{
System.Console.WriteLine("Key = {0}, Value = {1}",
enumDict.Current.Key, enumDict.Current.Value.First);
}
while (enumDict.MoveNext())
{
if (enumDict.Current.Key == 10)
{
myDict.DeleteAll(enumDict.Current.Key);
}
}
Threading scenario 3:
The next step is to achieve Thread Safety in enumeration.
Consider the scenario in which, Thread 1 uses the MoveNext() method to get Current. Meanwhile, Thread 2 removes the current item pointed to by Thread 1. If this scenario is not handled, we will see a funny NullReferenceException screen in Thread 1. The basic idea is, when Thread 1 calls the MoveNext() method, it owns Current. However, when Thread 2 attempts to delete 'Thread 1's Current', there are two choices presented to Thread 2. Choice 1: Thread 2 can either 'Blocking Call Delete', where the call will return only when Thread 1 releases from MoveNext and moves to the next item. Choice 2: Thread 2 can call a 'Non-blocking-Delete', where the call will return immediately, but the item will be marked for deletion. When Thread 1 moves away from the marked item, this item will be deleted safely from the collection.
Let us leave the other concurrency scenarios for brevity. However, the major concurrency issues handled are listed in the next section.
Addressing Concurrency concerns
Discussing all the concurrency issues handled will make the article very lengthy. However, it is useful to list the concurrency issues that are handled:
- Multiple threads updating (or adding items to) the
MultiMap collection at the same instance? Items are added in the order they are received. - Enumerators passed across different threads. I.e., an enumerator created by one thread, but passed on to be used by another thread? Allowed. Even though more than one thread share the same instance of enumerator, each thread will get its correct
next_item [on MoveNext()] and Current. - One thread removes an item from the collection, while another thread enumerating/reading the same item? Allowed. The remove will take effect once the thread reading the element steers away [by
MoveNext(), or thread_abort or thread_close]. However, the interesting part is, when the thread that removes the item enumerates again [through Reset()], it will *not* see the deleted item. This applies to any thread other than the thread that was reading the element at the instance of deletion. - Multiple threads removing the same item from the collection? If no other thread is currently accessing that element, it will be safely removed.
- One thread removing an item, while another thread adding the same item? Depends on which one gets the lock first. However, the result is same.
- One thread accesses an item and terminates. After some time, another thread attempts to remove the same item? Item will be removed.
- One thread removes an item, while another thread reading the item. And, a third thread attempts to enumerate over the same item? This item will *not* be visible for the third thread.
- Why not expose
Count (the number of elements) in the API? To avoid bad coding as listed in 'Reference 2'.
Why thread-safe enumeration is useful
Consider we have a UI that displays the values from a Dictionary collection . For this collection to have agile (or more recent) values, we have a thread updating this collection. Now, the user presses Refresh. Follow the events in the below picture based on sequence numbers marked in red color. The result is an InvalidOperationException thrown by the Dictionary collection enumerator.
Let's solve this exception in the Dictionary collection by locking the: 'enumeration' and 'update' operations. Consider the situation where the user presses the Refresh button in the UI while a background update is already going on. The UI will hang. This behavior is undesirable.
Now consider the same scenario using a MultiMap collection. The 'UI thread' refresh and the 'Update thread' are executed concurrently. The picture below explains this:
The code below is a sample for reproducing the exception in the Dictionary collection while the MultiMap collection performs this operation smoothly.
Let us write a code in which one thread adds values to the collection Dictionary<key,value>, while the other thread reads/enumerates it:
using System;
using System.Collections.Generic;
using BK.Util;
namespace TestThreadOnCollection
{
class Program
{
static Dictionary<string,> myDict = new Dictionary<string,>();
static object lockObj = new object();
public static void ThreadProc1()
{
int Counter = 0;
while (true)
{
lock (lockObj)
{
myDict.Add(Counter.ToString(), "Just Value");
}
Counter++;
}
}
public static void ThreadProc()
{
Dictionary<string,>.Enumerator enumDict = myDict.GetEnumerator();
while (true)
{
lock (lockObj)
{
enumDict = myDict.GetEnumerator();
}
while (enumDict.MoveNext())
{
System.Console.WriteLine("Key = {0}, Value = {1}",
enumDict.Current.Key, enumDict.Current.Value);
}
System.Console.WriteLine(" ------ End of List --------");
System.Console.ReadLine();
}
}
static void Main(string[] args)
{
System.Threading.Thread th1 =
new System.Threading.Thread(new System.Threading.ThreadStart(ThreadProc));
th1.Start();
System.Threading.Thread th2 =
new System.Threading.Thread(new System.Threading.ThreadStart(ThreadProc1));
th2.Start();
}
}
}
Output: (crushhhh!!) Invalid Operation Exception: {"Collection was modified; enumeration operation may not execute."}
By providing a built-in mechanism for thread-safety, this problem is solved elegantly with less code as below, using the MultiMap collection:
using System;
using System.Collections.Generic;
using BK.Util;
namespace TestThreadOnCollection
{
class Program
{
static MultimapBK<string,> myDict = new MultimapBK<string,>();
public static void ThreadProc1()
{
int Counter = 0;
while (true)
{
myDict.Add(Counter.ToString(), "Just Value");
Counter++;
}
}
public static void ThreadProc()
{
MultimapBK<string,>.MultimapEnum enumDict = myDict.GetEnumerator();
while (true)
{
enumDict.Reset();
while (enumDict.MoveNext())
{
System.Console.WriteLine("Key = {0}, Value = {1}",
enumDict.Current.Key, enumDict.Current.Value.First);
}
System.Console.WriteLine(" ------ End of List --------");
System.Console.ReadLine();
}
}
static void Main(string[] args)
{
System.Threading.Thread th1 =
new System.Threading.Thread(new System.Threading.ThreadStart(ThreadProc));
th1.Start();
System.Threading.Thread th2 =
new System.Threading.Thread(new System.Threading.ThreadStart(ThreadProc1));
th2.Start();
}
}
}
Output:
Key = 1, Value = Just Value
Key = 2, Value = Just Value
Key = 3, Value = Just Value
Key = 4, Value = Just Value
Key = 5, Value = Just Value
Key = 6, Value = Just Value
Key = 7, Value = Just Value
Key = 8, Value = Just Value
Key = 9, Value = Just Value
Key = 10, Value = Just Value
Key = 11, Value = Just Value
.. And both the threads continue well-married.
Since the reading and writing in the MultiMap is of Order(1), we do not need to worry much about the method of lock used. We will just see microseconds advantage in using other locks.
What is the difference
What is the difference between using a locked Dictionary collection and a MultiMap generic collection?
- Multi-thread enumerable:
What does this mean? Normally, enumerators cannot be used in one thread while another thread updates the same collection. The MultiMap collection supports such operations. Independent threads can update, modify, and enumerate the MultiMap collection. To know why such operations can be useful, read the section: ‘Why thread-safe enumeration is useful’ below.
- Thread aware enumerator:
What does this mean? Consider using a Dictionary collection in a WCF service. Typically, multiple threads may serve multiple sessions. In this case, the Dictionary collection needs to be wrapped by a thread-aware class to handle race conditions.
- Disposable (supports
IDisposable) What does this mean? In case you store un-managed resources in a MultiMap, it supports disposing the stored objects through a single call. Wouldn’t you be happy to write multiMapObject.Dispose(), instead of enumerating each item in the collection to call Dispose?
Points of interest
What is new in Part II:
- Thread-aware: This means, multiple thread(s)/session(s) can add, modify, delete, enumerate contents of the same instance of a
Dictionary collection object. - Supports
IDisposable: In case you are storing unmanaged resources in a MultiMap collection class, you can dispose it easily with one Dispose call. - Supports
IEnumerable: You can enumerate the contents of this collection like any standard .NET collection type. And this is thread-safe. i.e., one thread can enumerate while another thread adds content to the collection. - Can be used both in Web and Windows app projects.
Important reminder!
I would like to hear from you guys on your feedback. I would love to hear your detailed feedback, even if you rate 1 or below. So, please do write your messages. Thanks!
References
History
- 9th March 2009 - First version.
- 13th March 2009 - Added pictures, modified code.
- 16th March 2009 - Added link for plain-vanilla
MultiMap.
