A Multi-threaded search engine in C#

Many applications require some sort of search. The information being searched for is usually located in many different locations. Most applications we build might just be searching from one single location, like a database server, but there are times when we need to search information from multiple locations, such as a database server or a file server. However, most of the time, even when the resources are independently and physically separated from each other, we still have to perform the searches one by one in the order in which they are defined in the code. In Windows, it's simply because the languages we are developing the applications in either just lack the capability or are too hard for us to make all the searches start at the same time, and go in parallel. With the simple but sophisticated multithreading model provided by the System.Threading namespace in the .NET Framework, it is now a relatively easy task. We can simply create a thread for each search, start them all at the same time, then have them run in parallel. When the searches are done, we can process their results as each of them return. Multi-threaded programming is a huge topic, full coverage of it is beyond the scope of this article. This article assumes some basic understanding of the concept of it (you can read more about it from the links at the end of the article). We will keep our focus in this article on showing how to apply it in a very practical way.

The search engine

In this article, we are making use of a little search engine that searches information from three separate locations: a database server, a directory server, and the Internet. It's a web based search engine, and the results are displayed on a web page. We will begin by looking at a standard search engine, without threads. Then look at it with threads. Finally, we will be looking at it with both threads and a timeout. The main purpose of this article is only to demonstrate how to feature threads in searching. We will just be using some static values for the search result, and use the Thread.Sleep() method to simulate the time which would normally spent by the real searches. We will have five seconds for searching the Internet, three seconds for the database server and one second for the directory server.

This sample search engine has been developed and tested in Microsoft .NET SDK beta 2.0. All source code can be found in the support code download, as well as some batch files to compile them. It consists of 7 files:

• bin\link.cs, a class definition for a link
• bin\result.cs, a class definition for a result from a search
• bin\linearSearch.cs, a class definition for the linear search engine
• bin\parallelSearch.cs, a class definition for the parallel search engine
• search1.aspx, asp code to call the search method in the linearSearch class
• search2.aspx, asp code to call the search method in the parallelSearch class
• search3.aspx, asp code to call the search method in the parallelSearch class with a timeout.

The search engine that searches in order

Here, we have a C# version of the search that's similar to what we usually see in applications:

The link.cs

using System;

public class link {

private string _name = "";
private string _url = "";

public string name {
get { return _name; }
}

public string url {
get { return _url; }
}

public link(string pName, string pUrl) {
_name = pName;
_url = pUrl;
}
}

It's nothing interesting - just a class that holds a link information, which is just the url and the name.

The result.cs

using System;
using System.Collections; // for ArrayList

public class result {

private string _label = "";
private string _message = "";
private ArrayList _links = new ArrayList();
private bool _isCompleted = false;
private DateTime _started;
private DateTime _done;

public string label {
get { return _label; }
}

public string message {
get { return _message; }
set { _message = value; }
}

public ArrayList links {
get { return _links; }
}

public bool isCompleted {
get { return _isCompleted; }
set {
_isCompleted = value;
_done = DateTime.Now;
}
}

public TimeSpan timeSpent {
get { return _done.Subtract( _started ); }
}

public result(string pLabel) {
_started = DateTime.Now;
_label = pLabel;
}
}

A little more code is going on here, but it's still pretty staight forward. links holds an ArrayList of link objects. The timeSpent is a TimeSpan object. It starts when the result object is created, and ends when isComplete is set.

The linearSearch.cs

using System;
using System.Threading; // for Threading
using System.Collections; // for ArrayList

