Mikeal Rogers wrote a blog post on MongoDB performance and durability. In one of the sections, he writes about the request/response model, and makes the following statement:

MongoDB, by default, doesn’t actually have a response for writes.

In response, one of 10gen employees (the company behind MongoDB) made the following comment on Hacker News:

We did this to make MongoDB look good in stupid benchmarks.

The benchmark in question shows a single graph, which demonstrates that MongoDB is 27 times faster than CouchDB on inserting one million rows. At the first glance, the benchmark immediately looks silly if you’ve ever done serious benchmarking before. CouchDB people are smart, inserting such a small number of elements is a relatively simple feature, and it’s almost certain that either they would have fixed something that simple or they had a very good reason not to (in which case the benchmark is likely measuring apples and oranges).

Let’s do some back of the envelope math. Roundtrip latency on a commodity network for a small packet can range from 0.2ms to 0.8ms. A single rotational drive can do 15000RPM / 60sec = 250 operations per second (resulting in close to 5ms latency in practice), and a single Intel X25-m SSD drive can do about 7000 write operations per second (resulting in close to 0.15ms latency).

The benchmark demonstrates that CouchDB takes an average of 0.5ms per document to insert one million documents, while MongoDB does the same in 0.01ms. Clearly the rotational drives are too slow to play a part in the measurement, and the SSD drives are probably too fast to matter for CouchDB and too slow to matter for MongoDB. However, CouchDB appears to be awfully close to commonly encountered network latencies, while MongoDB inserts each document 50 times faster than commodity network latency.

At first observation, it appears likely that the CouchDB client library is configured to wait for the socket to receive a response from the database server before sending the next insert, while the MongoDB client is configured to continue sending insert requests without waiting for a response. If this is true, the benchmark compares apples and oranges and tells you absolutely nothing about which database engine is actually faster at inserting elements. It doesn’t measure how fast each engine handles insertion when the dataset fits into memory, when the dataset spills onto disk, or when there are multiple concurrent clients (which is a whole different can of worms). It doesn’t even begin to address the more subtle issues of whether the potential bottlenecks for each database might reside in the virtual memory configuration, or the file system, or the operating system I/O scheduler, or some other part of the stack, because each database uses each one of these components slightly differently. What the benchmark likely measures is something that is never mentioned – the latency of the network stack for CouchDB, and something entirely unrelated for MongoDB.

Unfortunately most benchmarks published online have similar crucial flaws in the methodology, and since many people make decisions based on this information, software vendors are forced to modify the default configuration of their products to look good on these benchmarks. There is no easy solution – performing proper benchmarks is very error-prone, time consuming work. It’s good to be very skeptical about benchmarks that show a large performance difference but don’t carefully discuss the methodology and potential pitfalls. As Brad Pitt’s character says at the end of Inglourious Basterds – “Long story short, we hear a story too good to be true, it ain’t”.

Interested in working at RethinkDB? We’re hiring – please see our jobs page for more details.

We’ve been actively recruiting for four months now, and if there is one thing we’ve learned, it’s that Jeff Atwood wasn’t kidding about FizzBuzz.

Among our friends in the startup community, RethinkDB has the rep for having the toughest interview process on the block. And it’s true – the interview process is something we won’t compromise on. We’re prepared to turn away as many people as it takes to build a superb development team. We wrote that much in an earlier post. In the past few months we ran into people that thought we have ridiculously high standards and are hiring rocket scientists who also double majored in quantum mechanics and computer science. We don’t. We just won’t hire programmers that can’t code.

In the interest of openness, we’ll post the smoke test that makes us turn away 19 out of 20 candidates within half an hour of a phone conversation (and that’s after screening the resumes). We don’t ask people to code a solution to a complex algorithms problem. We don’t ask to solve tricky puzzle questions. We don’t ask to do complex pointer arithmetic or manipulation. Here is the question that the vast majority of candidates are unable to successfully solve, even in half an hour, even with a lot of nudging in the right direction:

Write a C function that reverses a singly-linked list.

That’s it. We’ve turned away people with incredibly impressive resumes (including kernel developers, compiler designers, and many a Ph.D. candidate) because they were unable to code a solution to this problem in any reasonable amount of time.

We ask other questions, of course. What’s the worst case complexity of inserting N elements into a vector (or an ArrayList, or whatever your language of choice calls dynamic arrays)? We don’t care if you know, we just want you to try and figure it out. We’ll explain how a vector works internally. Hell, we’ll even accept O(N log N) as an answer.

