CloudFS - A Cloud-backed File System

Logical and Physical View of CloudFS

This is a course project for CMU 15-746: Storage Systems. The project is implemented in C++ and is tested on Ubuntu 18.04 using Amazon EC2.

As per the school's integrity policy, I am not allowed to share any related code publicly. This post documents my design choices and what I learned from the project; the Learnings section at the end covers the things I would do differently if I were to start over.

Huge thanks to Prof. Greg and Prof. George for their wonderful lectures.

At a glance

• Course: CMU 15-746 Storage Systems, Fall 2022
• Stack: C++, FUSE, Amazon S3, Ubuntu 18.04 on EC2
• Scope: core FUSE file system, content-based deduplication, snapshots, local cache manager
• My role: solo project
• Code: not public (course integrity policy)

Introduction

CloudFS is a cloud-backed local file system. Specifically, a CloudFS instance stores all file metadata and files under a predefined file size threshold on a local SSD, and stores the rest of the file data using a cloud storage service from Amazon S3. CloudFS is developed based on the FUSE (Filesystem in USErspace) software interface.

CloudFS consists of four components: a core file system leveraging the properties of local SSD and cloud storage for making data placement decisions; a component that takes advantage of redundancy in data to reduce storage capacity; a component that adds the ability to create, delete, and restore file system snapshots while minimizing cloud storage costs; and a component that uses local on-device and in-memory caching to improve performance and reduce cloud operation costs.

Background

File System and Implementation

In computing, a file system or filesystem (often abbreviated to fs) is a method and data structure that the operating system uses to control how data is stored and retrieved. Without a file system, data placed in a storage medium would be one large body of data with no way to tell where one piece of data stopped and the next began, or where any piece of data was located when it was time to retrieve it. By separating the data into pieces and giving each piece a name, the data are easily isolated and identified. Taking its name from the way a paper-based data management system is named, each group of data is called a "file". The structure and logic rules used to manage the groups of data and their names is called a "file system."

From the perspective of computer architecture, a file system is an abstraction layer between the program layer and the device driver layer. Programs use it to read and write files; the device driver uses it to read and write blocks on the storage device. The file system translates file operations into block operations.

