Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Mounting tar archives as a filesystem in WebAssembly

jeroen.github.io

Post reply on HN
Print view View original

11–20 of 42 posts

Re: Mounting tar archives as a filesystem in WebAssembly

#11

Post by nrclark »

johannes1234321 wrote: post #6
Ecco wrote: post #3

How about using a format that has actually been designed to be a compressed read-only filesystem? Something like a SquashFS or cramfs disk image?

When looking at established file formats, I'd start with zip for that usecase over tarballs. zip has compression and ability to access any file. A tarfule you have to uncompress first. SquashFS or cramps or such have less tooling, which makes the usage for generating, inspecting, ... more complex.

You only have to decompress it first if it's compressed (commonly using gzip, which is shown with the .gz suffix).

Otherwise, you can randomly access any file in a .tar as long as: - the file is seekable/range-addressible - you scan through it and build the file index first, either at runtime or in advance.

Uncompressed .tar is a reasonable choice for this application because the tools to read/write tar files are very standard, the file format is simple and well-documented, and it incurs no computational overhead.

Re: Mounting tar archives as a filesystem in WebAssembly

#12

Post by vlovich123 »

phiresky wrote: post #5

I'm a bit disappointed that this only solves the "find index of file in tar" problem, but not at all the "partially read a tar.gz" file problem. So really you're still reading the whole file into memory, so why not just extract the files properly while you are doing that? Takes the same amount of time (O(n)) and less memory. The gzip-random-access problem one is a lot more difficult because the gzip has internal stat…

> Each seek point is accompanied by a chunk (32KB) of uncompressed data which is used to initialise the decompression algorithm, allowing us to start reading from any seek point.

> Apparently the internal state is only 32kB, so if you save this at 1MB offsets, you can reduce the amount of data you need to decompress for one file access to a constant.

You may need to revisit the definition of a constant. A 1/32 additional data is small but it still grows the more data you’re trying to process (we call that O(n) not O(1)). Specifically it’s 3% and so you generally want to target 1% for this kind of stuff (once every 3mib)

And the process still has to read though the enter gzip once to build that index

Re: Mounting tar archives as a filesystem in WebAssembly

#13

Post by phiresky »

vlovich123 wrote: post #12
phiresky wrote: post #5

I'm a bit disappointed that this only solves the "find index of file in tar" problem, but not at all the "partially read a tar.gz" file problem. So really you're still reading the whole file into memory, so why not just extract the files properly while you are doing that? Takes the same amount of time (O(n)) and less memory. The gzip-random-access problem one is a lot more difficult because the gzip has internal stat…

> Each seek point is accompanied by a chunk (32KB) of uncompressed data which is used to initialise the decompression algorithm, allowing us to start reading from any seek point. > Apparently the internal state is only 32kB, so if you save this at 1MB offsets, you can reduce the amount of data you need to decompress for one file access to a constant. You may need to revisit the definition of a constant. A 1/32 additi…

I think you're looking at a different perspective than me. At _build time_ you need to process O(n), yes, and generate O(n) additional data. But I said "The amount of data you need to decompress is a constant". At _read time_, you need to do exactly three steps:

1. Load the file index - this one scales with the number of files unless you do something else smart and get it down to O(log(n)). This gives you an offset into the file. *That same offset/32 is an offset into your gzip index.*

2. take that offset, load 32kB into memory (constant - does not change by number of files, total size, or anything else apart from the actual file you are looking at)

3. decompress a 1MB chunk (or more if necessary)

So yes, it's a constant.

Re: Mounting tar archives as a filesystem in WebAssembly

#14

Post by electroly »

nrclark wrote: post #11
johannes1234321 wrote: post #6

Earlier quoted context omitted.

When looking at established file formats, I'd start with zip for that usecase over tarballs. zip has compression and ability to access any file. A tarfule you have to uncompress first. SquashFS or cramps or such have less tooling, which makes the usage for generating, inspecting, ... more complex.

You only have to decompress it first if it's compressed (commonly using gzip, which is shown with the .gz suffix). Otherwise, you can randomly access any file in a .tar as long as: - the file is seekable/range-addressible - you scan through it and build the file index first, either at runtime or in advance. Uncompressed .tar is a reasonable choice for this application because the tools to read/write tar files are ver…

You've just constructed your own crappy in-memory zip file, here. If you have to build your own custom index, you're no longer using the standard tools. If you find yourself building indices of tar files, and you control the creation, give yourself a break and use a zip file instead. It has the index built in. Compression is not required when packing files into a zip, if you don't want it.

Re: Mounting tar archives as a filesystem in WebAssembly

#15

Post by sixdimensional »

johannes1234321 wrote: post #6
Ecco wrote: post #3

How about using a format that has actually been designed to be a compressed read-only filesystem? Something like a SquashFS or cramfs disk image?

