Google Docs

video locked
Enroll to watch

48 mins

Chapters
About
Discussion0
Notes
Be the first to start a conversation!

Google Docs Requirements

Google Docs is an app for creating and storing documents, and multiple people read and change a shared document in real time.

The features:

  1. Creating, reading, updating and deleting documents: the CRUD model.
  2. Sharing, with permissions for reading and editing. A shared document sends a notification through email.
  3. Export as a PDF, which is not considered here.
  4. Version history, with a diff checker between two versions.
  5. Spell checking. The concern is the inputs a spell checker needs as a black box.
  6. Comment support for multiple collaborators.
  7. Offline support: changes made offline for a couple of days are sent in bulk.

Storage and sharing are the core. Version history and offline support are solved with them, and notifications and comments are not core features.

The core problems point to collaboration, which is a challenge in a distributed system for two reasons:

  1. Concurrency. Two people do operations without being aware of each other, and the conflict has to be resolved.
  2. Data consistency. Multi-region support keeps multiple copies of a document around the world.

Document Schema

A document is stored as an ID, an author and the data, with metadata such as a creation timestamp around it.

The data holds all the characters and is of type text. The author is a varchar. The ID is randomly generated and is the primary key.

One design splits this into two tables. Doc metadata holds the ID, the author, the timestamp and the other metadata in a relational database. Doc content holds the ID and the content in a NoSQL database. Relational queries run on the metadata table.

The split turns into a mess:

  1. The metadata is hard to fix, so the table takes many alter queries.
  2. Finding the last 10 documents of an author reads IDs from one table and fetches them from the other.
  3. Such a join, across a NoSQL database and a relational database, takes forever.

The design taken keeps one table of ID and data. The data is a JSON object whose key value pairs hold the author, the timestamp, the rest of the metadata and the contents.

Storing Documents

A document is stored with a limit on its size, because a document of arbitrary length is expensive to read and to update.

A very large document could be stored as a linked list of pages: page 1, page 2, page 3. Each page ends with the ID of the next one. The file system picks up pages one after another until it reads an ID of zero.

The problems:

  1. Arbitrary length. A person who does not want the system to succeed makes a document of 1 million pages.
  2. Additions. 10 more lines on page 3 push content to page 4, which may overflow too.
  3. Deletions. Deleted lines leave blank pointers and dead nodes.

This is complex in a collaborative environment, so every application limits the size. In Google Docs the max document size is 50 MB, or 1 million characters.

The limit is the max size that the text column allows. The database is most likely Cassandra, or Amazon DynamoDB, or a custom in-house key value database.

Version History

Version history stores each version of a document as its own row, keyed by the document ID and the version number.

Document 1 holds ABC at version 1, AB at version 2 and ABD at version 3. The ID and the version number are merged into a single unique key.

Most reads ask for the latest version, so the versions are kept in a separate table. The document table holds one entry for each ID, replaced on every update, so reads are quick. A request for a specific version goes to the version table.

A version at every keystroke is wasteful. A cron job takes snapshots instead:

  1. The cron job reads the document.
  2. If the contents differ from the last version, it stores them under the next version number.
  3. If they match, nothing is stored.

A cron job that checks all the documents every half an hour is a thundering herd. With a last modified timestamp on each document, the cron job runs every minute and picks up the documents modified in the last half an hour.

Avoiding Thundering Herds in Crons

A cron job run in a naive way performs no tasks until the cron time hits and then performs them all together: a thundering herd.

With x tasks to be done in a time y, the aim is x by y tasks processed per second. The naive cron job instead puts a spike on the server, and other requests stop being served.

The fix is inspired by hashing. Take 3000 documents and 30 minutes:

  1. A document's ID is divided by 30 and the remainder is its cron index. ID 37 gives 7 and ID 30 gives zero. The index is at most 29.
  2. At minute zero the cron job processes the documents with index zero: IDs zero, 30, 60. At minute one it processes 1, 31, 61.

The documents are broken into 30 pieces, and each piece is picked up by one cron job that runs every 30 minutes. One big cron job becomes 30 small ones. The volume of tasks is the same and the peak is reduced, at the cost of some software complexity.

Compression and Caching

Storage cost is reduced by compressing documents, and compression has a processing cost.

The compression is lossless, because lossy compression is devastating to people who work on the document professionally. Huffman codes are one choice, and there are better algorithms for text.

Every write compresses the document before saving it to the database. Every read decompresses it before serving.

A hybrid approach keeps the latest version, Vn, in its full form, because users are working on it. It is fast to access. The versions V1, V2 and V3 are compressed and kept in cold storage, which is cheap.

Writes are sped up by storing operations as a log beside the copy of the latest version:

  1. The copy is ABC.
  2. Add XY and delete BC are stored as two operations.
  3. A get takes the copy, applies the changes yet to be made and serves AXY.

Reads become compute intensive and many write operations are saved. The current document is eventually consistent. Going through the list of changes gives perfect consistency.

Concurrent Writes with Locks

A concurrent write is two people making changes to the same document at the same time.

A document holds ABC. User A adds D to the end and expects ABCD. User B deletes B and expects AC. The operations can reach in any order, and both users are eventually served ACD.

  1. Pessimistic locking. Add D takes an exclusive lock on the document. Delete B fails to acquire the lock and waits till ABCD is written, then makes it ACD. Multiple writers cannot write at the same time, so it is too slow.
  2. Optimistic locking. Delete B does not wait. Each writer takes a copy of the document, giving ABCD and AC, and both try to write. One wins, and the other cancels its operation and retries or fails. Copying the entire document is expensive.

Locks do not work, so the operations are merged instead of the state: ABC with add D and ABC with delete B merge into ACD. Two problems remain: how the operations are ordered, and who defines a complex operation such as bolding.

Operational Transform Overview

Operational transform is an algorithm that reconciles two copies of a document by shifting the index of each operation for the operations the other copy has already applied.

A document is ABCD. One copy deletes at index 1 and becomes ACD. The other adds E at index 2 and becomes ABECD. An operation is defined by its index, not its character.

The naive way performs each operation on the opposing copy:

  1. Adding E at index 2 of ACD gives ACED.
  2. Deleting at index 1 of ABECD gives AECD. The copies do not match.

The delete pulled every index after it back by one. So the add is applied at index 1, and both copies are AECD. Google Docs most likely runs operational transform, which makes more sense with a server.

A CRDT, a conflict-free replicated data type, is peer-to-peer: the copies share their data and are eventually consistent, with no central authority.

The differences between two versions of a document come from the Myers algorithm, which Git uses. The longest common subsequence is a simpler idea.

Permission Management

Permissions on a document are held by a separate service, the permission manager, and not in the document's own table.

The permission manager looks at every user request and decides whether it is valid.

For each document ID it stores key value pairs of a user ID and an access:

  1. A private document has one pair: user 123 is the owner. Any other user gets an error.
  2. To share with user 124, a request to update the permission goes through the gateway to the permission manager, which appends 124 with read access. A write from 124 then fails.
  3. Link sharing for reads is a pair where star, meaning anybody, has read access.

If any pair satisfies the permission the operation requires, the permission manager returns yes. Creating a document also goes through it, and the document is then added to the document service's database.

With the permission manager in between, the gateway is decoupled from the document service. Each service scales independently.