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.

TopCoding

"An expert is a person who has made all the mistakes that can be made in a very narrow field." -- Niels Bohr

An error-prone physicist

I've been thinking about mastery lately, after reading books like Outliers and discussing Talent is Overrated with my brother.  The basic premise of the latter is that mastery is achieved by many hours of mindful practice of things that are within your grasp.  At any point in time, there are

1. things you can already do,
2. things you could do with some practice, and
3. things you might eventually be able to do but are not within your grasp yet.

Since time is a precious resource, you should avoid either striving for things far outside your ken or sticking with what you already know.  You should try to attain what is within your reach and will cause you to improve.

How do you improve as a programmer?  For the last few months, I've been practicing on TopCoder.  TopCoder is a free programming competition site with a number of areas for competition, though it centers around algorithms.  I had tried it when my grad student advisor first told me about it around ten years ago, but my initial and incorrect impression was that it was only for can't-see-the-forest-for-the-trees hackers who loved writing cryptic and nested for loops and who never had any other plans for the evening.  To be sure, doing the competitions and practice problems is a bit like practicing musical scales, but if you're serious about your craft, then you should be serious about practicing.  By and large, the kinds of problems you can find at TopCoder will challenge you in ways that you might not get at work, and they let you do it in a focused manner.

TopCoder's algorithm problems should help you practice the mapping of a real problem to algorithms and data structures, which is really the heart of what it means to be a programmer.  I suggest starting with Division II problems.  I didn't realize there was a difference at first and was highly discouraged by a Division I problem that eluded me for hours.  Each division has easy, medium, and hard problems which you can do at your leisure.  I've been practicing using Java, since I've been spending more time lately with the language and want to learn it well, though it seems like the top ranked programmers use C or C++.  Make sure you look at other people's code after you've tried a problem.  I've been following a guy named DoublePointer, who also programs in Java, and seems to have done every single problem.

I'll admit that some of the worse problems--or perhaps the problems I like the least--are the ones that admit of no answer besides many nested loops where you have to keep track of multiple indexes.  Solving any problem will involve some measure of implementation and some of algorithm design, but these tend too much towards the former.  In general, however, I think the problems on TopCoder are excellent.  Not only do they let you practice at a level within your grasp, but you get to learn about all kinds of subjects, like lotteries, tire rotation, and Incan numbering systems.  I recommend trying a practice set each week.  That should only take an hour or two.

In the end, mastery is all about doing things you can't quite do, which means making a lot of mistakes.  Practice makes perfect because it's in practice where you get to screw up when no one is looking.  I give many thanks to TopCoder for the chance to mess up and learn from what I've done  wrong.  My TopCoder profile consists entirely of the Bohr quote above and is my inspiration to keep at it when I get frustrated by a tough problem.

Logarithm Confessional

The truth is, I never really understood logarithms.  Like many students, I was just going through the motions--memorizing the rules but never having them really click.  Whenever I heard about people using logarithms and slide rules to multiply numbers in the days Before Calculators (BC), I was confused.  In college, I understood that algorithms with logarithmic growth or superlinear growth were better than quadratic ones, but I didn't have a good intuition about exactly how much better they were.

Does it matter?  I've come to think that it's essential for developers to have a good sense of logarithms and the other functions that describe algorithms.  Even if you're not writing many algorithms from scratch, it's important to know what's going on underneath the hood when you search through a database or use a hash table.  Even as computing power has become cheaper and cheaper, you can't always throw hardware at a problem.

I think an example helps.  Let's say you want to find a name in a phone book, and let's say there are 1,000,000 names in the phone book.  What if the names in the phone book were in random order?  In the worst case, you might have to look at all 1,000,000 names.  If it takes 1 second to look at 10 names, this could take around 28 hours.  In the best case, you only have to look at 1 name, but on average you'll have to look through 500,000.

Luckily in 1604 Robert Cawdrey invented alphabetical ordering.  If the phone book is in alphabetical order, how long would it take to find any name?  The answer is 2 seconds, if you flip to the middle of the book and keep dividing it in half until you find the name (and if you can still look at 10 in 1 second).  The first name you look at lets you ignore 500,000 other names.  The second name lets you cut out another 250,000.  Since we divide the number of names we're considering is cut in half each time, this is a logarithmic algorithm, and it will take 20 steps at most to find any name.  This can be shown by the fact that 2²⁰ = 1048576 or that log₂1048576 = 20.

