Introducing JotFS: a content-defined deduplicating file store

June 09, 2020

Today I’m happy to announce the beta release of JotFS, a deduplicating file storage engine backed by any S3 compatible object store. JotFS works by splitting files into small content-defined chunks and only storing chunks it hasn’t seen yet, saving storage space and bandwidth.

Some of its key features include:

Reduced storage and upload bandwidth requirements
Optional file versioning
Backed by any S3-compatible object store
Golang client library (more languages planned)
CLI client with familiar commands: jot cp, jot ls etc.
Easy to deploy — just a single binary (or use the Docker image)

Quickstart

JotFS operates under a client-server architecture. The server, jotfs, is responsible for validating data uploaded by clients, storing file metadata and coordinating client downloads. It communicates with clients over a HTTP(S) connection.

In its simplest configuration, just pass the name of the S3 bucket to start the server:

jotfs -store_bucket="jotfs-test"

The server is now listening on port 6777 and ready to accept client requests.

Interacting with the server

The easiest way to start using JotFS is with its command line interface jot. Like jotfs, its just a single binary which you can download and begin using right away.

We can use jot cp to upload a file from our local machine:

# Generate a file containing 6MB of random data
head -c 6M </dev/urandom > random.data
jot cp random.data jot://

And jot ls to list files:

jot ls /
# CREATED                         SIZE  ID        NAME
# 2020-06-10T19:27:14+01:00    6.0 MiB  58a5b419  /random.data

And jot cp again to download files:

jot cp jot://random.data ./random_download.data

Deduplication

The raison d’être for JotFS is to reduce storage space when saving files which are similar to each other but not exactly the same, for example, multiple versions of a dataset, VM images or database backups. It achieves this by deduplicating data through content-defined chunking. More, on that in the next section. First let’s see it in action.

Let’s take the random.data file from the last section and modify it, replacing 1MB of data in the middle of the file:

head -c 3M random.data > random_new.data
head -c 1M </dev/urandom >> random_new.data
tail -c 2M random.data >> random_new.data

Each file is 6MiB for a 12MiB total, but JotFS only requires an extra 1.7MiB to store the second file!

jot cp random_new.data jot://random_new.data
jot admin stats
# Output:
# Number of files         = 2
# Number of file versions = 2
# Total files size        = 12.0 MiB
# Total data size         = 7.7 MiB

A significant factor controlling the deduplication rate is the chunk size. By default, JotFS tries to split data into chunks averaging about 512KiB, but this is configurable with the -chunk_size flag. Smaller chunks will tend to increase the deduplication rate at the cost of more metadata stored.

Content defined chunking

JotFS deduplicates data through a process called content-defined chunking. Specifically, it uses its own implementation of the FastCDC algorithm. It works by rolling a fast hash function over an input stream, byte by byte, and setting a chunk cut-point when the hash value reaches a predefined condition.

To see how this works, I ran the chunking algorithm over the two files above (with 1MiB average chunk size for brevity).

fastcdc -file random.data -avg 1024
# Output:
#  OFFSET    FINGERPRINT
#       0    0x1e3c2c9c3b300000
# 1326324    0xc4d5935e7a900000
# 2395436    0x48c695ce38100000
# 3448088    0x5ec77783f1580000
# 4626185    0xa35efdf122b80000
# 5933891    0x44e9930c242efd20


fastcdc -file random_new.data -avg 1024
# Output
#  OFFSET    FINGERPRINT
#       0    0x1e3c2c9c3b300000
# 1326324    0xc4d5935e7a900000
# 2395436    0xc3cae3c890840000
# 3523540    0x5ec77783f1580000
# 4626185    0xa35efdf122b80000
# 5933891    0x44e9930c242efd20

Comparing the chunk offsets for each file, there is only a single chunk difference between them. When JotFS encounters the second file, only a single chunk needs to uploaded and saved to the object store.

JotFS works best on data which is not compressed beforehand because it hinders the ability of the chunking algorithm to deduplicate data across files. Instead, JotFS automatically compresses data with Zstandard after chunking has been performed.

Internals

JotFS has been intentionally designed to cater to the advantages, and to mitigate the disadvantages, of S3-compatible object stores.

Chunking is performed client-side, with the advantage of reducing server CPU load and improving upload speeds. As it’s reading a file, the client gathers chunks into mini-batches and queries the server to see which chunks it needs to upload. The server stores metadata in a local SQLite database and can respond quickly without needing to query S3. As new chunks arrive from the client, the server places them into a “packfile”. This file is sent to S3 once its size reaches a certain limit. Storing chunks into packfiles is an important optimization. If each chunk was stored individually, the request based pricing of AWS could become prohibitive. By storing chunks coming from the same file together we reduce the number of requests required when that file is to be downloaded.

All uploaded data must pass through the server so that it can be verified before it reaches S3. But, for downloads, JotFS leverages the bandwidth of S3 directly without any data passing through the server. When a client makes a request to download a file, the server looks up its local metadata database for the chunks contained in the file and their corresponding location within the collection of packfiles. It responds with one or more pre-signed URLs over a specific content-range in the required packfiles. The client then downloads the data from these URLs and assembles the file.

Files may be deleted using the client library or with jot rm. When the server receives a request to delete a file, it immediately deletes the file’s metadata, but the underlying data will persist until a later stage. Similar to PostgreSQL, JotFS also has a vacuum procedure to remove stale data. When a file is deleted, the reference count for each chunk in that file is reduced by one. The vacuum picks up any chunks with a refcount that has reached zero and removes the chunk from its packfile. The vacuum runs on a configurable schedule, or can also be run manually with jot admin start-vacuum.

Next steps

Thank you for reading this introduction to JotFS. Take a look at the main JotFS repo for instructions on how to get started. It’s early days, and JotFS is currently beta-level software. Contributions are welcome, and I’m happy to help out either through Github issues, or on the JotFS gitter channel. Have a nice day!