[infinispan-dev] range query in Infinispan !!

[Sanne Grinovero]

On 14 May 2012 18:06, Tristan Tarrant <ttarrant at redhat.com> 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.

No I'm not sure as I didn't try. But some questions:

- how to you distribute comparables in a deterministic way on a consistent hash?

- you have an efficient multithreaded linkedlist implementation which
also implements ConcurrentMap ? (because if it's not a map, we'll have
to rewrite all of the API as well, not considering yet CacheLoader &
co)

- in terms of consistency, now you have a function(Key)->Value .
Changing the value means performing a logical "CAS" operation to remap
a key to a new value. This poses all kinds of problems by the simple
fact that this single relation K,V needs to be "seen"
consistently/transactionally across all nodes. It's going to be pretty
more complex if each write also has to keep with the next(Key) and
maybe previous(Key).
For sure the simple fat that it's changing multiple attributes on
multiple entry (as it affects previous and/or next) on each write
means that any simple design is impossible, as multiple changes means
CAS is never going to be reliable but you'll have to lock graphs of
entries. Maybe small graphs, but multiple ones. And backoff+retry on
multiple transactions inserting entries which are close in the same
order and might conflict in our datastructure even if they don't write
on conflicting keys..

 - I'll stop thinking about more problems as I guess I'm already
satisfied on the result: I might have underestimated the problem ;-)

Cheers,
Sanne

>
> Tristan
>
> _______________________________________________
> infinispan-dev mailing list
> infinispan-dev at lists.jboss.org
> https://lists.jboss.org/mailman/listinfo/infinispan-dev