How Google Docs Works

Here's an interview question for you: How would you implement an online word processing system like Google Docs?

This isn't too complicated if people are working on different pieces of a document or if they work at different times.  But pretty soon you'll start thinking about concurrent edits, lag, network failures, and the like.  What happens when two people edit the same line at the exact same time?  What if one person deletes a line above one that another person is editing, but the message takes a while to get there?

If you think about this a while, you may come up with a solution similar to the following, which uses vector clocks.  1) Each person keeps a clock and 2) each event is associated with a new tick on the clock so that 3) at any time the state of a document can be constructed from the events executed in temporal order.  Making a change to the document or receiving changes from another author causes an author's clock to increment.  See the diagram below, in which three authors edit the same document.  You can see the causes and effects of event B4.

C makes a change.  B gets the change and propagates the change to A.  A and B make changes at the same time and propagate to B and C, respectively.  Then B and C make changes at the same time and propagate to C and A, respectively.  Then C makes a change and forwards to A.  At the end of this timeline, A and C have the latest changes, but B does not.

Is it OK that B doesn't have the latest changes?  That depends on the system you're building.  You have to make a choice between multiple authorship and transactional integrity.  (More generally, there's a trade-off between consistency, availability, and partitioning).  Word-processing is typically not mission-critical.  It's not worth the delays that would be incurred by ensuring that all changes are propagated to all authors.

Although many people think that financial transactions require ACID transactions, ATMs use vector clocks in much the same way.  This is because ATMs are not always connected, and it takes time to sync them.  If you and your partner drain a joint account at the same time, you both get the money.  When the systems eventually talk to each other, they agree that the account is overdrawn, and you get an overdraft fee (or worse).  Debits and deposits are like edits to a shared document.  You just have to add them up to get the current balance of an account.

This is a bit of a simplification, but you get the idea.  Note that you must have some method for resolving conflicts.  If A and B edit the document at the same time and propagate changes to C, C must decide what to do.  If A and B both add a title to the first line of the document, for example, C could arbitrarily put B's title on the first line and decide that A's title should go on the second line.  At a bank, you have overdraft fees and fraud alerts.  You'll have to try to resolve conflicts in ways that aren't too confusing to users.

There are some other things to think about.  For example, at some point the clocks need to be reset and the systems synced.  This used to be more noticeable in Google Docs when you'd get a syncing message.  Also, when you get a lot of authors (or servers that need to be synced), things can get pretty complicated.  But, in situations in which you have a relatively small number of people who can make changes and in which response time (availability and partitioning) is more important than consistency, you may need to use vector clocks.

To read more, check out Wikipedia's article on operational transformation.

Erlang and Concurrency

I was excited to learn me some Erlang, since the mysterious language has recently gotten a lot of press for being the tool of choice for Facebook Chat. It's often cited as a way to break the performance barriers of multi-processor architecture and mainstream programming languages that use multi-threading. A program is as fast as its slowest part, and this is typically the resources shared by threads. These resources also require some fancy coding techniques to ensure their integrity. And, of course, the more complicated the code, the more likely it is to break and be difficult to maintain.

Erlang's simple model is based around processes that pass messages to each other, crash, and respawn very quickly. After compiling a module, you spawn a process using:

handle = spawn(module, function, parameters).

The process is defined as a function that shreds out the parameters with a series of case statements:

function -> receive
	{parameter1} ->
		%do something
	{parameter2} ->
		%do something else
	Unexpected ->
		%handle exceptions
end.

You can pass messages to a spawned process using:

handle ! parameters.

This architecture allows you to quickly create, monitor, message, and respawn processes whenever they fail. Because Erlang is a functional language, there are no variables or any other shared resources that can form a bottleneck between processes liked global variables. Processes communicate using messages, and these can be processed asynchronously or independent of any other processes.

Erlang's concurrency model is similar to Service Oriented Architecture, except that concurrency is built into the system at the lowest level, not added on top of an Object Oriented framework and requiring several other technologies. Note also that concurrency is very different from parallelism. If you need to crunch a lot of numbers, you'd need to use a parallel processing system, not a concurrency model.

Erlang is best for soft real-time, distributed, and highly-available applications that could be composed of message-handling systems, like Facebook Chat or low-level telecommunications software. (These are very specific applications that I tend not to think about very often, so I don't have a mock-up like I have tried to have in other posts.)

For these reasons, Erlang is not a cure-all for performance-related problems, though it is important to note that there are limits to any concurrent or parallel approach. Amdahl's law states that even with 95% parallelism, performance benefits will quickly plateau as the number of processors increase.  E.g., if your program takes 20 seconds to run, and 1 second of it cannot be parallelized, the least amount of time it could run in is 1 second.  No matter how many processors you add, you cannot break that 1 second barrier without further parallelizations.


As a side note, I had not heard of Amdahl's law before researching Erlang. Interestingly, I also just learned of IBM's SyNAPSE project, which has the grand aim of functionally replicating the human brain. One argument for a new hardware architecture based on neural networks is that, though the firing of individual neurons is slow, the massively parallel processing power of a brain more than makes up for the performance of any individual part. I'm not sure how this argument stacks up against Amdahl's.

I'll be looking for opportunities to write me some Erlang, but--given my own limits to processing in parallel--this may not be any time soon.

Links:
-Erlang home page
-Eugene Letuchy's notes on designing Facebook Chat
-Learn You Some Erlang, a free online book