_content/talks/2012/concurrency.slide - website - Git at Google

 Go Concurrency Patterns

 Rob Pike
 Google
 http://golang.org/s/plusrob
 @rob_pike
 http://golang.org

 * Video

 This talk was presented at Google I/O in June 2012.

 .link http://www.youtube.com/watch?v=f6kdp27TYZs Watch the talk on YouTube

 * Introduction

 * Concurrency features in Go

 People seemed fascinated by the concurrency features of Go when the language was first announced.

 Questions:

 - Why is concurrency supported?
 - What is concurrency, anyway?
 - Where does the idea come from?
 - What is it good for?
 - How do I use it?

 * Why?

 Look around you. What do you see?

 Do you see a single-stepping world doing one thing at a time?

 Or do you see a complex world of interacting, independently behaving pieces?

 That's why. Sequential processing on its own does not model the world's behavior.

 * What is concurrency?

 Concurrency is the composition of independently executing computations.

 Concurrency is a way to structure software, particularly as a way to write clean code that interacts well with the real world.

 It is not parallelism.

 * Concurrency is not parallelism

 Concurrency is not parallelism, although it enables parallelism.

 If you have only one processor, your program can still be concurrent  but it cannot be parallel.

 On the other hand, a well-written concurrent program might run efficiently in parallel on a multiprocessor. That property could be important...

 For more on that distinction, see the link below. Too much to discuss here.

 .link http://golang.org/s/concurrency-is-not-parallelism

 * A model for software construction

 Easy to understand.

 Easy to use.

 Easy to reason about.

 You don't need to be an expert!

 (Much nicer than dealing with the minutiae of parallelism (threads, semaphores, locks, barriers, etc.))

 * History

 To many, the concurrency features of Go seemed new.

 But they are rooted in a long history, reaching back to Hoare's CSP in 1978 and even Dijkstra's guarded commands (1975).

 Languages with similar features:

 - Occam (May, 1983)
 - Erlang (Armstrong, 1986)
 - Newsqueak (Pike, 1988)
 - Concurrent ML (Reppy, 1993)
 - Alef (Winterbottom, 1995)
 - Limbo (Dorward, Pike, Winterbottom, 1996).

 * Distinction

 Go is the latest on the Newsqueak-Alef-Limbo branch, distinguished by first-class channels.

 Erlang is closer to the original CSP, where you communicate to a process by name rather than over a channel.

 The models are equivalent but express things differently.

 Rough analogy: writing to a file by name (process, Erlang) vs. writing to a file descriptor (channel, Go).

 * Basic Examples

 * A boring function

 We need an example to show the interesting properties of the concurrency primitives.

 To avoid distraction, we make it a boring example.

 .play concurrency/support/boring.go /START/,/STOP.*/

 * Slightly less boring

 Make the intervals between messages unpredictable (still under a second).

 .play concurrency/support/lessboring.go /START/,/STOP/

 * Running it

 The boring function runs on forever, like a boring party guest.

 .play concurrency/support/lessboring.go /^func.main/,$

 * Ignoring it

 The go statement runs the function as usual, but doesn't make the caller wait.

 It launches a goroutine.

 The functionality is analogous to the & on the end of a shell command.

 .play concurrency/support/goboring.go 1,/^}/

 * Ignoring it a little less

 When main returns, the program exits and takes the boring function down with it.

 We can hang around a little, and on the way show that both main and the launched goroutine are running.

 .play concurrency/support/waitgoboring.go /func.main/,/^}/

 * Goroutines

 What is a goroutine? It's an independently executing function, launched by a go statement.

 It has its own call stack, which grows and shrinks as required.

 It's very cheap. It's practical to have thousands, even hundreds of thousands of goroutines.

 It's not a thread.

 There might be only one thread in a program with thousands of goroutines.

 Instead, goroutines are multiplexed dynamically onto threads as needed to keep all the goroutines running.

 But if you think of it as a very cheap thread, you won't be far off.

 * Communication

 Our boring examples cheated: the main function couldn't see the output from the other goroutine.

 It was just printed to the screen, where we pretended we saw a conversation.

 Real conversations require communication.

 * Channels

 A channel in Go provides a connection between two goroutines, allowing them to communicate.

 .code concurrency/support/helpers.go /START1/,/STOP1/
 .code concurrency/support/helpers.go /START2/,/STOP2/
 .code concurrency/support/helpers.go /START3/,/STOP3/

 * Using channels

 A channel connects the main and boring goroutines so they can communicate.

 .play concurrency/support/changoboring.go /START1/,/STOP1/
 .code concurrency/support/changoboring.go /START2/,/STOP2/

 * Synchronization

 When the main function executes <–c, it will wait for a value to be sent.

 Similarly, when the boring function executes c <– value, it waits for a receiver to be ready.

 A sender and receiver must both be ready to play their part in the communication. Otherwise we wait until they are.

 Thus channels both communicate and synchronize.

 * An aside about buffered channels

 Note for experts: Go channels can also be created with a buffer.

 Buffering removes synchronization.

 Buffering makes them more like Erlang's mailboxes.

 Buffered channels can be important for some problems but they are more subtle to reason about.

 We won't need them today.

 * The Go approach

 Don't communicate by sharing memory, share memory by communicating.

 * "Patterns"

 * Generator: function that returns a channel

 Channels are first-class values, just like strings or integers.

 .play concurrency/support/generatorboring.go /START1/,/STOP1/
 .code concurrency/support/generatorboring.go /START2/,/STOP2/

 * Channels as a handle on a service

 Our boring function returns a channel that lets us communicate with the boring service it provides.

 We can have more instances of the service.

 .play concurrency/support/generator2boring.go /START1/,/STOP1/

 * Multiplexing

 These programs make Joe and Ann count in lockstep.
 We can instead use a fan-in function to let whosoever is ready talk.

 .code concurrency/support/faninboring.go /START3/,/STOP3/
 .play concurrency/support/faninboring.go /START1/,/STOP1/

 * Fan-in

 .image concurrency/images/gophermegaphones.jpg

 * Restoring sequencing

 Send a channel on a channel, making goroutine wait its turn.

 Receive all messages, then enable them again by sending on a private channel.

 First we define a message type that contains a channel for the reply.

 .code concurrency/support/sequenceboring.go /START0/,/STOP0/

 * Restoring sequencing.

 Each speaker must wait for a go-ahead.

 .code concurrency/support/sequenceboring.go /START1/,/STOP1/
 .code concurrency/support/sequenceboring.go /START2/,/STOP2/
 .play concurrency/support/sequenceboring.go /START3/,/STOP3/

 * Select

 A control structure unique to concurrency.

 The reason channels and goroutines are built into the language.

 * Select

 The select statement provides another way to handle multiple channels.
 It's like a switch, but each case is a communication:
 - All channels are evaluated.
 - Selection blocks until one communication can proceed, which then does.
 - If multiple can proceed, select chooses pseudo-randomly.
 - A default clause, if present, executes immediately if no channel is ready.

 .code concurrency/support/select.go /START0/,/STOP0/

 * Fan-in again

 Rewrite our original fanIn function. Only one goroutine is needed. Old:

 .code concurrency/support/faninboring.go /START3/,/STOP3/

 * Fan-in using select

 Rewrite our original fanIn function. Only one goroutine is needed. New:

 .play concurrency/support/selectboring.go /START3/,/STOP3/

 * Timeout using select

 The time.After function returns a channel that blocks for the specified duration.
 After the interval, the channel delivers the current time, once.

 .play concurrency/support/timeout.go /START1/,/STOP1/

 * Timeout for whole conversation using select

 Create the timer once, outside the loop, to time out the entire conversation.
 (In the previous program, we had a timeout for each message.)

 .play concurrency/support/timeoutall.go /START1/,/STOP1/


 * Quit channel

 We can turn this around and tell Joe to stop when we're tired of listening to him.

 .code concurrency/support/quit.go /START1/,/STOP1/
 .play concurrency/support/quit.go /START2/,/STOP2/


 * Receive on quit channel

 How do we know it's finished? Wait for it to tell us it's done: receive on the quit channel

 .code concurrency/support/rcvquit.go /START1/,/STOP1/
 .play concurrency/support/rcvquit.go /START2/,/STOP2/

 * Daisy-chain

 .play concurrency/support/daisy.go /func/,$

 * Chinese whispers, gopher style

 .image concurrency/images/gophereartrumpet.jpg

 * Systems software

 Go was designed for writing systems software.
 Let's see how the concurrency features come into play.

 * Example: Google Search

 Q: What does Google search do?

 A: Given a query, return a page of search results (and some ads).

 Q: How do we get the search results?

 A: Send the query to Web search, Image search, YouTube, Maps, News,etc., then mix the results.

 How do we implement this?

 * Google Search: A fake framework

 We can simulate the search function, much as we simulated conversation before.

 .code concurrency/support/google.go /START2/,/STOP2/

 * Google Search: Test the framework

 .play concurrency/support/google.go /func.main/,/}/

 * Google Search 1.0

 The Google function takes a query and returns a slice of Results (which are just strings).

 Google invokes Web, Image, and Video searches serially, appending them to the results slice.

 .play concurrency/support/google.go /START1/,/STOP1/

 * Google Search 2.0

 Run the Web, Image, and Video searches concurrently, and wait for all results.

 No locks.  No condition variables.  No callbacks.

 .play concurrency/support/google2.1.go /Google/,/^}/

 * Google Search 2.1

 Don't wait for slow servers. No locks.  No condition variables.  No callbacks.

 .play concurrency/support/google2.2.go /START/,/STOP/

 * Avoid timeout

 Q: How do we avoid discarding results from slow servers?

 A: Replicate the servers.  Send requests to multiple replicas, and use the first response.

 .code concurrency/support/google2.3.go /START1/,/STOP1/

 * Using the First function

 .play concurrency/support/google2.3.go /START2/,/STOP2/

 * Google Search 3.0

 Reduce tail latency using replicated search servers.

 .play concurrency/support/google3.0.go /START/,/STOP/

 * And still…

 No locks.  No condition variables.  No callbacks.

 * Summary

 In just a few simple transformations we used Go's concurrency primitives to convert a

 - slow
 - sequential
 - failure-sensitive

 program into one that is

 - fast
 - concurrent
 - replicated
 - robust.

 * More party tricks

 There are endless ways to use these tools, many presented elsewhere.

 Chatroulette toy:

 .link http://golang.org/s/chat-roulette

 Load balancer:

 .link http://golang.org/s/load-balancer

 Concurrent prime sieve:

 .link http://golang.org/s/prime-sieve

 Concurrent power series (by McIlroy):

 .link http://golang.org/s/power-series

 * Don't overdo it

 They're fun to play with, but don't overuse these ideas.

 Goroutines and channels are big ideas. They're tools for program construction.

 But sometimes all you need is a reference counter.

 Go has "sync" and "sync/atomic" packages that provide mutexes, condition variables, etc. They provide tools for smaller problems.

 Often, these things will work together to solve a bigger problem.

 Always use the right tool for the job.

 * Conclusions

 Goroutines and channels make it easy to express complex operations dealing with

 - multiple inputs
 - multiple outputs
 - timeouts
 - failure

 And they're fun to use.


 * Links

 Go Home Page:

 .link http://golang.org

 Go Tour (learn Go in your browser)

 .link http://tour.golang.org

 Package documentation:

 .link http://golang.org/pkg

 Articles galore:

 .link http://golang.org/doc

 Concurrency is not parallelism:

 .link http://golang.org/s/concurrency-is-not-parallelism
	Go Concurrency Patterns

	Rob Pike
	Google
	http://golang.org/s/plusrob
	@rob_pike
	http://golang.org

	* Video

	This talk was presented at Google I/O in June 2012.

	.link http://www.youtube.com/watch?v=f6kdp27TYZs Watch the talk on YouTube

	* Introduction

	* Concurrency features in Go

	People seemed fascinated by the concurrency features of Go when the language was first announced.

	Questions:

	- Why is concurrency supported?
	- What is concurrency, anyway?
	- Where does the idea come from?
	- What is it good for?
	- How do I use it?

	* Why?

	Look around you. What do you see?

	Do you see a single-stepping world doing one thing at a time?

	Or do you see a complex world of interacting, independently behaving pieces?

	That's why. Sequential processing on its own does not model the world's behavior.

	* What is concurrency?

	Concurrency is the composition of independently executing computations.

	Concurrency is a way to structure software, particularly as a way to write clean code that interacts well with the real world.

	It is not parallelism.

	* Concurrency is not parallelism

	Concurrency is not parallelism, although it enables parallelism.

	If you have only one processor, your program can still be concurrent but it cannot be parallel.

	On the other hand, a well-written concurrent program might run efficiently in parallel on a multiprocessor. That property could be important...

	For more on that distinction, see the link below. Too much to discuss here.

	.link http://golang.org/s/concurrency-is-not-parallelism

	* A model for software construction

	Easy to understand.

	Easy to use.

	Easy to reason about.

	You don't need to be an expert!

	(Much nicer than dealing with the minutiae of parallelism (threads, semaphores, locks, barriers, etc.))

	* History

	To many, the concurrency features of Go seemed new.

	But they are rooted in a long history, reaching back to Hoare's CSP in 1978 and even Dijkstra's guarded commands (1975).

	Languages with similar features:

	- Occam (May, 1983)
	- Erlang (Armstrong, 1986)
	- Newsqueak (Pike, 1988)
	- Concurrent ML (Reppy, 1993)
	- Alef (Winterbottom, 1995)
	- Limbo (Dorward, Pike, Winterbottom, 1996).

	* Distinction

	Go is the latest on the Newsqueak-Alef-Limbo branch, distinguished by first-class channels.

	Erlang is closer to the original CSP, where you communicate to a process by name rather than over a channel.

	The models are equivalent but express things differently.

	Rough analogy: writing to a file by name (process, Erlang) vs. writing to a file descriptor (channel, Go).

	* Basic Examples

	* A boring function

	We need an example to show the interesting properties of the concurrency primitives.

	To avoid distraction, we make it a boring example.

	.play concurrency/support/boring.go /START/,/STOP.*/

	* Slightly less boring

	Make the intervals between messages unpredictable (still under a second).

	.play concurrency/support/lessboring.go /START/,/STOP/

	* Running it

	The boring function runs on forever, like a boring party guest.

	.play concurrency/support/lessboring.go /^func.main/,$

	* Ignoring it

	The go statement runs the function as usual, but doesn't make the caller wait.

	It launches a goroutine.

	The functionality is analogous to the & on the end of a shell command.

	.play concurrency/support/goboring.go 1,/^}/

	* Ignoring it a little less

	When main returns, the program exits and takes the boring function down with it.

	We can hang around a little, and on the way show that both main and the launched goroutine are running.

	.play concurrency/support/waitgoboring.go /func.main/,/^}/

	* Goroutines

	What is a goroutine? It's an independently executing function, launched by a go statement.

	It has its own call stack, which grows and shrinks as required.

	It's very cheap. It's practical to have thousands, even hundreds of thousands of goroutines.

	It's not a thread.

	There might be only one thread in a program with thousands of goroutines.

	Instead, goroutines are multiplexed dynamically onto threads as needed to keep all the goroutines running.

	But if you think of it as a very cheap thread, you won't be far off.

	* Communication

	Our boring examples cheated: the main function couldn't see the output from the other goroutine.

	It was just printed to the screen, where we pretended we saw a conversation.

	Real conversations require communication.

	* Channels

	A channel in Go provides a connection between two goroutines, allowing them to communicate.

	.code concurrency/support/helpers.go /START1/,/STOP1/
	.code concurrency/support/helpers.go /START2/,/STOP2/
	.code concurrency/support/helpers.go /START3/,/STOP3/

	* Using channels

	A channel connects the main and boring goroutines so they can communicate.

	.play concurrency/support/changoboring.go /START1/,/STOP1/
	.code concurrency/support/changoboring.go /START2/,/STOP2/

	* Synchronization

	When the main function executes <–c, it will wait for a value to be sent.

	Similarly, when the boring function executes c <– value, it waits for a receiver to be ready.

	A sender and receiver must both be ready to play their part in the communication. Otherwise we wait until they are.

	Thus channels both communicate and synchronize.

	* An aside about buffered channels

	Note for experts: Go channels can also be created with a buffer.

	Buffering removes synchronization.

	Buffering makes them more like Erlang's mailboxes.

	Buffered channels can be important for some problems but they are more subtle to reason about.

	We won't need them today.

	* The Go approach

	Don't communicate by sharing memory, share memory by communicating.

	* "Patterns"

	* Generator: function that returns a channel

	Channels are first-class values, just like strings or integers.

	.play concurrency/support/generatorboring.go /START1/,/STOP1/
	.code concurrency/support/generatorboring.go /START2/,/STOP2/

	* Channels as a handle on a service

	Our boring function returns a channel that lets us communicate with the boring service it provides.

	We can have more instances of the service.

	.play concurrency/support/generator2boring.go /START1/,/STOP1/

	* Multiplexing

	These programs make Joe and Ann count in lockstep.
	We can instead use a fan-in function to let whosoever is ready talk.

	.code concurrency/support/faninboring.go /START3/,/STOP3/
	.play concurrency/support/faninboring.go /START1/,/STOP1/

	* Fan-in

	.image concurrency/images/gophermegaphones.jpg

	* Restoring sequencing

	Send a channel on a channel, making goroutine wait its turn.

	Receive all messages, then enable them again by sending on a private channel.

	First we define a message type that contains a channel for the reply.

	.code concurrency/support/sequenceboring.go /START0/,/STOP0/

	* Restoring sequencing.

	Each speaker must wait for a go-ahead.

	.code concurrency/support/sequenceboring.go /START1/,/STOP1/
	.code concurrency/support/sequenceboring.go /START2/,/STOP2/
	.play concurrency/support/sequenceboring.go /START3/,/STOP3/

	* Select

	A control structure unique to concurrency.

	The reason channels and goroutines are built into the language.

	* Select

	The select statement provides another way to handle multiple channels.
	It's like a switch, but each case is a communication:
	- All channels are evaluated.
	- Selection blocks until one communication can proceed, which then does.
	- If multiple can proceed, select chooses pseudo-randomly.
	- A default clause, if present, executes immediately if no channel is ready.

	.code concurrency/support/select.go /START0/,/STOP0/

	* Fan-in again

	Rewrite our original fanIn function. Only one goroutine is needed. Old:

	.code concurrency/support/faninboring.go /START3/,/STOP3/

	* Fan-in using select

	Rewrite our original fanIn function. Only one goroutine is needed. New:

	.play concurrency/support/selectboring.go /START3/,/STOP3/

	* Timeout using select

	The time.After function returns a channel that blocks for the specified duration.
	After the interval, the channel delivers the current time, once.

	.play concurrency/support/timeout.go /START1/,/STOP1/

	* Timeout for whole conversation using select

	Create the timer once, outside the loop, to time out the entire conversation.
	(In the previous program, we had a timeout for each message.)

	.play concurrency/support/timeoutall.go /START1/,/STOP1/


	* Quit channel

	We can turn this around and tell Joe to stop when we're tired of listening to him.

	.code concurrency/support/quit.go /START1/,/STOP1/
	.play concurrency/support/quit.go /START2/,/STOP2/


	* Receive on quit channel

	How do we know it's finished? Wait for it to tell us it's done: receive on the quit channel

	.code concurrency/support/rcvquit.go /START1/,/STOP1/
	.play concurrency/support/rcvquit.go /START2/,/STOP2/

	* Daisy-chain

	.play concurrency/support/daisy.go /func/,$

	* Chinese whispers, gopher style

	.image concurrency/images/gophereartrumpet.jpg

	* Systems software

	Go was designed for writing systems software.
	Let's see how the concurrency features come into play.

	* Example: Google Search

	Q: What does Google search do?

	A: Given a query, return a page of search results (and some ads).

	Q: How do we get the search results?

	A: Send the query to Web search, Image search, YouTube, Maps, News,etc., then mix the results.

	How do we implement this?

	* Google Search: A fake framework

	We can simulate the search function, much as we simulated conversation before.

	.code concurrency/support/google.go /START2/,/STOP2/

	* Google Search: Test the framework

	.play concurrency/support/google.go /func.main/,/}/

	* Google Search 1.0

	The Google function takes a query and returns a slice of Results (which are just strings).

	Google invokes Web, Image, and Video searches serially, appending them to the results slice.

	.play concurrency/support/google.go /START1/,/STOP1/

	* Google Search 2.0

	Run the Web, Image, and Video searches concurrently, and wait for all results.

	No locks. No condition variables. No callbacks.

	.play concurrency/support/google2.1.go /Google/,/^}/

	* Google Search 2.1

	Don't wait for slow servers. No locks. No condition variables. No callbacks.

	.play concurrency/support/google2.2.go /START/,/STOP/

	* Avoid timeout

	Q: How do we avoid discarding results from slow servers?

	A: Replicate the servers. Send requests to multiple replicas, and use the first response.

	.code concurrency/support/google2.3.go /START1/,/STOP1/

	* Using the First function

	.play concurrency/support/google2.3.go /START2/,/STOP2/

	* Google Search 3.0

	Reduce tail latency using replicated search servers.

	.play concurrency/support/google3.0.go /START/,/STOP/

	* And still…

	No locks. No condition variables. No callbacks.

	* Summary

	In just a few simple transformations we used Go's concurrency primitives to convert a

	- slow
	- sequential
	- failure-sensitive

	program into one that is

	- fast
	- concurrent
	- replicated
	- robust.

	* More party tricks

	There are endless ways to use these tools, many presented elsewhere.

	Chatroulette toy:

	.link http://golang.org/s/chat-roulette

	Load balancer:

	.link http://golang.org/s/load-balancer

	Concurrent prime sieve:

	.link http://golang.org/s/prime-sieve

	Concurrent power series (by McIlroy):

	.link http://golang.org/s/power-series

	* Don't overdo it

	They're fun to play with, but don't overuse these ideas.

	Goroutines and channels are big ideas. They're tools for program construction.

	But sometimes all you need is a reference counter.

	Go has "sync" and "sync/atomic" packages that provide mutexes, condition variables, etc. They provide tools for smaller problems.

	Often, these things will work together to solve a bigger problem.

	Always use the right tool for the job.

	* Conclusions

	Goroutines and channels make it easy to express complex operations dealing with

	- multiple inputs
	- multiple outputs
	- timeouts
	- failure

	And they're fun to use.


	* Links

	Go Home Page:

	.link http://golang.org

	Go Tour (learn Go in your browser)

	.link http://tour.golang.org

	Package documentation:

	.link http://golang.org/pkg

	Articles galore:

	.link http://golang.org/doc

	Concurrency is not parallelism:

	.link http://golang.org/s/concurrency-is-not-parallelism