Implementing deferred registration (or lazy registration) with Django

Published at

Friday 24th July, 2009

Tagged as

Django
Deferred registration
Lazy registration

Rationale

Imagine a shopping site where you had to sign up before you added things to your basket; you could certainly use it, but it would have to have strong incentives for you to bother rather than, say, use Amazon or another site where you can just get stuck straight into shopping. Of course, most shopping sites work like this, so you never really think about it.

But why should you have to register for any site before using it? (Beyond special cases.) You don't have to register before using Google, and you don't have to register before using the BBC News site; you also don't have to register before using Hunch, a site to help you make decisions that first has to get various pieces of information out of you so it can make useful suggestions. Deferred registration is a way of describing this, a phrase I've heard bandied around over the last year or so among web folk. But isn't it terribly difficult?

While at /dev/fort 2 back in June, we built a cooking site, where the main object is a recipe. Since we were building the site from scratch, and since it seemed like obviously the right thing to do, we used deferred registration: you can create recipes before you login or register, and later on they get stuck under the right user. We did this partly to convince ourselves that it really wasn't that difficult; and partly so we could convince other people ;-)

At some point we may put the code for the entire site online, but for now I've extracted what we wrote into a small re-usable extension to Django; it provides an easy way of storing objects in the session until we're ready to assign them to the correct user. Here, I'll describe how to use it in building a very simple website for keeping track of your present wishlist, in a manner similar to Things I Love.

"Deferred registration"?

It made sense to me calling this deferred registration, but it turns out it's more commonly called lazy registration.

Doing it in Django

We have a few assumptions here, and one is that you know how to use Django; I'm not going to go into great detail about the mechanics that are common to Django projects, since we can get that from the online documentation. I won't show every detail, and you won't end up with a fully-working wishlist system at the end of this, but hopefully you'll understand how to implement deferred registration. Additionally, I assume you're using the Django session middleware, and the standard auth system (in django.contrib.auth).

The code I've written is on github; this just needs to be on your PYTHONPATH somewhere.

Later on, I assume you're going to use Simon Willison's new django-openid (also on github), which while still a work-in-progress is sufficiently complete that it can be used here, and makes life a little easier. (The name is slightly misleading, as it doesn't just support OpenId, but provides a consistent workflow around registration and authentication.)

Creating our models

We'll have three main models: Wishlist, WishlistItem and WishlistPurchase. There isn't going to be anything hugely sophisticated about what we build here; let's just keep things very simple. (Actually, I'm not even going to touch the latter two; but the intention is that this is a just-enough-complicated example I can use it again in future.)

The key thing here is that SessionStashable is a mixin to the Model class; it augments the class (and the instantiated objects) with some useful methods for managing a list of objects in the session. If you're working with more than one stashable model, as we are here, you need to set session_variable to something different on each model. For now, that's all we need to do: your models are session-stashable straight off.

We're making wishlists and purchases stashable, but not wishlist items, because every item is already in a wishlist, so we know all the items were created by whoever created the wishlist. Note that created_by on both our stashable models is marked null=True, blank=True, because we need to be able to create them without a creator in the database.

Finally, I'm not showing the mechanism for generating slugs; I use another tiny Django plugin that takes care of this for me. Hopefully I'll be able to write about this in due course.

# wishlist.wishlists.models
from django.db import models
from django.contrib.auth.models import User
from django_session_stashable import SessionStashable

class Wishlist(models.Model, SessionStashable):
    slug = models.CharField(max_length=255)
    created_by = models.ForeignKey(User, null=True, blank=True)
    name = models.CharField(max_length=255)

    session_variable = 'wishlist_stash'

    @models.permalink
    def get_absolute_url(self):
        return ('wishlist', (), { 'list_slug': self.slug })

    def __unicode__(self):
        return self.name

class WishlistItem(models.Model):
    slug = models.CharField(max_length=255)
    wishlist = models.ForeignKey(Wishlist)
    name = models.CharField(max_length=255)
    description = models.TextField()

    def __unicode__(self):
        return self.name

class WishlistItemPurchase(models.Model, SessionStashable):
    item = models.ForeignKey(WishlistItem)
    created_by = models.ForeignKey(User, null=True, blank=True)
    created_at = models.DateTimeField(auto_now_add=True)

    session_variable = 'purchase_stash'

    def __unicode__(self):
        if self.created_by:
            return u"%s: %s @ %s" % (self.created_by, self.item, self.created_at)
        else:
            return u"%s @ %s" % (self.item, self.created_at)

Hopefully there's nothing unexpected there, and you're following along nicely.

Creating our views

I'm not going to bother showing all the views here, as the same techniques will apply to both stashable models. Let's set up urls.py as follows.

urlpatterns += patterns('',
    url(r'^lists/$', 'wishlist.wishlists.views.list_list', name='wishlist-list'),
    url(r'^lists/create/$', 'wishlist.wishlists.views.list_create', name='create-wishlist'),
    url(r'^lists/(?P<list_slug>[a-zA-Z0-9-]+)/$', 'wishlist.wishlists.views.list_view', name='wishlist'),
    url(r'^lists/(?P<list_slug>[a-zA-Z0-9-]+)/edit/$', 'wishlist.wishlists.views.list_edit', name='edit-wishlist'),
)

Anyone (including an anonymous user) can list wishlists; in a full application, we'd show your friends' lists, but for now we'll just show any you've created. You can then edit any wishlist you created (similarly for delete, not shown here).

Don't worry about the render function for the moment; we'll look at that further in a minute. For now, it's doing basically the same job as render_to_response.

