Fast navigation in binary gzip'ed file that includes messages of variable length

[Roman Vinogradov]

Hello,

I use protobuf to store events in playback file for further replaying.
I use Coded*Stream on top of Gzip*Stream which is on top of
File*Stream. The playback file is big enough, can be up to 3 GB a day
(hundreds of millions of events).
Everything works ok - all events encoded in the file can be replayed
back just fine.
Now I need to navigate through the playback (forth and back), kind of
rewinding.
I wanted to periodically insert special key frames that include such
information as byte offset of previous key frame (to rewind back) and
similar offset of the next key frame (to rewind forth), plus some
other key data. So I would navigate through the file faster by
skipping big portions of events between such key frames.
In order to maintain key frames linked each to other I need to move
back in the output buffer, modify previous key frame with correct
value of offset field and move forward to the initial position in
order to serialize next key frame and further events and so on. If
needed key frame can be of fixed size (e.g. sfixed64 types can be
used).
Reading and partial parsing of all events until good one is found is
not an option.

How is this possible with protobuf implementation? e.g.
CodedOutputStream::Skip(int count) doesn't accept negative count as a
parameter.

Perhaps there is alternate way to reach the goal - fast navigation in
the binary gzip'ed file that includes messages of variable length.
Any thoughts?

Thank you in advance.

/Roman

[Jason Hsueh]

In general protobuf doesn't try to provide these kinds of container formats. Gzip*Stream is meant to deal with data that is valid gzip; inserting frames to make it searchable would break the format. In the archives you may find other references to the internal container file format that Google has; this effectively has blocks of individual records, and it's possible to skip blocks or seek to a position (or the next valid record after a position). It sounds like you want something similar, with your events as the records, and each block as the 'key frames'. Rather than compressing the entire file, you could perform block level compression, and treat each individual record as a separate stream that can be decoded into your protobuf.

/Roman

--
You received this message because you are subscribed to the Google Groups "Protocol Buffers" group.
To post to this group, send email to prot...@googlegroups.com.
To unsubscribe from this group, send email to protobuf+u...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/protobuf?hl=en.

[Igor Gatis]

Similarly to what Jason suggested, you may have summary blocks which
lets you quick inspect value ranges. Like:

message Record {
optional int id = 1;
  //  fields only you know about.
}

message RecordBlock {
  repeated Record record = 1; // You could declare these as 'bytes' type
// instead of 'Record'
type. This avoids parsing
// each Record if you're
not going to use it.
optional int max_id = 2;
optional int min_id = 3;
}

message RecordsFile {
  repeated RecordBlock raw_blocks = 1; // Readly available RecordBlock.
  repeated bytes gziped_blocks = 2; // Gzip encoded RecordBlock.
  repeated bytes other_encoding_blocks = 3; // Other encoded RecordBlock.
}

You may use RecordsFile to append records to your file. For parsing,
you can use CodedInputStream.

[Eyal Farago]

you can use an approach like HADDOP's TFile https://issues.apache.org/jira/secure/attachment/12396286/TFile%20Specification%2020081217.pdf

basically they store compressed chunks in a file, and at the end of the file (hence T(ail)File) they store come kind of a sparse index to the chunks.

Eyal.

[Roman Vinogradov]

Thank you all.
I think TFile is very similar to what I am trying to do.
One issue of TFile is that it stores all meta and indices in its tail
which in turn means that if the writing process suddenly crashes for
some reason (e.g. hardware issue or something not related to our
process) then file will be of incomplete format and it won't be
possible to read it or even recover it.

/Roman

On 17 май, 10:28, Eyal Farago <eyal.far...@gmail.com> wrote:
> you can use an approach like HADDOP's TFilehttps://issues.apache.org/jira/secure/attachment/12396286/TFile%20Spe...

>
> basically they store compressed chunks in a file, and at the end of the
> file (hence T(ail)File) they store come kind of a sparse index to
> the chunks.
>
> Eyal.
>
>
>

> - Скрыть цитируемый текст -
>
> - Показать цитируемый текст -

[Igor Gatis]

Is a separate index file an option? You could build main file and this index file. If one file only is desirable, you can prepend or append index later.

--
You received this message because you are subscribed to the Google Groups "Protocol Buffers" group.

[Eyal Farago]

a separate file only makes things worse as you have to deal with the possibility of corruption in either one of the files or both...

