Object Container Files format questions

[Matt Massie <ma...@cloudera.com>]

Hello Avro developers-

Forgive me if I'm (re)opening questions that have already been discussed.

I'd like to understand the design decisions that went into the Avro Object
Container Files format.

(1) Why is a meta block not required to immediately follow the header?  It
seems counter-intuitive to me that the requirement is for a meta block at
the end of the file.  I would expect that we would want the reader to know
the meta data before any data blocks are sent (especially if you want to
transfer/decode a file on the fly over the wire).

(2) Why are we using a 16-byte UUID block delimiter to mark block boundaries
instead of using say Consistent Overhead Byte Stuffing (COBS)?

The paper on COBS can be found at
http://www.sigcomm.org/sigcomm97/papers/p062.pdf including some nice C code
at the end for encoding/decoding records (it's easy to find Java code for
COBs too).

A COBS-based block format might look like the following

delimiter     (a single byte set to 0)
type            (a non-zero zig-zag long that expresses the record type)
length         (a non-zero zig-zag long the expresses the length of the
record)
cobs_code  (a single byte used to help encode/decode the payload)
...                (cobs encoded data)

The nice thing about zig-zag longs is that non-zero values will never be
encoded with a single zero byte (correct?).  This allows us to keep the
simple 1 byte delimiter/record boundary (set to zero).  Since the record
type and length are not COBS encoded, we can quickly scan a
file/socket/memory for the next record boundary and easily know the payload
type and length (to decide whether to process or skip the record).  COBs
also allows for in-place encoding and decoding with very little overhead and
copying (see the paper for test results).

It make more sense to make that we use the same record boundary (0) for all
Avro records instead of having them be random.  The format would be more
resilient to data corruption easier to parse.  It's also possible (although
improbable) that the 16-byte UUID might be part of the payload... especially
given the size of the data Hadoop processes.

-Matt

Re: Object Container Files format questions

[Matt Massie <ma...@cloudera.com>]

I've opened..

https://issues.apache.org/jira/browse/AVRO-27

in order to discuss the potential of a COBS encoded container.  Jira let's
me make pretty tables to express the format.  :)

-Matt


On Mon, May 4, 2009 at 10:43 AM, Doug Cutting <cu...@apache.org> wrote:

