Thought Palace

Brent “NetNewsWire” Simmons raises the idea of “an open protocol (and open source server) for syncing RSS/Atom subscriptions”:http://inessential.com/2010/02/08/idea_for_alternative_rss_syncing_system, that is, a way of keeping multiple local newsreader apps (like on a Mac and an iPhone) in sync with each other, so that they share the same set of subscribed feeds, and remember which articles have already been read. You can think of it as “IMAP for RSS”.

NetNewsWire already does this using Google Reader, and Apple’s PubSub framework (which is what Safari and Mail use) shares the read/unread state using MobileMe. But it would be nice to have an open protocol.

I have some experience with this, having implemented the sync system used by PubSub. It’s an interesting problem—you might think I would have just used Apple’s SyncServices, and it’s true that it would have worked great for the subscription list, but it doesn’t scale well to huge numbers of rapidly-changing “read/unread” flags.

I have two suggestions (which I would have made on Brent’s blog, except he doesn’t allow comments anymore.)

Yes, I’m still working on Ottoman (my append-only multiversion-concurrent storage library). As the code grows in size and complexity, so it grows in its resistance to being changed. But I just pushed my latest changes up to bitbucket.org. What’s new? …

ZSync is a new Mac/iPhone library that uses my BLIP P2P networking protocol.

As everyone knows who works in the pet-food industry (or computer software for that matter), it can be hard to start eating your own dogfood. Case in point: I just this week set Chrome to be my default browser, though I’ve been working on it for four months now.

Partly that’s because when I started in July the Mac version of Chrome was too immature; and partly it’s because a web browser is something you need to have running and working all the time—especially since the Chrome project’s bug tracker and code-review tool are web-based.

But Mac Chrome is quite stable enough to use now, and as I haven’t been doing much Chrome development on this MacBook Pro lately (it takes too long to compile compared to my souped-up Mac Pro) I’ve installed the latest dev-channel build and replaced Safari with it.

I’ve pushed a new update of my Ottoman storage library.

What’s new is the option to have individual additions to the dictionary written directly to disk, instead of being buffered in memory until you save a new version. This helps performance if you’re writing a ton of data all at once. And there’s a simple demo called PackDir that writes a ton of data all at once: it packs the contents of an entire directory tree into an Ottoman file, with keys being filenames and values being file contents.

To implement this I had to violate the lockless semantics a bit, because having multiple clients appending key/value pairs to the file at the same time would make it a lot harder to keep their revisions straight. So before being able to do any direct puts, you have to enter an [ugh] ExclusiveTransaction.

(Of course, the issues with locking don’t matter if the file is only being used by one process. Or even if there are multiple readers but only one writer, since the locks don’t interrupt readers.)

Farhad Manjoo writing in Slate about Google Wave:

The trouble is, everything you type into Wave is transmitted live, in real time—every keystroke was getting sent to Zach just as I hit it. This made me too self-conscious to get my thoughts across.

… Maybe I should just delete what I’d written and say, “Twitter works because it’s simple.” But I couldn’t do that, because Zach was watching me. He could see me struggling right now—he could see that I’d gotten myself stuck in a textual cul-de-sac and that I was desperately searching for a way out without looking foolish. Now I saw Zach beginning to type: “Don’t let the live-typing get you down!” The game was up; what was the point of making a point now? I ended my thought clumsily and then resolved never to attempt to say anything very deep on Wave.

The same thing happened seven years ago with the live-typing feature that I implemented in iChat 1.0 (which was only supported for Bonjour chats.) I thought it was an awesome idea, and I’d wanted to have it in a chat program since about 1997. But it turned out that, in actual use, people hated it, for exactly the [...]

I’ve pushed out a few updates to the Ottoman library today. These fix a couple of embarrassing bugs, and also add an API in regular ol’ Objective-C for those of you who aren’t into that funky “C++” stuff.

(The Cocoa stuff uses MYUtilities, so if you’re not already using that, please read the setup instructions.)

It’s got a moose! But then I found the ottoman with hanging files inside and it was even more perfect…

I thought this one was pretty damn stylish too:

Ottoman is a lightweight, reliable key-value store with multi-version concurrency control.

A key-value store is a persistent on-disk dictionary that maps arbitrary keys (usually short text strings) to arbitrary values (binary data of any length). There’s already a large and venerable family of libraries that do this, often referred to by the name “db”. Notable members include dbm, Berkeley DB, cdb and Tokyo Cabinet. What makes Ottoman different?

I know, three weeks ago I said I was building me a B-Tree. I did build it, even the parts I listed under “What’s next?” in that post, and it works. But it became apparent there was a more urgent need for a hash table, for work-related reasons, so I switched gears to build one of those on the same principles.

The biggest principle is Append-Only Storage, as described in the prior post. So I thought back to the simplest on-disk hash table I know of—Dan Bernstein’s CDB—which is very clever, but read-only. I implemented something similar, and then mashed in the CouchDB-like approach of incrementally appending only the modified sub-components.

Initially I made the file a series of key-value pairs, followed by the hash-table index as an array of {hash code, position} structures, each of which pointed to the position of the corresponding key and value. Very simple. To save changes, I’d write out the changed pairs, followed by a new copy of the index. The problem with that was that the index gets large as the number of records increases, so with a 100,000-record file, changing even one record would append almost a megabyte.

I had a brainstorm about how to [...]