Saturday, February 28, 2009

Interview questions and poop

As part of the job hunt, I am reviewing potential interview questions and practicing (as much as one can practice this sort of thing).

There are four major groups of interview questions, as far as I can tell:
  • General knowledge - discussions about what you know, questions like "what does the synchronized keyword mean?"
  • Coding questions - "reverse a linked list"
  • Puzzlers with one or two right answers - "you have two candles that burn for 60 minutes. How do you use them to measure 45 minutes?" - no, you can't cut the candle, or make marks with a ruler...
  • Puzzlers with no right answer - "you have been reduced to the size of a nickel and placed in a blender. The blender will turn on in 60 seconds. What do you do to save your life?"
I haven't personally been asked the last kind of question, but I've read about them. They're supposed to test your creativity and, I don't know, spunk.

However, a few days ago I had an experience with my son that got me thinking, and I realized that as a father and a homeowner I have to face these kinds of questions all the time. Note: none of these situations are made up...

You're in a bookstore with your three year old child who has just recently been potty trained. You are enjoying reading a book while he plays with the train set in the kid's section when all of a sudden he says matter-of-factly "I pooped." You have no change of clothes and no wipes. How do you clean up your son without making a huge mess, embarrassing yourself, or both?

You are on the airplane to Hawaii with your five-year-old daughter, and there is massive turbulence. The flight attendants refuse to provide water, and there are no airsickness bags. Your daughter throws up on herself. Twice. What do you do?

You have a son who likes how things "work". One day you discover most of your daughter's plastic necklaces are missing. The next day brown disgusting water starts bubbling into your bathtub. What do you suspect has happened?

You hear a roaring sound at 2 am and stumble downstairs to find two inches of water in the kitchen. The roaring sound is coming from under the sink. What is happening, and how wet do you think your pajamas actually get?

You have an invasion of rats that have destroyed your futon mattresses in your garage and have eaten their way through your plastic earthquake bin to tear apart your earthquake supplies. They wake you up every night chewing on the drywall just behind the bed. They ignore all traps. How do you get rid of the rats?

So, perhaps I am more prepared for these kinds of questions than I may think...

Wednesday, February 25, 2009

Turning Japanese - Paul Krugman Blog -

Scary stuff
Pretending that distressed assets are worth more than they actually are today for regulatory purposes persuades no one besides the regulators, and just gives the banks more taxpayer money to spend down, and more time to impose a credit crunch. These kind of half-measures to keep banks open rather than disciplined are precisely what the Japanese Ministry of Finance engaged in from their bubble’s burst in 1992 through to 1998 …

Facebook's Cassandra - what's going on?

I read with interest the SIGMOD paper on Facebook's Cassandra.  It looked very interesting, an open source combination of BigTable and Dynamo (PDF) .  It appears to be running in production in Facebook serving the very demanding inbox notification system.

So I wanted to try it out.  I went to the Google Code project, and it just seemed, well, dead.  The instructions for checking out the source are wrong both on the Sources tab as well as in the Wiki.  The mailing list has almost no activity.  It looks like they are trying to get into Apache incubator, but meanwhile people are asking what's going on, what the status is, and there appears to be no response.

A consideration for using any technology is understanding the strength of the community behind it.  You don't want to bet your infrastructure on something where there is no support and you are basically on your own to maintain it.

So, if you know what's going on with Cassandra, please let me know.  Meanwhile, I'm going to put it on the back burner and take a look at some alternative clustered key-value stores, like Project Voldemort, SimpleDB and HBase.

Hitting the scalability wall - Amdahl's Law

Author's note: I was thinking about this blog and how I didn't quite capture some things correctly, particularly around what it means for processing to become serialized.  Then I saw some comments that repeated my own concerns.  So I have done some rewriting in an attempt to explain more clearly what I think the issues are... 

When examining the challenges of throughput and scalability in the brave new world of Web Scale, one solution I've been looking at is Gigaspaces.

I recently read their article about scalability (follow the link to "The Scalability Revolution" - you may need to register to be able to see it), and they made a claim that gave me pause, to say the least.

Basically they said that if you have a multi-tier architecture, you are doomed - sooner or later you are going to hit a scalability wall, either because of cost, complexity or latency.  I think in particular they meant that if your end-to-end request/response path must travel over multiple tiers to complete, you are doomed.

