liw's blog

Photo by Soile Mottisenkangas

Welcome to my web log. See the first post for an introduction. See the archive page for all posts. See also identi.ca.

Server maintenance styles

This thought struck me today, out of the blue.

There are two ways of running servers:

  1. Keep it rock solid, by avoiding change as much as possible. This is quite excellent: nothing changes, so minimal effort is required and costs are cheap. Those relying on the server can just assume it is there. However, when there is a necessary change, such as a kernel security update, it is quite disruptive. Everything stops, people get nervous, and deodorant sales go up.
  2. Make frequent changes, and build everything on the assumption that the server may be out of service at any time. Replicate services, avoid keeping state unnecessarily, and do anything else you need to do to handle the constant rebooting and other outages. This is more expensive to build, and to run, but perhaps not a lot more, and a kernel update will barely even be noticed. It is not disruptive at all. You will save a lot on deodorant.

Now, I do not run many servers, so this may be bogus.

Keeping a journal

For a while now, I have kept a journal of my programming related activities. I find this to be good for three things:

  1. I pour out all my thoughts about a problem I am solving, or task I am doing, and this helps me think more clearly. The act of writing requires me to think things through. When I write like this, I write to a future self, who is angry and digging in the journal to find out why I did the stupid thing I did. Sometimes, if I explain my reasoning, I realize while writing that I am doing a stupid thing. Other times, my future self will realize that my reasoning was sound, but something happened to make it stupid later. In a more social setting, I could discuss things with a co-worker to get the same benefit.
  2. I write down steps to do specific tasks, which is sometimes helpful when I need to do them again, or when I need to figure out what broke.
  3. If I am hacking on some code, and need to take a long break (for example, to drive from Christchurch to Wellington via Auckland), I can more easily pick up the work again. My journal will tell me where I was, and what I was thinking.

I do not keep the journal as regularly as I wish I would, but even when I update it only half the time, it is quite useful. When you can't walk, it helps if someone carries you, even if they only carry you half way.

I started this journal on November 3, 2005, using a single plain text file. Eventually that grew too big to be practical, so it became a series of text files instead, one per day. For a while the files were in HTML, but that was tedious, so I switched back to plain text again. Now, I use ikiwiki and markdown.

Markdown is a wonderful, minimal markup language. Almost all of my journal entries from the plain text era were already in markdown, perhaps with minor tweaks. When I need more power, I have it, but when I don't, I do not have to do suffer from the tediousness of writing HTML by hand.

Ikiwiki is a wonderful wiki engine, which is quite flexible. It can use a real version control system to store the wiki contents. With modern distributed version control systems, this gives the additional possibility of having multiple instances of the wiki. For my journal, this is useful: I can have the same journal on my laptop, for personal projects, and on my work machine, for work stuff. Having the same journal on both places makes it easier to look things up.

I could keep the journal on a server, of course, and access it over the Internet. That is what I would do, if I had good Internet access everywhere, but I don't.

Using a good wiki engine for the journal has proven to be quite useful. I can use tagging to make it easier to see journal entries for specific topics. Ikiwiki uses the xapian search engine to provide handy full text searches.

I am also experimenting with a feature to have wiki pages for people I mention in my journal entries. Each person has a dedicated page (/person/wirzenius.lars), and each entry that mentions that person, links to their page. The page then uses ikiwiki's inline directive to automatically list all journal entries that mention them.

This makes it much easier for me to remember who the people are, for people I meet rarely. There is something wrong with my brain when it comes to remembering people, and I need every bit of help I can get.

I may expand this to other things than people, some day, but I need to be careful about not making it too tedious, or I will stop keeping the journal. Full semantic web markup is not going to happen.

Lazyweb: B-tree code review?

I think I need a B-tree implementation for Obnam, in Python. I could not find anything suitable so I wrote my own. However, since it about two decades since my data structures class at university, I probably messed it up. Please tell me how?

I include the code below, and it can also be found via bzr:

bzr get http://code.liw.fi/btree/bzr/trunk/

