Date: Tue, 10 Feb 1998 08:29:23 +0000 (GMT) From: Terry Lambert <tlambert@primenet.com> To: roark_hilomen_at_meridian@meridian-data.com Cc: freebsd-fs@FreeBSD.ORG Subject: Re: Soft update usage Message-ID: <199802100829.BAA21865@usr05.primenet.com> In-Reply-To: <9802098870.AA887071056@meridian-data.com> from "roark_hilomen_at_meridian@meridian-data.com" at Feb 9, 98 04:43:15 pm
next in thread | previous in thread | raw e-mail | index | archive | help
> Does anyone know if "Soft Updates" has been in use in the industry > or is OpenBSD and now FreeBSD the first to implement it? BSDI has them. The original Ganger/Patt work was done in SVR4 (if you are familiar with SVR4 internals, this is obvious from looking at the published Appendix A code). > How extensively has it been tested (outside the current FreeBSD flurry)? Kirk would be a better person to answer that. > And for that matter, is anyone testing it on a large multi-client system? I don't know; they should. > Has anyone tried crashing it and seeing if FSCK works well and as advertised > with Soft Updates? That's Kirk's testbed. He uses a SCSI drive and two machines; he halts the one from the other, randomly, and fsck's (among other tests). He claims many, many months of reliable operation. > I'm trying to see how cutting edge this technology is. It's "medium". It's a good leap past current implementations, but the paper was published several years ago, and it does not support general updates between layered FS's. Effectively, Ganger and Patt did this: 1) Determine all operations that could be done on SVR4 UFS 2) Determine the events that would result from these operations, as small DAG fragments (directed acylic graphs). 3) Invent a structure called a "dependency" that defined relationships between these DAG's. 4) Invent a mechanism for ensuring ordering of operations in dependency order (this mechanism is superior to DOW -- delayed ordered writes -- a USL patent-pending technology, because there is, in effect, write gathering and meta-data ordering without flush -- unlike DOW). 5) Hard-code (rather than parametrically code) these dependency queueing events. This is the step that degeneralizes the Ganger/Patt code, and makes it a lot of work to port -- at a 3-5% performance increase (negligible in comparison to the win of soft updates themselves over using sync writes to guarantee ordering of operations). The DOW mechanism is basically the classic "banker's algorithm", which determines potential cycles in a graph and denies operations based on the possibility of cycles. The soft updates mechanism (effectively) precomputes transitive closure over the graph, so any insertion that would result in a cycle is seen as depending on prior insertions. The difference in these mechisms can be best characterized by: DOW: Prevent operations which are dangerous. Also, using back-tracking via Howard's algortihm, prevent operations which *may* be dangerous, even if it ends up that they *aren't* dangerous. SU: Prevent only operations which are dangerous. I *seriously* recommend the following books: Algorithms in C++ Robert Sedgewick Addison-Wesley Publishing Company ISBN 0-201-51059-6 The Art Of computer Programming _Volume 1: Fundamental Algorithms_ Donald Knuth Addison-Wesley Publishing Company ISBN 0-201-03809-9 UNIX Systems for Modern Architectures _Symmetric Multiprocessing and Caching for Kernel Programmers_ Curt Schimmel Addison-Wesley Publishing Company ISBN 0-201-63338-8 For more information on graphical algorithms. Don't be put off by the Sedgewick book; it is very light on the code and heavy on the graph theory (chapters 29 through 34 -- I recommend chapters 24 through 28, on geomentric algorithms, as well). For example, if you were to implement a lock manager using graphical representations and cycle detection, you could probably expect to do about 20,000 transactions a second (this is the measured rate through the NetWare for UNIX lock manager, which used an intention mode lock manager based on graphical algorithms). Of course, you may not want to use this in an SMP kernel, since it's only two orders of magnitude faster than Tuxedo, which used the same algorithm as the BSD lockmgr code. If you used a graphical soloution to locking in an SMP kernel, you'd have to put up with your kernel being faster, more highly concurrent, and unfortunately scalable to a larger number of processors than SVR4 or Solaris could every hope to support. Then where would you be? Oh. Yeah. You'd be at the cutting edge. Couldn't have that... Heh. 8-). Terry Lambert terry@lambert.org --- Any opinions in this posting are my own and not those of my present or previous employers. To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-fs" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199802100829.BAA21865>