FileTree CRDT for SAFE Network

Core Libraries
33

I’ve taken a detour around the FUSE implementations while learning about Windows support and here’s my summary wrt high and low level approaches.

Based on the summary below I’m inclined towards the low-level FUSE route if we can map paths to inodes because we have more consistent Rust based options across Linux/MacOS/Windows, and can support hard links on all but Windows. I’m not so familiar with the low-level API though, so would need to look at that in more detail if the inode issue can be handled.

Using Path Hash as inode

On the last point, one option would be to create a u64 hash of the path for use as the inode. This would avoid the need for a map as all FS access will begin with a path to get to the inode of a file, directory or symlink and the FileTree doesn’t need to know about the path once it knows the inode.

So I did some calculations. Chances of a collision appear very small, one in 2^64 per path, so for a filesystem with:

  • a billion files (10^9 ~ 2^30) would be one in 2^34 or one in 17,179,869,184 = very safe

    • average file size 20 bytes would total ~60GB (18GB for content and maybe >40GB for metadata)
    • average file size 1KB would total ~ 1TB (960GB for content and maybe >40GB for metadata)

  • ten billion files (10^10 ~ 2^34) would be one in 2^30 or one in 1,073,741,824 = safe enough?

    • average file size 20 bytes would total ~220GB (180GB for content and maybe >40GB for metadata)
    • average file size 1KB would total ~ 9TB (9,600GB for content and maybe >40GB for metadata)

  • a thousand billion files (10^12 ~ 2^40) would be one in 2^24 or one in 16,777,216 = unsafe but still useful for archiving as some files would be trampled eventually but on SAFE old data is never overwritten so you could always get it back.

Caveats: I plucked all the ‘typical’ figures out of the air and have been known to get maths badly wrong, so both need checking! (ref: table of powers of two on Wikipedia)

Look the inode up in the FileTree

Alternatively we can just look up the path in the FileTree to get the inode as this is not a particularly frequent operation, not that expensive (one lookup per level to find the directory, get the directory contents which could be a hash-map, and get the inode from that). If we’re keeping the FileTree in client memory these operations are all in local memory.

I think we can start with one and easily switch to another as well. So I’m voting for the low-level API at this point. I’ve made a summary of both and how they could map to the SAFE FS API here:

Summary of FUSE API Options

Note: cxfuse (github, by crossmeta) is an additional option for Windows, both high and low level FUSE APIs and has commercial support, but no source code for the libraries (BSD license).

High Level API

Pros:

  • easier to implement and mapping paths to inodes taken care of

Cons:

  • no pure Rust options
  • can’t support hard links (no inodes)
  • Windows/WinFsp maybe more work to implement
  • Windows/Dokany Dokan-FUSE maybe unmaintained with some outstanding bugs

Linux / MacOS

  • fuse-mt - high level FUSE API wrapper for libfuse, as used by Syncer (github)

Windows

  • WinFsp - create user mode file systems on Windows, including an implementation of FUSE high level API (github, docs, Wiki)
  • Dokany - high level FUSE API, LGPL and MIT licensed fork of Dokan (github, dokan google group)
    • ☐ has Dokany maintained the Dokan-FUSE wrapper since departing from Dokan API? If not, the Dokany FUSE will be out of date and unmaintained
    • ☐ WinFsp github reports much faster performance than Dokany

Low Level API

Pros:

  • Rust crates available for Linux/MacOS/Windows
  • can support hard links on Linux/MacOS (but probably not Windows)
  • easier code maintenance across operating systems (all Rust)

Cons:

  • we need to map paths to u64 inodes
  • risk that WinFUSE is flaky

Linux / MacOS

  • fuse-rs - low level FUSE rewritten in Rust (github)

Windows

  • WinFUSE - low level FUSE API in Rust which uses WinFsp (github)
  • ☐ Possible issues (github):
    • “alpha” quality
    • “Finally note that this release contains the winfuse kernel driver, which exposes the FUSE protocol in the Windows kernel (via DeviceIoControl). It does not contain the wslfuse kernel driver, which will expose the FUSE protocol in WSL1 (via /dev/fuse)”
2 Likes