# wishlist.wishlists.views
from django.http import HttpResponse, HttpResponseRedirect, HttpResponseForbidden
from django.shortcuts import get_object_or_404
from django.forms.models import ModelForm
from wishlist.wishlists.models import Wishlist
from wishlist.shortcuts import render, HttpResponseRedirect

class WishlistForm(ModelForm):
    class Meta:
        model = Wishlist
        fields = ('name',)

def list_list(request):
    if request.user.is_anonymous():
        lists = Wishlist.get_stashed_in_session(request.session)
    else:
        lists = Wishlist.objects.filter(created_by=request.user)
    return render(request, 'wishlists/list_list.html', { 'lists': lists })

def list_view(request, list_slug):
    l = get_object_or_404(Wishlist, slug=list_slug)
    if not l.viewable_on_this_request(request):
        return HttpResponseForbidden("You're not allow to see this wishlist. Sorry!")
    return render(request, 'wishlists/list_view.html', { 'list': l, 'editable': l.editable_on_this_request(request) })

def list_edit(request, list_slug):
    l = get_object_or_404(Wishlist, slug=list_slug)
    if not l.editable_on_this_request(request):
        return HttpResponseForbidden("You're not allow to edit this wishlist. Sorry!")
    if request.method=='POST':
        form = WishlistForm(request.POST, instance=l)

        if form.is_valid():
            l = form.save()
            return HttpResponseRedirect(l.get_absolute_url())
    else:
        form = WishlistForm(instance=l)
    return render(request, 'wishlists/list_edit.html', {
        'list': l,
        'form': form,
    })

def list_create(request):
    if request.method=='POST':
        form = WishlistForm(request.POST)

        if form.is_valid():
            list = form.save(commit=False)
            if not request.user.is_anonymous():
                list.created_by = request.user
            list.save()
            list.stash_in_session(request.session)
            return HttpResponseRedirect(list.get_absolute_url())
    else:
        form = WishlistForm()

    return render(request, 'wishlists/list_create.html', {
        'form': form,
    })

Again, nothing terribly complex. The list_list view pulls objects out of the session stash if you're an anonymous user (since once you've logged in or registered they'll just be marked as created by you). list_create does a tiny dance to set created_by if you're logged in, and stashes the request away (stash_in_session is careful not to stash anything if the object has something in created_by).

Notice that we haven't used anything like login_required, because this shuts off everything to users who haven't registered yet. Instead, we check whether the user can view or edit a wishlist, and return a HttpResponseForbidden object. (This looks a little ugly by default, although you can set things up to get a custom template rendered instead.) We've introduced two new methods into the Wishlist class: editable_on_this_request() and viewable_on_this_request(), which are needed so we can check the session if needed.

def viewable_on_this_request(self, request):
    if self.created_by==None:
        return self.stashed_in_session(request.session)
    else:
        return True

def editable_on_this_request(self, request):
    if self.created_by==None:
        return self.stashed_in_session(request.session)
    else:
        return self.created_by == request.user

In editable_on_this_request, if created_by is set it won't match the AnonymousUser, only a real authenticated one.

Reparenting on registration/login

Finally, on registration or login, we need to pass over the wishlists we've created (and wishlist purchases we've made, although we haven't discussed any of that side of the site) and reparent them to the user we now have. This is actually very easy, and takes two lines of code in a suitable view.

Wishlist.reparent_all_my_session_objects(request.session, request.user)
WishlistItemPurchase.reparent_all_my_session_objects(request.session, request.user)

Let's look at how this will work with django_openid. First, we modify urls.py.

from auth.views import registration_views

urlpatterns += patterns('',
    (r'^login/$', registration_views, {
        'rest_of_url': 'login/',
    }),
    (r'^logout/$', registration_views, {
        'rest_of_url': 'logout/',
    }),
    (r'^account/(.*)$', registration_views),
)

Then we write our views file; django_openid uses a Strategy pattern, so all the views are tied into a single object.

# wishlist.auth.views
from django_openid.registration import RegistrationConsumer
from django_openid.forms import RegistrationForm
from django.conf import settings
from wishlist.wishlists.models import Wishlist, WishlistItemPurchase
from wishlist.shortcuts import render, HttpResponseRedirect

class RegistrationViews(RegistrationConsumer):
    def on_registration_complete(self, request):
        Wishlist.reparent_all_my_session_objects(request.session, request.user)
        WishlistItemPurchase.reparent_all_my_session_objects(request.session, request.user)
        return HttpResponseRedirect('/')

    def on_login_complete(self, request, user, openid=None):
        Wishlist.reparent_all_my_session_objects(request.session, request.user)
        WishlistItemPurchase.reparent_all_my_session_objects(request.session, request.user)
        return HttpResponseRedirect('/')

    def render(self, request, template_name, context = None):
        context = context or {}
        return render(request, template_name, context)

registration_views = RegistrationViews()

In practice you'll want to do more work here. For a start, there are lots of templates you'll need, although django_openid ships with ones that may be suitable for you. But this shows the bits that matter to us: two hook methods, on_registration_complete and on_login_complete, which are the right place to reparent all our stashed objects. It also makes django_openid use our render function — and now it's time to look at that.

Warning users of unparented objects

One final touch: it's nice to give a hint to people who haven't registered or logged in that they will lose their wishlists unless they do. Since we want to put this message on every single page, it needs to be done centrally, at the point that we render our templates. This is where the render function we've been using comes in.

# wishlist.shortcuts
from django.template import RequestContext
from django.shortcuts import render_to_response
from django.http import HttpResponseRedirect

def render(request, template_name, context=None):
    from wishlist.wishlists.models import Wishlist, WishlistItemPurchase
    context = context or {}
    context['stashed_wishlists'] = Wishlist.num_stashed_in_session(request.session)
    context['stashed_purchases'] = WishlistItemPurchase.num_stashed_in_session(request.session)
    return render_to_response(
        template_name, context, context_instance = RequestContext(request)
    )

