Question about btrfs compression

Question about btrfs compression

[Sijie Lan]

As described in
https://archive.kernel.org/oldwiki/btrfs.wiki.kernel.org/index.php/Compression.html.
"The compression processes ranges of a file of maximum size 128 KiB
and compresses each 4 KiB (or page-sized) block separately. Accessing
a byte in the middle of the given 128 KiB range requires to decompress
the whole range. This is not optimal and is subject to optimizations
and further development."

Since Btrfs compresses each 4KiB block of data separately. My question
is that when randomly accessing some of the bytes in the entire
compressed chunk, decompressing some of the bytes in the entire chunk
seems to be much more efficient than decompressing the entire range
(128 KiB), but the current method still decompresses the entire 128KiB
chunk when accessing some of the bytes in the chunk (e.g., 4KiB). So
why is it not optimized for this, is it a basic implementation
difficulty or something else?

Re: Question about btrfs compression

[David Sterba]

On Fri, May 24, 2024 at 02:32:38AM +0800, Sijie Lan wrote:
> As described in
> https://archive.kernel.org/oldwiki/btrfs.wiki.kernel.org/index.php/Compression.html.
> "The compression processes ranges of a file of maximum size 128 KiB
> and compresses each 4 KiB (or page-sized) block separately. Accessing
> a byte in the middle of the given 128 KiB range requires to decompress
> the whole range. This is not optimal and is subject to optimizations
> and further development."
> 
> Since Btrfs compresses each 4KiB block of data separately. My question
> is that when randomly accessing some of the bytes in the entire
> compressed chunk, decompressing some of the bytes in the entire chunk
> seems to be much more efficient than decompressing the entire range
> (128 KiB), but the current method still decompresses the entire 128KiB
> chunk when accessing some of the bytes in the chunk (e.g., 4KiB). So
> why is it not optimized for this, is it a basic implementation
> difficulty or something else?

Technically it's possible. I'm not sure if this would be that noticeable
because page cache readahead reads more memory around what is accessed
so the requested range could be bigger once it ends up in the
decompression.

Assuming we're reading 4k page, we'd need to support seeking into the
compressed stream.  This depends on the used compression algorithm,
we'd need somehow let each decompression to start from there.

For LZO the chunking is done manually, as it needs a contiguous buffer
and referes to previous data directly. We could skip the segments,
though I'm not sure if we store the compressed size (ie. the amount to
skip).

Zstd or zlib keep the state separately and there's no outer container so
we'd need API support for that, returning offset in compressed stream
for a given uncompressed offset in the result. I'm not familiar with the
formats but to make this work the internal segments would have to track
the compressed size and would be able to go over them without
decompression.

The last thing is probably the interface for btrfs compression to fill
just the given range.