Distributed Systems
Four systems on my own: calls over an unreliable network, group chat in one order, a cached network file system, and a runtime that moves running programs between machines.
9.5Course grade
Distributed runtime
Programs move between machines while they run
A runtime that runs small programs across several machines. The programs share data through a distributed tuple space, and a running thread can move to another machine without stopping.
Network file system
With a client cache
What it is
A network file system: programs open, read, write and truncate files that live on another machine, through a C library over UDP. The client keeps recently used blocks in a cache, so it doesn’t ask the server for the same data again and again.
A server that forgets
The server keeps no record of its clients. It holds only a map from the file numbers it hands out to the files it has open, forgets files that go unused, and saves the last number it gave out, so it never reuses one after a restart. When the server has closed or forgotten a file, the client opens it again and repeats the request.

The cache
The cache holds blocks by file and position and throws out the least recently used one when it is full. A block counts as fresh for a set time after it was fetched. After that, the client asks the server again and sends the time the file was last changed; if it hasn’t changed since, the server answers with nothing to read, and the client keeps its copy.
A write of a whole block updates the cache and goes on to the server.
How much it helps
Reading a 10 MB file, a big enough cache cut the packets sent from about 12,800 to about 2,600. Without a cache, larger blocks were faster on their own: under 3 MB/s with 1 KB blocks, about 21 MB/s with 8 KB.
The cache pays off only once it holds the whole working set: at 2,500 blocks it was no faster than none at all, and at 2,750 it was five times faster.
Results
Read throughput by cache size, in 4 KB blocks, for a workload that uses 2,560 blocks. Below that size the cache can't hold them all and keeps throwing out blocks it will need again.
Code
CacheBlockT *cached = cache_get(server_fid, block_index);
if (cached && cache_is_fresh(cached)) {
#ifdef DEBUG
printf("[DEBUG] Block is cached and fresh returning cached...\n");
#endif
long available = (long)cached->data_len - block_offset;
if (available <= 0) {
pthread_mutex_unlock(&lock);
return 0;
}
if (bytes_to_copy > available)
bytes_to_copy = available;
memcpy(buf, cached->data + block_offset, bytes_to_copy);
client_file->pos += bytes_to_copy;
pthread_mutex_unlock(&lock);
return bytes_to_copy;
}
PacketT packet = create_packet(READ);
packet.body.read_req.fid = client_file->server_file->fid;
packet.body.read_req.cached_mtime = cached ? cached->mtime : 0;
packet.body.read_req.cached_mtimensec = cached ? cached->mtimensec : 0;
packet.body.read_req.length = block_size;Total-order multicast
Group chat, same order
What it is
A group chat where every member sees every message in exactly the same order, even when messages are sent at once from different machines. It is written in Java: a membership service over TCP keeps track of who is in each group, and messages travel over UDP.
Three layers
Each message passes down through three layers, and each one adds a guarantee:
- Reliable: every member gets the message and acknowledges it.
- Uniform: a member delivers it only once everyone has it, and drops duplicates.
- Total order: every member delivers it in the same position.
One order for everyone
One member acts as coordinator. When a message arrives, the coordinator gives it the next delivery number and sends that number to the whole group. Every member holds messages until the one numbered just before has been delivered, so all of them deliver in the same order. If the coordinator leaves or fails, another member takes over the numbering.

The cost in packets
The guarantees aren’t free. Reliable delivery to N members costs 2N packets; the uniform layer has every member pass the message on, 2N²; and total order sends two messages through it, one with the message and one with its number. That predicts 4N² packets per message: 64 in a group of four.
We measured it: four members sending 10,000 messages each sent 2,570,374 packets, 64.2 per message.
Results
Messages delivered per second with one member sending, by group size. Every message reaches every member, in the same order everywhere.
Code
private List<SerializableObject> checkBuffer() {
List<SerializableObject> ready = new ArrayList<>();
String id = deliveryOrder.get(delivered + 1);
while (id != null && messages.get(id) != null) {
ready.add(messages.remove(id));
Printer.printDebug(api.getNetworkManager().getPort() + " [CatocManager] (Group " + groupId + ") TRM Request with ID " + id + " is being delivered");
deliveryOrder.remove(delivered + 1);
delivered++;
id = deliveryOrder.get(delivered + 1);
}
return ready;
}RPC library
Reliable calls over UDP
What it is
A library for calling a service on another machine over UDP, which can lose, repeat or reorder any packet. The server side is in C, the client side in Python. A client finds a server by broadcasting a discovery message, sends its request, and gets the reply, with each request carried out at most once however many times it is sent.
At most once
Every request carries the client’s ID and a sequence number. The server remembers, for each client, the last number it saw and its reply, and keeps that memory on disk, so it survives a restart.
A repeat of a request still being worked on is dropped. A repeat of one already answered gets the stored reply again, without running it twice. Once the client acknowledges the reply, the server lets the stored copy go; if a repeat arrives after that, the server answers that the reply expired rather than running the request again.
When things fail
We walked through each failure on its own. A lost request is simply sent again. A lost reply is resent from the server’s memory. A client that crashes and restarts cancels what it had in flight. A server that crashes and restarts reloads its memory from disk, so it still recognises a repeat it had already run.

Threads
The server runs three threads of its own: one receives and sorts packets, one sends replies, one answers discovery. The application’s worker threads take requests from a queue per service.
With a single client, a request that does no work and its reply took 1.324 ms on average over 1,000 tries, all of which succeeded.
Results
Requests per second the server answered, by number of worker threads: 20 clients sending 500 requests each, every request a primality check on a large number. The fastest and slowest client times were left out.
Code
// Duplicate currently in process
if (servicelist_containsReq(serviceRegistry, req) || reqlist_contains(activeRequests, req, NULL)) {
#ifdef DEBUG
printf("Request was active so dropping...\n");
#endif
return 1;
}
// Duplicate already processed
RequestT *cached;
int success = reqlist_contains(cachedRequests, req, &cached);
if (success) {
#ifdef DEBUG
printf("Reply was cached, %s\n", cached->packet.payload == NULL ? "but expired..." : "so resending...");
#endif
cached->clientAddr = req->clientAddr;
cached->clientAddrLen = req->clientAddrLen;
cached->id = req->id;
if (cached->packet.payload == NULL)
cached->packet.type = EXPIRED;
updateCachedRequest(cached, 1);
reqlist_add(replies, cached);Tools
What this course's projects were built with. Pick one to see where else I used it.