TimeLimitedIndexReader and associated utility class [LUCENE-1720]

[asfimport]

An alternative to TimeLimitedCollector that has the following advantages:

1. Any reader activity can be time-limited rather than just single searches e.g. the document retrieve phase.
2. Times out faster (i.e. runaway queries such as fuzzies detected quickly before last "collect" stage of query processing)

Uses new utility timeout class that is independent of IndexReader.

Initial contribution includes a performance test class but not had time as yet to work up a formal Junit test.
TimeLimitedIndexReader is coded as JDK1.5 but can easily be undone.

---

Migrated from LUCENE-1720 by Mark Harwood (@markharwood), 2 votes, updated Aug 16 2011
Attachments: ActivityTimedOutException.java, ActivityTimeMonitor.java (versions: 3), Lucene-1720.patch (versions: 2), LUCENE-1720.patch (versions: 3), TestTimeLimitedIndexReader.java (versions: 2), TimeLimitedIndexReader.java (versions: 2)
Linked issues:

• FilterIndexReader in trunk does not implement getSequentialSubReaders() correctly [LUCENE-2769] #3843

[asfimport]

Shai Erera (@shaie) (migrated from JIRA)

In stop(), shouldn't the 'else' part be reached only if the firstAnticipatedThreadToFail == Thread.currentThread()? Currently, if no thread has timed out, and I'm not the firstAnticipatedThreadToFail, the code will still look for a new candidate, and probably find the same firstAnticipatedThreadToFail. Right?

Also, even though that's somewhat mentioned in the class, we don't support multiple timing out threads, and I'm not sure if that's good. Currently, if two threads time out, and the calling thread to checkTimeOutIsThisThread() is not firstAnticipatedThreadToFail, it will continue processing. That may not be good, if the other thread is busy-waiting somewhere, and may not call checkTimeOutIsThisThread for a long time.

What if we change firstAnticipatedThreadToFail to a HashSet and call contains()? It's slower than '==', but safer, which is also an important aspect of this utility. TimeoutThread can add all the timeoud threads to this HashSet, when it detects a timeout has occurred (by iterating on all the 'registered' threads and their expected time out time, and compare to the current time). What do you think?

[asfimport]

Mark Harwood (@markharwood) (migrated from JIRA)

Currently the class hinges on a "fast fail" mechanism whereby all the many calls checking for a timeout are very quickly testing a single volatile boolean, "anActivityHasTimedOut".
99.99% of calls are expected to fail this test (nothing has timed out) and fail quickly - I was reluctant to add any hashset lookup etc in there needed to determine failure.

With that as a guiding principle maybe the solution is to change
volatile boolean anActivityHasTimedOut
into
volatile int numberOfTimedOutThreads;