Using a central function like this means that we can have a number of variables appear in the render context for every template rendered. In this case, we just have two: stashed_wishlists and stashed_purchases. We can then use them to show a brief warning. This would go in a base template (so all other templates would need to use {% extends "base.html" %} or similar).

{% if stashed_wishlists %}
    <div id="notifications" class="receptacle">
        <div class="section">
            <p><em>Warning</em>: you have <a href="{% url wishlist-list %}">unsaved wishlists</a>!
            <a href="/account/register/">Register</a> or <a href="/login/">log in</a> to keep them forever.</p>
        </div>
    </div>
{% endif %}

There isn't much to say here at all. (Except, okay, the HTML could be simpler; but this is all taken from a running app, in the hope it will avoid introducing bugs.)

Going further

You can use the same approach for things like comments; store the comment with no creator, stash it in the session, and come back to it later. With care, and some thought, you can apply this technique to most things that might need deferred registration.

It's a good idea to plan all the interactions around deferred registration before you start coding (which goes against the instincts of a lot of developers). As well as the code behind creation and reparenting, it can have an impact on how your pages fit together, and the interaction elements on those pages. You also have to pay attention when you render lists of things that can be created in this way, so you either don't display those waiting for a real creator, or alter the display suitably so you don't show text like created by None. If the latter, you may want to open up the display page to more than just the creator.

Despite a little bit more work up front, it shouldn't take much longer overall to get this right. Don't believe me? Grab the code and try using it next time you build a site.

Ada Lovelace Day

Published at

Tuesday 24th March, 2009

Tagged as

Women
Inspiration
Ada Lovelace
Ada Lovelace Day

Today, 24th March, is Ada Lovelace Day, an idea from Suw Charman-Anderson for people to celebrate the women in technology whom they admire. Amongst the aims are to provide role models for women in technology, and to celebrate inspirational women in technology. Both of these are great aims (and this approach strikes me as considerably more practical and sane than getting only women together for some tech love-in, or having serious round-table discussions about how to get more women into tech jobs).

But I'm not going to write about a leading woman in technology, either now or in the past. I want to spend a few quick words stating, flatly, that the women I've worked with on technology projects (be they programmers, designers, product folk, customer service people, or going right back to school and the girls I did experiments with in my A-level chemistry class¹) have been, with very few exceptions, talented, dedicated, interesting and passionate people. Almost all have inspired me to be better at what I do; and many have challenged me at some point or other, forcing me to think again when I was certain I was right, or to consider a different perspective when I thought there was only one valid viewpoint. I can say that of far fewer of the men I've worked with².

I could spend half an hour drawing up a list of those women, but I'd be bound to leave some out. Come talk to me about them, or perhaps check out who I follow on twitter and find some to inspire you as well. I would be poorer without any one of them.

¹ With them, not on them. They were entirely willing to play reflux reactions with me.

² Although it's possible that I just ignored more of the men. I don't react well to declarative statements I disagree with, which appears to be a more male way of trying to argue with me.

Reinstall

Published at

Wednesday 25th February, 2009

Tagged as

Microsoft
Old School
The future (is more shiny)

I'm currently reinstalling my Windows machine, giving it brand new drives and basically a complete make-over, this to prepare it for editing Talk To Rex's next production. Generally speaking, you have to reinstall Windows every so often anyway, and this machine has gone for some time without, so all is well and good.

Except... except that it all seems so alien to the modern way of working with computers. For instance, the motherboard doesn't have SATA onboard, so I have a card to do that. Windows therefore can't install onto the new drives, despite the card installing BIOS features so that everything other than Windows knows what's going on. Instead, I have to install onto a plain IDE drive, install the SATA drivers onto that (which is painful in the extreme, because the driver disk doesn't install directly but instead tries to write a floppy image containing the installer), and then let Windows take control of the new drives. Another example: my keyboard and graphics tablet are USB, like anything sane these days, and are plugged into my monitor, which is a USB hub plugged into the computer. Windows Setup doesn't bother initialising the hub, so it's like there's no keyboard plugged into the machine until I go and find an old PS/2 one to use.

