ltr/litter

Author:	Thomas Langewouters
tags:	software
description:	A distributed offline file-keeping system

Caution!

This is mostly a draft, when linking keep in mind that this document changes a LOT, there is presently no Changelog or version info available. Not much of the things described here are implemented at this time. But things are looking good, the design is almost complete.

Introduction

From the moment you have multiple (portable) PC's, you find your files scattered all over PC's, disks and maybe even locations.

I'm growing tired of having to power on machines to check if some of my stuff is on them. And, I can't just pull one of my laptops out of the closet, sync it up quickly and later pick up my work on it, as I left it on my desktop.

All my files should be present in the filesystem tree, at any time. Even when I choose file contents are not needed (on my EeePC laptop for instance, where disk space is scarce).
In the case of the EeePC, access to file contents should be denied if on the road, but if a host that caries the files is reachable access should be transparent.
New files and file changes should be distributed to other computers on a snap of the fingers.

I looked into distributed filesystems such as the andrew- and coda filesystem, but found these to be unsuitable. Novell iFolder comes closer, but iFolder isn't easy to setup.

Over time I shaped my own vision on how some of these things could be implemented, and I named it litter.

Features:

A standard ltr volume is mounted and accessed like any other filesystem in true UNIX style (technologies used: FUSE, inotify).
Ltr uses any Linux directory/filesystem to store its data, and standard networked filesystems to synchronize volumes between hosts.
Commits are fast and do not require the entire volume to be crawled to check for changes. Hashes are calculated for new and changed files.
Partial volumes: choose which files of the volume you want to keep on disk on each computer. (Cherry-pick or only the most recent).
You can select and distribute the changes you like, online.
Filenames are matched against an 'excluded' list, matches are excluded from the volume and not distributed to other hosts.

Advantages:

You can always navigate your volumes, even when their contents are not present on the local computer. This feature comes in handy for large archive- and multimedia volumes.
The file store of an other (networked) host can be used transparently to access files that were chosen not to be kept on localhost.
Keep an eye on your stuff. You can review what files were changed/removed, and feed that information into scripts.
Replace backups by mirroring your files amongst multiple computers.
Volume scrubs can detect silent file corruption.
Provides location uniformity amongst hosts if you consistently mount your volumes on all your computers at the same paths.
Carry changes/updates to remote computers using a portable disk.
Easy to combine with a central versioning system (cvs,svn,git,...) to provide time-machine-like functionality.

Tidy-ness is a bliss

Organising your files over multiple ltr volumes will bring advantages. Here are some examples of volumes I will be using:

thome: thomas's homefolder: dot- and rc-files.
pets: my personal 'pet' projects.
mail: maildir's with my email messages
vhosts: disk images of virtualized computers
pictures: personal- and family photos
images: such as wallpapers, clip-art, icons
video: family movies, TV recordings, ...
audio: converted audio discs, podcasts, radio recordings, ...
books: manuals, books under the creative commons, ...

Litter does not seek to replace version control tools, it solves a distinctly different problem. Integration with a version control system might be welcome depending on the kind of data is stored in a volume. Ltr is designed with this in mind.

(in)direct access volumes

I keep a copy of my audio on my iPod running Rockbox. Since this removable storage device is to be accessed directly by the Rockbox OS, a more cruder approach is used.

(FIXME: this piece is missing here)

Flash-based players with less storage would profit from ltr's partial volumes capability.

Terminology

Volume:	(litter volume) a folder containing files. Volumes are distributed (mirrored) over a pool.
Peers:	Two or more computers that keep the same volume.
Pool:	A group of volume peers.
Slicekeeper:	A host that has a subset of a volume's files(a slice) on disk.
ghost:	A file not kept on local disk.
Store:	Contains a snapshot of the volume's files (not necessary all files, but at any time all digests)
Digest:	A file tree mirroring the store, but its files contain hash+filesize.
Track:	A list of changes made to the store by a commit.

Implementation

There were two approaches I considered. The first one uses a combination of unionfs(aufs) and a simple FUSE filesystem. The second one uses a complex FUSE process to expose the volume to the user. There are some serious limitations to the first design, so it was opted to use a full FUSE mount.

Advantages/disadvantages of first versus second design:

