How Notion sharded their Postgres Database

Hey Everyone,

Today we’ll be talking about

  • How Notion sharded their Postgres databases

    • Why they sharded

    • Picking a shard key

    • Database Migration

  • Plus, a couple awesome tech snippets on

    • How Bash works under the hood

    • WebRTC explained

    • Hands on Web Assembly

We also have a solution to our last coding interview question on arrays, plus a new question from Microsoft.

Quastor Daily is a free Software Engineering newsletter sends out FAANG Interview questions (with detailed solutions), Technical Deep Dives and summaries of Engineering Blog Posts.

Notion is an app that is meant to serve as a personal (or corporate) workspace.

You can store notes, tasks, wikis, kanban boards and other things in a Notion workspace and you can easily share it with other users.

If you’ve been a Notion user for a while, you probably noticed that the app got extremely slow in late 2019 and 2020.

Earlier this year, Notion sharded their Postgres monolith into a fleet of horizontally scalable databases. The resulting performance boost was pretty big.

Sharding a database means partitioning your data across multiple database instances.

This allows you to run your database on multiple computers and scale horizontally instead of vertically.

When to Shard?

Sharding your database prematurely can be a big mistake. It can result in an increased maintenance burden, new constraints in application code and little to no performance improvement (so a waste of engineering time).

However, Notion was growing extremely quickly, so they knew they’d have to implement sharding at some point.

The breaking point came when the Postgres VACUUM process began to stall consistently.

The VACUUM process clears storage occupied by dead tuples in your database.

When you update data in Postgres, the existing data is not modified. Instead, a new (updated) version of that data is added to the database.

This is because it’s not safe to directly modify existing data, as other transactions could be reading it.

At a later point, you can run the VACUUM process to delete the old, outdated data and reclaim disk space.

If you don’t regularly vacuum your database (or have Postgres run autovacuum, where it does this for you), you’ll eventually reach a transaction ID wraparound failure.

So, you must vacuum your database or it will eventually fail.

Having the VACUUM process consistently stall is not an issue that can be ignored.

Application-Level vs. Managed

Sharding can be divided into two approaches

  • Application-Level Sharding - You implement the data partitioning scheme in your application code. You might direct all American users to one database and all Asian users to another database.

  • Third-Party Sharding - You rely on a third party to handle the sharding for you. An example is Citus, an open source extension for Postgres.

Notion decided to go with Application-Level sharding.

They didn’t want to go with a third party solution because they felt it’s sharding logic would be opaque and hard to debug.

Shard Key

In order to shard a database, you have to pick a shard key. This determines how your data will be split up amongst the shards.

You want to pick a shard key that will equally distribute loads amongst all the shards.

If one shard is getting a lot more reads/writes than the others, that can make scaling very difficult.

Notion decided to partition their database by workspace. Workspaces are the folders that contain all the pages, tasks, notes, etc.

So, if you’re a student using Notion, you might have separate Workspaces for all your classes.

Each workspace is assigned a UUID upon creation, so that UUID space is partitioned into uniform buckets.

Each bucket goes to a different shard.

How many Shards?

Notion ended up going with 460 logical shards distributed across 32 physical databases (with 15 logical shards per database).

This allows them to handle their existing data and scale for the next two years (based off their projected growth).

Database Migration

After establishing how the sharded database works, you still have to migrate from the old database to the new distributed database.

  1. Double-write: Incoming writes are applied to both the old and new databases.

  2. Backfill: Migrate the old data to the new database.

  3. Verification: Ensure the integrity of data in the new database.

  4. Switch-over: Actually switch to the new database. This can be done incrementally, e.g. double-reads, then migrate all reads.

Tech Snippets

  • How Bash works under the hood - This is a great post on the architecture of Bash. It goes through the major components: input processing, parsing, word expansions / other command processing, and command execution.

  • Hands-on WebAssembly - This is an awesome tutorial that gets you started with WebAssembly. The only prerequisite is some general knowledge about web development. Crack out your favorite code editor and learn some WASM!

  • WebRTC explained - This is a free book that goes through WebRTC. It’s written by the maintainers of WebRTC and it talks about the protocol and APIs.

Interview Question

You are given the head of a linked list.

You are also given an integer n.

Remove the nth node from the end of the linked list and return it’s head.

Example

Input: head = [1, 2, 3, 4, 5], n = 2

Output: [1, 2, 3, 5]

We’ll send the solution in our next email, so make sure you move our emails to primary, so you don’t miss them!

Gmail users—move us to your primary inbox

  • On your phone? Hit the 3 dots at the top right corner, click "Move to" then "Primary"

  • On desktop? Back out of this email then drag and drop this email into the "Primary" tab near the top left of your screen

  • A pop-up will ask you “Do you want to do this for future messages from [email protected]” - please select yes

Apple mail users—tap on our email address at the top of this email (next to "From:" on mobile) and click “Add to VIPs”

Previous Solution

As a reminder, here’s our last question

You are given an integer array called nums. You are also given an integer called target.

Find 3 integers in nums such that the sum is closest to target.

Return the sum of the 3 integers.

Each input will have exactly one solution

Example

Input: nums = [-1, 2, 1, -4], target = 1

Output: 2

The sum that is closest to the target is (-1, 2, 1)

Solution

We can solve this question by first sorting nums from smallest to greatest.

After sorting, we’ll iterate through all the integers in nums.

Our loop counter will be the variable i.

nums[i] will be one of the numbers in our sum.

Now, we have to find the other 2 numbers greater than nums[i] that minimize the distance between sum and target.

We do that with two pointers, L and R.

L points to nums[i + 1] and R points to the last number in nums.

Now, we take the sum of the integers at i, L and R.

If the sum is closer to the target than any of the previous sums, then we’ll store this sum as our closest.

If the sum is greater than our target, then we’ll decrement R. This will make the sum smaller.

If the sum is less than our target, then we’ll increment L. This will make the sum larger.

We’ll end the current iteration when L is greater than or equal to R.

Then, we’ll increment i.

After the for loop ends, we can return the closest sum.

Here’s the Python 3 code.