Re: DAG-enforcement versus garbage-collection?

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). 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.

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