How would you implement a read-write lock? You don’t actually have to code it over the phone. Mentioning starvation issues is bonus points. For heaven’s sakes, just give us something.

We try to ask about the difference between cooperative and preemptive multitasking. We try to ask about condition variables. 19 out of 20 times there is silence on the other end.

Why do we ask these specific questions? Because they’re part of a core body of knowledge taught in any undergraduate curriculum worth its salt, and because in some form or another, they came up in our daily work. And in four months we found out that if you understand the difference between threads and coroutines, can reverse a linked list, and have a basic understanding of condition variables, chances are you’re probably a much better programmer than most who are looking for a job, and a huge chunk of those who aren’t looking as well.

We’re hiring people who can do more than what I listed above, but I don’t think we’re asking for too much more. Just a solid understanding of the fundamentals, the drive to accomplish great things, and a little genuine love for your craft. To quote one of my colleagues who heard about FizzBuzz for the first time, “If they can’t do FizzBuzz, what can they do?”. After spending hours reviewing resumes, it takes twenty interviews to get to the candidate that can pass the smoke tests. At an average of 45 minutes per interview, this works out to fifteen hours of work. That’s a lot of time to find one candidate with a basic understanding of software engineering.

Will the real programmers please stand up?

Interested in working at RethinkDB? We’re hiring – please see our jobs page for more details.

There are two types of non-blocking thread synchronization algorithms – lock-free, and wait-free. Their meaning is often confused. In lock-free systems, while any particular computation may be blocked for some period of time, all CPUs are able to continue performing other computations. To put it differently, while a given thread might be blocked by other threads in a lock-free system, all CPUs can continue doing other useful work without stalls. Lock-free algorithms increase the overall throughput of a system by occassionally increasing the latency of a particular transaction. Most high-end database systems are based on lock-free algorithms, to varying degrees.

By contrast, wait-free algorithms ensure that in addition to all CPUs continuing to do useful work, no computation can ever be blocked by another computation. Wait-free algorithms have stronger guarantees than lock-free algorithms, and ensure a high thorughput without sacrificing latency of a particular transaction. They’re also much harder to implement, test, and debug. The lockless page cache patches to the Linux kernel are an example of a wait-free system.

In a situation where a system handles dozens of concurrent transactions and has soft latency requirements, lock-free systems are a good compromise between development complexity and high concurrency requirements. A database server for a website is a good candidate for a lock-free design. While any given transaction might block, there are always more transactions to process in the meantime, so the CPUs will never stay idle. The challenge is to build a transaction scheduler that maintains a good mean latency, and a well bounded standard deviation.

In a scenario where a system has roughly as many concurrent transactions as CPU cores, or has hard real-time requirements, the developers need to spend the extra time to build wait-free systems. In these cases blocking a single transaction isn’t acceptable – either because there are no other transactions for the CPUs to handle, minimizing the throughput, or a given transaction needs to complete with a well defined non-probabilistic time period. Nuclear reactor control software is a good candidate for wait-free systems.

RethinkDB is a lock-free system. On a machine with N CPU cores, under most common workloads, we can gurantee that no core will stay idle and no IO pipeline capacity is wasted as long as there are roughly N * 4 concurrent transactions. For example, on an eight core system, no piece of hardware will sit idle if RethinkDB is handling roughly 32 concurrent transactions or more. If there are fewer than 32 transactions, you’ve likely overpaid for some of the cores. (Of course if you only have 32 concurrent transactions, you don’t need an eight-core machine).

Interested in working at RethinkDB? We’re hiring – please see our jobs page for more details.

We were honored to give a closing keynote talk at MySQL Conference & Expo 2010, and wanted to share the video with you. Why start a new database company? What is RethinkDB all about? What will database technology look like twenty years from now? In this talk we explore these questions, present some of the exciting technology we’ve been developing at RethinkDB, and show how it fits into our larger vision of what database systems may look like in the future.

2010 will be an incredibly exciting year for database technology. The amount of stored information has long been increasing exponentially, presenting unprecedented challenges for modern technology companies. Dropping RAM prices and affordable multicore CPUs have drastically changed the hardware profile of a typical server machine from what it was only five years ago. The emergence of solid-state drives is about to revolutionize database systems, enabling new kinds of applications we can barely envision today.

The database technology we have been using for over four decades is about to become obsolete. At RethinkDB, we’re redesigning databases from the ground up to meet modern data management demands, and to take advantage of the latest advances in hardware. We’re working to breathe new life into database technology, from the low level intricacies of database internals, to high level data access technology.

