Home | About | Sematext search-lucene.com search-hadoop.com
 Search Hadoop and all its subprojects:

Switch to Threaded View
HBase >> mail # dev >> prefix compression

Copy link to this message
Re: prefix compression
What about turning KeyValue into an interface with only the essential
getXX() methods?  Whatever is using the KeyValue shouldn't *have* to know
what sort of structure it's backed by, but could figure out the
implementation in cases where it wants to optimize performance.  Seems like
this is warranted right now just for the sake of breaking up such a huge
class... Possible implementations include:

new SimpleKeyValue(final byte[] row, final byte[] family,
      final byte[] qualifier, final long timestamp, Type type,
      final byte[] value) (separate fields, low performance, useful for

new ArrayKeyValue(byte[] bytes)

new SubArrayKeyValue(byte[] bytes, int offset, int length)

new BlockIndexKeyValue(BlockIndex blockIndex, int kvPosition)

new HFileKeyValue(HFileScanner scanner)

etc... where each implementation knows how to fish out the underlying data.
 Later we add more implementations:

new CssTreeBlockIndexKeyValue(CssTreeBlockIndex blockIndex, int kvPosition)
@Jason - i agree about starting with the block index since it's a relatively
isolated piece of code.  Could possibly be done without KeyValue
modifications.  Also, i think it could work without changing the HFile if
people are willing to let it compact the index when the HFile is read rather
than when the when it's written.  Would make for slightly slower startup
times but would save a lot of memory.  Could be configurable.
On Thu, Jun 2, 2011 at 4:44 PM, Jonathan Gray <[EMAIL PROTECTED]> wrote:

> I'm here!
> Still parsing through the stuff in this e-mail but I agree that many
> approaches will require rejiggering of KeyValue in a significant way.  I
> have made some attempts at this but nothing is very far.  It's definitely
> something that we are hoping to put some resources into over the summer.
> JG
> > -----Original Message-----
> > From: Todd Lipcon [mailto:[EMAIL PROTECTED]]
> > Sent: Thursday, June 02, 2011 3:37 PM
> > Subject: Re: prefix compression
> >
> > Hey Matt,
> >
> > Interesting email, and also something I've been thinking about recently.
> >
> > Unfortunately, I think one of the big prerequisites before we can start
> > thinking about actual compression algorithms is some refactoring around
> > how KeyValue is used. Currently, KeyValue exposes byte arrays in a lot of
> > places
> > - these byte arrays are expected to have discrete sub-ranges that
> represent
> > row key, column qualifier, etc. Various parts of the code directly grab
> these
> > byte arrays and offsets and do stuff with them (eg comparison,
> serialization,
> > etc).
> >
> > In order to split the different components up, or do true prefix
> compression,
> > we'd need to be able to have KeyValue do some smarter things for
> > comparison, and never call functions like "getBuffer), getRowKeyOffset(),
> > getRowKeyLength()" expecting that to show us a byte array range with a
> row
> > key in it.
> >
> > I think Jonathan Gray has some code hacked together for this, but last I
> > heard it wasn't in shippable state... Jonathan, you out there?
> >
> > As for the particular compression algorithms, a nice first step would be
> a very
> > simplistic one: the first row key of any HFile block would be given in
> full.
> > Following that, each key uses a single byte token which identifies the
> > number of key components shared with the previous row (ie same row,
> > same col, different ts). This isn't quite as good as true prefix
> compression,
> > but for common cases where each cell has three versions, and each row has
> > many columns, it's probably a huge savings.
> >
> > -Todd
> >
> > On Thu, Jun 2, 2011 at 3:28 PM, Matt Corgan <[EMAIL PROTECTED]>
> > wrote:
> >
> > > I've been reading up on prefix compression for a few weeks trying to
> > > figure out the best approach.  Maybe some of you have noticed that 90%
> > > of my emails to the user list have something to do with it...  Now
> > > that people are working on HFile v2 and the topic of Lucene's FST has