4 ms·

We ended up going with a very trivial system based on tar files and bitfield allocators and delegated the more filesystem-y like functionality to a higher level

We ended up going with a very trivial system based on tar files and bitfield allocators and delegated the more filesystem-y like functionality to a higher level of the stack.

yjftsjthsd-h 3y ago
I happen to be in the middle of writing a simple tar implementation, and had in fact just started playing with the idea of just using it as an on-disk filesystem format. The caveats I can see are that 1. it's approximately append-only[0], and 2. you have to replay the whole thing in order to make sure you have the latest version of a file (I'm leaning towards doing so on mount because then I can also build an in-memory filename-to-block-address cache). Have you hit any issues, or is this as surprisingly reasonable as it sounds? [0] I mean, if the new version of a file fits in the same number of 512-byte blocks as the old version you could update in place, but that's an unreliable condition at best and also guarantees data corruption if you lose power halfway; really going append-only makes the implementation simple and also makes it easy to be really resilient.
- aappleby 3y ago
  I'm not on the team anymore so I don't know if they kept the tar stuff around, but it was straightforward to scan the flash for valid tar header blocks to build the allocation bitmap and then flag header blocks as invalid when files were deleted. The total number of files we needed to keep in the flash was small, so simple brute-force stuff worked fine.
- e63f67dd-065b 3y ago
  Not so sure about the tar part, but the append-only nature is actually really well-known: look up log-structured filesystems, where all operations append to the log and GC comes to clean up stale data later. I’m in the middle of writing a log-structured disk, and it’s really nice to work with. You get many things like clones, snapshots, etc for free. The replay problem is usually solved with periodic checkpoints of your map, and a checkpoint on shutdown. This way you only ever replay on failure, at which point performance doesn’t matter as much.
  - yjftsjthsd-h 3y ago
    Yeah, knowing there were filesystems designed like that on purpose made me feel better about it:) And once you get over the initial weirdness, the ability to get any version of any file is pretty nice. Though my favorite angle is that if you can live with just burning space[0], it makes the thing so easy to implement:) [0] To be fair, a huge caveat.
- mschuster91 3y ago
  > The caveats I can see are that 1. it's approximately append-only[0], and 2. you have to replay the whole thing in order to make sure you have the latest version of a file Hmm. I'd go and build a separate metadata/index file that you keep updated on each write(=tar-append) operation. Grow the tar from the beginning of the underlying block device, and the metadata from the rear, and have a pointer in the filesystem header that points to the current metadata address. That way, everything is atomic, you avoid the RAM penalty from having to maintain the metadata mapping, and the only operation that can result in damage in a power-loss event is when the write of the filesystem header messes up - but that can easily be reconstructed by walking both the tar stream and the metadata stream from the beginning to the last element that has a valid header.
- reycharles 3y ago
  I helped build a tar-backed filesystem for MirageOS[0]. It is definitely easiest to make it append-only. I did add in-place renaming, updates (of file content), pre-allocating a file and removing the last file. We also scan the filesystem on boot and keep a mapping in-memory of file names to file metadata and block offsets, and update this memory representation when modifying the on-disk tar filesystem. If you have a lot of small files this is maybe not a great idea as you will be storing most in memory, though. For the purpose we had in mind it worked fine: A content addressable mirror of package archives. The archives exist somewhere on the web and the package file has a link to the archive and a checksum. We can then download the package and store it by the checksum. This gives integrity that the tar filesystem does not offer. Removing the last file works great if you only have one download job. Otherwise if a download fails and it is not the latest file you can rename it to `failed/<hash>-<random>` and do garbage collection in the filesystem at a later point. [0]: https://github.com/mirage/ocaml-tar/blob/main/mirage/tar_mirage.ml https://github.com/mirage/ocaml-tar/blob/main/mirage/tar_mir... Update: interestingly, this was motivated after trying to use a (mostly) LittleFS-compatible filesystem which unfortunately didn't work very well for us at the time (bugs, poor performance).