The code in bzr may get updated; I will keep the code below static. The bzr branch also contains some automatic test cases.

One of the requirements I have for the B-tree code is that it needs to update things via copy-on-write. In Obnam, I will not overwrite data on disk, I will instead write a new file, and then do garbage collection at a later time to reclaim the files that are no longer needed. This will be necessary for implementing backup generations, for example. That's why some of the code might be a bit weird.

Once I have some confidence that my code works, I will extend the tree code to use some external, user-provided mechanism for storing the nodes, and to use the size of the nodes in bytes as the limiting factor, not the number of keys.

In addition to bugs, I welcome any other feedback.

class Node(dict):

    '''Abstract base class for index and leaf nodes.

    A node may be initialized with a list of (key, value) pairs. For
    leaf nodes, the values are the actual values. For index nodes, they
    are references to other nodes.

    '''

    def keys(self):
        '''Return keys in the node, sorted.'''
        return sorted(dict.keys(self))

    def first_key(self):
        '''Return smallest key in the node.'''
        return self.keys()[0]

    def pairs(self, exclude=None):
        '''Return (key, value) pairs in the node.

        ``exclude`` can be set to a list of keys that should be excluded
        from the list.

        '''

        if exclude is None:
            exclude = []
        return sorted((key, self[key]) for key in self if key not in exclude)


class LeafNode(Node):

    '''Leaf node in the tree.

    A leaf node contains key/value pairs, and has no children.

    '''

    pass


class IndexNode(Node):

    '''Index node in the tree.

    An index node contains pairs of keys and references to other nodes.
    The other nodes may be either index nodes or leaf nodes.

    '''

    def __init__(self, pairs):
        for key, child in pairs:
            assert type(key) == str
            assert isinstance(child, IndexNode) or isinstance(child, LeafNode)
        dict.__init__(self, pairs)

    def find_key_for_child_containing(self, key):
        '''Return key for the child that contains ``key``.'''
        for k in reversed(self.keys()):
            if key >= k:
                return k
        return None


