[pool] GenericObjectPool not FIFO with respect to borrowing threads

• Key: POOL-75
• Type: Improvement
• Status: Resolved
• Resolution: Fixed
• Priority: Minor
• Assignee: Unassigned
• Reporter: Gordon Mohr
• Affects Version/s: Nightly Builds
• Fix Version/s: 1.5

Environment

Operating System: All
Platform: All

Description

GenericObjectPool has recently been made FIFO with respect to the managed pool
objects – however, it is still not FIFO with respect to threads requesting
those objects. Specifically, because standard non-fair Java synchronization
monitors are used, later threads may barge ahead of earlier threads that are
already waiting for a pool object to become available. At its extreme, some
threads can cycle objects through the pool many times while others wait
interminable.

Not every application needs FIFO fairness with respect to threads, and such
fairness implies an overhead, so it need not be the default behavior, but it
would be a valuable option where many threads are sharing a smaller number of
pool objects.

I can submit a FairGenericObjectPool which achieves thread-fairness; it only
requires small changes to GenericObjectPool which allow some subclass overriding.

Comments

[Sandy McArthur (from Bugzilla import)]

I'd be interested to see your FairGenericObjectPool implementation. Be aware
that if it depends on features of the 1.5 JDK it may be a while before included
in the Pool distribution. The next release I'm working on will use Java 1.4 as a
baseline. If you have fair ordering working with only Java 1.4 features I'll
probably add it to my to do list for Pool 2.0.

[Sandy McArthur]

Untill Pool can use the util.concurrent package this will have to wait.

You didn't like my patch? (See bugzilla; it doesn't depend on util.concurrent.)

Even if the subclass itself isn't to be integrated – it is a little awkward – if the GenericObjectPool class were a bit more friendly to subclassing (fewer private fields) anyone could drop in the Fair subclass without having to patch GenericObjectPool itself.

[Sandy McArthur]

While the implementation in the patch (in bugzilla) looks straight forward, I think it has some problems.

1: I think with the _borrowerQueue.add(Thread.currentThread()); out side the sync block you have race that could lead to:
1.a: a pool configured to use WHEN_EXHAUSTED_FAIL to throw a NoSuchElementException when it shouldn't.
1.b: a pool configured to use WHEN_EXHAUSTED_GROW to create a new poolable objects when there are idle objects available.

2. Since if this were to be included in Pool it would mostly likely be included in Pool 2.0 it should pass those unit tests. (To test with these extend TestObjectPool or subclass and implement the makeEmptyPool methods and the suit method.) Currently it fails the TestObjectPool.testPOFBorrowObjectUsages() test as it calls activateObject for an object that was just made via makeObject. This fix is as simple as adding return pair.value; right after the newlyCreated = true; line.

3. How is this supposed to work with the evictor? Is the evictor allowed to preempt the other threads? I think that is what would happen now.

[Gordon Mohr]

Re: (1)

I see; it seems it would be sufficient to move the "_borrowerQueue.add(Thread.currentThread());" inside the synchronized block.

(I believe the idea of thread-fairness is really only sensible with respect to WHEN_EXHAUSTED_BLOCK pools – in the others, borrowObject() never blocks, so there's never the unfair/barging risk.)

Re: (2)

This was a straight copy of the superclass code; I see that the superclass has been changed in the SVN tree, so definitely the same fix should apply here.

Re: (3)

I hadn't considered the evictor; our use case doesn't use it, and I think the usual case where thread fairness is important – rationing a small number of pool objects among a large number of threads – may be more likely to use non-expiring pool objects.

Looking at evict(), it appears to me that it is indeterminate whether the evictor or a blocking borrower would get the first chance to run after an object is returned – but also that it doesn't need to be determinate, and any app using eviction is going to be robust about pool objects sometimes expiring "an instant" before being requested. (That is, my concept of "thread fairness" is orthogonal to the evictor's actions.)

Thanks for considering the patch. Do you want me to make the recommended changes and resubmit?

[Sandy McArthur]

After having slept on it and since thread fairness only makes sense in the WHEN_EXHAUSTED_BLOCK case I think the best plan is to:

1. Patch GenericObjectPool instead of creating a subclass. GOP is a bit of a hair ball but I think adding one more configurable feature is less hairy than exposing more of it's internals to allow subclassing. Personally, I think GOP is really dangerous to extend as use of it in that way wasn't well thought out as it was patched over the years and I don't want to encourage that kind of use as it's so fragile.

Also, I don't think the setting "use fair queueing" feature should be added to the constructors. They are unwieldily enough already and I've fixed few bugs due to the confusing nature of keeping the parameters straight. Just let it be controlled via a setter method, no need to add another constructor that will take 14 parameters, though I do think it should be added to the GOP.Config class.

2. I think all or most all of the thread fairness can be implemented in the WHEN_EXHAUSTED_BLOCK case of the switch statement. This would keep the scope of the changes as narrow as possible.

3. Since the evictor sometimes adds idle objects to the pool, despite it's name, I don't think it should get in line like the other threads as that could slow everything down.

If you want to rework the patch then go for it, else I'll eventually get to it before the 2.0 release.

[Takayuki Kaneko]

Hi,

I made the patch of fairness connection pool for trunk.

