#project#cmu#java#file-systems#distributed-systems#raft

RexFS, a Raft-Based Distributed File System

Published on
•
10 mins read
•
––– views

RexFS: a naming server and replicated storage servers coordinated by Raft

This is a course project for CMU 15-440/640: Distributed Systems. It was a group project, so the rest of this post says "we"; the Learnings at the end are mine.

At a glance

  • Course: CMU 15-440/640 Distributed Systems, Spring 2023
  • Stack: Java, Raft consensus, RPC over TCP
  • Scope: naming server (path index), replicated storage servers, locking and coherence, Raft-based replication
  • Team: group project
  • Code: not public (course integrity policy)

Introduction

RexFS is a distributed file system (DFS): it stores, reads and writes files across several machines while hiding that distribution from the user, so using it feels like using a local file system.

Replication is managed by the Raft consensus algorithm. We picked Raft over alternatives like Paxos for its safety guarantees and its comparatively simple design. The system is written in Java, which gave us object-oriented structure, concurrency primitives and a large standard library.

Raft keeps the nodes consistent with each other, so RexFS keeps returning correct results through partial network failures.

Fig-1 Replicated state machine architecture (borrowed from the Raft paper). The consensus algorithm manages a replicated log containing state machine commands from clients. The state machines process identical sequences of commands from the logs, so they produce the same outputs.

Design

Clients and servers interact as shown in Figure 2. They refer to files by path: a string that uniquely identifies a (possibly replicated) file or directory. Clients mostly read and write file and directory contents; storage servers maintain those resources and serve them to clients. In our design, storage servers also manage file metadata such as size, and they respond to commands from the naming server.

Fig-2 RexFS Architecture.

In many practical DFS designs, clients never talk to storage servers directly; their whole view of the file system is a single naming server, so they only need one address. The naming server tracks the directory structure and which servers hold the primary and secondary replicas of each file. A client that wants to operate on a file asks the naming server, which replies with the IP address and port of the storage server hosting it; the client then talks to that storage server directly. The naming server also provides an interface through which new storage servers register.

Paths

Paths are strings of the form /directory/directory2/.../dir-or-filename, passed through every interface in the system. We index them with a trie. Paths are always relative to the root /, and they have to be comparable to each other, which matters for locking (below).

Storage Servers

A storage server provides two interfaces. The client interface is for file operations and offers three of them: read, write and size query. The command interface is for management by the naming server, which can ask the storage server to create a file, delete it, or copy it from another server as part of replication. The storage server's job is to respond to these requests, which may arrive concurrently.

A storage server keeps all of its files in local storage on its own machine, laid out to mirror its view of the whole file system. If storage server k uses /var/storagek as its root and hosts /directory/README.txt, the file lives at /var/storagek/directory/README.txt on that machine. A server that does not know about a file (because it is stored elsewhere) has nothing at that path. This scheme also makes data persist across storage server restarts for free.

Naming Server

The naming server is an object that holds the current state of the directory tree plus the operations on it. It exposes two interfaces. The service interface lets a client create, list and delete directories; create and delete files; check whether a path is a valid directory or file; look up the IP address and client port of a storage server; and lock and unlock files and directories. The registration interface is what storage servers call once, on startup, to join the file system: the server sends its IP address and the ports for its client and command interfaces. The naming server later hands the client port to clients and uses the command interface to keep the storage server's state consistent. During registration the storage server also lists every file in its local directory. Files the naming server does not know about are added to its tree; files it does not want that server to keep are deleted on request.

The naming server also replicates frequently read files across several storage servers, without any involvement from the client. The replication section has the details.

Communications

Naming servers, storage servers and clients all need to talk to each other. Rather than reuse the RPC library from earlier labs, we built this on HTTP-based RESTful APIs. Every component exposes a uniform interface, which decouples the pieces and lets each evolve on its own. Requests identify resources by URL, and the resources are separate from the representations returned to the client. All commands, responses and data are exchanged as JSON.

Coherence and Thread Safety

Each server must be thread-safe on its own: it performs local actions without letting its state become inconsistent. Consistency across the whole file system is much more relaxed. The design is fragile and leans heavily on well-behaved clients. Without locking, consistency also depends on luck, because clients keep no state that would let them treat a file as open or reserved.

A single read or write completes correctly once it reaches the storage server, but any other client may interfere between requests: a file one client is using can be overwritten, deleted, moved to another server and re-created without that client noticing. With locking in place, the file system stops well-behaved clients from doing any of that until the lock is released.