They have examples to back up this claim, but what was compelling for me was their reference to Amdahl's Law.

Amdahl's Law states if any portion of your system requires processing to be serial instead of parallel  then the system is going to hit a scalability wall where it can go no further, no matter how much hardware you throw at it.   From the Wikipedia article:
The speedup of a program using multiple processors in parallel computing is limited by the time needed for the sequential fraction of the program. For example, if a program needs 20 hours using a single processor core, and a particular portion of 1 hour cannot be parallelized, while the remaining promising portion of 19 hours (95%) can be parallelized, then regardless of how many processors we devote to a parallelized execution of this program, the minimal execution time can not be less than that critical 1 hour. Hence the speed up is limited up to 20x.
Note that the actual numbers don't matter too much.  You can avoid hitting the wall by reducing the amount of serialization, but sooner or later, you are going to hit that wall.  And even before you hit it, the cost of getting a fraction more speedup is going to increase exponentially.  I have heard many stories to vouch for this, where getting 10% more throughput requires 100 times the hardware investment and/or complete rewrites of applications.

If your system architecture requires you to potentially wait for a shared resource within the request/response path, then you are shifting from parallel to serial execution, and you are going to hit Amdahl's Wall.   Here are some examples:
  • Reading/writing data in a shared database
  • Sending a request over a network which will block if the network is congested (the network is shared by multiple simultaneous requests)
  • Writing to a disk which may block if it is busy, where the disk is shared between multiple simultaneous requests.
Well, that does seem to throw a wrench in things.  How can a service run independently, with no database access, disk I/O or network I/O, and still be useful?

Well, the key thing is that these things can not happen within the request/response path.  They can still be done in the background, asynchronously. For example, if the user updates their profile, then this update is stored in-memory and then, in the background, this status update is stored in the database.  If you want to send a message to another service, the message is queued up in memory and then delivered to the external service asynchronously.  

Note the consistency implications of this.  You end up with a system where not everybody has a consistent view of the current state of the system.  But we already know through the CAP theorem that this is something you probably need to accept.

There is also a window of possibility where the user thinks the update succeeded but the actual persistence of this update fails or there is some kind of conflict.  This means your company and your application has to know how to apologize.

But if the benefit of this is linear scalability, these tradeoffs may be well worth it.  Better to apologize to a small subset of customers about a lost order than apologize to all of them for terrible latency or to apologize to your management about the cost and time overruns for your system.

Gigaspaces claims to have accomplished this kind of architecture with a runtime environment they call a space which provides in-memory access to all the resources you need to process a request.  The underlying Gigaspaces runtime ensures that each request is routed to the right cluster node and that the node contains all the resources needed, in memory, for that object to get its job done.   To be honest, I am still mystified how they can accomplish this, and this is something I would like to investigate further.

At any rate, I appreciate the Gigaspaces article helping me understand the implications of Amdahl's Law.  As I evaluate a scalability architecture, if something, somewhere, requires the request/response path to potentially wait on a shared resource, then I know that sooner or later we've got trouble.  It's the law.

Sunday, February 22, 2009

InfoQ: CouchDB and Me

Wonderful talk by Damien Katz, author of CouchDB. How to get a job doing cool stuff? Close your eyes and jump...

Monday, February 16, 2009

Why not just put the whole friggin' thing in memory?

When I was at Sun, I worked on the design for a replicated in-memory data store. One of the principles was, scale and throughput demands are increasing, and memory is getting cheaper, so why not put it all in memory, and use disk/database only as a backing store. We provided durability not through writing to disk but through replication, and then writing back to disk (e.g. to a traditional relational database) in the background. Even if there were a node failure, we would recover from the replica, not from the database.

We couldn't get this project funded for various reasons. It's been frustrating because I knew we were on to something but couldn't make it happen - and now, as many of us predicted, the industry is moving in that direction - a growing belief in denormalization, caching, and eventual consistency. But still, many applications write to the database as part of the cycle of a transaction.

But this article at HighScalability hit the nail on the head - you evolve your application from database-centric to cache-centric to memory-centric. Money quote:

As scaling and performance requirements for complicated operations increase, leaving the entire system in memory starts to make a great deal of sense. Why use cache at all? Why shouldn't your system be all in memory from the start?

