Thought Palace

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?

So far, this blog’s main claim to fame has been as the #2-ranked Google hit for [apricot jam recipe]. But that’s no longer enough to sustain my extravagant lifestyle, so I’m following the next most obvious business opportunity: Elephant jokes! These were huge (the jokes) when I was a kid, but they seem to have been largely forgotten, which is a shame. I tested them out on my kids today, and they still work fine.

These jokes are, admittedly, about as unoriginal as my jam recipe. And the list was generated roughly the same way as the jam, by picking pre-existing collections, cleaning off the typos, and boiling them down a lot. In fact, I’ll lead off with an apricot joke:

Q: How is an elephant like an apricot?
A: They are both gray. Well, except the apricot.

Q: How can you tell if an elephant is in the refrigerator?
A: The door won’t shut.

Q: How can you tell if an elephant has been in the refrigerator earlier?
A: Footprints in the butter.

Q: How do you get an elephant into the fridge in the first place?
A: Open door; Insert elephant; Close door.

Q: How do you get a giraffe into the fridge?
A: Open door; Remove elephant; Insert giraffe; Close door.

I finally bit the bullet and upgraded to the latest WordPress from the seriously prehistoric version I used to run (I think it was 2.0.4 or something like that.) With the current attacks against older versions, it finally seemed like a worthwhile thing to waste an afternoon on. :-P

Almost everything should work more or less the same. I’ve taken the opportunity to move to a subdomain—jens.mooseyard.com—but the old URLs redirect. The theme is different, because my hacked-up, customized old theme probably wouldn’t have survived the upgrade intact. I can’t say I like this one better, but it’ll do.

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 [...]

Last year I wrote a series of blog posts about a peer-to-peer system called Cloudy that I was developing. I was going up the stack, from messaging to identity, but didn’t finish documenting all the layers I’d built. I mostly stopped working on Cloudy after I went back to gainful employment, but I keep thinking about this stuff.

“Lakitu”?

I’ve since heard about another unrelated project nicknamed Cloudy; and the whole term “cloud” has gotten so debased in the past year that it now stands for outsourcing to giant hidden server farms, which is the antithesis of what I stand for. So I’ve decided to use the name Lakitu instead. Nintendo fans will recognize Lakitu as a bit character in the Mario games—he’s a goggled turtle who rides a little one-seater cloud. This makes him an appropriate mascot for P2P technologies, I think.

[I’m sure Nintendo has a trademark on the character, but they don’t appear to have copyrighted the word “Lakitu”. He’s not even known by that name in Japan, where he’s called “ジュゲム” or “Jugem”. I have been unable to find out what “Lakitu” means or why they decided to use it in the English translation. I could also note threateningly [...]

The other day I took it into my head to implement a B+tree. Why? Because they sound neat, and I’ve done hardly any serious programming with trees in my career. (Someone, I think Buzz Andersen, once noted that there are two kinds of programmers: those who do think in terms of trees, and those who do everything with hash tables. I’m in the latter camp.)

And also because I’m a big fan of CouchDB, and really admire its elegant storage model. It’s an on-disk B-tree—no surprises there—but the file is append-only, which both makes it impervious to crash-related corruption, provides nearly lockless concurrency, and makes it easy to access earlier revisions.

[In a nutshell: Updated data values or tree nodes are appended to the file instead of overwriting the earlier versions. Since updating a node changes its location, its parent node needs to be updated too to point to the new location. This recurses up the tree, meaning any change ends up with a new root node written at the very end of the file. In fact, when you open the file you find the root by looking at the very end. Since no data is ever changed, once you open the [...]

AppleInsider reports on the iTunes 9 rumors:

“The social networking integration that we reported iTunes 9 would have seems to be part of a bigger social networking push by Apple,” the report states. “We’ve been informed that Apple has plans to tie iTunes 9 into a “Social” application that they plan to release in the future.”

This sounds like the kind of app (though separate from iTunes) that Jessica Kahn and I kept trying in vain to get Apple to build, circa 2003-2005. Maybe they’ll get some use out of our abandoned prototypes.

The report goes on to say that the new application would allow users to share their listening habits with friends [and] send music to friends”

Mike Estee and I had actually prototyped this in iChat in 2003, but the feature never got approved since there were so many more important things to add, like 3-way video conferencing. (Plus the fact that Apple execs turned white as a sheet if you said the words “send music” near them.)

Anyway, personal bitterness aside, I think it’s really amusing that Apple keeps shoving the kitchen sink into iTunes, since that has to be the single nastiest, hardest-to-extend codebase they have — it’s their last remaining [...]

iPhone playing cards by Meninos:

I got an iPhone 3GS yesterday (yes, it totally rules.) While setting up online account access for billing, AT&T had me enter a password.

There was one of those colored password-strength meters next to the text field, and it said the password I entered was “weak”. Alright, I changed it to add some commas and dashes.

Then I hit Submit, and was told that passwords can only contain letters and digits.

sigh.

New happy fun summer mix!