NOTE: This was originally written as the sole description of Obnam's on-disk repository storage. At the time, there was no other repository format, and so this text doesn't separate that which is generic from that which is specific. This page needs to be updated to discuss the specific parts only. For the generic parts, see ondisk.

Obnam is a backup tool for making backups to hard disks, either local ones or over the network. It does not work with tape drives, or optical disks. The backup server is stupid: it does not run any Obnam specific code, only ssh (sftp).

The location where backups are stored is called the backup store, and may be shared between multiple co-operating clients. The backup store resides on a backup server. The computers that own the data being backed up are the clients.

Performance is obviously a consideration. It has many aspects:

• run-time
• RAM
• disk space, both server and client
• disk bandwidth, both server and client
• network bandwidth, between server and client

To achieve its performance goals, Obnam uses the B-tree variant devised by Ohad Rodeh[1], also used by btrfs. This document is describes how it does that.

Characteristics of the B-tree

The Rodeh B-trees are designed for shadowing, i.e., copy-on-write updates of tree nodes. Nodes are not modified, instead a new copy is created to replace it. This allows an efficient way to copy a tree and to update the copy, while keeping the original tree intact. The two trees will share as many nodes as possible. Obnam calls the collection of related trees a forest.

The trees use fixed-length binary strings as keys. For each key, a variable-length binary string is stored as the value. The tree consists of interior nodes and leaf nodes; all values are stored in leaves only. There is a maximum size for nodes, which in some applications would be a raw disk block, but is a separate file for Obnam. Value strings can be as big as a node (minus a small header), but no bigger.

Lookups and removals from the tree can be done using ranges: all keys within a range are looked up, or removed from the tree. This is an important optimization and opens up some interesting design possibilities.

File data (chunk) storage

File data is not stored directly in B-trees, but externally. Data is broken up into chunks of suitable size (say, 64 KiB) and assigned identifiers, which also act as filenames. Given a chunk id, its contents can be easily retrieved.

Chunks are shared within and across clients. This allows clients to avoid uploading data that another client has already uploaded, or storing the same data twice. The same mechanism allows Obnam to efficiently back up files that have moved, or that have been modified, or both at the same time. If a chunk of data already exists in the store, Obnam tries hard to avoid having to back it up again.

To back up a chunk, Obnam chooses a random, unused 64-bit identifier, and uploads a file of that name. The next chunk uses the next identifier, until it hits one that has been used, at which point it picks a new random one.

Chunks are managed using reference counts. We will cover these later, after discussing other details of the store. See section "Chunks, part 2" below.

Overview of store forests

The backup store consists of several forests:

• client list: map client names to 64-bit identifiers
• chunk list: map chunk identifiers to checksums
• chunk checksums: map chunk checksum to identifiers
• per-client data: backup generations for each client

Locking

Locking is done only for writes. Reads are always allowed, even while write locks exist. This allows race conditions between readers and writers, but thanks to copy-on-write updates those are no different from files getting corrupted or deleted on the server by hardware failures, and can be treated the same.

Each forest is locked separately. If more than one forest needs to be locked at the same time, they are locked in an order sorted by the name of the forest, using the C locale. If a client fails to lock a particular forest, it releases all the locks it holds, and tries again. This avoids deadlocks, but allows starving. The most likely reason for starving is too many clients sharing the same store, and that needs to be solved by increasing backup server performance, or having more stores.

Locks are implemented as files, which are created atomically. Each lock file contains the name of the host that holds it (which might not be a backup client), and the process id on that client, and the time of creating the lock. If the time is very old, another client may decide to break the lock. If the backup store is encryped, then also the contents of the lock file is encrypted.

To reduce lock congestion, each client attempts to keep a lock for as short a time as possible. For per-client data, this means keeping the lock for the duration of the backup. For shared forests, updates can be spooled: the shared forest is used read-only until the end of the backup run, or until a checkpoint, and updated then, as quickly as possible.

Client list forest

The client list forest consists of a single tree. Its key is consists of a tuple:

• 128 bits of MD5 checksum of the name of the client
• 64 bits of client id (for hash collision avoidance)