+ single FUSE mount point in /proc/mounts
+ FUSE mount helper; use ltr#mail <mountpoint> fuse in /etc/fstab
+ cross-platform if you consider the Mac, BSD and OpenSolaris FUSE ports.
+ local overlay can be implemented properly
+ no copy-ups on file moves
- more complicated implementation.
- more CPU overhead compared to the in-kernel aufs.

Implementation: single FUSE

Components:

mount.ltr: FUSE based filesystem
litter: python classes
ltr: command line tool (python)
Look at existing FUSE union filesystems.
IPC communication might be best using UNIX sockets.
The ltrfs configuration is kept in /usr/ltr/fsname/mounts/, for each mount, a configuration file is held by the name of the mount path, with / replaced with :.
mountpoint/.ltr -> /usr/ltr/volume

Note

If a filename is postfixed with with /, the next indented block refers to folder contents. If a filename is postfixed with :: the next indented block refers to ASCII file contents.

/usr/ltr/volumename
`-- mounts/
|   `-- :home:thomas:myvolume ::
|   |       |inbox0 rw
|   |       |*inbox1 ro
|   |       |store O
|   |       |peer0 sshfs#whirlpool:/usr/ltr/myvolume
|   `-- :export:samba:myvolume ::
|           |inbox2 rw
|           |inbox1 ro
|           |store A1
`-- store/
|   `-- data/
|   `-- meta/
|   `-- local/
|   `-- tracks/
|   `-- HEAD::
|   `-- hooks/
`-- inbox0/
|   `-- data/
|   `-- meta/
 `-- peer0/
    `-- store/
    `-- inbox0/

The store

^
|
`-- store/
|   `-- data/
|   |       (volume contents)
|   `-- meta/
|   |       (digest tree)
|   `-- local/
|   |       (excluded files)
|   `-- trash/
|   |       (rm's get moved here if keeptrash enabled)
|   `-- excluded::
|   |   |.zshrc
|   |   |.bash*
|   |   |.gnome2/
|   |   |.gconfd/
|   |   |.local/share/Trash/
|   |   |.cache/
|   |
|   `-- SUMS::
|   |       |(sorted list of checksums)
|   `-- tracks/
|   `-- HEAD::
|   |       O/A1/A1B2
|   `-- hooks/
|   |   `--- pre-commit
|   |   `--- post-commit
|   |   |       date1rand.sh
|   |   `-- anotherhostname::
|   |           date0rand.sh
|   |           date2rand.sh
|   `-- behaviour::
|   |       |slicekeeper false
|   |       |keeptrash true
|   |       |keeneye true
|   |       |badfs true
|   |       |directa true
|   `-- LOCK::
|           (lockfile to prevent concurent access)
\/

Data is kept in the data/ and local/ directories. The volume's directory tree is replicated there to the extend necessary to keep the files at the same relative path as in the volume.

The excluded file contains a plain-text list of which paths should at all times be redirected to the ``local/`` overlay.

hooks/ is a place to put scripts, e.g. you can put a script there that runs at post-commit and checks the new snapshot into a VCS.

The validity of the lockfile can for instance be ensured by updating its mtime at regular intervals. No change during for n-intervals indicates a stale file.

Tracks

tracks/
`-- O/
    `-- diff::
    `-- trail::
    `-- A1/
        `-- diff::
        `-- trail::
        `-- A1B1
            `-- diff::
            `-- trail::

The diff file contains a file list (one per line) with file checksum and plus/minus indicator.

The trail is a list of volume instances based on this tree, if all instances are moved past a certain point, old trails (the lowest, most down to the root) can be removed, and the new lowest common tree can be used as the main track.

(O is origin, and its diff may be empty)

Inbox

data/

The data folder is used to hold new and modified file content. The volume's directory tree is replicated to the extend necessary to host files on the same path as those in the store relative to the volume root.

The modified data's metadata is also applied.

meta/

The contents of files in meta/ are never presented to the user. meta/ only contains four relevant kinds of information:

directories: an empty directory might indicate changed stat data.
if a file is deleted; a whiteout file (wh.) is created.
if a file is moved; a whiteout file is created, a symlink on destination is created, pointing to source.
stat indicators, when a file's permissions and/or mtime are modified, but the contents are identical to those in the store.

Peer(n)