Admittedly I'm spoiled because most of the time I'm using a Mac, or a server running *nix. Both of these tend to just plug and play anything that is actually going to work with them in any way; no messing around there. (When I had to replace a drive in my server earlier this year, it took five minutes; by the time I'd found a way of logging in from the insanely set-up network in the data centre, it was already rebuilding the volume onto the drive quite happily, thank you very much.)

But this spoiling is the way of the future. It's the reason I'm able to blog while waiting for Windows to figure out what I have to do next; this is probably the first time I've installed Windows while having a second machine lying around that wasn't just a server or firewall. And, despite having just bought a brand new Samsung NC-10 (no link because their website is utter shit and I gave up looking), this will likely be the last time I install Windows. Ever. The next evolution of this machine will be either to take the two 1TB SATA drives out and put them in a Mac Pro, or to slap linux on the machine once more and be done with it. Microsoft loses: there's nothing running on that machine I cannot replace with similar software on other platforms. Usually it's better. It's almost never as annoying.

Except for one thing. I'm doing another install, at the same time as this, to get a working Windows system on my Mac again, under VMWare Fusion, on the off-chance that I need to test things.

I doubt it'll be all that long before my multimedia machine ceases to run Windows. I'm guessing that Creative Suite 5 will be out, at the latest, in early 2010; at that point I'll probably bite the bullet and both upgrade and get them to transfer the license to Mac. Windows will have been relegated.

The Open Rights Group

Published at

Wednesday 19th November, 2008

Tagged as

Rights
Internet
Freedom
ORG

The Open Rights Group (sometimes known by their un-Googlable acronym ORG) has turned three. Happy birthday, and congratulations!

To, erm, me. When the initial word went out in mid 2005, I pledged to become a founder member, and (beyond a short period where PayPal cancelled my subscription) I've been a supporter ever since. Not a particularly active one, admittedly.

Anyway, as you can see from their birthday review, they've achieved lots of really good things - getting the word out on digital rights issues, working with policy makers, and confronting police officers using clipboards and hand gestures. These kinds of challenges aren't going away, so please help out, or give financial support, or even both.

Interface magic

Published at

Sunday 21st September, 2008

Tagged as

Interfaces
Interaction
UI
Doom

The PlayStation 3 has a pretty good interface for playing DVDs, all things told: the key controls are immediately available from the controller, mostly using shoulder buttons as jogs, and I'd guess that most people who have got a PS3 and know what a DVD is have little difficulty using it. The problem arises with the magic.

Magic interfaces are one of those things that are a very good idea, but very difficulty to get exactly right: you want to take the thinking away from the user, so that stuff just works, but this means that if there's any significant mismatch between what you think people will want to happen and what they actually want, your users will start getting frustrated.

This is the area that Apple lives in, at least for the iPod and iPhone: don't think about how this thing works, just assume it will, and get stuck into it. By and large they do pretty well, and by and large Sony do okay with the PS3 also. The key magic that Sony have come up with (or at least the bit that I've noticed) is around what happens when you don't finish watching a film, but need to take the disc out. This is a pretty common requirement with a games machine, so it's not difficult to see why they've decided to make this simple: put the disc back in, and the PS3 will pick up where you left off. This would be an unambiguously good thing, except for a couple of points. Firstly, and less importantly, if you eject the disc at the end of the movie (or TV episode, or whatever), while the credits are running, then the next time you put the disc in it'll jump back to that point, and you have to navigate back to the menu - which some DVDs make much harder than others, because of their desire to show lots of copyright notices for countries I'm not resident in. (I suspect this doesn't happen in the US, and perhaps also not in Japan either.) If DVD authors would stop trying to persuade us that we're criminals, this would be a non-issue.

But the second issue was much more of a pain when I encountered it. Something I didn't notice for ages. Something which is almost never important, because it's simply not something you're likely to want to do. I started watching an episode of something, and noticed there was a commentary by the writer, which I thought might be interesting... and after about five minutes decided it wasn't. So I ducked out of playback back to the menu, and hit the 'play episode' button instead of the 'play with commentary'. And the PS3 helpfully picked up where I'd stopped, with the commentary track.

It took me perhaps ten minutes of turning the machine off and back on, ejecting the disc, and so forth, until I figured out that I could turn the commentary off by resetting the language options on the disc. (For some reason the audio tracks control was disabled for the disc.)

The question, of course, is: is this remotely important? I've been playing DVDs on the PS3 for about eight months, and I haven't run into this problem before now. Most people, I'd guess, don't listen to commentaries anyway; those that do probably only seldom back out once they've started. And most DVDs probably won't cause this problem, because they won't have the audio tracks disabled. So it isn't actually important at all.

The important point is that magic is by its nature opaque; if it weren't, it wouldn't be magic. And, like diesel engines and anything containing a class 4 laser, you can't take apart magic and figure out what isn't working. Instead, you have to build up a conceptual model of how it works inside, and figure out how to game it - which is doubly difficult because the point where the magic needs fixing is the point where the conceptual model that you already have doesn't match the magic in the first place. All your preconceptions go out of the window, and you have to think. Uh-oh.

There are two solutions to this when designing a system. One is not to care: this is the simple route, and has many advantages (including simpler testing). The other is to provide a way of turning the magic off; a kind of less magic switch. Personally I think that the former is a better choice: decide how your system will work, and trust to your own ability to make good decisions. Of course, you may get feedback that suggests you're better off removing the magic entirely, but options force people to think, which goes against the reason you wanted to introduce the magic in the first place.

Just use the best magic you can possibly manage.

Improvising makes me gulp

Published at

Thursday 11th September, 2008

Tagged as

Improvisation
Teaching
Terror
Seedcamp
Mentoring

Improvising makes me gulp; I get a visceral reaction before I go on stage. To be honest, this is a reaction I have to lots of similar situations: concerts where I was a soloist while back at school, plays, presenting, teaching. It's part of why I do it, although it doesn't feel like that at the time: adrenaline starts to rush through my body, and I want to throw up. But that passes, quickly, and then I'm on a high. I could probably sit down and rank the different things I do according to how great I feel doing them, and afterwards. Improvisation, and teaching improvisation, would come out at the top.

For the last few Barcamps I've been to I've taught impro for half an hour to whoever turns up; Barcamp Brighton 3, last weekend, was no exception. Best of all, we had a big enough crowd to play one of my favourite games to wrap up. I know it as The King Game, from Keith Johnstone (p237 of the Faber & Faber edition of Impro for Storytellers, if you have it), and it's particularly satisfying because you end up with a huge mound of bodies on the stage, all of whom are still paying attention to the scene.

Basically, people come in as servants, and the King orders them to commit suicide when (as inevitably happens) they get irritated. It's actually very hard to be a good servant, but some people actually try very hard to be bad (and in a quick session, it's generally more satisfying to play like this, admittedly breaking all the rules of good impro). Where it gets interesting is where people come up with strategies to avoid being ordered to die; at the weekend, someone came on as the King's daughter. (I think she actually lasted less time than the average.) The only time I've ever seen someone come on and survive was when I was doing this in Cambridge, preparing for a Whose Line Is It Anyway-style late-night show, and one of the women walked on and seduced the King. I suspect that works quite well as a strategy in real life, as well.