We also had to decide when the naming server should command each storage server to create or delete files and directories so that their views stay consistent. Ideally the storage servers would not have to be kept in lockstep, but the interfaces are simple and leave little room for lazy creation or deletion schemes. A file the naming server has agreed to delete, for example, must not remain reachable through later requests to the storage server.

Locking

RexFS has a custom lock type and locking scheme that well-behaved clients use to stay consistent across several requests. Each file and directory can be locked for shared reading or exclusive writing. Many clients may hold a read lock on the same object at once, but an exclusive lock excludes every other client. Shared access covers operations that do not interfere with each other, such as reading a file or listing a directory; exclusive access covers writing files and modifying the directory tree.

Locking any object also takes a shared lock on every object along its path, including the root; otherwise a file locked for reading could disappear when another client removes its unlocked parent directory. The order in which those parent locks are taken matters. Taken haphazardly, two clients can each hold one lock while waiting for the other's, and deadlock.

There is one more constraint. Some clients need to lock several objects at once, and doing that in arbitrary order can deadlock for the same reason. So paths are comparable, and clients take locks in the total order that comparison defines. This interacts with the parent-locking rule above, since locking an object also locks everything on the path to it; the comparison order therefore has to be chosen so that the two rules together cannot deadlock.

The locks also have to be fair. A client waiting for a lock must not keep losing it to clients that asked later. This matters most for writers: without fairness, a steady stream of readers can keep sharing the lock among themselves and starve a writer forever.

RexFS therefore grants locks first come, first served. A later request is never granted before an earlier one, except that two shared requests with no exclusive request waiting between them are granted together.

Replication

RexFS replicates according to a simple policy. A file gains one more replica for every 20 read requests, as long as enough storage servers are connected to hold the extra copies. On a write, the naming server picks one storage server to keep the file and invalidates (removes) every other copy before the remaining one is updated.

The naming server cannot see individual reads and writes or per-file traffic, so it counts shared locks as reads and exclusive locks as writes.

Replication has to coexist with locking: well-behaved clients must not be able to disturb a replication in progress, but they must still be able to read the existing copies of a file while a new copy is being made.

APIs

Several APIs return JSON error responses like this:

{
    "exception type": "FileNotFoundException",
    "exception info": "File/path cannot be found."
}

Since everything on the wire is JSON, read() and write() have a problem: they carry byte arrays, and JSON has no byte type. We base64-encode them.

Potential Failure Scenarios

Network Partitions

Network partitions are inevitable in a distributed system. If a partition cuts the leader off from the majority, the majority elects a new leader, while the old one, unaware, may keep serving clients. Raft guarantees those writes are never committed (they lack a majority), but from the client's point of view they look accepted and are later overwritten.

High Load and Resource Exhaustion

Incoming requests can outrun what the nodes can process, causing high latency, dropped client requests, or a crash from resource exhaustion. Our implementation keeps data consistent under normal operation but has no load balancing or rate limiting to prevent this.

Unbounded Log Growth

We implemented neither log compaction nor snapshots, so the log grows without bound, degrading performance and consuming resources over time. It is a limitation rather than a failure, but it would hurt a long-running deployment.

Learnings

The write-up above is what we built. This is what I took away from building it.

  • List the failure scenarios before designing, not after. We wrote the section above near the end. Partitions, overload and unbounded log growth each forced a design change, and listing them on day one would have made the storage-server and log-compaction designs simpler.
  • Raft is simple on paper; persistence and restarts are where the bugs live. Leader election and log replication follow the paper closely. Almost every hard bug we hit was about what survives a crash: which state has to be fsync'd before replying, and how a restarted node rejoins without corrupting the log.
  • Give each piece of state one owner. Java offers plenty of concurrency primitives, which is exactly the problem: the naming server, the storage servers and the Raft module each touched shared state from several threads. Once every piece of state had a single owning thread (or lock) and everything else went through messages, the code became far easier to reason about.
  • Keep consensus separate from the file system. Raft should replicate an opaque command log, and the naming and storage logic should not know it is replicated. Where the two leaked into each other (locking, in particular) we paid in both correctness and testability.
  • Build a deterministic test harness early. Reproducing a partition-induced bug by hand is hopeless. A harness that can drop, delay and reorder messages between in-process nodes would have found most of our late bugs in the first week.

Things we would still like to add: a proper membership-change protocol for resizing the cluster, snapshotting or erasure coding to bound log and storage growth, and authentication/encryption between clients and servers.

Reference