which would cater for >1 error condition at once. The fast-fail check then becomes:
if(numberOfTimedOutThreads > 0)
{
if(timedoutThreads.contains(Thread.currentThread)
{
timedoutThreads.remove(Thread.currentThread);
numberOfTimedOutThreads=timedoutThreads.size();
throw RuntimeException.....
}
}

[asfimport]

Eks Dev (migrated from JIRA)

it's been late for this issue, but maybe worth thinking about. We could change semantics of this problem completely. Imo, the problem can be reformulated as "Provide possibility to cancel running queries on best effort basis, with or without providing so far collected results"

That would leave Timer management to the end users and make an issue focus on one "Lucene core" ... Timeout management can be then provided as an example somewhere "How to implement Timeout management using ..."

[asfimport]

Shai Erera (@shaie) (migrated from JIRA)

... quickly testing a single volatile boolean, "anActivityHasTimedOut".

Oh, I did not mean to skip this check. After anActivityHasTimedOut is true, instead of comparing Thread.currentThread() to firstAnticipatedThreadToFail, check if Thread.currentThread() is in the failed HashSet of threads, or something like that.

I totally agree this should be kept and used that way, and it's probably better than numberOfTimedOutThreads since we don't need to inc/dec the latter every failure, just set a boolean flag and test it.

Imo, the problem can be reformulated as "Provide possibility to cancel running queries on best effort basis, with or without providing so far collected results".

That's where we started from, but Mark here wanted to provide a much more generalized way of stopping any other activity, not just search. With this utility class, someone can implement a TimeLimitedIndexWriter which times out indexing, merging etc. Search is just one operation which will be covered as well.

I also think that TimeLimitingCollector already provides a possibility to "cancel running queries on a best effort basis" and therefore if someone is interested in just that, he doesn't need to use TimeLimitedIndexReader. However this approach seems much more simple if you want to ensure queries are stopped ASAP, w/o passing a Timeout object around or anything. This approach also guarantees (I think) that any custom Scorer which does a lot of work, but uses IndexReader for that, will be stopped, even if the Scorer's developer did not implement a Timeout mechanism. Right?

[asfimport]

Mark Harwood (@markharwood) (migrated from JIRA)

Oh, I did not mean to skip this check.

But the check is on a variable with a yes/no state. We need to cater for >1 simultaneous timeout error condition in play. With only a boolean it could be hard to know precisely when to clear it, no?

Mark here wanted to provide a much more generalized way of stopping any other activity, not just search

To be fair I think the use case for IndexWriter is weaker. In reader you have multiple users all expressing different queries and you want them all to share nicely with each other. In index writing it's typically a batch system indexing docs and there's no "fairness" to mediate? Breaking it out into a utility class seems like a good idea anyway.

[asfimport]

Eks Dev (migrated from JIRA)

Sure, I just wanted to "sharpen definition" what is Lucene core issue, and what we can leave to end users. It is not only about the time, rather about canceling search requests (even better, general activities).

[asfimport]

Shai Erera (@shaie) (migrated from JIRA)

With only a boolean it could be hard to know precisely when to clear it, no?

We can cleat it when the time out threads' Set's size() is 0?

I agree that this issue is mostly about IndexReader (and hence the name), and that the scenario of IndexWriter is weaker. But a utility class together w/ the TimeLimitedIndexReader example can help someone write a TimeLimitedIndexWriter very easily, and/or reuse this utility elsewhere.

[asfimport]

Mark Harwood (@markharwood) (migrated from JIRA)

any custom Scorer which does a lot of work, but uses IndexReader for that, will be stopped, even if the Scorer's developer did not implement a Timeout mechanism. Right?

Correct. I'm not familiar with the proposal to pass around a Timeout object but I get the idea and the code here would certainly avoid that overhead.

We can cleat it when the time out threads' Set's size() is 0?

Yes, that would work.

[asfimport]

Shai Erera (@shaie) (migrated from JIRA)

I'm not familiar with the proposal to pass around a Timeout object

On the email thread I offered to create on QueryWeight a scorer(IndexSearcher, boolean, boolean, Timeout) in order to pass a Timeout object to Scorer, and also create a TimeLimitedQuery. But it's no longer needed.

[asfimport]

Jason Rutherglen (migrated from JIRA)

Maybe we can benchmark this approach to see if it slows down
queries due to the the Thread.currentThread and hash lookup? As
this would go into 3.0 ? maybe we can look at how to change
the Lucene API such that we pass in an argument to the
IndexReader methods where the timeout may be checked for?

[asfimport]

Mark Harwood (@markharwood) (migrated from JIRA)

Maybe we can benchmark this approach

See http://www.nabble.com/Improving-TimeLimitedCollector-td24174758.html#a24229185
The figures were produced by TestTimeLimitedIndexReader that is part of this Jira issue so you can try benchmarks on your own indexes.

bq.if it slows down queries due to the the Thread.currentThread and hash lookup

This lookup only happens when threads start or stop timed activities and when there is a timed out state - all other method invocations on TimeLimitedIndexReader eg termDocs.next() are simply testing a volatile boolean which is used to indicate if any timeout has occurred. This seems to be fast in my benchmarks.

maybe we can .. change the Lucene API such that we pass in an argument to the IndexReader methods where the timeout may be checked

The current design uses static methods which remove the need to pass a timeout object as context everywhere but using this approach comes with the downside that a single client thread is unable to time >1 activity at once which we thought was a reasonable trade-off. See http://www.nabble.com/Re%3A-Improving-TimeLimitedCollector-p24234976.html

[asfimport]

Jason Rutherglen (migrated from JIRA)

This lookup only happens when threads start or stop timed
activities and when there is a timed out state

Ah, so we're assuming most actions don't timeout, and when they
do we're then doing the slightly more expensive threadlocal
lookup.

Sounds good!

Maybe we can turn this into a patch, and create a benchmark .alg
etc (I'll volunteer to do the latter).

[asfimport]

Mark Harwood (@markharwood) (migrated from JIRA)

Ah, so we're assuming most actions don't timeout....

Yes, that's it.

(I'll volunteer to do the latter).

Cool. I'll work on tidying up the classes under test as per comments earlier .

[asfimport]

Mark Harwood (@markharwood) (migrated from JIRA)

Updated to allow >1 simultaneous timeout error to be handled

[asfimport]

Shai Erera (@shaie) (migrated from JIRA)

1. Can we move to call Thread.currentThread() only once per method? Currently stop() calls it 3 times, start() 2 and checkTimeoutIsThisThread()
2. Can we change TimeoutThread to just wait() on timeLimitedThreads, instead of wait(1000)? I think it's enough to rely on notify()? Otherwise, if my system is idle, this thread will wake up every second for nothing.
3. Maybe change checkTimeoutIsThisThread to do "if(timedOutThreads.remove(Thread.currentThread()) != null)" and delete the next line? If a thread has timed out, there's no need to look it up in the map twice.

Question - TimeoutThread checks firstAnticipatedTimeout vs. the current time and if it has exceeded, it adds firstAnticipatedThreadToFail to timedoutThreads. I think it will fail in the following scenario:

• Thread 1 start an activity w/ time 100 (the expected exceeded time).
• Thread 2 start an activity w/ time 150.
• Thread 1 is stuck somewhere.
• TimeoutThread checks the current time against firstAnticipatedTimeout and adds firstAnticipatedThreadToFail to timedOutThreads.
• Thread 2 checks for timeout, but timedOutThreads does not contain it. Therefore it continues its execution.

If a thread is stuck, the rest of the threads should not fail on their "timeout exceeded" checks. How about if when TimeoutThread detects the first timeout has reached it will: (1) add that thread to the timedOutThreads Set and (2) set "first timeout" to be the next in the Map/List. I think we'll need an additional LinkedList or something, so that start(), stop(), check() and TimeoutThread.run() will work properly, but that shouldn't be too complicated.

What do you think?