Cassandra Deep Dive with an Ex-Meta Staff Engineer

[00:02] Today we are going to be deep diving into Cassandra and this is specifically design interview. And so I'm going to give you the minimum amount of information you need in order to present this information in an interview, but

[00:14] interviewer probes, you can justify your decisions accordingly. So we're going to try to walk that fine line. Now at a high level before we get started, Cassandra is a distributed NoSQL database and it's designed for

[00:27] handling massive amounts of data across many different servers without any given high level summary. Importantly, it was created by Facebook in 2007 by Avinash Lakshman. There's your guy right there.

[00:41] important? Well, he's important because he was also the co-creator of Amazon's Dynamo. And so when designing Cassandra, they took a ton of inspiration from both Dynamo and Google's BigQuery. And so if you're familiar with either of those

[00:55] here today is going to be a lot more straightforward cuz there's tons of overlap. We also have a video breakdown of DynamoDB. I'll put it in the of the corners if I can figure out how to do that. And so feel free to give

[01:08] that video or that written breakdown a read as well. Now Cassandra was created specifically to solve the Facebook inbox messaging system. And so they needed a amounts of write throughput for millions of users sending billions of messages in

[01:24] be able to scale horizontally, right? Without manually sharding. It needed to be able to provide tons of availability with zero downtime. And it needed to deliver these super low latency reads and writes globally. And so that was the

[01:38] relational databases, which I'm going to assume throughout this video most of you have some basic familiarity with, Cassandra was designed to give up on flexibility in querying. So there aren't things like joins or strong consistency,

[01:51] but in exchange we get three main things that every massive system needs. You can see them at the bottom of your screen. Highly scalable, highly available, and through this video, we're going to talk about exactly how Cassandra achieves

[02:04] each of those things. And at the end, I'll tell you not it makes sense to use Cassandra in your system design interview or not. So without further ado, let's get after it. Now that we know why Cassandra exists,

[02:19] actually organizes data. And so the Cassandra data model looks a little different from relational databases, but there are still plenty of similarities that you can anchor to. Starting with the very top, we have what's called a

[02:31] space just like a database in Postgres or MySQL. It's simply a logical container that holds your tables and defines some global settings. These are things like how data should be replicated across the cluster

[02:44] be maintained. Now within each key space, you have what are called tables. And a table defines the schema. This would be the columns, the data types that can be stored. But importantly, unlike relational

[02:58] databases, Cassandra tables are actually flexible, meaning they don't require that every single row has the exact same set of columns. And that's as I said that in just a moment. But within tables, you have rows. Each row

[03:12] represents a single record in the table and it's identified by something called a primary key. We'll come back to how exactly these keys work in just a large sets of data and they're grouped together for efficient access.

[03:26] And then within each row, you have columns. These are the actual pieces of data. And so columns have a name, a type, and a value. Like in this case, the name is name, the type is string, and the

[03:38] value is Evan. And as I mentioned before, what makes Cassandra interesting is that it's a wide column store. If you've ever heard that terminology wide column store, it just means that you can have completely different sets of

[03:51] columns within the same within different rows of the same table. And so in this case, we have user 101 who has just three columns, name, email, and age, spelled incorrectly I see.

[04:04] actually has an additional column, an address. And this is fine. Whereas in a SQL database, you would need to define need to have an address even if that address was null, they would need to

[04:17] have a column for address. That's not the case here. Cassandra was built with three particular things in mind, scalability, availability, and fault tolerance. So let's talk about how it achieves each of

[04:30] these three starting with scalability. When you're dealing with millions and some cases even billions of rows, then a single machine, a single server can't possibly handle all of that data. And so in order to scale, Cassandra distributes

[04:43] that data across many nodes in the cluster. So that each node stores just a fraction of the total data set, right? So in this case, maybe a fourth of the data ends up on node one, a fourth of the data ends up on node two, and so on.

[04:56] sure that's a terminology you're all familiar with. This isn't unique to Cassandra. It's how all distributed databases work, of course. But once you you split the data across multiple nodes, then you have a critical question

[05:10] that needs to be answered. Which node should store this particular piece of comes in. So when you're defining a table in you're defining a table in Cassandra, you specify what's called a primary key.

[05:26] And that primary key is made up of two parts, a partition key and optionally a Now if you know anything about Dynamo or you watched our Dynamo video, then this the same. It's partition key and then we just call the clustering key a sort key

[05:40] But the partition key importantly determines where data lives. So all rows with the same partition key are grouped together and end up on the same node, determines how data is ordered inside of

