Ring Buffer

the ring buffer is one of my favorite data structures it's used all over the place like in this Wikipedia diagram that shows a keyboard buffer where keys are being typed by the user and then on some interval it actually gets read by this red arrow and sent to a Target device now we're going to be looking at a more modern case of this today around sensor information but we're going to talk about just the design of the data structure as a whole what the implementation might look like in this case in go and hopefully you'll leave this with an appreciation for this data structure and some ideas of how you might use it should that come up in your future shortly we will be coding this up as a brand new go project but let's first talk about a use case where this could be applicable so let's pretend for a moment that we have a problem where we're taxed with getting sensor information from multiple low powered sensors and we need to eventually get this into a database now often when you look at cases like this you might realize that having many of those connections from the low power device is not a great architectural decision additionally just hitting the database with an insert for every sensor read might not be feasible so we have to think about is a potential model with a co-located emitter and this co-located emitter will take in information and then provide some output to the database on an interval like every 30 seconds the final thing to think about when we come to the conclusion that we need this kind of buffer emitter model is oftentimes what should our maximum batch size be if we're on a timed interval so you know we probably don't want to hit the database with 17 days of information in one batch we want to have a Max like a hundred a thousand whatever the right number is and if we set that constraint of the batch size we then need to think about what should we do if we have sensor data that enters when the size is reached if it's reached should we try to page out old information persist it maybe send it at a different time and so on and this might be a requirement for you but a lot of times we come to this conclusion that we don't want to deal with these more complex constructs like in the case of back pressure where we try to think about how we can adjust routing and input based on telling other parts of the system that it needs to slow down instead of worrying about that level of complexity we might just commit to the idea that the most up-to-date signal from Those sensors is the most important thing in our use case it's certainly unideal to have data loss but it's just way better to keep it simple and get the most up-to-date info our solution design ends up looking something like this or we have multiple sensors collecting info sending it to the buffer and that buffer is sending it to the data store but the question of course is what is this buffer how is it implemented and we know from that diagram on the keyboard that it's supposed to be kind of like this ring like construct now the good news is if we think about this for a moment the design is pretty simple using just an array where the key thing here here is that if we had an array let's say it's an array of size three so we've got our different indexes inside of here 0 1 and 2. what we want to be able to do is we want to ensure that if we ever go next from the index two right or the index two being the length of the array minus one plus one is kind of like a way to think about this operation right so effectively in our case this would be index two plus one we want to somehow make it so that this ends up equaling zero so we wrap around the array and end up with a pointer or whatever we're doing you know one of these red or blue arrows we looked at earlier sitting at the zero position so that we can potentially write or read from that so keep this kind of redirection in mind as we get into the implementation and we'll look at some cool tricks that you can do in almost any programming language to implement this model time to implement as I mentioned earlier we have an empty go file with just a go mod and I'm going to start a main.go file here this will be inside of package Main and we're going to start off with setting up the ring buffer structure so the type here is going to be a ring buffer and then this ring buffer is going to be a struct and this struct will of course hold multiple Fields the first internal field that it's going to have is the data itself so we're going to keep this as a slice with a pointer to a data struct or object that we will be defining a bit later on top of data we're going to have the size and the size is just going to be a way for us to internally specify what the size of that buffer should be there's some optimizations this will do in kind of the go side for the array allocation and so on we'll get to that in a bit and then we're going to keep track of the last insert we did so last insert which will be an integer and the next read that we did as well also an integer so you can kind of think think of these as pointers to where in the array we sit and since this is going to be a time-based model although I probably won't be implementing time in this exact video we'll just set it up to have it so emit time could be like a time.time that the user specifies and allows us to you know say 30 seconds 45 seconds and so on so when we effectively look at the ring buffer kind of from a visual standpoint what we know that we have here is we've got this data structure data and this is our underlying array and we know that we're going to keep track of our insertions and our reads so reads are probably going to start here so NR for next read and we'll have 0 3 2 and then this will be an empty one at the very end and we know that last insert is going to track what the last insert is in here and keeping these in mind knowing that we're tracking them will be crucial to our emit logic and even to a degree our insert logic as we get deeper now I also mentioned that inside of this ring buffer structure I have a data field so let's Implement that as well we'll bring this up a little bit here so you can see it and we'll call this the data struct and data struct is really just a holder of some small values the data structure is going to have a stamp which will be time dot time inside of it and then we're also going to have a value and the value is going to be a string whether we keep track of the time of the insertion is going to be kind of up to our implementation but it'll be cool to kind of make fake sensor info with with a Time attached to a potential arbitrary value which will represent as a string next let's implement the Constructor for this ring buffer so I'll send this a little bit higher and we will do a func and this will be a new ring buffer and this new ring buffer is going to be specified as a certain size we are going to emit again that time piece just to keep this simple for now and it's going to return a pointer to a ring buffer all right so what we can do here is we can set up the address of that ring buffer and we can fill the struct to kind of initialize some of the key values so here are some of the key things that we're going to want to consider in the initialization the first thing we know is that we actually know the size so in go there's a bit of a benefit that we could do by pre-allocating the size of this slice slices are kind of like vectors or lists by saying that we want to make data and we want to specifically make data of the size okay and again it's a very very small optimization but how go slices work like a lot of libraries it's going to pre-allocate a certain underlying array and then as you hit the limit of that it will grow it and grow it which is going to require new allocations this will just omit that since we are at a fixed size next read is going to start at zero which is also the default value for integers and go but for last insert we are going to specify a value here which will be negative one so this will be a way for us to identify when no inserts have occurred a second an insert occurs in the life of this ring buffer this should never be negative one again and as I mentioned the uh emit or the emit timing if you will is something we're going to not worry about right now so this is a perfect ring buffer Constructor that we can call to create a ring buffer the insert function is going to be implemented to add an API for bringing new items into that ring buffer so once again I'll bring this up and this is going to be a funk it is going to be a method which is going to be attached to the ring buffer itself so let's attach that to ring buffer and we're going to call this insert insert is going to take an input which will be of course the type data and we don't actually need to do a return here because it's just going to be this insert that happens now here's where we're going to calculate where to insert in the ring buffer you might remember that we have an understanding of the last insert and next read so the first thing that we want to do and kind of this tricky piece I was alluding to earlier is that we are going to say that r dot last insert equals the r dot last insert plus one so this actually works even if last insert is set to negative one right because Plus One will start us at index zero if for some reason our last insert was at zero and so on it would just increment perfectly now of course the problem that this is going to create for us is that if we're at the end of the array it's going to go out of bounds when we hit that plus one so the little trick that we're going to be doing throughout this exercise is to actually modulo against r dot size so if you think about what this is going to equate to pretend you have an array and the length of that array is five so if you're doing an operation where you say okay so last insert is three three plus one equals index four that's a perfectly valid operation right and if you add a modulo in here for this so we'll do percentage sign length or I guess percentage side five in this case and you do need to worry about kind of your PEMDAS order of operations thing so three plus one modulo 5 is still going to equal four so you're still going to get that same plus one operation but the great thing about this trick is if we were at the end so we were actually at four and we moduloed to five what this is going to end up being is 5 modulo 5 which is going to equate to zero so that is effectively the trick here where when we hit the end and do the plus one as long as the modulo is there we're going to guarantee to wrap back into index zero so a neat little trick we're going to be using this throughout the rest of the implementation so we've got r dot last insert set and good to go let's now look at r dot data and we will do r dot last insert so we've kind of preemptively moved the last insert up and now we're going to use this as the place that we put the input since it is a pointer we're going to do a reference to the input value and then the last thing we need to do when we do this insert is check to see where was next read relative to this last insert so if we do r dot next read equals equals r dot last insert the key here is we want to ensure that if last insert reached the next read that we move next read forward so I'll continue programming this and then maybe we'll just kind of draw it out to make sure that we're all on the same page so if next read equals equals last insert all we're going to do here is check to increment the next read next read needs to do the same looping principle so if we do r dot next read Plus one and then we do the modulo once again in Access r dot size this is going to be the correct calculation for next read now let's think about this logic a little bit here in case it's hazy for anybody so if we were to put out our buffer for just a moment let's pretend we are in that case where the buffer is completely filled up so we've got an array it's again our buffer which is of size three and let's pretend for a moment that we have values in here 3 6 and 7. now next read is starting at zero which is where it should be so NR right is going to be at zero it has not read anything yet and then what happened at seven is we've got last insert setting here right Li is to 7. now let's imagine for a moment that Li moves over so we're going to pop back here and we're going to pretend that Li overwrote this three in made it in eight so now Li has reached this point in the array now what's the problem here well the issue is that next read shouldn't be eight think about it eight is in fact the latest value so we really want next read to always be pointing at the oldest value inserted to start from there from the admission so this is when these two are equal as we did our expression we effectively want to take next read in move it one index up or wrapped around if we were at the end of the array so hopefully that kind of makes sense we basically want to keep next read in front of that last insert pointer with insert in place we're ready to implement the emit Logics this will be the last method on the ring buffer we'll bring this up here so it's easier to read and we will instead of insert call this emit now emit is not going to take any parameters it's just going going to be in a mission call and a mission is going to return a list of these pointers to the data objects so to start us off here we're going to start by capturing the output that we will collect as we iterate through this is going to allocate a new slice of data now do note that this has some memory overhead of course but these are Pointers to the data object so for the most part it should be minimal for us with this in place we're now ready to start looping through and figuring out what we want to pull out of the ring buffer and as a kind of visual representation here this is quite close to the idea obviously ours is time based and unlike this example we talked about how the red right pointer should be able to overwrite existing things if new things were to come up regardless it'll be a pretty simple for Loop for us to put together now what we're going to be doing here and it'll be a little more obvious later is we're going to first check to see if the r data at next read is filled up so since we have these arrays or lists of pointers to data they can in fact be nil so if they don't equal nil we are going to capture them into the output so the output then becomes this command where we want to append to that output that data array will be returning and we're going to specifically append the r dot data next read so we will open this up it will be the next read and then that object is going to get appended inside of here and we'll clean this up by just specifying that we will be returning that output once we are all done and this will be r dot next read because remember next read is part of the read ring buffer so now we're appending this in and capturing it all of that looks pretty good and once we have read it what we're going to do and this is maybe a bit of a design Choice you'd want to think about we're going to take that r dot data at the r dot next read so r dot next read and we are going to set this to nil so this will kind of clean out of that data structure the nil object and it keeps it clean helps with debugging but could have some like memory overhead doing garbage collection like there are ways to implement this where you just never clean stuff out and just continue to overwrite existing data but that has some trade-offs too so we're just going to keep it simple for cleanliness sake and set it to nil now once we have gone through and we have checked if next read isn't nil and whether we need to append it we then need to check to see if next read equals equals r dot last insert okay now if next read equals r dot last insert this is where we want to break out of the array because what we've done is that we have effectively gotten to the last inserted element there's nothing else that has been inserted for us to deal with so we will break out of the for Loop here again this for Loop has no conditions as you can kind of see here I'm trying to keep it all in frame sorry for jumping around let's get it right there so the for Loop has no conditions this is going to be our break condition it actually is one more condition we should handle here we should actually say or if last insert equals negative one because remember we started the last insert value out and the Constructor is negative one so if for some reason admit gets called and there is no data because last insert is negative one we need to just pop out right away and break this Loop because there's really nothing for us to send out all right so we have got the condition for adding things things in we've got the break condition if we've reached last insert and then of course if we get down here because we have not reached last insert the last thing we want to do is increment next read so you probably could guess where this is going we're going to do that same operation we did before Where We Gather what would be r dot next read plus one but of course we need to have that wrap around so we're going to do the percentage sign and we will do r dot size to ensure we get this so I will I see my head is blocking this a bit let me drop it down there now you can see this kind of expression here so this is the entire function let's make it smaller so you can see it great and then let's just make sure we're super clear as a last step on everything that's happening so emit is going to get called probably based on some timer right we know that it is going to return the data and this data is going to be captured over time in this output thing that we're calling now the for loop as mentioned is condition list so the for Loop is going to continue until next read reaches last insert that represents that we've read everything at this point in time that has been inserted as we're going through assuming that next read is not sitting over top of a nil value we are going to add to that output and we are going to set next read once read into a nil value so that we can clear it out assuming we did not reach the end we are once again going to move next read up which is either going to be incremented by one or wrapped around if we were at the last element and then of course as a very very final step that output that we accrued we are going to return that as well so now we've got our logic in place here and we're looking pretty good it does look like we have a small error somewhere oh last insert that's my bad this needs to equal equal negative one an equality check not an assignment check but otherwise the logic looks great and this should do our mitts and this should do our inserts now I think we're ready to write a simple main function that tests this out for main I'll go to the bottom of the file as usual and make sure that I type up here so my face isn't blocking it and we will do a funk of main this is just a standard main function to kick off our package and for main we are going to capture a ring buffer using our ring buffer Constructor we'll set it at size five and we'll start off with just a simple use case where we print out an empty test so effectively doing an emit when nothing has been filled into the ring buffer we want to make sure that works so this will be an empty test and after the empty test I'm actually going to be using a package called spew spew has a function called dump and while my head's blocking it a bit the great thing about dump is it will take whatever you give it it'll follow pointers it'll de-reference them and it'll give you a full text output of everything known inside of that data structure so we are going to dump what RB dot emit returns and that will be a great first test for us so I'll just cancel out while we're here and let's do a go run of main.go and you can see that empty task returns an empty set of data that's exactly what we'd hope for in the case of zero insertions so let's go back into Main and let's Implement some insertions so what we'll do to do some insertions is I'm going to just kind of capture the alphabet to increment over the letters in the alphabet so we can do this with runes and go this will kind of respect the ASCII table and the values that underlie it so we'll start with a and I don't know what comes before a so let's just start with a minus 1 and I will eventually be incrementing current roon as we insert things in so we're going to do a simple for Loop here and what this for Loop will do is initialize a variable to zero and we'll do 10 iterations here so while I is less than 10 I plus plus and inside of this we're going to start off by incrementing current Rune so current Rune will start off at the letter A in the alphabet as we get going and we're going to do an rb.insert using our API and this will grab the data and the data struct is going to have two Fields inside of it stamp in value for the stamp I think the easiest thing we could do is time dot now which is going to be like a sensor giving a read at a current time and then for Value we're just going to take the string representation of the current Rune and that will be what we gather so you'll notice that I chose 10 here and the reason I chose 10 is I'm actually hoping that this is going to be overwritten as we get deeper the example that I'm sort of thinking about here is that we know that we've got a b c d and actually we won't even worry about e just yet let's pause on E actually no we'll we'll capture e so we know it's of size five fair so since it's up size five at some point the ring buffer is going to be filled with a b c d e now when we go in and increment or do another insert what we'd expect here is for f to take over a and then the values of b c d and e to remain the same and then we increment again and B will get erased and so on and so forth and of course as we talked about next read should be kind of moving in front of last insert as we Circle back around here in the Final End state that I think we should expect is to be in a b c d e f g h i j per the alphabet so our end result when we admit the thing that we're expecting is f g h i j and let's see if we get just that so we are going to capture kind of the same output from before this value was oops did I see if I can bring that value back there we go so we'll copy this empty test from before and then outside of the loop let's do a full test and the full test will just run and emit once again so we'll save this up we will do go run main.go and the output got a lot going on but hopefully you can kind of see some of the key values here actually that will capture it for you right there let's look at these so we have got F through J so f g h i j this is that ring buffer re-wrapping around calling a MIT and then Reed is just going through from zero all the way to the end and returning these values to us wrapping up there are a couple things that are worth pointing out first off this algorithm slash data structure is doing nothing to consider our needs around thread safety so if we did take it a step further and do that time-based emit we probably want to consider some type of mutex or something so that insertions aren't coming in while we're attempting to do the emits additionally we might even want to consider something like that for insertions if multiple sensors might be coming in perhaps you're like an HTTP Handler that could be firing off on different go routines and inserting data another thing that I wanted to mention is that if you find this expression quite ugly this kind of clever calculation that we've been doing what we could do is we could have actually attached a type instead of int to let's go back into our browser here and let's or our terminal and let's do main Dot go instead of using ins for last insert and next read we could have introduced a new type something like type Index struct right actually type index int and what type index int would have allowed us to do is to put these as this type that is effectively an INT and we'd be able to attach methods to it specifically we could have in theory attached a method that represented next so instead of calling this again kind of ugly calculation from an API standpoint we could have said last insert.next and it could have wrapped this functionality kind of creating a bit of an abstraction for the reader of the code or people using this I suppose I also mentioned earlier that emit is setting values to nil this does have potentially some overhead but I think it's going to be pretty small we're probably only concerned about premature garbage collection from these values when we wouldn't normally have to do it but generally speaking I I think this is probably fine and then the last passing I'll call out is that go has a ring package now the ring package is actually quite different than what we implemented they're using I believe like a linked list that is kind of pointing to these things so the ring could in theory grow uh you know that has trade-offs like the idea that it's less contiguous memory there's pointers flowing it might not end up in a CPU cache and they also have some extra apis for like joining rings together and stuff it's it's been a while since I've looked at this package but it does kind of approach the problem a bit differently nonetheless it's in the standard Library so if you want to check it out see if it meets your needs nonetheless whether you implement this or use their ring package I hope you found this kind of interesting you know I think the cool thing about this data structure is that it allows us to look at really simple Primitives and know that just small modifications around them can allow us to solve real world use cases which I find really fun and interesting so happy building and I'll catch you in the next video

Blog Post: https://joshrosso.com/c/ring-buffer A ring buffer, or circular queue, is my favorite data structure. I’ve used it countless times throughout my career to solve a myriad of things. Today i’m going to take you through an example problem, the design of a ring buffer, and an implementation (in Go). Overview: 00:00:00 Sensor Use Case: 00:00:41 Design: 00:02:54 Structs: 00:03:58 Constructor: 00:06:42 Insert: 00:08:23 Emit: 00:13:30 main Func: 00:19:38 Closing: 00:24:03