Recursively walk a directory using File Coordination

I’m trying to extract information from all files of a particular type, so I think using NSFileCoordinator.ReadingOptions.immediatelyAvailableMetadataOnly on each file before acquiring a full read lock on it (if it’s the right file type) would make sense. Am I on the right track?

So, the first question here is "what are you actually trying to do"?

The problem here is that, by design, file systems are basically shared databases with minimal locking, which means that file coordination for JUST metadata isn't necessarily all that useful. As a concrete example, take a basic task like calculating the size of the directory. You do that by summing up the size of every file, but it's always possible for a file you've looked at to change after you've looked at it, at which point the size of the directory is no longer "right". Now, adding file coordination into that process may (depending on the configuration you pick) change the "answer" you get, but that's only because it delayed writes "later" than they would otherwise have been. The writes are still going to happen, at which point you're just getting a different "wrong" than you would have gotten without file coordination.

Looking at "NSFileCoordinator.ReadingOptions.immediatelyAvailableMetadataOnly" in particular, a careful read of its documentation has a good "hint" about what it's "for". It starts by saying:

"Specifying this option grants the coordinated read immediately"

...but the key point there is actually what follows:

"...(barring any conflicts with other readers, writers, or file presenters on the same system)"

In other words, what you're actually saying is "let me read the metadata but let anyone who happens to be doing something finish first". Whether or not that's what you want... depends on what you're trying to do. Looking at the two "extremes":

1. If you're working inside a directory you "own" and/or where the contents are modified with some consistent "pattern", then it can help you get more "coherent" results. For example, if two files are always modified in the same coordinated write, then immediatelyAvailableMetadataOnly means you're less likely* to see the "intermediate" state where only one of them has been modified.

2. If you're scanning in the "public" file system (like the user’s home or Documents directory on macOS), then immediatelyAvailableMetadataOnly has a lot less value. You don't really have any control over what's going on, so it's likely that at least part of the waiting will be for things you don't care about. More the point, the "public" file system is also much more dynamic so the longer it takes to scan, the more likely it is that whatever you've scanned has ALREADY changed.

*One lesson I've been taught over and over again is to avoid relying on the file system working EXACTLY the way you expect. Good file system code should be flexible enough that an unexpected situation doesn't break the app.

Covering a few other details:

What’s the recommended way to recursively walk through a directory tree using File Coordination?

The race conditions inherent to the file system are what lead to the file presenter "side" of the file coordination system. That is, you can't scan a directory "fast enough" that you’re GUARANTEED to have an accurate "view" of the file system state. However, you CAN tell the system "this is what I'm interested in" and let the system tell you when something changes.

From what I understand, coordinating a read of a directory only performs a “shallow” lock; this would mean that I’d need to implement the recursive walk myself...

I'll warn you now, the words "implement the recursive walk myself" are a bit of a red flag. It is (probably) possible to read the contents of a directory faster than NSDirectoryEnumerator. It is NOT easy to do* and can't really be done with any of our high-level APIs. If you want to "recursively coordinate", I would probably do this:

*Case in point, what contentsOfDirectory(at:includingPropertiesForKeys:...) actually does is use NSDirectoryEnumerator to "fill up" an array, then return that array.

1. Use coordinate(with:queue:byAccessor:) to issue an asynchronous coordinated read against a directory.

2. Inside that block, use enumerator(at:includingPropertiesForKeys:...) with"skipsSubdirectoryDescendants" to enumerate the directory’s immediate contents (a "shallow" enumeration).

3. For every directory you encounter, issue another (asynchronous) call to "#1".

This will walk through the entire hierarchy without a lot of extra overhead and without issuing "nested" coordinated reads against the large hierarchy. One note on the concurrency side of this— to avoid a thread explosion, you'll want to use the same OperationQueue for #1; however, if you're dealing with very large hierarchies, increasing maxConcurrentOperationCount above "1" might have some** benefit.

**Unfortunately, being more specific than that is very difficult, as it depends on the file system and the performance of the target device. If performance is critical, this is something you'd need to experiment with and "tune", possibly on a device/target basis. I mentioned this for "completeness", but I would just use "1" unless this is a critical part of your product.

__
Kevin Elliott
DTS Engineer, CoreOS/Hardware

Thank you for the detailed reply!

So, the first question here is "what are you actually trying to do"?

I’m adding a bulk import feature to my shoebox app. The user selects a folder, and the app walks the directory hierarchy looking for files of the type it supports (suppose they’re images for example’s sake). The app extracts image metadata by parsing the file, and then copies the image into a “Library” package if everything was successful.

More the point, the "public" file system is also much more dynamic so the longer it takes to scan, the more likely it is that whatever you've scanned has ALREADY changed.