[05:54] partition key decides where the data actually lives in the cluster and the organized once it's there. So this makes the most sense when we You'll see this statement here in order to create a new table for user messages

[06:10] in Cassandra. We define our primary key, which is made up of the partition key In our case, we've chosen our partition key importantly to be the user ID. This means that all users or all messages, excuse me, from a given user

[06:25] are going to show up on the same node. This is important because if your query pattern was to say fetch all messages from a given user, then now you'd only having to query a bunch of different nodes and then merging or combining that

[06:38] data together at the end. And so if we scroll down and we look at this example, if we've partition key as user ID, then all the users with the ID 0 to 10,000, I made up random numbers here. Just know it would

[06:50] be some fixed range, are going to show up on node one, 10K to 20K on node two, and so on. Now we have a way to decide what to partition by. But how does it actually map those partitions to the specific nodes?

[07:03] Now the simplest approach would be to use a hash plus a modulo. And so you can take the user ID. In our case, user ID was the partition key, right? So take whatever value you're partitioning by, hash it, and then mod it by the number

[07:15] of nodes you have in the in your system. This is going to return a number of either 0, 1, or 2 so that you can know which one of these nodes it should live on, right? So concrete example, if our user ID was 1234 and we hash that and we

[07:29] up value, of course, but maybe you would use a hash function like MD5. And then if we took the modulo of that, modded it by three, then we end up with two. And so we know that this goes on node two. This partition should go on node two.

[07:45] This works, but it falls apart at scale, of course. And the reason for that is pretty straightforward and shown by this diagram here. If you end up adding or removing a node, then the number of nodes changes, which means that nearly

[07:59] every key gets remapped to a new node. And so in a larger cluster, this would data around every single time you need to scale up and down. And so you can If all of a sudden we are now modding by four instead of three because we added a

[08:13] new node to the system, then everything that was previously on two probably shows up somewhere else now. Right? And so as a result, we got to move all the so as a result, we got to move all the data around. And this is a lot of work.

[08:26] And so to solve this, Cassandra uses what's called consistent hashing. And if watching any of our content, if you know if you know anything about distributed coming, right? But instead of using a modulo, consistent hashing is actually a

[08:40] really simple concept. It just arranges all of the possible possible hash values in a ring. Of course, this is just a virtual ring, right? But each node owns one or more ranges of that ring. And so when a key is hashed, in this case, we

[08:57] can hash whatever our user ID was, maybe we get the value 16. Then we find that value on our virtual ring and we walk clockwise until we find the first node and that's where that data should live. And so by using consistent hashing, this

[09:11] design keeps data evenly distributed and it minimizes movement when a node joins or leaves. And so if database two ended up leaving now, then everything between 0 and in our case 25 here is going to end up on database three, but database

[09:26] four and database one didn't change at all, right? This is how we achieve that nodes without disrupting the cluster or redistributing everything. Now importantly, this is a very high level overview of consistent hashing.

[09:40] virtual nodes, which make this redistribution more even. If you want to have a quick video on it. I'll link it in the description so you can go check consistent hashing explains how Cassandra is able to scale by

[09:56] lives. But how do we ensure that we're always The first thing that we need to consider is replication. Every single piece of nodes. And this is controlled by something called the replication factor

[10:10] factor is a setting that is set at the key space level. factor was set to three, then Cassandra keeps three copies of each partition on different nodes across across the cluster. And so maybe the original data

[10:25] hashes to node two, but we're also going to write it to node three and node four just to make sure that we have replicas or backups in case every anything Uh these replicas are also they're placed strategically on different parts

[10:38] of the hash ring, often times even across different racks and across off the top of my head, but it's in the linked written article, um which actually allows you to have your replication factor explicitly specify

[10:52] that replicas need to be on different racks or different data centers if you are in uh a global setup. This way of course if one node goes down, then the others can immediately just start serving those reads and writes. And if

[11:05] we lose data but or if we lose a node and it comes back up, then it can just learn from the uh from the nodes that stayed online how it should kind of fits back into the cluster and starts operating again effectively. Unlike with

[11:18] many other databases, with Cassandra there isn't a single leader or primary interesting. Every single replica is equal and any node can accept any given request. But if there's no single leader, how do

[11:32] usually the role of the leader in the system. Like how do you know who owns what, who's alive, who's dead, um when things are added to the cluster, how do something's removed, how do we know? Well, Cassandra handles all of this

[11:45] protocol. And so every node in the cluster is equal, like I said, there's coordinator, and each node randomly second exchanging small bits of information. And so this is small bits

