I recently wrote to bongo-devel about a problem in our store protocol: in the trunk version, some commands have a "query" parameter which is unspecified in our documentation. The reason it's unspecified is that it turns out that the parameter just gets passed through to CLucene, which as well as being something of a security issue also makes it more difficult to tell people how to use it.
In the experimental Store (coming soon to a server near you!) the CLucene index has been removed, and the query interface to it therefore doesn't exist any more. It's quite possible that CLucene will make a come-back, but the query interface is something I want to get rid of: for no better reason than it requires us to duplicate information from the SQL database to the Lucene index.
Because we need a parser for these queries which is simple, safe and isn't going to do nasty things with our memory allocator, I proposed a version of prefix notation / Polish notation, and have written some code which parses this into a tree structure stored in an array. The code is pretty straightforward, so I've documented the algorithm here - I'm sure it must be a known algorithm, but I've been unable to find any examples of anything similar.
In general, prefix notation isn't used as commonly as postfix notation. This is mainly because it's more efficient in terms of stack space to evaluate an expression in postfix notation, because the constants come before the operators and you can start calculating earlier. However, we're not evaluating an expression - we're going to turn it into SQL - so that isn't a benefit, and having the operators come first means we can find places to later store the constants simply.
The next step is to transform this parsed expression into something we can throw at SQLite. This is actually much easier said than done: for example, we have to be able to handle arbitrary properties on documents, which are stored in a separate table with a one-to-many relationship between the document and its properties.
The problem with that is that it's not that natural to say something like "give me rows from table A where there are rows in table B which relate to it and some of those rows contain X and Y". So, this may turn out to be something quite hard or even impossible to provide a general solution to if the logic is quite deeply nested - but ideally, I want all of that nastiness hidden from the client.
Some readers may be asking how the current Store does this. Effectively, it runs the query against the index with the properties it has at hand, and retrieves a list of Store guids of the documents which have those properties set. It then queries the SQL database for each individual guid to see if any of the properties there match the query also, and if so it outputs the match.
posted at: 16:12 | path: /bongo/hacking | permanent link to this entry
First things, we just went past r800 yesterday - a commit I bagged myself, woo! Sadly no pretty graphs to show for it, but I think we're back to a decent pace of commits again.
The work on the experimental branch of the Store is a good way through. This branch of Bongo builds reasonably cleanly, and works somewhat - you can deliver mail into it, and get mail out of it via IMAP. It's at the point now where it needs some decent testing while the final pieces are put together.
Somewhat incredibly, the code size is on the way down again - it's already about 1000 lines smaller, and might be double that by the time it's done. Although this is extremely dammaging to our project valuation on Ohloh (which currently stands at some .5 million), it's beneficial for Bongo ;)
What's good is that there is a decent turn of speed already, especially when dealing with large amounts of mail, and things seem to be relatively stable for me copying large chunks around. And this is without doing any performance work at all: I know for sure there is plenty of really low hanging fruit on this; for example, we don't cache SQL statements in a parsed state ready for re-use, and we don't do simultaneous access to the store which should be quite easy now. I haven't timed anything, but Thunderbird feels a lot snappier.
So if you want to do some testing, please grab the /svn/bongo/experiments/store-sqlite branch of Bongo, and run your favourite software against it - trying using it with imap or pop3, or whatever, and see what happens.
posted at: 16:57 | path: /bongo/hacking | permanent link to this entry
Sorry - another slightly technical post. This is yet again another visit to the subject of locking, which I briefly described the problems with a while ago, and then wrote some new code to help alleviate the problems.
One thing I didn't explain at all, looking back at those posts, is the different reasons for locking. We can simplify this down to two major reasons:
Those problems seem very similar, and indeed, our previous issues are mostly to do with the fact that those problems were conflated: the SQLite locking was used to ensure external consistency in the store. That's actually a really common - and often desirable - way of doing things. The way it works is you wrap all your SQL operations in an SQL transaction, and whether or not your operation (e.g., writing a file) succeeds stands or falls on whether or not the transaction succeeds. The database guarantees that when you use a transaction, you can make many alterations at once but no other database client gets an intermediate view of the partially-written data.
However, at this point, we run into an issue with SQLite. "Proper" SQL servers give you the ability to lock single tables, or even rows within tables, to help ensure that transactions succeed where-ever possible. SQLite doesn't give us that, it basically ensures consistency by locking the whole database. This makes the external consistency above suddenly very expensive to implement at the SQL level.
Now, surprisingly, there is also another set of locks within the store. At the moment, for example, collections are locked at a higher level when you read/write to them, because we also access other data - document contents on disk, the search index, etc. These locks are needed for the external consistency also, and almost make the SQL locks redundant.
So, my work on the store now is mainly to decouple the SQL-level locking from the provision of external consistency. We'll effectively only use the locks at that level specifically when we're reading/writing from the database to ensure that the data is written consistently when it matters (for example, allocating IDs) but not when it doesn't (for example, creating a document and then later adding the correct metadata to it). External consistency will then be provided by the higher-level locks which we already use.
posted at: 11:00 | path: /bongo/hacking | permanent link to this entry
I do love a good diagram, and I noticed that I have a number of Bongo-related diagrams stuck on my hard-drive. Most of them have seen action in a past blog post of mine, but my blog isn't really a Bongo development resource, and the ones which haven't yet been seen really ought to be a bit more widely available.
In general, though, programmers aren't great at drawing things and worse, updating diagrams in drawing programs is often tedious and time-consuming. So, I've committed some graphviz support into our build system which runs when you build the development documentation.
The first - and only - fruit of this endeavour is a UML-like diagram I've done to try to figure out what the Store's SQLite database structure should be. Behold (clicky for bigger):
I should at this point take a little bit of time to explain why I did this. I've decided that the SQLite usage in the store needs to be pretty much refactored, for a number of reasons. Amongst those is the fact that we store a binary blob within the tables which represents much of this data: some, like "mime_lines" in mail documents is completely hidden with this structure, other, "time_sent" appears in both this blob and as a column in a table.
So, job number one has basically been getting rid of this evil binary blob. This schema, then, isn't me really redesigning it per se - I'm simply pulling the structure out of this blob and putting it in tables, where it belongs.
I've also slightly denormalised the table a little. In our current database, event and mail attributes exist for all documents: and if the document isn't an event or mail, those fields are just empty. That's a bit of a waste, hence the one-to-one relations between "StoreObject" (which represents any object in a store - a mail item, a collection, etc.) and "MailDocument" et al.
The one big change I have made is the addition on the many-to-many "links" table. The purpose of this is simply to group together store objects. In our current store, we have a concept of "calendars" and "events", and events are linked into calendars rather than calendars being collections which hold events. Rather than having something specific to calendars, I've generalised this out. I'm not totally sure I like this as a way of representing calendars - I presume that it was done this way because collections can't be "typed" like a calendar document can - but it would also allow us to do stuff like linking conversations with events, so you could associate a meeting with the invitation conversation or something.
posted at: 12:48 | path: /bongo/hacking | permanent link to this entry
So, someone asked me the first good question about the vision for Bongo. To paraphrase, why am I against using the word groupware?
The easy historical answer is that it was almost the rallying call for Hula, and the groupware bad essay by jwz expressed this quite neatly in some ways. But that's not a very good 'why' answer.
For me, the difference is probably quite slight in some respects, but it comes down to who we design features for. Do we design them for people, or do we design them for groups / teams / organisations? In my opinion, the answer has to be that you design for individual people.
A good example of a feature which I don't think is person-oriented is "Read receipts" on e-mails. For those who haven't seen it - and I can't believe there are many - the idea is that by setting a read receipt on an e-mail, the person you e-mail sends you a signal back when they've opened the mail. In some software, that signal goes back automatically, in others a dialog comes up, sometimes it's a setting that controls the behaviour.
From having seen how some businesses operate with regards to receipts, I can't think of another feature which induces complete communication avoidance in people: I know people who are actively afraid of opening their e-mail lest they accidentally read something and inadvertantly tell someone they've read it, implying that they're "actioning" the e-mail. Total loss of control over their time. (You can make similar criticisms of Blackberries too, I believe)
The basic issue with giving too much visibility into someone else's data is that you get that Big Brother mentality, which if it doesn't actually exist will certainly exist in the minds of the more paranoid members of an organisation. It's almost like having your boss stand over your shoulder watching you work.
Are there examples of features I think ought to be in Bongo, but might not appear in "groupware"? Possibly. It seems to me that the aim of groupware generally seems to be to suck people in online, whereas software which is about communication, time management, etc., is actually about getting people offline. Putting in work-flow which manages more of people's work in a groupware system seems to me to be totally the wrong answer, particularly where you have to have "group acceptance" for things to work properly: "Oh, you changed the meeting online to 3pm? We agreed it would be 4pm at the last meeting...". Bongo would never assume that everyone else is using Bongo in the way that Exchange divides people between "Users" and "Everyone else".
There's no really easy way of expressing this, and I don't think that there is a bright-line test for this either. In many ways, Bongo will be groupware, or be usable in the same way, and it will have most of the same features. But I think the focus has to be on the individual, and providing tools for an individual to use, not attempting to mold a team into a specific set of processes.
Of course, that could all still be "groupware". We're just redefining what groupware means :)
posted at: 15:15 | path: /bongo/community | permanent link to this entry
Within this post, I mention the B-word (business) a few times. Don't let this put you off, please ;)
One thing I've noticed when meeting up with other free software users and developers is that a strikingly high proportion of them are involved in business in some way: either owner/managers of their own small business, or having a key role in one. Not most of them by any means, but a much higher proportion than any other group of people I meet (which perhaps says more about the company I keep - I don't know!). People who are involved with business will know that occasionally you do less day-to-day stuff and think more strategically - at least, I'm told that's what you're supposed to do - and the one I'm involved in is no exception. Part of this strategic thinking is revisiting the vision of the business(es).
So, I'm preparing for this meeting this evening, and I'm finding some of my tasks for this meeting pretty tough. "Blue sky thinking" is pretty hard, if you want to do it right: you can think up all sorts of ideas, but not matter how grand sounding they are, they can easily sound hollow and meaningless. As an example, Microsoft's vision statement is (or was, I can't find it on their site) "A computer in every home". Not, "To sell lots of copies of Windows" or "Provide powerful software to let users to more" - neither of those statements is as meaningful, emotional, or as motivational. And no matter what your opinion of Microsoft, they're coming pretty close to achieving their vision, at least for the western world.
There's plenty of other examples. You don't have to be a business, either - I'm told Tiger Woods has a vision statement. Again, not "A very good golfer", or "Win many tournaments", or even "Be the number one golfer in the world". His is (allegedly) "Be the best golfer ever". If that's not a vision, I don't know what is.
Getting back vaguely on topic. I'm finding these tasks tough, as I mentioned before. So, I'm thinking, maybe it would be easier to think about developing some for Bongo? It's easier in a way, because it's much more specific, so I got to thinking, and this is what I've come up with.
Vision statement: Be the recognised benchmark for personal collaborative software.
This is slightly wishy-washy, and could use improvement. What I mean by this is basically this: in the same way Word sets the benchmark for wordprocessing, and Apache does for web serving, Bongo should set the standard for collaboration, and be recognised by name for that. By "personal collaborative software" I'm kind of grasping around a little bit, because I don't want to say (and don't mean) "groupware". I mean personal tools which enable you to organise yourself and co-ordinate with others: power over your inbox, over your calendar, and your contacts. The word "personal" in there is important I think: we're centred around people.
Mission statement: The Project creates standards-based software for managing personal communications and organisational information, accessible online and from the desktop, aimed at small office / home office type users. Bongo is adaptable and versatile, while maintaining simplicity and usability, so people can use as many or as few of its features as they are interested in. The user experience is integrated, and doesn't offer simply the "lowest common denominator" or "most interoperable" functionality at the cost of user productivity. Bongo will continue to be completely free software.
This is more wordy, but is more about "this is how we will achieve our vision". Arguably, the scope of userbase I've offered above isn't enough to achieve the vision, but we can always revisit this again in the future :)
Culture and values: Bongo is the friendliest project on earth, and offers a uniquely accessible community of development. We aim for technical excellence and practicality while having fun developing the software.
We've actually said something a bit like this before: in the contributor agreement, I specifically wrote in from the beginning that friendliness was crucial. I'm not sure I needed to write it; I've never needed to remind people of it, and we have a community which has never suffered a flamewar, which is really great.
Now, none of the above is set in stone in any way - this is purely a personal exercise for me at the moment ;) But, I don't see why we can't adopt something like the above - I think it will tell people a lot more about what our project is trying to do. So, feel free to discuss this in the forums or on the mailing list, and if you know of any free software/open source projects who've already adopted a vision or mission statement, please let me know - I did search around and couldn't see anything.
posted at: 14:16 | path: /bongo/community | permanent link to this entry
Well, I'm sorry to announce that my prediction was about right: we didn't get into this year's Summer of Code. From what I've seen, this year was extremely competitive, and many good projects didn't get in.
It looks like only one project similar to us got in was OSAF/Chandler - they are a returning project, so that's not a huge surprise. They have some nice looking Javascript ideas which I don't think are very applicable to us, sadly, but who knows. They also have a natural language parsing idea which was something I wanted us to do, so I need to investigate what they have and what they're doing.. I hope they're doing it for international languages, but we'll see.
I'm also really happy to see that some of our sister projects at the Conservancy got in - Mercurial and OpenChange, as well as the Software Freedom Law Center itself. It's also nice to see that a number of projects aren't simply technical challenges, but software supporting people working on some of the toughest problems in the world: poverty, illness, education, that kind of thing.
Leslie offered feedback to projects, but unfortunately wasn't able to say too much to me: her response was roughly, "Another example of not enough space: good ideas, good docs, but we can't take everyone." In a way, I'm glad: I did everything I could to give Bongo the best chance, and one year our number will come up. Again, she asked that we apply again next year, and I have some ideas about how to improve our application even further: it will need more preparation, but I think we're almost there in terms of getting selected. We just need that final push to make us irresistable somehow :)
posted at: 22:33 | path: /bongo/community | permanent link to this entry
Since my last techie post on locks was appreciated and since I'm still crook, here comes another one. Again, the focus on making Thunderbird work better with Bongo was the main aim - after my locking changes, I found that we ran into a whole new set of problems: mostly, that the IMAP agent wasn't responding in a timely manner.
So, my next step was to address the progress reporting with a small new piece of code which sits in the various command loops inside the IMAP agent. Basically, as we spin around doing work, it checks to see when it last spoke to the IMAP agent, and if it was too long ago it responds again. I also found out that there was some code already in place which did similar, but it wasn't working because the socket wasn't being flushed: in non-techie terms, the responses were waiting on the server because the OS hadn't sent the data to the client. So, in those cases, the data is now sent, and things are happier.
The Tbird problems aren't totally done with yet - I do occasionally get errors still which I'm trying to track down - but it is much better. Certainly, copying large amounts of mail around is much better, and setting read/unread status works much more quickly. It's getting there as being actually usable long-term: I now have some tens of thousands of mails in my system, and it works, which is good news.
Going further with the "actually usable" thing, one thing I wanted to get some better information on was the performance of the Store in various places. From having read the code, I knew there were some places in the code which were obviously poorly performing: the algorithms in use are very naive, and there are much better ways of doing some things. But in order to know where to look, I decided I needed to instrument the Store a little bit. I've written a patch which I'll send along to -devel, but let me show you a little bit of output:
Command COPY took 0.726920 seconds.
- Out of band messages (0.000033)
- Starting document copy (0.000295)
- Files linked (0.033004)
- Processed doc (0.024436)
- Parse contents (0.602086)
- Index contents (0.049533)
- Commit transaction (0.016867)
- Finished processing (0.000047)
What happens is that every time a command is run, and during the command run, it pockets away little bits of data about the time performance so far. With enough bits of logging inside you get a reasonably granular idea of what's going on.
This example is of a particularly poor-performing COPY command. You may think you don't copy mail very often, but actually a lot of operations turn into COPY: deleting a mail is copying it to the Trash, filing a mail is copying it to the new folder, etc. (IMAP doesn't know about moving mail). This command took 0.7 seconds: most of the time it's quicker than that, but that's close to a mail per second. That's horrible performance.
If you'd have asked me before where all the time was going, I would have pointed the finger directly at CLucene. However, looking at the timings above, we can see it's not the main problem: far and away, accounting for 83% of the runtime, is actually the "Parse Contents" stage. The code at that point looks like this:
TCLog(client, "Processed doc");
errmsg = StoreProcessDocument(client, &info, collection, dstpath, 0);
if (errmsg) {
ccode = ConnWriteStr(client->conn, errmsg);
goto finish;
}
TCLog(client, "Parse contents");
(The log comes after the code it's measuring for technical reasons)
So, we can see that single StoreProcessDocument() call is actually the big deal. And what is that call doing? It's actually just filling in the SQLite database (but not writing to it - that happens later, and doesn't account for the speed). Re-generating data we already have is accounting for 4/5ths of the run-time cost. Ouch.
No, I don't have a patch which fixes COPY yet. But I'm thinking about it :)
posted at: 18:43 | path: /bongo/hacking | permanent link to this entry
First post after being "away" - my server was down for a little while too :/ No matter, I wasn't really in a position to blog anyway. Real life has interrupted for a bit, although I've managed a bit of hacking to distract myself.
So, we've had various troubles with IMAP. Somewhat hilariously, although I wrote a message to -devel about this, I did it from my trunk Bongo, which doesn't actually send e-mail since the smtpc code was committed (which I think is a configuration issue over here rather than a bug of Pat's). So, d'oh to that. I'll blog about this instead, then.
In one word - "Thunderbird". Tbird is a pretty smart IMAP client in many ways, and one of the smart things it does is use multiple IMAP connections to do many things at once: for example, doing things like mail filtering on your Inbox in the background while you're reading mails in another folder. The issue with doing many things at once is that you then enter the world of concurrency, which is relatively Hard.
To prevent concurrent tasks from corrupting each other, what I call "locks" are put in place. You can think of these a bit like signals in a railway shunting yard: you don't want to risk collision between trains, so you put signals on the track in such a way that trains obeying the signals will never meet. We have locks around access to store collections, access to the database, access to the text index, and access to internal data structures: all these locks are used to ensure access works consistently.
Following this metaphor, locks are great, but there are problems you want to avoid - one of which is "starvation". If a train waits for the green signal but only gets it rarely, it's effectively "starved of track" - similarly, a process waiting on a lock and not getting in there is starved of a resource - usually, some piece of data.
Starvation was effectively happening in our IMAP. When the IMAP agent is starved of access to a store object for too long, it returns an error to the IMAP client, and the IMAP client assumes that everything has failed and starts again. Sadly, with Tbird, starvation wasn't a rare occurance - it was effectively guaranteed. If Tbird was doing something like moving mail in one IMAP connection, that IMAP connection would work the Store quite hard and would effectively prevent the other IMAP connection from getting access unless by fluke of timing it was able to grab a lock in the short time the other process didn't hold it.
So, if we care about making sure that starvation doesn't occur, you need some system other than just basic signalling. You want a system to ensure some kind of basic fairness. Now, in computer science, you can write about "fairness" until the cows come home, but in this case it's probably good enough that a queue be put in place - that ensures that everyone gets a turn at some point.
It turned out that our existing locking system wasn't able to really do this. In fact, it was pretty complex, for another good reason: it has both "shared" and "exclusive" locks. The semaphore system works like signals in the train yard: only one process is allowed at a time. Let's say the code was written to a "look, but don't touch" rule: if the code isn't altering anything, you can have many of them looking at the same time without fear of corruption, which is good for performance. However, you can't do that with basic semaphores alone, you need to build that on top. In fact, you can look at the previous code and see how complex it is - a lot of that is machinery to allow shared locks, and mediate access when someone comes along and does want to touch - you have to get rid of all the look-ers first.
What I've written is along the lines of the original. There is a concept of shared and exclusive locks, and it attempts to mediate between those two. However, when the lock in unavailable, where the previous version waited a while and then gave up, this version puts the process in a queue and waits until access is possible. You might wonder why it needed a ground-up new version of locking - well, you don't need to be a coder to compare the original code to the new hotness, and you'll see mine is half the size, better commented and (in theory) more featureful - I tried bolting it on top of the old, it was buggy and awful.
How does it work? Well, it's relatively simple. Like the old system, there is a pool of locks, each of which is associated with a particular store resource that we want access to. Each lock is made up of two integers (readers, writer) and a queue. 'readers' is the number of processes who hold a shared lock, 'writer' is true if a process holds an exclusive lock. If 'writer' is false, you acquire and release a shared lock just by incrementing and decrementing 'readers'. If 'readers' is zero, 'writer' can be set to true to acquire a write lock.
What if those assumptions ('writer' is true or 'readers' is greater than zero) don't hold? That means someone else has the lock we want, and we're going to have to wait: we turn to the queue. We place a ticket in the queue, and wait for that ticket to be called. At the point the ticket is called, the lock is free and we can grab it for whatever purpose.
When does your ticket get called? Well, if you're a reader, you get called when either the writer holding the lock lets it go, or the reader in front of you in the queue got its shared lock. If you're a writer, it happens when all the readers have let go of their shared locks. Obviously, for the latter to happen, you have to ensure that readers don't skip in front of waiting writers: in fact, this turns out to be quite easy to code, because the logic is simple: when you come to acquire the lock (whether reader or writer), you look at the queue and if it's not empty, you join the back of it.
That's the idea of the code, anyway, and hopefully if you read through the code you'll find it follows that logic. It's already partly hooked into the store as of r680, and at least for me, I don't seem to get IMAP errors any more, which is great. I'm awaiting feedback from people like Pat who have huge mailboxes, though ;)
Like any locking system, it may well have serious bugs which cause the whole house of cards to fall down. Hopefully these will shake out pretty quickly: I'm using this revision on my system, so if there is a problem it should be obvious. Also, the interaction with the Store WATCH system is potentially dodgy at the moment. If this code works, there is a good amount of legacy code which can come away and again simplify things massively, which will be great - that was just a patch too far at this stage, though :)
posted at: 15:41 | path: /bongo/hacking | permanent link to this entry
So, this is the extra task I alluded to in my last blog post, but don't let that put you off!
I'd love to hear from people about how they use Bongo now, and how they want to use Bongo in the future. Especially, I'd like to hear from people who are watching this project but not participating more directly. So, to that end, I've kicked off a discussion on the forum: Where do you (want to) use Bongo?
There is no burning reason behind this, but I'd really like to have an idea of where people see the software being useful, and in what scenarios they'd think about deploying it. It's fine to say "I'm waiting for (X crucial feature)", and it's not likely to make me work on that crucial feature because they're different for everyone ;), but I'd really like to hear what kind of organisation you're in, or what tasks you'd want to use Bongo for, or why you're not happy with your current system.
Everyone can contribute to the forums, so no excuses! There are no right or wrong answers, and I imagine everyone will have a different reason. I've posted mine, so please post yours :)
posted at: 17:23 | path: /bongo/feedback | permanent link to this entry