It lets you mount .tar files as a read only filesystem.
It’s cool because you basically get random access to the tarball without paying any decompression costs. (It builds an index saying exactly where so-and-so is for every file.)
crabique 21 hours ago [-]
Very cool, I wish there were something similar to this for filesystem images though.
Just recently I needed to somehow generate a .tar.gz from a .raw ext4 image and, surprisingly, there's still no better option than actually mounting it and then creating an archive.
I managed to "isolate" it a bit with guestfish's tar-out, but still it's pretty slow as it needs to seek around the image (in my case over NBD) to get the actual files.
tredre3 19 hours ago [-]
There are surprisingly few tools to work on file system images in the Linux world, they expect loopback mounting to always be available.
There are a few libraries to read ext4 but every time I've tried to use one it missed one feature that my specific image was using (mke2fs changes its defaults every couple years to rely on newer ext4 features).
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?
johannes1234321 23 hours ago [-]
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.
nrclark 23 hours ago [-]
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.
electroly 22 hours ago [-]
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.
marginalia_nu 22 hours ago [-]
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.
johannes1234321 22 hours ago [-]
> 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.
chungy 21 hours ago [-]
Zip allows you to set compression algorithm on a per-file basis, including no compression.
QuantumNomad_ 21 hours ago [-]
You can achieve the same with tar if you individually compress the files before adding them to the tar ball instead of compressing the tar ball itself.
I don’t see how that plus a small index of offsets would be notably more or less work to do from using a zip file.
chungy 20 hours ago [-]
Zip has a central directory you could just query, instead of having to construct one in-memory by scanning the entire archive. That's significantly less work.
QuantumNomad_ 18 hours ago [-]
I mean if they include a pre-made index with it. For example an uncompressed index at byte offset 0 in the tar ball that lists what is inside and their offsets. It would still be comparable amount of work to create software to do that with tar as to use a zip file, if fine grained compression levels etc is being used.
johannes1234321 15 hours ago [-]
But then you are not using tar, you are doing your own file format atop of tar.
QuantumNomad_ 12 hours ago [-]
I suppose you are right about that. But it would still be a valid tar file that can be viewed and extracted with normal tools. Kind of similar to how a .docx file can be extracted as zip but still has additional structure to its contents.
kevin_thibedeau 20 hours ago [-]
Romfs is more capable, simple to support, and doesn't have the overhead of tar's large headers and typical large blocking factors.
blipvert 23 hours ago [-]
Zip is a piece of cake.
I had need to embed noVNC into an app recently in Golang. Serving files via net/http from the zip file is practically a one-liner (then just a Gorilla websocket to take the place of websockify).
sixdimensional 22 hours ago [-]
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.
stingraycharles 1 days ago [-]
Sometimes (read: very often) you can’t choose the format. Obviously if squashfs is available that is a better solution.
hnlmorg 21 hours ago [-]
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.
Rather Dumbly it is loading the files from a tar archive that is encoded into a PNG because tar files are one of the forbidden file formats.
phiresky 24 hours ago [-]
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.
All depends on the use case of course. Seems like the author here has a pretty specific one - though I still don't see what the advantage of this is vs extracting in JS and adding all files individually to memfs. "Without any copying" doesn't really make sense because the only difference is copying ONE 1MB tar blob into a Uint8Array vs 1000 1kB file blobs
One very valid constraint the author makes is not being able to touch the source file. If you can do that, there's of course a thousand better solutions to all this - like using zip, which compresses each file individually and always has a central index at the end.
Exactly. And often this state is either highly compressible or non-compressible but only sparsely used. The latter can then be made compressible by replacing the unused bytes with zeros.
Ratarmount uses indexed_gzip, and when parallelization makes sense, it also uses rapidgzip. Rapidgzip implements the sparsity analysis to increase compressibility and then simply uses the gztool index format, i.e., compresses each 32 KiB using gzip itself, with unused bytes replaced with zeros where possible.
indexed_gzip, gztool, and rapidgzip all support seeking in gzip streams, but all have some trade-offs, e.g., rapidgzip is parallelized but will have much higher memory usage because of that than indexed_gzip or gztool. It might be possible to compile either of these to WebAssembly if there is demand.
nrclark 6 hours ago [-]
Tar doesn't need to imply gzip (or bzip2, or zstd, etc). Tar's default operation produces uncompressed archives.
vlovich123 23 hours ago [-]
> 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
phiresky 22 hours ago [-]
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.
vlovich123 22 hours ago [-]
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.
phiresky 20 hours ago [-]
I actually first thought this wasn't possible at all because I'm used to zstd which by default uses a 128MB window and I usually set it to the max (2GB window). 32kB is _really_ tiny in comparison. On the other hand though, zstd also compresses in parallel by default and has tools built in to handle these things, so seekable zstd archives are fairly common.
a_t48 18 hours ago [-]
If anyone knows a similar solution for zstd, I'm very interested. I'm doing streaming uncompression to disk and I'd like to be able to do resumable downloads without _also_ storing the compressed file.
Note, however, that this can only seek to frames, and zstd still only creates files containing a single frame by default. pzstd did create multi-frame files, but it is not being developed anymore. Other alternatives for creating seekable zstd files are: zeekstd, t2sz, and zstd-seekable-format-go.
a_t48 15 hours ago [-]
Thanks, this is helpful. I might just end up using content defined chunking in addition/instead, but it's good to know that there is a path forward if I stick with the current architecture.
Dwedit 19 hours ago [-]
TAR archives are good in a few ways, but random access to files is not one of them. You need to iterate over every file before you can create a mapping between filename and its TAR file address.
(Meanwhile, sending TAR over Netcat is a valid way to clone a filesystem to another computer, including maintaining the hardlinks and symlinks)
jghn 18 hours ago [-]
Isn't "archive" embedded in "tar" already? In other words, is this like saying one went to the "ATM machine"?
Clamchop 18 hours ago [-]
Redundancy in natural language isn't a big deal, and it isn't entirely useless, either.
jghn 17 hours ago [-]
Ok, insofar as saying "tape archive archive" out loud doesn't sound odd to you, keep doing it I suppose.
haunter 23 hours ago [-]
Now I want to try how does that work with BTFS which in a similar vein mounts a torrent file or magnet link as a read only directory https://github.com/johang/btfs
It lets you mount .tar files as a read only filesystem.
It’s cool because you basically get random access to the tarball without paying any decompression costs. (It builds an index saying exactly where so-and-so is for every file.)
Just recently I needed to somehow generate a .tar.gz from a .raw ext4 image and, surprisingly, there's still no better option than actually mounting it and then creating an archive.
I managed to "isolate" it a bit with guestfish's tar-out, but still it's pretty slow as it needs to seek around the image (in my case over NBD) to get the actual files.
There are a few libraries to read ext4 but every time I've tried to use one it missed one feature that my specific image was using (mke2fs changes its defaults every couple years to rely on newer ext4 features).
7-zip can also read ext4 to some degree and, I'm not sure but, they seem to have written a naive parser of their own to do it: https://github.com/mcmilk/7-Zip/blob/master/CPP/7zip/Archive...
SquashFS or cramps or such have less tooling, which makes the usage for generating, inspecting, ... more complex.
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.
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.
I don’t see how that plus a small index of offsets would be notably more or less work to do from using a zip file.
I had need to embed noVNC into an app recently in Golang. Serving files via net/http from the zip file is practically a one-liner (then just a Gorilla websocket to take the place of websockify).
The problem they’re solving is literally right there in the article you didn’t read.
It uses IndexedDB for the filesystem.
Rather Dumbly it is loading the files from a tar archive that is encoded into a PNG because tar files are one of the forbidden file formats.
The gzip-random-access problem one is a lot more difficult because the gzip has internal state. But in any case, solutions exist! 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. https://github.com/mxmlnkn/ratarmount does this, apparently using https://github.com/pauldmccarthy/indexed_gzip internally. zlib even has an example of this method in its own source tree: https://github.com/gcc-mirror/gcc/blob/master/zlib/examples/...
All depends on the use case of course. Seems like the author here has a pretty specific one - though I still don't see what the advantage of this is vs extracting in JS and adding all files individually to memfs. "Without any copying" doesn't really make sense because the only difference is copying ONE 1MB tar blob into a Uint8Array vs 1000 1kB file blobs
One very valid constraint the author makes is not being able to touch the source file. If you can do that, there's of course a thousand better solutions to all this - like using zip, which compresses each file individually and always has a central index at the end.
Exactly. And often this state is either highly compressible or non-compressible but only sparsely used. The latter can then be made compressible by replacing the unused bytes with zeros.
Ratarmount uses indexed_gzip, and when parallelization makes sense, it also uses rapidgzip. Rapidgzip implements the sparsity analysis to increase compressibility and then simply uses the gztool index format, i.e., compresses each 32 KiB using gzip itself, with unused bytes replaced with zeros where possible.
indexed_gzip, gztool, and rapidgzip all support seeking in gzip streams, but all have some trade-offs, e.g., rapidgzip is parallelized but will have much higher memory usage because of that than indexed_gzip or gztool. It might be possible to compile either of these to WebAssembly if there is demand.
> 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
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.
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.
https://github.com/martinellimarco/libzstd-seek
Note, however, that this can only seek to frames, and zstd still only creates files containing a single frame by default. pzstd did create multi-frame files, but it is not being developed anymore. Other alternatives for creating seekable zstd files are: zeekstd, t2sz, and zstd-seekable-format-go.
(Meanwhile, sending TAR over Netcat is a valid way to clone a filesystem to another computer, including maintaining the hardlinks and symlinks)