← writing

Designing the Controller/Dstore protocol: what broke first

Project: Distributed File Storage

The protocol for this project is deliberately small: a Controller, some number of Dstores, and Clients, talking in plain line-delimited text over persistent TCP sockets. No message queue, no consensus algorithm, just enough structure to replicate a file across several stores and know, definitively, when it's safe to say the store succeeded.

A store looks like this:

Client     → Controller   STORE <filename> <filesize>
Controller → Client       STORE_TO <port1> <port2> <port3>
Client     → Dstores      (raw bytes, one connection per port)
Dstore     → Controller   STORE_ACK <filename>   (×R)
Controller → Client       STORE_COMPLETE

The Controller decides which R Dstores get a given file with a simple greedy rule: count how many files each connected Dstore currently holds, and hand the write to whichever hold the fewest. Waiting for the replicas to actually confirm the write uses a CountDownLatch per filename, initialized to R. Every STORE_ACK counts it down; a background thread blocks on latch.await(timeout, ...), and on timeout it rolls the file back out of the index rather than leaving it wedged half-stored. None of that is exotic. It's the part that looks obviously correct that broke first.

The bug

Handling a STORE has to answer two questions before doing anything else: does this filename already exist, and if not, reserve it. Early on, those were two separate steps (a lookup against the index, then, if it came back empty, a call to add the entry) with nothing serializing them against a second thread doing the exact same thing for the exact same filename.

That's invisible with one client. It's not invisible under the test harness this coursework was marked against, which fires concurrent operations at the Controller specifically to catch this class of bug. Two threads racing to store the same filename could both read "does not exist" before either had written its reservation, and both would proceed: two separate sets of Dstores writing to what the index still thought was one logical file. Whichever STORE_COMPLETE arrived last would win, silently, with no error surfaced to whichever client actually lost the race.

It's the textbook shape of a concurrency bug: correct in isolation, wrong under interleaving, and the kind of thing you don't see until you deliberately go looking for it, because a single-threaded test suite will never trigger it.

The fix, and why it's small

The fix is one synchronized block:

synchronized (index) {
    if (index.getFileInformation(filename) != null) {
        sendMessage(controllerSocket, "ERROR_FILE_ALREADY_EXISTS");
        return;
    }
    index.addFile(filename, filesize, selectDstores());
}

What's worth noticing is how little of the operation actually needs to be inside that block. The lock only has to cover the read-check-write on the index: the moment a filename is successfully reserved, nothing else in the system can race against it for that name, so sending STORE_TO, streaming the file, and waiting on the ACK latch can all happen unsynchronized. Wrapping the whole store operation in the same lock would have been the lazier fix, and it would have quietly serialized every store against every other store in the system, regardless of filename, for no reason connected to the actual bug.