Support for compressed inline extents

Support for compressed inline extents

[Forza]

I'd like to see the option to allow compressed extents to be inlined. It could greatly reduce disk usage and speed up small files by avoiding extra seeks.

I tried to understand why we don't allow it but could only find this reference  https://btrfs.wiki.kernel.org/index.php/On-disk_Format#EXTENT_DATA_.286c.29

"the extent is inline, the remaining item bytes are the data bytes (n bytes in case no compression/encryption/other encoding is used)." 

Is the limitation in the disk format or perhaps in the compression heuristics?

Not all use cases would benefit, and we'd have more metadata, which increase the risk of enospc. But i think it could be very valuable nonetheless. For example mail servers, source code/CI, webservers, and others that commonly deal with many small but highly compressible files. 


I did a quick test by copying all files smaller than 8192 bytes from my home server. The filesystem has 90GiB used. 

The result was 357129 files, 207605 inline. 792MiB disk usage, 1.0GiB data size, or 1.1% of fs usage. 

Zstd compressed them, which gave 295419 files inline. Total data size 500MiB. The size of the inlined files is 208MiB. 

Uncompressed the inlined files to see how much of the original data could have been compressed and inlined. 599MiB total data with 501MiB disk usage and 207576 inlined files. 

All in all we would save 501-208=293MiB, which is very good. Ontop of this we'd have savings because we avoid padding up to 4kiB block size due to inlining. Also my test only included files less than 8kiB. It is possible that many files larger than this could be compressed to less than max_inline size. 


Thanks

Re: Support for compressed inline extents

[Zygo Blaxell]

On Sun, Aug 22, 2021 at 01:25:48AM +0200, Forza wrote:
> I'd like to see the option to allow compressed extents to be inlined. It
> could greatly reduce disk usage and speed up small files by avoiding
> extra seeks.
>
> I tried to understand why we don't allow
> it but could only find this reference
> https://btrfs.wiki.kernel.org/index.php/On-disk_Format#EXTENT_DATA_.286c.29
>
> "the extent is inline, the remaining item bytes are the data bytes
> (n bytes in case no compression/encryption/other encoding is used)."
>
> Is the limitation in the disk format or perhaps in the compression
> heuristics?

A far better question is "when did we _stop_ compressing inlined extents",
and the answer is in v5.14-rc1: f2165627319f "btrfs: compression: don't
try to compress if we don't have enough pages".  This check affects
inlined extents, so they are never compressed after 5.14.  Oops.

> Not all use cases would benefit, and we'd have more metadata, which
> increase the risk of enospc. But i think it could be very valuable
> nonetheless. For example mail servers, source code/CI, webservers, and
> others that commonly deal with many small but highly compressible files.
>
>
> I did a quick test by copying all files smaller than 8192 bytes from
> my home server. The filesystem has 90GiB used.

An 8192 byte file cannot currently be inline (on a 4K page size system)
because the read code in btrfs assumes inline extents always fit inside
one page after decoding.

What you're really asking here is "can we have an arbitrary length
of compressed inline extent, as long as the encoded version fits in a
metadata block" and the short answer is "not with this on-disk format,"
because existing readers cannot cope with it.  If we are to consider this,
it requires an incompatible format change.

> The result was 357129 files, 207605 inline. 792MiB disk usage, 1.0GiB
> data size, or 1.1% of fs usage.
>
> Zstd compressed them, which gave 295419 files inline. Total data size
> 500MiB. The size of the inlined files is 208MiB.
>
> Uncompressed the inlined files to see how much of the original data
> could have been compressed and inlined. 599MiB total data with 501MiB
> disk usage and 207576 inlined files.
>
> All in all we would save 501-208=293MiB, which is very good. Ontop of
> this we'd have savings because we avoid padding up to 4kiB block size
> due to inlining. Also my test only included files less than 8kiB. It
> is possible that many files larger than this could be compressed to
> less than max_inline size.
>
>
> Thanks

Re: Support for compressed inline extents

[Forza]

