Robey

Fanout queues in kestrel 1.2

2009-10-10T00:00:00-07:00

I bumped kestrel to version 1.2 this week and there are a few new features:

Queue files are loaded at startup time now, before opening the listening port.
You can explicitly abort an outstanding transcational GET by passing the /abort option (in the same way as /open or /close).
You can also peek at the current head item on a queue with /peek.
New options max_item_size and sync_journal.
Queues can be deleted with DELETE, which just forgets every item and erases any journal file (ie: fast & unrecoverable).
Some bugs in stats reporting were fixed.
Hopefully the documentation is much better. There’s a guide now.

Thanks to Clement, Zachary Kim, Blair Zajac, and Frederic Jean for submitting patches!

Special thanks to Justin Azoff, who’s responsible for the coolest new feature: fanout queues. My coworkers had been asking about for this feature for a while, and he posted a branch on github which added them in a way that makes sense to me, so I pulled it in with minor changes. Here’s how they work:

A fanout queue is a “parent” queue that has “children” queues. Whenever an item is added to the parent, the same item is added automatically to each child. The children each have their own journal files, and are essentially independent queues. An item removed from one child doesn’t affect any other children. In fact, you can even add items directly to a child if you want, bypassing the fanout. The primary distinction is that SETs to the parent are repeated to each child automatically.

A child queue is created automatically by referring to a queue with a + in its name. For example, a queue named “orders+audit” is considered to be a child of the “orders” queue. Once a child is created, it starts receiving new items immediately, but existing items in the parent are not copied over. (The child’s history begins now.) Fanout stops when a child is DELETEd.

Children use the same configuration as their parent, to make things easier. There’s no specific configuration for a child. Also, you can expect fanout queues to use more disk space and memory, since items are being copied around muliple times.

Hopefully the simplicity of the implementation makes it easy to reason about, which I think is more important than having a lot of clever tricks or magic.

Kestrel is, as always, hosted here: http://github.com/robey/kestrel

Follow-up on Scala on Android

2009-07-19T00:00:00-07:00

Dan Bornstein had a correction about my guesswork on how dx works, and I got permission to post it here. I said:

The end result is a little wasteful: even a tiny “hello world” app is 800K, probably because of that big ol' scala library. I suspect dex is proactively throwing away classes that I didn’t use, or it would be even bigger.

Dan replies:

Actually, dx doesn’t do any sort of tree-shaking. It’s just that I obsessed over making the dex format compact, and I got a bit of help on that front from mikef who designed a super-tight encoding for debug info (line numbers, local variables, etc.).

An uncompressed dex file is usually a little smaller (5% or so) than a corresponding (compressed) jar file, and for distribution a compressed dex file is generally about 40-45% the size of that.

For comparison on the distribution front, a compressed pack200 is still usually a bit better than a compressed dex file, weighing in at 30-35% of the original compressed jar size, a win which it gets by translating class files into a compressability-optimized intermediate format (doing stuff like collating immediate integer constants out of bytecode streams). The distinction here is that the dex format loses a bit of compressability, trading that for suitability to be directly executed.

We decided that the overhead (both in terms of code and runtime) of doing something like pack200 wasn’t worth it for us, at least not yet, because most apps don’t actually have that much code (much more likely to be heavy with media), though if people start regularly including language runtimes with their apps, we may want to revise.

Oh, a much more minor tidbit: You can pass dx options for the underlying JVM by prefixing them with “-J”, e.g. “-JXmx2000m” or what-have-you.

Actors talk for SDForum

2009-06-25T00:00:00-07:00

Last night I got to give a short talk at SDForum on “solving real problems with actors”, or more specifically, why I got interested in using scala actors, how they’re used in naggati and kestrel, and what I learned about where they’re useful and not. It was fun, even though I was a little nervous — they had me speaking after Carl Hewitt, one of the instigators of the actor model, and Frank Sommers, who’s writing a book about actors in scala.

Here are the slides: http://robey.lag.net/docs/robey-actors-sdforum.pdf

Thanks to everyone who came, and everyone who chatted afterwards! It was worth the drive. :)

Performance bug in kestrel 1.1

2009-05-18T00:00:00-07:00

If you’re using (or have tried to use) kestrel 1.1, you should upgrade to 1.1.1 (in github) for a performance fix.

Kestrel uses naggati, an actor-adapter for mina, to handle I/O and session management. Mina is a java library for handling thousands of open connections across NIO, and naggati converts mina events from java-style “listener method calls” to actor messages. I wrote all about mina & naggati in another article.

One feature added to naggati 0.6 was the ability to filter out mina events you didn’t care about. So if, for example, you didn’t care to receive an event message every time mina finished transmitting a block of data, you could filter out those messages:

IoHandlerActorAdapter.filter(session) -= classOf[MinaMessage.MessageSent]

Potentially this saves you a lot of unwanted actor messages that you'd just ignore anyway, causing fewer context switches. If the feature works correctly… aye, there’s the rub.

Naggati 0.6 would accidentally overwrite any filter changes that happened during an actor’s constructor. Kestrel’s session actors changed their filters in the constructor, and so their filter changes were lost. This caused kestrel actors to receive reams of unwanted messages like MessageSent, which by itself would only be a minor annoyance, and would have the same performance behavior as kestrel 1.0.

But, in actors, if you don’t pattern match on a message type, and you receive a message of that type, the message just sits in your queue forever. Long-lived connections would eventually have thousands of these unwanted MessageSent messages, which had to be linearly traversed to get to interesting messages. Scanning this queue on every I/O event eventually slowed down a long-lived session to a crawl — and it consumed memory in the process.

This bug is now fixed in naggati 0.7 and kestrel 1.1.1. Kudos to John Kalucki, who found the bug during his own stress tests and persevered when I couldn’t reproduce it myself.

Sidekick LX party

2009-05-15T00:00:00-07:00

When Nick, Evan and I stumbled out of “Star Trek” at the Metreon last night, it was 1am. Nick announced that there was some kind of party at the Mezzanine, and Jack was there, but it seemed pretty late, and my iPhone said there was a final bart train in 10 minutes, so I decided to clock out and go home. Nick and Evan went on to the club.

All 4 bart entrances on Market around Powell were gated up, though. (How exactly is one supposed to take the last bart train?) So I texted back that I was coming anyway and went to the Mezzanine in Mint Plaza. The place was set up like an LA bar in decline, with bouncers and a bunch of signs celebrating the “Sidekick LX”, which is apparently the name of the final Sidekick. I wasn’t sure I was at the right place and had to text Nick a bit before I decided to go in.

It was packed, even at 1am. There was no cover and it was an open bar filled with all kinds of kitchy decorations to celebrate the launch of Danger’s final phone in some sort of fake Metropolis-slash-amalgamation of all American cities (plus an English phone booth). One of the first things I witnessed was a set of fake “telephone poles” fall on top of partiers, light bulbs tinkling under our feet. I immediately took this as a metaphor for Danger.

There were no other Danger people there, and a very buxom woman wearing a Sidekick LX shirt wasn’t even sure what Danger might be. But never mind, the drinks were free, and DJ Jazzy Jeff was on stage. Another guy was “MC"ing, which appeared to mean that for several hours he had to walk around on stage shouting "What! What! DJ Jazzy Jeff in the house! Say what! Yeaaaaah!”

