Welcome to my web log. See the first post for an introduction. See the archive page for all posts. See also identi.ca.
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.
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.
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.
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.
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.
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.
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.
Tuesday: Gabriella Coleman's keynote about the origins and impact of the free software and hacker communities on the rest of the world was wonderful. Missed other talks, feeling very "shell shocked" and maybe culture shocked, and not really wanting to talk to people or hear people talk. Did see Blackheath's Haskell talk, which was a basic overview of Haskell features.
Wednesday: Mako Hill's keynote was very inspiring. Concepts of autonomy and anti-features are good. Matthew Garrett's "Making yourself popular" talk was good, though perhpas a bit shallow. JobsBOF was a washout for me, nothing interesting there. Roger Fenwick's "World's worst inventions" was funny.
(The above photo is rather bad. Sorry. I did not feel like carrying around with a real camera so I made do with the phone's.)
Thursday: Glyn Moody's keynote quite exceptionally good. He's one of my favorite two IT journalists. (The other one, Jon Corbet, was also at LCA, though I missed his talk and failed to talk to him.) Skipped the rest of the conference day, as Soile and I went and opened bank accounts and shopped for a car.
Friday: Lighting talks were ok, it's a good concept. Photo management BOF not too exciting, but interesting to hear that most people think tagging is too much work to be practical. I might want to make Dimbola be really good at that. Martin Krafft was late for the DebianBOF so I chaired/secretaried it. Lots of discussions, I almost felt it was my crowd still.
Penguin dinner in the evening was a disappointment from my point of view. Too many people, too much noise, I did not hear much and was slightly miserable. I should learn some day that I do not thrive in noisy crowds. I did, however, draw a penguin on my phone while there.
Saturday: LCA Open Day, talked to a bunch of people from companies, handed out my business card. A company called Lucid is doing a backup program called LBackup, free software, I might want to collaborate with them, given my continued interest in Obnam.
Also, saw a RepRap. Stunningly cool. A glimpse of the future.
I'm at the the LCA2010 conference in Wellington. Today was the first day, with miniconfs. A few notes:
The conference venue works well, except for occasional wireless problems.
Attempted to see how long my X200s battery actually lasts, and I managed to get through the day without charging. When I left the hotel, the battery was fully charged, and when I came back, there was an estimated 15 minutes left. However, I didn't use the laptop all the time, and I can't figure out from the GNOME Power Manager how much battery time I've actually used up today. The history dialog is entirely incomprehensible to me.
One thing that happens in conferences, including this LCA, is that people realize they've forgotten a cable or a charger or something, and someone else lends it to them. There's a bit of a shuffle for the lender and borrower to meet. I wonder if it would be too big a hassle for the organizers to set up a "post office": the lender would bring the cable, or whatever, put it in a bag, put their own name and the borrower's name on the bag, and then give it to the reception people to keep. The borrower could then fetch if from the reception whenever is suitable. Maybe this would be too much work and responsibility for the organizers, who are overworked as it is.
The weather is pretty nice. Some rain occasionally, but lots of sunshine, too. Pretty warm. People are very friendly.
As I'm reading Cory Doctorow's Makers novel, I can't help wondering whether it might be possible to write a novel collaboratively. Each participant would write a paragraph per day, and readers could vote paragraphs up and down. It might be interesting to see if a coherent story would eventually emerge.