[11:59] of information like uh which nodes are up, which nodes are down, what data ranges they own, what schemas they should be using, etc. And so every few seconds they ping these messages to each other. And if you ping it to just a

[12:12] couple nodes in the network and then that node pings it to a couple other nodes in the network, then eventually all nodes in the network agree on some consistent state, right? Over time that information spreads just like a gossip

[12:24] uh in real life, and then everybody has that updated consistent view of the cluster. So this peer-to-peer design means that it's fully self-managing and you can add and remove nodes and the gossip will just automatically update

[12:36] Obviously this is a sufficient simplification, um but certainly for the for uh an interview's purpose this is more than enough information. But this is how we avoid things like Zookeeper or etcd,

[12:50] um which are used in many other popular distributed systems in order to be that that central source of truth. But the benefit is that there's now no single coordination. So if you've ever dealt with for example a Zookeeper outage, uh

[13:04] system, then you know just how valuable it is to not have that single point of introduced replication and we've also introduced that gossip product protocol this distributed network, something really interesting comes up. And that's

[13:18] that we've created multiple copies of the same data, which means that those copies could temporarily disagree with each other. So imagine that you have a replication factor of three, you have three different nodes, you then write an

[13:31] update to your username, my username changes from Evan to Evan123. Well, if that write lands on one node and then gets propagated to two of the replicas, where somebody could read from one of the replicas and still read Evan as

[13:46] And the question that always comes up in a system design interview is that is that okay, right? This is the topic of CAP theorem. So CAP theorem, as a system, whenever a network partition occurs, right? A network partition here

[14:03] can't talk to each other over the network, then you have to choose between Guarantee one would be consistency. This means that every single read returns the latest data, which was not the case in the example I just gave.

[14:17] Guarantee two would be availability, which would be that the system keeps accepting reads and writes, right? This is the option that we chose in that example. And so you have to choose one of these, either strong consistency or

[14:29] high availability. There is no both answer necessarily. And so Cassandra of course was designed to stay online no matter what. We talked scalability, high availability, and fault tolerance. So it of course

[14:42] prioritizes availability and partition tolerance. If a few replicas are unreachable, it still accepts writes and synchronizes them later. That's why Cassandra is described as an AP system, availability

[14:55] and partition tolerance. But here's the cool part. And if you are in a system design interview and you can uh bring up this nuance, it's it's the sometimes love to hear. And that's that Cassandra doesn't actually force you to

[15:08] pick one side, consistency or availability, forever. It lets you tune it actually per query. This is what tunable consistency and and so every single read and write that you issue to Cassandra, you can specify a consistency

[15:22] level. This is how many replicas must respond before the operation is considered successful. And you have three different settings here. The first is option one. This is the one that aligns with high availability. And

[15:35] this is we wait for just one replica to respond. And so if our partition is replica is replicated on three different nodes, then we only need one of those to them can take it, tell us that it got it, and then we're good to go. And so

[15:49] has weak consistency because this is the example that we opened with. You could still read stale data from one of those nodes that hasn't yet accepted that The second is quorum. This is the middle ground and often times actually the most

[16:03] going to wait for a majority of the replicas. system, a replication factor of five, the majority would be three. And so if until three of those nodes have responded saying, "Hey, I got the write

[16:17] to the user saying, "Write confirmed." right? And then the last one is all. This is where we wait for every single replica. And so this is for strong consistency. Uh so in the case where we need that

[16:30] consistency, we want to make Cassandra a CP system, consistent and partition tolerant, then we would use the setting all. We're going to wait for all right. So with one, you maximize speed and

[16:42] availability, but you risk reading outdated data. With all, you get strong issue, uh like a network problem, a hardware failure, whatever it may be, then your request can't complete. And so most

[16:56] production systems end up using quorum, which is that sweet spot or that middle what happens on each write and read request respectively, let's just check in and recap what we've discussed so far. We started with the data model, and

[17:10] consistent hashing is what allows Cassandra to scale, excuse me gives it availability and leaderless design keep the cluster decentralized and self-healing, and then

[17:24] a tunable consistency lets you control how it balances correctness and uptime how it balances correctness and uptime per each request. popular feature on hellointerview.com, guided practice.

[17:38] practice system design interviews step by step using that hello interview through everything from the non-functional requirements to the core entities, API routes, all the way through to your high-level design and

[17:51] deep dives, drawing on the whiteboard and narrating your response, all while you're doing well and where you can improve by a model that Stefan and I have spent hundreds of hours tuning. We've expanded the library to 25 of the