On 2021-08-22 07:45, Zygo Blaxell wrote:
> On Sun, Aug 22, 2021 at 01:25:48AM +0200, Forza wrote:
>> I'd like to see the option to allow compressed extents to be inlined. It
>> could greatly reduce disk usage and speed up small files by avoiding
>> extra seeks.
>>
>> I tried to understand why we don't allow
>> it but could only find this reference
>> https://btrfs.wiki.kernel.org/index.php/On-disk_Format#EXTENT_DATA_.286c.29
>>
>> "the extent is inline, the remaining item bytes are the data bytes
>> (n bytes in case no compression/encryption/other encoding is used)."
>>
>> Is the limitation in the disk format or perhaps in the compression
>> heuristics?
> 
> A far better question is "when did we _stop_ compressing inlined extents",
> and the answer is in v5.14-rc1: f2165627319f "btrfs: compression: don't
> try to compress if we don't have enough pages".  This check affects
> inlined extents, so they are never compressed after 5.14.  Oops.

I don't understand this comment as you say below we do not allow 
compressed (encoded) data inline? Do you mean we only used to compress 
data inline if the original uncompressed data would fit inline too?

> 
>> Not all use cases would benefit, and we'd have more metadata, which
>> increase the risk of enospc. But i think it could be very valuable
>> nonetheless. For example mail servers, source code/CI, webservers, and
>> others that commonly deal with many small but highly compressible files.
>>
>>
>> I did a quick test by copying all files smaller than 8192 bytes from
>> my home server. The filesystem has 90GiB used.
> 
> An 8192 byte file cannot currently be inline (on a 4K page size system)
> because the read code in btrfs assumes inline extents always fit inside
> one page after decoding.
> 
> What you're really asking here is "can we have an arbitrary length
> of compressed inline extent, as long as the encoded version fits in a
> metadata block" and the short answer is "not with this on-disk format,"
> because existing readers cannot cope with it.  If we are to consider this,
> it requires an incompatible format change.

Yes, this is what I meant. As long as the resulting data after 
compression would fit inline, we should allow it to be inlined.

> 
>> The result was 357129 files, 207605 inline. 792MiB disk usage, 1.0GiB
>> data size, or 1.1% of fs usage.
>>
>> Zstd compressed them, which gave 295419 files inline. Total data size
>> 500MiB. The size of the inlined files is 208MiB.
>>
>> Uncompressed the inlined files to see how much of the original data
>> could have been compressed and inlined. 599MiB total data with 501MiB
>> disk usage and 207576 inlined files.
>>
>> All in all we would save 501-208=293MiB, which is very good. Ontop of
>> this we'd have savings because we avoid padding up to 4kiB block size
>> due to inlining. Also my test only included files less than 8kiB. It
>> is possible that many files larger than this could be compressed to
>> less than max_inline size.
>>
>>
>> Thanks

Re: Support for compressed inline extents

[Zygo Blaxell]

On Sun, Aug 22, 2021 at 09:09:10AM +0200, Forza wrote:
> On 2021-08-22 07:45, Zygo Blaxell wrote:
> > On Sun, Aug 22, 2021 at 01:25:48AM +0200, Forza wrote:
> > > I'd like to see the option to allow compressed extents to be inlined. It
> > > could greatly reduce disk usage and speed up small files by avoiding
> > > extra seeks.
> > > 
> > > I tried to understand why we don't allow
> > > it but could only find this reference
> > > https://btrfs.wiki.kernel.org/index.php/On-disk_Format#EXTENT_DATA_.286c.29
> > > 
> > > "the extent is inline, the remaining item bytes are the data bytes
> > > (n bytes in case no compression/encryption/other encoding is used)."
> > > 
> > > Is the limitation in the disk format or perhaps in the compression
> > > heuristics?
> > 
> > A far better question is "when did we _stop_ compressing inlined extents",
> > and the answer is in v5.14-rc1: f2165627319f "btrfs: compression: don't
> > try to compress if we don't have enough pages".  This check affects
> > inlined extents, so they are never compressed after 5.14.  Oops.
> 
> I don't understand this comment as you say below we do not allow compressed
> (encoded) data inline? Do you mean we only used to compress data inline if
> the original uncompressed data would fit inline too?

