Xref: utzoo comp.protocols.nfs:1900 comp.arch:21299 Path: utzoo!news-server.csri.toronto.edu!cs.utexas.edu!sun-barr!newstop!exodus!appserv!slovax!lm From: lm@slovax.Eng.Sun.COM (Larry McVoy) Newsgroups: comp.protocols.nfs,comp.arch Subject: Re: The merits of FCFS for file servers Message-ID: <492@appserv.Eng.Sun.COM> Date: 8 Mar 91 07:12:39 GMT References: <28975@cs.yale.edu> Sender: news@appserv.Eng.Sun.COM Reply-To: lm@Eng.Sun.COM Followup-To: comp.protocols.nfs Organization: Sun Microsystems, Inc. Lines: 39 In article , pcg@cs.aber.ac.uk (Piercarlo Antonio Grandi) writes: |> 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). I hate to break an otherwise perfect record, but for once I have to agree. :-) And for the same reasons. I think it is a right of passage for all new engineers (well, fs hackers at least) to think they can improve disksort(). I was no different. I did do a nice job of actually measuring a system, building a simulator, and running the data through all the algs I could dream up (inorder, elevator, hacksaw, sstf). By the way, Unix (at least SunOS) doesn't use an elevator, it uses what I call hacksaw, which is in increasing block order, then one long seek back. Anyway, I found that the BSD FFS is doing a nice job of clustering related requests (the whole point of cylinder groups, remember them?). My conclusion was that FIFO would work just fine. My data showed about 5% difference between optimal and the worst of them all (don't remember which that was). I am *not* sure that this scales up. The server that I measured (a local Sun server dishing up home directories and diskless client gunk), was not that busy. I wouldn't call it idle, but the I/O patterns were definitely bursts, and the bursts where typically related I/O's (inode, data, dir stuff). I predict, off the cuff, that lightly to medium loaded servers will typically work just fine with FCFS. I'm not sure how bad things will get when the server's arm is saturated, but I suspect that disksort() helps a lot in that case. --- Larry McVoy, Sun Microsystems (415) 336-7627 ...!sun!lm or lm@sun.com