[18:05] most common system design interview questions now and we're constantly love this feature. I think you will, too. Check it out at hellointerview.com. let's talk about the write path and the read path respectively. So what exactly

[18:19] happens when a client wants to write data or read data from Cassandra? Starting with writes, when a client wants to send data to Cassandra to write to the database, it contacts first any node in the cluster. This is actually

[18:31] than most databases where they have that central coordinator, right? Remember, we don't have that in Cassandra. So you contact any node in the cluster and that particular request. And so that coordinator figures out

[18:45] which nodes own that particular partition key and it forwards the write requests to those replicas in parallel. So of course it has all of its internal memory based on the gossip messages that it's been receiving to know the full

[18:58] request comes in, it can send it to the right replicas to be able to service And that's where this diagram enters. This diagram here on the right is a This diagram here on the right is a single clustered a single Cassandra

[19:12] node, okay? And so when that write comes in, we end up writing that data in parallel to two different places. We write it to one, the commit log. This is just a write ahead log. Uh the write is first appended immediately to disk.

[19:26] Note that this is on disk. This is to guarantee that durability. If things node, we had to bring it back online, then it's important that the very first thing that we did is we persisted that write to disk, right?

[19:41] to write it into memory, into what is And so the memtable, you can think of it just like a sorted map of recently written rows. It keeps everything in order by the partition key and the

[19:54] clustering key, and it's fully in memory. It's It's in RAM, okay? So, this guy's nice and quick and fast. So, that makes that right easy and fast. asynchronous, right? So, once it's written to the memtable and to the

[20:08] commit log, then we return uh back to the client saying, "Acknowledged, we've received that right." But then asynchronously, as the memtable fills up, it's flushed to disk uh into an immutable file that we call the SSTable.

[20:22] This is sorted string table. And so, SSTables are append-only, they're never updated in place. And so, instead, new writes create new SSTables, and the old ones are merged later through a process called compaction.

[20:35] of detail here, but it is a little bit interesting, though not relevant for a a system design interview, probably. Um but in a SQL database, you actually particular data. If you want to update your name, then you find that row on

[20:50] disk and you update name to Evan123 from Evan. In the case of Cassandra, you never make those updates. You just flush this new memtable, so you have new data. You have a new row that says Evan's name is now

[21:02] Uh and that means that um ends up happening is this compaction process, which goes through and compacts all of those old rows to say

[21:14] definitively, "Evan's is 123 now, so you don't have to go read all of the current state. I'm just going to tell you the current state because I've reads faster." So, hopefully that makes more sense. I don't

[21:27] Um but then finally, when enough replicas based on that chosen consistency level, which we discussed a moment ago, then the coordinator can reply to the client um and say, "You know, we've accepted

[21:42] this point." Um but this is what makes, importantly, Cassandra's writes so fast. They're sequential disk appends and an in-memory insert. There's no random IO. There's no finding the right place in a table.

[21:56] coordination overhead. All of these things that exist in SQL tables don't happen here. We simply write to memory super fast, and we append to the end um of a log on disk, an append-only log. Now, reads are just a tiny bit more

[22:10] involved. It starts off the same. The client again contacts any node, which is going to act as the coordinator. That node then knows which replicas hold the partition and queries them again in parallel based on the requested

[22:22] But then each replica, and again, this is where we jump into this diagram here, places. It first has to check the memtable in So, it's going to check there first for any unflushed writes.

[22:37] Then it's going to check the SSTable on disk. And so, if it were to just check the SSTable on disk, it would have to scan through every single row and try to and this, of course, would be incredibly slow. This is the consequence of the

[22:50] fact that we have this append-only log in order to make writes fast. Well, on the other side, it makes reads slower. And so, Cassandra has some fancy things detail on, but it has some additional

[23:02] files in here. One of which is a bloom filter, and as well as some indexes that allow you to skip files that don't contain the partition that you're after. indexes, makes this read a little bit quicker, so that we don't have to scan

[23:16] the written guide, which is linked below, um but that's how this ends up working. So, you look first in the memtable, then in the SSTable, then you respond back to the coordinator. And the coordinator takes the results of

[23:29] all of the replicas and merges them together, and it picks the newest value using the timestamp of the right. So, whichever one is the newest, that's the one I'm going to send back to the user. But if the replicas disagree, then the

[23:41] coordinator needs to perform a read repair in the background to synchronize maybe they were written at at the same time, but they have different values. heck happened. Um but in short, it's this combination