public class linearSearch {

private ArrayList _results = null;
private string _keyword;
private DateTime _started;
private DateTime _end;

private void addResult(result thisResult) {
_results.Add( thisResult );
}

public TimeSpan totalTime {
get { return _end.Subtract( _started ); }
}

public linearSearch() {}

public ArrayList search(string keyword) {

if ( keyword == null || keyword == "" )
return null;

_started = DateTime.Now;
_keyword = keyword;
_results = new ArrayList();

searchWebSites();
searchDatabases();
searchDirectoryServers();

_end = DateTime.Now;
return _results;
}

private void searchDatabases() {

result r = new result("Result of \"" + _keyword + "\" from the database servers");
try {
// In real world scenarios, you will want to connect to some databases,
// and perform some real searches. But here we just make use of some static values,
// and use the Thread.Sleep() to simulate some delays to make it looks like it's
// actually doing some time consumming work.

// found 3 records from the company's book inventory databases
// simulating a 3 seconds database searches
Thread.Sleep(1000);
r.links.Add( new link("Book - The Tin Princess", "/") );
Thread.Sleep(1000);
r.links.Add( new link("Book - The Tin Woodman of Oz", "/") );
Thread.Sleep(1000);
r.links.Add( new link("Book - The Tin Man", "/") );
r.message = "found: " + r.links.Count;
r.isCompleted = true;

} catch(Exception e) {

r.isCompleted = false;
r.message = "failed";

} finally {
// release database connection resources
// then add the results
// both partial/full result is wanted
addResult(r);
}
}

private void searchDirectoryServers() {

result r = new result("Result of \"" + _keyword + "\" from the directory servers");
try {
// found 2 records from the company's employee directory
// simulating a one second search.
Thread.Sleep(1000);
// "Christine Yakukilu" is in our search result simply
// because there's a "tin" in "Christine"
r.links.Add( new link("Employee - Christine Yakukilu", "/") );
r.links.Add( new link("Employee - Tin Lam", "/") );
r.message = "found: " + r.links.Count;
r.isCompleted = true;

} catch(Exception e) {

r.isCompleted = false;
r.message = "failed";

} finally {
// release directory server connection resources
// then add the results
addResult(r);
}
}

private void searchWebSites() {

result r = new result("Result of \"" + _keyword + "\" from the Web Sites");
try {
// found 4 web sites from the web
// simulating a five seconds site searches.
Thread.Sleep(2000);
r.links.Add( new link("Web Site - Periodic Table of the Elements: Tin", "/") );
Thread.Sleep(1000);
r.links.Add( new link("Web Site - Welcome to Tin Lam's Home Page", "/") );
Thread.Sleep(1000);
r.links.Add( new link("Web Site - eBay Has Great Buys on Tin Toys", "/") );
Thread.Sleep(1000);
r.links.Add( new link("Web Site - Tin Cup: Music From The Motion Picture", "/") );
r.message = "found: " + r.links.Count;
r.isCompleted = true;

} catch(Exception e) {

r.isCompleted = false;
r.message = "failed";

} finally {
// free up connection resources
// then add the results
addResult(r);
}
}
}

Below diagram illustrate how this linearSearch works:

_results is an ArrayList of result objects added from the search methods, as represented by result¹, result² and result³ in the diagram respectively. search¹, search² and search³ represent searchWebSites(), searchDatabases() and searchDirectoryServers() respectively. These three methods do four things:

• Create the result objects, passing the name of the searches to its constructors.
• With Try, we are adding some static values as link objects to the result and using Thread.Sleep() for some delay. In the real world, you will want to initialize and open proper connections to the resources, such a database connections, etc, then process and add the real results from the server to the result object's link property.
• With Catch, we handle any Exceptions thrown from the Try block. Here, we are only setting the isCompleted variable to false, and showing the message saying it has failed. In the real world, you might want to do a little more. Perhaps logging the error messages somewhere, sending an email to report it to someone who's responsible for it, or find some ways to recover from the errors and continue the searches, such as trying the search on some backup servers, etc. You might also want to expand the catch block to include more exception specific catches - maybe some database related exceptions in the searchDatabases(), and some WebRequest and network related exceptions in searchWebSites().
• With Finally, we are releasing and closing all the opened connections to the resources. We then add the result to the _results property.

Since we are also interested in partial search results, we are adding the result object r to _results in the finally block. For instance, if we were to loop through a DataReader and add each row as a link to the links collection, and suddenly an Exception is thrown on the 11th row, then we could still have the first 10 links. But, if we only wanted a complete search result, then we would have called the addResult() at the end of the try block.

The search1.aspx

<%@ Page Language = "C#" %>

<script language="C#" runat="server">

linearSearch s;
ArrayList results;
result r;
link l = null;

protected void Page_Load(object sender, System.EventArgs e) {
s = new linearSearch();
results = s.search("tin");
}

</script>

<html>
<head><title>Linear Search</title></head>
<body>