What's amazing is that it hardly takes any more time to find a name as the phone book gets bigger and bigger.  It would take 3 seconds to look through 1,000,000,000 names and 4 seconds to look through 1,000,000,000,000.  Logarithms are the inverse of exponents.  Everyone knows that exponential growth is really fast growth.  Logarithmic growth is really slow growth.  In fact, it's almost constant.

This example shows why it's important to try to find algorithms that take a logarithmic amount of time to complete as data size increases.  The table below shows common algorithmic patterns.  For example, trying to compare all possible moves in a chess game could take longer than the history of the universe, since the number of boards increases exponentially.  It's hugely important to find an nlogn approach over an n² one.  How huge?  32 years if you're working with 1,000,000,000 data points.

Commit it to memory!  And read Steve Skiena's book

If you are like I once was, don't curse your pathetic existence.  Humans are simply not good at understanding exponential or logarithmic growth--just like we're not good at memorizing random sequences of numbers though we excel and remembering spatial information (mental athletes typically turn memorization problems into spatial ones).  It makes no sense that $1.00 compounded at 10% annual growth for 100 years somehow becomes $13,780.61.  We can work hard to develop an intuition for such things, but it's easy to forget.  What helps me is revisiting tables like these from time to time.

The Clouds

I am walking in the air, and speculating about the sun.
-- Socrates, in Aristophanes' The Clouds

Self-explanatory.

What's wrong with having your head in the clouds?  For starters, you might fall into a well.  That's what happened to the ancient Greek philosopher Thales while he was gazing at the heavens.  Aristophanes ridiculed Socrates in a satire called The Clouds for speculating about abstract nonsense without understanding anything about the here-and-now.

Slightly more recently, 'The Cloud' has arrived to save us from all earthly ills.  Got a problem scaling?  Move to the cloud.  Want to reduce cost?  Go to the cloud.  Disaster recovery?  Cloud.  High availability?  Cloud.  Yet, the cloud can't really be a cure-all.  It may be appropriate for your needs, but this has to be evaluated given an understanding of how your cloud implementation will work.  If your number one problem is performance or security, the cloud is probably not going to help.

There are many 'clouds' or high-level cure-alls available to developers today.  For example, I've been learning the Spring Framework, which is a Dependency Injection (DI) framework.  DI is a form of Inversion of Control (IoC), in which object coupling is not known at compile-time but rather is determined at compile-time.  Using a DI framework, you can build interfaces, inherit classes from them, and control application flow using configuration files and annotations (like @inject).  During development, you can stick to the pure work of thought--programming, that is--without having to worry so much about the nuts-and-bolts of connecting classes.

DI frameworks like Spring are just one more layer of abstraction (or one more cloud) that let us focus on business logic rather than implementation details.  And, just like other layers of abstraction, they're a double-edged sword.  Dependency injection isn't always a great idea, such as if your interfaces are likely to change often.  Dependency information has to be stored somewhere, after all.  Enterprise frameworks tend to give you flexibility for the price of code bloat and complexity.  In my time, I've seen programming become ever more complex, but, at the same time, ever more like plumbing.  Frameworks like Spring, Rails, and .Net's Entity Framework let you quickly build applications.  But they don't prevent you from doing very stupid things if you don't know how they really work.  ORM libraries are great, for example, until you have to scale.

For this reason, I've been brushing up on my data structures and algorithms.  It's easy to think such things don't matter.  Plenty of people get by without earning computer science degrees.  And who cares if a client-side algorithm is O(N^2) when the database is orders of magnitude slower?  You might concede that algorithmic theory is worth studying only to develop certain intuitions about processing time, memory size, problem size, and algorithmic complexity, which is certainly true.  But I think it's useful to revisit data structures and algorithms once in a while to stay grounded in reality.  If you're only doing high-level plumbing, you have your head in the clouds. 

What is Code?

You've probably heard the term 'knowledge worker.'  It's one of those terrible euphemisms like 'sandwich engineer.'  But, for programmers, I think it's actually apt.  What are the inputs, outputs, and substance of our work?  Knowledge.

Andy Hunt and Dave Thomas, the pragmatic programmers, explain:

"As [programmers], our base material isn't wood or iron, it's knowledge. We gather requirements as knowledge, and then express that knowledge in our designs, implementations, tests, and documents.  We collect, organize, maintain, and harness knowledge. We document knowledge in specifications, we make it come alive in running code, and we use it to provide the checks needed during testing."

All craftsmen work in ideas.  But code might be the closest thing to pure thought that a person can build in.

What does it mean?

Painting, for example, manifests ideas, but you have to bring those ideas to a work when you view it.  Medieval paintings of Christ or Neoclassical paintings like the Oath of the Horatii make sense only if you know the story.  This is also true of contemporary art.  Most exhibits require a write-up in order for them to be comprehensible.

