[
https://issues.apache.org/jira/browse/AVRO-27?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12707454#action_12707454
]
Todd Lipcon commented on AVRO-27:
---------------------------------
If the Java performance of byte-by-byte processing is the major issue, is it
worth considering native code to optimize this? I don't generally like using
native code, but I feel like it may be worth it if the advantages of COBS are
significant enough.
On a side note, I recently read a paper that added a JVM optimization to really
improve element-by-element processing of arrays by automatically eliminating
bounds checking. I imagine that would apply here. Unfortunately, basing a
system around a JVM that doesn't exist yet isn't so wise ;-) But down the road
this performance issue may be ameliorated.
> Consistent Overhead Byte Stuffing (COBS) encoded block format for Object
> Container Files
> ----------------------------------------------------------------------------------------
>
> Key: AVRO-27
> URL: https://issues.apache.org/jira/browse/AVRO-27
> Project: Avro
> Issue Type: New Feature
> Components: spec
> Reporter: Matt Massie
>
> Object Container Files could use a 1 byte sync marker (set to zero) using
> zig-zag and COBS encoding within blocks to efficiently escape zeros from the
> record data.
> h4. Zig-Zag encoding
> With zig-zag encoding only the value of 0 (zero) gets encoded into a value
> with a single zero byte. This property means that we can write any non-zero
> zig-zag long inside a block within concern for creating an unintentional sync
> byte.
> h4. COBS encoding
> We'll use COBS encoding to ensure that all zeros are escaped inside the block
> payload. You can read http://www.sigcomm.org/sigcomm97/papers/p062.pdf for
> the details about COBS encoding.
> h1. Block Format
> All blocks start and end with a sync byte (set to zero) with a
> type-length-value format internally as follows:
> || name || format || length in bytes || value || meaning ||
> | sync | byte | 1 | always 0 (zero) | The sync byte serves as a clear marker
> for the start of a block |
> | type | zig-zag long | variable | must be non-zero | The type field
> expresses whether the block is for _metadata_ or _normal_ data. |
> | length | zig-zag long | variable | must be non-zero | The length field
> expresses the number of bytes until the next record (including the cobs code
> and sync byte). Useful for skipping ahead to the next block. |
> | cobs_code | byte | 1 | see COBS code table below | Used in escaping zeros
> from the block payload |
> | payload | cobs-encoded | Greater than or equal to zero | all non-zero bytes
> | The payload of the block |
> | sync | byte | 1 | always 0 (zero) | The sync byte serves as a clear marker
> for the end of the block |
> h2. COBS code table
> || Code || Followed by || Meaning |
> | 0x00 | (not applicable) | (not allowed ) |
> | 0x01 | nothing | Empty payload followed by the closing sync byte |
> | 0x02 | one data byte | The single data byte, followed by the closing sync
> byte |
> | 0x03 | two data bytes | The pair of data bytes, followed by the closing
> sync byte |
> | 0x04 | three data bytes | The three data bytes, followed by the closing
> sync byte |
> | n | (n-1) data bytes | The (n-1) data bytes, followed by the closing sync
> byte |
> | 0xFD | 252 data bytes | The 252 data bytes, followed by the closing sync
> byte |
> | 0xFE | 253 data bytes | The 253 data bytes, followed by the closing sync
> byte |
> | 0xFF | 254 data bytes | The 254 data bytes *not* followed by a zero. |
> (taken from http://www.sigcomm.org/sigcomm97/papers/p062.pdf)
> h1. Encoding
> Only the block writer needs to perform byte-by-byte processing to encode the
> block. The overhead for COBS encoding is very small in terms of the
> in-memory state required.
> h1. Decoding
> Block readers are not required to do as much byte-by-byte processing as a
> writer. The reader could (for example) find a _metadata_ block by doing the
> following:
> # Search for a zero byte in the file which marks the start of a record
> # Read and zig-zag decode the _type_ of the block
> #* If the block is _normal_ data, read the _length_, seek ahead to the next
> block and goto step #2 again
> #* If the block is a _metadata_ block, cobs decode the data
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