Everyone in the audience was taking pictures of each other and texting — using blackberries and iPhones. The only Sidekick I saw anywhere was in the hands of a drunk T-Mobile rep. But Twitter was represented! A looping movie behind the “MC” showed a bird flying around, and a Sidekick that opened up to reveal 3 apps: Facebook, Myspace (?!), and Twitter. Neet! Jack teased me a few times about the work I'd put into making a push-notification service for the Sidekick, which they were too disorganized to make use of for six months until we finally just threw the code away. I think the current Sidekick Twitter app just uses the same polling API as everyone else. Not a metaphor: That’s a good example of how poor Danger’s follow-through was.

This all could very well have been a dream or nightmare, or both combined. Certainly an event that combines Twitter, Danger, DJ Jazzy Jeff, and free drinks sounds highly improbable. But I must report it as I remember it, because that is the only way I know how.

Does anyone actually use JMX?

2009-03-29T00:00:00-07:00

In java 5 update 6, or 1.5.0_06, or whatever goofy release naming scheme they’re using now, there’s a cool replacement for jconsole called “visualvm”. (On my mac, it didn’t come with the installed java, but it can easily be downloaded.) It cleans up jconsole a little bit, and merges in some of the other tools. You can monitor, take heap snapshots, and even do an extremely skeletal form of profiling.

We were tinkering with hooking up some of our servers' stats to monitoring tools by exposing them as “mbeans” across JMX (Java Management Xtreme), and someone suggested that it would be nice if the server’s configuration could be viewed and edited through the same console interface. So during some of the more lucid moments of my two-week-long cold, I tried hooking up a JMX interface to configgy to do just that.

It hasn’t gone extremely well.

Java — and JMX in particular — has reams of documentation, but most of it assumes you are a drooling infant or recent PHP convert. Quite a lot of it assumes you want to write your own replacement for jconsole or visualvm. Very little of it is written for someone who may just want to hook up management tools to an existing app or server. This seems strange when java is used so heavily for servers.

I finally figured out that the best interface for a tree of config nodes was to create a tree of DynamicMBean objects which report their attributes as being the attributes on the config node. This works pretty well. The interface through visualvm won’t win any awards (and would make a UX person weep openly) but functions basically the way you expect and lets you discover and edit things in a straightforward way.

The fatal flaw in the UI is that if you add a new config item, visualvm doesn’t update the display tab to show the new attribute. (Jconsole behaves similarly.) At some level, it does appear to know to re-fetch the “mbeans” for the config tree, because I can see it doing that in the debugger. But it doesn’t use this information to update the display.

Looks like I have 2 options:

Register “mbeans” as the config nodes, and just live with the fact that they won’t be updated for new attributes. If you add a new attribute, you’ll have to disconnect visualvm and reconnect it to see everything.
Any time any config attribute changes, unregister and re-register the “mbeans” for config nodes. This makes visualvm destroy all open tabs to config nodes and rebuild the tree of config nodes in the left panel. You have to open the nodes back up to see the changes.

For now, I'm leaning toward #1 but both options make me sad. The punchline is this article I found while searching around on google, since I was convinced I must be doing it wrong:

http://forums.sun.com/thread.jspa?threadID=5218394

The thread summary seems to be: “We have documented a way for dynamic ‘mbeans’ to indicate that their attributes may change. We did not code our own tools to follow our own documentation so no existing tool uses this hint. Has our incompetence convinced you that you really want to do what you want to do, or are you eyeing that python book with a bit more interest now?”

Is there anyone out there that actually uses JMX for real?

Actors, Mina, and Naggati

2009-03-02T00:00:00-08:00

A few weeks ago, Jorge Ortiz gave a good talk at BASE about actors. I want to summarize a bit of that and explain why I wrote naggati, and why I think mina-plus-actors is a big deal.

The history

In the 90s, we server coders wrote daemons using the fork/exec process model. Apache still does it this way, though you can switch to threaded models in the current version.

Having a bunch of processes makes coordination difficult (you have to use shared memory, pipes, or something similar) but works well for a web server where there isn’t really any shared state except configuration, and you can just respawn new processes if the configuration changes.

For a chat server, you’d like a lot of shared state and communication between the various sessions. So in the late 90s (early 2000s on Linux), we started using threads. Each incoming connection spawns a new thread.

Each session is exactly one thread. Because threads all share the same memory space, communication between sessions is easy. You just have to make sure to use locks and condition variables, and to get the locking logic right — which can be tricky.

When you start to have a lot of sessions, the number of active threads begins to get a little unmanagable. At a past job, we had a daemon that would handle between 3000-4000 sessions this way. We couldn’t push it past that, because the OS wasn’t able to allocate stack space for more than about 4000 threads, and the task switching overhead was getting pretty ridiculous anyway.

Most sessions are blocked waiting for new data most of the time, so in the mid-2000s, server coders migrated to a thread-pool model.

Java even included a good thread pool library in java 5. In this model, you can have thousands of open sessions or socket connections, but you farm out work across a smaller pool of threads. Usually you have one or two threads in a socket poll() call (or Selector in java) across all the open sockets, and when incoming data arrives, it posts a work item into a queue, which gets handled by the next available thread from the pool.

Here’s where mina comes in

Mina takes this thread-pool pattern and pulls it out into a reusable library. You can register a socket with mina and get an IoSession object back. There’s a Selector running in its own thread, and when an I/O event happens on one of your registered sockets, mina calls an event method on your IoHandler, passing in the IoSession. These methods represent events like “new data has arrived” or “some data you sent has been successfully transmitted”, and they are called from within a thread pool, or other executor of your choosing.

The great thing mina adds to this mix is the idea of a “protocol decoder”. Instead of handling I/O events in your session and doing stateful buffering and protocol decoding there, mina lets you write a ProtocolFilter that receives incoming data as a byte buffer. This filter can do the buffering and decoding, and pass decoded objects on to the session. For example, a web server could have a decoder that takes byte buffers and generates HttpRequests.

The protocol decoding happens in a special set of I/O processor threads maintained by the mina library, so your IoHandler only gets events for fully decoded objects, and the handler code can be small and simple. In the web server example, an IoHandler would receive HttpRequest objects as events that run in a worker thread from a thread pool. The repsonse can be created and queued for writing, and then the event is over. Since the queued work items are small, discrete tasks that finish quickly, many active sessions can be handled across a much smaller number of threads.

There are only two big speedbumps with this system:

You’re using threads, so you need to be very careful about locking and all the other threading issues.
The protocol decoder is isolated into its own filter class, but it still has to be stateful and buffered. So it will still be ugly and gnarly.

Enter actors…

Actors solve problem 1. There are several good articles about actors out there, so I won’t belabor the point. With actors, you can write code in a way similar to writing threaded code, but all communication happens through message passing. The actor library promises that any actor will only be running in one thread at a time, so you can avoid using locks entirely if you want. Shared state can be passed around as “messages” that are immutable objects.

There’s a pretty clear one-to-one mapping between the events that mina would like to notify you about, and messages passed to an actor. It’s straightforward enough that I put it into naggati as a helper class called IoHandlerActorAdapter. It creates an IoHandler that handles every event by sending a corresponding message to the actor handling that session. (For example, the messageReceived method causes MinaMessage.MessageReceived to be sent.)

This line in kestrel is all that’s needed to tell mina to create a new actor for each incoming connection:

acceptor.setHandler(new IoHandlerActorAdapter(session => new KestrelHandler(session, config)))

…and naggati

Mina’s written in java, so they can’t do much about the way protocol filters need to be written, beyond giving you some tools to store state between calls and some base classes you can use to get implementations of some common bits (like reading a line). But scala’s syntax supports attaching code blocks to method calls as Function objects, so we can write code that looks sequential but is actually a series of continuations.

