How to Render the Mandelbrot Set in the Joyent Cloud with Node.js
First of all: Apologies for not posting for a long time. The reason? I was having too much fun with node.js and the Joyent Cloud :).
What started as a small experimental hack turned quickly into an exciting new pet project involving the good old Mandelbrot Set, as a web service, running in the Joyent cloud, programmed in node.js.
But first things first: Let's take a look at node.js as a language and programming model, at the Joyent Cloud and how it relates to Solaris and finally some details on how the picture you see was rendered inside the Joyent Cloud, including an interactive Mandelbrot Set explorer you can play with now, written as a web app.
I think the first time I heard about node.js was from Bryan Cantrill in this post where he explained the story about Joyent and a node.js programming contest and how they added DTrace probes to Node to enable some analytics for their contestants' machines.
What Is Node.js?
Node is lower level than most web application frameworks: HTTP and sockets are first-class citizens in Node, and "Hello world" in Node is actually a web server. Other frameworks like Java, PHP etc. typically sit on top of an existing web server (though it is possible, but not common, to implement web servers in these languages as well). Node's intimacy with networking protocols make it interesting from a minimalistic point of view: Develop the web server with the web app in sync, and only implement the pieces that are really necessary, leaving out the rest.
You can also implement pure socket based protocols with node.js, which makes Node interesting to game developers, for chat servers, messaging in general, etc.
There's a rapidly growing library of Node extensions called Modules, including a package manager called npm that makes installation of modules very easy. Most low level web server programming needs can be addressed easily with the connect framework, higher level web apps will enjoy working with the Express framework.
Why Node is Cool
Here's why I think node.js is so interesting:
onclicketc.), node.js is based on server events.
- node.js removes the complexity of dealing with concurrency, locking etc. by ignoring these concepts: If everything is driven by little pieces of code that run independently, triggered by events, there's a complete disconnect between them. This is a good thing: No need to watch out for the other guys, no need to do any locking or other complicated stuff. Just write small pieces of code that do their job little by little and let the database, the OS or the node.js runtime deal with the messy concurrency stuff. Eventually, there will be a way to fire off parallel threads, but it will be batch-oriented and message based, through the web workers API.
- It's easy. I managed to put together a Mandelbrot Set rendering web service in about an hour. From scratch. And I'm not a real programmer.
- It's new. There's a lot of innovation around Node. It's a completely new world, which makes it fun and exciting, too.
Joyent and node.js
As you may know, Joyent is a startup company that delivers cloud software and cloud hosting services. Joyent is probably the most innovative company in terms of cloud computing right now, and they're big supporters of Solaris. In fact, their own "SmartOS" operating system for the cloud is based on OpenSolaris. Cool people including sysadmin god Ben Rockwood, DTrace gods Bryan Cantrill and Brendan Gregg (Buy his DTrace book now*, it's really good!), and of course node.js inventor Ryan Dahl work there.
IMHO, Joyent is where the future of Clouds is made.
Anyway, the Joyent Software Stack uses node.js at the top to deliver a powerful, asynchronous, open source PaaS platform.
Getting Started with Your Own Joyent SmartMachine for Node.js for Free
Of course, you can play with node.js on your laptop, but it's more fun when you use it inside a real cloud.
Thankfully, this is really easy (and free) with Joyent's SmartMachine for node.js service:
- Go to http://no.de/ (yay, a German domain!) and sign up for a Joyent account there.
- Read the Getting Started With a Node SmartMachine guide, including how to apply for a provisioning code so you can provision your first Joyent SmartMachine.
- Upload your SSH key, set up your Git repository and off you go!
The beauty of a Joyent SmartMachine is that it's actually a Solaris Container: You get all the flexibility and power of being king on a Solaris system, with all of the security, reliability and efficiency of a Solaris system, but without the hassle or without annoying your other buddies running on the same physical machine.
The node.js service running inside a SmartMachine is nicely integrated with Solaris: It's configured as an SMF service and the pre-supplied commands
node-service-log etc. make great use of it. Even better: As soon as you push your Git repository into your Joyent SmartMachine, the node.js service is automatically restarted through SMF to immediately update your service. And if anything fails, it will automatically revert back to the previous version. How cool is that?
But the real killer here is the integration of node.js, DTrace and the Joyent Cloud Analytics feature. As your node.js app gathers more and more users, you can use Cloud Analytics to diagnose, monitor and better understand the dynamics of your service. Watch the video with Bryan Cantrill and Brendan Gregg on Cloud Analytics to get an overview of how it works.
Joyent gives you a simple package manager with a large amount of pre-configured packages called pkgin. npm, the Node Package Manager is pre-installed, but some extra packages are recommended for a smoother install of some npm modules.
Introducing the Constant Thinking Mandelbrot Rendering Web Service
So I started playing with Node in a Joyent SmartMachine. And it was fun! After a few weeks of trying stuff out, optimizing and tinkering I can now present you with my first real web app, the Constant Thinking Mandelbrot Set Web Service!
Most of you already know that the Mandelbrot set is a beautiful mathematical object that can be generated using a simple formula over and over again over the coordinates of a complex number plane. I think I wrote my first Mandelbrot set program at the age of 12 or so, when these things became fashionable in the home computer crowd.
Now here's how Mandelbrot 2.0 works:
- On this page, click anywhere within the image to set a new center for the image computation.
- Click on "Zoom" to zoom into the set, and on "Zoom out" to back out. The math says there's infinite detail hidden in the set. The limits of floating-point calculations will put an end to this but as soon as I start seeing precision errors, I'll work on a more precise implementation.
- The amount of detail is limited by the maximum number of iterations. If after a few rounds of zooming into the image the black areas start to look boring, hit the "more details" button and you should see more cool stuff. This simply doubles the maximum number of iterations for the computation.
- There's some anti-aliasing, too: If you select one of the anti-aliasing options, the image will be generated at a larger resolution (3x3 or 5x5), then shrinked into the target resolution using one of two filtering methods (simple Gaussian or the more sophisticated Mitchell-Netravali filter). In theory, this should make the image smoother. In practice, the infinite detail of the set counters that a bit. Still worth a try.
- Finally, there's some timing displayed and you have a choice of different optimization algorithms. The fastest algorithm is chosen by default, but if stuff looks funky, send me the parameters that were displayed and how you got there, and go with one of the lower optimization levels to get a decent picture.
Experiences, Gotchas and Further Plans
Since Node is so new, there are a couple of minor annoyances: There's no easy way to do parallelism (it's not encouraged yet, until the web workers API is built in), the amount of available modules is rapidly changing or incomplete, and sometimes the best documentation is to read some example source code. All of these are just symptoms of a good thing: A new, innovative and rapidly evolving world.
Bonus: Source Code and Some Mandelbrot Set Geekiness
Most of the time I spent writing this web service was actually spent on optimizing the algorithm for computing the Mandelbrot set. For the standard image you see in the beginning of the Mandelbrot web service page, the speedup is more than 2x, so it was worth the effort. Here's a crash course in Mandelbrot set optimization:
- The two main big bulbs that the Mandelbrot set is made of are actually well understood (see the Wikipedia article on the Mandelbrot set). This means one can use a simple formula to detemine whether a point is inside one of the two bulbs, then decide whether to skip or continue the standard, lengthy iteration formula.
- Exploiting connectedness: The Mandelbrot set is connected. This means that there are no "islands". This also means that if all points of the circumference of any area are inside the set (= black), the whole area is. To exploit this, an algorithm can subdivide the set into rectangular blocks, walk the blocks' edges and try to find blocks with circumferences inside the set through binary (or any other convenient) subdivision. For such blocks, further iterations can be skipped and the whole block can be marked as inside the set.
- Major areas of the Mandelbrot set are well-known: This means that we don't need to test for bulbs if we're rendering the piece that's above them, so we can skip the check. We can also skip the check for bulb 1 if we're left or right of it, etc. This optimization therefore computes the intersection of different areas with predefined optimization settings and the areas that are actually to be rendered, then uses the right optimizations for the right pieces of the image.
- Exploiting symmetry: The Mandelbrot set is symmetrical along the real axis. So if the area to be rendered crosses that axis, up to half of the image can be recycled through mirroring.
The highest optimization setting (which is also the default) makes use of all of the above and should be pretty good for most cases. If you have any more cool and easy to implement optimization ideas, let me know!
That said, the only thing left for me to do in this article is to give you the source :). Like any good Node citizen, I've set up an account on Github and uploaded the current version of the source:
Of course the usual disclaimers apply: Use at your own risk, don't sue me, forgive any code uglinesses, let me know if you find bugs, send me your suggestions and generally have fun with it.
Conclusion and Further Plans
Many thanks to the fine people at Joyent for bringing node.js to the world and giving it such a cool place to live! Thanks to their great support people who helped me find the magic incantation for getting a provisioning code. I'm looking forward to seeing Node grow and continue playing with it :).
Actually, the fun has just started: Right now, the Mandelbrot set rendering web service ist pretty basic, and it doesn't use many of the cool Node features. Over time, I'd like to add some more:
- Caching should be easy to do in Node, and I already have an idea on how to exploit it.
- Parallelism is the next big thing: Put together a stack of batch jobs that make up the total rendering process, then fire them at some worker nodes, then collect the pieces together. Should be fun to implement while learning something new.
- Integration with C: While Node is pretty fast already, it would be fun to implement the basic number-crunching in C so I can learn how the integration of C works with Node.
- While we're at it, I'd like to increase rendering precision through implementing the computations in a purely integer manner. You know, floating-point is evil.
- The user interface on the web browser side could use some brushups, perhaps with some jQuery magic.
- Colormaps should be configurable.
- And so on. You know, some projects are never finished...
Did you try out Node already? What are your experiences? Any cool libraries, hacks, tips to share? Do you like the Mandelbrot set web service, or do you think this is too 80's? Let me know in the comments!
* Affiliate link: You buy great stuff that's good for you, I get a small commission to help finance this blog, we both win!