class BTree(object):

    '''B-tree.

    The tree is balanced, and has a fan-out factor given to the initializer
    as its only argument. The fan-out factor determines how aggressively
    the tree expands at each level.

    Three basic operations are available to the tree: lookup, insert, and
    remove.

    '''

    def __init__(self, fanout):
        self.root = IndexNode([])
        self.fanout = fanout
        self.min_index_length = self.fanout
        self.max_index_length = 2 * self.fanout + 1

    def lookup(self, key):
        '''Return value corresponding to ``key``.

        If the key is not in the tree, raise ``KeyError``.

        '''

        return self._lookup(self.root, key)

    def _lookup(self, node, key):
        if isinstance(node, LeafNode):
            return node[key]
        else:
            k = node.find_key_for_child_containing(key)
            if k is None:
                raise KeyError(key)
            else:
                return self._lookup(node[k], key)

    def insert(self, key, value):
        '''Insert a new key/value pair into the tree.

        If the key already existed in the tree, the old value is silently
        forgotten.

        '''

        a, b = self._insert(self.root, key, value)
        if b is None:
            self.root = a
        else:
            self.root = IndexNode([(a.first_key(), a),
                                   (b.first_key(), b)])

    def _insert(self, node, key, value):
        if isinstance(node, LeafNode):
            return self._insert_into_leaf(node, key, value)
        elif len(node) == 0:
            return self._insert_into_empty_root(key, value)
        elif len(node) == self.max_index_length:
            return self._insert_into_full_index(node, key, value)
        else:
            return self._insert_into_nonfull_index(node, key, value)

    def _insert_into_leaf(self, leaf, key, value):
        pairs = sorted(leaf.pairs(exclude=[key]) + [(key, value)])
        if len(pairs) <= self.fanout:
            return LeafNode(pairs), None
        else:
            n = len(pairs) / 2
            leaf1 = LeafNode(pairs[:n])
            leaf2 = LeafNode(pairs[n:])
            return leaf1, leaf2

    def _insert_into_empty_root(self, key, value):
        leaf = LeafNode([(key, value)])
        return IndexNode([(leaf.first_key(), leaf)]), None

    def _insert_into_full_index(self, node, key, value):
        # A full index node needs to be split, then key/value inserted into
        # one of the halves.
        pairs = node.pairs()
        n = len(pairs) / 2
        node1 = IndexNode(pairs[:n])
        node2 = IndexNode(pairs[n:])
        if key <  node2.first_key():
            a, b = self._insert(node1, key, value)
            assert b is None
            return a, node2
        else:
            a, b = self._insert(node2, key, value)
            assert b is None
            return node1, a

    def _insert_into_nonfull_index(self, node, key, value):        
        # Insert into correct child, get up to two replacements for
        # that child.

        k = node.find_key_for_child_containing(key)
        if k is None:
            k = node.first_key()

        a, b = self._insert(node[k], key, value)
        assert a is not None
        pairs = node.pairs(exclude=[k]) + [(a.first_key(), a)]
        if b is not None:
            pairs += [(b.first_key(), b)]
        pairs.sort()
        assert len(pairs) <= self.max_index_length
        return IndexNode(pairs), None

    def remove(self, key):
        '''Remove ``key`` and its associated value from tree.

        If key is not in the tree, ``KeyValue`` is raised.

        '''

        self.root = self._remove(self.root, key)
        if self.root is None:
            self.root = IndexNode([])

    def _remove(self, node, key):
        if isinstance(node, LeafNode):
            return self._remove_from_leaf(node, key)
        else:
            k = node.find_key_for_child_containing(key)
            if k is None:
                raise KeyError(key)
            elif len(node[k]) <= self.min_index_length:
                return self._remove_from_minimal_index(node, key, k) 
            else:
                return self._remove_from_nonminimal_index(node, key, k)

    def _remove_from_leaf(self, node, key):
        if key in node:
            pairs = node.pairs(exclude=[key])
            if pairs:
                return LeafNode(pairs)
            else:
                return None
        else:
            raise KeyError(key)

    def _merge(self, n1, n2):
        if isinstance(n1, IndexNode):
            assert isinstance(n2, IndexNode)
            return IndexNode(n1.pairs() + n2.pairs())
        else:
            assert isinstance(n1, LeafNode)
            assert isinstance(n2, LeafNode)
            return LeafNode(n1.pairs() + n2.pairs())

    def _remove_from_minimal_index(self, node, key, child_key):
        exclude = [child_key]
        new_ones = []
        child = self._remove(node[child_key], key)

        if child is not None:
            keys = node.keys()
            i = keys.index(child_key)

            # If possible, merge with left or right sibling.
            if i > 0 and len(node[keys[i-1]]) < self.max_index_length:
                new_ones.append(self._merge(node[keys[i-1]], child))
                exclude.append(keys[i-1])
            elif i+1 < len(keys) and len(node[keys[i+1]]) < self.max_index_length:
                new_ones.append(self._merge(node[keys[i+1]], child))
                exclude.append(keys[i+1])
            else:
                new_ones.append(child)

        others = node.pairs(exclude=exclude)
        if others + new_ones:
            return IndexNode(others + [(n.first_key(), n) for n in new_ones])
        else:
            return None

    def _remove_from_nonminimal_index(self, node, key, child_key):
        child = self._remove(node[child_key], key)
        pairs = node.pairs(exclude=[child_key])
        if child is not None:
            pairs += [(child.first_key(), child)]
        pairs.sort()
        assert pairs
        return IndexNode(pairs)

Obnam performance requirement

I don't think I've said this publically yet, so I'll do it now: My performance goal with obnam for the 1.0 release is to be able to saturate a wifi connection. That means that it needs to be able to write at least 3 megabytes per second when doing a local backup.

It's not a hugely impressive goal, but it satisfies my personal use cases.

Living with limited Internet access: saving web pages instead of bookmarking them