To help us build a disruptive database system, we’ve raised a seed round of over $1.2 million from a syndicate of some of the best institutional and angel investors in Silicon Valley. The institutional investors that participated in this round include Highland Capital Partners, Avalon Ventures, Andreessen Horowitz, and Charles River Ventures. Our angel investors include Brian Pokorny from SV Angel, Paul Buchheit, Udi Manber, Steve Chen, and Russ Siegelman. Database guru, Jeremy Zawodny, has signed on as an advisor to our company. We’re looking forward to working with these amazing people to build a great product that can solve many of the emerging data management problems.

Over the next eighteen months, we intend to build a world-class team of software engineers to help create the database of the future. We are looking for people passionate about algorithms, computer architecture, and solving challenging problems. If you’re interested in building products that will have huge influence on the software industry for years to come, we’d love to hear from you!

Interested in working at RethinkDB? We’re hiring – please see our jobs page for more details.

April Fools! We aren’t switching to Lisp (as much as we love the language). We couldn’t resist having a bit of fun.

Over the past few months we’ve had many architectural discussions about the future of database technology. It quickly became apparent to us that C++, the language we used to develop RethinkDB, is not sufficiently expressive to build the next-generation database product. We realized that in order to design the database system of the future, we need to use a programming language of the future as well.

We did a quick survey of programming languages and eventually narrowed down our choices to Erlang, Haskell, and Common Lisp. Two years ago, Damien Katz of CouchDB laid out the reasons why Erlang is a poor choice for database products. Many of his arguments resonated with us, and we made a wise decision not to repeat Damien’s mistakes. When we dropped Erlang from consideration, we were left with an impossible choice – Haskell vs. Lisp.

After many heated debates, I remembered a phrase drilled into to me by an ex-coworker I deeply respect. He always said: “Don’t guess. Measure.” We decided to take a measured approach and use data and logical reasoning instead of emotional arguments. Because of the immense expressive power of both programming languages, we could develop two prototypes in a matter of days, and measure the performance with our internal benchmarking toolkit. Mike rewrote RethinkDB in Haskell, and I rewrote it in Common Lisp.

After running both prototypes through our standard benchmarks, it immediately became clear that the Lisp version easily beat the Haskell version by every metric we could fathom. And so, we settled on Common Lisp.

One of the major criticisms of RethinkDB has been the closed nature of the project. Fortunately, this is no longer a problem. The fact is, there are very few developers that understand Common Lisp, so we no longer need to worry about competing companies forking our source code. As we’re preparing to open source our Lisp code base, I’m happy to kick off the effort by listing the last few lines of the source code in this post:

))))))))
)))))))))))))))))))))))))))))
)))))))))))
)))
)

Interested in working at RethinkDB? We’re hiring – please see our jobs page for more details.

For the past few weeks my primary job at RethinkDB has been to hire world-class software developers (we’re still hiring – see our jobs page). Recruiting great people is a difficult process with at least seven components: sourcing candidates, reviewing resumes, doing technical phone screens, conducting technical interviews, closing candidates, extending offers, and keeping candidates happy once they’ve joined. Each component seems simple in principle, but is very subtle in practice. A testament to this is that all software companies aspire to hire only the best people, but in practice very few companies achieve this goal.

I’ve performed many technical interviews before, but always as a small part of a process designed by someone else. I was very excited to start recruiting for RethinkDB because I could finally design the recruiting process from scratch, and fix many of the issues that were previously outside of my control. There are many amazing articles on how to recruit for software companies. Many of the ideas I borrowed for our process come from the articles written by Joel Spolsky, Steve Yegge, Marc Andreessen, Michael Lopp, and Paul English. I won’t attempt to restate all of their advice, which largely became conventional wisdom anyway. Instead, I will focus on pointing out the mistakes I’ve made early in my career, even after reading everything there is to read about hiring. I hope this will add a little more clarity to the subtleties of the process.

Over time, I hope to write about every component of the recruiting process, but for now I will focus on my favorite part – doing technical interviews. In this blog post I will cover what not to do. Later on I will write a follow up post discussing exactly how we conduct technical interviews and what types of questions we ask.

Informal interviews

Almost every great article on interviewing I’ve ever read insists on one thing: that you should establish a formal interview process and stick to it. Despite reading this over and over again, early in my career I did all of the technical interviews informally. In almost every case I can think of, this turned out to be a disaster.