The folder selected by the user is a user-visible one which may be dataless or have dataless contents. Ideally files would only be downloaded if they’re actually image files, which is why I brought up immediatelyAvailableMetadataOnly. This is a good point, though, thanks; I had this idea that I’d want to get a consistent snapshot of the entire hierarchy without any “tearing”, but I suppose there’s little reason to do that. I was thinking that I’d want to lock each file in a directory before I unlock the directory itself, but really why delay writes/moves/etc after the scan if that’ll mean the scan is out-of-date anyway?

I'll warn you now, the words "implement the recursive walk myself" are a bit of a red flag.

I’m aware of readattrlistbulk :) Using a shallow directory enumerator to get the contents seems like a good idea.

So, would you say something like this would make sense (in pseudocode)?

func scan(directory: URL) async {
    await coordinate(forReading: directory)
    for child in contents(of: directory) {
        if child.isDirectory {
            Task { await scan(directory: child) }
        } else {
            // don’t bother using immediatelyAvailableMetadataOnly?
            guard child.fileType == .image else { continue }

            // don’t block the directory scan on children completing, so spawn a new unstructured task
            Task {
                await coordinate(forReading: child)
                let photoMetadata = parseMetadata(child)
                let imageID = UUID()
                let urlInLibrary = PhotoLibrary.url.appending(imageID)
                copy(from: child, to: urlInLibrary)
                Persistence.add(imageID, metadata)
            }
        }
    }
}

The folder selected by the user is a user-visible one which may be dataless or have dataless contents. Ideally, files would only be downloaded if they’re actually image files, which is why I brought up immediatelyAvailableMetadataOnly.

I was probably harder on "immediatelyAvailableMetadataOnly" than I needed to be. I don't think it's necessarily "bad" to use it, as you're basically telling the system "please finish up anything you happen to be doing, then let me see the data". Most of the time, that's pretty a pretty reasonable approach. The trap is in thinking that you this:

...I had this idea that I’d want to get a consistent snapshot of the entire hierarchy without any “tearing”,

...which it definitely won't. Strictly speaking, you could get that (by cloning the directory), but that opens up a whole other set of messes. More to the point, in practice, there's a level of "user cooperation" involved with any operation in the "public" file system. That is, either:

• The user "paused" their operations in that hierarchy so that you'd get a "reasonable" result.

OR

• The user didn't do that, in which case it is basically impossible for your app to guarantee a reasonable result.