Naggati is a library that makes it easy to build protocol filters for mina 2.0 using this sequential style. A DSL allows you to write the decoder in sequence, but each decoding step is actually a state in a state machine, and when one step is finished decoding, it calls the code block for the next step.

As an example, let’s say there’s a simple protocol that sends packets. Each packet starts with an (ascii) count of the number of bytes in the packet, followed by a linefeed, and then the actual bytes. (This is how HTTP chunked encoding works.) We could write the decoder like this:

case class DataBlob(data: Array[Byte])

val decode = readLine { line =>
  readByteBuffer(line.toInt) { data =>
    state.out.write(DataBlob(data))
    End
  }
}
val decoder = new Decoder(decode)

The first line just defines a case class for the decoded objects we’re going to be throwing to an actor inside a MinaMessage.MessageReceived event.

The decode step is where it gets interesting. It just calls readLine with a block of code that will process that line when it’s read. readLine returns a Step object that contains that code block and some logic for reading bytes from mina’s buffers until a linefeed is found. Once a complete line has been read, readLine passes it to the saved code block.

In this example, that code block just contains another call (readByteBuffer) which returns a Step that reads a certain number of bytes and then passes them on to the attached code block. The nested code block takes that byte array and sends it back to mina as a decoded object, to be handed off to a session actor. End is a special state object that means decoding is complete, and the decoder should reset and start over at the beginning again.

We’ve written a tiny state machine here, which buffers data as it arrives and progresses through each state as the previous state is completed. But we didn’t have to write it that way. By passing code blocks around, we got to write a very simple, sequential description of the protocol without worrying about callbacks or buffers.

There are a couple of more in-depth examples in the naggati source code, including an ASN.1 tag decoder, and a simple HTTP request decoder. They’re too long to quote here, but they demonstrate things like using a value from one decoded state to help decode a later state. Kestrel is another good example, because it uses nagatti to decode memcache requests in a pretty small chunk of code.

With actors, mina, and naggati, I think the promise of a simple programming model for servers with thousands of connections is here. You can spend your time thinking about and coding up the actual logic of a server, and not worry so much about how to juggle all those sockets and threads.

Hopefully in this tiny space I’ve convinced you too.

Paramiko is on github now

2009-02-16T00:00:00-08:00

A story

A few years ago, at Danger, I wrote an SSH client for the Hiptop (or Sidekick) phone, which we gave away to developers for free as a demonstration of our API and the cool things you could do with it. Later, the developer program would be effectively shut down, and the app would be renamed “Terminal Client” and sold to hapless users for $10. But I didn’t know that yet.

The protocol implementation was awful. SSH protocol “documentation” was just a handful of poorly written RFC drafts that described things in seemingly random order. I hacked on some java code until I got it mostly functioning and left it at that. But it was so buggy and bare-bones that it often would only connect to certain OpenSSH daemon versions, and this eventually bothered me enough that I wanted to fix it.

Python was my favorite language at the time. The syntax is so simple and clean that I feel like I'm writing in pseudocode. It’s a very close match to “the way I think” when I'm trying to solve a problem, so there’s a very low impedance between what I think and what I type. If I'm trying to sketch out a rough draft of code, I usually do it in python as a prototype. And since the SSH protocol seemed like a difficult problem to me, I decided I should try to write an SSH library in python, as a prototype for doing it in java.

The basic idea was to use a thread to handle the protocol level of the socket, so that SSH’s packet windowing requests would get immediate responses, and supply an API to the client that looked just like a normal python file. Data should arrive, get handled by the protocol thread, and stuffed into a buffer so that a client read could get it. The read would trigger window feedback to the server, but the client could go do other stuff while waiting for data.

It worked beautifully. I called it paramiko as a dorky esperanto pun and released it, and after a while, to my moderate surprise, people were using it. I didn’t really anticipate that it would be useful for automating tasks for working with server machines and clusters, though it’s kind of obvious in retrospect.

Python’s thread model (the dreaded Global Interpreter Lock) isn’t awesome, but when threads are mostly blocked on I/O, they’re good enough. The bazaar team obsessed about performance, and helped find and solve some real bottlenecks, so that in the end, paramiko was slower than OpenSSH, but not by much.

Over time, the feature set exploded. Now it can be an SSH client or server, or an SFTP client or server, and has a few experimental SFTP features and a few made-up ones (just to see if they were useful). I wanted to try writing a standalone SFTP server based on it, for making little file-server sandboxes, but… I only have so much free time. :)

I did end up using what I learned to write “jaramiko”, a java library for SSH, and used that in later releases of the Sidekick SSH client, but it was never really as powerful or successful as paramiko. In retrospect, it’s obvious why: Java is not even remotely as expressive or concise as python, so most of the java code is boilerplate that obscures the real logic. It’s hard to keep up-to-date and maintain, much less add new features to.

What now?

I haven’t made a new release of paramiko since July. It feels like even longer than that. Really, to me, the library is finished. I'd like to fix any remaining bugs in it, but I don’t get many bug reports any more, and most of the mailing list support questions are answered by other users.

I don’t want the project to die. I just have to admit to myself that I'm not really taking a leading role in it anymore. So I've migrated the repository to git and put it on github here: github.com/robey/paramiko Anyone can fork it there and submit patches, and I’ll make regular releases as long as there are still bugs to fix, or new features that look cool.

Why git? I like bazaar better (see some previous rants on this blog) but the rest of the world has chosen git, and I don’t have the energy to keep fighting that fight. It’s also easier for me if I can use the same VCS everywhere. Keeping the project on github, in front of my face, will make it less likely to bitrot. At least, that’s my hope.

Scala on Android

2009-01-19T00:00:00-08:00

Chris DiBona gave me a free G-phone after an open-source talk last week (thanks!) with the admonishment that I write an app for it. I'm going to give it an effort, at least!

My first task was to figure out the scala-android build process, because that will make coding much easier. Turns out to be easier than the instructions I found online, so I thought I'd share.

You don’t have to use Eclipse like the instructions say. You can use the ant build file, but you have to modify it to find and compile using the scala compiler.

First, copy scala-compiler.jar and scala-library.jar out from your scala-home and into your android project folder. Since the compiler is only needed for building, and the library is the only one you’ll need installed, I made a folder for the compiler and put the library in libs/

$ mkdir scala-compiler
$ cp $SCALA_HOME/lib/scala-compiler.jar scala-compiler/
$ cp $SCALA_HOME/lib/scala-library.jar libs/

Second, edit build.xml and change the compile task to look like this:

<target name="compile" depends="dirs, resource-src, aidl">
    <javac encoding="ascii" target="1.5" debug="true" extdirs=""
           srcdir="${srcdir}" includes="**/*.java"
           destdir="${outdir-classes}"
           bootclasspath="${android-jar}">
        <classpath>
            <fileset dir="${external-libs}" includes="*.jar"/>
        </classpath>
    </javac>

    <taskdef resource="scala/tools/ant/antlib.xml"
             classpath="scala-compiler/scala-compiler.jar:${external-libs-ospath}/scala-library.jar" />
    <scalac force="changed" deprecation="on"
            srcdir="${srcdir}" includes="**/*.scala"
            destdir="${outdir-classes}"
            bootclasspath="${android-jar}">
        <classpath>
            <fileset dir="${external-libs}" includes="*.jar"/>
        </classpath>
    </scalac>
</target>

Third, you need to edit dx from the android toolkit so that it gets lots of memory. Uncomment the line with the java heap option and give it a lot of memory, like 512MB ("-Xmx=512m"). It needs this because dex is going to convert the entire scala library into dalvik. Without a lot of memory, it will run out of heap space.

