
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:
- 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.
- 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:
- 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.
- 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.
- 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?
-
Permalink
- 2010-03-14 06:04:35 +0200
-
obnam
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
-
Permalink
- 2010-02-28 07:53:29 +0200
-
obnam
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)
-
Permalink
- 2010-02-19 04:53:46 +0200
-
obnam
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
-
Permalink
- 2010-02-05 08:45:12 +0200
-
idea
travel
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
-
Permalink
- 2010-02-05 00:58:51 +0200
-
freedom
politics
rant
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
-
Permalink
- 2010-02-01 05:56:39 +0200
-
obnam
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.