Xref: utzoo comp.protocols.nfs:1871 comp.arch:21188 Path: utzoo!utgpu!watserv1!watmath!att!linac!uwm.edu!zaphod.mps.ohio-state.edu!samsung!olivea!uunet!mcsun!ukc!dcl-cs!aber-cs!athene!pcg From: pcg@cs.aber.ac.uk (Piercarlo Antonio Grandi) Newsgroups: comp.protocols.nfs,comp.arch Subject: The merits of FCFS for file servers Message-ID: Date: 4 Mar 91 21:05:05 GMT References: <28975@cs.yale.edu> <476@appserv.Eng.Sun.COM> Sender: pcg@aber-cs.UUCP Organization: Coleg Prifysgol Cymru Lines: 97 Nntp-Posting-Host: aberdb In-reply-to: lm@slovax.Berkeley.EDU's message of 1 Mar 91 21:37:30 GMT X-Old-Subject: Re: how many nfsd's should I run? [ this article may have already appeared; I repost it because probably it did not get out of the local machine; apologies if you see it more than once ] I had written, on whether it pays to have enough nfsds that there is a chance that several of them may queue on a disk and thus exercise the elevator sorting algorithm of the Unix kernel: pcg> The latter argument is somewhat doubtful as there is contradictory pcg> evidence about the relative merits of FCFS and of elevator style pcg> sorting as used by the Unix kernel. lm> Ahem. References, please? I've looked at this one in detail, this lm> should be interesting. Apparently the gist of the argument is that elevator sorting imposes excessive latency. There are several variations on elevator sorting that try to break the input queue into segments in order to limit the maximum latency to to which a request may be subjected. Some argue that having a segment length of 1 (FCFS) is not that bad, actually, depending on conditions. I was myself surprised by this, but on second thoughts it is not that incredible; if the filesystem is careful in laying out blocks in a physically clustered way (the SunOS for one is fanatical about this, as you well know :->), and requests for sections of the same file are closely clustered in time (not an uncommon circumstance), the arm will tend to move optimally anyhow (there is some paper, possibly in TOCS, about the DTSS filesystem in which they find this to be the case). This is one side for the contradictory evidence; the other side is that theoretical analysis shows that FCFS should be pretty bad, and then there is the article (in BTLJ, I seem to remember) in which it is reported that the addition of disk sorting to V7 made three disks across which load was balanced perform as a single disk with one fixed arm, which is a big win. The assumption there is that thruput is important, not latency, so maybe there is little contradiciton with the above analysis. Also, the V7 filesystem was prone to dispersing file blocks, thus making the arm move far more randomly than with designs that use a bitmap for frelist. I am not at home unfortunately, so I cannot give you now many article or book references. Ah, I actually have around here the following, which is a bit old: %A Robert Geist %A Stephen Daniel %T A continuum for disk scheduling algorithms %J TOCS %I ACM %V 5 %N 1 %D FEB 1987 This is a bit old; the first paragraph is Scheduling algorithms for moving-head disks have been studied for many years, but which algorithm is "best" is still an open question. The first section continues on the relative merits of FCFS, SSTF, and variations on SCAN. The rest of the article shows that even if their favourite technology is superior to FCFS, the superiority is not massive. The contradictory evidence is neatly summed in the conclusions: Certainly the efficient implementation of V(R) presented in Section 4 is no more complex than SSTF (or SCAN), so the question is easily reduce to one of V(R) versus FCFS. Our simulation results and those of other studies [4, 8, 9] continue to indicate horrible performance for FCFS, our tests from a real system indicate that FCFS is merely inferior and far short of catastrophic. This paper was published in a journal not yet subject to Top Secret classification, its subversive contents notwithstanding. I will add that I have seen other (equally unclassified :->) papers in which FCFS was shown to be actually on a par with (in admittedly particular cases even better than) more sophisticated policies under some fairly reasonable assumptions. Did I seem them in some IEEE transactions? I will check... I seem also to dimly remember that Wiederhold's book, "Database Design" has a relevant discussion on arm scheduling. IMNHO a nice short segment variation on elevator sorting (but not the historical V7 Unix one) is probably, even if somewhat more complex preferable to FCFS, because it can be expected either to win or not to lose. Going back to an NFS environment, allowing nfsds to queue outstanding requests may therefore or may not be a win; it may be a lose, because in certain environments having many nfsds can be a performance loss greater than the advantage of elevator sorting. Finally, as I am fond of repeating, architecture is a difficult balancing of contradictory requirements and evidence. Flexibility is the key, and reducing the cost of certain mechanisms makes flexibility affordable... -- Piercarlo Grandi | ARPA: pcg%uk.ac.aber@nsfnet-relay.ac.uk Dept of CS, UCW Aberystwyth | UUCP: ...!mcsun!ukc!aber-cs!pcg Penglais, Aberystwyth SY23 3BZ, UK | INET: pcg@aber.ac.uk