A versioned file system comprises a set of structured data representations, such as XML. Each structured data representation corresponds to a “version,” and each version comprises a tree of write-once objects rooted at a root directory manifest. Each version in the versioned file system has associated therewith a “borrow window.” When it is desired to reconstruct the file system to a point in time (or, more generally, a given state), i.e., to perform a “restore,” it is only required to walk (use) a single structured data representation (a tree). During a restore, metadata is pulled back from the cloud first, so users can see the existence of needed files immediately. The remainder of the data is then pulled back from the cloud if/when the user goes to open the file. As a result, the entire file system (or any portion thereof) can be restored to a previous time nearly instantaneously. A “fast” restore is performed if an object being restored exists within a “borrow window” of the version from which the system is restoring.