# ☕ 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)`

.

## Create your profile

## Only paid subscribers can comment on this post

Log in## Check your email

For your security, we need to re-authenticate you.

Click the link we sent to , or click here to log in.