The old code had two conditions and both must be met:

	1.  encoded data size <= max_inline mount parameter (default
	page_size / 2)

	2.  unencoded data size < page_size (must fit in a single page
	without filling it).

So with compression you can fit up to 4095 bytes in an inline extent on
a page-size-4096 machine; however, the data must compress to 2048 bytes
or less (or whatever the max_inline limit is set to).  If the compressed
data doesn't fit inline, it gets stored uncompressed in a normal data
block, since the compression can't save any space.

Without compression, it's much simpler:  only the extent's length matters,
it's inline or not inline.

The new code adds a third condition which must also be met:

	3.  unencoded data size > page_size

Condition 3 and condition 2 can never be true at the same time, so new
kernel code cannot compress any extent that could possibly be inline.

> > > Not all use cases would benefit, and we'd have more metadata, which
> > > increase the risk of enospc. But i think it could be very valuable
> > > nonetheless. For example mail servers, source code/CI, webservers, and
> > > others that commonly deal with many small but highly compressible files.
> > > 
> > > 
> > > I did a quick test by copying all files smaller than 8192 bytes from
> > > my home server. The filesystem has 90GiB used.
> > 
> > An 8192 byte file cannot currently be inline (on a 4K page size system)
> > because the read code in btrfs assumes inline extents always fit inside
> > one page after decoding.
> > 
> > What you're really asking here is "can we have an arbitrary length
> > of compressed inline extent, as long as the encoded version fits in a
> > metadata block" and the short answer is "not with this on-disk format,"
> > because existing readers cannot cope with it.  If we are to consider this,
> > it requires an incompatible format change.
> 
> Yes, this is what I meant. As long as the resulting data after compression
> would fit inline, we should allow it to be inlined.

There's nothing about the disk format that would prevent this, except that
no implementations exist that could read it correctly.

> > > The result was 357129 files, 207605 inline. 792MiB disk usage, 1.0GiB
> > > data size, or 1.1% of fs usage.
> > > 
> > > Zstd compressed them, which gave 295419 files inline. Total data size
> > > 500MiB. The size of the inlined files is 208MiB.
> > > 
> > > Uncompressed the inlined files to see how much of the original data
> > > could have been compressed and inlined. 599MiB total data with 501MiB
> > > disk usage and 207576 inlined files.
> > > 
> > > All in all we would save 501-208=293MiB, which is very good. Ontop of
> > > this we'd have savings because we avoid padding up to 4kiB block size
> > > due to inlining. Also my test only included files less than 8kiB. It
> > > is possible that many files larger than this could be compressed to
> > > less than max_inline size.
> > > 
> > > 
> > > Thanks

Re: Support for compressed inline extents

[Forza]

On 2021-08-22 10:33, Zygo Blaxell wrote:
> On Sun, Aug 22, 2021 at 09:09:10AM +0200, Forza wrote:
>> On 2021-08-22 07:45, Zygo Blaxell wrote:
>>> On Sun, Aug 22, 2021 at 01:25:48AM +0200, Forza wrote:
>>>> I'd like to see the option to allow compressed extents to be inlined. It
>>>> could greatly reduce disk usage and speed up small files by avoiding
>>>> extra seeks.
>>>>
>>>> I tried to understand why we don't allow
>>>> it but could only find this reference
>>>> https://btrfs.wiki.kernel.org/index.php/On-disk_Format#EXTENT_DATA_.286c.29
>>>>
>>>> "the extent is inline, the remaining item bytes are the data bytes
>>>> (n bytes in case no compression/encryption/other encoding is used)."
>>>>
>>>> Is the limitation in the disk format or perhaps in the compression
>>>> heuristics?
>>>
>>> A far better question is "when did we _stop_ compressing inlined extents",
>>> and the answer is in v5.14-rc1: f2165627319f "btrfs: compression: don't
>>> try to compress if we don't have enough pages".  This check affects
>>> inlined extents, so they are never compressed after 5.14.  Oops.
>>
>> I don't understand this comment as you say below we do not allow compressed
>> (encoded) data inline? Do you mean we only used to compress data inline if
>> the original uncompressed data would fit inline too?
> 
> The old code had two conditions and both must be met:
> 
> 	1.  encoded data size <= max_inline mount parameter (default
> 	page_size / 2)
> 
> 	2.  unencoded data size < page_size (must fit in a single page
> 	without filling it).