[23:57] immutable disk file, these timestamp-based reconciliations, these these beautiful properties of really fast writes, that eventual consistency, and high availability. Um and it's what makes Cassandra so great for these

[24:11] really high write throughput scenarios. All right. Now, before we wrap up, I modeling in Cassandra because of just how important it is to a system design that are going to end up using Cassandra, you need to model your data

[24:25] of the architecture that we've been discussing throughout the video. Now, if you're coming from a relational database world, then this is going to first. So, let me try to explain. With relational databases, you normalize

[24:39] here. And so, you store each entity once, usually in its own table, and then we use foreign keys in order to create relationships, and we can use joins to query across different tables, right? And so, the relational data modeling is

[24:53] what we refer to as entity-driven, meaning you think first about entities and their relationships, posts and users. So, in this example, we of course user table. And if you wanted to query for all posts and their users, then you

[25:08] would query the post table, join it on user ID based on the foreign key here in the post table to the user ID. But this ensures that even if we have a post with the same user twice, it they both still reference the same row in another table,

[25:22] right? That's the normalization. But in Cassandra, we don't have foreign And we don't even support queries across multiple tables. And so, normalization actually works against you. Instead, data modeling in Cassandra is

[25:37] what we call query-driven. Maybe I should even write these down. So, query-driven for Cassandra, and then this was entity- Um And so, it's query-driven. So, you start by asking, "What queries does this

[25:52] application actually need in order to run?" And then you design your table specifically to answer those queries efficiently. So, map your query directly to your table. And this means that you'll often have to denormalize your

[26:04] in order to make sure that each of those different queries are are as optimized as they could be. And yes, this creates redundancy. That is the trade-off. And discussing in your interview, as well.

[26:17] But in Cassandra, the argument would be storage is cheap, duplication is fine, you, so you can't do that. And so, in this case, you see that we have a single post table, but now we've denormalized, and we've put the user data uh in this

[26:30] in order to get all posts and their users, it's a single query to this table. It's fast and it's efficient. But you can see that we've stored I guess this is actually not the I don't know why that was Jane. There

[26:43] twice here. We have his information redundancy. So, system design interview, if you're but then you design normalized tables like you would in Postgres, it can be a

[26:56] It shows that you don't actually understand how Cassandra works. And so, that you're thinking about the access patterns in this query-driven design. most important to you guys. And that's when should you actually consider using

[27:11] interview? Well, I've broken it down here to try to And that's that you're going to want to consider using Cassandra when you have really high write throughput. And we're going to describe really high write

[27:24] throughput as something over 100,000 writes per second. have far more writes than you're going to have reads, and it makes it a good candidate. And importantly, you should have predictable, limited query

[27:36] patterns. So, there's a handful of common queries that you're going to run, just going to be those handful of queries. Things like get all posts for a main use case, potentially. Then Cassandra is a great fit. These are

[27:50] things like activity feeds, time series data, messaging systems, maybe event writes are dominated, and you know querying for the data. You can just denormalize across a few tables, and

[28:03] that specific pattern. Then Cassandra will scale beautifully, and everything Importantly, there are places where you don't want to use Cassandra, where it Cassandra. And that should be any place,

[28:15] querying, things like ad hoc analytics, complex aggregations. If you have joins support these things, and so it's not the right fit. Cassandra has some simple support for lightweight transactions, these are

[28:30] partition, uh it doesn't support any cross-table consistency, and certainly not cross-partition consistency. And so, uh it doesn't have transactions that can span these multiple tables. And if you need to write to three denormalized

[28:46] left with inconsistent data across those tables. And so, if you need strong consistency, if this is a financial app or a ticketing app or things like this, Cassandra probably doesn't make sense for that use case. Great. So, we covered

[28:59] Hopefully you guys found it valuable. Just to conclude, I want to summarize what we discussed, and that's this simple. Remember that Cassandra is scalable, highly available, and fault-tolerant. It's great for high

[29:11] write throughput apps with a few simple query patterns. consider your partition key. This is where the data lives. Your clustering key. This is how it's sorted on each partition. And then denormalization.

[29:23] What data needs to be duplicated in order to support all of your simple query patterns. With that, please leave a comment. Let me know if I got anything wrong. Uh like, subscribe, all of those good

[29:36] things. We're going to continue to try to post one video roughly every 2 weeks. description. Feel free to follow. Shoot me a message. Always love to connect with you guys offline, as well. And most importantly,

[29:49] best of luck with your upcoming interviews.