Your app’s role here is really about taking "reasonable" precautions (for example, immediatelyAvailableMetadataOnly isn't a bad option) and providing the user clear feedback about what you "did" (so the user can figure out if something went wrong). In both cases, you need to make a judgement call about how "far" you want to take either approach.

So, would you say something like this would make sense (in pseudocode)?

Yes, but... there are issues:

(1)
I think using Task() for I/O work like this is probably a mistake. The Task intentionally disables overcommit because overcommit was/is one of the major issues with GCD (case in point, the bug I mention below is caused by "overcommit"). However, the problem is that large-scale I/O work is EXACTLY why GCD implemented overcommit in the first place.

Putting that in concrete terms, imagine you have 10 cores and nothing else is going on. The default behavior here is:

• GCD keeps spinning up threads every time I/O blocks, so you end up with 80+ threads which are all twiddling their thumbs waiting on the kernel. That's a lot of overhead waste and generally makes things "slower”.

• Task spins up 10 threads, all of which block twiddling their thumbs* waiting on the kernel. The CPUs are basically idle, but no other work will proceed because Task doesn't overcommit.

*In the long run, Task should be able to fix this if/when some kind of non-blocking Swift Async API exits. However, something like that doesn't really exist, at least not for the "general" file system.

Both of those are "bad", with plenty of room for a lively debate about who is more "wrong-ish". However, if your goal is to actually maximize I/O, then what you really need is GCD's behavior (so you can use the CPU for "other stuff") but constrained to a much more reasonable number of threads (probably somewhere between "4" and "10"). My personal recommendation for that would be to use OperationQueue and then constrain the width. However, there is another problem...

(2)
As it happens, I was working on filing a bug on our code for this here, which should be constraining the queue width (but doesn't). Unfortunately, it turns out queue width isn't the only issue here; Mach ports are as well. I haven't debugged it in depth, but I think what's going on is that every call you make to coordinate(with:) is setting up the coordination call against the target, with the operation queue then acting as the target for the result of that coordination.

The problem with that is that each of those pending coordination requests consumes a Mach port, so when "enough" operations get backed up, your app runs out of Mach ports and dies. I don't know how much of an issue that will be under real-world conditions, but the problem was trivial to reproduce with my "massive" (~1.7 million objects) test directory. The directory count required was pretty large (40,000-60,000 depending on queue width), but not so large that I'd consider it "impossible".

So, what I think you actually want to do is manually queue each operation, then use the synchronous API to do the actual coordination call.

Since I wrote code for all of this anyway, I've attached that code below. Note that this was originally written as test code, so it's not the neatest work I've ever done, nor is the error handling all that great. However, it did run for "minutes", not "seconds", which is much better than the original implementation.

__
Kevin Elliott
DTS Engineer, CoreOS/Hardware

Your app’s role here is really about taking "reasonable" precautions (for example, immediatelyAvailableMetadataOnly isn't a bad option) and providing the user clear feedback about what you "did" (so the user can figure out if something went wrong).

That makes sense as a philosophy to keep in the back of my head, thanks.

I think using Task() for I/O work like this is probably a mistake.

Ah, my mistake, I should’ve clarified that this would all be running inside a single actor, so the resulting behavior should be equivalent to an NSOperationQueue with a width of 1.

However, if your goal is to actually maximize I/O, then what you really need is GCD's behavior (so you can use the CPU for "other stuff") but constrained to a much more reasonable number of threads (probably somewhere between "4" and "10").

I’ll make sure to keep this in mind when I start profiling.

The problem with that is that each of those pending coordination requests consumes a Mach port

Would this maybe be solved by reusing a single NSFileCoordinator() or by passing file access intents to coordinate(with:) in batches (as suggested by the docs)? Should I be doing that anyway? I’d rather avoid using the synchronous coordination API.

I think using Task() for I/O work like this is probably a mistake.

Ah, my mistake. I should’ve clarified that this would all be running inside a single actor, so the resulting behavior should be equivalent to an NSOperationQueue with a width of 1.

OK. SO, FYI, I did some very rough performance testing with the code I posted yesterday, and a queue width of "4" was ~4x faster than #1. However, the big question here is the nature of the data you're expecting to process. While we generally talk about it as I/O bound (and it technically "is"), I think that term can be somewhat misleading, particularly when you're talking about the devices’ local storage or other "fast" SSDs. The issue here is that, in practice, much of the volume’s catalog data is either already in memory or WILL be streamed into memory fairly "quickly" as you start iterating over the device. That means that in many cases, the real bottleneck isn't disk I/O but is actually how fast you can make syscalls into the kernel. Using multiple threads lets you "throw" more requests into the kernel, which speeds things up until the request volume starts delaying each other.

The problem with that is that each of those pending coordination requests consumes a Mach port.

Would this maybe be solved by reusing a single NSFileCoordinator()?

No, I don't think so. coordinate(with:) is using Mach ports because that's how it's "told" that it can actually run, but the problem is that you can "find" new files to scan MUCH faster than you can actually process the coordinate calls. I didn't check this when I was yesterday, but there are ~30,000 coordinate calls "waiting" to fire when the crash actually occurs. That ridiculous backlog is what you need to prevent.

or by passing file access intents to coordinate(with:) in batches (as suggested by the docs)?

It would probably reduce the issue, but not enough that I'd consider it a real "solution". The "backlog" here really needs to be more like "10", not "1000's".

Should I be doing that anyway?

However, on the doc side, this did catch my eye:

However, if you make multiple, concurrent calls to coordinate(with:queue:byAccessor:), you risk deadlocking with another process that is similarly making multiple concurrent calls to its file coordinator. Wherever possible, invoke coordinate(with:queue:byAccessor:) once, passing in multiple file access intent objects.

I hadn't considered that, and I think that's a fairly "scary" edge case. I don't think it will matter here, but it could be a real issue anytime you're doing actual modifications. More importantly, I think the way to understand that risk is that you can't just "pile up" requests (like my original code did).

I’d rather avoid using the synchronous coordination API.

First off, why? Theoretically, "coordinate" has some benefit here since you can do "other" work while you're waiting; however, in practice:

1. You shouldn't actually be waiting that long.

2. Taking advantage of the "extra" time means generating a backlog into coordinate, which is exactly what we were trying to avoid.

3. If you actually "are" waiting, throwing more requests into the system is unlikely to be all that helpful.

Maybe there's some benefit I hadn't considered, but for your purposes, I don't think there's a huge difference between the two APIs.

Shifting to the technical issue:

I’d rather avoid using the synchronous coordination API.

If you're going to use the async API, then the critical issue is that you need to throttle the number of calls you make into coordinate(with:queue:byAccessor:). I'm not sure what the "right" answer to that is, but my current inclination would be to separate "directory discovery" from "coordination queuing" by initially doing something like this:

1. Enumerate finds a directory.
2. Add directory to pending directory list.
3. Check the count of pending coordinate calls.
4. Based on #3, pull an entry off of the pending list and call coordinate(with:queue:byAccessor:).

However, once pending is "high enough", you can actually shift to doing #4 at the start of each directory you process so that you're now submitting coordinate calls at roughly the same rate as you’re processing them.

__
Kevin Elliott
DTS Engineer, CoreOS/Hardware