10:58 a.m.
Hi,
In QuickTweet we needed a way to get most recent x tweets for a user or
on a topic. Currently we are implementing it by keeping entries in the
cache and updating a bounded FIFO queue in parallel. However, to get
most recent data or data for a given time range is a very common use
case specially in social media applications. It would be good to see
this range feature available in out of box (not using Query) in upcoming
Infinispan releases. Thoughts?
I can get it started by creating a Jira unless I hear otherwise.
Regards,
Prabhat
11:40 a.m.
I have not used Infinispan's Query or Map/Reduce functionalities yet
because of them not being in JDG yet. Yes, we can use those to get what
I have mentioned. Query should be more straight forward and simpler than
M/R I think. But Query has dependency on Lucene and I have experienced
great pain in the past when using Lucene and FileSystem for shared storage.
My perspective is a bit different. I am arguing for a "simpler" solution
for a problem that I find to be very common. Similar to how in
Cassandra, you can easily query based on a time range and the order you
want.
On 05/14/2012 11:05 AM, Sanne Grinovero wrote:
11:50 a.m.
Sanne,
Prabhat and I had a chat the other day and agreed that Infinispan would
be much easier to apply to a large variety of use cases if we could
iterate over ordered keys given a starting point. Cassandra does this by
partitioning (grouping in Infinispan speak) consecutive keys on the same
node for performance reasons. I guess you could use the Query module and
distributed keys for this, but I think it is a bit overkill.
Tristan
On 05/14/2012 06:40 PM, Prabhat Jha wrote:
12:01 p.m.
On 14 May 2012 17:50, Tristan Tarrant <ttarrant(a)redhat.com> wrote:
I agree, Query would be overkill. I'm the first one to *not* recommend
using Query if you also need good write performance ;)
I would also agree that being unable to iterate the keys is often a
though problem;
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 ideas about a similar design while in St Louis with
Emmanuel and Hardy about a truly partitioned index, with index
segments and values located in the same containers; if someone is
serious about it I could share the design but I'd estimate some ~6
months full time work on it, including an ad-hoc B-tree in memory to
replace traditional Lucene indexes. And we had some Whiskey, so maybe
it won't work.
Cheers,
Sanne
12:25 p.m.
On 14 May 2012 18:06, Tristan Tarrant <ttarrant(a)redhat.com> wrote:
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
9:11 a.m.
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:
--
Manik Surtani
manik(a)jboss.org
twitter.com/maniksurtani
Lead, Infinispan
http://www.infinispan.org
9:03 a.m.
On 14 May 2012, at 18:01, Sanne Grinovero wrote:
We should certainly chat about this. I sent out an email re: a brainstorming session re:
querying.
--
Manik Surtani
manik(a)jboss.org
twitter.com/maniksurtani
Lead, Infinispan
http://www.infinispan.org
11:51 a.m.
On 14 May 2012 17:40, Prabhat Jha <pjha(a)redhat.com> wrote:
I have not used Infinispan's Query or Map/Reduce functionalities
yet
because of them not being in JDG yet.
I see but even assuming we would start something new, it will likely
take longer for it to eventually get into JDG compared to Query or
Map/Reduce.
Well Infinispan solves that problem, no shared filesystems ;)
https://github.com/infinispan/infinispan/blob/master/lucene-directory/src...
BTW cool that you have experience with it.. feel to start working more
on this area?
I'm all for simplicity, but.. Cassandra is column oriented, so it can
do some more tricks.. have you thought how this could be implemented
on a distributed key value store like Infinispan?
Unless you have a really neat idea, I'm not sure how simple that could be.
12:48 p.m.
I agree with Sanne, Cassandra is very good at that use case due to the way they store
things. OTOH, that's their best use case by far :)
We could think about a way to mix together:
- fine grained locking
- AtomicMap
- partial load
basically we could imagine some new primitive features for AtomicMap like:
- get subkeys between x and y
- add subkey (not requiring to load the AtomicMap)
That would get us a long way towards some of what MongoDB does wrt partial document
update.
On 14 mai 2012, at 18:51, Sanne Grinovero wrote:
9:06 a.m.
On 14 May 2012, at 18:48, Emmanuel Bernard wrote:
Don't we have a good deal of this already with Randall's schematic patch
(currently as a part of ModeShape, targeted for inclusion in Infinispan 5.2.0)?
https://issues.jboss.org/browse/ISPN-1103
https://github.com/ModeShape/modeshape/tree/master/modeshape-schematic
--
Manik Surtani
manik(a)jboss.org
twitter.com/maniksurtani
Lead, Infinispan
http://www.infinispan.org
1:27 p.m.
On 05/14/2012 11:51 AM, Sanne Grinovero wrote:
I
meant simpler from users of this feature point of view, not in terms
of implementation. I don't have any implementation experience on these
topics but my thought was implementing distributed comparator and
distributed sorted map. But you have already laid out challenges in your
another reply on this thread.
For this use case IMO, it would be okay to have expensive write for
faster read.
4686
days inactive
4688
days old
infinispan-dev@lists.jboss.org
13 comments
5 participants
participants (5)
-
Emmanuel Bernard -
Manik Surtani -
Prabhat Jha -
Sanne Grinovero -
Tristan Tarrant