IBU News (Germany) Edition 0.9.9

Threads

IB is designed to handle S/R concurrency. In IBU News, for instance, the indexer is running nearly continuously and search is always in-step with the index. Its built using the POSIX threads model. IB, however, isn't 100% 'thread-safe' in the sense that the programmer can use code indiscriminately from threads. Its been designed with reasonable process safety in mind to allow for robust development of search and retrieval applications. IB is typically used in Web server environments as a service (via protocols). IB can be via JNI embedded into application servers such as Tomcat but its not advised--- and especially not on Linux 32-bit systems (due to the design of the 32-bit kernel and how it uses low memory to manage memory mapped pages which together with the size of Tomcat+Apache and the max. address space leaves very little room despite available memory in RAM and swap) highly discouraged. De-coupling search from the application server increases the resilience of the application server to traffic. Java, after all, is about modularization and client-server objects.

Why not make IB 100% thread safe? The most obvious problem is performance. When a thread blocks, the data (and in search its all about data) must either be locked or saved (and re-accessed). In the balance its seemed that trying to make things 100% safe (to do something in a manner that we don't think makes sense— see below) is either a flirt with deadlocks and race conditions or significantly increasing the I/O demands (which are our bottleneck).

Should one run search in threads? Does it make sense? Threads make a lot of sense doing small mathematical calculations with the current generation of multi-pipelined processors such as the AMD Athlon™ and Hyper-Threaded Intel Pentium™ 4 processors. They don't make too much sense with I/O since these processors all have single data ports. Input and output is limited to their serial flow through the pipeline. Disks too are limited to reads within a sector. Their relatively small disk buffers favor sector-to-sector serial reads for highest throughput. Given search speed is limited by I/O throughput, a multi-threaded search is counterproductive. Disk access will tend to use the cache less and demand more head movements (slower, more heat, more power needed etc.). In total this means that the total time for N searches in N threads tend to be larger than the time spend in queued queries.

Benchmarks with Lucene as an example of a engine often used in Java threads rather than in concurrency, despite using caches, confirm this: http://lucene.apache.org/java/docs/benchmarks.html

                                Threads|Avg Time per query (ms)
                                1       1009ms
                                2       2043ms
                                3       3087ms
                                4       4045ms
                                ..        .
                                ..        .
                                10      10091ms

In this case 10 users running the search in 10 threads will each wait 10 seconds for the result. Using serialization of searches with similar search times means that nearly everyone will wait less (half the people, less than half the time). The threaded model here makes everyone unhappy while the queued model makes almost everyone happier with first come first served. That's why we agree to queue (stand in line) to ride the bus (also an object with limited input/output bandwidth). Anyone who has ever taken a public bus has personal experience on how much longer it takes to travel when people all rush to get on. The trip nearly always will take longer and will certainly be less comfortable or safe.

When the queue, however, has searches with different time requirements this can be less than fully optimal--- like waiting for a table in a restaurant it calls for some queue adjustment.

IB running in threads addressing information in a single large multi-record document scales better to threads due to the O/S caching (more page reclaims and fewer I/O events) but experiences are mixed in larger file systems. Searching for the term "money" in the collected works of Shakespeare, for instance, in 500 concurrent threads (OK, we wanted to push things to absurdity) ran the search in:

Got  "money"  -> 32  =  ('The Comedy of Errors', 1.5649999999999968)
Got  "money"  -> 32  =  ('The Comedy of Errors', 0.16000000000000736)
Got  "money"  -> 32  =  ('The Comedy of Errors', 0.13999999999998736)
Got  "money"  -> 32  =  ('The Comedy of Errors', 0.13399999999999523)
Got  "money"  -> 32  =  ('The Comedy of Errors', 0.13599999999999723)
Got  "money"  -> 32  =  ('The Comedy of Errors', 0.11300000000000199)
Got  "hedgehog"  -> 1  =  ('The Tragedy of Richard the Third', 3.5680000000000156)
Got  "money"  -> 32  =  ('The Comedy of Errors', 0.18499999999987971)
Got  "hate"  -> 33  =  ('The Tragedy of Coriolanus', 0.7139999999998814)
....

Running 500 threads with a search in each:
Thread Total time = 54.661 Clock time total = 93.75
Absolute total time (real) = 39.0625
Now as sequence x 500
Total = 28.272 Real Total = 39.0625
This shows that the threads take around 150% more CPU to do the same work and produce response times not at least as bad as the last in the sequential queue.

As the number of files to access increases the performance of threads should even decline as more I/O events and memory pages are not in cache.

In general use, however, most searches don't ever start "at the same time". In a typical Web application environment intended to run on a single machine/CPU we don't, I think ever want more than than 2 or 3 threads on a regular basis (in contrast to peak) since performance would become unacceptable. It makes all people wait for the longest time. 1 second might be reasonable but 30 seconds might not. Having 30 people wait 30 seconds for a result can alienate many users so many will leave before the search is completed increasing the mean time for completed searches. Its double poison.

In general these considerations suggest a model of search pools (which can be threaded) and priority queues.