`-- peer0/
      `-- store/
      `-- inbox0/

Probably a network mount or a bindmount of a volume on a removable storage device.

Notes

how do we do timeouts? I don't want my volume locking up when a lookup from a peer volume locks up.
mount with allow_other is a must!
File operations during merging? Make this robust.
Copy-up on open(,"rw") should be done in a thread?
does mv open the file for reading/writing, or does it just do a rename

ltr: Tool

Cherry-picking

On a slicekeeper host, you can pick which files to keep local in several ways (CLI,GUI).

Possible actions on each file:

Fetch/mark (we want it local now)
Abandon (we don't want it local anymore)

Implementation:

CLI: running ltr pick in the corresponding folder
GUI: nautilus shell extension: popup menu.
WEB: show a file tree accompanied with checkboxes (simple python+http)

Possible problems this can cause:

All hosts abandon a file:

At least one host has to be forced to keep ALL FILES (favoured)
hosts have keep trash?
or: require network check before abandoning a file

We run out disk space on one of the hosts:

Impose an artificial disk quota for a volume.
or: force the user to abandon other files.

cli tool: ltr pick: +/-filename, - means read list from stdin.

Network mount

If available, a networked remote host can be used to access files not cached locally. This feature will be mostly used in the case of archive volumes or slice-keeping of a volume with big files (like media) on it.

A store is mounted and locked before using files from it. Note that the file hash has to match the wanted file.

|
`-- mount0.info::
|       |(hostname) NFS/SSHFS
`-- mount0/
|       (store contents)
|       LOCK

ltr command

partial commits e.g.: ltr commit podcasts/

ltr use volume@otherhost
ltr <volume> sync <host>
ltr status
ltr freeze (spawns new inbox)
ltr commit [-a] [filespec] [list on stdin]
ltr [!]lo                   [not] localonly (hide/show ghost files)

Indexer

Implemented by the inbox class.

The indexer can possibly speed up indexing by using diff on similarly named files.

The indexer should keep track of sha1 sums and produce a list of duplicates in a special file.

stay on one filesystem!!! (/proc/mounts look up mount, or python os.path.ismount())
recognise symbolic links!

Committing switches the active inbox to ro, compose todo list. (keep list of open files!)

Merger

implemented by the volume class.

keep attributes, mtime when copying/moving files!!!
update snapshot's index at once.

Conflicts:

file has been modified on A and B. (resolve: most recent?)
file has been modified on A before it was deleted on B

This is complicated by the fact that file moves are recognised.

-> should really proof of concept this...

Direct access volume

In this case, the store can be directly manipulated by other computers and the user (using the Rockbox file manager).

A technique has to be devised to track volume manipulations in an efficient manner, we could do SHA1 hashes of each file on every sync, but this takes a lot of time.

Therefore I suggest we consider the volume 'dirty'. When changes are to be applied to the volume we can use superficial scans on mtimes and existence of files. If the volume is to be used as a datasource by another ltr volume however, checksums must be matched for each file that is used.

The ltr command has to work in such a volume (e.g.; the presence of .ltrbin has to be checked in parent dirs.

When a direct access volume is found, it can be watched with Linux inotify, and a log can be kept of file operations. Care should be taken to exclude file operations by a ltr process (e.g.: sync-up with peer volume).

Suggested directory structure (incomplete):

ipod mountpoint
|
`---(other files)
|
`---audio/
|   |   (volume contents)
|   `-- .ltrbin/
|       `-- HEAD:
|       `-- tracks/
|       `-- manifest::
|       |   (which files were present)
|       `-- meta/
|           (tree with sha1+size files)

Ideas

Email

IMAP mail servers use maildirs to store email. Each mail is saved as a plain text file. This got me thinking. Instead of using IMAP, I could just store my mail (in maildirs) on a separate litter volume, like this setup:

litter to synchronize email between computers
getmail to fetch new mail
msmtp + ssh tunnel to send mail
mutt and Balsa as email clients.

It is still possible to use your mail from any IMAP aware (hand-held possibly) application if you set up an IMAP service on a server and have it operate on a litter volume.

Nautilus shell extension

Write it in python. Use existing vcs extensions, like tortoisehg-dev/contrib/nautilus-thg.py as a starting point.

Features:

emblems for local/non-local/queued files
shell shortcuts to mark files fetch/abandon

LitterHub

Central volume repository (doesn't have to keep any file contents though). On a server, set up an account using jailkit, put only sftp-server in it and make a .ssh/authorized_keys file with your private keys on the hosts you like. Use sshfs or sftp to access it.