chrisvest / stormpot Goto Github PK

Maybe also update the readme.

A Pool implementation that stripes access across a set of sub-pools, in the hope that this will lower the contention on some important cache lines and make the pool perform and scale to higher core counts. See #20.

Metrics and features that'd be interesting to expose:

Likely:

• Allocation count
• Allocation failure count
• Mean object lifetime
• Pool size
• setTargetSize(int)

On the fence:

• Allocation latency histogram
• Claims collected sum (sum of claim counts, collected lazily as objects gets deallocated)
• Recent allocation success rate

A mixin-style Pool extension interface like the LifecycledPool interface, except this one will be for pools that can be resized on the fly.

Pools, or the QueuePool at least, should be able to take an Executor or similar through the Config. The Executor should be used instead of the allocation thread. I'm not entirely sure why this is a brilliant idea, but Viktor Klang thought it was important for Journal.IO, so it might also be important here. I should probably ask him about it.

A thread that is block in claim() might stay there long enough for their Request to be removed from the publist. If this happens, the threads will never be unparked - they will stay blocked forever.

An implementation of LifecycledPool based on flat-combining.

... to Maven Central.

Whirlpool must create sufficient allocator threads, to keep up with pool churn. Even in the face of very short TTL and very slow-to-create objects.

See https://github.com/chrisvest/stormpot/blob/master/src/test/java/stormpot/PoolTest.java#L314

The second claim attempt will cause another object to the put onto the dead-queue. This object might cause a second deallocation before the assertion is checked.

QueuePool might miss the exception provided by slot.poison at line 81 in QueuePool.java, because it by that point has already reentered the dead-queue and might have been picked up by the allocation thread and cleared.
The solution is to pull the poison exception into a local variable before putting the slot into the dead-queue.

Allow the QueuePool to stripe access across a set of partitions, to reduce queue contention.

I use TimeUnit.MINUTES somewhere, which is not Java 5 compatible. I should try and change that.

See https://github.com/blog/1184-contributing-guidelines

We should have a benchmark that compares Stormpot to Commons-Pool under various loads.

Benchmarking hacked Nanopool and BoneCP implementations would also be interresting, but not of highest priority.

And we should also showcase those numbers on the web-site. Especially if they are in our favor :)

Make the jUnit dependency optional (I think is the best choice) and create an AbstractAllocatorTest class as part of the product code.

Clients will be able to use this test case scaffold to test their Allocator implementations.

See #21 for the procedure.

• Fix all the issues
• Update & review the javadoc & documentation
• Perform the release procedure from #21
• Remember to promote the released artefacts to Maven Central
• Update the website on github
• Blog about the new release and its performance

See issue #21 (the release of 1.0) for a guide.

Attempt to construct an informal proof of correctness for the blazepool implementation. See existing research papers on concurrent algorithms for inspiration.

Informal proofs are good enough. Machine verification is too much to take on in one go.

So that the project may compile again.

A pretty yet simple web site is needed. Preferably Jekyll based so content is in markdown, and gh-pages can build the site on commit.

The Whirlpool.lock field might have false sharing with the publist field, so adding an AtomicInteger indirection might move it to a different cache line and thus improve performance.

Also test the reverse idea, where publist is turned into an AtomicReference.

Using VirtualBox or something other. Anyway, try building and testing the code in a virtual machine with a real Java 5, because setting target and source version is not enough.

The normal TimeExpiration is at risk of causing all items in a pool to become expired at very close to the same time. This effect, if this is sudden enough, can temporarily cause the pool to become depleted, because all items in it are dead and await reallocation.

A GaussianTimeExpiration would randomly spread the expiration out over a period, over time resulting in a much more uniform spread of expiration load.

It'll probably take some experimenting to figure out what the best curve is, in relation to the proposed lifetime of the items.

See http://en.wikipedia.org/wiki/Normal_distribution for maths.

Convert to a multi-module maven setup, so things like tests, benchmarks and non-core features can be separate.

