Re: Unbound(?) internal fragmentation in Btrfs

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



Aloha Mat:
On Thu, Jun 3, 2010 at 4:58 PM, Edward Shishkin<edward@xxxxxxxxxx>  wrote:
Hello everyone.

I was asked to review/evaluate Btrfs for using in enterprise
systems and the below are my first impressions (linux-2.6.33).

The first test I have made was filling an empty 659M (/dev/sdb2)
btrfs partition (mounted to /mnt) with 2K files:

# for i in $(seq 1000000); \
do dd if=/dev/zero of=/mnt/file_$i bs=2048 count=1; done
(terminated after getting "No space left on device" reports).

# ls /mnt | wc -l
59480

So, I got the "dirty" utilization 59480*2048 / (659*1024*1024) = 0.17,
and the first obvious question is "hey, where are other 83% of my
disk space???" I looked at the btrfs storage tree (fs_tree) and was
shocked with the situation on the leaf level. The Appendix B shows
5 adjacent btrfs leafs, which have the same parent.

For example, look at the leaf 29425664: "items 1 free space 3892"
(of 4096!!). Note, that this "free" space (3892) is _dead_: any
attempts to write to the file system will result in "No space left
on device".

Internal fragmentation (see Appendix A) of those 5 leafs is
(1572+3892+1901+3666+1675)/4096*5 = 0.62. This is even worse then
ext4 and xfs: The last ones in this example will show fragmentation
near zero with blocksize<= 2K. Even with 4K blocksize they will
show better utilization 0.50 (against 0.38 in btrfs)!

I have a small question for btrfs developers: Why do you folks put
"inline extents", xattr, etc items of variable size to the B-tree
in spite of the fact that B-tree is a data structure NOT for variable
sized records? This disadvantage of B-trees was widely discussed.
For example, maestro D. Knuth warned about this issue long time
ago (see Appendix C).