<% for ( int i = 0; i < results.Count; i ++ ) {
r = (result)results[i]; %>
<b><%= r.label %></b> - <i><%= r.message %></i>
<% for ( int j = 0; j < r.links.Count; j ++ ) {
l = (link)r.links[j]; %>
<li><a href="<%= l.url %>"><%= l.name %></a>
<% } %>
<br>time: <%= r.timeSpent.Seconds %> second(s).
<p>
<% } %>

<hr>
total time: <%= s.totalTime.Seconds %> second(s).

</body>
</html>

ArrayList results = s.search("tin"); - We are creating the linearSearch object right away and calling its search() method, passing in the string "tin". In all the .ASPX files, we are passing in a static string "tin" to the search methods. In the real world, you might want to setup a form in a web page, or in a Windows Form, letting the user type in the keyword to search for. When the search methods are done, we will have an ArrayList of result objects. Then we just simply loop through the ArrayList and display all their links. When you run this page, assuming you have everything setup correctly, you will see something like the following:

As you can see from the diagram and the screen shot, or just by looking at the code, the total time required for this search is 9 seconds. 5 for the web sites, 3 for the database, and 1 for the directory. Consider this though: since the database might be in another server, and the directory is in another server, then what's the point of having the directory search to wait for the database search to finish? Furthermore, the search on the directory server will just take 1 second, so why does it has to wait for 8 seconds until both the two other searches are done? Even thought it's not doing anything in these 8 long seconds? Plus, if there's any problems in the other two methods, like when the database search method is trying to connect to an overloaded database server, then the directory search method will even have to wait for the database search method to wait for the database server!

The search engine that searches in parallel

The search will be a lot more efficient if we can just start all the searches at the same time, and then process the results in a first-come-first-serve manner as they return. Threads can make this happen. Manipulating threads in Windows isn't easy: VB6 and earlier versions lacked threading capability without some 3rd party components and some unstable workarounds; C++ just doesn't usually fit into the learning timeframe and the development schedule; and Java/VJ++ might not be an ideal choice either. The threading model provided in the System.Threading namespace makes threading so much easier, but it is still very powerful. We can create a thread for each search, and start them all at the same time instead of letting them all wait for the preceding searches to return. We can also process the result as each search returns, so whichever search finishes first will get its result processed first, without caring if other searches have finished (or even succeed) or not.

The diagram below illustrates how this parallelSearch works:

The parallelSearch.cs

using System;
using System.Threading; // for Threading
using System.Collections; // for ArrayList