Well, that sounds awfully familiar. And it's true. If you are replicating anyway, your risk of data loss is pretty minimal, and as Pat Helland, Amazon ex-architect says, computer suck, and you should just plan to apologize sometimes. If you batch your changes every N minutes, then you have an N minute window where some changes may be lost. But for many applications, that's OK. And the wins you get in terms of throughput are significant.

Latency was slashed because logic was separated out of the HTTP request/response loop into a separate process and database persistence is done offline.

It looks like the way they implemented an all-memory solution was using Gigaspaces, which, by the way, has a solution that deploys and scales automatically on the Amazon EC2 fabric. And the result: near linear scalability and 1 billion events a day[1]. Yeah, that's the ticket.

[1] I think actually this statement is misleading. Reading the article more carefully, they are claiming they can get to 1 billion events a day. This hasn't actually been tested, so take it with a grain of salt.

Posted via email from David Van Couvering's Posterous

Friday, February 13, 2009

RESTing on the Couch - adjusting my CouchDB experiment

As I was playing with my son - a great way to let the right brain chew over a problem - I came up with a different architecture for my memcache/CouchDB experiment, one that I think makes more sense.

Rather than have a traditional PHP front-end, I realized that I need to follow the model I've been espousing for a while now. The server interface, rather than being HTML/browser-centric, is instead a REST web service. The client could be HTML, but I think my first representation of a REST resource will be JSON, and the client user interface will initially be written in JavaScript. Subsequent clients could be written in JavaFX or Flex or Silverlight or an Apache/PHP server, mine or somebody else's... Exercises left to the reader, or to myself time permitting.

Tempting as it may be ("hey, CouchDB is REST with JSON!"), I'm not going to expose CouchDB REST directly to the clients. In general I think it's dangerous (architecturally) to expose your database directly to clients.

Instead, I'm going to put a middleware layer on top so I can do clustering and caching, and also so I can swap in a different caching and storage mechanisms.

Another solution I'd like to try is Gigaspaces, but I'm getting ahead of myself...

.NYC Gets Big Boost from New York City Gov’t » Names@Work

My brother makes big news today - his effort to create a top-level domain for New York City - .nyc - is starting to bear fruit.
New York City will soon have its own place on the web – with dot NYC. Mark Twain famously advised “Buy land, they’re not making it anymore.” Well now we can make more New York addresses – just on the internet! A local business won’t have to outbid a guy in Kansas to get Tony’s Pizza dot com. They’ll be able to get Tony’s Pizza dot NYC, a name associated with the greatest city – and home of the greatest pizza – in the world.

Setup a Memcached-Enabled MAMP Sandbox Environment | Lullabot

Here are some great instructions for getting yourself bootstrapped with memcached on Mac so you can work in a local sandbox.

Setting up a CouchDB cluster fronted by memcached

While I'm looking for work, I thought I'd get to play around with some technologies that I have been very interested in but I haven't been able to get really hands-on with because of my day job.

My first project - set up a CouchDB cluster fronted by memcached and run a simple PHP application on top of that.

The architecture I'm thinking of looks something like this. I'm sure I'll refine it over time after playing around with it, but starting fairly simple first:
  • A web tier running Apache and PHP
  • A memcached tier
  • A CouchDB cluster tier
I will distribute records across the CouchDB cluster by using a distributed hashing algorithm against the keys. The ones that look most promising are Kademlia and Chord. I'm leaning towards Kademlia.

I think it's cool that the same qualities you need for peer-to-peer file sharing are valuable for server-side clustering - even distribution, good performance when nodes come and go, and robustness under heavy changes to node configuration.

Once I have something working, I'll let you know my experiences. Then I'm interested in trying this with SimpleDB and Project Voldemort... I also want to take a look at MemcacheDB. So much interesting stuff, so little time :)

Thursday, February 05, 2009

The Canonical Cloud Architecture | High Scalability

This is a very nice and useful architecture with some "patterns" for cloud architectures - although I believe a lot of these patterns can be applied to any system of large enough size. I am particularly a fan of queuing as a great option for tying together loosely coupled system components in a way that can scale and perform. If you can handle delays in your system and don't need a lot of synchronized workflows, it is one architecture I personally would look at very seriously.

Monday, February 02, 2009

Hm, I'm not sure about this new president

You know, I was always bashing Bush, but at least I had a job under his administration. Two days after this Obama guy takes office, and I'm out of a job.  What's that about?