This means we have methods to read encoded inlined data? Further below..

> 
> So with compression you can fit up to 4095 bytes in an inline extent on
> a page-size-4096 machine; however, the data must compress to 2048 bytes
> or less (or whatever the max_inline limit is set to).  If the compressed
> data doesn't fit inline, it gets stored uncompressed in a normal data
> block, since the compression can't save any space.
> 
> Without compression, it's much simpler:  only the extent's length matters,
> it's inline or not inline.
> 
> The new code adds a third condition which must also be met:
> 
> 	3.  unencoded data size > page_size
> 
> Condition 3 and condition 2 can never be true at the same time, so new
> kernel code cannot compress any extent that could possibly be inline.

Ouch
> 
>>>> Not all use cases would benefit, and we'd have more metadata, which
>>>> increase the risk of enospc. But i think it could be very valuable
>>>> nonetheless. For example mail servers, source code/CI, webservers, and
>>>> others that commonly deal with many small but highly compressible files.
>>>>
>>>>
>>>> I did a quick test by copying all files smaller than 8192 bytes from
>>>> my home server. The filesystem has 90GiB used.
>>>
>>> An 8192 byte file cannot currently be inline (on a 4K page size system)
>>> because the read code in btrfs assumes inline extents always fit inside
>>> one page after decoding.
>>>
>>> What you're really asking here is "can we have an arbitrary length
>>> of compressed inline extent, as long as the encoded version fits in a
>>> metadata block" and the short answer is "not with this on-disk format,"
>>> because existing readers cannot cope with it.  If we are to consider this,
>>> it requires an incompatible format change.
>>
>> Yes, this is what I meant. As long as the resulting data after compression
>> would fit inline, we should allow it to be inlined.
> 
> There's nothing about the disk format that would prevent this, except that
> no implementations exist that could read it correctly.

Further up you showed that we can read encoded inlined data. What is 
missing for that we can read encoded inlined data that decode to 
 >page_size in size?

> 
>>>> The result was 357129 files, 207605 inline. 792MiB disk usage, 1.0GiB
>>>> data size, or 1.1% of fs usage.
>>>>
>>>> Zstd compressed them, which gave 295419 files inline. Total data size
>>>> 500MiB. The size of the inlined files is 208MiB.
>>>>
>>>> Uncompressed the inlined files to see how much of the original data
>>>> could have been compressed and inlined. 599MiB total data with 501MiB
>>>> disk usage and 207576 inlined files.
>>>>
>>>> All in all we would save 501-208=293MiB, which is very good. Ontop of
>>>> this we'd have savings because we avoid padding up to 4kiB block size
>>>> due to inlining. Also my test only included files less than 8kiB. It
>>>> is possible that many files larger than this could be compressed to
>>>> less than max_inline size.
>>>>
>>>>
>>>> Thanks

Re: Support for compressed inline extents

[Zygo Blaxell]

On Mon, Aug 23, 2021 at 09:34:27PM +0200, Forza wrote:
> Further up you showed that we can read encoded inlined data. What is missing
> for that we can read encoded inlined data that decode to >page_size in size?

In uncompress_inline():

	// decoded length of extent on disk...
	max_size = btrfs_file_extent_ram_bytes(leaf, item);

	...

	// ...can never be more than one page because of this line(*)
	max_size = min_t(unsigned long, PAGE_SIZE, max_size);

There might be further constraints around this code (e.g. the caller
only fills in structures for one page, or doesn't bother to call this
function at all for offsets above PAGE_SIZE).

All the restrictions would need to be removed in the kernel and support
for reading multi-page inline extents added where necessary.  There would
have to be an incompat bit on the filesystem to prevent old kernels from
trying (and failing) to read longer inline extents.  The disk format is
already technically capable of specifying a longer inline extent (up to
min(UINT32_MAX, metadata_page_size)) but that was never the problem.

