API to allow explicit compaction/garbage collection

[gtaska]

From what I can tell, compaction/garbage collection only occurs as the file system is being used (written to).

On devices with longer erase times (I'm currently looking at a part that takes 1.6 seconds to erase 32kB), this will lead to poor performance during write function calls if compaction/garbage collection is needed.

It would be very useful to have a separate API that the system integrators can call to explicitly initiates a rounds of compaction/garbage collection. An API like this would allow them to schedule expensive erase operations at times that have less likelihood of impacting their system's write performance.

An example of where this may be useful, is for when data is only intermittently/periodically being written to flash, but when it does, it needs to be written as quickly as possible. Garbage collection can then be performed over the longer time periods between the write bursts, ensuring that the flash is in a readily written to state by the time the next series of write calls occurs.

While this may not eliminate the need for all compaction/garbage collection during write calls, it has the potential to improve the consistency of write call durations.

[geky]

This is a good idea for the garbage collection/block allocator, and wouldn't be too difficult to add. I am hoping to address the issues in #75 by moving away from garbage collection completely, but adding a function to eagerly populate the block allocator could be a good temporary solution.

It also wouldn't be too difficult to extend the block allocator with information about which blocks have been erased, currently it doesn't track this since it only erases on demand.

One issue is that unlike SPIFFS or Dhara, LittleFS doesn't persist the garbage collection state on disk. This limits the use of eager garbage collection if your device loses power often, and wouldn't change the cold-start time.

The metadata compaction is a different system and might be a bit more complex. You could iterate over all metadata-pairs and force a compaction if the metadata-pair is full past some threshold, but in doing so you are effectively losing potential writes from the last erase. But maybe this is acceptable if the threshold is sufficiently high around ~75%? It could be a user provided option.

The metadata compaction operates on the sub-block level, so it currently throws away the existing metadata when it compacts.

schedule expensive erase operations

One of the future challenges, even with a different block allocator, is tracking which blocks have been erased. LittleFS doesn't require erased blocks to be all 0xffs, and this allows some interesting use cases such as cheap SD/eMMC and encrypted block devices.

The downside is, in order to know which blocks have been erased, we would need to store that somewhere. One of the more promising allocator schemes is basically just a bitmap in a file, but in order update such a file you likely end up needing to erase+write new blocks. So updating the allocator to indicate a block is erased would require an erase, which sort of defeats the purpose. Still need to explore this more, but it promises to be challenging.

[gtaska]

This appears to be a dupe of #493. Closing.

[geky]

I'm going to reopen this since it is subtly different than #493 and worth noting, #493 is a signalling mechanism from littlefs to disk, where as this (explicit compaction/garbage collection) is a more general feature for littlefs that may be useful. Development-wise they involve different layers. They may both be solved by an allocator redesign (#75), but we'll have to see.

[victorallume]

I've been experiencing some performance issues as well, and was looking for a garbage collection trigger.

In my testing I noticed the following behaviour - write(append) operations would gradually take longer as a file gets bigger. Then a single write operation would take about double the previous write, then the next one would be considerably shorter, and the process would repeat. I figured the 'long' write is performing a garbage collection (is this assumption correct?). Then I introduced another file, which gets over-written every time I append to the original file (this is to simulate the real-world operation of our system). Instead of a 'long write' to the file I'm appending to (as happened before), the append op takes a similar time to before, but the op to the extra file takes a lot longer than the other writes to it would have taken. So I'm figuring that write op has taken over the garbage collection.

So I got to thinking: why not just have a dummy file I write to that effectively triggers the garbage collection? Could this be made in a deterministic way (I'm guessing I'm just lucky with my test setup that the gc is happening only on the extra file, while in the wild it might happen on either). Any thoughts?

[geky]

Hi @victorallume, this does sounds like metadata compaction. One of the two garbage-collecting-like processes. And one of the two main open problems for littlefs right now (#203).

Out of curiosity how large is your block size?

The key thing is that metadata compaction occurs per metadata-pair, with each directory being made out of one or more metadata-pairs. So if the files are in the same directory, they probably share a metadata-pair, which would show the behavior you're describing: one file write might compact the metadata-pair so the other file doesn't need to.

If you moved the other file into a different directory, then you wouldn't see the largest cost, but eventually the second directory would need to compact as well.

while in the wild it might happen on either

Yep, this it could happen to either. If one file fits in an "inline" file or has a bigger file name, it's metadata may take up more space which could make it more likely to trigger a compaction. But this isn't guaranteed, so shouldn't be relied on.

why not just have a dummy file I write to that effectively triggers the garbage collection?

This is interesting and I suppose could work if you're able to instrument the block device to detect the compaction. But it probably wouldn't work in the general case. If you have multiple files in the directory it could take up multiple metadata-pairs, which means you might not be compacting the right metadata-pair.

---

You might be interested in enabling the metadata_max configuration option. This is a workaround that lets you artificially limit the size of metadata in each metadata-pair to keep the cost of compaction usable. It wastes disk space, but is currently necessary for reasonable performance on devices with large block sizes:

littlefs/lfs.h

Lines 260 to 264 in 9c7e232

	// Optional upper limit on total space given to metadata pairs in bytes. On
	// devices with large blocks (e.g. 128kB) setting this to a low size (2-8kB)
	// can help bound the metadata compaction time. Must be <= block_size.
	// Defaults to block_size when zero.
	lfs_size_t metadata_max;

[victorallume]

Hi @geky, thanks for the reply. The block size we're using is 4kB, and all of the files in question are in the same directory.

[kyrreaa]

I'm using LittleFS on a 8Gbit NAND flash and would love to trigger compaction to speed up my directory listings later.
Since my particular NAND allows 4 partial page writes (1024 bytes at a time per 4096 byte page if one wants instead of full 4096 byte) without erasing and since NAND can change any 1's in memory to 0's only tracking or identifying used/free space is at least possible.

[geky]

Unfortunately, relying on the masking nature of flash is not a good general solution. It works for many (most?) flash devices, but a number of flash devices disallow it due to either write perturbation concerns or because of hardware-backed ECC.

The current design I'm working towards batches this up with the allocator redesign (#75), and adds an optional "block map" that tracks the status of every block in the filesystem.

Such a block map could also be used to track bad blocks and allow blocks to be reserved for non-filesystem use.

[kyrreaa]

Agree completely on the abuse of NAND masking. I was more thinking of the ability to write partial blocks and combining this knowledge with the erase-block information. An erase wears flash too, and for example for my flash, if the first 1/4 has been written to but next 1/4 still shows FF's it can update the first block's information with a new revised version without requiring erasing and without having to go to next block. The read operation can still read the entire 4096 sector (in my case) and this is supported by the automatic ECC of the chip. It specifically mentions up to 4 partial writes are allowed. I am just thinking how this flexibility could be exploited after noticing some massive delays during testing creating small(ish) (120 sectors of 4096 bytes) and measuring the directory listing performance for each addition. I noticed that once I reached enough files to compact the entires the delay dropped significantly. I created a graph to test it. I understand ofcource that this mostly applies to my current implementation and interface speed also affects it, but it should scale regardless for anyones access, depending on size of buffers etc. (4096 byte access, 409664 blocks, 4096 write buffer and a total of 4096 blocks (of 409664 bytes) storage with a lookahead of 4096/8 hoping it would allow full chip overview...)

(Edit: Updated graph)
Compacting (when closing the file that triggered it) took a very very long time though... Is this due to the alphabetical sorting perhaps?

[kyrreaa]

I ran my test again now that 2.9 is out!

Looks like there are small improvements in listing speed! (Edit: Nope, it was caused by other compiler changes. But performance is not worse so that is good :) )

I've also tested the manual garbage collection / compacting and it seems to work.
I am curious though if there are any metrics we can extract on how the metadata are organized before/after compaction. It would be good to be able to verify what the compaction did and maybe even analyse the metadata to determine how much wasted space/programming blocks a block of metadata contains.