I've actually done much more of teaching improvisation than performing over the last couple of years (something I hope to change); but it does at least provide a (weak) segue to Seedcamp, where I'm a technical mentor this year. Looking over the entire list of mentors is a little daunting, but there are enough people on the list that I know from various things to make me feel I'll fit in. If you're one of this year's 22 finalists, I'll see you on Wednesday 17th, talking about How to Scale. According to Tom Coates, it has something to do with elephants.

Thoughts on Google Chrome

Published at

Tuesday 2nd September, 2008

Tagged as

Google
Web browser
Unwise predictions

First, let's start by saying that having a new web browser on the market to shake things up is never going to be a bad thing; and having something fresh from Ben Goodger is always going to be fun. The other people on the Chrome team sound smart as well, and it's clear that they're trying to solve a problem using a savvy blend of UI nous, applied research, and good software development. All that stuff about testing? Awesome. Oh, and using Scott McCloud for your promo literature is inspired.

But... am I really the only person who disagrees with their fundamental tenet? They claim that the majority of people's use of the web is as applications, not as web pages. I'm sure this is true of people inside Google (if nothing else because it can cause problems when they don't have high uptime), but I'm less than convinced for the general populace. It's certainly not true of me: of the tabs I have open in my browser right now, only seven fall within their broad definition of 'web applications' (actually three are films and one a list of audio clips, both of which I'd actually have watched or listened to by now if they'd instead been presented as something I could shunt onto my iPod; one is the Google Chrome comic itself, which I include as a web application mostly to deride the fact that it requires Javascript to function for absolutely no reason, giving absolutely no benefit to the user), compared to 41 'normal' pages (six items on shopping sites which use little or no Javascript; most of the rest are articles, main pages of sites with lots of articles, blogs or software sites). My remaining two tabs are one site that's down (and I can't remember what it is), and MySpace (which is anybody's guess how to classify). That's around 16% 'web applications', or a mere 6% if people would have done things properly in the first place.

Okay, so - disclaimers. I don't use web mail, which would definitely be an application, and would probably count for a reasonable amount of my usage online if I used it. I do use Facebook, sometimes, but I don't have it open anywhere right now; in fact, I almost never leave Facebook open, except for event information, which in my book is a web page not a web application. However I'm perfectly prepared to admit that I might be unusual. Freakish, even.

Of course, I'll benefit from a faster Javascript engine once they release on the Mac (on Windows I run Firefox with NoScript, so frankly I couldn't care one way or the other); and the process separation of tabs is smart (and, unlike others who've thought of it in the past, they've actually gone to the effort of doing it). But what I really want is genuine, resource-focussed, web-browsing features. Like, I don't know, proper video and audio support in the browser.

What's that you say, Lassie? Little Timmy's done what?.

However it's a huge deal to bring a new browser to market (or even to beta), so congratulations to the Google Chrome team (although... Chrome... really?). As they say, it's open source, so everyone can learn from each other. (Although of course strictly speaking this is Chris diBona wafflecrap, but that's for another post entirely.) But I'm not convinced this is on the critical path between us and jetpacks. Not even little ones.

Complexity increases

Published at: Tuesday 24th June, 2008

Or more accurately: complexity never decreases, both in the strict sense that if something’s O(n), it will always be O(n), and if you find a faster way of doing it, the complexity hasn’t changed, you’ve just been really smart (or you were particularly dumb to start off with).

But I also mean this in another way, with a more sloppy use of the word ‘complexity’: that just because you’ve done something before doesn’t necessarily mean it will be easier this time round. The complexity of the problem is the same, after all; the only real advantage you’ve got from having done it before is an existence proof. I think this is an important point that a lot of people miss. Then they act all surprised when building a new widget takes longer than they expected.

Complexity never decreases. You can represent this mathematically as:

which is what I’ve got on my t-shirt today at the second half of the O’Reilly Velocity Conference, which is all about performance and operations for internet-scale websites. And there’s some good stuff here - besides interesting conversations with vendors, and a couple of product launches, the very fact that this is happening, rather than being confined to what I’m sure a lot of my fellow delegates consider more “academic” arenas such as Usenix feels like a positive step forward.

Of course, some of this isn’t new. One of the conference chairs is Steve Souders, who has been banging the drum about front-end web performance techniques for a while, so it’s not surprising that we’re seeing a lot of that kind of approach being talked about. Since I follow this stuff pretty closely anyway, even over the last six months when I’ve been only flakily connected to the industry, I know much of this already; however it doesn’t mean it’s a bad thing: there will be people here who haven’t had it explained sufficiently for them yet, so they’ll go away with important new tools for improving the sites they work on.

Some of the things people are saying are older yet; and some are a bad sign. At least four speakers yesterday laid into the advertising technology industry, including Souders. However I note that they don’t appear to have actually sat down with the tech vendors, and they haven’t got any representatives speaking here. No matter what people think, performance problems related to putting ads on your pages aren’t always the fault of the tech vendors, and even when they are they’re open and often eager to talk to people about improving things. There’s a panel this afternoon on how to avoid performance problems with adverts, which I’m sure will have some interesting and useful techniques, but I’m equally sure some of them will date very rapidly, and very few if any will have been submitted to the tech vendors to make sure that they don’t have unintended side-effects. People are thinking about this, which is good; but they also have to talk about it, and not just at smallish conferences in San Francisco, but at things like Ad:Tech in New York. Hopefully this is the start of the right approach, though: advertising isn’t going away.

I’ll probably have more thoughts by the end of the day, but for now sessions are starting up again, so I’m going to go learn.

Plain Scaling

Published at

Tuesday 24th June, 2008

Tagged as

Scaling
Blog

Update: Yahoo! Pipes is no more, and I never wrote much on Plain Scaling, so I’ve folded the entries in here and shut it down.

The recent stuff on Wide Finder has been pretty fun, and I’m typing this during the Velocity conference on performance and operations, so it seems as good a time as any to announce a new blog I’ve created: Plain Scaling. I can’t guarantee it’ll always have lots of stuff in there, but my thoughts on scaling and performance will end up there. In particular, I’ve likely got some more stuff on WF-2 coming following conversations with some Sun guys at Velocity.

Of course, this is more of a pain to follow than just one blog, so I’ve set up a little thing using Yahoo! Pipes to bring them all into one RSS feed containing all my blog entries - at least in theory. Currently it won’t cope with the Atom feed generated from this blog, which seems to be a bug in Pipes; there’s definitely a blog post coming on that. If I can’t fix it using Pipes, I’ll write my own approach, but I really don’t want to.

Anyway. There you are.

Widefinder: Final Results

Published at

Tuesday 17th June, 2008

Tagged as

Scaling
Widefinder
Parallelism

By the end of my last chunk of work on WideFinder, I'd found a set of things to investigate to improve performance. All were helpful, one way or another.

Use fixed string searches either instead of (for referrer checking) or as well as (for page detection) regular expressions [Fredrik Lundh]
Pre-fetch the regular expression method outside the loop [Fredrik Lundh]
Snap my Python wrapper of dict to use a built-in [me]
Use temporary files instead of pipes to communicate between workers and master [Alex Morega]
Out of order processing [me]
Reducing concurrent memory usage to fit within core [me]
Use the CoolStack SPARC-optimised build of Python 2.5 [Tim Bray]

With smaller data sets, the first three together gave around a 10% improvement running on my dev machine; the last gave about 1.5% on the WF-2 machine over the 2.5 build I'd made myself; however I can't use it for the full run because it's 32 bit (the problem here is discussed below).

Initially I was running tests on my dev machine, using small amounts of data. There, out of order processing lost out slightly. It's bound to be a little slower in pure terms, because I had to use files instead of pipes for communication (I'm guessing the output was big enough to fill up the pipe; with some thought this could be fixed), but is more efficient with lots of workers across a large amount of data, because the run time variance increases. Additionally, the naive way of decreasing concurrent memory usage meant increasing the number of reduces; the alternative would increase the complexity of the user code, which I wanted to avoid. So there's probably some further improvements that can be made.