(*) OK I said unencoded_data_len < PAGE_SIZE in earlier messages because
that's the write-side threshold, but apparently the read-side code uses
a different constraint unencoded_data_len <= PAGE_SIZE, i.e. we can pack
one more byte in there without changing anything else.

Re: Support for compressed inline extents

[David Sterba]

On Mon, Aug 23, 2021 at 04:23:29PM -0400, Zygo Blaxell wrote:
> On Mon, Aug 23, 2021 at 09:34:27PM +0200, Forza wrote:
> > Further up you showed that we can read encoded inlined data. What is missing
> > for that we can read encoded inlined data that decode to >page_size in size?
> 
> In uncompress_inline():
> 
> 	// decoded length of extent on disk...
> 	max_size = btrfs_file_extent_ram_bytes(leaf, item);
> 
> 	...
> 
> 	// ...can never be more than one page because of this line(*)
> 	max_size = min_t(unsigned long, PAGE_SIZE, max_size);
> 
> There might be further constraints around this code (e.g. the caller
> only fills in structures for one page, or doesn't bother to call this
> function at all for offsets above PAGE_SIZE).
> 
> All the restrictions would need to be removed in the kernel and support
> for reading multi-page inline extents added where necessary.  There would
> have to be an incompat bit on the filesystem to prevent old kernels from
> trying (and failing) to read longer inline extents.  The disk format is
> already technically capable of specifying a longer inline extent (up to
> min(UINT32_MAX, metadata_page_size)) but that was never the problem.

Regarding the idea of compressed inline extents, I'm not much in favor
of increasing the limit beyond one page (or sector). The metadata space
is more precious and that's also the motivation behind low default
max_inline. Another thing is mixing data and metadata with potentially
different block group profiles.

The inline files is IMO a nice little optimization and helps when the
size is below certain limit to avoid wasting data blocks and the
indirection.

Re: Support for compressed inline extents

[Forza]

On 2021-08-27 12:08, David Sterba wrote:
> On Mon, Aug 23, 2021 at 04:23:29PM -0400, Zygo Blaxell wrote:
>> On Mon, Aug 23, 2021 at 09:34:27PM +0200, Forza wrote:
>>> Further up you showed that we can read encoded inlined data. What is missing
>>> for that we can read encoded inlined data that decode to >page_size in size?
>>
>> In uncompress_inline():
>>
>> 	// decoded length of extent on disk...
>> 	max_size = btrfs_file_extent_ram_bytes(leaf, item);
>>
>> 	...
>>
>> 	// ...can never be more than one page because of this line(*)
>> 	max_size = min_t(unsigned long, PAGE_SIZE, max_size);
>>
>> There might be further constraints around this code (e.g. the caller
>> only fills in structures for one page, or doesn't bother to call this
>> function at all for offsets above PAGE_SIZE).
>>
>> All the restrictions would need to be removed in the kernel and support
>> for reading multi-page inline extents added where necessary.  There would
>> have to be an incompat bit on the filesystem to prevent old kernels from
>> trying (and failing) to read longer inline extents.  The disk format is
>> already technically capable of specifying a longer inline extent (up to
>> min(UINT32_MAX, metadata_page_size)) but that was never the problem.
> 
> Regarding the idea of compressed inline extents, I'm not much in favor
> of increasing the limit beyond one page (or sector). The metadata space
> is more precious and that's also the motivation behind low default
> max_inline. Another thing is mixing data and metadata with potentially
> different block group profiles.

We already mix profiles today with inlining small extents. It is not a 
problem as most people use a better/higher redundancy for metadata than 
for data.

> The inline files is IMO a nice little optimization and helps when the
> size is below certain limit to avoid wasting data blocks and the
> indirection.
> 

To be fair, I think the benefit is that we inline instead of creating 
4KiB extents for small amounts of data. This benefit would be true even 
if that data was compressed data and the compressed size was <2KiB.

I do understand the earlier points that this would perhaps be a big 
thing to change, also incompatible with earlier kernels. Given that work 
the benefit is rather small.