For an inexperienced person, performing a formal interview is psychologically difficult. Early on, I lacked the confidence to place smarter, older, or more experienced people in front of a white board, and ask them tough technical questions. Eventually I learned that it is much easier to do than it seems. The best people not only welcome a challenge, they require it. All the great people I know would never work for a company that doesn’t perform a tough, formal interview because they recognize the company will mostly end up with bad employees. The first time I resolved to do a formal interview, I cautiously asked a candidate who looked twice my age and had a stellar resume to code a binary search. I was pleasantly surprised when he smiled and gladly walked up to the whiteboard.

The only counterexample I’ve seen is Aaron Swartz’s article on hiring. His main argument is that he was never great at solving problems under the social pressure of the interview, and wouldn’t want to ask others to do it too. I agree with Aaron – I am often unable to solve complex problems during the interview because of the nervous pressure. But I don’t want to hire people as good as me, I want to hire people much better than me. It’s a cliché, but firing an employee is so difficult and expensive, that the last thing to be concerned about is a false negative.

Occasionally, some candidates suggest an alternative to a formal process (such as asking them to write a piece of code over a period of a few days, or hiring them temporarily as contractors). This has never really worked for me. Firstly, I can never feel confident enough in the candidate’s abilities without going through all the technical questions. Secondly, this ends up taking a tremendous amount of time, and if the candidate doesn’t work out (which will happen most of the time), you’ve essentially wasted a ton of your time and theirs.

If you decide to go down the path of informal interviews, I’d caution you to be extremely careful. At the very least, make sure you do it because you honestly think it’s a better way to hire great people, and not because you feel insecure about asking intimidating people tough questions. My opinion is that if you end up hiring great people this way, it will probably be an accident.

Making exceptions for technical friends or ex-coworkers

A special case of the above is hiring technical friends, family, or old coworkers, without a formal interview. Unless you’re absolutely certain, beyond a shadow of a reasonable doubt, that they’re one of the best developers in the world, don’t hire them without an interview. It might be awkward to ask a friend or someone you’ve already worked with for two years to go through a formal interview, but it will be much more awkward to ask them to leave when they don’t work out.

This is one of the reasons I prefer not to meet new candidates in an informal setting before the first interview. It establishes a rapport of friendship, and makes it that much harder to ask them to do a formal interview later. If you’re a beginner and lack the confidence to ask a friend to go through a formal interview, try to meet new candidates in a formal setting to avoid having an awkward conversation later. In retrospect, this seems somewhat obvious, but I’ve seen too many smart people skip a formal interview process because they’ve made friends with the candidate. I’d wager a guess that the overwhelming majority of Silicon Valley startups founded by young, first-time entrepreneurs make this mistake, and most of the time it has disastrous consequences.

Avoiding candidates that seem intimidating

It’s funny how many of the rookie mistakes stem from lack of confidence. Early on, I avoided candidates that seemed intimidating either because of their skills, age, or track record. In retrospect, this is the exact opposite of what I should have been doing! Recently, someone who was a very successful manager at Google gave me great advice – if someone does not intimidate you, don’t hire them. Period.

Building an army of clones

Diversity is very much valued in the U.S. Every company aspires to have diverse employees, but this is much easier said than done because true diversity is completely unobvious. You can go out of your way to hire people of different nationalities, skin colors, and cultural backgrounds, but if they’re all Java-only programmers, it won’t do your company much good. We are naturally inclined to sympathize with people that are similar to us, so the intellectual honesty required not to mistake diversity for lack of intelligence is staggering.

Sometimes it is immediately obvious that a company (or an industry sector) is hiring clones of its current employees because its interview questions resemble a secret handshake for a fraternity. When I was working on Wall Street, everyone always asked what C++ keywords “explicit” and “mutable” do. Every Wall Street software veteran knew the answer, but I’ve never encountered a single codebase there that made use of these keywords.

In many cases, the fact that a company hires only very specialized people is hidden by an unconscious linguistic transformation. Many companies today heavily focus on questions from the field of algorithms, but rename them to “problem solving” questions. The field of algorithm design and analysis is an essential pillar of Computer Science, but it is very important not to focus the vast majority of the interview on algorithms alone. It is only one field of many that need to be probed during an interview. Algorithms involve problem solving, sure, but they also involve a tremendous amount of domain expertise in algorithms. Not being able to solve complex and unobvious algorithmic problems doesn’t necessarily make one a poor problem solver – only a poor algorist.