It is a well known fact that internal fragmentation of classic Bayer's
B-trees is restricted by the value 0.50 (see Appendix C). However it
takes place only if your tree contains records of the _same_ length
(for example, extent pointers). Once you put to your B-tree records
of variable length (restricted only by leaf size, like btrfs "inline
extents"), your tree LOSES this boundary. Moreover, even worse:
it is clear, that in this case utilization of B-tree scales as zero(!).
That said, for every small E and for every amount of data N we
can construct a consistent B-tree, which contains data N and has
utilization worse then E. I.e. from the standpoint of utilization
such trees can be completely degenerated.

That said, the very important property of B-trees, which guarantees
non-zero utilization, has been lost, and I don't see in Btrfs code any
substitution for this property. In other words, where is a formal
guarantee that all disk space of our users won't be eaten by internal
fragmentation? I consider such guarantee as a *necessary* condition
for putting a file system to production.

Any technical comments are welcome.

Thanks,
Edward.


Appendix A.
-----------
Glossary

1. Utilization of data and(or) metadata storage.

The fraction A/B, where
A is total size in bytes of stored data and(or) metadata.
B = N * S, where
N is number of blocks occupied by stored data and(or) metadata.
S is block size in bytes.

2. Internal fragmentation of data and(or) metadata storage.

difference (1 - U), where U is utilization.


Appendix B.
-----------
a "period" in the dump of the fs_tree (btrfs-debug-tree /dev/sdb2)

...

leaf 29982720 items 4 free space 1572 generation 8 owner 5
fs uuid 50268d9d-2a53-4f4d-b3a3-4fbff74dd956
chunk uuid 963ba49a-bb2b-48a3-9b35-520d857aade6
       item 0 key (319 XATTR_ITEM 3817753667) itemoff 3917 itemsize 78
               location key (0 UNKNOWN 0) type 8
               namelen 16 datalen 32 name: security.selinux
       item 1 key (319 EXTENT_DATA 0) itemoff 1848 itemsize 2069
               inline extent data size 2048 ram 2048 compress 0
       item 2 key (320 INODE_ITEM 0) itemoff 1688 itemsize 160
               inode generation 8 size 2048 block group 29360128 mode 100644
links 1
       item 3 key (320 INODE_REF 256) itemoff 1672 itemsize 16
               inode ref index 65 namelen 6 name: file64
leaf 29425664 items 1 free space 3892 generation 8 owner 5
fs uuid 50268d9d-2a53-4f4d-b3a3-4fbff74dd956
chunk uuid 963ba49a-bb2b-48a3-9b35-520d857aade6
       item 0 key (320 XATTR_ITEM 3817753667) itemoff 3917 itemsize 78
               location key (0 UNKNOWN 0) type 8
               namelen 16 datalen 32 name: security.selinux
leaf 29990912 items 1 free space 1901 generation 8 owner 5
fs uuid 50268d9d-2a53-4f4d-b3a3-4fbff74dd956
chunk uuid 963ba49a-bb2b-48a3-9b35-520d857aade6
       item 0 key (320 EXTENT_DATA 0) itemoff 1926 itemsize 2069
               inline extent data size 2048 ram 2048 compress 0
leaf 29986816 items 3 free space 3666 generation 8 owner 5
fs uuid 50268d9d-2a53-4f4d-b3a3-4fbff74dd956
chunk uuid 963ba49a-bb2b-48a3-9b35-520d857aade6
       item 0 key (321 INODE_ITEM 0) itemoff 3835 itemsize 160
               inode generation 8 size 2048 block group 29360128 mode 100644
links 1
       item 1 key (321 INODE_REF 256) itemoff 3819 itemsize 16
               inode ref index 66 namelen 6 name: file65
       item 2 key (321 XATTR_ITEM 3817753667) itemoff 3741 itemsize 78
               location key (0 UNKNOWN 0) type 8
               namelen 16 datalen 32 name: security.selinux
leaf 29995008 items 3 free space 1675 generation 8 owner 5
fs uuid 50268d9d-2a53-4f4d-b3a3-4fbff74dd956
chunk uuid 963ba49a-bb2b-48a3-9b35-520d857aade6
       item 0 key (321 EXTENT_DATA 0) itemoff 1926 itemsize 2069
               inline extent data size 2048 ram 2048 compress 0
       item 1 key (322 INODE_ITEM 0) itemoff 1766 itemsize 160
               inode generation 8 size 2048 block group 29360128 mode 100644
links 1
       item 2 key (322 INODE_REF 256) itemoff 1750 itemsize 16
               inode ref index 67 namelen 6 name: file66
...

Appendix C.
-----------

D.E. Knuth, The Art of Computer Programming, vol. 3 (Sorting and Searching),
Addison-Wesley, Reading, MA, 1973.

--
Edward O. Shishkin
Principal Software Engineer
Red Hat Czech

--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Hi to all,

First of let me say: Btrfs really has matured a lot in the last months
and this is thanks to you guys (the developers !)

More and more people are making it their dedicated filesystem (MeeGo)
or an option (Ubuntu, Fedora)

So thank you very very much for your on-going efforts on making this
more and more a viable (and usable !) alternative/competition to zfs
:)

The problems Edward mentioned sound like some very important points
(issues ?) to investigate

I find it somewhat surprising that none of you guys commented on his mail
Me too.
I'm in no way a developer (in fact a power-user) but would
nevertheless be interested in your opinions on this matter -
especially Chris'

Thanks !

Mat

With all the best
Christian Stroetmann

--
To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html


[Index of Archives]     [Linux Ext4 Filesystem]     [Union Filesystem]     [Filesystem Testing]     [Ceph Users]     [Ecryptfs]     [AutoFS]     [Kernel Newbies]     [Share Photos]     [Security]     [Netfilter]     [Bugtraq]     [Yosemite News]     [MIPS Linux]     [ARM Linux]     [Linux Security]     [Linux Cachefs]     [Reiser Filesystem]     [Linux RAID]     [Samba]     [Device Mapper]     [CEPH Development]
  Powered by Linux