The client name is typically its host name, but might be anything. It is up to the sysadmins of the clients to co-operate so that each client has a unique name.

It is unlikely that there will be checksum collisions for client names, but it's easy to not have to worry about that. The client id will be chosen randomly.

Chunk list forest

The chunk list forest consists of a single tree. Its key consists of a 64-bit integer containing a chunk identifier. The value is the MD5 checksum for the chunk.

This tree is needed so that it is possible to quickly find the checksum of a chunk, given its identifier, when removing generations from the per-client forest.

Chunk checksum forest

The chunk checksum forest uses a tuple as a key:

• 128-bit MD5 checksum of the data in the chunk
• 64-bit chunk id
• 64-bit client id

The chunk id is used to handle checksum collisions. While MD5 collisions are not likely in general use, they are certain for people who research cryptographic hashes, so Obnam needs to be able to handle them. When Obnam has a chunk it wants to back up, it does a range lookup from (md5,0) through (md5,chunkd_id_max), and then checks if the chunk is identical to any of the chunks already in the store. This checking is expensive, but safety may more important than performance here. (Obnam may provide an option to disable the data comparison check, and rely only on the hashes.)

The value is empty.

Per-client forest

The per-client forest has one tree per backup generation or checkpoint, and represents a snapshot of the filesystem at a specific time, or as close to a snapshot as Obnam can make it. Obnam does not freeze the filesystem while the backup runs, so it cannot guarantee a true snapshot.

The forest uses a tuple as a key:

• 8-bit prefix
• 64-bit main key
• 8-bit subkey type
• 64-bit subkey

The prefix is one of the following:

• 0 for filesystem metadata
• 1 for chunk references
• 2 for generation metadata

For prefix 0, the main key is the file identifier. See below for how they are generated.

The subkey type and subkey and value are using as follows:

subkey type	subkey	value
0	file-id	full pathname to file
1	counter 0...	up to N chunk-ids
2	0	number of chunk-ids stored
3	0...	inode fields, user/group name, xattr, ...

Subkey type 0 is used to handle hash collisions for the pathnames. They are unlikely, but it is entirely unacceptable for Obnam to fail if they happen. Each file has an identifier that is unique within the generation: there is a one-to-one mapping between fully qualified pathnames and file-ids within a generation (but not across generations).

By default, the file-id is one half of the 128-bit MD5 of the full pathname to the file. To check for collisions, we see if the value for key (1, default-file-id, 0, file-id) is the full pathname for the file we are interested in. If it is not, we generate a new file-id by some deterministic approach, and do the lookup again, and repeat this until we find a free file-id. Note that the default-file-id in the lookup stays the same, it will always be the half of the MD5 of the pathname.

Subkey type 1 is used to store a list of chunks that represent the contents of the file. Since a file can be quite large, we store more than one chunk-id per value, to reduce the overhead a bit. Benchmarking will determine the suitable number of chunk-ids to put in each value, but probably the size of the value should not be larger than about a quarter of a node. To avoid having to do a range lookup to find the next counter, when appending new chunk ids to an existing list, we store the number of items at subkey type 2 (subkey 0).

Subkey type 2 is used for file metadata, such as inode data (st_mtime, st_size, etc), the name of the owner and group for the file, xattr fields, etc. To reduce space use, the most common metadata is stored in subkey value 0, encoded in a special format. Other subkey values are used for additional metadata, which also allows for future expansion.

For prefix 1, the rest of the key is used like this:

• main key is the chunk-id
• subkey type is 0
• subkey is file-id for file that uses the chunk

For prefix 1, the value is always empty. Whenever Obnam backs up a file, it adds the key (1, chunk-id, 0, file-id). If the file existed in the previous generation, but not in the new generation, it removes the key.

For prefix 2, the main key is fixed as the hash of the string "generation", and the subkey type is fixed at 0. The subkey is one of the values in the following table.

subkey	value
0	generation id
1	timestamp for the start of the generation
2	timestamp for the end of the generation
3	boolean (0 or 1) for whether the generation is a checkpoint

