Re: DAG-enforcement versus garbage-collection?

Hi Jonathan,

Tnx very much for your answer, it has convinced me further that GC would
not be a good option for CapFs.

On Sun, November 24, 2013 23:40, Jonathan S. Shapiro wrote:
> If DAG enforcement is dropped, a practical problem arises: there is no
> known algorithm for performing a file system consistency check on an
> arbitrary-sized DCG using constant-bounded storage. The practical
> consequence of this is that file system errors can become unrecoverable
> due
> to inability to execute the recovery program. This is why the UNIX and
> Windows file systems are both strictly restricted to a lattice. In fact,
> both have a stronger restriction: the file system must be a tree at all
> nodes that are not leaf nodes (files, devices).

This is correct in UNIX only when you consider symbolic links to be leaf
node's. CapFS is part of the MinorFs user-space least-authority
file-system set for Linux that I'm currently working on on a new version.

What I'm now doing with CapFS is that I give every node a so called
'strong-path' that contains a sparse-cap. When the filesystem is asked for
the info on anything relative to such a strong-path, that relative path is
represented to the user as a symbolic link to the strong path.


That is, the following will be a possible scenario:

$ echo Hi > /minorfs/cap/rw-A19B7D9FFC9C5553/Foo.txt
$ mkdir /minorfs/cap/rw-A19B7D9FFC9C5553/Bar
$ ls -la /minorfs/cap/rw-A19B7D9FFC9C5553/
$ ln -s /minorfs/cap/ro-F0BFCD66DABFFFAC /minorfs/cap/rw-A19B7D9FFC9C5553/Bz
drwxrwxr-x 2 capfs capfs 4096 Nov 25 09:12 .
drwx------ 4 capfs capfs 4096 May  7  2013 ..
lrwxrwxrwx 1 rob rob    4 Nov 25 09:12 Foo.txt -> ../rw-C73DB8801467AA7C
lrwxrwxrwx 1 rob rob    4 Nov 25 09:12 Bar     -> ../rw-8B410CBA6649DFA8
lrwxrwxrwx 1 rob rob    4 Nov 25 09:12 Bz      -> ../rw-B4D4C4A1F889A123

While in the implementation there still is a strict distinction between
node's that are part of the main Rumpelstiltskin-tree structure, from a
user perspective, this distinction becomes more difficult to understand.

That is, on shallow inspection, every node looks like a symbolic link when
viewed from the context of its parent directory. A real symlink (that is
used as an anchor for an accepted delegation) will end up looking like a
symlink to a symlink.

In the old version this distinction was more clear as the file-system
basically hid the strong-paths in extended attributes rather than exposing
them as symbolic links. In the new version, extended attributes are used
only for read-only attenuation. This is why the broken-symlink concept
worked reasonably well and why its a bit less intuitive in the upcoming
version.

> The tree restriction
> ensures that directories can be visited in constant-bounded memory. The
> high in-degree on leaf nodes is okay because such nodes cannot participate
> in cycles (because they have an out-degree of zero). Ultimately, both
> restrictions are about preventing cycles in service of the consistency
> checking algorithm.
>
> Lest you think that this is not a problem in practice, it is. Even when
> file system graphs are acyclic, the performance of checks is closely tied
> to available storage for the checking algorithm. The time to check a large
> file system with a typical amount of fragmentation is basically driven by
> the swapping delays of the checker.
>
> Disk-GC is *notoriously* slow, even in the non-distributed case,
> essentially because it has to deal with cycles. In contrast to an
> in-memory
> GC, where you might adopt a deferred-and-coalesced RC scheme backed by a
> conventional mark-evacuate pass for cycle elimination, there is no good
> cycle detection strategy for disk-based data structures. IIRC, Marc
> Shapiro
> at Inria was "the guy" on disk-based collection for a long time. You might
> look at some of his research results before finalizing your decision.

Being slow is probably the price I will have to pay for DAG integrity
anyway. The algorithm I would probably use for validation of the DAG
integrity on soft-linking would be something like:

1) Create a soft-link candidate (that is ignored by the rest of the
operations and is invisible from the user) and check its creation time T1.
2) Get the strong-path of the soft-link candidate node P1.
3) Walk the whole sub-graph of P1:
   3a) Follow symbolic links
   3b) Follow candidate symbolic links that are not older than T1

This basically makes delegation of large sub-graphs pretty expensive an
operation. So expensive in terms of performance, that I need to be pretty
convinced of the merits of DAG-enforcement as alternative to less obvious
broken-symlinks in order to justify this cost.

Do you understand the broken-syslink issue, and if so, do you think
replacing it with an (expensive) symlink-creation-time
DAG-consistency-guarantee check is worth the cost to the performance of
persistent delegations?

> Finally, the *size* of disk has been growing much faster than the
> sustained
> transfer rate (which hasn't changed substantially in a long time). A good
> disk GC is going to be bounded by the sustained rate, not the peak rate.
> It's a useful exercise to consider just how long a mark/sweep pass
> actually
> takes on a 4TB drive, never mind a RAID-concatenated store comprised of
> *multiple* drives. This consideration (and swapping in general) is
> changing
> as solid-state store takes hold, but solid state won't replace mainstream
> use of rotating media within the next decade. There's no real technical
> impediment; it's a global manufacturing capacity issue.
>
>
> Jonathan
> _______________________________________________
> cap-talk mailing list
> [email protected]
> http://www.eros-os.org/mailman/listinfo/cap-talk
>