The end result is a little wasteful: even a tiny “hello world” app is 800K, probably because of that big ol' scala library. I suspect dex is proactively throwing away classes that I didn’t use, or it would be even bigger.

Java SE6 on Leopard

2008-12-01T00:00:00-08:00

I could not find this anywhere on google in one place, but I pieced it together from clues Steve found by poring over a half dozen other blogs.

To get Java 6 to run on Leopard, you must go into /System/Library/Frameworks/JavaVM.framework/Versions and blow away the Current and CurrentJDK symlinks. Make them point to A:

$ sudo rm Current CurrentJDK
$ sudo ln -s A Current
$ sudo ln -s A CurrentJDK

Now launch the Java Preferences app and move the JDK order to the way you want it.

Setting the symlinks manually to 1.5 or 1.6 will make text apps work, but jconsole will blow chunks. It seems like the Java Preferences app changes “what’s in A” and then the symlinks make that work.

If you have the symlinks set up in the pre-Leopard way, the prefs app won’t fix them.

Sigh. Apple.

Scarling » Kestrel

2008-11-27T00:00:00-08:00

Ever since we deployed scarling in production, its name has progressed from being a stale joke to an annoyance. It started out as a test of porting starling to scala, but as features have been added and it’s been hardened by the real world, it has needed its own identity. I wanted to stay with the bird theme, because I think it’s cute, so after spending several days mulling over possible new names, I've settled on “kestrel”.

Poof! And so it is. What was scarling is now kestrel. I've updated the code and github page: http://github.com/robey/kestrel/

Meanwhile, over the last couple of weeks, I've added three big features.

Big Queues

One of the working assumptions of kestrel is that queues are normally empty. A healthy system has more consumers than producers, so new work items are gobbled up as fast as they come in, and we can usually keep all queued items in memory, for the rare times there are any items queued at all.

However, you may have an event — like a realigning US presidential election — which causes brief “high traffic” bursts that temporarily overwhelm consumers. It became clear at Twitter that we needed to have a graceful soft-landing for these bursts, to prevent kestrel from running out of memory or needing manual intervention.

In kestrel’s git-head, now, when a queue passes a memory limit (128MB by default), that queue will be dropped into what I call “read-behind mode”. New items are added to the queue by writing them into the queue’s journal, but not kept around in memory. Instead, we just keep the first 128MB of the queue head in memory, and track a second file pointer to our journal. As items are read from the queue, this new file pointer replays the journal from behind, filling the queue back up until it either catches up with the write pointer or fills up 128MB again.

In effect, we’re keeping a window of the head of the queue in memory, and using the journal as a disk store for the rest. It nicely caps memory consumption and the added disk I/O can be amortized out across consumers.

You probably don’t want to let an out-of-control queue grow forever because it will fill up your disk, but this should make it cope well with short-term spikes and give you one less thing to worry about when the snake is trying to swallow the pig.

Blocking fetches

Something that’s bothered me about using the memcache protocol is that there’s no way for a consumer to do a blocking fetch from a queue. If an item is immediately available, kestrel will give it to you. If not, you’ll immediately get a “nothing” response. Since, like I just said above, you always want to have more consumers/workers than work items, these consumers swarm all over the cluster, asking for work and immediately being sent away empty-handed. Just to keep them from going crazy, we have ruby client code that looks something like this:

while !(response = QUEUE.get(queue_name))
  sleep 0.25
end

Good grief. If we’re going to let the workers take a nap on the job, we could at least make it happen while blocking on a queue fetch.

So I did a little sneaky thing with queue names in the memcache “get” command by letting clients add options to the end, separated by slashes. Slashes aren’t allowed in filenames anyway so they were never valid in queue names. Then I made a timeout option, so a client can ask to block for work for some amount of time:

while !(response = QUEUE.get("<b>#{queue_name}/t=250</b>")); end

The “t=250” option means “if there’s nothing in the queue right now, I'm willing to wait up to 250 milliseconds for something to arrive”. After that timeout, if there’s still nothing, kestrel will answer with the usual empty-response. It’s important here to make sure that your memcache client is set to have a read-timeout larger than the timeout you send in the “get” request.

This was the easiest thing to implement after I worked out how. Each queue just has a kernel-style wait-list of clients attached to it. If a client makes a timeout-style “get” request, and the queue is empty, we just put the client on the wait-list and the client’s actor does a receiveWithin(timeout) to wait for a message saying something new has arrived. When items are put on the queue, the first wait-list client is removed from the wait-list and notified.

The ManyClients load test exercises this by having 100 (or 500) clients pile on to a queue with blocking fetches while a single producer slowly trickles out data. It seems to work like a charm.

Reliable Fetch

Writing something into a queue is pretty reliable. The client does a “set” operation, and if it worked, kestrel responds “STORED”. Naturally, it only sends that response after the item has been written into the queue’s journal file. The “STORED” response means kestrel has taken responsibility for the item.

Fetching from a queue is not such a happy story. When kestrel sends an item to a client, it will never get an acknowledgement or confirmation, and has to blithely assume that the client got all the data okay and took responsibility for it. If a client loses its connection during the data transfer, or crashes right after receiving a work item, that item is gone forever.

So I added an “open” option to “get” which opens a tentative fetch on a queue. If an item is available, kestrel will remove it from the queue and send it to the client as usual. But it will also set the item aside and prepare to “un-get” it if the client disconnects without confirming it. So a tentative fetch is started with:

QUEUE.get("#{queue_name}/open")

and confirmed with:

QUEUE.get("#{queue_name}/close")

which returns nothing. For efficiency, you can also confirm a previous fetch and get the next item in one operation (avoiding an extra round-trip):

QUEUE.get("#{queue_name}/close/open")

Each client connection may only have one outstanding tentative fetch, and if a connection is dropped, any tentatively-fetched item will be put back on the head of the queue and given to the next available consumer.

I want to briefly make a distinction here between confirming that a client receives an enqueued item and confirming that some useful work was done on it. Kestrel can really only concern itself with the former. As a good queue server, it would like confirmation that a client has accepted responsibility for an item before that item is erased from the queue and journal. But it has no way of confirming that “something useful” was done with that item. You still need to write careful client code to ensure that an item isn’t lost after it’s received.

Using reliable fetch means you are protected from losing items, at the expense of potentially receiving duplicates — that’s the trade-off. A client may successfully handle a fetched item but crash before confirming it to kestrel, and the item may then be given to another client. I think this is a good trade-off, though. If you know you may handle some items twice, you can design your system so that duplicate work is harmless — versus the case where you may lose items and don’t have any recourse.

Summary

With these three new features, you should be able to survive large bursts of traffic more easily (with big queues), allow incoming items to be processed immediately by the next available consumer (with blocking fetches), and deliver items reliably even to flaky consumers (with reliable fetch). They expanded the code size 50%, from 1000 lines to 1500, but I think they were worth it, because they solve several limitations inherited from starling.

Coder Dvorak

2008-09-20T00:00:00-07:00

Some kind of bug was spreading around at work a few weeks ago and got me interested in alternate keyboard layouts again. Several of my co-workers use Dvorak, which never really interested me. But Evan pointed me to a page on “programmer dvorak” and suddenly my interest was piqued.

Dvorak rearranges the letter keys so that letters used more frequently in english are closer to the home row, and Progammer dvorak continues that concept into the symbol keys and attempts to rearrange them so that symbols frequently used in code are close at hand. The stroke of genius that makes it worthwhile is that he moves the number keys up to shifted positions, making space for more non-shifted symbols. I don’t hit the number 8 nearly as much as I hit underline, plus, or the “squiggly braces”.

