4 ms·

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'r

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 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 https://github.com/mxmlnkn/ratarmount does this, apparently using https://github.com/pauldmccarthy/indexed_gzip 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/zran.c 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.

ImJasonH 5mo ago
The first time I'd heard of this was via https://github.com/jonjohnsonjr/dagdotdev/blob/main/internal/explore/README.md#blobs https://github.com/jonjohnsonjr/dagdotdev/blob/main/internal... which powers https://oci.dag.dev https://oci.dag.dev to let you browse OCI images (e.g., https://oci.dag.dev/fs/ubuntu@sha256:b40150c1c2717d324cdb17278c8efdfa4dfcd2ffe083e976f0bcedf31115f081/?mt=application%2Fvnd.oci.image.layer.v1.tar%2Bgzip&size=29732978 https://oci.dag.dev/fs/ubuntu@sha256:b40150c1c2717d324cdb172...)
- a_t48 5mo ago
  This is very cool. Worth a submission by itself.
vlovich123 5mo 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 5mo 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 5mo 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.
    - 5mo ago
mxmlnkn 5mo ago
> Apparently the internal state is only 32kB 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.
a_t48 5mo 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.
- mxmlnkn 5mo ago
  https://github.com/martinellimarco/indexed_zstd https://github.com/martinellimarco/indexed_zstd https://github.com/martinellimarco/libzstd-seek 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.
  - a_t48 5mo 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.
nrclark 5mo ago
Tar doesn't need to imply gzip (or bzip2, or zstd, etc). Tar's default operation produces uncompressed archives.

ImJasonH 5mo ago

The first time I'd heard of this was via https://github.com/jonjohnsonjr/dagdotdev/blob/main/internal/explore/README.md#blobs https://github.com/jonjohnsonjr/dagdotdev/blob/main/internal... which powers https://oci.dag.dev https://oci.dag.dev to let you browse OCI images (e.g., https://oci.dag.dev/fs/ubuntu@sha256:b40150c1c2717d324cdb17278c8efdfa4dfcd2ffe083e976f0bcedf31115f081/?mt=application%2Fvnd.oci.image.layer.v1.tar%2Bgzip&size=29732978 https://oci.dag.dev/fs/ubuntu@sha256:b40150c1c2717d324cdb172...)

a_t48 5mo ago
This is very cool. Worth a submission by itself.

vlovich123 5mo 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 5mo 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 5mo 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.
  - 5mo ago

mxmlnkn 5mo ago

> Apparently the internal state is only 32kB 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.

a_t48 5mo 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.

mxmlnkn 5mo ago
https://github.com/martinellimarco/indexed_zstd https://github.com/martinellimarco/indexed_zstd https://github.com/martinellimarco/libzstd-seek 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.
- a_t48 5mo 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.

nrclark 5mo ago

Tar doesn't need to imply gzip (or bzip2, or zstd, etc). Tar's default operation produces uncompressed archives.