Kiar: Key/Value Store with MVCC-Based Transaction System

SF Scala: Kiar - Key/Value store with MVCC based Transaction System By Sandeep Virdi

Recording: SF Scala: Kiar - Key/Value store with MVCC based Transaction System By Sandeep Virdi

[Music] everyone who's watching uh thank you very much for coming to this month's sf style meetup tonight we have one of our uh tonight we have uh san diego who has done a talk with us before back to do a great talk on kiara key value store with mvcc based transaction systems they do i hope i got that right over to you sandy hello and welcome everyone to scala is of meetup my name is sandeep um thank you everyone for taking the time to attend this talk a special talk a special thanks to solar for organizing organizing this meetup today i'm going to be talking about kiara key value store it's an mvcc based transaction system so motivation i've been interested in databases and how they work last year i got my hands on this paper mentioned in the slide after reading it i wanted to implement it disclaimer i'm not a database expert by any means there is 50 plus years of literature out there if i do if i do make a mistake do feel free to correct me at the end it's a learning experience for me as well i'll try to add all the links that i've used in this slide at the end in a slide since i do not want to assume anybody has read the paper i want to build up some context and then work towards the algorithm described in the paper i've split the the talk in sections and hopefully that would make this talk more approachable so the first section is will we look at how things are done on a disk based systems and for this we'll look at how postgres handles things then we could look at format in our case it's columnar format and then we could look at what apache arrow brings to the table then we look at the various components from the paper then we can look at the implementation in scala if time permits we could look at what but how and we can talk a little bit about zeo and what it has to offer and if you really have some time then we could look at like improvements what i've learned um etc so context let's look at a small demo um i'm going to present my terminal now and i would like if anybody could not see if i would like everyone to let me know that they could see my terminal and the fonts are fine if anybody could let me know that it's fine then i could proceed i can i can see the terminal i just make the fonts a little bit bigger if you can for people with a smaller screen than mine is that good yeah yeah like i said if anyone uh thinks it should be better on twitch let me know yeah please feel free to let me know i could wait um but this is just a regular pro squares database i have a tmx on two sessions on so let's let's do this so i'm going to create a simple table and add some data to it it's nothing special here so i'm going to start a transaction with isolation level serializable and let's do a simple select um you can see the contents of the trouble again nothing special here so let's do something a little bit interesting let's try to get the x million x max so databases have internal metadata that they use to keep track of copies or versions of couples that they create during transactions in progress these are called x-min x max these values usually get populated by transaction that last process this shuffles x max you can think of x max equal to zero here represents infinity so one way to think about it is 755 was the last transaction or timestamp uh of a transaction that updated this tuple and this is open till infinity we and we'll get more into what these things mean uh in in later slides so let's look at the transaction id or the timestamp id so you'll notice that the so think of transaction id as a logical timestamp not wall clock timestamp um here timestamp here here you can think of timestamp as a monotonically increasing number even if it says transaction id if you think about it as timestamp it'll help um when we talk about the paper and how it's doing its uh it's it's realization and portrait um okay so let's do something a little bit interesting and let's try to update a tuple with id one all right so now let's try to do select again but this time with ctid so if you if you look at the x min here and you see the the timestamp id is the the current timestamp id for the transaction that actually is being used in the xmin um and that that tells us that this this physical version was updated by this at this time in this transaction um okay so the cd id here shows the page and offset at which this new tuple lives so the city id is something new and this is the this represents the page and this represents the offset all right so let's do this let's start another transaction in the terminal below let this also be at isolation levels realizable so each transaction is creating a new version of the tuple or the database object the way to prove this assertion is to print out the cd ct id in this new transaction so let's go ahead and do just that and long behold we are we are selecting the same tuple um and here you can see the id but if you if you look carefully the cd id and the page offset is different than this one so the page is the same but the after that which this couple lives is is completely different excuse me all right so let's look also at the timestamp here and it is as you can see its last was 256. now it's 257 and we could be it holds with our assumption that it's a monotonically increasing number all right so i'm going to do an update in the transaction in the in the lower in the lower window does anyone can anyone guess what the result of this is going to be i'm going to try to update this same top all with id1 um all right because this is not that interactive i'm going to do it and if you see the current thread is blocked so the main takeaway here is writers don't block readers readers don't block writers but writers do block writers okay so let's do this let's commit the transaction that's running in the upper window um can anyone guess what will happen to the transaction below if i commit this transaction um all right let me just do it all right so you see that we encounter the sterilized access due to concurrent update error which is what we expected because of the isolation level so the the gist of this is that you're not allowed to create new versions from an uncommitted transaction and so so and and another one is the fact that the trip the database was holding an exclusive lock on the tuple when we are doing these transactions um all right so now that we have that done let's um let's do another small demo so i'm going to create the databa the tables again and add the values and okay and so let's do let's do a simple selects i hope by now everybody knows that what x-men x max the city id represents um all right so now again let's start a transaction at isolation level it's realizable in the upper window right and let's go ahead and start the transaction at read uncommitted at the in the lower window so just fi read uncommitted that's the key here all right so let's do a select so that we see that the data is identical there's nothing monkey going on all right so let's go on the about terminal let's do and let's do a update at let's do an update for for tuple with id1 again nothing special and then let's check our result and we see that the id one has been updated let's come down and let's do an update on the tuple with id 2 right you see that here now let's do so again a question here if i run this select in this transaction um what would be the result um let me just run it and let's let's look at this results so the transaction sees its own rights right we we updated the id 2 and we see that it's being updated but it still sees the for id one it sees the original level even though we are running under iso isolation level read uncommitted we should actually be seeing this value since this was just this was just created in the transaction what this tells us that postgres is running at a higher isolation level even if you actually ask it to run at a lower isolation level so another way to understand this which is important for understanding the paper is like these ranges add validity and they they add a validity range a begin and end validity range to these database objects um this begin and end define the the you can think of the big the beginning and define the validity range of this physical versions of the logical object because we are not changing the actual objects until we commit so these are just like uh logical objects till we commit hopefully this this gives this this this gives you some context how things are done on on disk space databases so i'm going to go back and i'm going to go back to my slides and share and let me do that all right okay so i hope this gives uh some idea about how database systems manage versions of data objects and their visibility um they're under underneath the hood they're actually using metadata like timestamps during transactions so let's focus back to the paper pull each component apart and try to understand them let's begin with the main memory column store format um so main memory store format before we look at the the store format let's look at a very very very high level how this based systems database systems work database this index buffer pools etc data in fixed lens structures called pages so buffer pool is a cache that actually moves the data between the disk and the main memory so whenever a query is executed we check the index get the page id and look up the page in the buffer full if it's our present and get it from disk like any other cash flow that has like eviction policies and this could get tricky when we are dealing with 30 pages because now we need to flush them to disk before eviction so in general look at the pointer in general when you get a query you look up the index it'll give you some some page you go try to fresh the page if it's not in the buffer pool go get from disk if it's if the buffer and you bring it back into buffer pool if the buffer pool being a cache if it needs to evict something now it needs to think about which page to evict and this gets trickier if you have read dirty pages because of like uncommitted transactions and then if everything is good you return back the data to the consumer um this this complexity of uh how transact this complexity is also seen in transactions and conclusive control um and it's a and and and you you also need to keep this extra metadata about where the page resides whether the page resides on this or in the buffer pool cache is it dirty is it not we've not even talked about the lsn database objects and other database processes we can skip that for now um this is an over simplification but i hope this helps to give some context of um how this space systems work under the hood most of the issues described here will not be relevant to the in-memory data store or in-memory database so the main memory store format so irrespective of a row or a columnar format in memory database in in an in-memory database we are going to organize the data in in chunks let's call them blocks and these blocks will typically hold two kinds of data one is fixed length another one is variable length your fixed length being in date long etc and variable variable length being variable binary etc um again at a very high level when you execute a query it's going to return it's going to return a logical id from which you could get the block id and the offset and then which you could use to get the data from the underlying data store so again you have the index you ask the index it will look up and it'll give you a logical id in the logical id you could split and get the the block in which data resides from the block if you get calculate the offset because that's also part of the index and then you could return the data back so the main issues that you will encounter in an in-memory database in in-memory databases are pointer chasing cache line messages data copying etc which are very which are quite different from disk oriented databases uh a point that i want to highlight in the slide is variable length blocks need another layer of indirection we actually store the value in a separate memory location we then take that memory location and add that to a fixed-length block and then store that in an index so there's a layer of interaction and i hope that it is understood why it exists if not we could talk about it in the at the end after the after that uh talk all right so apache arrow um definition from say from the website apache arrow defines a language independent columnar memory format for flat and hierarchical data organized for efficient analytic operations on modern hardware like cpu and gpus arrow memory format also supports zero copy reads for lightning past data access without serialization overhead when i first read the paper one of the biggest barriers to implement it was the in-memory corner format described in the paper after a bit of searching i found out about apache arrow so a patio is an umbrella project with a lot of sub projects and one of them being the columnar format you could read this specification online excuse me so vectors so the main abstraction in apache arrow are vectors that are two base vectors based fixed vector that is used to define and sorry base fixed with vector and variable bit vector that can be used to define all the value types that a column store can support so let's look at the source code of of of one of the vectors defines a concept of the liberty buffer let's examine how it's tied to the paper every fixed width or variable length vector has a value buffer and a validity buffer if you look at this there's a validity buffer and a value buffer uh this is the internal state of every uh i'm showing only fixed with vector but it's the same for the variable with vector as well so the the the value buffer is used to store the values but the validity buffer shows the information whether a value is present at an index or is null furthermore it can do this very cheaply since effectively it's a bit set so validity buffer if if you read the paper in in section 2.6 it talks about efficient scanning which is highlighted in the slide as as version positions so version position represent ranges inclusive of start and exclusive end if we say if you have a column that has 10 000 elements but in reality there are elements present from 1 to 100 and from 9 000 to 10 000 without any knowledge if you scan the whole column you will end up tracing cpu cycles and also incurring a lot of cache misses this is where validity buffers come into play since they are very small they could fit into the cache lines and you could generate the version positions on the fly uh or even maintain them on the side just boosting the scanning efficiency so if we if you look at the paper they are described on this top left hand corner so let's say that we have this column that has the names of all the users and let's say that these this column is chunked into blocks shown here currently there are three blocks shown in the paper so the version position here gives us the information that in the first block there is no element present in the second block there is one element present and that's also represented by this this arrow here in the third block we see that there are two elements present and these are also shown by these arrows here we'll talk more about this uh structure later in the in the slides but this is where the concept of ability prefer is so helpful you get the version position functionality almost for free via validity buffers when you use apache arrow okay delta storage if you recall the demo about postgres we saw that the transactions were creating a new physical version of the tuple at some new location every time the transaction is executed this new location is called delta storage let's try to understand what a version vector is and how it's tied to a delta storage so let's take a quick look at how the complete record the complete database record is returned so given a key in in a row based format given a key will jump to some memory location of from which you can calculate the width of the co of the row and then you can return the whole row in a columnar layout given a key you'll need to jump at individual indexes in each column build out the whole record and then return it so keep this notion of building the the record by jumping at individual locations in mind because this will help us understand a few other things down in the slides so let's say we have a transaction t that affects a row with t and tuples um with the interval we copy the tuples in the new location excuse me call the delta storage and proceed with the transaction this model seems to be fine if you're dealing with the robes format um but and relation in relation to databases usually do not have a wide rows so this might just work out fine so in this example given the transaction t even if the tuple is is if you say you have tuples t1 t2 up to tn even if you want to work with tuples say just the attributes tuple 1 2 and 3 given the nature in which we access this information you might just end up reading the whole row if you recall about the whole idea of storing these things in pages um this that will help understand why i'm saying what i'm saying and you you might just you just end up copying the whole draw in the in the delta storage and work from there now imagine a corner layout if we had a table with hundred columns and say only two columns participated in a transaction then we do not need to copy all the other values instead we copy only the deltas involved i.e the tuples and their updates to better manage the idea of delta storage in a columnar database the paper introduces a concept or an indirection layer called version vector a version vector is a structure that's shared across all columns in the database for example a table with hundred columns there will only be one version vector additionally it's only used during transactions if you look at the slide inside the delta storage a transaction t1 b we only copy tuples t2 t3 and t10 and their updates and this forms a delta version record so here given a column it couples t1 t2 tn when we copy the during the actual transaction we only copy the tuples t2 it's update d3 it's updated on t10 and its update in the delta storage and that we use the version vector as a pointer to this entry so this complete structure is called a delta version record and we'll talk more about this so if you recall the whole idea of writers do not block readers and readers do not block writers by adding this layer of indirection you're effectively limiting the scope and the surface area of synchronization excuse me so if say it tuples t2 t3 t10 that are participating in a transaction you could still have your reader zip through the whole um except for these three attributes and work with that data without being bothered by ever uh synchronizing on this data and we saw how during transactions the the the transactions had an exclusive lock on the object that you're working with in a disk based system um so now that we have some more context about these things so let's see what we have covered so far we've we have some knowledge about delta storage a place where new double versions are stored for the lifetime of the transaction a version vector a structure described in the paper that helps print transactions in common database and a delta version record that contains all the attributes and updates during a transaction excuse me so when transactions are taking place concurrently you could end up with a chain of delta version records pointing to each other if you look at the figure in the slide the version vector the version vector entry is pointing to a linked list of delta records these records are ordered by timestamps and there are two there are a couple of ways to order these these records one is oldest to newest and the other one is newest to oldest the paper actually talks about ordering these timestamps from newest to oldest so during transaction we land on up there we just got there either it was an index or maybe it was sequential scan the entry in the version vector is null the column is not the column this column has not yet participated in any transactions if if we so the first thing we do is we copy the the delta record into the delta version vector proceed with the transaction if the version vector entry is not null we know that there is a pointer to a linked list of delta variant triggers we do some validation and a pendant entry to the head of the chain so this is the word vector if you see if the pointer is to a null that means the this column has not participated in transactions you copy you create a new delta record and you copy it into the delta version record if it points to a linked list of delta records then you do some validation and add them to the list so if you look at the previous slide we had we had this transaction we had these tuples in it this is nothing but each tuple now is sorry the this group of tuple in t1 this is what the delta record is all right excuse me version maintenance let's look at the delta version record entry format each entry has a start and end timestamp a value and a transaction id and some other metadata fields i'm not adding i haven't added transaction id here usually transaction id is of type long this is to mitigate the whole wraparound issue for example in postgres the transaction id is 32 bits and you have 4 billion ids if you do not run vacuum you will end up wrapping around and now the transactions in the past will start to appear as if they are in the future the paper talks about drawing the start and the end time stand from the same global counter to help with this realization order um just a hint that we we saw the same in postgres as well where we had the monotonically increasing number the time stamp number the x min and x max so say that this is the so say that this is the this so 50 to infinity represents the latest delta record entry uh its predecessor here is 30 to 50 and its predecessor is 20 to 30. so say a transaction at timestamp 65 comes into this version vector and starts to look for a delta entry to use it'll come and look at the head the 65 is between 50 and infinity so it'll choose this delta entry and use that for its transaction say another transaction with timestamp 45 comes comes to this version vector and starts going up the chain so it will first look between 45 45 so if it will first look between 50 and infinity it'll fail 45 is between 30 and 50 so it'll end up choosing this delta record and it will proceed with the transaction so with the previous transaction we saw the delta record entry this is what a delta delta record entry looks like so i hope you're slowly building up with these concepts um all right so version maintenance concurrency and visibility so let's talk about concurrency visibility of the delta version entries the the slide shows that the state of the version vector for it for an attribute say column a now we do we do support speculative beats i.e uncommitted reads say we have three transactions in the system how do these transactions keep track of which delta entries were committed say you have these three transactions say this transaction started at 65 so it gets this entry transaction 2 started at 45 gets this entry but there is no notion of committedness attached to the entry itself these entries are not tagged in any way so one way to do it would be to have an external data structure to store metadata about the the committedness or whether the delta entries are committed or not but now all transaction transaction validation process redo log garbage collection etc need to access this data structure this this structure will end up requiring a lot of synchronization it will have a lot of contention which is not a good idea for a uh in-memory database so the the the golden rule of anything in memory is is is represented by the acronym cream cash flow or anything around me so if we go back one slide and we see that you know say that we we have the transactions 65 accessing this delta version entry and then we add that metadata in this data structure well now this this will be accessed not only by transaction three but also two one could be one as well it could also be it it could also be it will also be accessed by the validation process it will also be accessed by the redo log and soon this will become the bottleneck and source of contention um so contention on external data structure means a lot of cache meshes and this is a big node for in-memory databases and if folks are interested we could talk more at the end of the end of the talk about the latest like design that people are trying to do and achieve with all new infrastructure coming into play or hardware coming into play version maintenance concurrency and visibility so let's look at this version vector again if this is the current state of the world vector the latest entry as shown by tension 30 n times time infinity let's say that there's a new transact new right transaction the system and we want other read transactions to read the new version that will be created by this right transaction but also maintain the notion that the newly committed version is not yet committed newly created entry is not yet committed what i mean by that so say that this is the state uh say a transaction at time stem 45 comes in it's a right transaction it'll copy this value create a new entry here and it'll start working with that then there's another transaction that comes in at say 50 and it uses this slot and it uses the previous value but we we want the the the newbie transaction to be able to know when this right transaction was was uh the the transaction at timestamp45 was committed so that it it knows when it can come in and this is important during the validation phase in a transaction's lifetime it needs this information otherwise it will need to abort or retry all right so the way to accomplish this is to first create a new version entry take the start timestamp from the new entry and add it as an end time stamp to its predecessor now make sure that the start timestamp of the new entry and the end time stamp of the predecessor both have the msb the more significant bit flipped are they are negative as shown in the slide now we do not need any external data structure to keep the information about uncommitted versions all the information is present within the timestamps and since timestamps are 64-bit they follow the golden rule of cache friendliness during the transaction commit stat step or phase we do need to check whether the delta entries processed by this transaction whether they were committed or not if yes then go ahead and commit if not either reschedule retry again or report based on the kind of transaction we are dealing with so again so this was the previous state of our persian vector say a new transaction came in at times time 50 and we we got the new transaction has timestamp 50. so what we'll do is because it's a right transaction and it's not yet committed we will flip the first bit of the right of the of the start timestamp add the the same value up as the end timestamp of this previous or its predecessor close the the ability range and this is now the new validity range for this transaction mind you is this is all the information that we need uh when we need to know whether this delta version entry is committed or not it stands on its own excuse me so say now we are at the point where we can commit a transaction at that point we come back and the say the this transaction the the transaction that's at the start timestamp of 50 um it is it gets a commit timestamp of 65 at that point we come back the we update the timestamp of this delta entry to be 65 without the negative sign and also update this entry and add 65 without the negative sign mind you still the ranges hold the validity has not changed for this value or this delta record is still valid within the same range as it was uh when we were looking at when when we were looking at it at minus 50 or 50 times 150 so a a a few observations um during transactions first writer always wins and we saw that in our postgres example as well remember isolation levels realizable if you try to update the value that is being updated by another transaction you're bored so in here say that we are we there's a this is the current state of the version vector a new transaction comes in a right transaction with a timestamp 65 it cannot use this value and try to use it in its transaction why because that might result in cascading upwards which is again a bad idea for in in memory database um and generally it's it's a performance bottleneck and it has implica implications not only in in the comment phase but also redo in the validation phase and the redo do log phase and other database processes as well even in during garbage collection so to make things simpler this is the this is the simplest approaches that that's mentioned are applied so the so the database that's based on the paper that's described in it that i had linked in the in the slide is called hyper it does not have right right conflicts because all the rights are single threaded and we could talk more about this again at the end i don't want to get into that right now yeah um and okay we've already talked about cascading awards excuse me let me just have [Music] order all right apologize okay precision locking so precision locking is a very old technique described in a paper from 1981 the basic idea of this technique is to validate the predicates present in a transaction so say that you have two transactions and they have a where clause and each very class will produce a predicate space if there's an intersection between these two predicate space uh with the transaction that is against the with the transaction t that we're valid validating it against the abort the transaction if you look at this slide uh there are four predicates there are four predicate spaces mentioned here and we're trying to violate the transaction t these four predicate spaces were selected because they were generated by the transactions that completed during the lifetime of transaction t so here you see that we have predicate space excuse me p1 p2 v3 p4 and we are trying to validate a transaction and we see that there is an intersection with the data object present in this predicate space so we abort the paper talks about creating a predicate tree emerging the nodes if they have a common node if you look at the predicate p2 and p4 they share the same node hence they can be merged as shown by the image on the right so here if you look at p2 and p4 they have a common node b so they get merged here and we say it's it's an and so b 15 and i equal to 1 3 15 and i equal to 1.7 right so for the transaction t to be valid its predicate space should not intersect with p1 or p2 or p3 or p4 if we squint we realize that we are dealing with boolean algebra here and we could use d morgan's law to boost the performance of the precision locking at the implementation yeah but now we are entering the domain of query optimization uh which is a feel in itself and i'm going to skip it for now uh so how do we generate this predicate space during transactions we add delta version records to an undo buffer and we need to do this to support the redo log we can you we can reuse the undo buffer to generate the read set free ie pre images of the data objects and for the right transactions we also need the post images or the values after the update you know observation about precision locking is we do not do serializability checks on the record level but we do this at the attribute level this makes it cheaper and and more accurate less false positives so if you if you think about an example where you have the same tuple that's participating in two transactions but the two transactions are updating two completely different attributes of the tuple periodically you should not have any conflict but most validation most databases in the validation phase will be too conservative and they will abort those transactions more often than not all right let's look at some code um let me share my intellij then we could look at the implementation and now we could try to try to tie it back to the oh but sorry about that sorry can you can everyone still hear me i got disconnected for a second i wasn't sure what happened but yeah we can see you you just stopped sharing your screen hi okay all right okay is is this fine can everybody see this yep it looks good to me yes if anyone on twitch if it's not okay for you guys let me know and i can ascend it to make it bigger looks good to me thank you all right so let's start with the the the column abstraction so it has some internal state which i'm going to not talk about um so you could initialize it currently it supports in float and big end uh it's protected so you could easily override it so there is some internal state i'm going to skip all this this is not and this this is nothing new or interesting let's look at get instead so one thing i do want to mention is that the the column is genetic in a and b where a is constrained as a subtype of the base with vector um so this is why when we are reading we need this uh implicit evidence that we could read this this basic vector and return this value to the consumer um so when when you get the logical index you create you get the the the block and the offset um from the so you get the index and the offset you get the block and then you read from the block the offset and you return it um i hope this is this this is uh it's pretty straightforward there's nothing like folks who knows cause there's nothing um special but if anybody wants to talk about this we could talk later at the end of the at the end of the talk similarly for set again get the index and the value you do the same you get the block we then write it and there's a corresponding right hopefully this is clear why we have a and b and we do the same the only difference is uh if the block is full you do some internal state change and you update the blocks all right so one thing that i do want to mention i don't know if i'll get time to talk about xeo but this is a pretty cool uh abstraction from xeo it comes from the stm package um it's it's i i i highly recommend folks who at least check it out um so the the way this works is you could have multiple readers but one writer and the logs that you create you could promote a reader to writer and uh and and and yeah in a critical section you could do that it's based on a paper uh but i'll let folks do that i don't want to digest too much into this so that's the the column abstraction let's look at the the store abstraction um all right so so the store is basically what we call a table in um in a database what this is it has some internal state but it's storing the column name and the column you could create a column and add it to the store and then you could get the value out of the map or out of the store given the key excuse me given the key um so one interesting thing about this is the the storing the value as any uh but effectively this map is actually a heterogeneous map excuse me where we are storing different kinds of um columns to make the the uh the column or to to add to make the this abstraction of get column more type save i'm using this thing from shapeless called typable that helps with runtime casting or typesafe casting it's it's it's actually pretty neat trick what it does is it has a and b you create typicals for that and then you just ask if you check whether it's an instance of the the column that or the the type you're matching against if it is you cast it and then you again you need uh default values or values of that type and you try to cast them if they all work then you return them as an instance uh and given that these are in the flow four block if any of this fails will just escape and it will fail and we'll get an option uh we'll get a nun back all right so this is uh store let's look at store let's look at something different here so this is basically a map of key to delta version vector i think the only thing that i want to highlight here is this notion of composite key and we will come back to this all right delta version vector um so excuse me let me just sorry about that so the paper describes the version vector as a data structure that points to a linked list of delta version records participating in the transaction effectively what you have is a lookup by some key to get to a list which this list in the end is again a list so if you remember the whole um the the the transaction having tuples and then the the transaction the data lt the data entry the data entry nodes actually forming a linked list but the data entry itself could have tuples in it that participate in the transaction so you have a link list inside a linked list the data center the data structures mentioned in the paper are caspased these are these are all the operations that perform the pointer updates are are based on cash doing operations on nested lists and dvm is tricky so a simple workaround i came up with a simple workaround so the first key insight here is that the lookup is by a key so you need to some site of some sort of map the second is that the value itself is dynamic so remember not all columns participate in transaction so you want the inner structure to be dynamic as well so effectively now what we want is a map or tree uh the infrastructure to be a map or tree so now we have converted the problem from a nested list to a nested map which quite frankly doesn't seem any better but there's a very simple trick already general trick that you could use you could flatten the map if you if you change the structure of the key and this is where the composite key comes into play excuse me um we will look uh in the next we will look why it's important and how it helps us solve the implementation as well so let's look at the transaction implementation so you could think about the slice transaction as the as effectively a read transaction and there's a counterpart to this that's a right transaction and whenever there's any difference i'll highlight in the right transaction bit but what's with whatever is different so let's go up let's look at the this again this is there's some internal state for now let's not worry ourselves with all that so let's go to the start so so once when we start the transaction we register it we have a ledger and this ledger is basically storing the recently committed transactions and active transactions so we register ourselves with the ledger then we search for entries so one interesting thing is when you given an id how do you know when to read the value from the column or you go ahead and read the value from the version vector or you start searching the the linked list for the for the for the the the correct value so the for that there is in in the paper it described a check called in place version check actually i came up with this name but it's a very simple check all it does is we check whether the current transaction id is equal to the in timestamp or if it's greater we know that there is since we are ordering all our entries in the linked list by newest to oldest if this condition fails we know that you know the latest entry is actually in the column itself not in diversion vector and i hope by now everyone or hopefully understands why we have this absolute here because we could have negative values in the timestamps okay so so we do this another interesting bit about the whole flattening of map of maps so the paper describes the version vector as a pointer to a linked list but it doesn't describe how the entries in the linked list should appear um if you went with the regular linked list then you could have the pointer for the key to a heterogeneous list where you'll first have to search the column that you're trying to look for the entry for and then you've got to work from there towards which entry uh actually satisfies uh these validation rules anyway so this is the in place version check say if it succeeds uh say if he says okay we've got to read the column on true we go and copy the first the the first thing that we do when we if the column has not yet participated in a transaction is we create a delta version entry he updates some state and then we return but let's look at this bit because this is interesting and this is where we are adding undo buffer entry into the undo buffer this could also be used for building the redo log itself for the for recovery um so this is where we add the call this is where we are collecting the three images or uh this is where we're collecting the pre images for the validation state so let's look at this excuse me uh this is a very simple case class um but the interesting bit here is the roaring bitmap uh if you have if you this actually is an open spec a lot of data processing frameworks use this you any if you just go to if you search for roaring bitmap uh you'll end up on their website and you could read about it i don't want to go too much into detail but it has really really interesting cool applications one that i really like is where uh the golang version um they created a a search engine uh using rolling bitmaps which is insanely fast for for for some use cases um and if you see the internal structure of these things it's basically a bit set and why they're insanely fast use cases is because of this internal structure um anyway so we we store these values these before images into our bitmap then we could actually use these for doing our boolean algebra and do the validation to check if there's any intersection this is you get all that functionality for free if you're using uh an abstraction like this otherwise you have to hand roll it here you get it for free all right and so this is for read transactions let's look for write and as mentioned in the paper for the rights you actually also get the post images the updates of the values um i hope that makes sense we'll be starting to read and the post images or write transactions all right so excuse me all right so say that we we do not we should not feed the uh should read column is false then we got to do more work and we have to search the version vector so of course here we have two checks and these are described hopefully when we look at the implementation of this uh it'll reflect of what we've seen in the slides all right so first is let's look at this so this is the start and start and end check so what this is is we loop on the deltas on the on the version vector and try to find the first entry in the vector that satisfies this condition where the transaction id is between the start and end timestamp that's all there is to it but the interesting bit is we are doing this in a in a in a loop um so first things this might seem too this some this might seem very expensive but remember that we are storing our entries newest to oldest so more often than not you will hit the entry that you're looking for at the head or the upper region of your uh vector or list so this is this this this is actually is not that bad um the all right so if if you do find that if this is true if the status is true we did find it then we again update nothing special [Music] if it's false then we return from this then we go ahead and do this second check so this is a little bit interesting and this is where the whole idea of adding the adding the negative or flipping the msp comes into play so let's look at this [Music] so we have some state we are trying to update a version vector this is a ref and this is an update of a ref um i will if you if you are reading this commentary uh you might understand what's happening if not i'll try to explain so here we are trying to update our um so first let me just go let's let's forget about all this uh extraneous stuff let's let's let's just say that if this check passes say the current transaction is actually between the start and infinity then the first thing we need to do is create an ancestor right and then that ancestor will be the copy is actually the copy of the predecessor but with the start timestamp negated because it's uncommitted once we have that we will create the child or the predecessor with an nth timestamp negated once we have that we have to switch the pointers um so what we do is we split the the current vector at an index where we found the entry and we update that this vector is still not visible to the world so we go ahead and update the child pointer inside the vector once this is done you go ahead and make the global change so i want to i want to like talk a little bit about um concurrency and visibility and all that good stuff because the the main complexity here is concurrency and visibility of these versions rather than like how it's being done so first let's go back and understand why we are doing this um so there are there are two there are a couple of ways to do this so the first approach that i was trying to do was okay the paper suggests everything should be caspased i started looking at cash-based linked list solutions and i landed up on an ibm site with which actually has an implementation of the caspase linked list but there is the if you read the whole uh like the the set of blog posts or articles what it talks about it it suggests going uh it suggests against using these uh cache-based linked lists and they they go in great detail why not to do it first it's very hard to reason about it you might end up with like partial updates or you will end up with like partial visibility you you you could see threads having sids getting threads able to look at partially updated or corrupted data which is not what you want for an uh a database second the reason paper suggests cash-based operations is because casp-based operations cannot deadlock that's the biggest and that's the that's the reason people try to reach for them um so if so the the ref abstraction and it's common in cats and in zeo if you take a ref abstraction and back it with a immutable data structure you almost get not almost you get the you get zero visibility issues because the data structure is immutable you'll always have the complete data structure and there is no way to have partial rights you might have a wrong data in the data structure but you'll never have two threads reading incomplete or partial data that's one thing when using the the idea of using the ref the the the other interesting bit here is um this so the so uh remember i talked about um the notion of the the the the database hyper database having single right threads and the reason for that is we have not looked at indexes we have not looked at other database processes that actually go along with this garbage collection etc excuse me having a single thread minimizes contention when it comes to all those other database objects and uh processes which makes uh which makes not only the database performance but also the engineering that's involved uh very simple or easy to manage not simple but easy to manage anyways so this was a long-winded way of saying or talking about this because because i feel like there is a lot here and some sometimes get lost and the paper also and there's a lot of literature that talks about um cash-based uh data structures in databases one of these reasons is this and why they're good and why they're bad anyway so if we do this we now have the we've done this this um all right so we we we check the start we do this check and we do this check and if they both if one of them passes then um we go ahead and we during those checks we actually go and update some internal state which is again adding stuff to the read and write the read set and the right set that we'll use for predicate validation so once we have done this we we get we generate the commit time stamp this is just again going and asking the counter for a value then you build the predicate space this in our read excuse me this in our read transaction would be getting the reset and the right set and adding them then we do the validation hopefully this should be pretty straightforward now the only thing here interesting is the fact that we need to get the transactions that were committed during the lifespan of the transaction that is under validation so we need some some mechanism to get those values but it's not that hard um once we have that uh then it's uh it's then we basically go in and do our validation for read against read set foundation against right set there's a bunch of to-do's which hopefully uh makes you understand uh there's a lot of things that are missing uh but general idea and the implementation is there um all right so once we have this uh we could pass or fail and then you know we could move on again this is an iterable um so effectively you should you should never get this value all of the values that i get or the validation or transactions you'll get should be this um and it should all work the good thing or the heavy lifting is actually being done by the for each part from the zeo but i don't want to get into this for now anyways so once you get the validation you need to restart your version vectors remember once you get the the commit timestamp you go back you re-time these timestamp all your versions that had the the msb flipped once you do that this is again nothing great read times because this is effectively read you don't do much here because in read transactions the commit timestamp is actually the start timestamp and yeah so you don't need to do much there but during the right transaction you have to go and update the the vector and update all the entries with the flip the msp with the new command typestamp okay so once you do that um you set the once you've done all this you go ahead and set set the value in the care column this is effectively previous we've already looked at this there's nothing special here again you see i have comments here about real logs garbage collection which is another big one then you update the version store now you want to make this visible globally so that all threads could see the updates that the current transaction has done and you want to update the ledger um and again this is for the read you'll actually go ahead and delete it from the active and update the recently committed transactions and once you're done you return the result of your valid validity and your time um hopefully this was this gives you some idea of the implementation and hopefully the slides actually add some context of why we are doing all this and how it's all how it all ties ties back together to the paper all right let me share my oh yeah it's on this side so you have two monitors let me share my slides again all right so just if i just a time check how much time do i have uh i generally don't mind how long you go go go for us we're not at a physical venue where we're going to get kicked out yeah so go go as long as you you feel you need to yeah okay sure thank you um so zeo i touched upon this um this actually it's it's a very rich and complete uh framework and this is um the and if if i was doing a a web application and if i had to choose a framework i would choose this in a heartbeat there is so much goodness in it if folks have not seen uh i would highly highly recommend everyone to go and have a look uh batteries included again i have not uh shown the tests and the the testing framework that comes along with it it has its own generators the execution model the runner everything is beautifully baked in the i feel one thing that's not so great about the scala ecosystem is the choice paralysis there is so much choice out there that you know i like i just want to like the i want to implement the ideas in my head and not worry about what library or framework i have to deal with and the binary income incompatibility and all those good things so i think um i could talk more about this but that's a different talk this is uh i yeah i i was i was uh i was very impressed uh by by uh zeo so i i would die i would highly and definitely recommend anybody who wants to um uh have a look please do uh improvements oh boy um things that i have not talked about um and the paper actually just just glosses over is indexes garbage collection testing that's a big one you um how do you test a database you cannot just think of it as a crud you you have to be a little bit more um but you have to be a little bit better than that i i have a few ideas but again different that's a different topic altogether data compression recovery retry issues i haven't shown this but the the whole idea if you your transactions have a uncommitted value you have the you have the reset all you have to do is you have to just check that i have not added that but the the retry and i think this this is very trivial to do in gio excuse me it exposes the whole schedule abstraction uh but yeah this needs to be like you know thought through one of the like after implementing just the the paper and the idea the other thing that i when i was sitting and thinking about how to test it it and how to debug it one thing became very clear was if you turn the implementation into a state machine this becomes actually um it would help along in the testing and the uh the the implicat the implementation becomes much clearer it tests in it helps in testing and be debugging the system as a whole just the general performance um the literature in the paper talks about hardware um there's there's the there's other literature that talks about tying threads to cpu and then um making sure that you perfor you do all the um like you you your performance um you you actually okay there's a better way to put this you try to utilize the hardware to squeeze the performance um by tying the threads to cpu then you exporting the fact that you're running with this new architecture you do not even go across cores on the socket in the on the chip um there's like few other things that you know the when you start researching and reading about this it's just uh it's very it's very interesting but it's very hard to do on the jvm uh the max that you could do on the jvm is basically uh when a machine have a cpu tied to a process but that's most of that's that's the max that you could do um yeah there's like you know other stuff that i've missed uh but yeah this this this is like you know if the this is the the the the list of things that i i would like to improve if i get a chance but with that i would like to stop and complete this talk and if there are questions i'm happy to take them you