I'm currently touring New Zealand. Internet access here is either very slow, very expensive, or both. Or it's not there at all.

I have long bookmarked pages I want to read, but don't have time to read at the moment I encounter them. For example, if I'm reading reddit, I open all the pages that seem interesting, and if they seem interesting after the first ten seconds, I bookmark them.

This works quite well, when I have good Internet access.

I've now switched to saving pages locally instead. Firefox's "File/Save as" works quite well, except when pages insist on doing things in complicated ways.

Autojen GPS-urkinta etenee

YLE uutisoi, että Sunnuntaisuomalainen uutisoi, että Ajokilometreihin perustuva autovero altis huijaukselle:

Kilometreihin perustuva autovero ja Helsinkiin kaavailtu ruuhkamaksu ovat alttiita huijaukselle, kirjoittaa Väli-Suomen sanomalehtien Sunnuntaisuomalainen. Molemmat perustuvat autojen satelliittipaikannukseen, mutta internetistä saa tilattua laitteita, joilla paikannuksen voi estää.

Välineitä GPS-vastaanoton häiritsemiseen saa ostettua mistä tahansa rautakaupasta. Riittää, että antennin ympärille pistää metallipurkin.

YLE kirjoittaa myös:

Kilometreihin perustuvasta autoverosta ei ole päätöstä, mutta liikenneministeri Anu Vehviläinen (kesk.) on ehdottanut sellaista.

Pelkkien ajokilometrien seurantaan GPS on monimutkainen ja virheherkkä ratkaisu. Kaikissa autoissa on jo valmiiksi paljon yksinkertaisempi väline: kilometrimittari.

Monimutkaisen, virheherkän ja kalliin valvontajärjestelmän rakentamisen sijaan olisi helppoa vaatia, että ajoneuvon vuosittaiset kilometrit rekisteröidään katsastuksen yhteydessä.

Vielä helpompaa olisi nostaa polttoaineveroa. Se ei vaatisi minkään uusien järjestelmien rakentamista.

Tätä ei kuitenkaan tulla tekemään, koska Suomen poliittiset päättäjät ovat joko teknologiayritysten nenästä vedettävissä tai ovat ymmärtäneet kirjan 1984 aivan väärin.

Edelleen YLE:n uutisesta:

Öörni uskoo, että häirintälaitteiden kitkemiseksi joudutaan rakentamaan tekninen valvontajärjestelmä. Todennäköisin vaihtoehto on rekisterikilpiä kuvaavat liikuteltavat kamerat.

Totta kai on järkevää ensin rakentaa monimutkainen, virheherkkä, kallis GPS-valvontajärjestelmä ja sen jälkeen toinen monimutkainen, virheherkkä ja kallis järjestelmä valvomaan ensimmäisen toimivuutta. Tämä on järkevää nimenomaan siksi, että kumpikin järjestelmä on omiaan ihmisten valvomiseen.

Tämä on tärkeä pointti: kaikki nämä järjestelmät tähtäävät viime kädessä siihen, että autojen kaikkia liikkeitä valvotaan mahdollisimman tarkasti. Koska melkein kaikki autot ovat yhden tai kahden kuljettajan käytössä, tässä valvotaan siis ihmisten liikkumista.

Jos hallituksessa olisi yhtään yksityisyydestä välittävää henkilöä, nämä hankkeet ja puheet loppuisivat lyhyeen tai ainakin niiden hyödyistä ja haitoista käytäisiin julkista keskustelua. Nyt pelkästään puhutaan siitä, miten mahdolliset järjestelmää huijaavat saadaan kiinni.

Obnam is feature complete (sort of)

I have recently implemented all Obnam features I think I want before I start using it for real, except encryption. The next step is to re-implement the backup store implementation. The current implementation is the simplest, most stupidest one I could get away with. I did not care at all about performance, so it is rather, er, slow.

I said stupid, right? Yes I did.

I may end up implementing the backup store in several ways, to be able to compare them in semi-real-life benchmarks.