I think a better approach is to start with the TFile format, prefix each chunk in the file (sorry, it;s been some time since my last read about this interesting format) with its length, then write the mtd+index at the end when you close the file and add some kind of magic number /+ signature at the end. when you open the file, check the magic/signature/both, if it's valid you can trust the index to 'random access' blocks in the file, if it's not you can take the sequential path, based on the lengths that prefix each block in the file.

Eyal.

On Friday, May 18, 2012 7:05:38 PM UTC+3, Igor Gatis wrote:

Is a separate index file an option? You could build main file and this index file. If one file only is desirable, you can prepend or append index later.

On Thu, May 17, 2012 at 8:22 AM, Roman Vinogradov <...> wrote:

Thank you all.
I think TFile is very similar to what I am trying to do.
One issue of TFile is that it stores all meta and indices in its tail
which in turn means that if the writing process suddenly crashes for
some reason (e.g. hardware issue or something not related to our
process) then file will be of incomplete format and it won't be
possible to read it or even recover it.

/Roman

On 17 май, 10:28, Eyal Farago <...> wrote:
> you can use an approach like HADDOP's TFilehttps://issues.apache.org/jira/secure/attachment/12396286/TFile%20Spe...

>
> basically they store compressed chunks in a file, and at the end of the
> file (hence T(ail)File) they store come kind of a sparse index to
> the chunks.
>
> Eyal.
>
>
>

> - Скрыть цитируемый текст -
>
> - Показать цитируемый текст -

--
You received this message because you are subscribed to the Google Groups "Protocol Buffers" group.

To post to this group, send email to prot...@googlegroups.com.

To unsubscribe from this group, send email to protobuf+unsubscribe@googlegroups.com.

[Roman Vinogradov]

Yes, this is what I am thinking about too. I will use format similar
to TFile with some meta datas relevant to my problem.
If the file gets corrupted somewhere and index is not available then I
will be able to recover data before the place where corruption occurs
and build data index at least (if compression algorithm is known).
If I prefix each data chunk with magic number too we would not need to
take care of possible invalid reads at the end (if magic number is
missing at the beginning of the chunk then it is not data to read any
longer).
This scheme is quite good to be used with protobuf encoding.
Thank you.

/Roman

On 20 май, 09:40, Eyal Farago <eyal.far...@gmail.com> wrote:
> a separate file only makes things worse as you have to deal with the
> possibility of corruption in either one of the files or both...
>
> I think a better approach is to start with the TFile format, prefix each
> chunk in the file (sorry, it;s been some time since my last read about this
> interesting format) with its length, then write the mtd+index at the end
> when you close the file and add some kind of magic number /+ signature at
> the end. when you open the file, check the magic/signature/both, if it's
> valid you can trust the index to 'random access' blocks in the file, if
> it's not you can take the sequential path, based on the lengths that prefix
> each block in the file.
>
> Eyal.
>
>
>
> On Friday, May 18, 2012 7:05:38 PM UTC+3, Igor Gatis wrote:
>
> > Is a separate index file an option? You could build main file and this
> > index file. If one file only is desirable, you can prepend or append index
> > later.
>

> > On Thu, May 17, 2012 at 8:22 AM, Roman Vinogradov <.<vinogradov.ro...@gmail.com>

> > ..> wrote:
>
> >> Thank you all.
> >> I think TFile is very similar to what I am trying to do.
> >> One issue of TFile is that it stores all meta and indices in its tail
> >> which in turn means that if the writing process suddenly crashes for
> >> some reason (e.g. hardware issue or something not related to our
> >> process) then file will be of incomplete format and it won't be
> >> possible to read it or even recover it.
>
> >> /Roman
>
> >> On 17 май, 10:28, Eyal Farago <...> wrote:
> >> > you can use an approach like HADDOP's TFilehttps://
> >> issues.apache.org/jira/secure/attachment/12396286/TFile%20Spe...
>
> >> > basically they store compressed chunks in a file, and at the end of the
> >> > file (hence T(ail)File) they store come kind of a sparse index to
> >> > the chunks.
>
> >> > Eyal.
>
> >> > - Скрыть цитируемый текст -
>
> >> > - Показать цитируемый текст -
>
> >> --
> >> You received this message because you are subscribed to the Google Groups
> >> "Protocol Buffers" group.
> >> To post to this group, send email to prot...@googlegroups.com.
> >> To unsubscribe from this group, send email to

> >> protobuf+u...@googlegroups.com.

> >> For more options, visit this group at

> >>http://groups.google.com/group/protobuf?hl=en.- Скрыть цитируемый текст -