I ran tests with following settings.

• maxActive = 100
• each thread holds connection for 10 ms
• 300 threads runs cuncurrently

I got the good record of this patch.

dbcptype, throughput, Ave., Var., S.D. , min., 50%, 60%, 70%, 80%, 90%, max.
----------------------------------------------------------------------------------
original, 8533.9, 35.27, 18488.62, 135.97, 10, 12, 12, 12, 12, 13, 3527
fairness, 8744.2, 34.43, 18.87, 4.34, 10, 34, 34, 34, 35, 36, 160

"original" has a problem about fairness. maximum time of getting connection is 3527 ms
regardless of each threads holds connection for 10 ms.

I put 2 graphs that showed response time of borrowObject.

[Takayuki Kaneko]

I revised my patch.

• integrated with GenericObjectPool, which means removing duplicated operations around maxActive.
• fixed a problem around maxWait handling.

As a result, GenericObjectPool#borrowObject is simpler.

[Phil Steitz]

Thanks for the patch and sorry it took a while to look into it.

I like the ideas in the java2.patch and am interested in working on this. There are however a couple of problems with the patch, as is. Below all comments refer to the second patch, java2.patch

1) Multiple unit tests fail when the patch is applied. Let me know if you need help getting set up to run the pool unit tests. At least one failure is due to the missing break statement in setWhenExhaustedAction (after the WHEN_EXHAUSTED_FAIL case). I think there is also a missing release in borrowObject just before "return pair.value" after activating an object to return. I am not sure I understand exactly the semantics of acquire and release, though, so this could be wrong. In any case, we need the unit tests to pass (or to understand why they are in error if this is the case).

2) I don't follow exactly how the size and depth fields in FairnessSemaphore are supposed to work. Some class javadoc for this class explaining exactly what its contract is would help. I am not sure that the relationship between the pool's maxActive property and the size property of FairnessSemaphore is correct, though it is quite possible that I just don't understand how FairnessSemaphore works.

3) FairnessSemaphore needs ASF license header (like on all the other source files) and we need confirmation that the contribution can be made according to the Apache Contributor's License Agreement (http://www.apache.org/licenses/#clas)

Thanks again for the patch!

[Takayuki Kaneko]

Hi Phil,

Thanks for pointing out my patch's problems.

1) I'm trying to fix the issue on unit cases. I fixed some issue so I attach a new patch.
I wonder about TestGenericObjectPool#checkEvictorVisiting method. At line 335, pool's _numActive is greater than _maxActive because objects were already borrowed at line 294.
Is this a correct behavior?

2) "depth" is used to implement reentrant locking.　Reentrant locking is popular feature on lock algorithm.
But I had another think coming, in GenericObjectPool it is unnecessary feature.

3) Yeah, I accept this patch applies APL.

Please let me know about 1).
I will work more on this issue because fairness is really useful on enterprise use!

Regards,

[Phil Steitz]

Thanks, Takayuki.

I just committed a change to the address the failure you mention in 1). This is the result of what is at best an undocumented feature, but may be a bug in the current code's enforcement of the maxActive property. As you can see from the current implementation of borrowObject, if there are idle objects in the pool, borrowObject always succeeds - even if maxActive is exceeded. The latter can happen if addObject is invoked via the public API when there are instances checked out. That is what the test case does. addObject does no numActive check, though it does check maxIdle.

Unfortunately, changing behavior so that either addObject fails to add more than maxActive instances or borrowObject fails when idle instances are available in the pool will likely break some client applications, which like the test case above take advantage of the fact that you can inflate the pool using addObject. So we may need to work around this or at least discuss it some more. Part of the problem is that the documentation of maxActive as it stands now is weak and arguably ambiguous. This needs to be improved in any case.

Thanks again for the patch. I agree that getting fairness to work is a big plus. As I said above, some class javadoc for FairnessSemaphore would be good. Also, description of how exactly maxActive, maxWait, etc are enforced after the patch would be useful. I will complete review in the next couple of days. Comments from other interested parties welcome!

[Takayuki Kaneko]

Hi Phil,

I'm sorry for late replying.

I ran the latest test cases and passed them with my patch.

I added some comments on FairnessSemaphore javadoc.
My patch is bit difficult because multi-threading programming is difficult to comprehend.
But I think it's not so long, then, you can understand my patch easily with additional comment.

...I'm sorry, my English skill is not so good. Please let me know if you need more description of my patch.

IMHO, maxActive should be a hard limit of number of pooled objects.
Because the upper limit is necessary for system resources like database connection limit,
it can't be allowed to overflow.

Regards,

[Mark Thomas]

The recent changes to pool mean that this patch won't apply cleanly. There are also some things areas where I felt it could be improved. In particular:

• the FairnessSemaphore class seems to be duplicating some of the GOP functionality
• the same changes need to be made for GKOP as well as GOP.
• the test case isn't included.

I have taken some of the ideas from this patch and implemented an alternative solution for GOP. Test case and patches to follow. I'll then look at porting the changes to GKOP.

Although I'm not using the patch exactly as is, many thanks for providing it as helped considerably as I was looking at options to implement a fix for this issue.

[Mark Thomas]

The GOP fix has been ported to GKOP.