Unfortunately, he then moves the number keys into a jumbled-up order so that they’re no longer in incrementing or any other intuitive order. I'm not sure why. (I later found out that this is apparently the original Dvorak number layout which nobody uses.)

Being the type of person I am, I decided I could do better, so I constructed a “coder dvorak” based on this idea, but keeping the number keys in order, and moving symbols to positions that make sense for a modern language. (There’s not much need to keep $ nearby unless you still do a lot of perl.)

I grouped the symbol keys into four loose categories, the first being “paired” (like parentheses), and the other three ordered from “most used” to “least used”. Then after trying it out for a few days, I re-assigned several symbols because I made some mistakes in guessing frequency of use — both period and slash were used way more than i thought, for example.

The layout I finally adopted, unchanged for a month now, is below:

I used the awesome Ukelele to create the Mac keyboard layout file, which can just be dropped into ~/Library/Keyboard Layouts/ in your home folder.

A lot of the design came from whiskey-inspired ideas from Britt and Evan. Originally, I was going to put the paired keys on symmetric sides of the keyboard, like having “(” on 5 and “)” on 7, which we all convinced ourselves made sense. But after trying that for a day, it was clearly wrong. It turns out that by the time my fingers jump the two rows from the home row to the number row, the finger I use to hit a key isn’t 100% deterministic. It depends on what else I've been typing. The home row “bindings” don’t hold as tightly up there. So it was as if I'd put the symmetric keys randomly apart from each other.

Some placements worked out better than I expected. The underline key (used heavily in ruby, python, and scala) almost couldn’t be in a more accessible place. Similarly, period and slash ended up in great places, and putting bang (!) and question (?) on the same key is strangely intuitive.

The thing I have the most trouble with, after about 6 weeks, is the Dvorak letter layout.

1. Dvorak is right-handed-centric.

Great, because I'm right-handed. But it’s not that simple! Look at your QWERTY keyboard: more letters are centered around the left hand than the right. QWERTY even devotes one of the 8 precious home-row positions to semi-colon on the right hand — hardly a frequently used english key! (Most english writers have never even learned correct usage of the semi-colon.)

I never realized, until typing on Dvorak, that QWERTY has made my left hand a much stronger typer. Dvorak relies on the right hand a lot more, and I was in the strange position of having my right hand get tired pretty quickly for the first couple of weeks.

2. English has a different distribution than a programming language.

It mostly works, but there are a few cases that sting. Words like “if” and “while” appear all the time in code, but are difficult to type in Dvorak because F and W are in awkward places. A real coder layout would probably reorganize the keys to match actual words used in programming languages, but I chickened out. It seemed like a very large gratuitous change.

The worst is “I” versus “U”. “I” is used all over the place in coding. It’s also the most common loop variable name. So it should have been on the home row instead of “U”, which is rarely used.

Anyway…

I'm liking it so far. I may change my mind in another month or so, because I'm pretty hard to please, but it’s working well for now.

The keyboard layout can be downloaded here: http://www.lag.net/robey/cdv/

OS X Leopard JNI Link Error

2008-09-02T00:00:00-07:00

I just spent a long time tracking this down, and nobody else on google had ever reported a solution. So I'm posting this so the next person wit h this problem can find this post.

If you see this error when linking something in JNI:

$ gcc -dynamiclib -o libDirectorySyncer.jnilib target/c/dsync.o -framework JavaVM
ld: framework not found JavaVM

it’s because leopard has messed up your JDK folder:

$ ls -l /System/Library/Frameworks/JavaVM.framework/Versions/Current
/System/Library/Frameworks/JavaVM.framework/Versions/Current@ -> 1.6.0

Wrong! It needs to be pointing to “A”. No idea why.

$ cd /System/Library/Frameworks/JavaVM.framework/Versions/
$ sudo rm Current
$ sudo ln -s A Current

That will fix it. Yay!

CJC Prime Number Sieve

2008-08-27T00:00:00-07:00

Apologies in advance. This is probably the geekiest post I've ever done.

To get an SSH client working — with a reasonable response time — on a 200mhz ARM chip a few years ago, I had to optimize some crazy things. One of those things was the generation of prime numbers, which are needed to create new public keys.

You may have heard that it’s very difficult to factor large numbers. This is true, but it’s actually a lot easier to determine whether a large number is “probably prime”. Most prime number generators create a random number from a secure source of entropy and then run it through a Miller-Rabin test, which can identify composite (non-prime) numbers. If the test doesn’t prove that a number is composite, then there’s at least a ¾ chance that it’s prime. You can perform the test multiple times to improve those odds. More info here: Miller-Rabin test

The Miller-Rabin test can be pretty time consuming, though, and since you may need to run it against many random numbers before you’ll find one that’s prime, it would be nice to weed out obvious composites beforehand. For example, you wouldn’t want to test an even number since that’s obviously divisible by 2. So here’s a shortcut I came up with that I call the “CJC prime number sieve”.

The Sum-of-Digits Trick

I thought I would be able to gloss over this part of the explanation by throwing out a few links and saying “go read about the (name) theorem!” But a google search only turns up some anecdotal descriptions, and wikipedia barely devotes an entire sentence to it (here: Modular Arithmetic).

There’s a fairly well-known trick for finding out if a number is divisible by 3: add the digits, and if the sum of the digits is divisible by 3, so is the original number. If it’s not, the original number is not. For example, 4401 is divisible by 3 because 4 + 4 + 0 + 1 = 9, and 9 is divisible by 3. 512 is not, because 5 + 1 + 2 = 8, and 8 is not divisible by 3. (This trick also works for 11 and 9 but these are emo numbers that don’t get as much attention.)

So why does this work? As you can guess from the wikipedia link above, it has to do with modular arithmetic. In (mod k) space, the only numbers that exist are integers from 0 to k – 1. Coders recognize this as being the way all int math works on a computer: a byte can represent a number “mod 256”. It turns out that in (mod k) space, you can cancel out a factor if that factor is relatively prime to k.

Say what? Okay, “relatively prime” just means two numbers don’t share any factors. 9 and 10 are relatively prime because 10 = 2 5, and 9 = 3 3. But 4 and 6 aren’t, because they share the factor 2.

Sooo… since:

20 = 2 (mod 9)

and 20 is relatively prime to 9, you can figure out 40 mod 9 by factoring out the 20, and replacing it with its equivalent in (mod 9) space, 2:

40 = 2 * 20
2 * 20 = 2 * 2 = 4 (mod 9)

The reason this works well for finding numbers divisible by 3 is that:

4401 = (4 * 1000) + (4 * 100) + (0 * 10) + 1

and:

10 = 1 (mod 3)

Aha! So factoring all the 10s out and replacing them with 1s gives us:

(4 * 1000) + (4 * 100) + (0 * 10) + 1 (mod 3)
(4 * 1) + (4 * 1) + (0 * 1) + 1 (mod 3)
4 + 4 + 0 + 1 (mod 3)
9 (mod 3)
0 (mod 3)

and any number that’s 0 in (mod 3) is of course divisible by 3.

The reason 9 and 11 work is that 10 mod 9 = 1, and 10 mod 11 = -1. (The -1 means you have to do alternate add/subtracts instead of just summing the di gits, but it’s not worth obsessing over in this article.)

Making a sieve

So that’s exciting… if you do a lot of dividing by 3. But how does this help discover primes?

Well if computers worked in base 10 instead of 2, we'd now have a pretty fast way of determining if a really large number were divisible by 3. And I hope you won’t think I'm being pedantic if I point out here that if you make up a random number, it has about 1/3 chance of being divisible by 3. :)

