The Apache Cassandra storage engine
Lebresne, Sylvain
Apache Cassandra is a distributed database built to handle massive amounts of data on large clusters of community servers. This talk will present the storage engine at the core of Cassandra, motivating the use of a structure akin to a Log-Structured Merge Tree rather than of a usual B-Tree and it's implications for the data model. We will also introduce most of the current features of that engine (secondary indexes, integrated caching, TTL...) including recent developments introduced in Cassandra 1.0 like compression/checksumming and the new leveled compaction.
 Oops, I'm I'm still on the brain. I will talk about the apache Kissinger storage engine So I I work for a company called data stacks. I was doing Support for Apache Kissinger, but I'm actually that should pay me to work on the on the apache project full time So it's pretty good for me. And that's what I'll talk about So I'll talk about three things like yeah, I'll start with an introduction to do I apache Kissinger for maybe some of you don't know what it is so it's a distributed database, but I will tell a little bit more on that and then I'll quickly explain all the data model work and And and we'll talk about the storage engine. So how do we actually write stuff to this can and read it and why we do it that way? so apache Kissinger is a distributed data store and It was created to handle large amount of data. Okay That is the goal It's an apache project. It's an open source project. It's an apache project since two years February 2010 before that was in the apache incubator the top level project since two years and Actually last October we released version one of Kissinger. So we felt that it was It was major enough to call it version one and as a matter of fact even before the version one It was using production in a number of our company Including some some for a lash company will for for lash datasets and So yeah to give you an idea of the size largest cluster I know about is is is about a little bit more than for 400 Machines and and over 300 terabytes of data for one cluster So okay, so I've got some of these a database So you have a client you talk to your database you do query so you store stuff and you get stuff So that's what it does, but it's a distributed one. So You your database we usually have multiple nodes multiple machines and call nodes and while the goal is you can you can actually scale that but One thing with the case summarize it fully decentralized systems. So every of those node will actually run the same software and Each node will no node will be specific Okay, so it's completely distributed. There is no, you know master node and slave nodes every node is the same It's also replicated database So when you when you store data the data will be distributed. So not not every node will have a copy of every data That being said that is usually replicated. So replication is built It's built in Cassandra for from the beginning. That's a that's a native way It works which mean that every data will be actually replicated in more than one node Usually you can configure you can choose how many time each data is a is replicated and the database actually figure out Where each data should go? It's also it's also a durable data store Because it's not an in memory. We're gonna in need memory grid or something like that We do persist everything to disk. So it's locally Durable, but it's also it's also replicated. So you also get you actually get a very very strong durability guarantees thanks to replication and the fact that we actually event take durability seriously locally and One of the main thing we want is it to be scalable scalable meal Two things it mean that you can add new nodes new nodes easily and it means that when you add new nodes You are the capacity of the cluster will truly scale Linearly with the will the number of nodes So the way you actually add a new node while you start a new node with the software and you say, you know You configure a few IP address so that it can connect to the other nodes and then you say bootstrap and it will join So we call it the ring the cluster the ring because the way we distribute things is by Using something called consistent ashing which considered the machine on a ring But I won't give too many detail on that you can check consistent ashing online But so you you you ask a node to join and enjoy That's that I will be redistributed during that that Operation but it's all done under the hood and as a client you don't you don't see that happening Another thing is that it's full turn so it's built so that if a if a node fail You don't see it. Well, hopefully the operator will see it and we're playing the note at some point but at least the user the client won't see the failure and Because it's fully centralized there is no single point of failure So there is no node that if it fails while the world clusters down every node is same so every note can fail This is what we call highly available, which is a little bit of the same thing as for tolerant which it It tolerate fall but it's it's really transparent even if no dark down you can still insert Seeing and get stuff obviously if you replicate that only once and one node is done You won't be able to access the down that node, but usually you have more and more replicates so you can tolerate Some amount of failure fully transparently Okay, and the last thing I want to say is it's data center where so it's it's built to know about data center So you can actually have a cluster that cross multiple data center You may have one in the US you may have one in Europe you can have more than that And and they will all form only one cluster. Okay, but but the the cluster will still be aware of the of the Data center so what that means you can for example do things like I want to replicate data Twice but I want to be sure that there is one copy on the data in Europe and one copy of data in the US I don't want to have to copy in Europe and zero in the US because The goal is if I lose one one data center I don't want to have problems so you can do that and those things that a replication Is aware of that in the sense that it's optimized So for example if you have to replicate in the US and you write something in in in Europe So I didn't say a client can connect to any node and the rest is involved by the database So how you connect you connect to any node? Oh, you connect you connect to any node wherever you want and the database with will route the request so if you write in real Europe and you have to And and you need to replicate that twice to the US It will actually send only one copy over the Atlantic and then it will write into nodes in in the US And even when you do an operation you can actually ask the database to you can to respect a given contract So for example what can do is say I? Want to write something and as soon as the replica in Europe are I've acknowledged my my my right? I'm good. I'm okay that the replication in the US is actually I see Asynchronous because I don't know maybe if I post a story on something I just want that when I refresh The page I can see my update, but if it takes one or two seconds to get in the US That's okay. They will know that I did it that one second ago anyway So okay that that that was That was back we what what Cassandra is but I won't talk too much of all these are Replication thing what I want to talk today is oh So you can there is a lot of documentation online on that But what I won't say what happened on one on those on those bugs when you receive a query and before that I have to say a few words about the data more So first thing is not SQL okay, it's customized what we usually call nowadays no SQL database It's not well You know it's not necessarily completely opposed to SQL, but what it means that doesn't do It doesn't do everything that SQL does in particular It doesn't do transaction it doesn't do joins and the reason is fairly simple is if you actually start to scale database and it scale it horizontally on many machines well joins and Transaction to a lesser extent are actually hard to do very fast and so well we don't try But what I want to say here is it's more than a key value store I will give a number of example. It's not just you put some value and you and you get it with a key You can do much more important stuff much more interesting stuff and The data model is actually inspired by something called Google Bigtable So, you know Google write that database that they actually use internally, but they publish a paper like 2004 I believe and and you know they have a data model that look a little bit like that because Oh, the time model was inspired. It's not the same, but it's it's inspired and it's what we call Column family based, okay, but choose is a column family is is Kind of a table. So let's take an example. Okay, let's take an example. Let's say a very simple example I want to you know rewrite a Twitter clone. Okay, I want to Take over Twitter and I want sort that in my database. So what first thing I need to store is the user profile user will Create a profile you want to hold the data for those users? So if you if you do that you will first start creating a column family so that the yellow stuff my column family is called users and What my column family will do it will for each user it will keep the profile of the user So, you know, a column family is kind of a table inside Inside a column family You have rows. That's a row. Okay and a row a Row as a key which is the greeny Thing which is the row key you can you can think of that as a primary key for The row But we call that a row key. Okay, and in my example that would be a user ID So that can be anything that could be that could be the email of the user, but in my example I've taken some, you know random User ID as a side note in you know, you know SQL database you would usually use some auto increment for user ID, but in a distributed database Auto increment is a pretty r-sync to do so you use other stuff typically you ID That's and in a row what you have is columns. Okay, so a column is Well a pair of a name and a value Okay, so the you know first name here is the is the column name and just in is the column value So in a row, I will have a number of columns. So in that example Okay for my user I will store the first name the last name the burst here and I can have more of that and My column family will be you know will be composed of all those rows So I may have another user It will have a new a New user ID and it will have its own properties So first thing to notice here is that not every row need to have the same column in it Okay, my second user of an email, but the first one maybe didn't give me an email So you can sing that as a no, but the difference is we didn't define a schema for that So it's a schema s database which means that if you want to a new property to user and you have 4400 million user in your database You don't have to do an elder table that will take days or weeks to actually work So that's that's the reason why I can soon write actually as a schema s. Well, that's one of the reason why it's scheme Okay, that's a fine example. That's fairly simple one. So take another one example and so here I want to write a Twitter clone. So one of the thing I want to do is to Store the tweets that an user made so what I want is When the user clicks on my tweets, I want to show him his tweets and I want to do that in a chronological order So I will create a new clone family that I'll call timeline and inside I will have rows and each for each user I will learn one row and as my previous example the The row key will be the user The user hidden fire. So that's my just in Bieber user here and The user will do tweets So when it tweets something will insert a column and the column name will be a timestamp So zero we use zero one two three because it's an example But in real life that would be a time stop of when the tweet has been made So I will associate the the timestamp to the text of the tweet okay Both names and column Both name and value in a column that actually by to refer Cassandra So you can store everything you want in it and in particular you can here I just stored the text but I could store the text and I could add an info on On which device that which was done or anything so you can do all that but that's simple example And when the user do more tweets will add the tweets But what I want to notice here is that in a row the columns are ordered So there's an order in a row the actual order for the row is something defined in the column family So each column family will define the order of the column in the rows Okay in that example I I pick a you know reverse Integer order so that's something pretty fine, but you can actually write your own comparator. So there's Some poor coming from that so you can do interesting stuff, but there always isn't an order So when the user will do tweets will add this in the chronological order so as you can imagine the the interest of that is that If the query you want to do and that's likely what you want is ask what are the last ten tweets that this user made Well, we're able to answer that very very quickly because we just Find the row for that user and just read that are starting from that point And and and that's it. So there will be like one sick And you can also impression that you do is you can imagine there is there is tons of column and You can do a slice of a row. So you can ask, you know, what are the tweets for? You know one week three weeks ago, you meet all the tweets that this user did three weeks ago So sing like that you can answer just because it's chronologically order And so the second remark is that the row can actually have lots and lots and lots of column Okay, there there's there's actually is a limit on the number of columns you can have in one row But that limit is to billion so you have you can you can still Put a number of saying, you know when a user has as tweet to billion tweets You can start, you know thinking about solution to actually use maybe two rule for for that user, but usually not another big problem so Yeah, that's the way you you would use the that that the basics That's really is the basic of the data model So you have kind of static information where every year we have some set of info But then you can do much more interesting thing by using the fact that the the rows are a number of column that is that can be pretty large and The fact that those are sorted so you can do a number of query very efficiently We do we do have I won't go into the details, but we do have more more interesting stuff that all to Modeling much more easily. So we have things like secondary indexes if I take my first example of the profile I can I can create an index on the burst here of the user So if I do that, I'll be able to query well give me all the user that are born in the 80s for example Okay, and you can do that The database will actually do that automatically for you. We have some sequel distributed counters. So well, they are just counters, but because it's that distributed storage is distributed counters But it's basically using the column value if you use that it's a column value that just is a nint and insert instead of Setting the value you actually say increment the value by that many or decrement the value by that many and you can Do all of those and the database will aggregate everything and we have things like Composite columns so composite columns are a Column is just a name and a value, but in fact Because that can be anything any by terrarium you can actually stuff stuff a number of information both in the name and both in the value so you can for example you know have a name that is composed of multiple component and you can define the comparison so that it's first compare the first value and then the second one and the Third one and we have built-in support for that same thing for the value As I said previously you could have the tweet of the net the sorry the text of the tweet, but you can have With the in the value you can have only device the tweet was done and things like that and you can put all of that in in a value So, okay, that's that's what we are and Know what what I want to Talk about is Given this that I'm all How do we actually store things to this? So what do what is the goal here? One of the goal of Cassandra was to So there is one thing that I'm claiming you can disagree but I'm claiming that writes are usually harder to scale than reads and the reason is that If you write something You you have to you have to write the data on disk Okay, but when you do reads you can always put more caching if you really want to scale reads We kind of know to do that We had more caching or we had more, you know, we duplicate data and we are more more nodes to read but you cannot do caching for the rights because the goal is to actually write it to disk so it doesn't disappear and You cannot if you duplicate the number of nodes where you have your your data for your read to be to have more Read capacity you actually writing more stuff So it's actually make it harder for the right so So a lot of people were able to scale reads reasonably it's not a well simple but But the rights were sometimes a little bit harder. So what Cassandra tries to do is to make rights As fast as it can and say well, we'll try them to You read will be probably a little bit easier and the second thing is that Cassandra is is is made to work on commodity hardware. So the goal is you take a lot of You know you take servers, but probably Not too fancy servers and you put a lot of them and that's the way you scale that's not buying very expensive software And so in particular what you want to do is You usually will use spinning disk for for that kind of things because spinning disk cost Compared to what you can store spinning disk doesn't cost very much And and the thing is I've been this is very bad with random IO So that's something to take into into account So if we want to and if you do rights you will actually do a lot of random IO if you have to you know Modify your database your right your rights will be distributed everywhere on your data set So we'd have to change your files everywhere. So the goal is to minimize random IO. So how do we do that? We use something called lock strictures storage And it's basically with that way so you have a node it has some hard drive some memory and What we want to do is write something so what we want to write is well a given column So a better one column is an easy know is in a row So what you give when you want to write something you give a row key k1 and you give a column So c1 with a value v1 You want to write that so I assume that it's in one Call on family there would be another parameter which is the column family But let's say that I'm writing in one given common for example So when I when we do when we do that right we actually okay, we actually do two things We first write the data in something you know In a structure in memory that we call a main table So we write the you know the column k1 the column C1 in the row k1 and the main table is really kind of a hash map of The row key to the columns that it contains so the when the main table is empty I just add this new this new entry that for k1 I have I have a column c1 and the same thing that we do is we do write the the rights on the on disk and we write it in something called the commit log What the commit log do is? So in the commit log we will write queries write query as they as they come okay, so the commit log is an app and only structure We always add stuff to the end and Because we do that the commit log won't the commit log won't do random IO It will be sequential IO you just write stuff at the end you have you don't have to move anything on the disk But for that to work You need to have the commit log to be on a separate disk so that it doesn't do something else that It actually do run the myo just to come back to the end of that structure. So that's That's Cassandre configuration one-on-one you put your commit log in a separate disk You don't have to but you won't get the same performances if you if you don't do it so everything basically does it and as we'll see you don't need a big disk to all those commit logs because it will actually be Removed and and you can actually control the size that it can take so if you have a disk of 80 gigs You can say I don't want my commit log to be more than 80 gigs and you know Cassandra always will deal with that so that doesn't become that big and When we've done that well, we're done for that right so we actually acknowledge the clients we consider well for that node data is written So if there is a failure now We do have the data on this so we have we have a effsink that data and The node die will restart the node and what the node will do it will replay the commit log So it will just replay the insert that you know where in memory only and hasn't been really persisted yet to this kind of more Strictored on this format So All right, so we'll we'll get more will continue receiving rights So of course we can actually receive rights for more than one column You don't have to write one column at a time you can write multiple column at a time in fact you can actually write multiple column in multiple rows at a time, but let's keep it simple and So you write things you can write two columns So in the main table we'll add a new entry for for K2 we actually added two two columns for it and in the commit log We will just write what we received but one kind of Importance thing is that when we write in the commit log, it's it's it's atomic or more precisely We actually rock check some and everything to be sure that when we read the commit log we either read one of those Maybe not called that transaction with one of the mutation we call it mutation internally So we consider one mutation we write it atomically in the commit log which actually mean that when you write more than one colon Cassandra do that Atomic only what I mean by that is that if I write C1 and C2 in column K2 I I have the guarantee that either both of the column are persisted or none of them are I cannot have the first one persisted and not the other one What is true though is that we don't do that atomically in the main table part? So it's not isolated so it's actually possible unlikely but possible that That a read may only see K2 with only C1 for example and at C2 That actually true of the current version of Cassandra, but the next version that should be out in like a month or something actually add Isolation so in next version Cassandra the rise will actually be
 Oops, I'm I'm still on the brain. I will talk about the apache Kissinger storage engine  So I I work for a company called data stacks. I was doing  Support for Apache Kissinger, but I'm actually that should pay me to work on the on the apache project full time  So it's pretty good for me. And that's what I'll talk about  So I'll talk about three things like yeah, I'll start with an introduction to do I apache Kissinger for  maybe some of you don't know what it is so it's a distributed database, but I will tell a little bit more on that and  then I'll  quickly explain all the data model work and  And and we'll talk about the storage engine. So how do we actually write stuff to this can and read it and why we do it that way?  so  apache Kissinger is a distributed data store and  It was created to handle  large amount of data. Okay  That is the goal  It's an apache project. It's an open source project. It's an apache project since  two years February 2010 before that was in the apache incubator the top level project since  two years and  Actually last October we released version one of Kissinger. So we felt that it was  It was major enough to call it version one and as a matter of fact even before the version one  It was using production in a number of our company  Including some some for a lash company will for for lash datasets and  So yeah to give you an idea of the size  largest cluster I know about is is is  about a little bit more than for  400  Machines and and over 300 terabytes of data for one cluster  So okay, so I've got some of these a database  So you have a client you talk to your database you do query so you store stuff and you get stuff  So that's what it does, but it's a distributed one. So  You your database we usually have  multiple nodes  multiple machines and call nodes and  while the goal is you can you can actually scale that but  One thing with the case summarize it fully decentralized systems. So every of those node will actually run the same software and  Each node will no node will be specific  Okay, so it's completely distributed. There is no, you know master node and slave nodes every node is the same  It's also replicated database  So when you when you store data the data will be distributed. So not not every node will have a copy of every data  That being said that is usually replicated. So replication is built  It's built in Cassandra for from the beginning. That's a that's a native  way  It works which mean that every data will be actually replicated in more than one node  Usually you can configure you can choose how many time each data is a is replicated and the database actually figure out  Where each data should go? It's also it's also a durable data store  Because it's not an in memory. We're gonna in need memory grid or something like that  We do persist everything to disk. So it's locally  Durable, but it's also it's also replicated. So you also get you actually get a very very strong  durability guarantees thanks to replication and the fact that we actually  event take  durability seriously locally and  One of the main thing we want is it to be scalable  scalable meal  Two things it mean that you can add new nodes new nodes easily and it means that when you add new nodes  You are the capacity of the cluster will truly scale  Linearly with the will the number of nodes  So the way you actually add a new node while you start a new node with the software and you say, you know  You configure a few IP address so that it can connect to the other nodes and then you say bootstrap and it will join  So we call it the ring the cluster the ring because the way we distribute things is by  Using something called consistent ashing which considered the machine on a ring  But I won't give too many detail on that you can check consistent ashing online  But so you you you ask a node to join and enjoy  That's that I will be redistributed during that that  Operation but it's all done under the hood and as a client you don't you don't see that happening  Another thing is that it's full turn so it's built so that if a if a node fail  You don't see it. Well, hopefully the operator will see it and we're playing the note at some point  but at least the user the client won't see the failure and  Because it's fully centralized there is no single point of failure  So there is no node that if it fails while the world clusters down every node is same so every note can fail  This is what we call highly available, which is a little bit of the same thing as for tolerant which it  It tolerate fall but it's it's really transparent even if no dark down you can still insert  Seeing and get stuff obviously if you replicate that only once and one node is done  You won't be able to access the down that node, but usually you have more and more replicates so you can tolerate  Some amount of failure fully transparently  Okay, and the last thing I want to say is it's data center where so it's it's built to know about data center  So you can actually have a cluster that cross multiple data center  You may have one in the US you may have one in Europe you can have more than that  And and they will all form only one cluster. Okay, but  but the  the cluster will still be aware of the of the  Data center so what that means you can for example do things like I want to replicate data  Twice but I want to be sure that there is one copy on the data in Europe and one copy of data in the US  I don't want to have to copy in Europe and zero in the US because  The goal is if I lose one one data center  I don't want to have problems so you can do that and those things that a replication  Is aware of that in the sense that it's optimized  So for example if you have to replicate in the US and you write something in in in Europe  So I didn't say a client can connect to any node and the rest is involved by the database  So how you connect you connect to any node?  Oh, you connect you connect to any node wherever you want and the database with will route the  request so if you write in real Europe and you have to  And and you need to replicate that twice to the US  It will actually send only one copy over the Atlantic and then it will write into nodes in in the US  And even when you do an operation you can actually ask the database to you can to respect a given contract  So for example what can do is say I?  Want to write something and as soon as the replica in Europe are I've acknowledged my my my right?  I'm good. I'm okay that the replication in the US is actually I see  Asynchronous because I don't know maybe if I post a story on something  I just want that when I refresh  The page I can see my update, but if it takes one or two seconds to get in the US  That's okay. They will know that I did it that one second ago anyway  So okay that that that was  That was back we what what Cassandra is but I won't talk too much of all these are  Replication thing what I want to talk today is oh  So you can there is a lot of documentation online on that  But what I won't say what happened on one on those on those bugs when you receive a query and before that  I have to say a few words about the data more  So first thing is not SQL okay, it's customized what we usually call nowadays no SQL database  It's not well  You know it's not necessarily completely opposed to SQL, but what it means that doesn't do  It doesn't do everything that SQL does in particular  It doesn't do transaction it doesn't do joins and the reason is fairly simple is if you actually start to  scale database and it scale it  horizontally on many machines well joins and  Transaction to a lesser extent are actually hard to do very fast and so well we don't try  But what I want to say here is it's more than a key value store  I will give a number of example. It's not just you put some value and you and you get it with a key  You can do much more important stuff  much more interesting stuff and  The data model is actually inspired by something called Google Bigtable  So, you know Google write that database that they actually use internally, but they publish a paper like  2004 I believe and and you know they have a data model that look a little bit like that because  Oh, the time model was inspired. It's not the same, but it's it's inspired and it's what we call  Column family based, okay, but choose is a column family is is  Kind of a table. So let's take an example. Okay, let's take an example. Let's say a very simple example  I want to you know rewrite a Twitter clone. Okay, I want to  Take over Twitter and I want sort that in my database. So what first thing I need to store is the user profile user will  Create a profile you want to hold the data for those users?  So if you if you do that you will first start creating a column family so that the yellow stuff  my column family is called users and  What my column family will do it will for each user it will keep the profile of the user  So, you know, a column family is kind of a table inside  Inside a column family  You have rows. That's a row. Okay  and a row a  Row as a key which is the greeny  Thing which is the row key you can you can think of that as a primary key for  The row  But we call that a row key. Okay, and in my example that would be a user ID  So that can be anything that could be that could be the email of the user, but in my example I've taken some, you know random  User ID as a side note in you know, you know SQL database you would usually use some  auto increment for user ID, but in a distributed database  Auto increment is a pretty r-sync to do so you use other stuff  typically you ID  That's and in a row what you have is columns. Okay, so a column is  Well a pair of a name and a value  Okay, so the you know first name here is the is the column name and just in is the column value  So in a row, I will have a number of columns. So in that example  Okay for my user  I will store the first name the last name the burst here and I can have more of that and  My column family will be you know will be composed of all those rows  So I may have another user  It will have a new a  New user ID and it will have its own properties  So first thing to notice here is that not every row need to have the same column in it  Okay, my second user of an email, but the first one maybe didn't give me an email  So you can sing that as a no, but the difference is we didn't define a schema for that  So it's a schema s database which means that if you want to a new property to user and you have  4400 million user in your database  You don't have to do an elder table that will take days or weeks to actually work  So that's that's the reason why I can soon write actually as a schema s. Well, that's one of the reason why it's scheme  Okay, that's a fine example. That's fairly simple one. So take another one example and so here  I want to write a Twitter clone. So one of the thing I want to do is to  Store the tweets that an user made so what I want is  When the user clicks on my tweets, I want to show him his tweets and I want to do that in a chronological order  So I will create a new clone family that I'll call timeline and inside  I will have rows and each for each user  I will learn one row and as my previous example the  The row key will be the user  The user hidden fire. So that's my just in Bieber user here  and  The user will do tweets  So when it tweets something will insert a column and the column name will be a timestamp  So zero we use zero one two three because it's an example  But in real life that would be a time stop of when the tweet has been made  So I will associate the the timestamp to the text of the tweet  okay  Both names and column  Both name and value in a column that actually by to refer Cassandra  So you can store everything you want in it and in particular you can here  I just stored the text but I could store the text and I could add an info on  On which device that which was done or anything so you can do all that but that's simple example  And when the user do more tweets will add the tweets  But what I want to notice here is that in a row the columns are ordered  So there's an order in a row the actual order for the row is something defined in the column family  So each column family will define the order of the column in the rows  Okay in that example I I pick a you know reverse  Integer order so that's something pretty fine, but you can actually write your own comparator. So there's  Some poor coming from that so you can do interesting stuff, but there always isn't an order  So when the user will do tweets will add this in the chronological order  so as you can imagine the the interest of that is that  If the query you want to do and that's likely what you want is ask what are the last ten tweets that this user made  Well, we're able to answer that very very quickly because we just  Find the row for that user and just read that are starting from that point  And and and that's it. So there will be like one sick  And you can also impression that you do is you can imagine there is there is tons of column and  You can do a slice of a row. So you can ask, you know, what are the tweets for?  You know one week three weeks ago, you meet all the tweets that this user did three weeks ago  So sing like that you can answer just because it's chronologically order  And so the second remark is that the row can actually have lots and lots and lots of column  Okay, there there's there's actually is a limit on the number of columns you can have in one row  But that limit is to billion so you have you can you can still  Put a number of saying, you know when a user has as tweet to billion tweets  You can start, you know thinking about solution to actually use maybe two rule for for that user, but  usually not another big problem  so  Yeah, that's the way you you would use the that that the basics  That's really is the basic of the data model  So you have kind of static information where every year we have some set of info  But then you can do much more interesting thing by using the fact that the the rows are a number of column that is  that can be pretty large and  The fact that those are sorted so you can do a number of query very efficiently  We do we do have I won't go into the details, but we do have more more interesting stuff that all to  Modeling much more easily. So we have things like secondary indexes if I take my first example of the profile  I can I can create an index on the burst here of the user  So if I do that, I'll be able to query well give me all the user that are born in the 80s for example  Okay, and you can do that  The database will actually do that automatically for you. We have some sequel distributed counters. So well, they are just  counters, but because it's that distributed storage is distributed counters  But it's basically using the column value if you use that it's a column value that just is a nint and  insert instead of  Setting the value you actually say increment the value by that many or decrement the value by that many and you can  Do all of those and the database will aggregate everything  and we have things like  Composite columns so composite columns are a  Column is just a name and a value, but in fact  Because that can be anything any by terrarium you can actually stuff stuff a number of information both in the name and  both in the value so you can for example  you know have a name that is composed of multiple  component and you can define the comparison so that it's first compare the first value and then the second one and the  Third one and we have built-in support for that same thing for the value  As I said previously you could have the tweet of the net the sorry the text of the tweet, but you can have  With the in the value you can have only device the tweet was done and things like that and you can put all of that in  in a value  So, okay, that's that's what we are  and  Know what what I want to  Talk about is  Given this that I'm all  How do we actually store things to this?  So what do what is the goal here?  One of the goal of Cassandra was to  So there is one thing that I'm claiming you can disagree but I'm claiming that  writes are usually harder to scale than reads and the reason is that  If you write something  You you have to you have to write the data on disk  Okay, but when you do reads you can always put more caching if you really want to scale reads  We kind of know to do that  We had more caching or we had more, you know, we duplicate data and we are more more nodes to read  but you cannot do caching for the rights because the goal is to actually write it to disk so it doesn't disappear and  You cannot if you duplicate the number of nodes where you have your your data for your read to be to have more  Read capacity you actually writing more stuff  So it's actually make it harder for the right  so  So a lot of people were able to scale reads reasonably it's not a well simple but  But the rights were sometimes a little bit harder. So what Cassandra tries to do is to make rights  As fast as it can and say well, we'll try them to  You read will be probably a little bit easier and  the second thing is that Cassandra is is is made to work on  commodity hardware. So the goal is you take a lot of  You know you take servers, but probably  Not too fancy servers and you put a lot of them and that's the way you scale that's not buying very expensive software  And so in particular what you want to do is  You usually will use spinning disk for for that kind of  things because spinning disk cost  Compared to what you can store spinning disk doesn't cost very much  And and the thing is I've been this is very bad with random IO  So that's something to take into into account  So if we want to and if you do rights you will actually do a lot of random IO if you have to you know  Modify your database your right your rights will be distributed everywhere on your data set  So we'd have to change your files everywhere. So the goal is to minimize random IO. So how do we do that?  We use something called lock strictures storage  And it's basically with that way so you have a node it has some hard drive some memory and  What we want to do is write something so what we want to write is well a given column  So a better one column is an easy know is in a row  So what you give when you want to write something you give a row key k1 and you give a column  So c1 with a value v1  You want to write that so I assume that it's in one  Call on family there would be another parameter which is the column family  But let's say that I'm writing in one given common for example  So when I when we do when we do that right we actually okay, we actually do two things  We first write the data in something you know  In a structure in memory that we call a main table  So we write the you know the column k1 the column  C1 in the row k1 and the main table is really kind of a hash map of  The row key to the columns that it contains so the when the main table is empty  I just add this new this new entry that for k1  I have I have a column c1 and the same thing that we do is we do write the the rights on  the on disk and we write it in something called the commit log  What the commit log do is?  So in the commit log we will write  queries write query as they as they come okay, so the commit log is an app and only structure  We always add stuff to the end and  Because we do that the commit log won't the commit log won't do random IO  It will be sequential IO you just write stuff at the end you have you don't have to move anything on the disk  But for that to work  You need to have the commit log to be on a separate disk so that it doesn't do something else that  It actually do run the myo just to come back to the end of that structure. So that's  That's Cassandre configuration one-on-one you put your commit log in a separate disk  You don't have to but you won't get the same performances if you if you don't do it so  everything basically does it and as we'll see you don't need a big disk to all those commit logs because it will actually be  Removed and and you can actually control the size that it can take so if you have a disk of 80 gigs  You can say I don't want my commit log to be more than 80 gigs and you know  Cassandra always will deal with that so that doesn't become that big and  When we've done that well, we're done for that right so we actually acknowledge the clients we consider well for that node  data is written  So if there is a failure now  We do have the data on this so we have we have a effsink that data and  The node die will restart the node and what the node will do it will replay the commit log  So it will just replay the insert that you know where in memory only and hasn't been really persisted yet to this kind of more  Strictored on this format  So  All right, so we'll we'll get more will continue receiving rights  So of course we can actually receive rights for more than one column  You don't have to write one column at a time you can write multiple column at a time in fact you can actually write multiple column in  multiple rows at a time, but let's keep it simple and  So you write things you can write two columns  So in the main table we'll add a new entry for for K2 we actually added two two  columns for it and in the commit log  We will just write what we received but one kind of  Importance thing is that when we write in the commit log, it's it's it's atomic or more precisely  We actually rock check some and everything to be sure that when we read the commit log we either read one of those  Maybe not called that transaction with one of the mutation we call it mutation internally  So we consider one mutation we write it atomically in the commit log which actually mean that when you write more than one colon  Cassandra do that  Atomic only what I mean by that is that if I write C1 and C2 in column K2  I I have the guarantee that either both of the column are persisted or none of them are I cannot have the first one  persisted and not the other one  What is true though is that we don't do that atomically in the main table part?  So it's not isolated so it's actually possible  unlikely but possible that  That a read may only see K2 with only C1 for example and at C2  That actually true of the current version of Cassandra, but the next version that should be out in like a month or something  actually add  Isolation so in next version Cassandra the rise will actually be
