GopherCon 2017: Understanding Channels | Kavya Joshi

[00:00:01]good morning everybody how's everybody doing sufficiently caffeinated uh cool so my name is cavia and I'm here today to talk about channels specifically to open them up and show you how they work now I assume everybody here is familiar with Go's concurrency Primitives go routines and channels in fact I bet a number of you came to go and choose go for its concurrency is that actually true how many people here primarily use go for its concurrency so that's a fair number of you um so you don't need me to stand here and tell you that these are important that channels are important but there's another thing channels are inherently interesting what do I mean with an example say we have this um simple task processing function all it does is get a list of Tas tasks and for each task calls a process function now the process function itself you can assume is some long running function that makes a network request and what have you now if we had to take this program and scale it to a hell tasks we know how to do that we bust out our favorite concurrency tools go routines and channels and Implement a simple task Q model so we have a buffered channel to store the tasks uh we then run a fixed number of worker gur routines to process those tasks and finally we'd arrange for the main function to get the tasks and send them over the channel to the workers each worker receives a task processes it and repeats simple um but the point here is that single channel in this single program already illustrates some very interesting properties about these data types right first of all they are gutin safe secondly the buffer channel can store values and pass them from one G routine to another and does so in first in first out order and I assume most of you know this but that channel can also cause these go routines to block an unblock now that's a very unusual list of properties for a single in a seeming seemingly noio data type so what do you do when you see something like this it's like when somebody shows you a magic trick what do you do well you take a second to appreciate it and then you try and figure out how it works so that's what we're going to do today we're going to delve into the internals of the runtime the G run time to try and understand how channels have these properties and how they work how they work uh to do that I will first talk about uh what happens when you make a channel we will then look at the mechanics if s and receives and uh finally we'll take a step back in uh look at the design considerations okay then so in order to use a channel you have to first create it and we do that using the built-in make function now you can create buffered channels which have a non-zero capacity or you can create unbuffered channels uh or synchronous channels today I will primarily be talking about buffer channels but in any case making a channel gives us this uh this black box this this channel struck with these properties right we'll come back to the last two properties uh later since they have to do with runtime behavior in some sense but uh looking at those first two properties if I told you I wanted a go routine safe first in first out struct what would you say you'd probably say cavia just use a lock with a just use a que with a lock and it turns out that's exactly what the channels do making a channel allocates this hch struct it has some number of fields that Implement a que it has some other fields that we'll uncover later and uh it has a good old mutex um now the implementation of the queue itself is pretty straightforward uh there's a circular buffer or ring buffer so this is one that conceptually wraps around itself and and the send and receive positions from that buffer are tracked using those two indexes send X and receive x with a quick example say you make a channel um of capacity three you have those buffer with three slots and initially it's empty uh so send X and receive X is zero after your first NQ send X is incremented after two more nqs um the channel is full note that at this point again sendex and receive X have the same value this is very informally the definition of a circular buffer and finally there's a DQ so this time the receive index is incremented now this H Chan struct is allocated on the Heap and uh make returns a pointer to it so when you make a channel this fancy H this fancy Channel type you get is really just a pointer under the hood it's a pointer to this H Chan and this is why um we can simply pass channels from one function to another despite goes pass by value semantics and both functions end up enqing and deqing from the same underlying buffer right we don't need to pass pointers to channels for those semantics because the channel is a pointer under the hood okay so at this point we have a channel now let's go ahead and use it this is our program with with um all the non-channel related code removed uh for Simplicity and we're interested in how that send and receive operate now I'm going to assume that there's a single worker so we have a single sender and a single uh receiver for the sake of Simplicity but everything I say translates just as well to the case of multiple senders and multiple receivers I also going to call the G routine running main G1 and the go routine G2 executes uh the worker function so say at the beginning of the world the sender comes along first and so G1 comes along first and sends task zero at this point what needs to happen is pretty obvious it acquires the lock because it's going to modify that H chance struct it then performs an NQ like we saw before and finally it releases the lock and goes on its merry way now the thing to note here is the actual enqing is a memory C copy it copies task zero into that slot of the buffer okay now G2 comes along and uh receives from the channel and it mirrors those operations so it acquires the lock it uh Dees again this is a memory copy so it copies whatever is in that buffer slot to the memory corresponding to the variable T and uh it releases the lock and goes on its merry way pretty simple so the thing to note here is that this coping into and out of the buffer is what gives us memory safety when we use channels right the only memory that both that both Guru teams access the only memory they share is the H Chann and that is protected by the mutex everything else is just copies of memory this is also why our favorite go concurrency adage makes sense you've all seen this before right yeah okay um so back to our program uh G1 has sent G2 has received and we have an empty Channel again so say this task G2 is processing is taking it a really long time so it's just sitting there and processing while G1 keeps sending so G1 sends another task and another task and another task and another task now it can't actually send task 4 right the channel is full so what happens here well g1's execution is paused and it's resumed once there's space in the channel so it's resumed after a receive now we knew that what we are interested in today is how how does this pausing and resuming of goutin work and the answer is by calling into the runtime scheduler now now don't let the name scare you the concept um is quite straightforward um goroutines are simply us space threads so they are created and managed by the go runtime not the operating system and user space threads are generally preferred to O to OS threads because they uh tend to be less expensive with respects to Resource consumption and scheduling overhead and so go um chooses user space threads and the runtime is responsible for implementing them uh now these user space threads have to actually run on OS threads and the part of the go runtime that's responsible for that is the scheduler and it uses an MN scheduling model so the idea here is you have some number of G routines and a few operating system threads and the schedul multiplexes those go routines onto the few OS threads so in this example we have two OS threads and up to six go routines because the scheduler takes care of swapping in and out those go routines um at a high level Go's MN scheduling is described using three structures M represents an OS thread G represents a go routine and P holds the context for scheduling what that means is p holds so there are a fixed number of P's and these P's hold the L list of goroutines that are runnable that are ready to run and these are called run cues right so the P's hold the Run cues and um anytime a goroutine needs to run in an OS thread that OS thread must hold on to one of these P's because that's where it gets its workload from in some sense everybody with me cool um so why do we care about this the the reason we care about this and and where the power of this MN scheduling model really comes across is when a goutine needs to be paused like when it performs a blocking Channel send so what happens here is that channel that the channel send on a full Channel calls into the runtime scheduler the call it makes is go park um so it calls into the scheduler and at this point when we enter the scheduler the currently running go routine uh the go routine in yellow that is G1 right because G1 made the call and what the scheduler does is it changes g1's state from running to waiting and then it removes that association between the operating system thread and the go routine effectively freeing the OS thread to run a different go routine and then the G the scheduler goes ahead and does just that it pops a goutine off the Run que and schedules it to run on that OS thread so what we basically did here is walk through a context switch right when we entered the function when we entered go park G1 was the running go routine but at the end of this function when um when this function returns a different go routine is running so um this is cool this is cool because this is good for performance what we've done is blocked our go routine we've blocked G1 but we haven't blocked the underlying OS thread right we said these OS threads they're expensive so the go so the go runtime strives to not spawn and to not manage many of them and it does this by doing this clever switching out of the go routine and freeing the OS thread to run other G routines cool so this is great um we have successfully paused our go routine but we still have this problem that we have to resume it so once uh a channel receive happens and the space in the channel we want G1 to run again at that point so how do we do that um the the answer to that is G1 sets up some state for resumption before uh it calls into the scheduler okay so it turns out the H chance struct stores waiting senders and receivers uh and it stores them using the struct um the pseudo G struct it's simply another struct and this pseudo G contains information about the waiting go routine what what is this information this information is the waiting go routine so it has a pointer to the gine and it also has a pointer to the element it's waiting on so the element it's waiting to send or receive so in this case our program G1 the goroutine G1 it creates the pseudo G right so G over here is set to G1 and the element it's waiting to send is Task four so it creates one of these structs it puts it on the Channel's send Q um effectively setting up the state for a receiver in the future to use that information to resume G1 and finally it calls into the scheduler and the scheduler pauses it um cool so where's our hero or heroine where's G2 okay so our receiver finally comes along and the receiver is going to perform a receive on the channel and this is the state of the channel at this point right there's a full buffer and there's a waiting sender so what G2 does at this point is it first dqes the element from the buffer right it re it receives task one and then it pops off the waiting sender it pops off the pseudo G it enes task 4 into the buffer okay this is interesting we'll talk about that but it enues it and then finally it has to go in res G1 it has to set G1 to runable now the reason G2 itself and qes the element is also an optimization it's so that when G1 finally runs G1 doesn't have to mess with the channel G1 doesn't have to acquire the lock right okay so let's um go and set G1 to runnable again here because we're messing with goutine state it means calling into the runtime scheduler uh the call here is go ready this is G1 telling the scheduler to make G2 run G1 runable um so G2 calls into the scheduler and this time the scheduler sets G1 to runable so is the goutine off in the corner State waiting so it switches that back to runnable and then it puts it on a run que um and then it returns to G2 and G2 the receiver will continue executing now since G1 is on a run queue it will run at some point it will eventually be scheduled and it will run so this is pretty cool at this point we're basically seen how both sides of Channel sends and receives work but you know what's even cooler what happens when the receiver comes first what happens when the receiver comes first and it finds an empty Channel well we conceptually know what happens here this time the receiver's execution is paused and it'll be resumed after a send how do how does that happen well we now know how to do that as well this time G2 creates the pseudo G and sets up the state for resumption and then calls into the scheduler um so it's paused um and at the end of that sequence of operations this is what the channel looks like this time we have an empty buffer and a waiting receiver the rating receiver is G2 and it's waiting to receive to that to that variable T and uh now the sender comes along and the sender sends uh task what might happen here well just reasoning through it what could happen is G1 could put the task in the buffer and then it call into the scheduler to resume G2 or we can be smarter the key Insight here is we know the memory location waiting for the receive so we could just have the sender send there directly we could just have G1 write to T directly seems reasonable but this is incredible this is incredible because gtin have their own Stacks they they have separate Stacks they typically don't overlap and AG gortin never reads to or writes um writes to or reads from another gurtin stack never except in the case of these Channel operations now the reason to do this again is it's a performance optimization again here by doing this when G2 uh when G1 finally runs um it doesn't have to mess with the channel it doesn't have to acquire the lock in this case there's also a fewer memory copy right instead of the sender writing into the buffer and then the receiver copying out of the buffer into T we have the sender copy directly to the receiver's stack this is this is actually very cool um so at this point we finally fully sort of understand how channels operate end to end um the mut the buffer the pseudo gqs the calls into the runtime scheduler this cross G routine stack manipulation those make up the secret sauce um that's the big reveal of the magic trick now at this point we can talk about how these Core Concepts apply to other channel operations what happens in the case of unbuffered channels or selects um hint that it's pretty much what you expect them to be but in the interest of time I'm not going to do that go is written in go and it's open source actually it's all like very clean and very good go and you now have the fundamental knowledge needed to go and look at the source code of channels so if you're interested I highly encourage it it's pretty fun what I'd like to do now instead is uh take a step back from the how and ask why why are channels implemented the way they are and two themes emerge from the implementation Simplicity and performance a simple cue with a lock is preferred to a more involved implementation like a lock free implementation the latter may be more performant but not enough to justify the increase in implementation and code complexity on the other hand things like calling into the runtime scheduler and the cross go routine stack manipulation those are motivated by performance by performance gains but they come at a cost right the the cost is in a complexity of implementation the implementation now has to carefully account for things uh for memory management things like garbage collection and stack shrinking but in this case the the performance wins are persuasive enough to just ify performance over Simplicity and so in the implementation of channels we see these astute tradeoffs between performance and simplicity and maybe there's a lesson there for all of us and the systems we build that is all thank you all for coming out today I hope you leave with um with an understanding of how your favorite or my favorite at least synchronization PR itive works and um and an appreciation for the sophisticated Machinery behind the deceptively simple API uh of channels thank you