public class parallelSearch {

private ArrayList _results = null;
private string _keyword;
private DateTime _started;
private DateTime _end;

private void addResult(result thisResult) {
lock( _results ) {
_results.Add( thisResult );
}
}

public TimeSpan totalTime {
get { return _end.Subtract( _started ); }
}

public parallelSearch() {}

// for backward compartibility
public ArrayList search(string keyword) {
return search(keyword, 0);
}

public ArrayList search(string keyword, int maxMilliSeconds) {

if ( keyword == null || keyword == "" )
return null;

_started = DateTime.Now;
_keyword = keyword;
_results = new ArrayList();

// creating the threads that wrap the search methods
Thread ps1 = new Thread( new ThreadStart(searchWebSites) );
Thread ps2 = new Thread( new ThreadStart(searchDatabases) );
Thread ps3 = new Thread( new ThreadStart(searchDirectoryServers) );

// calling their Start() to start executing the methods
ps1.Start();
ps2.Start();
ps3.Start();

// if the maxMilliSeconds is greater than 0,
// then we want to do the Join() on the threads with timeout.
if ( maxMilliSeconds > 0 ) {

TimeSpan lDelta;
DateTime lStarted = DateTime.Now;

// waits for the thread to be finished with timeout, or we abort it
if ( !ps3.Join(maxMilliSeconds) )
ps3.Abort();

// work out the remaining time for the 2nd thread
lDelta = DateTime.Now.Subtract( lStarted );
maxMilliSeconds -= lDelta.Seconds * 1000 + lDelta.Milliseconds;
lStarted = DateTime.Now;
maxMilliSeconds = maxMilliSeconds > 0 ? maxMilliSeconds : 0;

// waits for the 2nd thread with the remaining time, or we abort it
if ( !ps2.Join(maxMilliSeconds) )
ps2.Abort();

// work out the remaining time for the 3rd thread
lDelta = DateTime.Now.Subtract( lStarted );
maxMilliSeconds -= lDelta.Seconds * 1000 + lDelta.Milliseconds;
maxMilliSeconds = maxMilliSeconds > 0 ? maxMilliSeconds : 0;

// waits for the 3rd thread with the remain time, or we abort it
if ( !ps1.Join(maxMilliSeconds) )
ps1.Abort();
}

// wait for them to clean up themselve if we aborted them,
// or simply wait infinitely for them to finish if maxMilliSeconds <= 0.
ps1.Join();
ps2.Join();
ps3.Join();

_end = DateTime.Now;
return _results;
}

private void searchDatabases() {

result r = new result("Result of \"" + _keyword + "\" from the database servers");
try {
// In real world scenarios, you will want to connect to some databases,
// and perform some real searches. But here we just make use of some static values,
// and use the Thread.Sleep() to simulate some delays to make it looks like it's
// actually doing some time consumming work.

// found 3 records from the company's book inventory databases
// simulating a 3 seconds database searches
Thread.Sleep(1000);
r.links.Add( new link("Book - The Tin Princess", "/") );
Thread.Sleep(1000);
r.links.Add( new link("Book - The Tin Woodman of Oz", "/") );
Thread.Sleep(1000);
r.links.Add( new link("Book - The Tin Man", "/") );
r.message = "found: " + r.links.Count + " in total";
r.isCompleted = true;

} catch(ThreadAbortException tae) {

r.isCompleted = false;
r.message = "found: " + r.links.Count + " before aborted";

} catch(Exception e) {

r.isCompleted = false;
r.message = "found: " + r.links.Count + " before failed";

} finally {
// release database connection resources
// then add the results
addResult(r);
}
}

private void searchDirectoryServers() {

result r = new result("Result of \"" + _keyword + "\" from the directory servers");
try {
// found 2 records from the company's employee directory
// simulating a one second search.
Thread.Sleep(1000);
r.links.Add( new link("Employee - Christine Yakukilu", "/") );
r.links.Add( new link("Employee - Tin Lam", "/") );
r.message = "found: " + r.links.Count + " in total";
r.isCompleted = true;

} catch(ThreadAbortException tae) {

r.isCompleted = false;
r.message = "found: " + r.links.Count + " before aborted";

} catch(Exception e) {

r.isCompleted = false;
r.message = "found: " + r.links.Count + " before failed";

} finally {
// release directory server connection resources
// then add the results
addResult(r);
}
}

private void searchWebSites() {

result r = new result("Result of \"" + _keyword + "\" from the Web Sites");
try {
// found 4 web sites from the web
// simulating a five seconds site searches.
Thread.Sleep(1000);
r.links.Add( new link("Web Site - Periodic Table of the Elements: Tin", "/") );
Thread.Sleep(1000);
r.links.Add( new link("Web Site - Welcome to Tin Lam's Home Page", "/") );
Thread.Sleep(1000);
r.links.Add( new link("Web Site - eBay Has Great Buys on Tin Toys", "/") );
Thread.Sleep(2000);
r.links.Add( new link("Web Site - Tin Cup: Music From The Motion Picture", "/") );
r.message = "found: " + r.links.Count + " in total";
r.isCompleted = true;

} catch(ThreadAbortException tae) {

r.isCompleted = false;
r.message = "found: " + r.links.Count + " before aborted";

} catch(Exception e) {

r.isCompleted = false;
r.message = "found: " + r.links.Count + " before failed";

} finally {
// free up connection resources
// then add the results
addResult(r);
}
}
}

Everything here is the same as in linearSearch.cs, except for the following:

1. Synchonized access to _result:

lock( _results ) {
_results.Add( thisResult );
}

Since all the search methods are running concurrently, there is a good chance that more than one method will finish their search and attempt to add their result objects to _results. Just like all the Collection classes in the System.Collections namespace, ArrayList is not thread-safe by default. If we just leave it the way it is, as in linearSearch, then when two or more threads are calling their Add() at the same time, we might encounter some problems. The values in _results might be corrupted for example. However, by putting a lock on _results, the .NET runtime will enforce the synchronized access to it for us. That is, the first thread enters the method, and it acquires a lock on _results. When the 2nd thread enters the method, and tries to acquire a lock on _results, the runtime will block it from doing so, and force it to wait until the 1st thread releases the lock. Alternatively, you can make an ArrayList thread-safe with this method in the ArrayList class: public static Arraylist Synchronized(ArrayList list); passing in _results as its argument, and have it returns a thread-safe ArrayList. This method basically put a wrap around an ArrayList object, and make sure all its methods and properties are accessed by no more than one thread at any given time.

