[infinispan-dev] Time measurement and expiry

[Dan Berindei]

Cool link Elias, I read the paper linked in the javadoc and it's very
interesting.

Netty seems to use scheme 6 (a single array of lists with hashing and
without any overflow). I believe in general our timeouts will be much
longer so I suspect scheme 5 or scheme 7 should perform better for us.

Scheme 5 should be much better than 6 if most of the timeouts use the
same value, and I believe we fit right in that use case.
On the other hand I think we could save some memory if we implement
scheme 7 by not actually storing the higher level wheels and building
them on the fly by iterating the data container. The downside is that
we'll need periodic sweeps of the data container, but those can be on
a separate thread.

One scenario that we should keep in mind is the L1 cache, whose
entries I would guess are invalidated much more often than they expire
after their 1 hour lifetime. If the user stores only immortal entries
+ L1 entries in the cache we might end up with a ticker task that
never rarely does anything useful so we should minimize its impact.

It might also be worth it to implement our own list type to make
adding and removing timeouts faster. I see Netty uses
IdentityHashMap-backed sets for the bucket lists, but as Sanne found
out they aren't the fastest thing around. Using a doubly-linked list
and keeping a reference to the Node in the cache entry should make it
much faster.

Cheers
Dan


On Tue, Oct 25, 2011 at 8:02 PM, Elias Ross <genman at noderunner.net> wrote:
> Rather than a heap, I recall Netty had a hash wheel timer[1]. Which should
> be better performing than a heap. You could get clever by having
> multiple heaps, segmented by orders of magnitude. For example wheel 1
> could have < 1 minute, 2 < 1 hour etc. Netty uses a lot of short lived
> timers and performs well.
>
> [1] http://docs.jboss.org/netty/3.1/api/org/jboss/netty/util/HashedWheelTimer.html
>
> Obviously this uses some memory, but you could probably optimize it
> somewhat to only work with Node instances.
> _______________________________________________
> infinispan-dev mailing list
> infinispan-dev at lists.jboss.org
> https://lists.jboss.org/mailman/listinfo/infinispan-dev
>