Sanne is right, it will be non-trivial.  Attempting to sort the data set in memory for each such range operation will not scale.  Actually storing it in a sorted form (a thread safe linked hash map or something) is tricky too - I've looked at several algorithms (including Sundell/Tsigas' lock-free doubly linked lists [1]) and even the best lock-free structures end up with contention on the heads/tails when performing a CAS.  Arbitrary insertions get very expensive too.

Another approach would be to accept O(log n) for reads as well as writes and use a B*tree in memory, but that would require a lot of re-architecting.

[1] http://www.sciencedirect.com/science/article/pii/S0743731508000518

On 14 May 2012, at 18:06, Tristan Tarrant wrote:

On 05/14/2012 07:01 PM, Sanne Grinovero wrote:
but what's this concept of "key order" you're mentioning ?? The
complexity of such a patch would be close to "rewrite Infinispan" !?
No actually that would be simpler since we likely learned a bit from
the first time :D I had drafted some
Are you sure it would be that complex ? Basically it's just comparable
keys, a linked list and a grouper class. I don't want to oversimplify
though, and there might be things I don't understand.

Tristan

_______________________________________________
infinispan-dev mailing list
infinispan-dev@lists.jboss.org
https://lists.jboss.org/mailman/listinfo/infinispan-dev

--
Manik Surtani
manik@jboss.org
twitter.com/maniksurtani

Lead, Infinispan
http://www.infinispan.org