We ended up going with a very trivial system based on tar files and bitfield allocators and delegated the more filesystem-y like functionality to a higher level of the stack.

yjftsjthsd-h 3y ago

I happen to be in the middle of writing a simple tar implementation, and had in fact just started playing with the idea of just using it as an on-disk filesystem format. The caveats I can see are that 1. it's approximately append-only[0], and 2. you have to replay the whole thing in order to make sure you have the latest version of a file (I'm leaning towards doing so on mount because then I can also build an in-memory filename-to-block-address cache). Have you hit any issues, or is this as surprisingly reasonable as it sounds? [0] I mean, if the new version of a file fits in the same number of 512-byte blocks as the old version you could update in place, but that's an unreliable condition at best and also guarantees data corruption if you lose power halfway; really going append-only makes the implementation simple and also makes it easy to be really resilient.

aappleby 3y ago
I'm not on the team anymore so I don't know if they kept the tar stuff around, but it was straightforward to scan the flash for valid tar header blocks to build the allocation bitmap and then flag header blocks as invalid when files were deleted. The total number of files we needed to keep in the flash was small, so simple brute-force stuff worked fine.
e63f67dd-065b 3y ago
Not so sure about the tar part, but the append-only nature is actually really well-known: look up log-structured filesystems, where all operations append to the log and GC comes to clean up stale data later. I’m in the middle of writing a log-structured disk, and it’s really nice to work with. You get many things like clones, snapshots, etc for free. The replay problem is usually solved with periodic checkpoints of your map, and a checkpoint on shutdown. This way you only ever replay on failure, at which point performance doesn’t matter as much.
- yjftsjthsd-h 3y ago
  Yeah, knowing there were filesystems designed like that on purpose made me feel better about it:) And once you get over the initial weirdness, the ability to get any version of any file is pretty nice. Though my favorite angle is that if you can live with just burning space[0], it makes the thing so easy to implement:) [0] To be fair, a huge caveat.
mschuster91 3y ago
> The caveats I can see are that 1. it's approximately append-only[0], and 2. you have to replay the whole thing in order to make sure you have the latest version of a file Hmm. I'd go and build a separate metadata/index file that you keep updated on each write(=tar-append) operation. Grow the tar from the beginning of the underlying block device, and the metadata from the rear, and have a pointer in the filesystem header that points to the current metadata address. That way, everything is atomic, you avoid the RAM penalty from having to maintain the metadata mapping, and the only operation that can result in damage in a power-loss event is when the write of the filesystem header messes up - but that can easily be reconstructed by walking both the tar stream and the metadata stream from the beginning to the last element that has a valid header.
reycharles 3y ago
I helped build a tar-backed filesystem for MirageOS[0]. It is definitely easiest to make it append-only. I did add in-place renaming, updates (of file content), pre-allocating a file and removing the last file. We also scan the filesystem on boot and keep a mapping in-memory of file names to file metadata and block offsets, and update this memory representation when modifying the on-disk tar filesystem. If you have a lot of small files this is maybe not a great idea as you will be storing most in memory, though. For the purpose we had in mind it worked fine: A content addressable mirror of package archives. The archives exist somewhere on the web and the package file has a link to the archive and a checksum. We can then download the package and store it by the checksum. This gives integrity that the tar filesystem does not offer. Removing the last file works great if you only have one download job. Otherwise if a download fails and it is not the latest file you can rename it to `failed/<hash>-<random>` and do garbage collection in the filesystem at a later point. [0]: https://github.com/mirage/ocaml-tar/blob/main/mirage/tar_mirage.ml https://github.com/mirage/ocaml-tar/blob/main/mirage/tar_mir... Update: interestingly, this was motivated after trying to use a (mostly) LittleFS-compatible filesystem which unfortunately didn't work very well for us at the time (bugs, poor performance).