They must throw in their constructors. Otherwise we'll get allocation errors when threads try to claim, which might be hard for clients to debug.

When you call SlotInfo.getPoolable(), you are engaging in concurrent access of that Poolable. It may not be obvious to most people that they now have to take their precautions to maintain thread-safety of their Poolables when they do that.

Therefore, the javadoc should be updated to indicate this.

Experiment with letting threads keep their last-claimed object in a thread-local. It will complicate things, I'm sure, but could potentially reduce the cost of a non-contended claim to a TLS-lookup and a CAS.

Luckily, this BlockingQueue implementation is available under the Apache 2 license:
http://git.eclipse.org/c/jetty/org.eclipse.jetty.project.git/tree/jetty-util/src/main/java/org/eclipse/jetty/util/BlockingArrayQueue.java

It might be faster, so it's worth testing.

Add an API where old Poolables can be rejuvenated, instead of going through the deallocate-allocate cycle.

The idea is to reuse the Poolable objects and keep them live, because they have probably long since been promoted to the old-gen. This will reduce old-gen garbage production, and thereby also the expensive full-gc cycles and compaction cycles, for application where this matters.

There is a case where threads who make non-timeouted claims, and threads who make claims with a negative timeout, can cause the non-timeouted threads to block forever.

Try adding mutation based testing to the mix, and see if some more bugs can be weeded out of the woodwork.

It appears that QueuePool, at least, is affected by this.

It was discovered during a benchmark run, that the Whirlpool implementation can deadlock when you await the completion of the shutdown procedure.

Thread dump:

"Whirlpool-Allocator-Thread for stormpot.benchmark.PoolSpin$SlowAllocator@11f2ee1" prio=10 tid=0x780d7800 nid=0x773c runnable [0x778fe000]
   java.lang.Thread.State: TIMED_WAITING (parking)
  at sun.misc.Unsafe.park(Native Method)
  - parking to wait for  <0x7c4f0358> (a stormpot.whirlpool.Request)
  at java.util.concurrent.locks.LockSupport.parkNanos(LockSupport.java:198)
  at stormpot.whirlpool.Request.await(Request.java:53)
  at stormpot.whirlpool.Whirlpool.perform(Whirlpool.java:220)
  at stormpot.whirlpool.Whirlpool.relieve(Whirlpool.java:145)
  at stormpot.whirlpool.WpAllocThread.deallocateAll(WpAllocThread.java:132)
  at stormpot.whirlpool.WpAllocThread.run(WpAllocThread.java:69)

   Locked ownable synchronizers:
  - None

"main" prio=10 tid=0x0978c800 nid=0x7731 waiting on condition [0xb6a92000]
   java.lang.Thread.State: WAITING (parking)
  at sun.misc.Unsafe.park(Native Method)
  - parking to wait for  <0x7c5298b0> (a java.util.concurrent.CountDownLatch$Sync)
  at java.util.concurrent.locks.LockSupport.park(LockSupport.java:158)
  at java.util.concurrent.locks.AbstractQueuedSynchronizer.parkAndCheckInterrupt(AbstractQueuedSynchronizer.java:811)
  at java.util.concurrent.locks.AbstractQueuedSynchronizer.doAcquireSharedInterruptibly(AbstractQueuedSynchronizer.java:969)
  at java.util.concurrent.locks.AbstractQueuedSynchronizer.acquireSharedInterruptibly(AbstractQueuedSynchronizer.java:1281)
  at java.util.concurrent.CountDownLatch.await(CountDownLatch.java:207)
  at stormpot.whirlpool.WpAllocThread.await(WpAllocThread.java:53)
  at stormpot.benchmark.PoolSpin.tearDown(PoolSpin.java:84)
  at stormpot.benchmark.ContendedPoolSpin.tearDown(ContendedPoolSpin.java:54)
  at com.google.caliper.SimpleBenchmark$1.close(SimpleBenchmark.java:139)
  at com.google.caliper.TimeMeasurer.measureReps(TimeMeasurer.java:177)
  at com.google.caliper.TimeMeasurer.warmUp(TimeMeasurer.java:62)
  at com.google.caliper.TimeMeasurer.run(TimeMeasurer.java:122)
  at com.google.caliper.InProcessRunner.run(InProcessRunner.java:74)
  at com.google.caliper.InProcessRunner.run(InProcessRunner.java:49)
  at com.google.caliper.InProcessRunner.main(InProcessRunner.java:103)

   Locked ownable synchronizers:
  - None

