: Directory Descriptor Grammar

This pseudo-BNF grammar defines Octavia’s directory descriptor format. A directory descriptor specifies the keys used to sign and encrypt the files, followed by a list of file descriptors.

File descriptors specify minimal metadata, followed by the IDs of the blocks that make up the file.

A Note on Notation

Grammar

Digits. Numerical values such as sizes and timestamps are expressed as of strings decimal or hexadecimal digits.

hex-digit := 0-9 | a-f | A-F
decimal-digit := 0-9

Protocol version. The protocol reserves one byte in protocol messages for the protocol version in use; each directory descriptor is tied to a protocol version. Clients may create directories with one protocol version, be upgraded to support a new version, and still support the old directories correctly by knowing the right protocol version for the directory.

protocol-version := protocol-version hex-digit{2}

Names consist of 1 – 64 printable Unicode code points, no more than 64 bytes. If the name contains spaces, surround it with quotes.

name := ” printable-utf8{1,64} ”
name := ’ printable-utf8{1,64} ’
name := printable-utf8{1,64}

Size in bytes, unsigned.

size := hex-digit{1,16}

Timestamp. Times are expressed in seconds since the Unix epoch. The hexadecimal digits represent an unsigned integer.

time := hex-digit{8}

Block ID. Block IDs uniquely identify blocks of data by their size and cryptographic hash value. File contents are constructed from an ordered list of block IDs. In protocol version 0, the hash is 256 bits.

block-id := size hex-digit{64}

Encryption key. Every directory’s files are encrypted with a distinct 128-bit key. Protocol version 0 specifies the encryption algorithm AES-128-CBC.

Note that the encryption key is not the signing key; signing keys represent a particular client’s relationship with a particular server, and can differ even when two clients share a directory. Signing keys are stored in a client’s keystore file, not in directory descriptors.

As a special case, a directory with no key does not use encryption, and the files are stored and transmitted over the internet in plaintext. We don’t recommend this even for public data.

encryption-key := encryption-key hex-digit{32}

File modification time. A timestamp, as defined above.

modified-time := time

Directory descriptor version. Every time a directory changes — including when any of the files it contains changes — the client creates and stores a new version of the directory. The client may choose to retain the old versions. The descriptor version allows clients to recall different versions of a directory (and hence different versions of its files).

The client chooses an arbitrary name. The client’s hostname is a fine possibility.

descriptor-version := version name modified-time

File type can be either “f” (file) or “d” (directory). A directory is, just like a file, a stream of bytes. However, clients interpret the bytes of directories as nested directory descriptors. Thus an Octavia directory can be hierarchical.

type := f
type := d

File descriptor. A file descriptor tells a client how to construct a stream of bytes from a set of blocks by ordering the set. File descriptors also include some metadata. Version 0 does not include the full set of POSIX metadata. Honestly, do you care?

file-descriptor := type name size modified-time block{1,}

Servers. A list of servers believed to have stored blocks for files in this directory. A client may or may not have a signing key relationship with the server; without one, the client cannot write blocks to the servers, but can still retrieve the file blocks from servers willing to respond.

host := ip-address
        host-name
port := decimal-digit{1,5}
server := host : port
servers := server{1,}

Directory descriptor. The most volatile components of a directory descriptor are bunched together toward the end of the text, in an attempt to minimize the block-level delta for new versions of the descriptor. Since servers store only a single instance of blocks, clients may avoid re-storing blocks the server already has, thus optimizing directory writes somewhat. In particular, although the list of file descriptors is not strictly ordered, clients should sort them in ascending order by modified time.

directory-descriptor := protocol-version encryption-key
        servers file-descriptor{1,} descriptor-version

Example Directory Descriptor

This example shows what a simple descriptor might look like.

protocol-version 0
encryption-key deadbeefdeadbeefdeadbeefdeadbeef
endpoints 127.0.0.1:55555 octavia.wieldysoftware.com:55555 noodle.doodle:1234 10.1.2.3:9999
f readme.txt 1502 4ac7ff2d
    400 deadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeef
    400 deadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeef
    400 deadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeef
    400 deadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeef
    400 deadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeef
    102 deadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeef
d stuff 457 4ac7ff2d
    457 deadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeef
version erdbei.local-1176 4ac7ff3d