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 > [email protected] > https://lists.jboss.org/mailman/listinfo/infinispan-dev -- Manik Surtani [email protected] twitter.com/maniksurtani Lead, Infinispan http://www.infinispan.org
_______________________________________________ infinispan-dev mailing list [email protected] https://lists.jboss.org/mailman/listinfo/infinispan-dev
