☕ Storing billions of messages

How Discord stores billions of messages with Cassandra. Plus, a top down and bottom up dynamic programming solution to our last coding interview question!

Hey Guys,

Tech Snippets

• How Discord Stores Billions of Messages

  • This is a blog post from 2017 on how Discord stores billions of messages (hundreds of millions of messages generated a day).

  • They started with MongoDB in order to iterate quickly but they knew they would have to find something scalable later.

    • “This is part of our company culture: build quickly to prove out a product feature, but always with a path to a more robust solution.”

  • Database reads were extremely random and the read/write ratio was approximately 50/50

    • Users need the ability to view their mentions for the last 30 days and then jump to that point in history for the discord chat. This means lots of random reads!

  • The Discord team decided to go with Cassandra, an open-source NoSQL database. They talk about why Cassandra was a good choice and what specific features they were looking for.

  • The post goes into data modeling, performance and launching a new database!

Interview Question

Write a function that sorts the elements in a stack so that the smallest elements are on top.

You can use an additional temporary stack, but you cannot copy the elements into any other data structure.

The stack supports the following operations

• push

• pop

• peek

• isEmpty

We’ll send a detailed solution tomorrow, 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

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 refresher, here’s the last question

You are walking up a staircase with n steps.

You can hop either 1 step, 2 steps or 3 steps in a single time (you have long legs).

Write a function to count how many possible ways you can walk up the stairs.

Solution

We can solve this question with Dynamic Programming.

If we have n steps, then the number of ways we can walk up the stairs is (n - 1) + (n - 2) + (n - 3).

Therefore, with top down DP, we can just recursively call each individual function and add them together to get our result.

Our base case will be if n == 0, in which case we just return 1.

Here’s the Python 3 code.

@lru_cache # Python decorator for Memoization
def countWays(n):
    if n < 0:
        return 0
    elif n == 0:
        return 1
    else:
        return countWays(n - 3) + countWays(n - 2) + countWays(n - 1) 

For Bottom Up DP, we’d typically use a memo table.

However, in this question we’re just accessing the last 3 values (n - 1, n - 2, n - 3).

Therefore, we can solve this question using constant space by just using 3 variables to keep track of those values. We don’t have to use an entire array to maintain our memo table.

Here’s the Bottom Up DP code.

def countWays(n):
    if n < 3:
        return n
    elif n == 3:
        return 4
    first = 1
    second = 2
    third = 4

    for i in range(3, n):
        first, second, third = second, third, first + second + third
    
    return third

The time complexity is O(n) and the space complexity is O(1).

---