File format

[mdnahas]

Hi @darrenldl,

I'm the designer of Parchive version 2, a.k.a. ".par2". I'm looking around for ideas for version 3. @MarcoPon told me about your project, when I asked him about SeqBox.

Do you have a description of the file format for blockyarchive?
(And if you have any comments/recommendations about Parchive, I'm glad to hear those too!)

Mike Nahas

[darrenldl]

Hey hi! Fancy meeting core par2 people here : D! Parchive2 was one of the projects I kept referencing to when making blkar.

The ecsbx format is available at: https://github.com/darrenldl/blockyarchive/blob/master/SBX_FORMAT.md#for-ecsbx-versions-17-0x11-18-0x12-19-0x13 , I will say it is probably of limited use though, as a lot of this "interleaving" was for working around the restriction of GF8 for the case of burst damage, but parchive uses GF16 iirc(?) for the Reed-Solomon encoding.

One issue that popped up after some time using it was that sbx (and thus ecsbx) does not lend itself to streaming use, since the checksum is stored in the header in the first block in the standard layout. I am interested in creating a successor, and also eyeing at encodings other than Reed-Solomon.

I'm highly curious about your plan! In particular what objectives you have for par3 and whether you intend to stick with RS encoding, and if that was ever a bottleneck in terms of performance (there have been majorly accelerated GF code cropping up in past couple of years, so maybe not a concern for par3 in general scenario).

[mdnahas]

Hey Darren,

So, I have a lot of goals for Par3. I started a discussion a year ago but got distracted. I'll give you a summary, but if you want the public discussion, it is here: Parchive/par2cmdline#130

The big goal is to make Par3 work with any linear code. That means it will work with Reed Solomon, but also Tornado codes and other LDPC. It will even support future codes that researchers might create. I actually like the idea of using just a random sparse matrix, which should run quickly and provide very good redundancy on average.

Other changes include: Support any galois field that aligns on byte boundaries. (Processors have support for GF(2^8), GF(2^64) and Intel has a whitepaper for GF(2^128).) Replace MD5 with a faster, more secure hashcode. (Probably K12.) Support single-pass recovery, by putting hints in Par3 file. Support putting Par3 recovery data inside another file format, like a ZIP file, so a single file can work as a ZIP file and contains data to repair itself!

Those are some of the goals. As I thought about the problem, I realized there are really a number of layers to creating a Parchive backup file. The layers seem to be:

1. Encode metadata (like permissions) as normal data
2. Calculate checksums for file data and metadata
3. If this is an incremental backup, diff the files with their previous versions
4. Merge multiple files/diffs into a single file
5. [optional] Compression
6. [optional] Encryption
7. Compute redundant data
8. Split the file into multiple files for storage/transmission

I don't want Parchive to touch encryption. It is hard to do well and it might change over time. I think Parchive should also avoid compression, which other programs can do better and might change over time or by application. So, my current plan is to create two different file formats, one for the layers 1 thru 4 and one for the layers 7 and 8. I've got a basic design for the file format that combines layers 7 and 8. I'm currently thinking about layers 1 through 4, and if you have any thoughts there, I'd love to hear them.

I had hoped to reuse an existing archive format, like TAR or ZIP or something. But they are old and complex and have many faults. I think the world needs a newer, simpler format. I had thought of some features and then ran into SeqBox. It isn't quite right for Parchive, but I do like that it is resilient under damage. That's a feature that Parchive users would like.

I'm also thinking about other uses for Parchive besides transmission redundancy and backups. Perhaps it would be good to act as a redundant filesystem? Wouldn't it be cool to mount a Parchive file with FUSE?

Anyway, let me know if you have any thoughts about Parchive3. I'd love to hear them.

Mike

[darrenldl]

The linked issue was a long read~

I'm surprised Tornado code is not that efficient. I've been playing with Luby transform code, and while it seems good for traffic use, for storage purposes at high loss it does not seem very effective at small block count - I'll try with much larger block count and see what happens. I was going to try layering LT code and see if such chaining would be more effective, but I can't tell if it is worth the effort (this field of study is definitely beyond me).

I had hoped to reuse an existing archive format, like TAR or ZIP or something. But they are old and complex and have many faults. I think the world needs a newer, simpler format. I had thought of some features and then ran into SeqBox. It isn't quite right for Parchive, but I do like that it is resilient under damage. That's a feature that Parchive users would like.

What's the ideal archive format you want? Or maybe why isn't SeqBox quite right?

I'm also thinking about other uses for Parchive besides transmission redundancy and backups. Perhaps it would be good to act as a redundant filesystem? Wouldn't it be cool to mount a Parchive file with FUSE?

That would be extremely handy yes, a user has asked about that before. A FUSE driver seemed easy to implement on paper, but never gotten around to making one.

I'll see what I come up with, and possibly check with a user of blkar and see what he thinks.

[mdnahas]

SeqBox isn't right because it uses too small a hash and doesn't have a single hash for all files (i.e., one that makes sure you got all the files and they're correct.) It also has pretty high overhead for small files. (They must have a Block 0.)

If I was going to do a FUSE-able system, it needs a directory structure, so that they're is fast lookup. I actually think an append-only filesystem could be useful. (There is a research paper on one, but I'd have to pay to read it.) I like how ZIP files put the directory structure at the end of the file and it is possible to add new files to the archive by appending.