CMU Database Group · 1:23:02 · https://www.youtube.com/watch?v=o7bjRUcDMx0
1. <Untitled Chapter 1>
0:05 official members bounce bust off the Chrome realize it's real hell what we call Home official members bounce bust off the Chrome realize it's real hell where we from the ins side one I Vision fat licks and M Clips the Chrome will make the average imitator do back flips you like a [Music]
0:28 pistol yo so all right so Andie is in Chicago so I'm here today instead and let's get started so yeah first administrative stuff project Tre was gee on last Sunday so hopefully you either done or you have at least three late days project four is going to be du on December 8th 11:59 p.m. and that's a Sunday and the final is going to be on uh December 13 8:30 a.m. that's a Friday so there are no early exams please don't leave campus before that date on the other hand sorry let me drink some water
1:00 according to the CMU exam policy if you have more than two exams within a 25h hour period please let Andy know if you need accommodations please let Andy know he will work something out cool so as Andy said last class at this point in the semester basically you should already know how to build a single node database system and that means systems like sqlite my SQL or postas uh and you kind of run bottom up here with your class projects with project one you started with the storage layer the buffer pool manager in Project two you spad up accesses to that storage layer using the database index the B3
1:38 and in Project three you kind of covered the basics of like query execution maybe query planning if you did the leaderboard and your next project which I think it's already released it's going to be on concurrency control so uh also let me just double check that I'm recording sorry uh yes I am yeah so your next project is going to be on concurrency control and uh Rich re have covered you also covered some database logging and Recovery which is pretty important if you want people to actually use your
2:05 software so all that all that to say that like you have all the ingredients to build like a single node database system however if you want to do a distributed database system clicker hello clicker good if you want to do a uh distributed datab base system the key theme Here is going to be problems around
2:26 coordination and so when we talk about coordination we mean that your database system might send messages through like the top components the cre planning components or at the bottom level uh the dis manager buffer pool manager or even somewhere in the middle but the key aspect is like everything that we talked about before in the single Noe case that's still going to remain here that's still going to be a
2:48 problem it's just that now when you run a query should you be pulling data from the other nodes should you have kind some kind of like central location where you're pushing this data these are the main challenges of like making your single note database a distributed
3:02 database and with all that said uh one thing that Andy likes to say is that like these three lectures on distributed databases they're just a crash course because these are actually pretty complex systems the goal of these lectures and your aim should be to just like familiarize yourself with the terminology vernacular that people use and also kind of get the ability to like
3:23 understand what the design trade-offs are so that you can evaluate Real World Systems in terms of what they do and so about one month ago at the end of I think your query execution lectures Andy already brought up the point of like parallel databases versus distributed
3:38 databases but we're going to quickly recap that here for a parallel database you can usually assume that your notes are going to be physically close to one another and by that we mean something like a data center they're on the same rack so they're connected with a high-speed land and your communication cost is assumed to be pretty small you can think on the order of like Nan seconds or microsc in terms of like how your messages can get to each other and also your communication can be pretty reliable usually if you send a message it's going to be
4:07 received this changes a lot in the distributed setting because in the distributed setting your noes can be far from each other you might have a note here on the east coast and a different Noe on the west coast the notes are going to be connected using some kind of public network usually so you can think of something like the internet that's linking these notes together and so because of that the communication cost uh is also going to increase greatly
4:30 because you might have a note that somewhere on the east coast and a note somewhere in like Asia or Europe and now when you're going across the world to send a message the speed of light is actually also going to start mattering
4:40 here so uh one more aspect of that is also that your messages are no longer going to be reliable if they're going over the internet and by that I mean that like uh TCP IP only goes so far even if it has like retries or retransmissions if your network is congested your messages are going to be very slow and even the like underc cables that connecting your nodes they can end up getting cut so your messages could be lost they could be retransmitted they could show up multiple times show up out of order
5:08 basically there's a whole bunch of problems here yes so why we PR distrib over is just a is this just because of the cost uh great question so the reason we kind of want a distributed database is for example in terms of like availability zones uh when you have something on like the US East and US West then your data is like more
5:30 reli uh reliably safe and secure for example on the west coast they just had this like really big uh Cyclone hurricane something like that and so some places lost your internet if you had all of your stuff as a parallel database like on the west coast now you just cannot access it anymore because it's down it's cut off from the internet but if you had something on the east coast and something on the west coast even though the west coast is down like right now you can still access things because it's on the east coast does that make sense y I forgot to repeat the question I will try to repeat the question next time
6:00 and so yeah to kind of recap our goal for today uh in a distributed database we're going to use the building blocks that you have already seen and use uh in your single node database setting and we are going to extend them to support transaction processing and query execution in this new kind of like distributed
6:18 environment and so today's class is just going to be like a high level overview of what a distributed database system looks like and when Angie is back next week he's going to talk about first distributed ogp systems and then distributed olab
6:31 systems but to give you a quick preview of what changes here uh we'll go over some of the like single node system components so for example you just finish a project on like query optimization query execution but now you also will need to worry in the distributed case where like your data is actually stored and there might also be some cost associated with moving data from one node to another so now that should also uh factor into like your uh pry optimizers cost
6:56 model for concurrency control which is one of the more complicated parts of a distributed database uh you also now need to find ways to get every node to basically agree on two things one what happened and two in what order did things happen for example right now it's actually 209 as opposed to 206 and time sync is like already pretty hard so even agreeing on what time it is uh can be pretty hard as for logging and Recovery if you only have a single node then okay your system is either up or it's down but if you have a distributed database and you have like 20 nodes and let's say two of them go down is your system up or is your system down can you still process queries that's kind of something that you have to think about and that's what we're going to
7:37 do also feel free to stop me at any point if you have questions or if I'm speaking too quickly so yeah so this is today's agenda basically we are going to talk about like system architectures for distributed databases and then following that we will talk about the core design issues that will come
7:57 up we will also cover like different partitioning schemes which are basically how we are going to spread the data around uh in our distributed database and lastly we're going to do a super fast preview of like distributed concurrency control following which we are going to have a flash talk today by data science they also work on the distributed database uh we will talk more about them later when we talk about Apachi
8:23 Cassandra so starting with the basics uh distributed database systems like uh system architecture it's basically just going to specify what shared resources are directly accessible by a CPU so the essence of that is just like answering these two questions where is the memory and where is the disk depending on your answer to those questions where the memory is and where the dis is this will influence the kind of messages that like you have to send between the different nodes and who should send them it basically will affect how these CPUs coordinate with each
8:56 other and so absolutely everything you have done and seen so far this semester is what the database literature people call a shared everything architecture and that means that every uh every single node is going to have its own like CPU that's the top diagram its own memory that's the middle and its own disc that's the
9:16 bottom so this is basically what bust Hub and post dress is for example if you ignore replication meaning that there are no additional nodes around but for most people when you say distributed databases what they are going to think about about is a shared nothing architecture and that's a term invented in the like 1980s by Mike Stonebreaker who is like this database curing award guy you have nodes and they each all have their own like individual CPU memory and disk but they're not allowed to directly talk to each other so whenever you need to communicate between nodes they need to go through the network so for example uh if you store data for like CS Majors on like the left most node and EC Majors on the rightmost Node then if your query is like who is coming to this who is inside this class right now you have to go over the network because you have to talk to like both of the
10:09 NES but with the rise of the public Cloud maybe like around 2010 or so uh sh this architectures have actually become much more popular and in some sense they are dominant nowadays most of the newer database startups in The Last 5 Years are going to be Shar this architectures
10:26 and as the name implies uh all of the nodes still have their own C CPU and their own memory but now they have a shared view of like one big logical dis and uh so you can think of something like Amazon S3 or just the internet the cloud as like what that logical disc is and that's not to say that these notes cannot have their own local disc they can still have their own local disc as like a faster cache it's just that they all uh do have this access to like one giant pool of like this is our logical disc representing what our data is
10:57 that's a distinguishing characteristic of like Shar this architecture and for completeness you can continue like moving this red box of the network around on this diagram to arrive at the Shar memory architecture and with the Shar memory architecture that is basically um going to be where every node just has a CPU they will share both the disc and the memory and by sharing memory what we mean is that like uh if you have some kind of like in-memory data structure
11:26 you already have to go to the network and say please get me the value at like memory address X for reading that data structure so the usual use case for this is something like a high performance like Computing kind of setup scientific simulations and you're going to see things that uh used like rgma or Infinity band like Technologies like that but in practice for a distributed database setting there's no real like use for like I shouldn't say use there's no real example of like Shar memory architectures that I know of so Shar memory is kind of this like academic thing
12:01 question uh the previous yes yes if it would go back hello yes uh for the Shar desk y may I consider assume that there's a machine like in for the desk machine logical uh it's not just logical it's a physical machine with a desk only without any CPU without any memory that
12:23 true yeah I guess so if I understand your question correctly your question is for the machine that is the disc can you assume it kind of has like no CPU no memory uh yeah conceptually it has no CPU or memory relevant to like the processing of your queries obviously I think it might still need like some kind of like uh computation ability of its own in order to actually send the data back to you but it's not going to be the kind of computation that is answering your query does that make sense that's true so you don't care about the CPU and memory inside the desk but you only use
12:56 uh the desk of that machine yeah you can think of it as like uh you make an API call to Amazon S3 and like just download the file that's like your logical disc mhm good question yeah any more cool
13:14 then so we're going to zoom in one by one on these different architectures and we're going to start with the shared nothing architecture so I'm going to need to look this up ignoring academic prototypes the first commercial like shared nothing system would be Terra data back in like 19 1982 and again what that means is that each node is going to have its own CPU memory and disk they are only allowed to talk to each other over the network and this is actually really good for performance and efficiency if each node has all the data that it needs to answer a query so it's currently course registration season and people on like waight list and stuff so in the earlier example the Cs Department
13:52 could just use like the Cs node and the EC Department could just use the ECE node and then you can kind of have this nice like uh way of splitting up the work alternatively if each node contains like all the data for everyone then you could also just give everyone one node basically they won't be botton and like fighting with each other to say I want to run my queries first your queries
14:14 first but so yeah that's the ideal case where like you can break up your query and send it to like max out the work on each individual nde however the problem with that is that it gets harder to scale the capacity because
14:28 uh sorry sorry sorry I lost where I am it gets harder to scale capacity because the data is basically going to be tied to the local disc of each node so that means that if you want to spin up a new node for answering like uh enrollment for CS Majors for example then you have to copy that over it's also going to be hard to to ensure consistency because each node does not know what's going on in the other nodes right so as you're uh updating things you have to go over the network to make sure everyone has the same
14:57 picture so the there are a lot of shared nothing databases and these are just a few of them uh Andy actually maintains the Encyclopedia of databases GB gb. I don't know if he has advertised this to you before uh but yeah you can go there to look for more databases if you are so
15:13 inclined the conventional wisdom for how yep question yeah so in your example of like CS students or whatever if you wanted to get an inner join on two things like the Cs and EC you'd have to get data from both and then join it somewhere else yep or you might get like data from the e one and then pull it to the Cs one that's one
15:32 way I need to remember to repeat your question yes sorry is that why it's hard to scale capacity The Joint uh so when you say scale capacity sorry your question is is that why we need is the reason it's hard to scale capacity the fact that we need to pass like join data over the network that is maybe part of it but usually what we mean is that like if you want to add a new note to answer queries like let's say uh course registration for like e Maes is really getting high because everyone's on a weight list or something and you want to have a second e node
16:02 then you have to copy over the existing data on the existing ECE node so scaling capacity is going to like uh have a lot of data movement this uh yeah so I guess uh maybe this will make more sense once we look at the Shar this example but let me see if you can see my cursor I don't think you can
16:25 what happens is like let's say you have like uh 2 terab of data on this dis over here and then you want to spin up a new node and then uh to spin up that new node and have it operate in this shared nothing architecture you're going to have to copy over this two terabytes of data to like the new noes disc as
16:43 well so the part that makes it expensive or hard to scale capacity is that you have to copy the existing data to the new thing that you are making oh it's hard to compare to share uh it's much harder compared to share this yes sorry yeah in terms of can you do the copy you can do the copy it's just going to be
17:02 painful any more questions and thanks for the question cool uh yeah but so basically from like the 1980s to early 2000s this architecture was actually held up as like if you want to do a distributed database you should do it this way and so that's why a lot of these systems here are doing it and part of that is also because a lot of the single node algorithms that you have been looking at in the semester so far they app to this kind of like shared nothing architecture
17:31 without too many changes you can use it you can use these algorithms to like minimize the amount of uh data copying or coordination that you need to do to un like joints and stuff however with like the rise of the public Cloud a lot of like these systems have been adapted to use a shared disc architecture instead and that's what we are talking about next or that is what we will be talking about in two slides because first here's an
17:57 example so for example example we have here a shared nothing database with two nodes and so each node will have its own local CPU memory and disk and the way that we have decided to like uh split up data here is we have a single table that is partition on IG so the top node will have IGS that go from like 1 to 150 and the bottom not has IDs that go from 150 to
18:19 300 and then a query comes in and it has to talk to some kind of like abstract Cloud that represents a metadata catalog that just says if you want to ask for ID whatever talk to this node and then let's say it wants to get ID like 200 so it's going to go to the bottom node the metadata service will like tell it to go there and then it's just going to get the
18:40 response similarly uh or not similarly on the other hand if you want to get IDs that kind of span across multiple nodes you don't want your application server to have to like talk to each and every single node individually so the distributed database is expected to kind of like figure this out for you talk to any no that it needs to answer the query then it will pull the data back to like one of the nodes the one that originally
19:04 uh the application server was talking to for example perform all the joining processing there complete the answer and send back the response so this is a shared nothing architecture and yeah does that make sense so far question for example whens ID 200 does it store it then or or is it just in memory and then flushed out yep so so the question is when it posts id2 200 does it store it there or is it just in memory and flushed out uh it does not store it because it it's not like uh logically in charge of that
19:41 ID but so now suppose that like our uh notes are super busy let's say uh it's I don't know like course registration season or Black Friday or something and the two notes that you have are not enough to answer all the queries then you might say Okay instead of storing like 150 IDs per partition we just want to store like 100 IDs per
20:00 partition this is a part that earlier you had a question on like why is scaling capacity hard it's a bit harder because now you're going to have to copy the data uh for those like 50 on the top 50 on the bottom and send them to the middle node and then make it in charge of like managing those IDs now so we have repartitioned it so that the top one is like IDs 1 to 100 then 100 and 1 to 200 2001 to 300
20:26 yeah and I believe yeah it's also pretty critical at this step that when you do the copy of like spinning up a new node you update the catalog metadata service to say that okay this new node actually has that metadata so an anty story would be that uh when mongod DB did this originally back in the day uh they had support for like Auto scaling they could do the copying part fine but they could not update the catalog metadata in like a single Atomic operation so what would happen is that like the data would get copied to let's say the middle node but if a query comes in and then asks for like give me id number 101 it would still be sent to the top note could not find the data and then people would be
21:08 said so that was the shared nothing architecture and next we're going to move on to the shared this architecture and here nodes are assessing like a single logical disc by some kind of interconnect think something like they all have direct access to like cloud storage like Amazon S3 but each node is still going to have its own CPU and memory and it also could have its own like locally attached this if it wants to have like a larger
21:35 cache this architecture was actually also designed in the 1980s uh but it was not successful back then and yet what I said earlier uh is that every database startup well most database startups in the past like 5 to 10 years are using Shar this architectures so what change
21:51 what really kind of change with the rise of the public cloud of Amazon S3 being available and so like the general availability of this kind of infrastructure that's already pretty good let a database developer uh avoid having to implement this shirt this part themselves and so the nice thing about this is that you basically have like infinite cloud storage up to the limit of like your credit card bill and if you want it replicated like however many places it's just magically handled it's just a lot of engineering like niess I guess that makes it take off
22:20 now and I guess one the maybe really beautiful parts of this architecture in my opinion is that like what this lets you do is it lets you scale like the uh Computing part like the part above the network and the storage part separately so previously in the like shared nothing case if you want to have more storage you also have to pay for more compute or if you have more compute you have to duplicate the data even if like your data uh was perfectly fine as it was in this case now if you want to add like more CPU you only need to pay for more CPU and you get more CPU and if you want to add more this you can just add more this you're not bundled into it anymore
23:02 and yeah so this is a pretty popular architecture for facilitating like data legs and serous systems and I'm not sure whether Andy went over the definition of that so just in case he hasn't a data L is basically uh the big idea behind data L is that people don't really actually like loading their data their data into a database that much they just want to be able to tell the database system hey I have this list of like giant this giant list of like CSV files Json files whatever files in S3 it's just like
23:31 where it is please go and query it and figure it out yourself so it's supporting this kind of like less structured data uh querying and conceptually that's kind of like shared this because you just have this giant pull of like data in the cloud for serverless architecture what they tend to have is like they have uh stateless compute nodes so basically what you see on the diagram here and the final resting place of the data that they are Computing on is still also going to to be somewhere in the public
24:00 cloud and so when you're in a Shar this setting and those stateless compute nodes are idle you can trut them down and everything will be fine but if you're in a Shar nothing setting and you shut them down you're losing some data that is no longer able to be able to like query or
24:17 updated so as before if my clicker Works uh I forgot to click that just now as before here are some examples of like shirt disc systems and and uh here's also a good time I guess to pause for any questions like I would say if you have to take away one thing from this slide or this lecture make sure you know what share this architecture
24:38 is yes right uh so I think conceptually how we are uh thinking about data lakes here is that you have a lot of like random files in the cloud some of them are CSV some of them are like Json some of them are par and they are not necessarily like ingested into your database by injested into your database I mean like they are not transformed into like uh two P that stored in a relational SEO table so conceptually you are kind of just telling your database hey here is this like G logical view of what data is accessible uh go figure it out uh and that's what we are pitching as like also kind of Shar this
25:25 architecture I uh I think it's like kind of a do you view it as like are you Al sorry the question is uh you get the data L part but how is data legs kind of like shared dis I would say it's more like Shar this facilitates data Lake architectures because it's used to this model where any data that you want is kind of already accessible there on the cloud like abstractly and so it does not have to be like natively loaded into your
26:02 database y then moving on to a quick example with like Shar this architectures like before we are going to have two nodes and uh each will have its own CPU and memory we still have the catalog metadata that tells the application server which node to talk to if it has a query but the storage is now conceptually like separate it's like a single logical
26:24 dis so when the application server is going to ask for an ID specific ID like 101 what you do need to do in this setting is you need to convert that into something that the shared disc understands so whether this maps to like some kind of S3 bucket clicker hello whether this maps to like some kind of S3 bucket which is like uh page ABC in this case or if IG 102 then it map to page like XYZ basically you have to convert like the tuo ID into the Shar this ID
26:59 and so the advantage of the share this uh architecture which we will show in this example is that let's say ID 101 is really popular and in our previous case in the Shar nothing example we would have had to copy the data for like ID 101 into the middle node right over here we don't have to do that copying anymore because again it's just going to translate it into like something that the Shar disc layer understands and then it's just going to read it directly from the sh this layer no data copying involved and this is kind of like the easy scale
27:31 part and so so far so good but what if you want to do an update of ID 101 well in this case it does get a little bit more complicated because while updating it itself is fine you have to make sure that like anyone else who is holding on to a local copy either in J memory or in J disc notes that you updated it and there's a bunch of different ways to do that uh I think Andy will actually cover more of this next lecture so I'm not going to go too in depth but at high level you could either broadcast a message to all the ndes
27:58 or you could like flip a bit inside the catalog metadata so that next time someone ask for it you know that it should be invalidated that you could do some kind of like gossip protocol between the notes stuff like
28:13 that and again for completeness we have shared memory it looks a lot like shared everything with like separate physical uh nodes the main difference is going to be that you have some kind of like common memory address space either through like rgma or Infinity or something like that because nobody really does this in like a distributed database setting we are going to skim right past it and move
28:37 on and oh yeah sure well actually uh I guess you could think of like the earlier slide where there were four of them side by side as like a classification back when they were thinking about all these different designs in the 1980s and in practice you do want to use this for something like maybe high performance Computing high high performance Computing is something that you might see in like if you take parallel over here 418 618 and you will use like the bridg superc computer it has a lot of like
29:06 RDMA it's just not as relevant for the database setting and that's the reason we're kind of like not paying a lot of attention to it if you are interested I would recommend you take like parallel in course registration right
29:21 now I need to repeat questions sorry uh so design issues now that we have a kind of a high level overview of like the system architecture looks like uh the main design issues we are going to be concerned with are like
29:35 uh how does the application server actually like kind of find the nodes that has the data at once in our previous examples we have this abstract like metadata catalog and okay in practice you have to actually implement the thing so how does that work uh another option for example is to have like a central coordinator that everyone will talk to instead to that basically access the metadata
29:56 catalog but even after you can find the data that's the question of like uh should you send the queries to the individual nodes containing the data or to the central coordinator and when you do send the query are you uh so-called like pushing the query to the data meaning that you do the computation on the Node that has the data or are you pulling the data to the query meaning that you do the computation on the Node that requested
30:20 the data that's also the question of like how you are dividing the database up across different resources and that's the partitioning that we alluded to earlier more that data and there's also the question of like how the database system continues to ensure kind of like uh correctness
30:35 because given that like different notes are reading data writing data some of them are being spun up some of them are being shut down possibly involuntarily that's also one more difference in the distributed world because like uh for example there was this case where like a sheep ate my internet in New Zealand that you can look up and basically a she at a network cable and brought the note down uh yeah it's a kind of crazy environment and so you have to be able to tolerate stuff like
31:02 this I had a note here to say that like in the interest of time we're also going to skip some slides on the history of like distributed databases so you can find and office hours if you're interested in that because some of those protocols and database systems are still being used for stuff like bang
31:20 ATMs and yeah that's for the next class so design wise one big design goal that we have is this idea of data transparency and the idea behind data transparency is that like you don't want to have to rewrite your application depending on whether the data that you're quering is physically like located on the East Coast or the West Coast you want it to just work if you have a query that runs today you want it to continue running tomorrow even if the data has actually shifted location to like I don't know Asia or something in practice your developers uh and people writing SQL curries might still need to be aware of like where the data is actually living but this is more for like cost regions because data movement across like different regions can get very expensive in terms of like can you do it you want the system to be able to
32:05 do it yeah so now we got to I guess the maybe one of the core parts of this secture which is database partitioning or how we want to split our database up and by database partitioning more explicitly what we mean is that we want to divide our database up into disjoint subsets so that you can spread the load on your datase around evenly and basically get full use of whatever resources that you're paying for for example if you have like uh let's say a node is typically let's say around $5,000 and you have 10 of them to answer queries if half of them are idle you're wasting a lot of money partitioning is also something that like you might see called Charing in noo systems or like if you play a lot of MMO RPGs Charing is also a term that arises there and what that is is that the database system is executing query fragments on each kind of like uh partition and then it will combine like the results to produce a single answer
33:04 yeah so let's talk about different ways to do partitioning and maybe the first like trivial obvious idea is to uh do naive table partitioning and by that we mean that each table is going to be assigned to a different node this node is going to be responsible for like this table F that node is responsible for that table
33:22 bar and according to Andie not too many systems do this GB actually did do this because the customer wanted it which is good listen to the customer but uh obviously this only works if like each node can hold the entire table and so actually if your queries never really drain data across these different tables and the assess patterns are like kind of uniform this is a pretty okay architecture because it does spread out the load but in practice a lot of workloads do not look like that so that's why it's
33:52 naive and so let's look at a quick example we will have two colorcoded tables one is red and one is blue and we will have uh a bunch of nodes so we will toss table one onto node one and we will toss table two onto node two then queries for table one like this ideal query over here select start from table one it's going to go to node one and similarly for note two uh C for note two go to note two for table two go to note
34:20 two so more context for why like the mongod DB customer wanted a feature like this is they basically had the equivalent of like an audit table if if you've done like web app development and that table was just logging everything that like happened in the application so it's right very very right heavy but it's really almost never you only look at it when like something goes really wrong and they wanted to make sure that like uh the rights to that table would not affect the performance of the rest of like the distributed database system
34:48 so they wanted to isolate that table to a partition of its own that's a context there so that was table partitioning and now we are going to look at vertical partitioning and what that is it's kind of like a hacky version of like turning a row store into a column store uh where you split a table into separate partitions based on like its attributes so like a column store you are going to need to maintain some metadata after you do the split to reconstruct the tupo back into its original form but unlike a column store you cannot benefit from like all the query execution stuff that like you have talked about and maybe implemented in your projects and that's actually a great by Dan a professor over at like Maryland where uh he kind of explores the limits of approximating a column store with a r
35:37 store but back to this example we have a table with like three in columns and one text column and so let's say that this text column is really expensive maybe it stores like megabytes of data and yet at the same time let's say that the text column is only occasionally assess most people are really only interested in like the tree in
35:55 attributes so we can do vertical part partitioning like this clicker good morning oh sorry Zoom has decided to kick me out stealing my focus I will rejoin Zoom later clicker issues clicker issues okay so yeah so we can do vertical partitioning like this uh where we basically have split off attribute 4 into a partition of its own and we have the tree and columns that most people care about in Partition
36:24 one the problem with what we have just done is that now if most of the queries are assessing partition one we have load imbalance again and so in practice you want to do both vertical partitioning which is this and horizontal partitioning which is coming in the next slide but a high level what we're going to do is we're also going to spread around these two BS across the different
36:46 partitions so horizontal partitioning is uh when you split a table's twoos into destroy subsets based on like some partition and key and scheme that is somewhat abstract we will look at some uh examples later but we are basically going to pick some columns and just like uh hopefully divide up the database equally in terms of like some kind of
37:07 met quick question yeah just go over back to the column partition that's basically a column store right if that's the case what's like the file format for you to BU store those partitions uh uh you say it's basically a column store uh conceptually it's kind of like a column store but we have not applied any of the column store optimizations like run L en coding I I'm actually not sure which ones you cover in this class at this point sorry uh but there are some optimizations you can do if your system is natively a column store in this case we are assuming you take like a row store like bus tub and split it up like this and you're not going to get any kind of like magic performance improvements it's kind of like having a ro with only one uh text attribute so is it bad uh I mean it's just a technique it can be improved shall we go with that
37:54 yeah I did not repeat the question once more dang it uh so yeah I guess uh so partitioning can only help you so much though like ultimately if you're trying to figure out if everyone is trying to figure out the answer to the same question like is Andy really in Chicago is he really meeting Mushu then like no matter how you partition it everyone's sitting the same exact same to both so it can only help you so much yeah uh but with that said we are going to cover a bunch of different common like uh horizontal
38:22 partitioning schemes and in this case we're going to cover hash partitioning this is when like you uh take a column you hash it you use a hash value to decide which partition it should go to we have already actually seen range partitioning that was from our earlier example where like uh the top partition has like IDs 100 sorry 1 to 150 and the bottom had like 15 to
38:45 300 and then predicate partitioning is this kind of interesting idea where like you can kind of specify a where Clause to Define your partition you're like manually specifying partitions so you can say one partition is like where uh the species is human and they are currently awake or the others partition is like the species is human and they are currently asleep so like you can kind of manually divide things up that way it can be pretty effective when like predicate partitioning is done well but the reason it's not so common in practice is because it requires you to really understand the workload and that's
39:18 hard question are we choosing columns or are we choosing R in this case uh we are choosing columns and maybe we will see an example to kind of make that more concrete so in this case we have a table with like uh rows going from like 101 to 105 and we are choosing to partition based on this key uh a b CDE e like this second
39:44 column and uh uh let's say our partition key partition key name key is that column what we're going to do is we're going to Hash it we're going to take the value mod four and that kind of decides what partition it's going to go to we're taking it mod for because we have four partitions so some pretty animations it moves like that and so that's how we are going to store the data and later at query time when we have this query that comes in select star from table where partition T is some value well the value will be provided so we just hasch the value again and that tells us like which partition we should be looking in to answer the
40:20 query question if there's a on another key do we have to ask every partition scan uh yeah if you have a so the question is if you have a more complicated like predicate on your we Clause where maybe multiple partitions are relevant then you would have to scan every single partition and that's why picking a good partition key can be
40:48 important and so you might be thinking uh at this point how partitioning is going to work for a Shir disc setting because kind of the whole point of like where Shar this is is that we have one big G logical disc right so how does partitioning work in this context the key idea here is that we have like let's say ID 1 2 3 4 we have these two like stateless compute nodes uh so something like serverless for example and we're going to assign like different IDs to different nodes so the top node would be uh responsible for like any queries involving IDs one and two the bottom node is responsible for any IDs like three and four so if uh so if you have something currying for id1 it's going to go to the top node and if you have something for ig3 it's going to go to the bottom
41:35 node but yeah sorry question are they really stess they're responsible for some gotcha so the question is whether they are really stateless if uh they are responsible for some part conceptually just like which IDs they are responsible for is that abstract catalog metadata thing that is not directly part of the
41:55 node also let let me check that I did not get kicked off recording yep I did not sorry so and as before if you have if you have a query that spans multiple partitions then the database system should figure this out uh automatically for
42:15 you so I guess here's a question actually uh why do you want to do this Y in this case which note will be returning the data of ID3 and only conceptually for this lecture you can think that the node that is returning the data is always the node that the application server is talking to so that noes job becomes like uh figuring out what other the nodes it has to talk to and it will do this like internally but it will not make the application say okay after you're done talking to me go talk to that person and that's because if you think of how the SQL cury is formed like uh the SQL cury itself might encode many different ID accesses that it needs to do at once so
42:55 it makes more sense for the database system to have to do it not the like application server question that means the application server server can rly Cho any of the node about and uh they will we will consume that uh assume that every Noe just return the result for then even though they don't know the answer they will ask the other for help right uh the question is can you kind of assume that the application server can talk to any node and the nodes will figure it out yes but the nodes the application server should um be guided by this like catalog metadata to minimize the amount of like cross node communication you have to do so there's some kind of service that says okay uh for your SE query you should go talk to like that note so the that means the application server still need to figure out which is the best note to talk to you uh what's not shown on this slide that is still there is the catalog
43:49 metadata service thing that basically tells it which note it should talk to given a query we are going to see a concrete implementation idea for like how to do this in a couple of slides cool so sorry uh one more question I guess is like why would you want to do
44:10 this so I heard the word cashing can you elabor it so just if you send like the exact query to uh the same note every time it's going to keep the cach from the S3 or whatever so it's like less um
44:23 yeah perfect so the answer was exactly as you said if you uh send the exact same query to the same node it can reuse the data that it already got from S3 and you can lower your bill from
44:34 AWS cool and so now we're going to have a very short slide on like how partitioning Works in a shared nothing environment it's very short because it's basically the same SL you have seen many times at this point uh in the shirt nothing partitioning the data lives with the nde so IDs one and two go above ID three and four go below depending on who it wants to get the ID from it will just talk to the node
44:59 clicker thank you and so going back to the previous slide on like hash partitioning what's one potential problem also with this approach any takers in sorry Lo balancing load balancing I think that's along the right track uh could you elaborate like if there is a note that got many request then other notes will be idle while this will be
45:27 yeah so the response was like if there's one note with many requests then that Noe will be active and other notes will be idle and that's along the lines of like uh where we're going with this which is that in that case you would want to like scale out right you would want to add maybe more notes or like re do the hashing somehow so that more of the queries are going to go to the other
45:48 notes and one issue with that is that we said that the hash function here is mod for because we had four partitions and that means if we add a new like partition then it's now mod 5 and you have to move all this data around and that's going to be hilariously
46:01 expensive so uh in practice uh Andy likes to do a survey at this point of like how many people have heard of this consistent hashing two uh I will say that's roughly one3 so Andy that would be one3 and moving on uh so consistent hashing is this idea that let's just like incrementally add and remove nodes from a cluster without having to rebalance everything and move data around uh as in the previous slide so consistent hashing itself was introduced like the terminology in 1997 by Cara he's this professor Mi and his name you will probably see again in like our algorithms
46:40 class consistent Hing is actually also the uh product idea behind like Akamai CN if you've heard of that they're a billion dollar company at this point pretty cool anyway the idea is pretty clever and it's also pretty simple you have a hash function right and hash function who are properties of good hash functions they're very good at Distributing things like uniform is that a question oh sorry yeah then uh so okay so if you have a good hash function then it can also distribute values kind of like uniformly around the unit circle so let's say the circle goes from values like Zer to one then you can place partitions roughly evenly on this unit circle and now when you Hash a partition
47:20 t uh it gets assigned to the partition that you get to by following like this I should stay closer to this it gets assigned to the partition uh that you get by following the ring clockwise and so the hash for key 1 goes to partition one the hash for key2 goes to partition three and then Andy did some color coding here so basically the color coding shows the range of hash values that get assigned to a particular
47:48 partition and so far that's kind of like okay kind of cool but whatever but what makes it interesting is later when you add a new Partition then you don't need to move all the data in this case we added a new Partition P4 the only kind of like data that needs to get moved around is all the stuff that was previously in P3 and so for everything in P3 you check if it will now has to P4
48:10 and if it does you move it there so you have greatly reduced the amount of like data movement that kind to kind of has to happen here and so some more examples P5 is going to get inserted there move some stuff from P3 into it or sorry p yeah P1 into
48:29 it and similarly for P6 what you will see again next week is that you can also use this idea for replication so replication is this idea that like if one of your partitions goes down maybe like uh the sheep from the earlier example at it then uh you don't want to lose that data permanently you want to have like copies of the data so what you will do with like replication Factor equals to three is say I want three copies of the data so
48:57 uh you're just going to put it into the next three copies as you walk along this ring so here A bunch of companies that uh or data distributed database systems that kind of use consistent hashing and so famously I guess like uh in the context of database systems consistent hashing was like used in Amazon's 2007 research system called Dynamo though in 2022 they actually wrote a research paper saying that when they turn Dynamo into Dynamo d B uh they drop consistent hashing in favor of like hierarchical replication and that's something that you will see more in future lectures but that said consistent hashing is still actually a very powerful and practical idea I think snowflake still uses it for like uh
49:41 something to do with the cashing subsystem and react's Logo over here is also supposed to be like the consistent hashing ring react as a product I think uh folded the company went bankrupt but the on the front page of like wait maybe not bankrupt so don't quote me on that but so they got bought over by like some other company uh and on the front page of H news today there was this like post on open react you can kind of see all the people like having good memories about it uh I have not actually been able to read that post because I was prepping for this lecture but yeah
50:13 question arey half right great question so when you add a new Partition where do you decide to put the new Partition yeah ideally you want to put the partition where it will balance the loader so that might not be halfway it depends on like how many keys are mapping to that space but you do want to spread the load around good
50:34 question uh and I think yeah while we're on the slide uh I said I would talk more about data saxs while we had Cassandra up here so Apachi Cassandra is also in this list it uses it pretty heavily I believe and here has some fun facts for yep before the fun facts what partion geter partition what if the partition T gets bigger than the partition uh could you elaborate on that so um when you're to a partion let's saying on a specific key yeah and then lot of records that so
51:07 the partition gets bigger than what can the partition space gets bigger than what can be stored here uh if I understand the question correctly it's whether like you run out of places that you can put partitions does that make sense run out of what you can store in Partition oh I see if you run of uh let's say a partition run of like storage Bas uh I think that's your question then I guess you would have to do uh add a new Partition to handle that like put one right before does that make
51:39 sense the same key get still the same key that just get bigger gotcha gotcha then I think yeah you would just have to increase your partition sizes like what the limit of what you can support there's no like um magic that this algorithm would handle for that case Yeah question also or sorry
51:58 yeah are very unlucky that two uh key after the cashing almost the same and uh so the location is almost the same so that's not not Balan the uh case right yeah if you're very unlucky uh the question was like if you are very unlucky you could still end up with imbalance this is where you kind of handwave away to like the algorithms and the people they will come up with these like very nice hash functions that will make it evenly distributed around yeah yeah if you are keeping running and sometime you are want to add a new node and at that time after hashing you find it's almost the same hashing location
52:35 after that it's it's hard for you to change the hash function again right yeah in terms of like what you change the hash function on the Fly uh this one I would double check with Angie but I don't think you can really change the hash function on the Fly sometimes if you're unlucky you're just
52:53 unlucky but so uh yeah the reason I brought up data stack in the context of apach Cassandra is that data sax offers a cloud database as a service uh also based on Cassandra and the speaker today Jonathan Ellis he'll be here in like 10 minutes he's the co-founder of data stack he was also apach Cassandra like project chair for six years so that's like the guy in charge of like decisions for where the project is going in terms of the largest known like Cassandra
53:19 deployment that's Apple they actually have over like a 100 petabytes of data with over like 160,000 instances over a couple like thousands of classes and the second like well maybe not second biggest but another big one is like Netflix they have around six petabytes of data with like over 10,000 instances and the reason I'm bringing up like how many petabytes of data they have is that the reason we like this idea is that you don't have to move around all those petabytes of data you only have to move around what's on the partition
53:51 before and now for something a little different uh you see transactions then in more detail next class we have reached a like setup for next lecture stage and the Big Challenge in like distributed transactions is just going to be a transaction shows up we look at this like catalog metadata service to figure out whether it's going to be a single node or a distributed transaction
54:11 in the latter case where it is going to be a distributed transaction meaning that it has to access data at one or more clusters then we're going to have some kind of expensive coordination problems if it's a single node transaction meaning you can do all your processing with just this node that's not going to be an issue
54:27 and so that I think I'm not skipping anything yep takes us to the next slide where if you want your database system to support like multi-operation and distributed transactions we need to coordinate the execution and broadly speaking there are two ways of doing that either you centralize it or you don't if you centralize it you basically end up with this what they call a global traffic C it has a global view of the system and it can decide like uh what's going on at any time so whether the transaction can proceed or not that's to do in a decentralized system the ndes will kind of self-organize and figure out what to do among themselves and in practice most distributed database systems are actually going to use a hybrid of these two approaches so what I mean by that is they will periodically
55:11 elect a leader node and if their elected leader kind of like dies or like their time just expires it's time to move on they will just select a new leader and that leader will proceed to continue this is for like performance reasons
55:26 so the earliest use cases for like distributed transactions were things like Bank ATMs and like flight reservations and some of the code and protocols that were developed back then are still out there and being run today if you're interested I recommend finding Andy at office hours ask him about TP
55:43 monitors but with that examples at this point we are not really talking about like shared this or shared nothing we just have like partitions they can't talk to each other and so in a centralized coordinator kind of like setup uh we still assume that we have this like catalog metadata service that will tell the application server which uh partitions to talk to if it needs to
56:04 with a global transaction coordinator though uh what happens is that the application server goes to like the coordinator and says hey the metadata service told me I have to do stuff to like P1 P3 P4 can I please lock P1 P3 and P4 the coordinator has this global view it's a traffic comp of what partitions are locked or not unlocked and so it will say okay you and lock D Tre I acknowledge your requests you are free to do whoever you want to these
56:32 partitions and later uh when it's done doing whatever updates it has to do or reading whatever data it has to read it will send a comit request the coordinator will just double check with the partitions that it's save to commit and it will send an acknowledgement request back to the application server and that's kind of how the transaction will now
56:54 work so there's a bunch of older systems that are this kind of like simplified model of a transaction centralized transaction coordinator uh transar actually came out of CMU or rather the founder is like the founder is a professor here at CMU he's Jeff Apper so if you're taking web application development this semester you can probably ask him about it uh he's in the software engineering department or what are they call now s3d
57:18 yep and an alternative approach which you might see a lot more nowadays is you have this middleware and by middleware all I mean is that like you have this kind of like coordinator but now instead of like the application server talking to the partitions directly the middleware is responsible for talking to the partitions on like the application servers behalf and it will like send out
57:42 the it will do the locking it will send out the requests and it will send back the response so yep how is this different from the previous example in the previous example the application server was talking to the partitions directly in this example the middleware is talking to the partitions on the application servers behalf but in the previous example we also had a coordinator and we just said that the coordinator is one of the nodes uh previously we had a coordinator and the only job of that coordinator in the previous example was to kind of manage the lock table in this example the middleware manages the lock table and also manages talking to the partitions
58:20 and this is an approach that is actually a little more widely adopted uh a lot of commercial systems do this now so and these examples would be like Facebook used to scale use this kind of architecture to scale out my SQL back in the day because my SQL had no like native support for distributed transactions YouTube also has something similar Google had something similar for ads uh yeah so this is kind of like common
58:47 nowadays but so what if there is no middleware uh so in a decentralized scheme there's no middleware no Global transaction coordinator and using the metad a transaction is just going to show up to some partition and say Hey I want to start a transaction this partition as an example might then decide okay I'm the leader nde so I have to coordinate that between the other partitions it wants to talk to and as part of that now uh after it has establish that like we have a leader note the application server can directly talk to all these partitions do whatever stuff it has to do but ultimately when it's done doing that it has to send a comment request back to the original leader note partition and that leader node partition is responsible for checking that it's safe to
59:31 commit so super quickly there's also going to be this idea of like Federated databases we have assumed or at least when I took this course I also assumed that like the nodes in your distributed system distributed database system would at least run like the same software but this does not have to be the case like the different nodes can be running different versions or in some cases completely different database systems some of them can be posters some of them can be MySQL and your typical like
59:56 environment you will have like post and then someone introduces your financial system uses Oracle there's like 10 different sqlite instances running around basically that's a lot of different data silos and it would be nice if you had a single query interface that could access all of them so Federated databases are one way to do this and what those are are a distributed architecture that uses a single middleware approach ideally you have only like a single query interface
1:00:22 and it can access data at any location so maybe for example it will rewrite the queries that you're sending so that can speak post address dialect to like post address SQL my SQL dialect to my SQL and so on but in practice this is really hard because all these different systems have like different data models C languages and in practice you have to speak like the lowest common lowest common
1:00:43 denominator and additionally as a database developer it's already hard enough like in Project 3 to optimize queries for a single note database now you want to make it distributed now you want to make it optimized across different systems that's just kind of a mess that said it is an interesting idea so uh yeah people do try to do it so as a quick example you have an application server that's a middleware as before you have my SQL reddis and Mr Pickles
1:01:10 uh and the middleware is what's going to be responsible for like sending requests and translating them to these different like backend systems uh through what is known as connectors in the industry Dragon question what would the Cur be like if we are trying to with different there is a SQL so the question is what query language do you use to communicate across different database systems there is like um a SQL standard it's just that everyone has a different interpretation of the SQL standard so I assume you would probably end up speaking like some very limited subset of SQL in practice it doesn't really like there's no standard answer here do I so do the application to determine
1:01:51 which kind of dbms does it want to talk to or uh the middleware exposes some kind of API and the application server will just uh speak that API the middleware is responsible for like translating it into these different dialects so to give a conrete example like
1:02:09 uh there's for example post foring data rappers and what those are is there a way for you to from inside post address you're writing like post address dialect post address SQL you are able to query external data sources so this might be parket files this might be like some other database instance and it's going to be exposed as a post stress table alternatively you have systems like trino or also Presto which come out like meta Facebook and what those do is they also expose connectors to like different database systems sometimes if they understand your query if it's like simple enough they will push it all the way down to like my SQL so like uh maybe if it understands my SQL it will just speak my SQL directly and then only the result has to come back up but if it cannot support that kind of like pushing down it will have to pull the data back up and then it will do that processing
1:02:57 uh in its own layer so there's no like satisfactory answer it's just whatever is supported and we're almost done with the lecture content I guess but so uh this is going to be more set up for next week's lecture uh we need to allow like
1:03:16 in distributed concurrency control we need to allow multiple transactions to execute simultaneously across multiple notes so on one hand we can adapt a lot of the stuff that we have learned from single node database systems but on the other hand we have new challenges for example with replication how do you sync up data across like all these different physical locations if the locations are far apart now then communication is a lot more expensive and notes can go down from the earlier a sheep made my internet example
1:03:43 uh if the Sheep just ate like the network cable then it's a temporary outage but if the Sheep ate your entire server then it's basically a permanent outage so and oh yeah there also the issue of like clock which is like time sync for example my phone says it's like 306 and that clock says it's like 303 getting times to agree across like different computers on the network can be pretty hard if you take distribut it you'll learn more about
1:04:08 it Google spanner is a system that famously kind of put atomic clocks in every single one of like your nodes so that you can get time in sync because the atomic clock is like a very very high Precision like kind of like timing thingy but those are going to cost you like 5,000 to 50,000 per clock and regular people can't really do that everywhere so uh Andie has basically described spanner I think as like one of the most advanced transactional systems out there for the rest of us without like thousands of dollars to put atomic clocks everywhere uh you can look for things like cockroach TB they have a post on like hybrid logical clocks those are some ways to approximate this timing problem just agreeing on what timing is but yeah the key takeaway is like timing keeping is hard and you will see more of it next week
1:04:55 and okay so for last example if you have two different application servers and you have a distributed database that has two nodes note one is in charge of like a Noe B is in charge sorry node two is in charge of like B then what's going to happen is that uh let's say the application server on the left wants to modify a on the right wants to modify B then it can take the lock no problem but now if they want to modify like each other stuff you have a deadlock because they already have the lock and they want to take the other person's loog and in a single note case
1:05:26 okay you can just build the weights for graph I think you have already done this in some homework assignment and you can figure out like okay you have to retry you have to wait whatever but if you're doing this over the network then you have a bunch of problems uh where is the weight for graph is it on node one is it on node two or is it some kind of like central location and because it's over the network you can't do this for like every single thing the communication
1:05:47 cost is going to be very very high so these are just like some problems that you're going to face and as a spoiler if you have of cut theorem like there's no magic solution you have to kind of pick what you're okay with that's next SL the key takeaway here is that distributed database systems is hard and like uh back when I was like interning for one of them you have a whole team dedicated to storage whole team dedicated to like CER execution it's not something that like one person writes everything that doesn't really
2. Jump to
1:06:17 work that said anti likes to emphasize that like most people can get byy without distributed databases because if you ignore like replication most database systems or database deployments are not that big they're in like tens hundreds of gigabytes they're not in like petabyte
1:06:34 scale and if you're interested you can look up the terms like small data and dgb to learn more and in the event that you do need like a distributed database there's like products like snowflake that have already basically handled a lot of these problems for you so if you're a developer that just wants to use a database it's usually way easier to pay them to like build and manage all this yourself
1:06:55 so that should be it for like uh today Andy will be back for the next class and he's going to talk about distributed ootp replication captum and he will have more re examples I would say that like if you have not been talking to Andy about Rew examples in office hours you're missing out because that's like a lot the advantage of having him as your lecturer but yeah with that thanks for having me I need to fix my zoom link uh so yeah so today's speaker is Jonathan Ellis from data sex I'm going to do a quick readout of his bio Jonathan is the co-founder of data STX before data STX Jonathan was Project chair of Apache Cassandra for six years where he built uh Cassandra's project and Community into an open source success previously
1:07:35 Jonathan built an object storage system based on like read Solomon uh encoding for data backup provider MOSI that scaled to pedabytes of data and gigabites per second throughput Jonathan thank you for waiting also it was really nice chatting to prop Moi was here the floor is yours thank
1:07:52 you uh So lately uh data stex is focusing its efforts on building a cloud database based on Cassandra but today I'm going to go really deep into the weeds and talk about how we built the vector index that powers Vector search in Astra our Cloud database as well as in Cassandra uh so just to give a really quick introduction to kind of the the B the foundations of the field
1:08:21 um broadly speaking graph indexes are categorized as either partition based or uh sorry Vector indexes are categorized as partition-based or graph-based and we can simplify it though because practically speaking every meaningful system out there today is based on graph PG Vector was the exception they started with a partition-based index and then they switched over to graph because uh it's it's almost two orders of magnitude faster uh to get the same level of ACC accuracy with with graph algorithms so the the first graph uh design of note
1:09:03 was the hnsw design coming that came out in 2016 and what made this special is that they were the first ones to figure out how to create uh good edges between the vectors in the graph and what they did was they invented this diversity heuristic and what that means is I'm other things being equal I want to have edges to the closest other vectors uh in my neighborhood but in order to avoid being stuck in local Maxima I'm going to introduce this rule called diversity and what that says is I cannot add a new
1:09:44 Edge if the node connected by that edge is closer to an existing neighbor than it is to the Target node so in this uh diagram I'm inserting the the new node in green and so after I've added edges to the three nodes in the lower left all the other nodes in the lower left are closer to one of those three than they are to the green one so I so I'm not going to add any of those nodes as neighbors
1:10:15 instead I'll go to the next closest one which is all the way in the upper right and so that helps me uh improve the quality of the connectivity of the graph the problem with with uh hnsw and and it is still used today in some systems but the problem is that uh it's very memory hungry and so when I started pushing an hnsw based index past uh with with a data set that was larger than memory this is what my flame graph looked like and so you can see that there there aren't any actual Flames there's just one big hill
1:10:56 uh that that starts if you if you look at the tan in the middle that's random access reader. read floats at so that's me reading the vectors off of dis uh to perform the comparisons to figure out if my greedy search is getting closer to my target uh so this is this is a well-known problem with hnsw that it it does impose a fairly uh low limit on the number of vectors that you can insert because it's holding them in memory so a more advanced graph algorithm is called disin and came out of Microsoft research
1:11:32 three years after uh hnsw and it divides the search into coarse and accurate passes and and the course pass is going to be done purely in memory using vectors that are compressed with uh it can be an arbitrary compression scheme in the paper they use product quantization today you also see people using binary quantization and and and scalar quantization but product quantization gives you the best combination of compression ratio and search accuracy and then after you do that course pass you you do a reranking
1:12:09 where for instance if you want to select the most uh the closest 100 vectors you might do the course pass for 200 and then of those 200 you'll load the full resolution Vector from disk and then order those um using those those full resolution vectors so this gives you uh it's basically a free lunch it gives you competitive speed while dramatically reducing what you need to keep in
1:12:38 memory I just want to talk really quickly about how product quantization works because that's going to be important later uh the idea is that I'm going to divide up my Vector into a bunch of subspaces in this case I'm taking 128 Dimension Vector I'm dividing it into eight subsp subspaces 16 Dimensions each and then I'm going to take each of the vectors in my data set and I'm going to carve those up into those subspaces and once I've carved them up I'm going to take each Subspace
1:13:08 and do a k means quantization with it and say what are the 256 um most distinct vectors uh that I can represent this Subspace with and then since I've said I'm going to do 256 that means I can represent each of those centroid that the K means comes up with as a single bite and so I'm I can represent each of my subspaces now as a single bite corresponding to the centroid that I can map each Vector in the Subspace to with some loss of accuracy because it you know obviously it's an
1:13:42 approximation um and so what that gives me is I can compress these vectors by a factor of 32 or uh actually for most machine learning embeddings today by a factor of 64 uh with very high speed without losing a ton of accuracy there are faster compression options uh binary quantization I mentioned is faster finger is faster but you lose a ton of accuracy when you when you switch to those uh by the same token there are quantizations that you can do that give you higher accuracy like anisotropic qu
1:14:17 quantization uh but you give up a lot of speed uh to use those so product quantization is really a sweet spot uh so with with disn uh if we look at its performance characteristics the core search is logarithmic and then the the rerank is linear in the number of course
1:14:36 uh candidates that you pulled out however as commonly implemented it has poor update concurrency and it's still linear in the amount of memory we we're using we've cut it down by a factor of 32 or 64 but it's still a linearly
1:14:49 increasing amount of memory which obviously puts a a ceiling on how large of a graph we can build eventually so uh with with J Vector 3 uh we wanted to address these problems and uh as well as a bunch of other improvements but the ones I'm going to focus on are those two so the we we've we put a lot of effort into building a non-blocking uh index you can insert as well as read from it with without blocking using optimistic concurrency
1:15:21 control and by the way this is my pitch for why you should write more code in Java uh I know that that the class is mostly C++ based but uh Java is actually a very productive language to build systems in uh developer productivity is through the roof compared to C++ and I bolded the important Point here a quote from Cliff click who was the architect of the hotspot jit compiler for uh for for oracles jdk and he says many concurrent algorithms are very easy to write with a garbage collector and totally hard to downright impossible
1:15:57 without one and and my experience matches that and that's one of the reasons I believe that all of the C++ uh Vector indexes use pessimistic concurrency control to my knowledge uh but uh J Vector uses optimistic concurrency control and is much much much higher throughput at ingest than uh than the others um so really quickly how we reduced the memory footprint to a constant amount um and this is using a a a technique that was implemented by Yahoo Japan as far as I know they were the first in an open source index called ngt and the idea the idea is you're going to apply something called quicker
1:16:39 ADC to graph indexes where uh and I I used a new term there called ADC so what that means is uh it's a standard term of art when you're dealing with product quandis vectors and it means asymmetric distance computation that means that I my search Vector my query Vector that's not quantized and I want to be able to compare it to these quantized uh vectors in memory without having to convert one
1:17:07 uh to the other domain because that's that's a copy in a slow slowness that I don't want to impose on myself so I've got my uh cine centroids and I've got my compressed representation of each of my vectors and what I'm going to do is I'm going to take that product quantization code book
1:17:25 and I'm going to precompute partial distances from the query Vector to each sub Vector in the code books and then when I go and I say what's the dotproduct of this query Vector with this uh compressed representation all I have to do is go through those partial distances table and add them up now the only problem with this is that uh you're now memory bandwidth constrainted uh the the actual ual addition is super fast but pulling it out of cache or out of dram into the registers to do the math
1:18:02 is actually your bottleneck now so a a simd genius named Fabian Andre created three papers on gr incrementally improving his solution to this and the idea is you're going to represent your your precomputed distances in a format that can be kept in AVX 512 registers
1:18:23 and so we're going to do that on a per node basis load it from dis when we're doing the search and compute the scores all at once and because we're so much faster pulling those distances out of registers that actually makes up for load from disc penalty and so we've we've reduced our our memory overhead to virtually nothing uh without making it slower uh so that's that's what the memory overhead looks like it's about it's under two megabytes per index that we have to keep in memory so uh in conclusion uh to build a fast Vector index today you need support for product quantization support for reranking uh and you want highly concurrent ingest
1:19:05 and a constant memory footprint uh some links to further reading the dis G in paper quicker ADC and then if you want to nerd out on better quantization with math uh this is the anisotropic uh product quantization paper from Google research at the bottom there and uh thank you for your time and I hope to hear from you if you're interested in working on things like this my email address is on the first slide and I'll provide the slides to
1:19:35 onean thank you does anyone have any questions for Jonathan because if not I have one so uh can you hear me yes yeah so I'm wondering where do you think uh it goes next right now your overhead is like 2 megab you said on a few ago so do you think 2 megabytes is practically good enough or would you like to reduce it further in in terms of the the overhead yeah I'm happy with that uh what I think
1:20:10 the next areas for optimization are how can we uh how can we reduce the number of reads from disc that we're doing and I don't think anyone knows the answer to that but that's definitely the bottleneck now is uh is is doing those reads to do the uh full resolution vectors to do the reranking gotcha I will say that that people have put a lot of effort into trying to improve the quality of the graph and that seems like a dead end nobody's people have tried lots of ideas
1:20:44 and they all maybe you increase it by 1% or by 3% uh situationally but uh past a certain minimum quality the graph edges don't seem to matter a great deal cool thank you then uh yeah it's oh one question yes oh uh kind of off the topic so uh you talked about uh Java GC and C++ um so why is there so much of a difference between Java's GC and B C++
1:21:17 uh share pointer con so I'm going to repeat the question for the mic uh the question is why is there such a big gap between like uh Java GC and the C++ share pointer mechanism for like handling similar
1:21:32 problems I'm not super familiar with C++ shared pointers if it's famili if it's similar to rust's uh automatic reference counting then the uh the key difference is that uh a real garbage collector can deal with cycles and many if not most of the concurrent collections that I work with uh do in fact deal with with cyclical
1:22:03 references thank you cool then yeah thank you again for your uh talk and will sync up on email I need something refreshing when I get finished manifesting to cold a whole B like Smith and Wesson one court and my thoughts hip hop related write a rhyme in my pants intoxicated lyrics quick with a simple Mo recer since I'm a city scker play Waves of Pier rhes I create rotate out aate to quick to duplicate feel a breeze had escate mik's at Fahrenheit when I holding real then I'm in flight then we ignite Blood starts the boil I heat up the party for you let my girl R me my mic down with oil Rec still turn with third Dee burn for one man I heat up your brain give it a suntan so just cool let the temperature
1:22:52 rise to cool it all was say odds [Music]