Anyway: my final result. I re-tested my two final versions, one with out-of-order processing and one not, on the 10m data sets before letting them both rip on the full data set. On the 10m line set, I was seeing up to a 25% improvement over my previous best run; for the whole lot, I saw only an 18% improvement: 34m15.76s. At this kind of scale, out of order processing, even with the file serialisation overhead, gives around a 10% speed improvement. (This is somewhat less than Mauricio Fernandez found doing pretty much the same thing in OCaml.)

This isn't even as good as the other Python implementation; for some reason I'm still getting nothing like efficient use out of the processor. Possibly having readers feeding the data to the processors over pipes might improve things here. I also still had to use the 64 bit version of Python, as Python's mmap doesn't support the offset parameter (there's a patch to allow it, which is private on the Python SourceForge site, sigh). In fact, it feels like every architectural optimisation I've tried to make has made things slower because of Python; the only things that have really speeded it up (beyond the initial parallelism) are the lower level optimisations that make the code less idiomatically Pythonic anyway.

It's possible that with some more thought and work, it would be possible to reduce this further; but I'd bet that Python will never get a run time below 15 minutes on WF-2 (although that would still put it in the same ballpark as the JVM-based implementations). At this point I'm mostly into optimising without being able to do the optimisations I want to, which seems fairly pointless; I've also sunk more time into this than I originally intended, so I'm going to stop there.

The code

User code (86 LOC)

I suspect that more code can be trimmed from here, particularly from the top() function, but it seems neater in many ways to leave it largely as the direct translation of Tim's original, with a few optimisations. Python is somewhat more verbose than Ruby; for this kind of job I find the readability about the same.

The only optimisation I'm unhappy with is the line that tests for a fixed string and then tests for a regular expression that starts with that fixed string; this does seem to work faster, but is crazily unreadable, and really needs a comment. Of course, regular expressions in general tend to cause readability problems on their own; it's notable that my thought on writing this was to think "hey, we could just get rid of the regular expression entirely and see what happens"—what happens is that we start treating URIs with '.' in them, such as /ongoing/When/200x/2007/06/17/IMGP5702.png, as pages, when they aren't, so all the results are wrong.

You can't do this easily by avoiding regular expressions entirely; Tim's URI layout means that /ongoing/When/200x/2007/06/17/ is an archive list page, rather than a genuine entry page, so you can't just check with a '.' somewhere in the URI (although this is actually slightly slower than using a regular expression anyway). However looking into this in detail brought up errors in the regular expression parsing as well: /ongoing/When/200x/2005/07/14/Atom-1.0 is a valid page URI, but the regex thinks it's an auxiliary file. There's also the unexpected /ongoing/When/200x/2005/04/18/Adobe-Macromedia?IWasEnlightenedBy=MossyBlog.com, which while not strictly within Tim's URI layout, is allowed to exist and be a page resource by his server configuration. Regular expressions, although powerful, are very difficult to craft correctly; this is made much harder by the problem being (essentially) an ad hoc one: I doubt Tim ever sat down and designed his URI layout with a thought to doing this kind of processing on it. (Even if he had, it would probably get caught out by something similar.)

import re, sys, parallel

def top(dct, num=10):
    keys = []
    last = None
    def sorter(k1,k2):
        if k2==None:
            return 1
        diff = cmp(dct[k1], dct[k2])
        if diff==0:
            return cmp(k2,k1)
        else:
            return diff
    for key in dct.keys():
        if sorter(key, last)>0:
            keys.append(key)
            keys.sort(sorter)
            if len(keys)>num:
                keys = keys[1:]
            last = keys[0]
    keys.reverse()
    return keys

hit_re = re.compile(r'^/ongoing/When/\d\d\dx/\d\d\d\d/\d\d/\d\d/[^ .]+$')
hit_re_search = hit_re.search
hit_str = "/ongoing/When/"
ref_str = '"http://www.tbray.org/ongoing/'

def report(label, hash, shrink = False):
    print "Top %s:" % label
    if shrink:
        fmt = " %9.1fM: %s"
    else:
        fmt = " %10d: %s"
    for key in top(hash):
        if len(key) > 60:
            pkey = key[0:60] + "..."
        else:
            pkey = key
        if shrink:
            print fmt % (hash[key] / 1024.0 / 1024.0, pkey)
        else:
            print fmt % (hash[key], pkey)
    print

def processor(lines, driver):
    u_hits = driver.get_accumulator()
    u_bytes = driver.get_accumulator()
    s404s = driver.get_accumulator()
    clients = driver.get_accumulator()
    refs = driver.get_accumulator()

    def record(client, u, bytes, ref):
        u_bytes[u] += bytes
        if hit_str in u and hit_re_search(u):
            u_hits[u] += 1
            clients[client] += 1
            if ref !='"-"' and not ref.startswith(ref_str):
                refs[ref[1:-1]] += 1 # lose the quotes

    for line in lines:
        f = line.split()
        if len(f)<11 or f[5]!='"GET':
            continue
        client, u, status, bytes, ref = f[0], f[6], f[8], f[9], f[10]
        if status == '200':
            try:
                b = int(bytes)
            except:
                b = 0
            record(client, u, b, ref)
        elif status == '304':
            record(client, u, 0, ref)
        elif status == '404':
            s404s[u] += 1
    return [u_hits, u_bytes, s404s, clients, refs]

(u_hits, u_bytes, s404s, clients, refs) = parallel.process(sys.argv[1], processor)

print "%i resources, %i 404s, %i clients\n" % (len(u_hits), len(s404s), len(clients))

report('URIs by hit', u_hits)
report('URIs by bytes', u_bytes, True)
report('404s', s404s)
report('client addresses', clients)
report('referrers', refs)

Supporting library code (134 LOC)

Perhaps 30 LOC here is logging and debugging, or could be removed by getting ridding of a layer or two of abstraction (I had lots of different driver types while working on this). This is actually my final running code: note that various things aren't needed any more (such as the chunksize parameter to ParallelDriver.process_chunk). This impedes readability a little, but hopefully it's still fairly obvious what's going on: we run J children, each of which subdivides its part of the data into a number of equal chunks (calculated based on the total memory we want to use, but calculated confusingly because I tried various different ways of doing things and evolved the code rather than, you know, thinking), and processes and reduces each one separately. The result per child gets pushed back over a pipe, and we run a final reduce per child in the parent process.

import os, mmap, string, cPickle, sys, collections, logging

logging.basicConfig(format="%(message)s")

class ParallelDriver:
    # chunksize only used to detect overflow back to start of previous chunk
    def process_chunk(self, processor, mm, worker_id, chunk_id, chunk_start, chunk_end, chunksize):
        start = chunk_start
        end = chunk_end
        if start>0:
            if mm[start]=='\n':
                start -= 1
            while mm[start]!='\n':
                start -= 1
            if mm[start]=='\n':
                start += 1
        # [start, end) ie don't include end, just like python slices
        mm.seek(start)
        class LineIter:
            def __init__(self, mm):
                self.mm = mm

            def __iter__(self):
                return self

            def next(self):
                c1 = self.mm.tell()
                l = self.mm.readline()
                c2 = self.mm.tell()
                if c2 > end or c1 == c2:
                    raise StopIteration
                return l

        it = LineIter(mm)
        result = processor(it, self)
        return result

    def get_accumulator(self):
        return collections.defaultdict(int)

class ParallelMmapFilesMaxMemDriver(ParallelDriver):
    def __init__(self, file):
        self.file = file

    def process(self, processor):
        # based on <http://www.cs.ucsd.edu/~sorourke/wf.pl>
        s = os.stat(self.file)
        f = open(self.file)
        j = os.environ.get('J', '8')
        j = int(j)
        maxmem = os.environ.get('MAXMEM', 24*1024*1024*1024)
        maxmem = int(maxmem)
        size = s.st_size
        if maxmem > size:
            maxmem = size
        chunksize = maxmem / j
        PAGE=16*1024
        if chunksize > PAGE:
            # round to pages
            chunksize = PAGE * chunksize / PAGE
        if chunksize < 1:
            chunksize = 1
        total_chunks = size / chunksize
        chunks_per_worker = float(total_chunks) / j
        commfiles = {}
        for i in range(0, j):
            commfile = os.tmpfile()
            pid = os.fork()
            if pid:
                commfiles[pid] = commfile
            else:
                pickle = cPickle.Pickler(commfile)
                result = None
                worker_start = int(i*chunks_per_worker) * chunksize
                worker_end = int((i+1)*chunks_per_worker) * chunksize
                if i==j-1:
                    worker_end = size
                chunks_for_this_worker = (worker_end - worker_start) / chunksize
                for chunk in range(0, chunks_for_this_worker):
                    chunk_start = worker_start + chunk*chunksize
                    if chunk_start >= size:
                        break
                    chunk_end = worker_start + (chunk + 1)*chunksize
                    if chunk==chunks_for_this_worker-1:
                        chunk_end = worker_end
                    mm = mmap.mmap(f.fileno(), size, mmap.MAP_SHARED, mmap.PROT_READ)
                    interim_result = self.process_chunk(processor, mm, i, chunk, chunk_start, chunk_end, chunksize)
                    mm.close()
                    if interim_result==None:
                        continue
                    if result==None:
                        result = interim_result
                    else:
                        for idx in range(0, len(interim_result)):
                            for key in interim_result[idx].keys():
                                result[idx][key] += interim_result[idx][key]
                pickle.dump(result)
                commfile.close()
                sys.exit(0)

        final = None
        for i in range(0, j):
            (pid, status) = os.wait()
            readf = commfiles[pid]
            readf.seek(0)
            unpickle = cPickle.Unpickler(readf)
            result = unpickle.load()
            if result==None:
                readf.close()
                continue
            if final==None:
                # first time through, set up final accumulators
                final = []
                for i in range(0, len(result)):
                    final.append(self.get_accumulator())
            for i in range(0, len(result)):
                for key in result[i].keys():
                    final[i][key] += result[i][key]
            readf.close()
        f.close()
        return final

def process(file, processor):
    d = ParallelMmapFilesMaxMemDriver(file)
    return d.process(processor)

Final thoughts

First off: functional languages. Let's use them more. Mauricio Fernandez's OCaml implementation is still the leader, and despite being a little more verbose than the Ruby original is still pretty damn readable (he's actually just announced an even faster one: 25% faster by using block rather than line-oriented I/O; the LOC count is creeping up with each optimisation he does, though). Functional languages require you to think in a different way, but when you're dealing with streams of data, why on earth would you not want to think like this? Better, OCaml gives you imperative and object-oriented language features as well, and seems to pack a solid standard library. I haven't learned a new language for a while, and I'm a little rusty on the functional languages I've been exposed to anyway; I guess OCaml is going to be my next.

Second off: compilers. Let's use them more as well. It's all very well to have an interpreted language where you have no build phase, and can just dive straight into fiddling with code, but I'm really not convinced this is a valid optimisation of the programming process. For one thing, if you're working with tests (and please, work with tests), my experience is that running them will vastly out-weigh any compile time; in particular, if you use an interpreted language, it is likely to completely mask the compilation time. There are enough good, high-level, compiled languages around that compilation doesn't put you on the wrong end of an abstraction trade-off (the way using assembler over C used to before everyone gave up writing assembler by hand).

I have an anecdote that I think further backs up my assertion that a compilation step isn't an impediment to programming. The only time I can remember writing a non-trivial program and having it work first time was with a compiled language. Not because of type safety, not because the compiler caught lots of foolish mistakes. What happened was I was using voice recognition software to control my computer, due to a very serious bout of RSI, so I spent a fair amount of time thinking about the problem before going near the computer. It took about the same amount of time overall as if I'd been able to type, and had started programming straight away—a couple of days total. But this way, I wasn't exploring the problem at the computer, just trying things out in the way I might with an interpreted language, particularly one with an interpreter shell. Programming is primarily about thinking: in many cases doing the thinking up front will take at most as long as sitting down and starting typing. Plus, you can do it at a whiteboard, which means you're standing up and so probably being more healthy, and you can also pretend you're on House, doing differential diagnosis of your problem space.

There are situations where you want to explore, of course; not where you have no idea how to shape your solution, but rather where you aren't sure about the behaviour of the systems you're building on. WF-2 has been mostly like that: much of my time was actually spent writing subtle variants of the parallel driver to test against each other, because I don't understand the effects of the T1 processor, ZFS, and so on, well enough. A lot of the remaining time was spent in debugging line splitting code, due to lack of up-front thought. Neither of which, as far as I'm concerned, is really getting to the point of WF-2. I suspect this is true of most people working on WF-2; you choose your approach, and it comes down to how fast your language goes, how smart you are, and how much time you spend profiling and optimising.

Anyway, you need to have a rapid prototyping environment to explore the systems you're working with, perhaps an interpreted language or one with a shell; and you want a final implementation environment, which may want to use a compiled language. For the best of both worlds, use a language with an interpreter and a native code compiler. (Perhaps unsurprisingly, OCaml has both.)

Where does this leave us with WF-2? None of my original three questions has been answered, although I certainly have learned other things by actually getting my hands dirty. It may be premature to call this, because people are still working on the problem, but I'm not aware of anyone trying a different approach, architecturally speaking, probably because straightforward data decomposition has got so close to the theoretical best case. The optimisations that we've seen work at this scale are helpful—but may not be trivial for the programmer-on-the-street to use, either because language support is sometimes flimsy, or because they'll be building on top of other people's libraries and frameworks. So it's good news that, besides automatic parallelisation of user code, it's possible to parallelise various common algorithms. GCC has parallel versions of various algorithms, there are various parallel libraries for Java, and we can expect other systems to follow. For obvious reasons there's lots of research in this space; check out a list of books on parallel algorithms. In particular check out the dates: this stuff has been around for a long time, waiting for us normal programmers to need it.

James Aylett: Recent diary entries

Rationale

"Deferred registration"?

Doing it in Django

Creating our models

Creating our views

Reparenting on registration/login

Warning users of unparented objects

Going further

The code

User code (86 LOC)

Supporting library code (134 LOC)

Final thoughts