Re: [gentoo-user] Portage spokes again...

[Rich Freeman]

On Wed, Dec 21, 2016 at 7:46 PM, Daniel Campbell <zlg@g.o> wrote:
>
> How does a file take up less than a single FS block? An inode has to be
> allocated _somewhere_, does it not?
>

So, the details are going to be filesystem-specific, but typically
inodes go into some kind of area of the disk reserved for metadata, so
that many of them can be stored in a single disk block.  They're also
fixed-length so storing them in groups lets you address them as an
array.  Likewise for directory trees, allocation tracking, and so on.

In ext4 inodes are 256 bytes by default.  So, obviously you can fit 16
of those in a single 4k disk block.

60 of those bytes are used to map the inode to the extents on the disk
that contain the file's data.  If the data within the file takes up
less than 60 bytes then ext4 will store the data inside the actual
inode itself since the mapping isn't actually needed in that case.
That saves a whole block.

Other filesystems do things differently.  I don't profess to be a
general expert, but I have read a fair bit on btrfs.  Btrfs allocates
spaces in b+ tree nodes that contain fixed-length records on one side
(which would store things like inodes and other metadata records), and
a heap full of variable-length records on the other.  The latter can
be used to store the content of small files.  I believe btrfs can also
use metadata space to store small regions of files as well (such as if
you have a file that is just a few bytes larger than the next block
boundary, or when you overwrite 1 byte of a large file which in btrfs
does not get done in-place).

The optimization of storing small bits of data without using entire
blocks is a pretty common one.  Another common optimization is dealing
with large blocks of zeros in files.  If you write a gigabyte of zeros
in most filesystems it will certainly not take a gigabyte of space,
even if the filesystem does not otherwise use compression.

And of course you have stuff that consumes nothing but inodes, like
links and device nodes and such.

It isn't surprising that these optimizations are widespread on
unix-like filesystems since small files for configuration/etc are so
common.  Not only does it save a ton of space, but it also saves a
seek when the file is read.

Finally, I'll just comment that if you're interested in brushing up on
data structures, the documentation for any of the modern filesystems
is a great thing to read up on.  Since disk seeks are incredibly
expensive but disks are very large a great deal of thought goes into
how the data gets stored.

--
Rich