> Matt Massie wrote:
>
>> (1) Why is a meta block not required to immediately follow the header?  It
>> seems counter-intuitive to me that the requirement is for a meta block at
>> the end of the file.  I would expect that we would want the reader to know
>> the meta data before any data blocks are sent (especially if you want to
>> transfer/decode a file on the fly over the wire).
>>
>
> I wanted to support append. The idea is that the meta-block is written each
> time the file is flushed, and that the file is valid through the last
> meta-block.  If a program crashes without flushing, then the file might be
> truncated to its last meta-block, and then new data could be appended.
>
> I did not have streaming in mind.  The meta-block was intended to be
> retroactive.  I contains the total number of entries.  If the file's schema
> is a union, one might add new entries into the union as the file is written,
> as new types are added, writing the full union when the file is flushed.
>
> To better ssupport streaming we might require that the metadata be written
> every so many bytes, so that a streaming application could buffer until it
> sees a metadata entry, then process the buffered items.  Could that work?
>  Note that automatic periodic metadata writes would also facilitate crash
> recovery, since one would know how far from the end of the file to begin
> scanning.
>
>  (2) Why are we using a 16-byte UUID block delimiter to mark block
>> boundaries
>> instead of using say Consistent Overhead Byte Stuffing (COBS)?
>>
>
> In part because I didn't yet know about COBS when I implemented this
> container.  (You're the second person to ask this.)  Perhaps we should
> instead use COBS.  The only potential disadvantage I see is that COBS seems
> to require byte-by-byte processing.  When projecting records to a subset
> schema, we've seen huge speedups if we skip through data by chunks, passing
> over strings, blobs, etc. just incrementing the file pointer.  So I worry
> that COBS, while quite fast, might add a significant cost to such skipping.
>  Compression also requires byte-by-byte processing, but provides more
> tangible value than COBS.  So COBS would need to add truly negligible CPU
> overhead, which it might.
>
>  COBs
>> also allows for in-place encoding and decoding with very little overhead
>> and
>> copying (see the paper for test results).
>>
> [ ... ]
>
> Thanks for all your COBS analysis!  It does seem attractive.  Skimming the
> paper, I see mostly space overhead benchmarks, not CPU overhead.  In
> projection benchmarks, we saw a 4x speedup from just skipping strings.
> AVRO-25 proposes to make entire arrays and maps skippable, which should,
> e.g., speed the projection of a single field from large, complex records by
> 10x or more.  But if compression is always used, perhaps the right
> comparison is with something like LZO.  If COBS is negligible next to LZO,
> that could be good enough.
>
> Hopefully we'll develop a benchmark suite for Avro that includes projection
> & compression, so we can more easily evaluate things like this.
>
> Doug
>

Re: Object Container Files format questions : COBS performance proposal

[Scott Carey <sc...@richrelevance.com>]

I have read the COBS paper, and I propose modifications to COBS to (likely)
make it significantly faster and fit the Hadoop use case better below.
When I first skimmed the paper, I identified the same issues that Doug did
-- particularly that it is a byte-by-byte encoding.  Java is SLOW at
byte-by-byte anything.  The JIT compilers in Java haven't really optimized
byte-by-byte work well -- compared to a C compiler.

I just saw that Matt Massie opened a JIRA ticket for this, so I'll leave the
bulk of the details for that and send what I have written so far below.

Initial comments inline below, with a summary at the end.  JIRA details
later.

On 5/4/09 10:43 AM, "Doug Cutting" <cu...@apache.org> wrote:

> Matt Massie wrote:
>> (2) Why are we using a 16-byte UUID block delimiter to mark block boundaries
>> instead of using say Consistent Overhead Byte Stuffing (COBS)?
> 
> In part because I didn't yet know about COBS when I implemented this
> container.  (You're the second person to ask this.)  Perhaps we should
> instead use COBS.  The only potential disadvantage I see is that COBS
> seems to require byte-by-byte processing.  When projecting records to a
> subset schema, we've seen huge speedups if we skip through data by
> chunks, passing over strings, blobs, etc. just incrementing the file
> pointer.  So I worry that COBS, while quite fast, might add a
> significant cost to such skipping.  Compression also requires
> byte-by-byte processing, but provides more tangible value than COBS.  So
> COBS would need to add truly negligible CPU overhead, which it might.

If its going byte by byte, its a performance risk for the low overhead, high
throughput case.  Perhaps a test using a ByteBuffer and simply counting the
number of zero values encountered would be a useful (prevents dead code
elimination).

One could compare this to something similar with IntBuffer or LongBuffer,
counting the occurances of zero values there.

> 
>> COBs
>> also allows for in-place encoding and decoding with very little overhead and
>> copying (see the paper for test results).
> [ ... ]
> 
> Thanks for all your COBS analysis!  It does seem attractive.  Skimming
> the paper, I see mostly space overhead benchmarks, not CPU overhead.  In
> projection benchmarks, we saw a 4x speedup from just skipping strings.
> AVRO-25 proposes to make entire arrays and maps skippable, which should,
> e.g., speed the projection of a single field from large, complex records
> by 10x or more.  But if compression is always used, perhaps the right
> comparison is with something like LZO.  If COBS is negligible next to
> LZO, that could be good enough.
> 

First, I do suspect that compression will be common.  But there will be very
important non-compressed use cases as well.

Next, even if it is roughly on par with LZO, that is too slow.  It would
have to be a couple times faster than LZO to have minimal CPU impact.  A
fast checksum operation is a few times faster than LZO.  A big reason for
that is that you do most checksums on 32 bit or 64 bit chunks.

LZO is also "slow".  Google mentions a compression scheme for BigTable that
is faster than LZO:

From the Google BigTable whitepaper (2006):
" Many clients use a two-pass custom
compression scheme. The first pass uses Bentley and
McIlroy’s scheme [6], which compresses long common
strings across a large window. The second pass uses a
fast compression algorithm that looks for repetitions in
a small 16 KB window of the data. Both compression
passes are very fast—they encode at 100–200 MB/s, and
decode at 400–1000 MB/s on modern machines "

LZO and its similar schemes are somewhat slower, especially in Java:
http://quicklz.com/

Sun's lzjb compression in ZFS claims to be a bit faster (benchmarks seem to
put it in the neighborhood of lzo, and they are related algorithms):
http://src.opensolaris.org/source/xref/onnv/onnv-gate/usr/src/uts/common/os/
compress.c

In short, if you want fast streaming for Java, I suspect COBS won't work in
the byte-by-byte form in the paper.  However ...

> Hopefully we'll develop a benchmark suite for Avro that includes
> projection & compression, so we can more easily evaluate things like this.
> 
> Doug
> 

COBS has fantastic properties.
My proposal is to essentially go from COBS to COWS or COLS.  Constant
Overhead Word Stuffing or Constant Overhead Long Stuffing.  The properties
of COBS all carry over with larger chunks, just faster.

Java may not compile efficient byte-by-byte operations, but it does pretty
well with 32 bit or 64 bit chunks.  My proposal is essentially to do almost
the same thing as COBS, but in 32 or 64 bit chunks.  This should be
efficient in many languages. Eyeballing the future, it should probably be 64
bit chunks.  Sun is about to release JVM 1.6.0_14 which has pointer
compression, and 64 bit JVMs will perform better than 32 bit ones on x86-64
with nearly the same memory overhead.
When scanning for the beginning of a 'packet', one can do so looking for a
zero WORD or LONG rather than a zero BYTE.

There are drawbacks to this, I'll address in the JIRA.  There are many ways
to handle them however and one can reduce overhead to a maximum of 16 bits.
Since we expect most hadoop related streams to be larger than the design
goals of COBS, we probably want to encode longer runs to 'skip' more data at
a time and can afford more overhead per packet.
The truth is, if we had access to SSE instructions, you'd probably do this
128 bits at a time and approach a few GB/sec in memory on newer hardware.

The COBS paper seems to target network protocols and low level network
devices and hardware, which already operate one byte at a time and would not
have a performance problem from that aspect of it.

Re: Object Container Files format questions

[Doug Cutting <cu...@apache.org>]

Matt Massie wrote:
> (1) Why is a meta block not required to immediately follow the header?  It
> seems counter-intuitive to me that the requirement is for a meta block at
> the end of the file.  I would expect that we would want the reader to know
> the meta data before any data blocks are sent (especially if you want to
> transfer/decode a file on the fly over the wire).

I wanted to support append. The idea is that the meta-block is written 
each time the file is flushed, and that the file is valid through the 
last meta-block.  If a program crashes without flushing, then the file 
might be truncated to its last meta-block, and then new data could be 
appended.

I did not have streaming in mind.  The meta-block was intended to be 
retroactive.  I contains the total number of entries.  If the file's 
schema is a union, one might add new entries into the union as the file 
is written, as new types are added, writing the full union when the file 
is flushed.

To better ssupport streaming we might require that the metadata be 
written every so many bytes, so that a streaming application could 
buffer until it sees a metadata entry, then process the buffered items. 
  Could that work?  Note that automatic periodic metadata writes would 
also facilitate crash recovery, since one would know how far from the 
end of the file to begin scanning.

> (2) Why are we using a 16-byte UUID block delimiter to mark block boundaries
> instead of using say Consistent Overhead Byte Stuffing (COBS)?

In part because I didn't yet know about COBS when I implemented this 
container.  (You're the second person to ask this.)  Perhaps we should 
instead use COBS.  The only potential disadvantage I see is that COBS 
seems to require byte-by-byte processing.  When projecting records to a 
subset schema, we've seen huge speedups if we skip through data by 
chunks, passing over strings, blobs, etc. just incrementing the file 
pointer.  So I worry that COBS, while quite fast, might add a 
significant cost to such skipping.  Compression also requires 
byte-by-byte processing, but provides more tangible value than COBS.  So 
COBS would need to add truly negligible CPU overhead, which it might.

> COBs
> also allows for in-place encoding and decoding with very little overhead and
> copying (see the paper for test results).
[ ... ]

Thanks for all your COBS analysis!  It does seem attractive.  Skimming 
the paper, I see mostly space overhead benchmarks, not CPU overhead.  In 
projection benchmarks, we saw a 4x speedup from just skipping strings. 
AVRO-25 proposes to make entire arrays and maps skippable, which should, 
e.g., speed the projection of a single field from large, complex records 
by 10x or more.  But if compression is always used, perhaps the right 
comparison is with something like LZO.  If COBS is negligible next to 
LZO, that could be good enough.

Hopefully we'll develop a benchmark suite for Avro that includes 
projection & compression, so we can more easily evaluate things like this.

Doug