Let’s say instead of working in base 10, we were working in some other base B that was relatively prime to a lot of interesting numbers. Ideally we'd like to be in a base B such that

B = 1 (mod n)

for as many n as possible. One nice coincidence is that

256 =
255 + 1 =
(3 * 5 * 17) + 1

256 = 1 (mod 3) and
256 = 1 (mod 5) and
256 = 1 (mod 17)

That means that in base 256, summing the digits will tell you quickly if 3, 5, or 17 is a factor. Summing the base-256 digits of a number also goes by the name “adding the bytes in the binary representation”. It actually helps a lot, as you can see from timings at the end of this article.

If we’re willing to leave powers of 2, though, we can do better. It just so happens that we can construct a base that’s relatively prime to a handful of small primes, yet is close to a power of 2. The key is noticing that, in the 256 case above, multiplying a few primes together and then adding 1 created a number that was both relatively prime to all those primes, and was equal to 1 in each of the primes' (mod k) spaces.

Think of it this way. If A, B, and C are all prime, then A B C will equal 0 in (mod A) because it’s a multiple of A. Same goes for B and C for the same reason. Adding 1 makes it equal 1 in all three (mod k) as long as the primes are all greater than 2. And that also means the resulting number is no longer a multiple of A, B, or C, which makes our new number relatively prime to them. In short, we can construct a base that’s relatively prime to a set of primes, and is equal to 1 in each of the primes' “mod spaces”, by just multiplying the primes together and adding 1.

We want the base to be close to a power of 2 to preserve our entropy source. If we grab 8 bits (0 – 255) from a secure random pool, but we want a smal ler base like 250, we have two choices. We can mod the random byte (rand % 250) to wrap into range, or we can just discard an d retry when we get a byte that’s out of our preferred range. If we mod-and-wrap, though, we’re giving more weight to results in the wrapped part — numbers like 1 are going to be more common because both 1 and 251 will mod-wrap to them. That ruins the “secure” part of our randomness, so we need to go with the discard option. And if we have to discard some bytes, we'd like to pick ranges to minimize the chance of a byte being discarded, which means choosing ranges that are as close to a power-of-2 range as possible.

One nice possibility is:

3 * 5 * 7 * 11 * 13 * 17 * 19**2 * 23 + 1 = 2119382266 = 0x7e5334fa

That’s a base that covers 98.7% of the 31-bit range, so it won’t cause many random digits to be discarded, and it’s relatively prime to the first 8 primes excluding 2. (We can ensure that a number isn’t divisible by 2 by just setting its lowest bit to 1 — a bonus for working in base 2!)

Let’s Go!

At this point, the code should just write itself. To generate a 1024-bit random prime, we need to figure out how many “digits” that would be in a base -2119382266 number, and what the range would be on the highest digit. We’ll lose some of the 1024-bit range because our new base doesn’t map exactly to the desired range, but we’ll never lose more than a single bit’s worth. (There’s probably a fancy proof for this, but if you think about it, you can reason it out pretty quickly in your head.) You already lose 2 bits for any prime, because you need to set the high bit to ensure a prime number of the desired size, and you need to set the low bit to ensure an odd number as mentioned above.

For a 1024-bit prime, that means a 34-digit number with the highest digit set to 2. For a 2048-bit prime, it’s a 67-digit number with the highest digit between 5 and 8 inclusive. (You can play around with other sizes by calling computeParams in the attached code.)

We can then generate, for a 1024-bit prime, 33 “digits” of 32-bit machine words, masking off the high bit and retrying any time we get a “digit” bigger than (base – 1). Set the high “digit” to 2 (or select a digit at random for other bit choices) and we’re done.

A quick shortcut here: Normally we should sum the digits, and then find the mod of that sum against each of our 8 primes. However, we already have a really convenient thing here: base – 1 is a multiple of all of 8 primes (by design), so we can mod the sum by (base – 1) as we add, and not lose any information, keeping the sum small enough to fit into a 32-bit word.

After summing, a few small mod operations tell us if the generated number is divisible by 3, 5, 7, 11, 13, 17, 19, or 23. If it is, we can loop back and generate another number immediately, skipping the Miller-Rabin prime test. If it passes, we still dump it into Miller-Rabin for final verification — the sum check just lets us quickly discard any simple composites.

Code and Results

I wrote a proof-of-concept in scala, and hosted it in git here:

git clone http://www.lag.net/robey/code/cjc/

It includes an implementation of CJC in base 2119382266, alongside a prime number generator that just uses the standard Miller-Rabin prime test by itself, and a variant of the standard M-R sieve that checks the base-256 primes (3, 5, 17) first.

The test code generates 5 primes from each algorithm, using a random number seed given on the command line. (By the way, never use the built-in random number generator like this code does! Use a secure one. I used a seeded generator so the results would be repeatable, which is exactly what you don’t want in the real world.) I've posted my own results in a chart below: Using the base-256 check alone gives a 2x speedup, and usi ng CJC gives over 3x! The primary increase, according to the second chart, appears to be due to cutting back on calls to the Miller-Rabin algorithm. The more candidates we can discard before trying M-R, the better.

(By the way, ignore how long these algorithms are taking in wall-clock time. I ran them in a standard JVM without JIT. In real life, you would definitely want this to be in JIT or possibly even C — horrors!)

Anyway, hopefully this is an interesting technique for filtering primes. And the name CJC? It’s named after my friend Communist J. Cat.

Git for the real world

2008-07-13T00:00:00-07:00

Now that we've been using git at Twitter for a couple of months, we've overcome several crippling problems and misunderstandings about how to use it properly. There are dozens of “intros” and “tutorials” to git online, but at some point you need to know more than just the basics of DVCS and the map to svn commands — you need to know practical considerations of real-world usage. None of the intros or tutorials had this stuff, so I thought I'd share what we learned.

Git’s command-line interface is hands-down the worst of any DVCS (except the archaic tla). There are inconsistencies: Some commands will expect you to type “origin/master”, while others will want “origin master”. Other commands should never ever be used, but are presented in the documentation as if they’re part of a normal usage pattern. Some commands are useless in their default form and need several command-line options to make them work right.

I ended up writing a wrapper script to cover up a lot of these flaws, which I consider an “ultimate fail” for a UI. But I'm still not sure the script is a good idea, since it may make me forget all the quirks I need to keep in mind when the script isn’t around.

Don’t change history

Two commands you should avoid: git rebase and git reset. Some of the tutorials will tell you that rebase is one of the first commands you should learn. Lies! rebase is a way to trick you into creating merge conflicts.

When you rebase, you are erasing every local commit you've made, and turning them into patches (as if you were back on CVS). After syncing your repository up with the remote one, your patches are re-applied one by one. Presto! you've changed history.

The only reason I can think of for doing this is if you’re not comfortable doing merges. But DVCS is all about merges, so you should just get used to doing them. A merge provides a little signpost to everyone else about your branch. Don’t fear the merge — love it! It records exactly how your local work should be rectified with remote changes, without requiring you to keep tweaking your patch.

reset is even worse. It erases commits from your history, which will very likely make your local repository different from everyone else’s, and guarantee future conflicts or even an inability to push in the future. Some people will say you should learn reset so you can use it in a panic situation, but if you’re panicking, you’re more likely to make things worse, so stop. Calm down. You have time to think and solve the problem in a rational way.

My problem with these two commands is that they violate a core philosophy of DVCS: Everyone has their own view of the repository, but these views obey entropy and flow in only one time direction. When they meet, they merge. Doing a rebase or reset goes back in time and changes the past. They should be in a separate tool, like “git-fix” or “git-hack”.

