You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@cassandra.apache.org by Jason Rutherglen <ja...@gmail.com> on 2012/06/06 18:00:00 UTC
Cassandra in memory key index
I am wondering how this is currently implemented? Is there prefix compression?
Re: Cassandra in memory key index
Posted by Radim Kolar <hs...@filez.com>.
Dne 8.6.2012 21:19, Jason Rutherglen napsal(a):
> Ok looks like the IndexSummary encapsulates everything, I can start with
> hacking that.
do memory part first. i want to test it on existing serialized index data.
Re: Cassandra in memory key index
Posted by Jason Rutherglen <ja...@gmail.com>.
> does FST provide a predecessor lookup function
Yes [1]. seekCeil, seekFloor, seekExact are the methods provided for
seeking.
1.
https://github.com/apache/lucene-solr/blob/trunk/lucene/core/src/java/org/apache/lucene/util/fst/BytesRefFSTEnum.java
On Fri, Jun 8, 2012 at 4:03 PM, Pavel Yaskevich <po...@gmail.com> wrote:
> Yeah, that is why I wrote "if possible" :) Also, does FST provide a
> predecessor lookup function, wasn't clear from the blog post?
>
> On Friday 8 June 2012 at 22:53, Jason Rutherglen wrote:
>
> > Yeah that's fine, however if there isn't a Java implementation that's a
> lot
> > of extra work. The FST approach should be a clear quick and easy win. The
> > current system of in heap keys and a binary search is what the FST
> replaced
> > in Lucene. There are plenty of references to the improvement.
> >
> > On Fri, Jun 8, 2012 at 3:50 PM, Pavel Yaskevich <povel.y@gmail.com(mailto:
> povel.y@gmail.com)> wrote:
> >
> > > I would vote, if possible, to compare it with y-fast trie [1] (it
> doesn't
> > > seem to be available java implementation unfortunately) by means of
> memory
> > > efficiency and lookup performance. As we use big integer tokens the
> main
> > > benefit from that trie could be O(log log M) predecessor lookup and
> compact
> > > in-memory size.
> > >
> > > [1] https://en.wikipedia.org/wiki/Y-fast_trie
> > >
> > > Best Regards
> > > --
> > > Pavel Yaskevich
> > >
> > >
> > > On Friday 8 June 2012 at 22:19, Jason Rutherglen wrote:
> > >
> > > > Ok looks like the IndexSummary encapsulates everything, I can start
> with
> > > > hacking that.
> > > >
> > > > On Fri, Jun 8, 2012 at 11:50 AM, Jason Rutherglen <
> > > > jason.rutherglen@gmail.com (mailto:jason.rutherglen@gmail.com)>
> wrote:
> > > >
> > > > > The Cassandra integration is probably beyond the time I have
> available.
> > > > > If the locations in the code that need to be rewritten to use the
> FST
> > > > >
> > > >
> > > >
> > >
> > > are
> > > > > known, and a patch simply 'plugs-in' the FST, that would be much
> > > >
> > >
> > > easier.
> > > > > Eg, I don't know how Cassandra stores the current key index for
> > > >
> > >
> > > example...
> > > > >
> > > > > Basically I can write FST serializing, deserializing, and key
> lookup
> > > code
> > > > > fairly easy by basing it on Lucene's terms dict.
> > > > >
> > > > >
> > > > > On Fri, Jun 8, 2012 at 6:00 AM, Radim Kolar <hsn@filez.com(mailto:
> hsn@filez.com) (mailto:
> > > hsn@filez.com (mailto:hsn@filez.com))> wrote:
> > > > >
> > > > > >
> > > > > > If you are interested I can help, I used the FST on a Hadoop
> project
> > > > > > > to implement a fast map side range join.
> > > > > >
> > > > > >
> > > > > > create JIRA item with patch attached, i will test it.
>
>
Re: Cassandra in memory key index
Posted by Pavel Yaskevich <po...@gmail.com>.
Yeah, that is why I wrote "if possible" :) Also, does FST provide a predecessor lookup function, wasn't clear from the blog post?
On Friday 8 June 2012 at 22:53, Jason Rutherglen wrote:
> Yeah that's fine, however if there isn't a Java implementation that's a lot
> of extra work. The FST approach should be a clear quick and easy win. The
> current system of in heap keys and a binary search is what the FST replaced
> in Lucene. There are plenty of references to the improvement.
>
> On Fri, Jun 8, 2012 at 3:50 PM, Pavel Yaskevich <povel.y@gmail.com (mailto:povel.y@gmail.com)> wrote:
>
> > I would vote, if possible, to compare it with y-fast trie [1] (it doesn't
> > seem to be available java implementation unfortunately) by means of memory
> > efficiency and lookup performance. As we use big integer tokens the main
> > benefit from that trie could be O(log log M) predecessor lookup and compact
> > in-memory size.
> >
> > [1] https://en.wikipedia.org/wiki/Y-fast_trie
> >
> > Best Regards
> > --
> > Pavel Yaskevich
> >
> >
> > On Friday 8 June 2012 at 22:19, Jason Rutherglen wrote:
> >
> > > Ok looks like the IndexSummary encapsulates everything, I can start with
> > > hacking that.
> > >
> > > On Fri, Jun 8, 2012 at 11:50 AM, Jason Rutherglen <
> > > jason.rutherglen@gmail.com (mailto:jason.rutherglen@gmail.com)> wrote:
> > >
> > > > The Cassandra integration is probably beyond the time I have available.
> > > > If the locations in the code that need to be rewritten to use the FST
> > > >
> > >
> > >
> >
> > are
> > > > known, and a patch simply 'plugs-in' the FST, that would be much
> > >
> >
> > easier.
> > > > Eg, I don't know how Cassandra stores the current key index for
> > >
> >
> > example...
> > > >
> > > > Basically I can write FST serializing, deserializing, and key lookup
> > code
> > > > fairly easy by basing it on Lucene's terms dict.
> > > >
> > > >
> > > > On Fri, Jun 8, 2012 at 6:00 AM, Radim Kolar <hsn@filez.com (mailto:hsn@filez.com) (mailto:
> > hsn@filez.com (mailto:hsn@filez.com))> wrote:
> > > >
> > > > >
> > > > > If you are interested I can help, I used the FST on a Hadoop project
> > > > > > to implement a fast map side range join.
> > > > >
> > > > >
> > > > > create JIRA item with patch attached, i will test it.
Re: Cassandra in memory key index
Posted by Jason Rutherglen <ja...@gmail.com>.
Yeah that's fine, however if there isn't a Java implementation that's a lot
of extra work. The FST approach should be a clear quick and easy win. The
current system of in heap keys and a binary search is what the FST replaced
in Lucene. There are plenty of references to the improvement.
On Fri, Jun 8, 2012 at 3:50 PM, Pavel Yaskevich <po...@gmail.com> wrote:
> I would vote, if possible, to compare it with y-fast trie [1] (it doesn't
> seem to be available java implementation unfortunately) by means of memory
> efficiency and lookup performance. As we use big integer tokens the main
> benefit from that trie could be O(log log M) predecessor lookup and compact
> in-memory size.
>
> [1] https://en.wikipedia.org/wiki/Y-fast_trie
>
> Best Regards
> --
> Pavel Yaskevich
>
>
> On Friday 8 June 2012 at 22:19, Jason Rutherglen wrote:
>
> > Ok looks like the IndexSummary encapsulates everything, I can start with
> > hacking that.
> >
> > On Fri, Jun 8, 2012 at 11:50 AM, Jason Rutherglen <
> > jason.rutherglen@gmail.com (mailto:jason.rutherglen@gmail.com)> wrote:
> >
> > > The Cassandra integration is probably beyond the time I have available.
> > > If the locations in the code that need to be rewritten to use the FST
> are
> > > known, and a patch simply 'plugs-in' the FST, that would be much
> easier.
> > > Eg, I don't know how Cassandra stores the current key index for
> example...
> > >
> > > Basically I can write FST serializing, deserializing, and key lookup
> code
> > > fairly easy by basing it on Lucene's terms dict.
> > >
> > >
> > > On Fri, Jun 8, 2012 at 6:00 AM, Radim Kolar <hsn@filez.com (mailto:
> hsn@filez.com)> wrote:
> > >
> > > >
> > > > If you are interested I can help, I used the FST on a Hadoop project
> > > > > to implement a fast map side range join.
> > > >
> > > > create JIRA item with patch attached, i will test it.
> > > >
> > >
> > >
> >
> >
> >
>
>
>
Re: Cassandra in memory key index
Posted by Pavel Yaskevich <po...@gmail.com>.
I would vote, if possible, to compare it with y-fast trie [1] (it doesn't seem to be available java implementation unfortunately) by means of memory efficiency and lookup performance. As we use big integer tokens the main benefit from that trie could be O(log log M) predecessor lookup and compact in-memory size.
[1] https://en.wikipedia.org/wiki/Y-fast_trie
Best Regards
--
Pavel Yaskevich
On Friday 8 June 2012 at 22:19, Jason Rutherglen wrote:
> Ok looks like the IndexSummary encapsulates everything, I can start with
> hacking that.
>
> On Fri, Jun 8, 2012 at 11:50 AM, Jason Rutherglen <
> jason.rutherglen@gmail.com (mailto:jason.rutherglen@gmail.com)> wrote:
>
> > The Cassandra integration is probably beyond the time I have available.
> > If the locations in the code that need to be rewritten to use the FST are
> > known, and a patch simply 'plugs-in' the FST, that would be much easier.
> > Eg, I don't know how Cassandra stores the current key index for example...
> >
> > Basically I can write FST serializing, deserializing, and key lookup code
> > fairly easy by basing it on Lucene's terms dict.
> >
> >
> > On Fri, Jun 8, 2012 at 6:00 AM, Radim Kolar <hsn@filez.com (mailto:hsn@filez.com)> wrote:
> >
> > >
> > > If you are interested I can help, I used the FST on a Hadoop project
> > > > to implement a fast map side range join.
> > >
> > > create JIRA item with patch attached, i will test it.
> > >
> >
> >
>
>
>
Re: Cassandra in memory key index
Posted by Jason Rutherglen <ja...@gmail.com>.
Ok looks like the IndexSummary encapsulates everything, I can start with
hacking that.
On Fri, Jun 8, 2012 at 11:50 AM, Jason Rutherglen <
jason.rutherglen@gmail.com> wrote:
> The Cassandra integration is probably beyond the time I have available.
> If the locations in the code that need to be rewritten to use the FST are
> known, and a patch simply 'plugs-in' the FST, that would be much easier.
> Eg, I don't know how Cassandra stores the current key index for example...
>
> Basically I can write FST serializing, deserializing, and key lookup code
> fairly easy by basing it on Lucene's terms dict.
>
>
> On Fri, Jun 8, 2012 at 6:00 AM, Radim Kolar <hs...@filez.com> wrote:
>
>>
>> If you are interested I can help, I used the FST on a Hadoop project
>>> to implement a fast map side range join.
>>>
>> create JIRA item with patch attached, i will test it.
>>
>
>
Re: Cassandra in memory key index
Posted by Jason Rutherglen <ja...@gmail.com>.
The Cassandra integration is probably beyond the time I have available. If
the locations in the code that need to be rewritten to use the FST are
known, and a patch simply 'plugs-in' the FST, that would be much easier.
Eg, I don't know how Cassandra stores the current key index for example...
Basically I can write FST serializing, deserializing, and key lookup code
fairly easy by basing it on Lucene's terms dict.
On Fri, Jun 8, 2012 at 6:00 AM, Radim Kolar <hs...@filez.com> wrote:
>
> If you are interested I can help, I used the FST on a Hadoop project
>> to implement a fast map side range join.
>>
> create JIRA item with patch attached, i will test it.
>
Re: Cassandra in memory key index
Posted by Radim Kolar <hs...@filez.com>.
> If you are interested I can help, I used the FST on a Hadoop project
> to implement a fast map side range join.
create JIRA item with patch attached, i will test it.
Re: Cassandra in memory key index
Posted by Jason Rutherglen <ja...@gmail.com>.
Seems like a good place to try out Lucene's FST [1] data structure
which would enable more keys to be loaded into RAM (for more granular
seeks), along with their positions. Lucene uses this for the terms
dictionary and it's use made for nice gains in the efficiency of the
terms dictionary. The efficiency gains are potentially much better if
the FST were used in Cassandra?
This is an example of how it is used [2]. Not only is the memory
usage very efficient because it's a single byte[], the keys are
compressed as well as the position value.
If you are interested I can help, I used the FST on a Hadoop project
to implement a fast map side range join.
1. http://blog.mikemccandless.com/2010/12/using-finite-state-transducers-in.html
2. https://github.com/apache/lucene-solr/blob/trunk/lucene/core/src/java/org/apache/lucene/codecs/VariableGapTermsIndexReader.java
On Wed, Jun 6, 2012 at 12:05 PM, Jonathan Ellis <jb...@gmail.com> wrote:
> Implementation is in IndexSummary.java; the core is
>
> private final ArrayList<Long> positions;
> private final ArrayList<DecoratedKey> keys;
>
> So no, nothing fancy like prefix compression.
>
> On Wed, Jun 6, 2012 at 11:00 AM, Jason Rutherglen
> <ja...@gmail.com> wrote:
>> I am wondering how this is currently implemented? Is there prefix compression?
>
>
>
> --
> Jonathan Ellis
> Project Chair, Apache Cassandra
> co-founder of DataStax, the source for professional Cassandra support
> http://www.datastax.com
Re: Cassandra in memory key index
Posted by Jonathan Ellis <jb...@gmail.com>.
Implementation is in IndexSummary.java; the core is
private final ArrayList<Long> positions;
private final ArrayList<DecoratedKey> keys;
So no, nothing fancy like prefix compression.
On Wed, Jun 6, 2012 at 11:00 AM, Jason Rutherglen
<ja...@gmail.com> wrote:
> I am wondering how this is currently implemented? Is there prefix compression?
--
Jonathan Ellis
Project Chair, Apache Cassandra
co-founder of DataStax, the source for professional Cassandra support
http://www.datastax.com