Timestamps are expressed in UTC as seconds since the beginning of 1970 (i.e, Unix epoch).

Chunks, part 2

When backing up, Obnam will do roughly this:

• clone the tree for previous generation
• traverse the filesystem tree, adding and removing files from the new tree
• when backing up a file's chunks, look up each chunk in the store, and add it if it is missing; after this, the id of the chunk is known
• add (1, chunk-id, 0, file-id) to the per-client forest, (chunk-id) to the chunk list forest, and (checksum, chunk-id, client-id) to the chunk checksum forest for any new chunks it uses; the updates to the chunk list and checksum forests can be batched to the end of the backup run
• remove (1, chunk-id, 0, file-id) from the per-client forest, for every chunk for any file it removes from the new generation (no need to remove anything from the chunk checksum forest, since previous generations will still use the chunks)

When removing a generation, Obnam will do roughly this:

• look up every chunk-id used in that generation
• look up each chunk-id in every other generation
• if not found in any other generation, remove (checksum, chunk-id, client-id) from the chunk checksum forest; look up the checksum from the chunk list forest
• if there are no keys in the range (checksum, chunk-id, 0) through (checksum, chunk-id, client_id_max) in the chunk checksum forest, then remove (chunk-id) from chunk list forest, and chunk file from disk
• remove the tree for the unwanted generation

Repository metadata

There is a need to store some metadata about the repository. This will be done in the metadata directory. Initially, the only piece of information is the version of the on-disk format, expressed as a single integer, stored in the file metadata/format.

Each version of Obnam will know which on-disk formats it supports. With the metadata/format file it knows if it can handle a particular format.

Upgrades to newer formats will happen explicitly, not implicitly.

Encryption

Obnam may optionally encrypt data in the backup store. The design for this is unclear, but will need to solve at least the following problems:

• each client should have access only to its own data, but still allow sharing of data across clients
• the server admin should be able to disable access for each client, or anyone who's compromised the client's encryption key
• the server admin should be able to do some operations on any client, such as expire generations, remove entire clients and their corresponding chunks, verify correctness of the whole data store ("fsck"), or restore data after the client has been entirely lost

On checksum algorithms

This design uses MD5 checksums for everything. It does not require the checksum algorithm to be cryptographically secure, and is content with having a hash that is unlikely to result in collisions, and only cares about the probability of collisions for performance, not correctness. The design handles collisions, and does not assume two pieces of data are identical just because the hashes are the same. A shorter or faster checksum algorithm may be used instead. Or a cryptographically stronger one. MD5 is not recommended for applications that rely on the security of the hash, but this design does not rely on that.

However, it may be quite expensive to verify that data chunks with the same checksum are the same. It may require reading back the chunk from the server. This may not be acceptable to all users. Some users may be willing to live with the chance of a checksum collision. Other users might not want to pay the price for de-duplication. Thus, it may be best for obnam to provide a tri-state option: full verification, rely on checksums, and no de-duplication. Further, it may be a good idea to allow the user to specify the checksum algorithm.

Comments?

Edit this page directly, or mail me at liw@liw.fi. Thanks.

Author

Obnam is being developed by Lars Wirzenius. Feedback and patches are most welcome.

References

1. Rodeh, Ohad: "B-trees, Shadowing, and Clones". IBM Haifa Research Labs. http://portal.acm.org/citation.cfm?id=1326544 http://www.cs.tau.ac.il/~ohadrode/papers/btree_TOS.pdf

Changes

• 2010-05-04: Modified the way hash collisions for filenames are handled, based on suggestion from Richard Braakman: store secondary hash and filename with primary hash.
• 2010-07-11: Minor tweaks.
• 2010-11-11: Change tense to current, add some notes and minor fixes.
• 2010-11-11: Add design for removal of chunks, some considerations for encryption, more details on how keys are used by various forests in the store, locking, and other clarifications.
• 2010-11-11: Refer to hosts as clients, for clarity.
• 2010-11-12: Typo fixes and checksum verification tri-state option suggestion from Richard Braakman.
• 2010-11-18: Add generation metadata to per-client forest.
• 2010-11-29: Add chunk list forest.