[Hadoop-common-dev] Redundant (?) lengths in SequenceFile

This permits code to process entries without parsing them, an important
optimization. For example, when seeking a MapFile, keys are parsed but
not values. When sorting, if a comparator is defined that can compare
raw binary data, then even keys are not parsed.

Doug

How can I define a comparator that can compare raw binary data? (our keys
are raw binary data)

Implement the following method:

http://lucene.apache.org/hadoop/docs/api/org/apache/hadoop/io/WritableComparator.html#compare(byte[],%20int,%20int,%20byte[],%20int,%20int)

To make a comparator the default for a class, call:

http://lucene.apache.org/hadoop/docs/api/org/apache/hadoop/io/WritableComparator.html#define(java.lang.Class,%20org.apache.hadoop.io.WritableComparator)

This is already done for most WritableComparable implementations. The
the bottom of, e.g., IntWritable.java for an example of the idiom.

http://svn.apache.org/viewvc/lucene/hadoop/trunk/src/java/org/apache/hadoop/io/IntWritable.java?view=markup

Doug

Paul,
Look at what I did for BytesWritable (lines 147-165). You need to
define a Comparator class and register it with WritableComparable.

-- Owen

Can we turn this around and assume that writables will be given a
stream and a length when they read? That would also let us remove
redundant info...

Unless I misunderstand, that would make it harder to nest writables,
since all containers would need to store the length. Currently only
top-level containers (SequenceFile and the RPC protocol) need to write
lengths. Even these are optional, used only to optimize things.

Doug

I agree, there's no easy way around this one without separate interfaces
(one where the caller keeps the counts, and one where the writable keeps the
counts), and that would be silly.

However -> It still seems to me that the key length in the sequence file is
redundant. Since each key must write its own length, know its own length,
or be able to figure it out - even via the high speed interface - there's no
reason to have that key length in the file.

Why do I care about 4 bytes per record? Because we're integrating an
external sort, and right now it has to look at a record with two key
lengths. And I assume that others (such as Yahoo) will want to incorporate
an external sort. And if we're going to be reading the sequence file in
another language, we might as well be sure about the format to use.

Thanks!

Paul

What if your keys are compound, containing, say, a combination of
floats, ints and strings? Then the key may not include a length of the
entire key entry. So you're seeking to optimize a special (if common) case.

Doug

its fine either way, i just wanted to know that its deleberate. it certainly
doesnt cost much space.

an external sorter can work only on keytypes it understands, and our keys
are compound and may include strings, floats, and ints.

the length is no problem at all.

Yikes, but this assumes that your external code can grock whatever
strange thing is stored in the writable. This is a non-trivial
assumption when you go multi-lingual.

We're going to take a crack at a block compressed format soon. This
will vastly reduce the storage impact of this kind of issue anyway.