CS 111 Lecture 1 Scribe Notes - Fall 2013

by Tushar Shrimali for a lecture by Professor Paul Eggert on November 27, 2013

Table of Contents

1. Pros and Cons of Remote Procedure Calls (RPC)
   1. Copying Data Back and Forth
   2. Marshalling - Problem and Solution
2. RPC Failure Modes
1. What can go wrong?
2. Strategies to Tackle the Problem
3. X Window System Protocol
1. Theoretical Implementation
2. Protocols to improve
4. Network File Systems
1. NFS Protocol
2. NFS Synchronization Issues

In the previous lecture were introduced to Remote Procedure Calls and how they differ from ordinary procedure calls. In this lecture, we will discuss RPCs and their associated problems in detail. Additionally, we will learn about Network File systems as protocols that employ RPCs.

Pros and Cons of Remote Procedure Call (RPC):

+ No Corruption of Other Memories
+ Caller Callee can have Different Architectures
- Difficulty in Copying Data back and forth

Problems with Copying Data

Let's say the following system specifications are present in the network transfer:

• Caller x86 (little Endian) LSB comes first
• Callee SPARC (Big Endian) MSB comes first

This is a problem since the callee won't receive the data in the say way the caller would send it.

There are three different protocols to do so:

1. Always default to Big Endian
2. Always default to Little Endian
3. Send the first byte of each message (By keeping a flag)

The Big endian approach is the most common (tends to win for historical reasons).
The last approach favors performance and is addressed by hardware support (The "swap bytes" insns in x86).

Problem of Marshalling

This arises when the caller tries to communicate a complocated data structure to the callee leading to the need of sending a compact/pickled version of the data across. We need a convention of sending arbitrary data over networks (the most common way to do so being XML).

Solution:

The pickled version needs to be compact so as to not waste enough CPU time. There is a glue code that is generated from the protocol spec (by an automated program called rpcgen). The aim here is to automate the RPCs as much as possible

Code Example:

Say the caller wants to say:
stat (fd, &st)
int struct stat*

The Pickled version that should be communicated would look like:
fd: int st: struct stat*

The following are the client and the server codes as they respectively generate and interepret the glue code.

CLIENT CODE:

1. pickle fd
2. ship fd over net
3. wait for an answer
4. unpickle struct stat
5. *st - Unpickled version return unpickled st value

SERVER CODE:

int stat (int fd, struct stat *p)
{
if (tab[fd])
---
---
*p = st;
}

RPC Failure Modes

What can go wrong?

1. Messages can get lost - When you ship the package to the network, the network might be overloaded and drop the packet.
2. Transmission error (on one of the wires connecting client server) - Messages can get corrupted. (Say the network is requesting File #24 and the client read it as File #23)
3. Network might go down or be slow.
4. Network and Client might be working perfectly but the server might be down (or might be slow/busy due to some bug).
5. We're assuming in here that the client code is perfect. The problem with this assumption is that client might be evil and/or doesn't respond to the server.

Strategies to Tackle the Problem

1. Message getting corrupted (Say, there's a byte error)

   Checksum the message (at least 32 bit):
   This would be done at the protocol level (end-to-end) since it increases the chance of detecting corruption. If the message is corrupted, the client should resend it.

2. Response Timeout (No sequence number when following TCP)
   *The client has no idea whether the server got the message. Do you keep trying ? Do you wait for the server to return an eror message ?*

   This problem has several differnet solutions:

   • At least once RPC: You Keep trying. This is suitable where doing something twice doesnt hurt you. In other words, the requests are idempotent.
   • At most once RPC: Return an error (err = ETIMEOUT). This is not suitable for idempotent requests. The drawback here is that the application must know about the error
   • Exactly once RPC: What we want. You can never really fully build this completely, there will always be some source of error.

X Window System Protocol

Theoretical Implementation

The system was developed 30 years ago and is still in use in netwoking functions.

Working of the protocol in theory -

Client: Send X Send "blue" Read reply

Server: Read Y Read Y Read "blue" Send "ok"

The client sends request in queue and waits for the server to respond. The above theoretical implemetation of the protocol is really slow and the following are some ways to speed up the process.

   
Images taken from http://www.cs.ucla.edu/classes/spring12/cs111/scribe/16c/

Protocols to Improve:

1. Give up the idea of using RPCs since they take too long.
2. Use Batch calls: Doing a bunch of calls at once to improve performance. The only problem is that the API would have to be changed.
3. Make calls in parallel
   • The requests may collide with each other
   • More load on server, net, client
   • Requests should not assume earlier request worked
   • Requests can be served out of order
   • HTTP pipelining: Lets you issue several requests simultaneously and get reponses at once
4. Cache results of inquiries
5. Prefetching: Look at old answers and predict answers to future requests.

Network File Systems

Network File System is a file system protocol designed to let clients access files and data shared on a server. The client accesses these files via the NFS protocol which is a form of RPC. The protocol syntax resembles the UNIX system calls to a large extent.

NFS Protocol

CREATE (dirfh, name, attr) - Return file Handle and attributes
MKDIR (dirfh, name, attr)
REMOVE (dirfh, name)
RMDIR (dirfh, name)
LOOKUP (dirfh, name) -Return file Handle and attributes for the requested file
READ
 (fh, data)
WRITE (fh, data)

So what is a 'file handle' ?
Essentially, it is a large integer (much like an inode number) that uniquely identifies a file on a server. The server has root priveleges since it needs to access file names by their inode number and needs access to the kernel.

A naive implementation requires NFS servers to keep track of client state. this is troublesome since the server would now be at the mercy of the client. However, according to NFS model, the server doesnt care about the client state. In other words, the NFS server is stateless, if it crashes or reboots the client wouldn't notice or care (except for performance).

NFS Synchronization

However, the NFS client does guarantee close to open consistency. This means that if client 1 issues a close command for a certain file and client 2 issues an open command for the same file, client 2 will open the a correctly updated version of the file. This is due to the overhead induced when closing a file as mentioned above in the Parallel Issues section: when a file is closed, all pending writes are finished first before the file is finally closed (remember closes are "slow"). Thus, when client 2 opens the same file, it will have the correct updates to the file.

NFS faces synchronization issues.
For example:

Process 1:
Gettimeofday()
Read (fd, buf, 1024)

Process 2:
Write (fd, buf, 1024)
Gettimeofday()

If both requests start at the same time then the read request will return a cached value. Thus, it does not have read after write consistency.

However, the client does have open after close consistency. If client 1 issues a close command for a file and client 2 issues an open command for the same file, client 2 will open the correct updated version of the file. This is because when the file is closed, all pending writes MUST BE finished before the file is opened again.

Hitachi Uniform Storage file mode 4100:
This is a network file system whose specifications were examined in class. The file system is a four node cluster storage subsystem with an overall response time of 1.25 ms. http://www.spec.org/sfs2008/results/res2013q4/sfs2008-20130905-00229.txt

Specifications and test result of such filesystems can be measured from specbench.org which follows the SPECsfs2008 benchmark.