# bcachefs status, roadmap: ## Performance: ### Core btree: The core btree code is heavily optimized, and I don't expect much in the way of significant gains without novel data structures. Btree performance is particularly important in bcachefs because we not shard btrees on a per inode basis like most filesystems. Instead have one global extents btree, one global dirents btree, et cetera. Historically, this came about because bcachefs started as a block cache where we needed a single index that would be fast enough to index an entire SSD worth of blocks, and for persistent data structures btrees have a number of advantages over hash tables (can do extents, and when access patterns have locality they preserve that locality). Using singleton btrees is a major simplification when writing a filesystem, but it does mean that everything is leaving rather heavily on the performance and scalability of the btree implementation. Bcachefs b-trees are a hybrid compacting data structure - they share some aspect with COW btrees, but btree nodes internally are log structured. This means that btree nodes are big (default 256k), and have a very high fanout. We keep multiple sorted sets of keys within a btree node (up to 3), compacting/sorting when the last set, the one that updates go to, becomes too large. Lookups within a btree node use eytzinger layout search trees with summary keys that fit in 4 bytes. Eytzinger layout means descendents of any given node are adjacent in memory, meaning they can be effectively prefetched, and 4 byte nodes mean 16 of them fit on a cacheline, which means we can prefetch 4 levels ahead - this means we can pipeline effectively enough to get good lookup performance even when our memery accesses are not cached. On my Ryzen 3900X single threaded lookups across 16M keys go at 1.3M second, and scale almost linearly - with 12 threads it's about 12M/second. We can do 16M random inserts at 670k per second single threaded; with 12 threads we achieve 2.4 random inserts per second. Btree locking is very well optimized. We have external btree iterators which make it easy to aggressively drop and retake locks, giving the filesystem as a whole very good latency. Minor scalability todo item: btree node splits/merges still take intent locks all the way up to the root, they should be checking how far up they need to go. This hasn't shown up yet because bcachefs btree nodes are big and splits/merges are infrequent. ### IO path: IO paths: the read path looks to be in excellent shape - I see around 350k iops doing async 4k random reads, single threaded, on a somewhat pokey Xeon server. We're nowhere near where we should be on 4k random writes - I've been getting in the neighborhood of 70k iops lately, single threaded, and it's unclear where the bottleneck is - we don't seem to be cpu bound. Considering the btree performance this shouldn't be a core architectural issue - work needs to be done to identify where we're losing performance. Filesystem metadata operation performance (e.g. fsmark): On most benchmarks, we seem to be approaching or sometimes mathing XFS on performance. There are exceptions: multithreaded rm -rf of empty files is currently roughly 4k slower than XFS - we bottleneck on journal reclaim, which is flushing inodes from the btree key cache back to the inodes btree. ## Scalability: There are still some places where we rely on walking/scanning metadata too much. ### Allocator: For allocation purposes, we divide up the device into buckets (default 512k, currently support up to 8M). There is an in-memory array that represents these buckets, and the allocator periodically scans this array to fill up freelists - this is currently a pain point, and eliminating this scanning is a high priority item. Secondarily, we want to get rid of this in memory array - buckets are primarily represented in the alloc btree. Almost all of the work to get rid of this has been done, fixing the allocator to not rescan for empty buckets is the last major item. ### Copygc: Because allocation is bucket based, we're subject to internal fragmentation that we need copygc to deal with, and when copygc needs to run it has to scan the bucket arrays to determine which buckets to evacuate, and then it has to scan the extents and reflink btrees for extents to be moved. This is something we'd like to improve, but is not a major pain point issue - being a filesystem, we're better positioned to avoid mixing unrelated writes which tends to be the main cause of write amplification in SSDs. Improving this will require adding a backpointer index, which will necessarily add overhead to the write path - thus, I intend to defer this until after we've diagnosed our current lack of performance in the write path and worked to make is fast as we think it can go. We may also want backpointers to be an optional feature. ### Rebalance: Various filesystem features may want data to be moved around or rewritten in the background: e.g. using a device as a writeback cache, or using the `background_compression` option - excluding copygc, these are all handled by the rebalance thread. Rebalance currently has to scan the entire extents and reflink btrees to find work items - and this is more of a pain point than copygc, as this is a normal filesystem feature. We should add a secondary index for extents that rebalance will need to move or rewrite - this will be a "pay if you're using it" feature so the performance impact should be less of a concern than with copygc. Some thought and attention should be given to what else we might want to use rebalance for in the future. There are also current bug reports of rebalance reading data and not doing any work; while work is being done on this subsystem we should think about improving visibility as to what it's doing. ### Disk space accounting: Currently, disk space accounting is primarily persisted in the journal (on clean shutdown, it's also stored in the superblock) - and each disk space counter is added to every journal entry. As the number of devices in a filesystem increases this overhead grows, but where this will really become an issue is adding per-snapshot disk space accounting. We really need these counters to be stored in btree keys, but this will be a nontrivial change as we use a complicated system of percpu counters for disk space accounting, with multiple sets of counters for each open journal entry - rolling them up just prior to each journal write. My plan is to extend the btree key cache so that it can support a similar mechanism. Also, we want disk space accounting to be broken by compression type, for compressed data, and compressed/uncompressed totals to both be kept - right now there's no good way for users to find out the compression ratio they're getting. ### Number of devices in a filesystem: Currently, we're limited to a maximum of 64 devices in a filesystem. It would be desirable and not much work to lift that limit - it's not encoded in any on disk data structures, just in memory bitmasks. After that we'll support 256 devices, and to go past that we'll need another, larger `bch_extent_ptr` type and a new superblock section for larger device index fields. `bch_extent_ptr` uses 44 bits for the offset field (in units of 512 byte sectors), giving us a current maximum device size of 8 petabytes. We already have code for different types of checksum fields within an extent for different size checksums, so adding support for a new, larger extent ptr type will be fairly trivial. ### Device management: We need a concept of "failure domains", and perhaps something more, for managing large numbers of devices with bcachefs to make sense. Currently, disks can be assigned labels that are essentially paths, delimited by periods, e.g. controller1.ssd.ssd1 controller1.ssd.ssd2 controller1.hdd.hdd1 controller2.hdd.hdd1 controller2.hdd.hdd2 This lets disks be organized into a heirarchy, and referring to any part of the heirarchy will include all the disks underneath that point: e.g. controller1 would refer to the first three disks in the example. This is insufficient, though. If a user has a filesystem with 60 drives, all alike, we need a way to specify that some disks are on the same controller and that multiple replicas should not be stored on the same controller, and we also need a way to constrain how replicated writes are laid out. Today, in a 60 devices filesystem with 3x replication, each allocation will be unconstrained which means that the failure of _any_ three devices would lead to loss of data. A feature that addresses these issues still needs to be designed. ### Fsck Fsck performance is good, but for supporting huge filesystems we are going to need online fsck. Fsck in bcachefs is divided up into two main components: there is `btree_gc`, which walks the btree and regenerates allocation information (and also checks btree topology), and there is fsck proper which checks higher level filesystme invariants (e.g. extents/dirents/xattrs must belong to an inode, and filesystem connectivity). so named because bachefs originally (when it was bcache) not only did not have persistent allocation information, it also didn't keep bucket sector counts up to date when adding/removing extents from the btree - it relied entirely on periodically rescanning the btree. This capability was kept for a very long time, partly as an aid to testing an debugging when uptodate allocation information was being developed, then persistent, then transactionally persistent allocation information was developed. The capability to run `btree_gc` at runtime has been disabled for roughly the past year or so - it was a bit too much to deal with while getting everything else stabilized - but the code has been retained and there haven't been any real architectural changes that would preclude making it a supported feature again - this is something that we'd like to do, after bcachefs is upstreamed and when more manpower is available. Additionally, fsck itself is part of the kernel bcachefs codebase - the userspace fsck tool uses a shim layer to run the kernel bcachefs codebase in userspace, and fsck uses the normal btree iterators interface that the rest of the filesystem uses. The in-kernel fsck code can be run at mount time by mounting wiht the `-o fsck` option - this is essentially what the userspace fsck tool does, just running the same code in userspace. This means that there's nothing preventing us from running the current fsck implementation at runtime, while the filesystem is in use, and there's actually not much work that needs to be done for this to work properly and reliably: we need to add locking for the parts of fsck are checking nonlocal invariants and can't rely solely on btree iterators for locking. Since backpointers from inodes to dirents were recently added, the checking of directory connectivity is about to become drastically simpler and shouldn't need any external data structures or locking with the rest of the filesystem. The only fsck passes that appear to require new locking are: * Counting of extents/dirents to validate `i_sectors` and subdirectory counts. * Checking of `i_nlink` for inodes with hardlinks - but since inode backpointers have now been added, this pass now only needs to consider inodes that actually have hardlinks. So that's cool. ### Snapshots: I expect bcachefs to scale well into the millions of snapshots. There will need to be some additional work to make this happen, but it shouldn't be much. * We have a function, `bch2_snapshot_is_ancestor()`, that needs to be fast - it's called by the btree iterator code (in `BTREE_ITER_FILTER_SNAPSHOTS` mode) for every key it looks at. The current implementation is linear in the depth of the snapshot tree. We'll probably need to improve this - perhaps by caching a bit vector, for each snapshot ID, of ancestor IDs. * Too many overwrites in different snapshots at the same part of the keyspace will slow down lookups - we haven't seen this come up yet, but it certainly will at some point. When this happens, it won't be for most files in the filesystem, in anything like typical usage - most files are created, written to once, and then overwritten with a rename; it will be for a subset of files that are long lived and continuously being overwritten - i.e. databases. To deal with this we'll need to implement per-inode counters so that we can detect this situation - and then when we detect too many overwrites, we can allocate a new inode number internally, and move all keys that aren't visible in the main subvolume to that inode number.