README
¶
Flexible Filesystem
An work-in-progress experimental storage-agnostic filesystem representation.
This project began as a way of sharing state for a transportable agent system I started building as a hobby project between undergrad and grad school. I lost interest in that, but found the idea behind the storage was still worth having. The original was built in a combination of Python and C and used a custom binary format; this re-implementation in Go uses Protocol Buffers and eliminates the need for FFI.
Summary
A file in FFS is represented as a Merkle tree encoded in a content-addressable blob store. Unlike files in POSIX style filesystems, all files in FFS have the same structure, consisting of binary content, children, and metadata. In other words, every "file" is also potentially a "directory", and vice versa.
Files are encoded in storage using wire-format protocol
buffer messages as defined in
wiretype.proto. The key messages are:
-
A
Nodeis the top-level encoding of a file. The storage key for a file is the content address (storage key) of its wire-encoded node message. An emptyNodemessage is a valid encoding of an empty file with no children and no metadata. -
An
Indexrecords the binary content of a file, if any. An index records the total size of the file along with the sizes, offsets, and storage keys of its data blocks. -
A
Childrecords the name and storage key of a child of a file. Children are ordered lexicographically by name.
Binary Content
Binary file content is stored in discrete blocks. The block size is not fixed, but varies over a (configurable) predefined range of sizes. Block boundaries are chosen by splitting the file data with a rolling hash, similar to the technique used in rsync or LBFS, and contents are stored as raw blobs.
The blocks belonging to a particular file are recorded in one or more extents, where each extent represents an ordered, contiguous sequence of blocks. Ranges of file content that consist of all zero-valued bytes are not stored, allowing sparse files to be represented compactly.
Children
The children of a file are themselves files. Within the node, each child is recorded as a pair comprising a non-empty string name and the storage key of another file. Each name must be unique among the children of a given file, but it is fine for multiple children to share the same storage key.
Metadata
Files have no required metadata, but for convenience the node representation
includes optional Stat and
XAttr messages that encode typical
filesystem metadata like POSIX permissions, file type, modification timestamp,
and ownership. These fields are persisted in the encoding of a node, and thus
affect its storage key, but are not otherwise interpreted.
Related Tools
The ffstools repository defines command-line tools for manipulating FFS data structures.
In addition, the ffuse repository
defines a FUSE filesystem that exposes the FFS data format.
# To install:
go install github.com/creachadair/ffuse/cmd/ffuse@latest
Directories
¶
| Path | Synopsis |
|---|---|
|
Package blob implements an interface and support code for persistent storage of untyped binary blobs.
|
Package blob implements an interface and support code for persistent storage of untyped binary blobs. |
|
memstore
Package memstore implements the blob.Store interface using a map.
|
Package memstore implements the blob.Store interface using a map. |
|
storetest
Package storetest provides correctness tests for implementations of the blob.Store interface.
|
Package storetest provides correctness tests for implementations of the blob.Store interface. |
|
Package block implements content-sensitive partitioning of a stream of byte data into blocks, using a rolling hash function.
|
Package block implements content-sensitive partitioning of a stream of byte data into blocks, using a rolling hash function. |
|
cmd
module
|
|
|
Package file implements a File API over a content-addressable blob.Store.
|
Package file implements a File API over a content-addressable blob.Store. |
|
root
Package root defines a storage representation for pointers to file trees and associated metadata.
|
Package root defines a storage representation for pointers to file trees and associated metadata. |
|
wiretype
Package wiretype defines the encoding types for the ffs package.
|
Package wiretype defines the encoding types for the ffs package. |
|
Package fpath implements path traversal relative to a *file.File.
|
Package fpath implements path traversal relative to a *file.File. |
|
Package index constructs a Bloom filter index for a set of string keys.
|
Package index constructs a Bloom filter index for a set of string keys. |
|
indexpb
Package indexpb defines the storage encoding of a Bloom filter index.
|
Package indexpb defines the storage encoding of a Bloom filter index. |
|
storage
module
|
|
|
affixed
Package affixed implements a blob.Store interface that delegates to another Store, with keys namespaced by a fixed prefix and/or suffix concatenated with each key.
|
Package affixed implements a blob.Store interface that delegates to another Store, with keys namespaced by a fixed prefix and/or suffix concatenated with each key. |
|
cachestore
Package cachestore implements the blob.Store that delegates to an underlying store through an in-memory cache.
|
Package cachestore implements the blob.Store that delegates to an underlying store through an in-memory cache. |
|
codecs/encrypted
Package encrypted implements an encryption codec which encodes data by encrypting and authenticating with a cipher.AEAD instance.
|
Package encrypted implements an encryption codec which encodes data by encrypting and authenticating with a cipher.AEAD instance. |
|
codecs/zlib
Package zlib implements the encoded.Codec interface to apply zlib compression to blobs.
|
Package zlib implements the encoded.Codec interface to apply zlib compression to blobs. |
|
encoded
Package encoded implements a blob.Store that applies a reversible encoding such as compression to the data.
|
Package encoded implements a blob.Store that applies a reversible encoding such as compression to the data. |
|
filestore
Package filestore implements the blob.Store interface using files.
|
Package filestore implements the blob.Store interface using files. |
|
hexkey
Package hexkey implements utilities for hexadecimal encoding of blob store keys.
|
Package hexkey implements utilities for hexadecimal encoding of blob store keys. |
|
wbstore
Package wbstore implements a wrapper for a blob.CAS that caches writes of content-addressed data in a buffer and pushes them into a base store in the background.
|
Package wbstore implements a wrapper for a blob.CAS that caches writes of content-addressed data in a buffer and pushes them into a base store in the background. |
|
zipstore
Package zipstore implements a read-only view of the blob.Store interface using files stored in a ZIP archive.
|
Package zipstore implements a read-only view of the blob.Store interface using files stored in a ZIP archive. |