Because of the great flexibility we have in building a file system, many different ones have been built, literally from AFS (the Andrew File System) to ZFS (Sun's Zettabyte File System). All of these file systems have different data structures and do some things better or worse than their peers.

As Figure-1 has shown, to implement a file systems, there must be quite a few operations involving interactions with the OS's kernel. One obvious approach is to build an in-kernel file system, which is obviously complex and error-prone. Luckily, there is an easier way to do it: FUSE.

Filesystem in Userspace (FUSE) is a software interface for Unix-like operating systems that lets unprivileged users create their own file systems without touching kernel code. The file system code runs in user space; the FUSE kernel module is only a bridge to the real kernel interfaces.

To implement a new file system, you write a handler program linked against libfuse. The handler specifies how the file system responds to read, write and stat requests, and it is also what mounts the file system. At mount time the handler is registered with the kernel; from then on, any read, write or stat request on the mounted path is forwarded to the handler, and the handler's response is sent back to the caller.

FUSE is particularly useful for virtual file systems. Unlike traditional file systems, which manage data on mass storage, a virtual file system stores nothing itself: it is a view or translation of an existing file system or storage device.

Cloud Storage Services

Cloud storage keeps data in logical pools "on the cloud": the physical storage spans many servers, often in several locations, owned and run by a hosting company that is responsible for keeping the data available and the hardware protected. People and organizations lease capacity from these providers for user, organization or application data.

CloudFS uses Amazon S3, through its plain HTTP API, to store large file data.

Unlike a local SSD, cloud storage is billed monthly, and each service has its own pricing model. Amazon S3 charges for the capacity you use, the amount of data transferred, and every command you submit, such as each object retrieval.

Implementation

The four components introduced above each get a section below.

Core File System

The core file system is built on FUSE. Among other things, it:

1. Takes command-line arguments to configure the file system: the mount point, the local directory, the cloud directory, the file-size threshold, tuning parameters for the cache and deduplication, and so on.
2. Supports the usual operations on files and directories: create, delete, modify.
3. Decides where each file lives based on its size: files below the threshold stay on the local SSD, larger files go to the cloud.

Deduplication

Deduplication is a term used when a storage system tries to discover duplication among unrelated files and store duplicate content only once.

The simplest way to think about deduplication is to compute a checksum or hash of the entire file, or perhaps each file block, storing the file's or block's hash in a large lookup table. When a new file (or block) is written to the storage system (i.e., added or modified), compute its hash and look up this hash in the lookup table. If the lookup table does not contain the hash, then this data is new, because identical content ensures identical hashes.

If the hash and the data match, the lookup table also gives the location of the stored copy, so you drop the new copy and point the file (or block) metadata at the existing one. Cloud storage use drops accordingly.

Snapshots

A snapshot restores the file system to an earlier point in time. Consistent snapshots double as backups: they let you undo a deleted or corrupted file, or rebuild the file system on a new SSD after a device failure.

snapshot() archives the current local small files, proxy files and metadata into a tar file. It records the snapshot's contribution to each chunk's cloud reference count and adds it to the global reference count table.

restore(t) takes the timestamp of an existing snapshot, removes every file on disk (except a few internal ones), downloads the snapshot archive and extracts it. Restoring to a snapshot invalidates every snapshot taken after it. CloudFS finds the reference-count changes those later snapshots made by consulting the global table, and undoes them by decrementing the counts.

delete(t) deletes a snapshot from the cloud, updates the global reference count table, and removes any chunk whose count drops to zero.

install(t) mounts a snapshot at a predefined path so the user can browse its files. Under the hood, CloudFS reads the file-to-chunks mapping stored in the snapshot and adds it to a snapshot mapping table keyed by the snapshot's timestamp. Reads inside an installed snapshot consult that namespace and fetch the chunks they need, so several snapshots can be installed at once without interfering with each other.

uninstall(t) reverses install(t): it removes the snapshot's namespace from the mapping table.

The snapshot component saves cloud cost in two ways. Snapshot state travels as a single archive, which saves request cost and turns many small I/Os into one large one. And because CloudFS tracks a reference count per chunk, it can delete chunks that restore() or delete() leave unreferenced.

One further idea: keep a server-side "cache" and delay deleting chunks whose reference count hits zero. If a later local operation produces a chunk that is still in that cache, there is nothing to upload. A time-to-live per chunk and a cap on the cache size would keep the extra storage cost bounded.

Caching

CloudFS has a cache manager with configurable strategies. Keeping file chunks local cuts both cloud storage and request costs. Figures 6 and 7 show the read and write paths with caching enabled.

The cache saves cloud cost mostly by keeping freshly segmented chunks local. When a large file is split, its chunks go to the local cache first, so as long as the working set fits, later reads and writes hit the cache and rarely touch the cloud. CloudFS scored 32 on the Autolab cache stress test: hit rates are decent, but cloud transfer cost is still high and there is room to improve.

Learnings

A few years on, these are the things I would carry into the next storage project.

• Build observability before features. Debugging a file system that spans a local disk and S3, with no trace of the cloud calls or the local writes, was the biggest time sink of the project. Next time, request-level tracing (which chunk, which S3 operation, how many bytes, how long) is the first thing I write.
• Cloud cost is a request-count problem more than a byte-count problem. The savings in the snapshot and cache components came from batching (one archive per snapshot, chunks kept local while the working set fits), not from moving fewer bytes. S3 bills per operation, and designing around the number of requests changed how I thought about every component.
• Deduplication chunk size is worth measuring rather than reasoning about. Smaller chunks find more duplicates but inflate the chunk table and the number of cloud objects, and therefore the number of requests. It deserves a benchmark against representative files early on.
• Decide how snapshots and the cache interact before writing either one. Copy-on-write snapshots and a write-back cache both want to own the current state of a chunk. Writing down the flush order and the reference-count rules first would have avoided the bugs I found last.
• Test against a fake cloud. Most correctness bugs have nothing to do with S3. A local stand-in for the cloud layer, with the real S3 reserved for cost and performance runs, would have made the edit-test loop much shorter.

Refs

• Wikipedia: File system
• MLA Style. Arpaci-Dusseau, Remzi H., Arpaci-Dusseau, Andrea C.. Operating systems: three easy pieces. : Arpaci-Dusseau Books, 2014. E-Book.