One example of this is Microsoft – a company that at its heyday had plenty of great coders, but very few people with a great sense of user interface design. This likely happened because early Microsoft employees, all brilliant people, mistook lack of algorithms experience coupled with a great sense of UI, for lack of intelligence. In order to avoid this problem I always ask the candidate to teach me about a field I know nothing about. Anything will do – jazz, physics, color theory, nutrition, computer vision, anything hard. If all our interests intersect, I’m probably hiring a clone of myself. If this happens too often, the interview process is likely overfitting, and needs to be redesigned.

Ignoring everything but intelligence

I’m ashamed to admit that early in my career I was a pretty bad employee. My skills and intelligence weren’t an issue – I never encountered a problem at work that I couldn’t solve. But my attitude was. I’d spend days lingering, and I often made my coworkers linger with me. I’d read technical articles all day long, or complain about the poor quality of the code base or the inflexibility of company policies, or talk for hours about how the whole thing would have been much better if it were written in Lisp.

Well, it was fun to read articles on my employer’s dime, the code base usually was horrendous, the policies were terrible, and the whole thing would have been much better were it written in Lisp. But none of that was constructive, or useful, or helpful to my employer or me. In retrospect, I can’t believe how incompetent I was, despite my skills and (hopefully) intelligence.

Intelligence means nothing without solid work ethic and a killer drive to accomplish useful things. Many young, intelligent people feel a sense of entitlement because the job market is heavily stacked in their favor. Smart people should feel entitled, but if this goes out of reasonable proportions, it can be a very poisonous mindset to be in. This is very difficult to recognize during the interview, so try to pay attention to little hints that might indicate the candidate has raw intelligence that isn’t backed by good old professionalism. Steer clear of such candidates no matter how smart they are, or you will have a much bigger problem on your hands later on.

Letting the job market set the anchor

In his article The Guerrilla Guide to Interviewing, Joel Spolsky says:

At the end of the interview, you must be prepared to make a sharp decision about the candidate. [...] Never say “Maybe, I can’t tell.” If you can’t tell, that means No Hire. It’s really easier than you’d think. Can’t tell? Just say no! If you are on the fence, that means No Hire. Never say, “Well, Hire, I guess, but I’m a little bit concerned about…” That’s a No Hire as well. Mechanically translate all the waffling to “no” and you’ll be all right.

In my experience, this is much harder to do than Joel might lead you to believe, because of a psychological effect sales people refer to as “anchoring”. In sales, naming a price first is called setting the anchor, because this number will affect the psychology of the counterparty for the rest of the negotiations process. If you offer a software license for $50,000 per year, people might try to negotiate you down to $25,000 per year, but it wouldn’t even occur to them to offer you fifty bucks.

During the recruiting process, you’re entering implicit negotiations with the job market, and the first few candidates it throws at you will act as the anchor. Chances are, the first few candidates will be mediocre, so when you see someone who’s a lot better than mediocre (but still nowhere near stellar), you’ll automatically get excited about hiring them.

Over time, the pressure to hire people in order to deliver the product will force you to second guess your standards. You’ll start wondering if the interview questions you’re asking are too hard, or if your standards are impossibly high. And you will hire mediocre employees who will hire more bad people, who eventually will wreck your company. The problem seems easy to avoid if you know about it, but in practice it’s very difficult to fight your own psychology.

So set the anchor first, before you even see the first resume. If you’re building a software startup, recognize that you’re competing with everyone in the world, and can only win if you first employees are the best in the world at what they do. Not the “Northeast division” best. The Olympics best. Theoretically, it’s possible that your standard is unreasonably high, but in practice people almost always have the opposite problem.

I look to Bell Labs for inspiration. At its peak, the folks at Bell Labs developed radio astronomy, the transistor, the laser, information theory, the C programming language, and the UNIX operating system. These are the kinds of people you should be trying to hire. Think Dennis Ritchie before he developed the C language. Think Claude Shannon before he invented information theory. When in doubt, ask yourself: “would this person have been good enough to be hired for a junior position at Bell Labs during its peak?” If the answer isn’t a resounding yes, it’s a No Hire.

Knowing about these mistakes helped us tremendously to design a balanced hiring process for recruiting great candidates. In the next post, I will cover the structure of the actual interviews, our philosophy for picking technical questions, and the exact types of questions we ask every candidate.

Interested in working at RethinkDB? We’re hiring – please see our jobs page for more details.

Thanks to Ben Kudria and John Rizzo for feedback and many great suggestions on how to improve this post.