O perating s ystems t hree e asy p ieces

measurement

is the key to understanding how systems work and how to

improve them. Hard data helps take intuition and make into a concrete

science of deconstructing systems. In their study, the authors found two

main problems with AFSv1:

• Path-traversal costs are too high: When performing a Fetch or Store

protocol request, the client passes the entire pathname (e.g., /home/

remzi/notes.txt

) to the server. The server, in order to access the

file, must perform a full pathname traversal, first looking in the root

directory to find home, then in home to find remzi, and so forth,

all the way down the path until finally the desired file is located.

With many clients accessing the server at once, the designers of AFS

found that the server was spending much of its CPU time simply

walking down directory paths.

• The client issues too many TestAuth protocol messages: Much

like NFS and its overabundance of GETATTR protocol messages,

AFSv1 generated a large amount of traffic to check whether a lo-

cal file (or its stat information) was valid with the TestAuth proto-

col message. Thus, servers spent much of their time telling clients

whether it was OK to used their cached copies of a file. Most of the

time, the answer was that the file had not changed.

There were actually two other problems with AFSv1: load was not

balanced across servers, and the server used a single distinct process per

client thus inducing context switching and other overheads. The load

imbalance problem was solved by introducing volumes, which an ad-

ministrator could move across servers to balance load; the context-switch

problem was solved in AFSv2 by building the server with threads instead

of processes. However, for the sake of space, we focus here on the main

two protocol problems above that limited the scale of the system.

c

 2014, A

RPACI

-D

USSEAU

T

HREE

E

ASY

P

IECES

---

578

T

HE

A

NDREW

F

ILE

S

YSTEM

(AFS)

49.3 Improving the Protocol

The two problems above limited the scalability of AFS; the server CPU

became the bottleneck of the system, and each server could only ser-

vice 20 clients without becoming overloaded. Servers were receiving too

many TestAuth messages, and when they received Fetch or Store mes-

sages, were spending too much time traversing the directory hierarchy.

Thus, the AFS designers were faced with a problem:

T

HE

C

RUX

: H

OW

T

O

D

ESIGN

A S

CALABLE

F

ILE

P

ROTOCOL

How should one redesign the protocol to minimize the number of

server interactions, i.e., how could they reduce the number of TestAuth

messages? Further, how could they design the protocol to make these

server interactions efficient? By attacking both of these issues, a new pro-

tocol would result in a much more scalable version AFS.

49.4 AFS Version 2

AFSv2 introduced the notion of a callback to reduce the number of

client/server interactions. A callback is simply a promise from the server

to the client that the server will inform the client when a file that the

client is caching has been modified. By adding this state to the server, the

client no longer needs to contact the server to find out if a cached file is

still valid. Rather, it assumes that the file is valid until the server tells it

otherwise; insert analogy to polling versus interrupts here.

AFSv2 also introduced the notion of a file identifier (FID) (similar to

the NFS file handle) instead of pathnames to specify which file a client

was interested in. An FID in AFS consists of a volume identifier, a file

identifier, and a “uniquifier” (to enable reuse of the volume and file IDs

when a file is deleted). Thus, instead of sending whole pathnames to

the server and letting the server walk the pathname to find the desired

file, the client would walk the pathname, one piece at a time, caching the

results and thus hopefully reducing the load on the server.

For example, if a client accessed the file /home/remzi/notes.txt,

and home was the AFS directory mounted onto / (i.e., / was the local root

directory, but home and its children were in AFS), the client would first

Fetch the directory contents of home, put them in the local-disk cache,

and setup a callback on home. Then, the client would Fetch the directory

remzi

, put it in the local-disk cache, and setup a callback on the server

on remzi. Finally, the client would Fetch notes.txt, cache this regular

file in the local disk, setup a callback, and finally return a file descriptor

to the calling application. See Table

49.1

for a summary.

The key difference, however, from NFS, is that with each fetch of a

directory or file, the AFS client would establish a callback with the server,

thus ensuring that the server would notify the client of a change in its

O

PERATING

S

YSTEMS

[V

ERSION

0.80]

WWW

.

OSTEP

.

ORG

---

T

HE

A

NDREW

F

ILE

S

YSTEM

(AFS)

579