2. Creating and starting a thread for each search:

Thread ps1 = new Thread( new ThreadStart(searchWebSites) );
Thread ps2 = new Thread( new ThreadStart(searchDatabases) );
Thread ps3 = new Thread( new ThreadStart(searchDirectoryServers) );

ps1.Start();
ps2.Start();
ps3.Start();

Just as an executable has a Main() as its entry point, a thread has an entry point too. We create the threads by passing their "entry points" to their constructors. These "entry points" are actually some ThreadStart objects. ThreadStart objects are really just some delegate objects, which we can create by passing the methods that we want to be invoked to their constructors. The methods passed to the ThreadStart must not take any parameters, and can not return anything. This is the reason we declared all three search methods as void and not taking any parameters. We then call their Start() to start the execution of the methods. When we call the Start() methods, the runtime will switch the threads to the "Running" state, so the OS can schedule them for execution. Then, when the threads begin executing and invoke the given methods, the methods will be returned. Then the runtime will move on to the next line of code.

3. Aborting the threads:

if ( !ps3.Join(maxMilliSeconds) )
ps3.Abort();

If the maxMilliSeconds value is greater than 0, then that means a timeout is specified, and we would like to abort the threads if they exceed the timeout. We are timing the timeout by first calling the Join() method on one of the threads. The Join() is overloaded with three signatures, and in this case we are using this one: public bool Join(int millisecondsTimeout). It returns true if the thread has finished executing within the millisecondsTimeout period, or false if the thread is still not done after this period. Here, if the thread has finished before the maxMilliSeconds, then we leave it alone, if not, then we call its Abort() to abort it:

lDelta = DateTime.Now.Subtract( lStarted );
maxMilliSeconds -= lDelta.Seconds * 1000 + lDelta.Milliseconds;
lStarted = DateTime.Now;
maxMilliSeconds = maxMilliSeconds > 0 ? maxMilliSeconds : 0;

We are using two local variables lDelta and lStarted to keep track of the time, so that we can calculate how much time we spent waiting for the first thread to finish. The time we can wait for the 2nd thread is the original maxMilliSeconds minus the time we waited for the first thread. Note that the maxMilliSeconds might turn into a negative value. For example, if we spend all 3500 milliseconds waiting for the first thread, the time span of lDelta will be the value of the call to Join(), plus the time that the CPU spends on the other statements. So, if we just take the maxMilliSeconds and minus the milliseconds we get from lDelta, we will get a negative value. So, we set it to 0 if that is the case. Since the threads are all running at the same time, if one of the threads has exceed the maxMilliSeconds period, then that means all the other threads are either already returned, or they have also been running for maxMilliSeconds. So when we call Join(0) on other threads, we expect them to return true right away, or we abort them too. We call Join() first on the 3rd thread, then the 2nd, then the 1st to demonstrate that the calculations do work.

