Jason NikasLive FPGA Lab

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

PythonBashGitJason Nikas
node 1node 2node 3runningshared tuple space

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

CpthreadsPythonBashGitJason Nikas

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.

Timeline of a client and server: a read fails because the server closed the unused file, the client opens it again and gets a new file number, and repeats the read, which now succeeds

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.

1,000 blocks10.5 MB/s
2,000 blocks10.5 MB/s
2,500 blocks10.6 MB/s
2,750 blocks53.0 MB/s
3,000 blocks53.5 MB/s

Code

A read: a fresh cached block is used as it is; otherwise the server is asked, with the cached copy's timestamp. Lines 181–203 on GitHub
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;

Presentation and repository

  • PresentationPDF, read in a new tabReadDownload
  • RepositoryGitHub, opens in a new tabOpen

Total-order multicast

Group chat, same order

JavaGradlePythonBashGitJason Nikas

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.

Timeline of three members: member B sends a message to everyone, coordinator A gives it delivery number 1 and sends that number to the group, and each member then delivers the message to the application

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.

1 member27,802
2 members3,294
3 members1,935
4 members1,592
5 members428
7 members264

Code

Delivery: a message waits until every message numbered before it has been delivered. Lines 434–447 on GitHub
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;
}

Presentation and repository

  • PresentationPDF, read in a new tabReadDownload
  • RepositoryGitHub, opens in a new tabOpen

RPC library

Reliable calls over UDP

CpthreadsPythonBashGitJason Nikas

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.

Timeline of a client and server: a handshake gives the client its ID, a request is answered, and the client's acknowledgement is lost, so the reply stays in the server's cache until it times out

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.

1 worker112
2 workers224
4 workers439
8 workers852
16 workers1,413
32 workers1,165

Code

A request seen before: dropped while it is still being worked on, answered from the cache once it is done, or told it expired. Lines 144–167 on GitHub
// 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);

Presentation and repository

  • PresentationPDF, read in a new tabReadDownload
  • RepositoryGitHub, opens in a new tabOpen

Tools

What this course's projects were built with. Pick one to see where else I used it.

Tap the picture to see it at full size