5 ms·

IMO, part of the issue is that something which used to be just a low-level optimization (don't store large sequences of zeros) became visible to userspace (SEEK

by cesarb 3y ago

IMO, part of the issue is that something which used to be just a low-level optimization (don't store large sequences of zeros) became visible to userspace (SEEK_HOLE and friends). Quoting from this article: "This is allowed; its always safe to say there’s data where there’s a hole, because reading a hole area will always find “zeroes”, which is valid data." But I recall reading elsewhere a discussion about some userspace program which did depend on holes being present in the filesystem as actual holes (visible to SEEK_HOLE and so on) and not as runs of zeros. Combined with the holes being restricted to specific alignments and sizes, this means that the underlying "sequence of fixed-size blocks" implementation is leaking too much over the abstract "stream of bytes" representation we're more used to. Perhaps it might be time to rethink our filesystem abstractions?

ajross 3y ago
Indeed, sparse files are simply a mistake to have included in Unix in the first place (I think we blame this on early SunOS? Not sure, though almost certain that 3BSD and v7 didn't have them). Yes, they have been used productively for various tricks, but they create a bunch of complexity that every filesystem needs to carry along with it. It's a bad trade.
- cogman10 3y ago
  This a feature I was completely unaware of. Why would you choose to use a sparse file instead of multiple files?
  - vlovich123 3y ago
    The number of file descriptors you can have open by a single program is limited and eats up kernel resources.
    - ajross 3y ago
      Even for a torrent client, the number of active file descriptors is a function of the number of peer connections (e.g. a few dozen). It doesn't scale with the size of the output file.
      - vlovich123 3y ago
        Think databases like RocksDB not torrents.
  - wolf550e 3y ago
    Imagine a torrent client (or http client downloading a file in parallel using HTTP range requests). It creates an empty file and then it has downloaded a 1MB of data to write at offset 100GB and wants to write it to disk. It does not want to pay the price of waiting for 100GB of zeroes to be written. The other blocks will all be downloaded and written eventually, all out of order. If the filesystem had an atomic operation to transform a bunch of (block aligned) files into a single file (like AWS S3 Multipart Upload), then sparse files would not be needed for this case.
    - myself248 3y ago
      Out of curiosity, do you know off-hand how torrent clients do it on filesystems that don't support sparse files? There must be either a preallocate-the-whole-thing step, or a gather-the-pieces-together-and-write-out-the-large-file step. The latter would seem to briefly double the disk space needed at the end of the download, so I suspect they do the former.
      - ajross 3y ago
        Chunk it up and resassemble, one assumes. Things aren't nearly as clear in the modern world of gigabit pipes into suburban households[1], but when these things were written the filesystem was 100x faster than the link to those peer connections from which the data was fetched. A final copy was only a small overhead. [1] Which is why all the stuff we used to torrent is in the cloud now.
      - cesarb 3y ago
        AFAIK, they preallocate; and even on filesystems which support sparse files, most bittorrent clients have an option to always preallocate (to both reserve space and reduce fragmentation).
    - loeg 3y ago
      Fallocate is a much better interface for this than sparse files. The torrent client does not care how the underlying filesystem provides the ability to randomly write a large file. And fallocate is a much clearer signal to the filesystem than a sparse file.
  - axus 3y ago
    A memory map of a gigabyte/whatever, that uses a bunch of large addresses but typically only uses 1% of the available space. Saves someone the trouble of managing the map or compressing it. It does feel like a weird decision from long time ago that we're stuck with. I thought it was some quirky Linux feature but it's been around https://en.wikipedia.org/wiki/Sparse_file https://en.wikipedia.org/wiki/Sparse_file
  - andoma 3y ago
    Somewhat related is that a few filesystem types on Linux allows you to remove / insert bytes "within" a file. But it needs alignment to filesystem block size. This uses the same syscall, fallocate(2), which can be used to punch new sparse holes in a file where it previously had data. See https://man7.org/linux/man-pages/man2/fallocate.2.html https://man7.org/linux/man-pages/man2/fallocate.2.html
- retrac 3y ago
  Sparse files make more sense if you see the file system and paging as unified. If you have allocated an array of 1 billion items, accessing the last item doesn't make the OS zero out everything from 0th to the billionth item, allocating millions of pages along the way. Virtual emory is sparse; so just one page of virtual memory is allocated. Mmap'd sparse files behave the same way.
  - ajross 3y ago
    No, I get it. I'm saying that's a bad design. The data structure for a VM system is a big tree of discontiguous mappings, which matches the API used for accessing it. If you make a random access to memory at an arbitrary spot, you expect to get a VM trap. If you want to map memory, you're expected to know the layout and manage the "holes" yourself (or else to let the OS manage your memory space for you). The data structure for a file is an ordered stream of bytes, which matches the API for accessing it. You can jump around by seeking, but there are no holes. Bytes start at 0 and go on from there. Want to seek() to an arbitrary value? Totally legal, presumptively valid. Making the filesystem, implemented from first principles to handle the second style of interaction, actually be implemented in terms of the first under the hood, is a source of needless complexity and bugs. And it was here, too.
    - avianlyric 3y ago
      > Making the filesystem, implemented from first principles to handle the second style of interaction, actually be implemented in terms of the first under the hood, is a source of needless complexity and bugs. And it was here, too. Aren’t all modern file systems implemented as a tree of discontinuous regions? That’s the whole reason block allocators exist, why file fragmentation is a thing (and defragmentation processes). How could you reasonably expect to implement a filesystem that under hood only operates with continuous blocks disk space? It would require the filesystem to have prior knowledge of the size of all the files that going to be written, so it can pre-allocate the continuous sections. Or the second writing a file resulted in that file exceeding the length of the continuous empty section of disk, future writes would have to pause until the filesystem had finished copying the entire file to a new region with more space. With ZFS its heavy dependence on tree structures of discontinuous address regions is what enables all of its desirable feature. To say the complexity is needless is to implicitly say ZFS itself is pointless.
codys 3y ago
> But I recall reading elsewhere a discussion about some userspace program which did depend on holes being present in the filesystem as actual holes (visible to SEEK_HOLE and so on) and not as runs of zeros. "treatment of on-disk segments as "what was written by programs" can cause areas of 0 to not be written by bmaptool copy": https://github.com/intel/bmap-tools/issues/75 https://github.com/intel/bmap-tools/issues/75 IMO, the issue here isn't filesystem or zfs behavior, it's that bmap-tool wants an extra "don't care bit" per block, which filesystems (traditionally) don't track, and programs interacting with filesystem don't expect to exist. Some of the comments I've made in this issue describe options to make things better. (FWIW: the original hn link discusses a different issue around seek hole/data, and the bmap-tool issue is backwards from the issue the parent posits: bmap-tool relies on explicit runs of zeros written not being holes, and particular behavior from programs writing data)

by cesarb 3y ago

ajross 3y ago

Indeed, sparse files are simply a mistake to have included in Unix in the first place (I think we blame this on early SunOS? Not sure, though almost certain that 3BSD and v7 didn't have them). Yes, they have been used productively for various tricks, but they create a bunch of complexity that every filesystem needs to carry along with it. It's a bad trade.

cogman10 3y ago
This a feature I was completely unaware of. Why would you choose to use a sparse file instead of multiple files?
- vlovich123 3y ago
  The number of file descriptors you can have open by a single program is limited and eats up kernel resources.
  - ajross 3y ago
    Even for a torrent client, the number of active file descriptors is a function of the number of peer connections (e.g. a few dozen). It doesn't scale with the size of the output file.
    - vlovich123 3y ago
      Think databases like RocksDB not torrents.
- wolf550e 3y ago
  Imagine a torrent client (or http client downloading a file in parallel using HTTP range requests). It creates an empty file and then it has downloaded a 1MB of data to write at offset 100GB and wants to write it to disk. It does not want to pay the price of waiting for 100GB of zeroes to be written. The other blocks will all be downloaded and written eventually, all out of order. If the filesystem had an atomic operation to transform a bunch of (block aligned) files into a single file (like AWS S3 Multipart Upload), then sparse files would not be needed for this case.
  - myself248 3y ago
    Out of curiosity, do you know off-hand how torrent clients do it on filesystems that don't support sparse files? There must be either a preallocate-the-whole-thing step, or a gather-the-pieces-together-and-write-out-the-large-file step. The latter would seem to briefly double the disk space needed at the end of the download, so I suspect they do the former.
    - ajross 3y ago
      Chunk it up and resassemble, one assumes. Things aren't nearly as clear in the modern world of gigabit pipes into suburban households[1], but when these things were written the filesystem was 100x faster than the link to those peer connections from which the data was fetched. A final copy was only a small overhead. [1] Which is why all the stuff we used to torrent is in the cloud now.
    - cesarb 3y ago
      AFAIK, they preallocate; and even on filesystems which support sparse files, most bittorrent clients have an option to always preallocate (to both reserve space and reduce fragmentation).
  - loeg 3y ago
    Fallocate is a much better interface for this than sparse files. The torrent client does not care how the underlying filesystem provides the ability to randomly write a large file. And fallocate is a much clearer signal to the filesystem than a sparse file.
- axus 3y ago
  A memory map of a gigabyte/whatever, that uses a bunch of large addresses but typically only uses 1% of the available space. Saves someone the trouble of managing the map or compressing it. It does feel like a weird decision from long time ago that we're stuck with. I thought it was some quirky Linux feature but it's been around https://en.wikipedia.org/wiki/Sparse_file https://en.wikipedia.org/wiki/Sparse_file
- andoma 3y ago
  Somewhat related is that a few filesystem types on Linux allows you to remove / insert bytes "within" a file. But it needs alignment to filesystem block size. This uses the same syscall, fallocate(2), which can be used to punch new sparse holes in a file where it previously had data. See https://man7.org/linux/man-pages/man2/fallocate.2.html https://man7.org/linux/man-pages/man2/fallocate.2.html
retrac 3y ago
Sparse files make more sense if you see the file system and paging as unified. If you have allocated an array of 1 billion items, accessing the last item doesn't make the OS zero out everything from 0th to the billionth item, allocating millions of pages along the way. Virtual emory is sparse; so just one page of virtual memory is allocated. Mmap'd sparse files behave the same way.
- ajross 3y ago
  No, I get it. I'm saying that's a bad design. The data structure for a VM system is a big tree of discontiguous mappings, which matches the API used for accessing it. If you make a random access to memory at an arbitrary spot, you expect to get a VM trap. If you want to map memory, you're expected to know the layout and manage the "holes" yourself (or else to let the OS manage your memory space for you). The data structure for a file is an ordered stream of bytes, which matches the API for accessing it. You can jump around by seeking, but there are no holes. Bytes start at 0 and go on from there. Want to seek() to an arbitrary value? Totally legal, presumptively valid. Making the filesystem, implemented from first principles to handle the second style of interaction, actually be implemented in terms of the first under the hood, is a source of needless complexity and bugs. And it was here, too.
  - avianlyric 3y ago
    > Making the filesystem, implemented from first principles to handle the second style of interaction, actually be implemented in terms of the first under the hood, is a source of needless complexity and bugs. And it was here, too. Aren’t all modern file systems implemented as a tree of discontinuous regions? That’s the whole reason block allocators exist, why file fragmentation is a thing (and defragmentation processes). How could you reasonably expect to implement a filesystem that under hood only operates with continuous blocks disk space? It would require the filesystem to have prior knowledge of the size of all the files that going to be written, so it can pre-allocate the continuous sections. Or the second writing a file resulted in that file exceeding the length of the continuous empty section of disk, future writes would have to pause until the filesystem had finished copying the entire file to a new region with more space. With ZFS its heavy dependence on tree structures of discontinuous address regions is what enables all of its desirable feature. To say the complexity is needless is to implicitly say ZFS itself is pointless.

codys 3y ago

> But I recall reading elsewhere a discussion about some userspace program which did depend on holes being present in the filesystem as actual holes (visible to SEEK_HOLE and so on) and not as runs of zeros. "treatment of on-disk segments as "what was written by programs" can cause areas of 0 to not be written by bmaptool copy": https://github.com/intel/bmap-tools/issues/75 https://github.com/intel/bmap-tools/issues/75 IMO, the issue here isn't filesystem or zfs behavior, it's that bmap-tool wants an extra "don't care bit" per block, which filesystems (traditionally) don't track, and programs interacting with filesystem don't expect to exist. Some of the comments I've made in this issue describe options to make things better. (FWIW: the original hn link discusses a different issue around seek hole/data, and the bmap-tool issue is backwards from the issue the parent posits: bmap-tool relies on explicit runs of zeros written not being holes, and particular behavior from programs writing data)