Perhaps if we are doing incompatible changes in the future, this could 
be considered at that time? One reference is what Qu wrote here about 
taking in more factors to consider for inlining? 
https://lore.kernel.org/linux-btrfs/d0dccd5e-c67f-a18d-8d6e-559504b5ee91@suse.com/

Thanks

Re: Support for compressed inline extents

[Qu Wenruo]

On 2021/8/29 下午7:22, Forza wrote:
>
>
> On 2021-08-27 12:08, David Sterba wrote:
>> On Mon, Aug 23, 2021 at 04:23:29PM -0400, Zygo Blaxell wrote:
>>> On Mon, Aug 23, 2021 at 09:34:27PM +0200, Forza wrote:
>>>> Further up you showed that we can read encoded inlined data. What is
>>>> missing
>>>> for that we can read encoded inlined data that decode to >page_size
>>>> in size?
>>>
>>> In uncompress_inline():
>>>
>>>     // decoded length of extent on disk...
>>>     max_size = btrfs_file_extent_ram_bytes(leaf, item);
>>>
>>>     ...
>>>
>>>     // ...can never be more than one page because of this line(*)
>>>     max_size = min_t(unsigned long, PAGE_SIZE, max_size);
>>>
>>> There might be further constraints around this code (e.g. the caller
>>> only fills in structures for one page, or doesn't bother to call this
>>> function at all for offsets above PAGE_SIZE).
>>>
>>> All the restrictions would need to be removed in the kernel and support
>>> for reading multi-page inline extents added where necessary.  There
>>> would
>>> have to be an incompat bit on the filesystem to prevent old kernels from
>>> trying (and failing) to read longer inline extents.  The disk format is
>>> already technically capable of specifying a longer inline extent (up to
>>> min(UINT32_MAX, metadata_page_size)) but that was never the problem.
>>
>> Regarding the idea of compressed inline extents, I'm not much in favor
>> of increasing the limit beyond one page (or sector). The metadata space
>> is more precious and that's also the motivation behind low default
>> max_inline. Another thing is mixing data and metadata with potentially
>> different block group profiles.
>
> We already mix profiles today with inlining small extents. It is not a
> problem as most people use a better/higher redundancy for metadata than
> for data.
>
>> The inline files is IMO a nice little optimization and helps when the
>> size is below certain limit to avoid wasting data blocks and the
>> indirection.
>>
>
> To be fair, I think the benefit is that we inline instead of creating
> 4KiB extents for small amounts of data. This benefit would be true even
> if that data was compressed data and the compressed size was <2KiB.
>
> I do understand the earlier points that this would perhaps be a big
> thing to change, also incompatible with earlier kernels. Given that work
> the benefit is rather small.
>
> Perhaps if we are doing incompatible changes in the future, this could
> be considered at that time? One reference is what Qu wrote here about
> taking in more factors to consider for inlining?
> https://lore.kernel.org/linux-btrfs/d0dccd5e-c67f-a18d-8d6e-559504b5ee91@suse.com/


There are way more things to consider for inlining extent larger than
one sector.

- Reading the inline extent
   Now we must consider multiple pages other than just simply copying the
   data to the page.
   This also brings extra error paths which must be considered.

- Writing the extra pages of the inline extent
   Unlike current single sector inline, what if you overwrite the 2nd
   page of the inline extent?

   In theory, we should make the whole inline extents into one regular
   extent, then this means we have to read the whole inline extent out,
   re-marking them dirty.

   We don't have the exact facility to do that.
   The most similar one is defrag, but now we need to do that in write
   path too.

   Or you can treat them as regular extents, just cow the 2nd page?
   Then it completely wastes the extra space in metadata.

   Either way, it's way complex than you thought, and all my respect to
   all those guys solving the corner cases with compression and inline.


So my idea towards inline and compression is pretty simple, they are
good optimization, but not critical part.

Thus if they are affecting regular core functions to be more complex
than they should, then no.

And extending inline extent size beyond page size is exactly bringing
extra cost to the developers, with little and uncertain benefit.

Thanks,
Qu


>
>
> Thanks