For instance, daylight savings time can cause clocks to be adjusted backwards, and so can NTP.

This influences the many time-outs and object TTLs in the pools.

As a way to deal with this: http://findbugs.sourceforge.net/bugDescriptions.html#SC_START_IN_CTOR

A fuzz-tester is needed to help make sure that we don't have any races on a more varied range of hardware.

A pool implementation, where many pool instances can share a pool (an Executor) of allocator threads.

A design similar to QueuePool can be used, but where the individual slots know who allocates them. Not sure if this can easily be made resizable. It probably can't be made lifecycled.

See if there are places where we can be made to go faster by using the weaker ordering constraints provided by Atomic_.weakCompareAndSet and Atomic_.lazySet, instead of their strongly-ordered counterparts.

See:
http://stackoverflow.com/questions/7557156/atomicxxx-lazyset-in-terms-of-happens-before-edges
http://stackoverflow.com/questions/1468007/atomicinteger-lazyset-and-set
http://psy-lob-saw.blogspot.co.uk/2012/12/atomiclazyset-is-performance-win-for.html

A lot of contention in the QueuePool implementation comes from the use of blocking queues.

Another non-blocking live-queue could be added as a fast-path option: claims would take from the non-blocking live-queue first, and only if it turns out to be empty, try to take from the blocking live-queue (with timeout logic, etc.)

The blocking live-queue will have to be bounded such that it is smaller than the maximum number of elements in the pool. Since the pool is resizable, the only real option for a bound is 1.

It must be bounded, because the allocation thread will have to release new live objects into the blocking live-queue first, and only if it's full, insert them into the non-blocking live-queue. This way, we ensure that if the pool has been depleted, the new object will allow a thread waiting in claim to make progress.

The javadocs needs to be reviewed and proof-read, to make sure that it is accurate with regards to what the code actually does.

Also, it needs to be vetted for spelling mistakes, grammatical errors and typos.

The BlazePool will currently throw an exception if a Poolable is released by a thread that isn't the claiming thread. The QueuePool and BasicPool implementations, however, do not perform this check.

Also, the documentation is silent on the topic, neither explicitly allowing it nor permitting it.

Is there a use case where it makes sense for a Poolable to be handed off between threads, or is the likelihood that this is an error so great, that the documentation should be updated to reflect this?

Because that's what we're actually pooling.

Add a DeallocationRule API that allows users to provide their own algorithm to determine whether a slot is invalid or not.

Perhaps make it look something like this:

interface SlotInfo<T extends Poolable> {
  long getCreatedTime(); // millis since epoc
  long claimCount();
  T getValue();
}

interface DeallocationRule<T extends Poolable> {
  boolean isInvalid(SlotInfo<T> slotInfo);
}

Make sure time-to-live remains a sane default.

Allocator.allocate and .deallocate should throws Exception so implementors don't have to worry so much.

Implement the Stormpot API using Apache Commons-Pool, so the two libraries can work together if people want that.

Make sure that the commons-pool is marked as optional in the POM, so we don't force any unnecessary dependencies upon people.

BlazePool performs poorly in situations where, e.g. two threads are cooperating such that one is exclusively claiming objects, and then sends them off to be released by the other thread.

-This will also make for an interesting benchmark.-

The MessagePassingBenchmark has been implemented. I think a double-lane queue design might help mitigate the problem a little, but I also think that BlazePool will always be slower than QueuePool for this use case.

See #37.