The story matters more than the chronology

Have you ever read a history book that said “In 1812, the British empire shelled the tiny new American capital. Meanwhile, Napoleon marched across Europe. In China, …”? Hopefully not, that would suck. Telling a thread of the story from beginning to end is more important than placing every single event in its exact chronological order. The default format for git log reorders commits by their exact date and time, so you need to be aware of that and not get confused.

Say, for example, you made a local branch, and made 3 local commits: L1, L2, and L3. Meanwhile, someone else is working on a different feature on their branch, and does commits R1 and R2. After you merge (M1), git is likely to show you a history like this:

M1 -> R2 -> L3 -> L2 -> R1 -> L1

Huh? What? Why are my local commits intermixed with my co-worker’s commits? The merge must have messed up! Crap! Time to git reset and destroy everything, right? No! Stop! Don’t do it. It’s a trap! Git is lying by omission — it’s telling the literal, actual truth, but it’s telling it to you in a way that makes it confusing. Git is re-ordering the history to make sure every commit is shown in its actual time order, not the story order.

You should probably just go ahead and alias log to:

git log --topo-order --decorate

That tells git to show things in “topological” (story) order, and to also mark where various branches are sitting. I usually find it useful to take that one step further:

git log --topo-order --decorate --first-parent

That tells git to show things in story order and to tell that story from my point of view. It’s sometimes interesting to see every commit that one of your coworkers did in their branch, but often you just want to see the merge-commit and move on. "-- first-parent" tells git to skip over the details of every branch that isn’t a linear parent of yours. Generally this means you’ll see a simplified history of what’s been going on, without the intricacies of what happened on forked branches while they were forked off.

If you want to see all the threads of history intertwined, I suggest using a graphical tool like gitk instead of git-log.

Don’t fast-forward — live every moment

This one is pretty confusing. And it sucks, because this concept doesn’t even exist in other DVCS. I think it’s another symptom of “fear of merge”. Basically, sometimes when you ask git to merge branch A into branch B, it will decide that it doesn’t want to merge and it will instead turn A and B into clones of each other.

For example, let’s pretend you made a branch of “master” called “feature” and did a few commits on it, and are now ready to merge it back into master. If no other work has happened on the master branch, git will try to out-clever you. It thinks: “Well, nobody else has worked on the master branch, so I could just make the feature branch become the new master branch and that would be logically equivalent.” So after the merge, you’ll see every single commit you made, as if you had done them directly on the master branch. Git has cloned your feature branch into the new master branch.

This might not be so bad if there are only a couple of people working on the project, but there are a few side effects: Your branch has effectively vanished from history. There is no longer any indication that you were working on a side branch; it looks like you were working directly on master. And if it turns out that there were bugs in your new feature (which, you know, sometimes happens), you can’t reverse the merge-commit because there is no merge-commit. You will have to reverse every single commit you made, in reverse order, or worse.

So really, you want git to always create a merge-commit when you do a merge. For this, you have to ask it nicely:

git merge --no-ff

(Git calls the history erasing “fast-forwarding”.)

A few other things

To remove a branch from a remote repository after it’s been merged and deployed, you have to push the branch with a colon in front of the branch name. This has become a running joke in the office: “Colon means delete.” Look, don’t ask me, I'm not Linus. That’s just how it works.

git push origin :stale_completed_branch

When other people remove branches, they won’t be removed from your local copy of the repository. To take care of this housekeeping, you need to express a fruit preference:

git remote prune origin

Again, don’t ask. I don’t know why. That’s just how it is.

I have a few ranty topics on how git is implemented and used, and how that compares with the older DVCS (especially bazaar), but I’ll save that for some other time. If you’re using git, hopefully this information is useful.

Git gripes

2008-05-11T00:00:00-07:00

I have to get this rant off my chest.

Why does git insist on making up new terminology for features that are in all DVCS, and already have commonly accepted names?

Last week during a presentation, I almost choked when someone showed off a git feature where you can temporarily shelve uncommitted changes. It’s called “git stash”. Stash?! Mercurial and bazaar at least agree that this is called, um, shelve. Since you are shelving. I don’t have a bag of heroin to stash, Linus. Just patches. To shelve. Now until the end of time I will need to remember which term to use when talking to git people or the rest of the universe.

In git, when you commit, you are actually staging. (Git doesn’t consider a commit to be truly committed until you've posted it to someone else’s repos itory — a charming bit of communism.) A staged commit is, to git, a cached commit. Wikipedia tells me a cache is a copy of data that’s already stored elsewhere, but nevermind, that definition doesn’t apply in the gitverse. Commit = staged; staged = cached; got it?

To switch branches in a working tree, you “checkout” in git. You also “checkout” to create a new working tree for a branch. The manpage for “git-check out” can’t even avoid sounding confused by this, and admits that the former usage really “switches branches”. Let’s see if we can think of a good term for switching branches. How about “switch”? Hey look, that’s what everyone else calls it! Must be a very odd coincidence. To branch is to “clone”; to revert is to “clean”. Not even the simplest of terms escape newspeak.

I want to end on a positive note, so I will say that compared to every other DVCS, git is fast. I frequently have no idea what it’s doing (is “deltifying” really a word?), or if it’s doing what I'd like it to do, but it’s doing it very very quickly. Maybe there’s a metaphor there.

Scarling

2008-05-07T00:00:00-07:00

I recently spent bits of my free time porting Starling to scala, and thought I'd post the story here in case anyone else finds it enlightening or interesting.

Starling is a simple, reliable message-queue server written in ruby. It uses MemCache protocol, so almost any language can already speak to it. You can set up multiple starling servers, and just like a memcache pool, the servers don’t need to know anything about each other. If clients pick a server at random for each operation, it appears to be a single loosely-ordered queue, with each server holding its own part. Starling is used extensively at Twitter.

I've been tinkering with scala since December, and have been building a config/logging library in my spare time. It was easy to pick up since I've been using java and python for many years, and scala seems to nicely synthesize the styles of those two languages. I felt like I was ready to try a meaningful project, and Starling is potentially the kind of project that could gain a lot from running on the JVM. At a mere 1000 lines of ruby, it was also a nice managable size.

First chunk

I'm a bottom-up coder, so I started with the PersistentQueue class. It’s the guts of Starling: a FIFO queue backed by a journal, and the means to rotate and replay that journal when necessary. For this class, I was able to do nearly a direct copy, just converting ruby syntax and library calls into scala ones. Only a few places tripped me up:

Scala, like java, has no equivalent of the “pack” function that’s in all of the perl/python/ruby languages. I actually had to write a 10-line class to write a little-endian int into a stream, and another 10-line class to read one. Ack! That wasn’t an auspicious start, and gave me pause. Everything that makes people run from java to higher-level languages was there: You’re given only the most basic, fundamental tools to do I/O, and serializing data is treated like some strange, rare operation.

Aside from that, it went smoothly, though. The payoff was when I downloaded a troublesome 500MB journal file from a running starling server and ran it through the scala journal replayer. Starling would take about a half hour to process the log (and frequently crash the ruby interpreter). “Scarling” (as I call my scala version) was able to process the log in 23 seconds. Exciting!

Next up was QueueCollection, which is what it sounds like: a collection of all the persistent queues, and methods for getting stats on them. Starling does some trickery here to avoid races around queues that are replaying journals. I made a few false starts, trying to either duplicate the logic or improve it, before I decided the really clever thing would be to make each queue an actor. Once I made that leap, the code practically wrote itself, and I stopped for a week.

Second chunk

The remainder of Starling is front-end code for handling connections, speaking memcache protocol, and interfacing with QueueCollection. I needed to break away from porting code at this point, because Starling uses a ruby wrapper around EventMachine, a fast asynchronous event I/O library. New incoming connections create a Handler object and send it events when new data arrives. I was sure this was a place to use actors, but I wasn’t sure how much of the I/O code I'd need to write. (I wrote most of ziggurat, Danger’s async I/O library, so I'm not scared of writing an I/O library, but it would be really time-consuming and non-fun.)

