Various littlefs operations are quite slow

[manuhrao]

Hi all:
I am using littlefs on an mx25r32 QSPI, driven by an nrf5340 running zephyr.
when I have approx 750 files( many/most of them 50 byte binary files), the fs_stat operation takes almost 5.6 seconds

Further more, when I am writing the (50 byte) files, I note that it typically takes ~300ms, but every ~25th attempt takes 12 seconds

A few questions

1. Is that expected/normal?
2. If no, what should I expect, and how can I improve this behavior?

Thanks a lot!

[PiKa20]

I am using littlefs on an mx25r32 QSPI, driven by an nrf5340 running zephyr.
when I have approx 750 files( many/most of them 50 byte binary files), the fs_stat operation takes almost 5.6 seconds

I'm also using littlefs on nRFf52840+W25Q64, SDK is nRF connect SDK v2.6.1, writing 50 bytes of data is also 300-400ms, and when I try to write data non-stop, it also blocks for more than 10 seconds every once in a while!

I open the file every time -> write data -> close the file.

Since I often modify the same file over and over again, I suspect littlefs is garbage collecting when it has 10 seconds of blocking (just a guess, I can't verify).

[Viatorus]

We see a very similar problem. It seems to have something to do with the lookahead buffer on our side.

@geky Could it be that littlefs is unsuitable for several megabytes of data (EMMC)?

During an initial write operation on our file system after startup, the entire file system is read first (~60 MB, ~50000 read operations -> 6 seconds) before one write operation is performed.

[manuhrao]

@PiKa20 , I actually DO NOT modify the same file, and instead create new files. So you and I have different use-cases that result in similar behavior.

@Viatorus , a simple "size-of-filesystem" operation often takes us as much as 5s ( and does so EACH TIME), and scales with number of files.

[manuhrao]

I have some additional information worth sharing @PiKa20 @Viatorus
Summary: the call to lfs_dir_splitting ( AKA compaction ) takes almost 9 seconds under certain conditions.

1. When I create <15 files in a folder, but create a LOT of folders, I dont hit compaction. However, each new attempt of the exact same operation takes longer than it did before. ( see picture 1)
2. When I create more than ~20 files in a folder, I hit compaction.( see picture 2)
3. It seems like the SIZE of each file doesnt matter as much as the number of files, but I cannot be certain about it.
4. (Semi-related ) When the file system uses a new block, it (often?always?) needs to erase it. That takes ~35ms on my chip.
5. (Unrelated ) When the file system has a lot of files, fs_vfsstat takes a long time

Much of this might be explained by the architecture of littlefs, and it would be good to have someone who knows about it chime in to clarify my understanding.

Lastly, and this might be beyond the scope of this conversation, my device has a battery, and thus "sudden-power-withdrawal"
is less important to me( I can stop writing under some voltage/state of charge) than wear leveling. Are there settings that would benefit me particularly?

[geky]

So, the TLDR, there are two significant bottlenecks in littlefs at the moment:

1. The block allocator needs to traverse the filesystem to fill the lookahead buffer. This occurs on the first write after mount, and after allocating all blocks in the current lookahead buffer.

   You can increase the lookahead buffer to make this scan occur less often, but you can never completely eliminate the traversal because otherwise littlefs wouldn't be able to know when blocks are freed.

2. Metadata compaction scales $O(n^2)$ with the block size.

   metadata_max exists as a hack to limit this runaway performance, at a cost of wasting most of the space in metadata blocks. Still, several users have commented that this is a reasonable tradeoff for achieving acceptable performance.

These bottlenecks often end up at odds with each other, since one way to reduce the traversal cost is to increase the logical block size. Fortunately metadata_max escapes this at a storage cost, and even more fortunately the devices that run into these bottlenecks usually have storage to spare, since the amount of storage is the whole problem.

That being said, these are both being worked on, but fixing these problems require some pretty fundamental changes to the filesystem, so it's a slow process.

It's also worth mentioning that these are both spike costs that can't be avoided, but can be moved out of critical writes via lfs_fs_gc if you have idle time.

---

when I have approx 750 files( many/most of them 50 byte binary files), the fs_stat operation takes almost 5.6 seconds

Currently, the only way for littlefs to know how many blocks are free/inuse is to traverse the entire filesystem. Eventually, this will hopefully be improved with same work that improves block allocation (on-disk block map), but in the meantime that's how it is.

You can mitigate this by increasing the block size to some multiple of the actual block size, larger blocks == fewer blocks to traverse, but this will probably have some other impacts such as making compaction times worse.

This is the main reason we don't include lfs_fs_size in lfs_fs_stat implicitly. But getting the size is probably the main reason to call lfs_fs_stat, so I don't think it's unreasonable for Zephyr to combine the two.

Further more, when I am writing the (50 byte) files, I note that it typically takes ~300ms, but every ~25th attempt takes 12 seconds

This is probably metadata compaction, but could be the block allocator if your lookahead buffer is really small (it's probably metadata compaction). You can tinker with metadata_max or use lfs_fs_gc to move compaction out of important code paths.

@Viatorus , a simple "size-of-filesystem" operation often takes us as much as 5s ( and does so EACH TIME), and scales with number of files.

I would like to make littlefs cache the "size-of-filesystem", but it would still need to scan after most write operations. It's low priority.

When I create <15 files in a folder, but create a LOT of folders, I dont hit compaction. However, each new attempt of the exact same operation takes longer than it did before. ( see picture 1)

It makes sense this is avoiding compaction. Each dir gets its own metadata block, and if you never fill up a metadata block: no compaction. The tradeoff would be storage consumption, but depending on your use case you may not care.

The increasing operation time is curious, I wonder if it's because path-lookup time is increasing as the parent directory is filling up? Path-lookup is currently $O(n)$. It would be interesting to see how much time is spent reading/progging/erasing.

When I create more than ~20 files in a folder, I hit compaction.( see picture 2)

This is expected. Metadata logs can always contain outdated metadata, so littlefs doesn't know if a metadata fits or needs to be split until after trying to compact the block. By separating files into multiple directories you're sort of precomputing the will-it-fit logic.

It seems like the SIZE of each file doesnt matter as much as the number of files, but I cannot be certain about it.

The size of files does not matter for metadata compaction*, but it does affect the allocator scans.

*Big asterisk: If a file is small enough to be inlineable (<inline_size, <block_size/4, and <cache_size), it is inlined in the metadata log directly. In which case the size of the file does increase metadata compaction. It sounds like this is not the case here, or else the effect would be much more noticeable.

(Semi-related ) When the file system uses a new block, it (often?always?) needs to erase it. That takes ~35ms on my chip.

Yes, littlefs currently doesn't persist erase state information, so it has to always pessimistically erase blocks on demand. This is also being worked on as part of the block map work.

(Unrelated ) When the file system has a lot of files, fs_vfsstat takes a long time

Explained above hopefully.

Lastly, and this might be beyond the scope of this conversation, my device has a battery, and thus "sudden-power-withdrawal" is less important to me( I can stop writing under some voltage/state of charge) than wear leveling. Are there settings that would benefit me particularly?

I don't think I've had this asked before, it's a very interesting question.

I think the short answer is this is out-of-scope.

Actually... I'm struggling to think of any case where ignoring powerlosses would lead to any advantage... Most of the costs come from dealing with the awkwardness of flash.

Even if you used RMW operations to avoid the $O(n^2)$ compaction cost, you would still be erasing basically every write, which is not great (this is what v1 did).

Oh wait, sorry, you asked about configuration settings and I started thinking about theoretical invasive changes. No, there's no tricks in the case. Having a safe shutdown just means less things to worry about, but littlefs has already worried about those things.

You might be able to save on block device cache flushes, but that would be below littlefs (in Zephyr?)