I was going to add support for ACLs and extended attributes, but I decided not to: I do not use them myself, and they're just non-obvious enough that I am going to need to find a collaborator to verify I do the right thing. (Ideally, someone who'll also write the code... I promise to show how.)

In other news, B-trees are surprisingly interesting.

Cable management while travelling

We're travelling and we have several electronic devices with us. This means we have many cables. Cables are difficult enough at home, but especially so while travelling.

My current best approach is to put each cable in a small clear plastic bag (zip lock bag, I think they're called). This prevents the cables from getting entangled, but there's so many of them that it's still hard to keep them in order.

I wonder if it would be possible to develop a better solution? My best idea so far is a long piece of fabric with pieces of velcro sewn into it. The velcro would be located so that it would be possible to neatly put each cable in place and then roll the whole piece of fabric into a neat roll.

When it would be time to get a cable, one would unroll the fabric, and then unfasten one or two pieces of velcro to get the cable.

Perhaps pockets instead of velcro?

Anyone have better ideas? Anyone have an actual solution? I live in mortal dread of waking up one morning and learning that my cables have started to breed, and have decided to overthrow their master, and have strangled me to death while I slept.

Computer driving licenses

Various countries have a training programme called the "computer driving license". The training aims to give basic computer using skills (word processing, spreadsheets, the web, etc). It's good for people unsure of their skills, but I object to the name.

I think it's worrying that it's called a license of any kind, since that implies that there is an entity whose permission people need to use a computer. Licenses to own and operate copying machines or typewriters have existed, and it's always a sign of political oppression. It's just a word, but words have power, or at least they give leverage to those in power.

Obnam storage API

The central data structure in Obnam is the way it stores backed up data on disk. This is the area I have struggled with most in the four years I've been sporadically developing Obnam.

My initial attempt was roughly this: everything was put in the backup store as a sort of object, which I'll call backup object. This included file contents, deltas between versions of a file, file metadata, and filenames. While the representation was quite different, essentially each of these objects was a list of key-value pairs:

file:
    id = 12765
    basename = "/home/liw/foobar/foobar.c"
    st_mtime = 32
    contref = 42

contents:
    id = 42
    data = "/* foobar.c -- a program to make foo do bar */\n..."

generation:
    id = 105
    file = "/home/liw/foobar/foobar.c", 12765
    file = "/home/liw/foobar/README", 32765
    ...

Each generation consists of a list of filenames and pointers to the object that represents the version of the file in that generation. If a file has not changed from generation to generation, the pointer (and thus the file contents) from the previous generation is reused.

This was pretty simple, but it repeated the entire list of files, with names for each generation. The filenames take a surprising amount of space. Some statistics from my laptop:

Number of files: 401509
Basenames: 6 MiB
Pathnames: 27 MiB

It is ridiculous to store the full list of files (whether basenames or pathnames) for each generation. Even just the basenames will use more than a typical delta between each backup run, for me. This is clearly not acceptable.

After I realized this, I set to fix this by storing only changed filenames. I got this to work, but for various reasons it was very slow, and the complexity of the code made it hard to improve.

Instead of using a pathname as an index to a hashtable, as before, I was now building a duplicate of the filesystem's directory tree in my backup store. Each directory and file was represented by by a backup object, and the generation only held a list of root objects (essentially, the root directory).

When making a new backup, I would carefully do an update from the bottom of the filesystem directory tree upwards, doing copy-on-write updates on any backup objects that had changed since the previous backup. While this is reasonably straightforward to do, it made the code unnecessarily complicated. The code to do backups had to worry about functional updates to trees, which really isn't its business.

The fundamental cause for this misplaced complexity was that the backup store API was using object identifiers as keys, whereas backups (and restores and other operations) really want to handle filenames.

My current approach in the second complete rewrite is to return to pathname based indexing, but keep the copy-on-write behavior. I do not yet know how I will implement this, but I do know I need to keep all the complexity inside the backup store implementation. Right now I am concentrating on finding the best API for the store so that the rest of the program will be easy to write.

It's important that the API be non-tedious to use. There's a lot of room for exploration in backups for what to back up and when, and in which order. There's even further room for exploration in doing stuff with backed up data: verification, FUSE filesystems, etc. If the store API is tedious, it'll be harder to do all those nice things. If it is easy, they'll be that much easier to do.

I have hacked up a first draft of the store API. Before I discuss it, I'll give outlines of how the backup is coded, in pseudo-Python:

def backup(directories):
    for each directory:
        backup_directory(directory)

def backup_directory(dirname):
    for each file directory:
        backup_file(filename)
    backup_metadata(dirname)

def backup_file(filename):
    if file has changed:
        backup_file_contents(filename)
        backup_metadata(filename)

def backup_file_contents(filename):
    for each chunk in file:
        if chunk exists in store already:
            remember its id
        else:
            put chunk into store and remember new id
    set chunk ids for filename

def backup_metadata(pathname):
    read metadata from filesystem
    put metadata into store

That's about as straightforward as one can imagine. The store API is starting to emerge (semi-real-Python):

class Store:

    def create(self, pathname):
    def set_metadata(self, pathname, metadata):
    def set_file_chunks(self, pathname, chunkids):
    def find_chunk(self, data):
    def put_chunk(self, data):

However, this is not quite ready yet. There is, for example, no concept of generations. After some playing around and discussions with Richard Braakman, I've ended up with the following approach.

A new generation is initially created as a clone of the previous generation (or empty, if it is the first generation). The new clone can be modified, in a copy-on-write fashion, and when all changes are done, they can be committed into the store. After that, the generation is immutable, and cannot be changed anymore.

This results in small changes to the main backup routine:

def backup(directories):
    start new generation
    for each directory:
        backup_directory(directory)
    commit started generation

And a couple of new methods to the Store class:

def start_generation(self):
def commit_generation(self):

Backups will now work reasonably efficiently, yet the code is simple. The complexity is all nicely hidden in the Store class.

Restoring should also be easy:

def restore():
    restore_directory(generation_id, '/')

def restore_directory(genid, dirname):
    create target directory on output filesystem
    for each item in the directory in the generation in the store:
        if it is a directory:
            restore_directory(genid, sub-directory name)
        else:
            restore_file(genid, full pathname to file)
    restore target directory metadata

def restore_file(genid, filename):
    for each chunk in file:
        read chunk
        write to output file
    restore file metadata

The store API needs a couple of new things:

def listdir(self, genid, dirname):
def get_metadata(self, genid, pathname):
def get_file_chunks(self, genid, filename):

There's a little bit more to it to handle hardlinks, symlinks, and other special cases, but this is basically what the API will now look like.

I have imlemented a proof-of-concept version of the API to allow me to play with it, and see what the rest of the code would look like. I am still assuming that using something like the funcational B-trees in btrfs will be a good way to implement it properly, but the API is not assuming that, I hope. (The code is slightly different from the above snippets. If you want to have look at the actual code, bzr get http://code.liw.fi/obnam/bzr/rewrite4/ will get you a copy.)

So far, I am happy with this. There's a whole bunch of questions remaining that I will get to. Right now the thing that worries me most is finding chunks in the backup store: can I implement it efficiently enough that it will be useful. Some version of this will need to be done, so that I can de-duplicate data in the filesystem. For example, if I move a ISO file to a new place and make some small changes to it, it would be disastrous if I had to back it up completely, even though almost all data is already in the backup store.

I am not sure how much effort to put into the de-duplication. It involves trade-offs that may depend on things like available bandwidth and bandwidth caps. It may be necessary to make it configurable: a user with vast amounts of bandwidth and disk space might not care, but someone travelling around the world and relying on hotel Inetnyet connections might care very much.

I'm running an experiment right now to see how much duplicate data there is on my laptop. My approach is to compute a checksum for each 4 kilobyte block at 64 byte intervals and then find duplicate checksums. Since I have quite a bit of data on my laptop, this is a pretty big computation, so it'll be a while before I get results.