Googling for “java EventMachine” turned up links to an apache project called Mina. Aha! This was pretty much exactly what I was looking for. In fact, it closely resembles a ziggurat-derived library my friend Matt is working on, since they both use the idea of pushing protocol encoders into the I/O event engine. Mina not only creates a new “session” object for incoming connections, it can decode the wire protocol inside its own worker threads, and notify your session of I/O events by sending it fully-decoded objects.

This model is so close to how actors work that it just made my mouth water. I just needed some kind of gasket! More googling revealed that one (and only one) person had already done this work, and written a scala wrapper for Mina that turned “I/O events” into actor messages. Well actually, he did it as a patch against Mina instead of a wrapper, for ill-explained reasons. Oh, and the patch fails to compile. Oh, and all the links on his project page are broken. Oh, and also he has no posted email address. FAIL. I made an attempt to reach him through blog comments (ugh) and decided to do this one on my own.

Luckily, once I read enough of the (actually semi-decent) Mina docs, I was able to connect Mina to actors in less than 50 lines of code. I told you: the two models (Mina and actors) really are made for each other. I hope someone ends up writing a working wrapper for it. Or heck, just use mine as a starting point.

The last piece was a memcache protocol handler, written to Mina’s API. I found one from a project called jmemcached, ported the bits I needed into scala, fixed it up to use some of scala’s nicer collections like ArrayBuffer[Byte], and impatiently patched the wrole thing together for some trial runs.

First Results

The first results were pretty discouraging. I wrote a quick test script to open a connection and do 10,000 queue SETs, and on my old Macbook Pro, Starling could do them in under 4 seconds. My scala port could do them in 30. This is roughly a factor of 10 worse — an order of magnitude. Miserable failure. What was I doing wrong?

Scala doesn’t have many (any?) performance benchmarking tools, but java does, and these java tools don’t seem to care if your jar was made by java or scala. I fixed a few small things, but wasn’t making much progress. My inexperience with hprof made me fix the least important things first, but the last two were worth telling about.

Using an actor for each queue was overkill. Reading from or writing to a queue is such a fast operation that the message-passing for “please write to this queue”, “okay done” was deadly. I reluctantly scrapped the actor code there and used simple locks for the queues, and shaved off several seconds. The client connections were already actors, so it was just adding too much overhead to have the queues themselves be separate actors.

The biggest gain, which took me the longest time to find, and made me feel the most foolish, was in the memcache protocol decoder. I thought I was being really clever by sending incoming data into a scala ArrayBuffer[Byte] and doing functional operations on it. Those operations are sometimes slow as molasses! One, “trimStart”, was using up 1 millsecond per queue push, or 10 seconds of total test time all by itself.

Begrudgingly, I dove into my memcache protocol decoder and decided to do things the Mina way instead of trying to be clever. Using Mina’s ByteBuffer class slashed times dramatically, and suddenly my scala code was as fast as Starling (less than 4 seconds). I actually spent a couple of days fretting about the poor performance before this “eureka” moment, and was very relieved to find out that the slowness was entirely due to my own brain damage, and not to anything in scala or actors.

Better Results

“As fast as ruby” may not sound impressive. In some circles, it’s actually an insult. But for this test, I felt good. First, Starling doesn’t do anything intensive in ruby. It uses ruby’s expressiveness and its libraries to make a small server that’s mostly disk I/O and network I/O bound. EventMachine does a bang-on job of network I/O so there’s little room for improvement.

However… My test was effectively written to play to Starling’s strengths. Since Starling runs in a single thread on a single process (STSP), it excels at handling a single client which makes a lot of requests, but waits for a response between each request. The advantage of the JVM appeared when I changed the test to emulate 100 clients doing 100 queries each.

To Starling, this is exactly the same test (10,000 queries, handled sequentially) so it gets approximately the same result (less than four seconds). Mina-plus-actors starts to shine here, though, and finishes in under two seconds. It’s able to juggle queue work with I/O threads. Success!

Conclusion

I've heard there’s a big migration of ruby people to scala, and so the first thing I would say to the ruby people is that this is no panacea. It’s not ruby on a JVM; it’s an entirely new langauge, with much stronger java roots than any other language, so familiarity with java is probably more helpful than python or ruby. On the other hand, if ruby whetted your appetite for functional programming, scala has more of that than ruby and python combined, and seems to live up to its promise of exposing the wonders of java’s scalability and rock-solid virtual machine and garbage collector.

The main stumbling blocks I hit were the same ones others have talked about: scarcity of tools, and a lack of pure-scala libraries — both probably due to the language being so new. Coming from java, it felt great to express myself with python conciseness. It was like opening up the space capsule and breathing fresh air again. Coming from ruby, it was reassuring to write for a platform and libraries that are solid and well-tested, not just an “overnight project” like many of the core ruby libraries appear to be.

Oh, and in the end, my Starling port was only a little over 900 lines long. I think if I added proper config file support like Starling has, it would end up being roughly the same number of lines (1000), even though I had to write a few large pieces (like the memcache codec) that aren’t necessary in ruby.

The end result, which I plan to keep playing with and expanding, is here: http://github.com/robey/scarling/tree/master

Scala infatuation

2008-03-16T00:00:00-07:00

Why my recent infatuation with scala? (Actually, since it’s reaching a half year, I guess it can no longer be called an infatuation.) Here’s my answer in the form of a quick example. I want to determine the average of a list of timings for something.

In python:

timings = [1.2, 1.5, 1.3, 1.5]
reduce(lambda a, b: a + b, timings, 0.0) / len(timings)

In ruby:

timings = [1.2, 1.5, 1.3, 1.5]
timings.inject(0.0) { |a, b| a + b } / timings.length

Besides demonstrating that ruby is just python with different spelling, this shows they both have some powerful built-in functions and syntax. I can type one line for calculating the average and move on to the real point of my code, whatever that is.

Here it is in scala:

var timings = Array(1.2, 1.5, 1.3, 1.5)
timings.foldLeft(0.0) { (a, b) => a + b } / timings.size

It’s pretty much the same! I can type code that is very close to the pseudocode in my head, and move on.

Whether intentionally or not, scala is borrowing very heavily from the “high level” language features of python (and ruby). But it’s running on top of the JVM, which is still the best combination of interpreter machine + libraries out there. Python’s VM is amateur at best, and ruby’s is even worse. This way is like getting my reeces cup, two great tastes that taste great together: a high-level, pseudocode language on top of a racecar engine.

I suspect this is the main reason scala has been getting a lot of attention recently, in spite of the gaping lack of decent documentation or tools.

Oh yeah, here’s that same code in java. I'm not including the creation of the array, because that takes 5 lines all by itself, and wouldn’t be fair to compare:

// assume omitted var: List<Double> timings.
double sum = 0.0;
for (double d : timings) {
    sum += d;
}
double average = sum / timings.size();

For java versions before 1.5, it’s a lot worse.

Incidentally, last night I found a nice introductory article on scala, which I skimmed and recommend.