When looking at established file formats, I'd start with zip for that usecase over tarballs. zip has compression and ability to access any file. A tarfule you have to uncompress first. SquashFS or cramps or such have less tooling, which makes the usage for generating, inspecting, ... more complex.

I second the idea to use a zip. In fact it's what a lot of vendors do because it is so ubiquitous, even Microsoft for example - the "open Microsoft Office XML document format" is just a zip file containing a bunch of folders and XML files.

Re: Mounting tar archives as a filesystem in WebAssembly

#16

Post by marginalia_nu »

electroly wrote: post #14
nrclark wrote: post #11

Earlier quoted context omitted.

You only have to decompress it first if it's compressed (commonly using gzip, which is shown with the .gz suffix). Otherwise, you can randomly access any file in a .tar as long as: - the file is seekable/range-addressible - you scan through it and build the file index first, either at runtime or in advance. Uncompressed .tar is a reasonable choice for this application because the tools to read/write tar files are ver…

You've just constructed your own crappy in-memory zip file, here. If you have to build your own custom index, you're no longer using the standard tools. If you find yourself building indices of tar files, and you control the creation, give yourself a break and use a zip file instead. It has the index built in. Compression is not required when packing files into a zip, if you don't want it.

Yeah it's pretty common to use zip files as purely a container format, with no compression enabled. You can even construct them in such a way it's possible to memory map the contents directly out of the zip file, or read them over network via a small number of range requsts.

Re: Mounting tar archives as a filesystem in WebAssembly

#17

Post by johannes1234321 »

nrclark wrote: post #11
johannes1234321 wrote: post #6

Earlier quoted context omitted.

When looking at established file formats, I'd start with zip for that usecase over tarballs. zip has compression and ability to access any file. A tarfule you have to uncompress first. SquashFS or cramps or such have less tooling, which makes the usage for generating, inspecting, ... more complex.

You only have to decompress it first if it's compressed (commonly using gzip, which is shown with the .gz suffix). Otherwise, you can randomly access any file in a .tar as long as: - the file is seekable/range-addressible - you scan through it and build the file index first, either at runtime or in advance. Uncompressed .tar is a reasonable choice for this application because the tools to read/write tar files are ver…

> Uncompressed .tar is a reasonable choice for this application

Yes, uncompressed tar (with transfer compression, which is offered in HTTP) is an option for some amount of data.

Till the point where it isn't. zip has similar benefits as tar(+transfer compression) but a later point where it fails for such a scenario.

Re: Mounting tar archives as a filesystem in WebAssembly

#18

Post by vlovich123 »

phiresky wrote: post #13
vlovich123 wrote: post #12

Earlier quoted context omitted.

> Each seek point is accompanied by a chunk (32KB) of uncompressed data which is used to initialise the decompression algorithm, allowing us to start reading from any seek point. > Apparently the internal state is only 32kB, so if you save this at 1MB offsets, you can reduce the amount of data you need to decompress for one file access to a constant. You may need to revisit the definition of a constant. A 1/32 additi…

I think you're looking at a different perspective than me. At _build time_ you need to process O(n), yes, and generate O(n) additional data. But I said "The amount of data you need to decompress is a constant". At _read time_, you need to do exactly three steps: 1. Load the file index - this one scales with the number of files unless you do something else smart and get it down to O(log(n)). This gives you an offset i…

My bad. Yes from decompression perspective you have O(1) ancillary data to initiate decompression at 1 seek point.

This is how seeking can work in encrypted data btw without the ancillary data - you just increment the IV every N bytes so there’s a guaranteed mapping for how to derive the IV for a block so you’re bounded by how much extra you need to encrypt/decrypt to do a random byte range access of the plaintext.

But none of this is unique to gzip. You can always do this for any compression algorithm provided you can snapshot the state - the state at a seek point is always going to be fairly small.

Re: Mounting tar archives as a filesystem in WebAssembly

#19

Post by hnlmorg »

Ecco wrote: post #3

How about using a format that has actually been designed to be a compressed read-only filesystem? Something like a SquashFS or cramfs disk image?

Because their use case was to support existing tarballs of code.

The problem they’re solving is literally right there in the article you didn’t read.

Re: Mounting tar archives as a filesystem in WebAssembly

#20

Post by chungy »

johannes1234321 wrote: post #17
nrclark wrote: post #11

Earlier quoted context omitted.

You only have to decompress it first if it's compressed (commonly using gzip, which is shown with the .gz suffix). Otherwise, you can randomly access any file in a .tar as long as: - the file is seekable/range-addressible - you scan through it and build the file index first, either at runtime or in advance. Uncompressed .tar is a reasonable choice for this application because the tools to read/write tar files are ver…

> Uncompressed .tar is a reasonable choice for this application Yes, uncompressed tar (with transfer compression, which is offered in HTTP) is an option for some amount of data. Till the point where it isn't. zip has similar benefits as tar(+transfer compression) but a later point where it fails for such a scenario.

Zip allows you to set compression algorithm on a per-file basis, including no compression.
Post reply on HN