4. Catching the ThreadAbortException:

} catch(ThreadAbortException tae) {

r.isCompleted = false;
r.message = "found: " + r.links.Count + " before aborted";

Now, there has been some inconsistency in the documentation of ThreadAbortException. On the .NET beta 2 documentation, it states that: " The ThreadAbortException is a special exception that is not catchable. " However, in the .NET RC0 documentation it states that: " When this method is invoked on a thread, the system throws a ThreadAbortException in the thread to abort it. ThreadAbortException is a special exception that can be caught by application code, but is re-thrown at the end of the catch block unless ResetAbort is called. " " When this method . " refers to Abort(), so it seems like the RC0 documentation is more exact and more accurate here. The example in this article has clearly shown how we catch this exception. So, when this exception is thrown, the program leaves the try block and enters the catch block to set a property to indicate that the search is not completed, and the message indicates that it's aborted. Lastly, the finally block is executed, and the addResult() is called. In the linearSearch class, we can keep adding links to the links collection until they're all added, or when an exception is thrown. In this parallelSearch class, even if there's no error from the code itself, but it's timed out, the ThreadAbortException will be thrown. However, we will still have the links that have been added to the links collection before the timeout.

5. Waiting for the threads to return:

ps1.Join();
ps2.Join();
ps3.Join();

Here we are using another signature of Thread.Join(): public void Join(). When this method is called on a thread, the calling method (in this case, it's our search()) will indefinitely wait for the thread to finish its execution, because we want to make sure all three threads are totally stopped (either done or aborted) before we return the results. So we call their Join() again. Even if we abort the threads, we still want to wait for them to finish their clean up in the catch and finally block. This way, we can be sure that before we return the method to the caller, not only is the clean up done, but the result objects are all added to _results as well.

The search2.aspx

<%@ Page Language = "C#" %>

<script language="C#" runat="server">

parallelSearch s;
ArrayList results;
result r;
link l = null;

protected void Page_Load(object sender, System.EventArgs e) {
s = new parallelSearch();
results = s.search("tin");
}

</script>

<html>
<head><title>Parallel Search</title></head>
<body>

<% for ( int i = 0; i < results.Count; i ++ ) {
r = (result)results[i]; %>
<b><%= r.label %></b> - <i><%= r.message %></i>
<% for ( int j = 0; j < r.links.Count; j ++ ) {
l = (link)r.links[j]; %>
<li><a href="<%= l.url %>"><%= l.name %></a>
<% } %>
<br>time: <%= r.timeSpent.Seconds %> second(s).
<p>
<% } %>

<hr>
total time: <%= s.totalTime.Seconds %> second(s).

</body>
</html>

Everything is the same as in search1.aspx except that the object s is created with a different class, s = new parallelSearch(). When you run this page, assuming you have everything setup correctly, you will see something like the following:

Now it makes much more sense, the total time for the search should be the around the same time as the longest search, which is 5 seconds by the searchWebSites(). Notice that we still have the exact same results!

The search engine that searches in parallel with timeout

We are able to abort threads, which means that we can abort the searches if they exceed the timeout. Note that we can abort the searches in linearSearch too with some additional timing calculations and conditions checking. But in either case, the searches won't always stop completely at the timeout. It also depends on the processing in the catch and finally block too. But in most cases, the threads will stop almost instantly, and the delay won't be noticeable.

Below diagram illustrate how this parallelSearch with timeout works:

The search3.aspx

<%@ Page Language = "C#" %>

<script language="C#" runat="server">

parallelSearch s;
ArrayList results;
result r;
link l = null;

protected void Page_Load(object sender, System.EventArgs e) {
s = new parallelSearch();
results = s.search("tin", 3500);
}

</script>

<html>
<head><title>Parallel Search with timeout</title></head>
<body>

<% for ( int i = 0; i < results.Count; i ++ ) {
r = (result)results[i]; %>
<b><%= r.label %></b> - <i><%= r.message %></i>
<% for ( int j = 0; j < r.links.Count; j ++ ) {
l = (link)r.links[j]; %>
<li><a href="<%= l.url %>"><%= l.name %></a>
<% } %>
<br>time: <%= r.timeSpent.Seconds %> second(s) and <%= r.timeSpent.Milliseconds %> millisecond(s).
<p>
<% } %>

<hr>
total time: <%= s.totalTime.Seconds %> second(s) and <%= s.totalTime.Milliseconds %> millisecond(s).

</body>
</html>

The only difference is the extra parameter 3500 for the timeout value in results = s.search("tin", 3500) ; here we are doing the search with the timeout set as 3.5 seconds. We are using the same parallelSearch class here. When you run it, assuming you have everything setup correctly, you will see something like the following:

Summary

As you can see, the threading model lets us build more efficient and responsive software. It also lets us build a faster and smarter search engine. However, the benefits of using threads in our example comes from the fact that the resources are all located on different machines. If the resources are located on the same machine, then the advantage of this method may be minimal. On the other hand, if you have too many locations to search, then creating a thread for each might also degrade the performance. For instance, the searchWebSites() might be searching thousands of web sites. If you just create a thread for each search, then switching between the threads might be all the CPU will be doing for a few minutes. In this case, you might want to utilize a ThreadPool.