[
https://issues.apache.org/jira/browse/HBASE-4218?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13086650#comment-13086650
]
Jacek Migdal commented on HBASE-4218:
-------------------------------------
So far the implemented interface looks like:
{noformat}
/**
* Fast compression of KeyValue. It aims to be fast and efficient
* using assumptions:
* - the KeyValue are stored sorted by key
* - we know the structure of KeyValue
* - the values are iterated always forward from beginning of block
* - application specific knowledge
*
* It is designed to work fast enough to be feasible as in memory compression.
*/
public interface DeltaEncoder {
/**
* Compress KeyValues and write them to output buffer.
* @param writeHere Where to write compressed data.
* @param rawKeyValues Source of KeyValue for compression.
* @throws IOException If there is an error in writeHere.
*/
public void compressKeyValue(OutputStream writeHere, ByteBuffer rawKeyValues)
throws IOException;
/**
* Uncompress assuming that original size is known.
* @param source Compressed stream of KeyValues.
* @param decompressedSize Size in bytes of uncompressed KeyValues.
* @return Uncompressed block of KeyValues.
* @throws IOException If there is an error in source.
* @throws DeltaEncoderToSmallBufferException If specified uncompressed
* size is too small.
*/
public ByteBuffer uncompressKeyValue(DataInputStream source,
int decompressedSize)
throws IOException, DeltaEncoderToSmallBufferException;
}
{noformat}
I also need some kind of interface for iterating and seeking. I haven't got it
yet but would like to have something like:
{noformat}
public Iterator<KeyValue> getIterator(ByteBuffer encodedKeyValues);
public Iterator<KeyValue> getIteratorStartingFrom(ByteBuffer
encodedKeyValues, byte[] keyBuffer, int offset, int length);
{noformat}
For me it would work, but for you I might have changing it to something like:
{noformat}
public EncodingIterator getState(ByteBuffer encodedKeyValues);
class EncodingIterator implements Iterator<KeyValue> {
...
public void seekToBeginning();
public void seekTo(byte[] keyBuffer, int offset, int length);
{noformat}
I will figure out how we could share the code.
> Delta Encoding of KeyValues (aka prefix compression)
> -----------------------------------------------------
>
> Key: HBASE-4218
> URL: https://issues.apache.org/jira/browse/HBASE-4218
> Project: HBase
> Issue Type: Improvement
> Components: io
> Reporter: Jacek Migdal
> Labels: compression
>
> A compression for keys. Keys are sorted in HFile and they are usually very
> similar. Because of that, it is possible to design better compression than
> general purpose algorithms,
> It is an additional step designed to be used in memory. It aims to save
> memory in cache as well as speeding seeks within HFileBlocks. It should
> improve performance a lot, if key lengths are larger than value lengths. For
> example, it makes a lot of sense to use it when value is a counter.
> Initial tests on real data (key length = ~ 90 bytes , value length = 8 bytes)
> shows that I could achieve decent level of compression:
> key compression ratio: 92%
> total compression ratio: 85%
> LZO on the same data: 85%
> LZO after delta encoding: 91%
> While having much better performance (20-80% faster decompression ratio than
> LZO). Moreover, it should allow far more efficient seeking which should
> improve performance a bit.
> It seems that a simple compression algorithms are good enough. Most of the
> savings are due to prefix compression, int128 encoding, timestamp diffs and
> bitfields to avoid duplication. That way, comparisons of compressed data can
> be much faster than a byte comparator (thanks to prefix compression and
> bitfields).
> In order to implement it in HBase two important changes in design will be
> needed:
> -solidify interface to HFileBlock / HFileReader Scanner to provide seeking
> and iterating; access to uncompressed buffer in HFileBlock will have bad
> performance
> -extend comparators to support comparison assuming that N first bytes are
> equal (or some fields are equal)
> Link to a discussion about something similar:
> http://search-hadoop.com/m/5aqGXJEnaD1/hbase+windows&subj=Re+prefix+compression
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