The thing about code is that it itself provides the background.  You need to bring an an understanding of syntax, but not semantics.  Documentation or knowledge of the industry should help you grasp the knowledge contained in code, but the code can stand alone and manifest its ideas clearly--if you know how to read it, of course. 

Interestingly, both written language and algorithms were invented at around the same time in Mesopotamia.  (It's also interesting that written language was invented as a tool of commerce and state power, but that's another post).  The word 'logic' comes from the Greek 'logos,' which means both 'word' and 'reason'.

It's all Sumerian to me.

In a program, we try to implement business logic with application logic.  I used to thing both terms were buzzwords, but I particularly like 'business logic' now.  It makes clear that there is a system of interconnected ideas that code should express.  In fact, one of the hardest things we have to do is to get users to come up with requirements that are logical.

Of course, things weren't always this good.  Object oriented programming and relational databases let us code in terms of objects and relations, which are self-defining.  This is much better than pushing and popping stacks, which have a tenuous connection to any business reality.  Still, even objects and relations have their limitations.  With all the advances in coding productivity in the last twenty years, I'm excited to see what new thought patterns we'll be able to have in the next twenty.

Algorithms, AI, and Emergence

The story about why Google overtook AltaVista is a fascinating one. Up until Google, there were two ways of accessing web pages. The first was Yahoo!'s portal approach, in which a single authority determines the web pages worth viewing, and you trust the experts to have done their work. You want to read sports news? Go to Yahoo! and then the Sports category.  Simple.

Lightning fast!

The obvious problem is that the experts at Yahoo! might have missed something. For this reason, I always preferred AltaVista (or WebCrawler, before that), which used an indexing approach, similar to an index in the back of a book. AltaVista used simple programs to search for key terms in a page's text and metadata and then aggregate that data in a way that later could be easily matched and ranked according to search terms you fed it.

AltaVista was better than the alternatives for a few years, but it had trouble determining relevance. If you're searching for a recipe with certain ingredients, you don't want just any recipe; you want the best recipe. If you want to read about last night's game, you don't want just anyone's commentary; you want the best commentary.

Enter Google's PageRank algorithm. PageRank takes authority into account, like Yahoo!, but it doesn't require a single source of information, like AltaVista. Pages that have more links to them are ranked higher than ones that don't. And the pages that link to these pages give an even higher ranking if many pages link to them. PageRank lets you find what the most important people are talking about.

.304 (at the center) is the highest page rank in this contrived example

It's a bit more complicated than this, but what is revolutionary here (and I use the term revolutionary sparingly, unlike, ahem, Apple) is that Google's algorithm did not try to reproduce the intelligence of the web that was already out there. Instead, it tried to capitalize on the accumulated intelligence of millions of individuals who had made a simple choice: to link to or not link.

Linking is a binary action that, when accumulated into a large network of linked pages, allows for an emergent kind of intelligence. Emergence happens when a simple set of rules add up to something greater than their parts. Ants, for example, are very stupid individually, but when they signal to each other using pheromonic rules that have evolved, some very complex behavior emerges. Similarly, neurons in themselves have no intelligence. They can either fire or not. But when you have a few hundred billion of them, you're on your way to self-consciousness. Markets too display emergent phenomena when the buying and selling of millions of people shape the direction of societies.

PageRank is just one of a few algorithms that have begun to capitalize on emergence. For decades, it was assumed that language translation software would have to know the rules of grammar of the source and destination language in order to decode and encode meaning appropriately. This was a miserable failure. The success of modern translation algorithms is that they use statistics to compare millions of existing translated documents. The algorithm knows that, for example, it has seen 'Je suis' much more frequently than 'Je es'.  It doesn't need to know anything about grammatical rules.

An ant fugue

The problem with algorithms like PageRank is that they are parasitic upon an existing emergent system, whether it is a network of linked pages or a network of translations. The algorithms themselves are not emergent. They require human maintenance and tweaking, and they lead to people gaming the system. PageRank spawned web spam, in which people post links to sites in order to increase their ranking. This is why it's now only one of 200 or so indicators of rank for Google. The whole point of Gödel, Escher, Bach is that intelligence cannot be decomposable into a set of rules. Algorithms like PageRank are still just that.

While we've made some tremendous advances in machine learning by fitting algorithms to emergent systems, the future of AI can't be algorithmic. It can't be only a set of rules. But it might be a set of rules that, when used in aggregate, lead to emergent and artificial intelligence. What set of rules could be this flexible? Perhaps only the binary links of neural networks.