Arpit's Newsletter read by 70000+ engineers
Weekly essays on real-world system design, distributed systems, or a deep dive into some super-clever algorithm.
Write an engineering article with a concrete timeline in Markdown format from the following transcript.
so writing multi-thread programs is essential to build high performance applications but to ensure correctness we need to lock the critical section wrapping the critical section with locks is the most common way to ensure correctness but it's but it reduces the throughput of your system so can we do it without locks in this video with Hands-On examples we'll understand what optimistic locking is how to use it what makes it different and more performant and pessimistic locking when to use it and most interestingly how it is internally implemented so here I'm using a cloud-based IDE called replit to code this out because it is cloud-based I do not have to set up anything locally and I just need a browser to get started replit has an amazing llm assistant named Ghostwriter which is extremely powerful because it is vertically trained on programming and software development knowledge base and the best part is it spits out answers and suggestions in the context of the code that you are writing apart from this webplate has something called as bounties which can help you make some money on the site as a bounty companies post paid projects on web applications AI tools Discord Bots and so much more you can pick the one that interests you complete it and get paid just sign up on replit with my link in the description down below once you sign up on the home page itself you can see a section called bounties when you click on explode you can see the projects that are listed there and the amount of money you can make out of that pick the one that interests you apply for it and just get started so the link for the sign up is in the description down below go through that sign up for my link and this to be honest is a great way to make some money on the site doing what you love so do check that out so now let's head back to the video so the most common way to ensure correctness while writing multi-threaded program is pessimistic locking wherein you wrap your critical section with acquiration of Lock and release of lock so when you have n threads who want to execute in the critical section only one thread is allowed to move in which can execute the critical section while everyone else keeps waiting only the thread that is executing the critical section once it releases the lock then one of the thread which was waiting is allowed to move in this ensures that in this critical section only one of the thread is active at a given time and is executed this ensures correctness but now you can clearly see how this could become a choke point now imagine you are having a severely High uh multi-threaded program which is all trying to execute the same critical section all of them trying to execute the same critical section only one of them is succeeding While others keep waiting so although you would want to leverage High number of cores but this one choke point is severely affecting the throughput of your system this is where optimistic locking comes in so the core idea the core intuition behind optimistic level it's really simple if there are two threads what trying to do some operation at the same time somehow make one thread succeed and other thread fail so if I have two threads T1 and T2 what if the operation that they are doing one of operation of one of the thread is successful while the other one does not take any effect and you get to know that it fit and then you have control to do whatever you want to do with it right we'll take an example and then we come back and look at advantages and disadvantages of it so the way it is implemented is with a very simple semantic called comparence file right we'll look at this and then come back to Advantage and disadvantage it would be it would be very natural flow so the compare and slab semantic says that let's say if I have a variable called count and I want to change the value of count to new value so I would write count equal to new value if I have two threads one of them wants to set count to 11 other thread to set the count of that value to 15. now if both of them come at the same time how do you know which one came first which one came second you could take locks and all to do it right that's pessimistic way of doing it but what optimistic approach says is you would want to one of the operation to succeed while other operation to fail how would you do that with compare and swap semantic it says that you set the value of count to new value only if the current value is old value so uh on a high level a pseudo code of it looks something like this if count equal to equal to 10 then you set count equal to 11 otherwise don't set it right now similarly if you have two threads one want to set eleven eight foot five comparence web count comma 10 comma eleven and another thread who wants to set it to 15 would do compare and swap count 10 comma 50. if we look carefully when these two threads execute at the exact same time What would happen one of them would succeed because the current value is 10 one of them let's say thread T1 came first it executed so then this 10 became 11 but when T2 came in the current value is 11 so this component swap statement would fail so its components of count 10 equal 10 comma 15 it would fail now it's under your control on what you need to do if it fails that's the beauty of optimistic login that you have an option to handle the failures however you like if you want to retry if you would want to ignore ignore if you want to throw error to your resource it's totally up to you right but this is the whole idea behind optimistic login but if you look carefully you would say but this is still not foolproof what if two threads did this there is still contention there's still bunch of code that needs to be executed no compare and swap operation understand this component swap operation is atomic in nature which means when this comparent swap is running no other like this your CPU will not be context switching at all that's the whole idea it's a instruction that is running that is one-to-one correspondence when it's running on like sorry when the instruction is executing your CPU will not your OS cannot contact switch OS context is once the current instruction execution is complete right that's the whole idea so when we talk about internals you'll get to know why it is atomic and how it is atomic and how it is implemented so let's take an uh before this let's jump into advantages and disadvantages of it so here we can see that what we are trying to do with optimistic locking is that here we are allowing n threads all the threads to execute the statement but only one of them successful other pay or other has no impact or no effect whatsoever so in a system where there are rare conflicts and fewer contentions optimistic locking gives you better throughput and pessimistic looking because pessimistic locking is being negative and it wants no matter what your threads wait for other thread to complete and whoever is wants to impact or whoever wants to execute the critical section right which is where the problem is it reduces the throughput but if your contentions are fewer and your conflicts are rare this would be much better choice second is there is very low locking over it because comparing swap does not require any fancy thing it just requires under support from underlying architecture underlying CPU if it's there it's very lightweight third is we get to pick how we want to resolve conflicts because in pessimistic locking because it is uh it is a sequential execution in the critical section there the chances are conflicts if you write good code are zero right so there it would happen one after another so here with optimistic locking you know that this fails so it's up to you you'd want to retry you'd want to ignore you'd want to throw error it's totally up to you so you can devise a very fine grained experience around contentions but disadvantages are the implementation is not trivial when we look at the code we'll see how it's not so intuitive to write code for optimistic login but it's essential if you'd want to go for it for a better throughput and it's not meant for all use cases there are some use cases for which you cannot use optimistic locking there are most use cases where you can Nokia occasionally use soft chemistry blocking but you need to know that there is no one golden solution in computer science there's always trade-offs you get some you lose some so understand where you can use up to a segment when you cannot so in a simple example where you can do compare and swap optimistic locking just works because you have native CPU support otherwise if you are doing bunch of stuff let's say making call to database doing this doing that what not it's big enough thing it's better to take pessimistic login if you're doing far too many things then sorry so now let's take a quick example a demonstration of optimistic law and we'll see how it is implemented and that's where the fun part is now first let's talk about the implementation how it is implemented here it's a very simple C code on what you end by the way you will find equivalent of this in any programming language you write for example in Java also you have it Go and has sync Atomic package so look out for Atomic packages and that's where you would find uh like that's what you need to use when you're using optimistic login but the idea is look at this very simple example here what we are trying to do is we are trying to create two threads both the threads when they spin up they execute the function increment count which is this and we wait for both of the threads to complete what this increment count does it just does count plus plus but instead of just writing if it was pessimistic locking you could just take mutex do count plus plus and release the mutex right but now because you're doing Optimus locking now see you have to do so much you have to write so much code so what we are doing first we are first atomically loading the value of the count variable first we are storing it in Old value so you read the old value then you compute the new value which is old Value Plus One and then you do an atomic compare and exchange of count old value and new value which means that internally the weight is implemented it would be doing count equal to new value only if the current value is old value if it is not true and this would return true or false if it is true which means it was successful in doing it which means there was no contention while this command executed so all good but if it was contention it would have returned false and which means your increment fate now it's up to us on what we need to do we could hear recursively invoke this increment count function if we want to it would keep on going until it succeeds or we could just throw the same error back to the user that hey we could not increment the account or we could just ignore leave it as right but now you see how the code that would have been simple with mutexes become very verbose when it came to optimistic login right and that's what the fun is and that's why you could see that it would not suit all use cases you need to figure out where to use optimacy locking where to specimistic login right but yeah this replied I use it very often I put it like I put the link in the description down below check that out for Kit play with it quite fun to play with optimistic okay now let's go deeper and see how it is implemented so how it is implemented will peek into thus the Assembly Language code that this generates so GCC hyphen capital is main dot C sorry this would create the file main.s which contains the assembly code this is a simple language code of my corresponding C code that we just wrote this code here the magic happens here you could see p thread create P thread join this is the main function that we wrote see this is the main function that we wrote increment count P thread create P thread create we are passing it but what happens in P thread create this is what happened this what our increment count looks like as a function now here you can see an instruction which is this look at this it's c m p x c h g l it's compare exchange L is for long lock means it is atomic instruction so when this instruction is happening your CPU will not contact switch and here it takes arguments and whatnot will not go deeper into Assembly Language code but you get the idea what's happening this is the instruction that is doing that magic now here good thing is this instruction is going to be executed on the underlying Hardware so your underlying Hardware needs to support or needs to expose an instruction like this for you to leverage leverage comparances otherwise you could not otherwise a lot of implementations of compare and swap in case your CPU does not support the instruction compare and exchange is using mutexes so you are actually using pessimistic clocking to implement optimistic locking in case of CPU does not support it but if your CPU supports it which in today's day and age most CPU does then it translates to directly one CPU instruction c m p x c h g l and this is the magical instruction that does exactly what the function does is it sets the value only if the current value is what we passed so old count old value new value is almost very similar to the semantic that your CPU instruction expects and this is what makes it Atomic because it's you are leveraging the underlying CPU to ensure that your program does not context which you're using that instruction that is given to you by CPU which guarantees that your context which will never happen when because instructions are executed in atomic fashion this instruction will be executed in an atomic fashion this is what your CPU is ensuring so leveraging the underlying stuff is what would give you that superpower to build a query to have an efficient optimistic locking implementation so few things just to summarize that your underlying architecture and compiler needs to support that whatever Assembly Language or bytecode it generates it leverages the underlying CPU so if it if your compiler or your CPU architecture does not give you the ability then internet will be implementing it would have Atomic package but it will be using pessimistic locking to implement it otherwise if it supports then great it can directly translate into the corresponding CPU instruction directly but although that's a worst case you would anyway it's it would still be a win-win but you could just model it in a different way right but peek into the internals of source code to understand how it is it's quite fun and quite interesting go through just look out for just Google search cnpxcn cmpxcn yes uh so just just Google that instruction and see what it does you will discover something new right but yeah this is how this is what optimistic blocking is like there is no one way to implement it but you get the overall idea of optimistic locking where you try to build it such a way that in an atomic fashion two things are executing one of them succeeds other one fails you capture the field one and see what you want to do with that optimistic locking in case of database exactly the same optimistic locking in case of multi-threaded applications like this exactly the same the concept Still Remains the Same implementation could vary depending on the situation right but I showed you one of them where you are using threads and how it leverages underlying CPU to do it right but the idea is you need Atomic way to do this update so that you capture one succeeded another field and voila you have your own optimistic login right so just Google search virtual systems use optimistic locking and how they do it it's very fascinating topic you will stumble upon some really interesting stuff out there and it will and you'll have a time you'll have a good time exploring them and yeah this is all what I wanted to cover in this one I hope you found it interesting hope you found it amusing that's it for this one I'll see in the next one thanks Adam [Music] [Music] thank you
Here's the video ⤵
Super practical courses, with a no-nonsense approach, are designed to spark engineering curiosity and help you ace your career.
Arpit's Newsletter read by 70000+ engineers
Weekly essays on real-world system design, distributed systems, or a deep dive into some super-clever algorithm.