cassandra_f1BKJUPmlx8_2_0_2471.png cassandra_f1BKJUPmlx8_2_2472_2843.png cassandra_f1BKJUPmlx8_2_2844_3107.png cassandra_f1BKJUPmlx8_2_3108_4247.png cassandra_f1BKJUPmlx8_2_4248_5903.png cassandra_f1BKJUPmlx8_2_5904_6407.png cassandra_f1BKJUPmlx8_2_6408_6803.png cassandra_f1BKJUPmlx8_2_6804_6995.png cassandra_f1BKJUPmlx8_2_6996_7295.png cassandra_f1BKJUPmlx8_2_7296_7499.png cassandra_f1BKJUPmlx8_2_7500_8363.png cassandra_f1BKJUPmlx8_2_8364_10199.png cassandra_f1BKJUPmlx8_2_10200_11279.png cassandra_f1BKJUPmlx8_2_11280_11807.png cassandra_f1BKJUPmlx8_2_11808_11915.png cassandra_f1BKJUPmlx8_2_11916_12203.png cassandra_f1BKJUPmlx8_2_12204_14003.png cassandra_f1BKJUPmlx8_2_14004_14495.png cassandra_f1BKJUPmlx8_2_14496_14903.png cassandra_f1BKJUPmlx8_2_14904_15011.png cassandra_f1BKJUPmlx8_2_15012_15131.png cassandra_f1BKJUPmlx8_2_15132_18659.png cassandra_f1BKJUPmlx8_2_18660_18731.png cassandra_f1BKJUPmlx8_2_18732_19043.png cassandra_f1BKJUPmlx8_2_19044_19379.png cassandra_f1BKJUPmlx8_2_19380_24287.png cassandra_f1BKJUPmlx8_2_24288_24671.png cassandra_f1BKJUPmlx8_2_24672_24935.png cassandra_f1BKJUPmlx8_2_24936_25343.png cassandra_f1BKJUPmlx8_2_25344_25547.png cassandra_f1BKJUPmlx8_2_25548_27791.png cassandra_f1BKJUPmlx8_2_27792_27851.png cassandra_f1BKJUPmlx8_2_27852_28955.png cassandra_f1BKJUPmlx8_2_28956_29195.png cassandra_f1BKJUPmlx8_2_29196_30443.png cassandra_f1BKJUPmlx8_2_30444_30875.png cassandra_f1BKJUPmlx8_2_30876_31055.png cassandra_f1BKJUPmlx8_2_31056_31223.png cassandra_f1BKJUPmlx8_2_31224_32063.png cassandra_f1BKJUPmlx8_2_32064_32939.png cassandra_f1BKJUPmlx8_2_32940_33059.png cassandra_f1BKJUPmlx8_2_33060_41397.png
Oops, I'm I'm still on the brain. I will talk about the apache Kissinger storage engine So I I work for a company called data stacks. I was doing Support for Apache Kissinger, but I'm actually that should pay me to work on the on the apache project full time So it's pretty good for me. And that's what I'll talk about So I'll talk about three things like yeah, I'll start with an introduction to do I apache Kissinger for maybe some of you don't know what it is so it's a distributed database, but I will tell a little bit more on that and then I'll quickly explain all the data model work and And and we'll talk about the storage engine. So how do we actually write stuff to this can and read it and why we do it that way? so apache Kissinger is a distributed data store and It was created to handle large amount of data. Okay That is the goal It's an apache project. It's an open source project. It's an apache project since two years February 2010 before that was in the apache incubator the top level project since two years and Actually last October we released version one of Kissinger. So we felt that it was It was major enough to call it version one and as a matter of fact even before the version one It was using production in a number of our company Including some some for a lash company will for for lash datasets and So yeah to give you an idea of the size largest cluster I know about is is is about a little bit more than for 400 Machines and and over 300 terabytes of data for one cluster So okay, so I've got some of these a database So you have a client you talk to your database you do query so you store stuff and you get stuff So that's what it does, but it's a distributed one. So You your database we usually have multiple nodes multiple machines and call nodes and while the goal is you can you can actually scale that but One thing with the case summarize it fully decentralized systems. So every of those node will actually run the same software and Each node will no node will be specific Okay, so it's completely distributed. There is no, you know master node and slave nodes every node is the same It's also replicated database So when you when you store data the data will be distributed. So not not every node will have a copy of every data That being said that is usually replicated. So replication is built It's built in Cassandra for from the beginning. That's a that's a native way It works which mean that every data will be actually replicated in more than one node Usually you can configure you can choose how many time each data is a is replicated and the database actually figure out Where each data should go? It's also it's also a durable data store Because it's not an in memory. We're gonna in need memory grid or something like that We do persist everything to disk. So it's locally Durable, but it's also it's also replicated. So you also get you actually get a very very strong durability guarantees thanks to replication and the fact that we actually event take durability seriously locally and One of the main thing we want is it to be scalable scalable meal Two things it mean that you can add new nodes new nodes easily and it means that when you add new nodes You are the capacity of the cluster will truly scale Linearly with the will the number of nodes So the way you actually add a new node while you start a new node with the software and you say, you know You configure a few IP address so that it can connect to the other nodes and then you say bootstrap and it will join So we call it the ring the cluster the ring because the way we distribute things is by Using something called consistent ashing which considered the machine on a ring But I won't give too many detail on that you can check consistent ashing online But so you you you ask a node to join and enjoy That's that I will be redistributed during that that Operation but it's all done under the hood and as a client you don't you don't see that happening Another thing is that it's full turn so it's built so that if a if a node fail You don't see it. Well, hopefully the operator will see it and we're playing the note at some point but at least the user the client won't see the failure and Because it's fully centralized there is no single point of failure So there is no node that if it fails while the world clusters down every node is same so every note can fail This is what we call highly available, which is a little bit of the same thing as for tolerant which it It tolerate fall but it's it's really transparent even if no dark down you can still insert Seeing and get stuff obviously if you replicate that only once and one node is done You won't be able to access the down that node, but usually you have more and more replicates so you can tolerate Some amount of failure fully transparently Okay, and the last thing I want to say is it's data center where so it's it's built to know about data center So you can actually have a cluster that cross multiple data center You may have one in the US you may have one in Europe you can have more than that And and they will all form only one cluster. Okay, but but the the cluster will still be aware of the of the Data center so what that means you can for example do things like I want to replicate data Twice but I want to be sure that there is one copy on the data in Europe and one copy of data in the US I don't want to have to copy in Europe and zero in the US because The goal is if I lose one one data center I don't want to have problems so you can do that and those things that a replication Is aware of that in the sense that it's optimized So for example if you have to replicate in the US and you write something in in in Europe So I didn't say a client can connect to any node and the rest is involved by the database So how you connect you connect to any node? Oh, you connect you connect to any node wherever you want and the database with will route the request so if you write in real Europe and you have to And and you need to replicate that twice to the US It will actually send only one copy over the Atlantic and then it will write into nodes in in the US And even when you do an operation you can actually ask the database to you can to respect a given contract So for example what can do is say I? Want to write something and as soon as the replica in Europe are I've acknowledged my my my right? I'm good. I'm okay that the replication in the US is actually I see Asynchronous because I don't know maybe if I post a story on something I just want that when I refresh The page I can see my update, but if it takes one or two seconds to get in the US That's okay. They will know that I did it that one second ago anyway So okay that that that was That was back we what what Cassandra is but I won't talk too much of all these are Replication thing what I want to talk today is oh So you can there is a lot of documentation online on that But what I won't say what happened on one on those on those bugs when you receive a query and before that I have to say a few words about the data more So first thing is not SQL okay, it's customized what we usually call nowadays no SQL database It's not well You know it's not necessarily completely opposed to SQL, but what it means that doesn't do It doesn't do everything that SQL does in particular It doesn't do transaction it doesn't do joins and the reason is fairly simple is if you actually start to scale database and it scale it horizontally on many machines well joins and Transaction to a lesser extent are actually hard to do very fast and so well we don't try But what I want to say here is it's more than a key value store I will give a number of example. It's not just you put some value and you and you get it with a key You can do much more important stuff much more interesting stuff and The data model is actually inspired by something called Google Bigtable So, you know Google write that database that they actually use internally, but they publish a paper like 2004 I believe and and you know they have a data model that look a little bit like that because Oh, the time model was inspired. It's not the same, but it's it's inspired and it's what we call Column family based, okay, but choose is a column family is is Kind of a table. So let's take an example. Okay, let's take an example. Let's say a very simple example I want to you know rewrite a Twitter clone. Okay, I want to Take over Twitter and I want sort that in my database. So what first thing I need to store is the user profile user will Create a profile you want to hold the data for those users? So if you if you do that you will first start creating a column family so that the yellow stuff my column family is called users and What my column family will do it will for each user it will keep the profile of the user So, you know, a column family is kind of a table inside Inside a column family You have rows. That's a row. Okay and a row a Row as a key which is the greeny Thing which is the row key you can you can think of that as a primary key for The row But we call that a row key. Okay, and in my example that would be a user ID So that can be anything that could be that could be the email of the user, but in my example I've taken some, you know random User ID as a side note in you know, you know SQL database you would usually use some auto increment for user ID, but in a distributed database Auto increment is a pretty r-sync to do so you use other stuff typically you ID That's and in a row what you have is columns. Okay, so a column is Well a pair of a name and a value Okay, so the you know first name here is the is the column name and just in is the column value So in a row, I will have a number of columns. So in that example Okay for my user I will store the first name the last name the burst here and I can have more of that and My column family will be you know will be composed of all those rows So I may have another user It will have a new a New user ID and it will have its own properties So first thing to notice here is that not every row need to have the same column in it Okay, my second user of an email, but the first one maybe didn't give me an email So you can sing that as a no, but the difference is we didn't define a schema for that So it's a schema s database which means that if you want to a new property to user and you have 4400 million user in your database You don't have to do an elder table that will take days or weeks to actually work So that's that's the reason why I can soon write actually as a schema s. Well, that's one of the reason why it's scheme Okay, that's a fine example. That's fairly simple one. So take another one example and so here I want to write a Twitter clone. So one of the thing I want to do is to Store the tweets that an user made so what I want is When the user clicks on my tweets, I want to show him his tweets and I want to do that in a chronological order So I will create a new clone family that I'll call timeline and inside I will have rows and each for each user I will learn one row and as my previous example the The row key will be the user The user hidden fire. So that's my just in Bieber user here and The user will do tweets So when it tweets something will insert a column and the column name will be a timestamp So zero we use zero one two three because it's an example But in real life that would be a time stop of when the tweet has been made So I will associate the the timestamp to the text of the tweet okay Both names and column Both name and value in a column that actually by to refer Cassandra So you can store everything you want in it and in particular you can here I just stored the text but I could store the text and I could add an info on On which device that which was done or anything so you can do all that but that's simple example And when the user do more tweets will add the tweets But what I want to notice here is that in a row the columns are ordered So there's an order in a row the actual order for the row is something defined in the column family So each column family will define the order of the column in the rows Okay in that example I I pick a you know reverse Integer order so that's something pretty fine, but you can actually write your own comparator. So there's Some poor coming from that so you can do interesting stuff, but there always isn't an order So when the user will do tweets will add this in the chronological order so as you can imagine the the interest of that is that If the query you want to do and that's likely what you want is ask what are the last ten tweets that this user made Well, we're able to answer that very very quickly because we just Find the row for that user and just read that are starting from that point And and and that's it. So there will be like one sick And you can also impression that you do is you can imagine there is there is tons of column and You can do a slice of a row. So you can ask, you know, what are the tweets for? You know one week three weeks ago, you meet all the tweets that this user did three weeks ago So sing like that you can answer just because it's chronologically order And so the second remark is that the row can actually have lots and lots and lots of column Okay, there there's there's actually is a limit on the number of columns you can have in one row But that limit is to billion so you have you can you can still Put a number of saying, you know when a user has as tweet to billion tweets You can start, you know thinking about solution to actually use maybe two rule for for that user, but usually not another big problem so Yeah, that's the way you you would use the that that the basics That's really is the basic of the data model So you have kind of static information where every year we have some set of info But then you can do much more interesting thing by using the fact that the the rows are a number of column that is that can be pretty large and The fact that those are sorted so you can do a number of query very efficiently We do we do have I won't go into the details, but we do have more more interesting stuff that all to Modeling much more easily. So we have things like secondary indexes if I take my first example of the profile I can I can create an index on the burst here of the user So if I do that, I'll be able to query well give me all the user that are born in the 80s for example Okay, and you can do that The database will actually do that automatically for you. We have some sequel distributed counters. So well, they are just counters, but because it's that distributed storage is distributed counters But it's basically using the column value if you use that it's a column value that just is a nint and insert instead of Setting the value you actually say increment the value by that many or decrement the value by that many and you can Do all of those and the database will aggregate everything and we have things like Composite columns so composite columns are a Column is just a name and a value, but in fact Because that can be anything any by terrarium you can actually stuff stuff a number of information both in the name and both in the value so you can for example you know have a name that is composed of multiple component and you can define the comparison so that it's first compare the first value and then the second one and the Third one and we have built-in support for that same thing for the value As I said previously you could have the tweet of the net the sorry the text of the tweet, but you can have With the in the value you can have only device the tweet was done and things like that and you can put all of that in in a value So, okay, that's that's what we are and Know what what I want to Talk about is Given this that I'm all How do we actually store things to this? So what do what is the goal here? One of the goal of Cassandra was to So there is one thing that I'm claiming you can disagree but I'm claiming that writes are usually harder to scale than reads and the reason is that If you write something You you have to you have to write the data on disk Okay, but when you do reads you can always put more caching if you really want to scale reads We kind of know to do that We had more caching or we had more, you know, we duplicate data and we are more more nodes to read but you cannot do caching for the rights because the goal is to actually write it to disk so it doesn't disappear and You cannot if you duplicate the number of nodes where you have your your data for your read to be to have more Read capacity you actually writing more stuff So it's actually make it harder for the right so So a lot of people were able to scale reads reasonably it's not a well simple but But the rights were sometimes a little bit harder. So what Cassandra tries to do is to make rights As fast as it can and say well, we'll try them to You read will be probably a little bit easier and the second thing is that Cassandra is is is made to work on commodity hardware. So the goal is you take a lot of You know you take servers, but probably Not too fancy servers and you put a lot of them and that's the way you scale that's not buying very expensive software And so in particular what you want to do is You usually will use spinning disk for for that kind of things because spinning disk cost Compared to what you can store spinning disk doesn't cost very much And and the thing is I've been this is very bad with random IO So that's something to take into into account So if we want to and if you do rights you will actually do a lot of random IO if you have to you know Modify your database your right your rights will be distributed everywhere on your data set So we'd have to change your files everywhere. So the goal is to minimize random IO. So how do we do that? We use something called lock strictures storage And it's basically with that way so you have a node it has some hard drive some memory and What we want to do is write something so what we want to write is well a given column So a better one column is an easy know is in a row So what you give when you want to write something you give a row key k1 and you give a column So c1 with a value v1 You want to write that so I assume that it's in one Call on family there would be another parameter which is the column family But let's say that I'm writing in one given common for example So when I when we do when we do that right we actually okay, we actually do two things We first write the data in something you know In a structure in memory that we call a main table So we write the you know the column k1 the column C1 in the row k1 and the main table is really kind of a hash map of The row key to the columns that it contains so the when the main table is empty I just add this new this new entry that for k1 I have I have a column c1 and the same thing that we do is we do write the the rights on the on disk and we write it in something called the commit log What the commit log do is? So in the commit log we will write queries write query as they as they come okay, so the commit log is an app and only structure We always add stuff to the end and Because we do that the commit log won't the commit log won't do random IO It will be sequential IO you just write stuff at the end you have you don't have to move anything on the disk But for that to work You need to have the commit log to be on a separate disk so that it doesn't do something else that It actually do run the myo just to come back to the end of that structure. So that's That's Cassandre configuration one-on-one you put your commit log in a separate disk You don't have to but you won't get the same performances if you if you don't do it so everything basically does it and as we'll see you don't need a big disk to all those commit logs because it will actually be Removed and and you can actually control the size that it can take so if you have a disk of 80 gigs You can say I don't want my commit log to be more than 80 gigs and you know Cassandra always will deal with that so that doesn't become that big and When we've done that well, we're done for that right so we actually acknowledge the clients we consider well for that node data is written So if there is a failure now We do have the data on this so we have we have a effsink that data and The node die will restart the node and what the node will do it will replay the commit log So it will just replay the insert that you know where in memory only and hasn't been really persisted yet to this kind of more Strictored on this format So All right, so we'll we'll get more will continue receiving rights So of course we can actually receive rights for more than one column You don't have to write one column at a time you can write multiple column at a time in fact you can actually write multiple column in multiple rows at a time, but let's keep it simple and So you write things you can write two columns So in the main table we'll add a new entry for for K2 we actually added two two columns for it and in the commit log We will just write what we received but one kind of Importance thing is that when we write in the commit log, it's it's it's atomic or more precisely We actually rock check some and everything to be sure that when we read the commit log we either read one of those Maybe not called that transaction with one of the mutation we call it mutation internally So we consider one mutation we write it atomically in the commit log which actually mean that when you write more than one colon Cassandra do that Atomic only what I mean by that is that if I write C1 and C2 in column K2 I I have the guarantee that either both of the column are persisted or none of them are I cannot have the first one persisted and not the other one What is true though is that we don't do that atomically in the main table part? So it's not isolated so it's actually possible unlikely but possible that That a read may only see K2 with only C1 for example and at C2 That actually true of the current version of Cassandra, but the next version that should be out in like a month or something actually add Isolation so in next version Cassandra the rise will actually be
all the data model work and And and we'll talk about the storage engine. So how do we actually data store and It was created to handle large built in Cassandra for from the beginning. That's Durable, but it's also it's also replicated. So there is a lot of documentation online on that ID, but in a distributed database Auto increment like secondary indexes if I take my first example sequential IO you just write stuff at the end you just to come back to the end of that structure. commit log We will just write what we received true of the current version of Cassandra, but the