Concurrency in Go Tools and Techniques for Developers (Katherine Cox-Buday) (z-library.sk, 1lib.sk, z-lib.sk)

📄 File Format: PDF

💾 File Size: 4.3 MB

📖 Read Online ⬇️ Download

Registered users can read the full content for free

Register as a Gaohf Library member to read the complete e-book online for free and enjoy a better reading experience.

📄 Page 1

Katherine Cox-Buday Concurrency in Go TOOLS & TECHNIQUES FOR DEVELOPERS

📄 Page 2

(This page has no text content)

📄 Page 3

Katherine Cox-Buday Concurrency in Go Tools and Techniques for Developers Boston Farnham Sebastopol TokyoBeijing

📄 Page 4

978-1-491-94119-5 [LSI] Concurrency in Go by Katherine Cox-Buday Copyright © 2017 Katherine Cox-Buday. All rights reserved. Printed in the United States of America. Published by O’Reilly Media, Inc., 1005 Gravenstein Highway North, Sebastopol, CA 95472. O’Reilly books may be purchased for educational, business, or sales promotional use. Online editions are also available for most titles (http://oreilly.com/safari). For more information, contact our corporate/insti‐ tutional sales department: 800-998-9938 or corporate@oreilly.com. Editor: Dawn Schanafelt Production Editor: Nicholas Adams Copyeditor: Kim Cofer Proofreader: Sonia Saruba Indexer: Judy McConville Interior Designer: David Futato Cover Designer: Karen Montgomery Illustrator: Rebecca Demarest August 2017: First Edition Revision History for the First Edition 2017-07-18: First Release See http://oreilly.com/catalog/errata.csp?isbn=9781491941195 for release details. The O’Reilly logo is a registered trademark of O’Reilly Media, Inc. Concurrency in Go, the cover image, and related trade dress are trademarks of O’Reilly Media, Inc. While the publisher and the author have used good faith efforts to ensure that the information and instructions contained in this work are accurate, the publisher and the author disclaim all responsibility for errors or omissions, including without limitation responsibility for damages resulting from the use of or reliance on this work. Use of the information and instructions contained in this work is at your own risk. If any code samples or other technology this work contains or describes is subject to open source licenses or the intellectual property rights of others, it is your responsibility to ensure that your use thereof complies with such licenses and/or rights.

📄 Page 5

For L. and N. whose sacrifice made this book possible. Of everything in my life, you are the best. I love you.

📄 Page 6

(This page has no text content)

📄 Page 7

Table of Contents Preface. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii 1. An Introduction to Concurrency. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Moore’s Law, Web Scale, and the Mess We’re In 2 Why Is Concurrency Hard? 4 Race Conditions 4 Atomicity 6 Memory Access Synchronization 8 Deadlocks, Livelocks, and Starvation 10 Determining Concurrency Safety 18 Simplicity in the Face of Complexity 20 2. Modeling Your Code: Communicating Sequential Processes. . . . . . . . . . . . . . . . . . . . . . . 23 The Difference Between Concurrency and Parallelism 23 What Is CSP? 26 How This Helps You 29 Go’s Philosophy on Concurrency 31 3. Go’s Concurrency Building Blocks. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 Goroutines 37 The sync Package 47 WaitGroup 47 Mutex and RWMutex 49 Cond 52 Once 57 Pool 59 Channels 64 The select Statement 78 v

📄 Page 8

The GOMAXPROCS Lever 83 Conclusion 83 4. Concurrency Patterns in Go. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 Confinement 85 The for-select Loop 89 Preventing Goroutine Leaks 90 The or-channel 94 Error Handling 97 Pipelines 100 Best Practices for Constructing Pipelines 104 Some Handy Generators 109 Fan-Out, Fan-In 114 The or-done-channel 119 The tee-channel 120 The bridge-channel 122 Queuing 124 The context Package 131 Summary 145 5. Concurrency at Scale. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 Error Propagation 147 Timeouts and Cancellation 155 Heartbeats 161 Replicated Requests 172 Rate Limiting 174 Healing Unhealthy Goroutines 188 Summary 194 6. Goroutines and the Go Runtime. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197 Work Stealing 197 Stealing Tasks or Continuations? 204 Presenting All of This to the Developer 212 Conclusion 212 A. Appendix. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213 Index. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219 vi | Table of Contents

📄 Page 9

Preface Hey, welcome to Concurrency in Go! I’m delighted that you’ve picked up this book and excited to join you in exploring the topic of concurrency in Go over the next six chapters! Go is a wonderful language. When it was first announced and birthed into the world, I remember exploring it with great interest: it was terse, compiled incredibly fast, per‐ formed well, supported duck typing, and—to my delight—I found working with its concurrency primitives to be intuitive. The first time I used the go keyword to create a goroutine (something we’ll cover, I promise!) I got this silly grin on my face. I had worked with concurrency in several languages, but I had never worked in a language that made concurrency so easy (which is not to say they don’t exist; I just hadn’t used any). I had found my way to Go. Over the years I moved from writing personal scripts in Go, to personal projects, until I found myself working on a many-hundreds-of-thousands-of-lines project pro‐ fessionally. Along the way the community was growing with the language, and we were collectively discovering best practices for working with concurrency in Go. A few people gave talks on patterns they had discovered. But there still weren’t many comprehensive guides on how to wield concurrency in Go in the community. It was with this in mind that I set out to write this book. I wanted the community to have access to high-quality and comprehensive information about concurrency in Go: how to use it, best practices and patterns for incorporating it into your systems, and how it all works under the covers. I have done my best to strike a balance between these concerns. I hope this book proves useful! vii

📄 Page 10

Who Should Read This Book This book is meant for developers who have some experience with Go; I make no attempt to explain the basic syntax of the language. Knowledge of how concurrency is presented in other languages is useful, but not necessary. By the end of this book we will have discussed the entire stack of Go concurrency concerns: common concurrency pitfalls, motivation behind the design of Go’s con‐ currency, the basic syntax of Go’s concurrency primitives, common concurrency pat‐ terns, patterns of patterns, and various tooling that will help you along the way. Because of the breadth of topics we’ll cover, this book will be useful to various cross- sections of people. The next section will help you navigate this book depending on what needs you have. Navigating This Book When I read technical books, I usually hop around to the areas that pique my inter‐ est. Or, if I’m trying to ramp up on a new technology for work, I frantically skim for the bits that are immediately relevant to my work. Whatever your use case is, here’s a roadmap for the book with the hopes that it help guide you to where you need to be! Chapter 1, An Introduction to Concurrency This chapter will give you a broad historical perspective on why concurrency is an important concept, and also discuss some of the fundamental problems that make concurrency difficult to get correct. It also briefly touches on how Go helps ease some of this burden. If you have a working knowledge of concurrency or just want to get to the tech‐ nical aspects of how to use Go’s concurrency primitives, it’s safe to skip this chapter. Chapter 2, Modeling Your Code: Communicating Sequential Processes This chapter deals with some of the motivational factors that contributed to Go’s design. This will help give you some context for conversations with others in the Go community and help to frame your understanding of why things work the way they do in the language. Chapter 3, Go’s Concurrency Building Blocks Here we’ll start to dig into the syntax of Go’s concurrency primitives. We’ll also cover the sync package, which is responsible for handling Go’s memory access synchronization. If you haven’t used concurrency within Go before and are look‐ ing to hop right in, this is the place to start. viii | Preface

📄 Page 11

Interspersed with the basics of writing concurrent code in Go are comparisons of concepts to other languages and concurrency models. Strictly speaking, it’s not necessary to understand these things, but these concepts help you to achieve a complete understanding on concurrency in Go. Chapter 4, Concurrency Patterns in Go In this chapter, we begin to look at how Go’s concurrency primitives are com‐ posed together to form useful patterns. These patterns will both help us solve problems and avoid issues that can come up when combining concurrency prim‐ itives. If you’ve already been writing some concurrent code in Go, this chapter should still prove useful. Chapter 5, Concurrency at Scale In this chapter, we take the patterns we have learned and compose these into larger patterns commonly employed in larger programs, services, and distributed systems. Chapter 6, Goroutines and the Go Runtime This chapter describes how the Go runtime handles scheduling goroutines. This is for those of you who want to understand the internals of Go’s runtime. Appendix The appendix simply enumerates various tools and commands that can help make writing and debugging concurrent programs easier. Online Resources Go has a very active and passionate community! For those newer to Go, take heart, it will be easy to find friendly, helpful people to guide you along on your path to Go. Here are a few of my favorite community-oriented resources for reading, getting help, and interacting with your fellow gophers: • https://golang.org/ • https://golang.org/play • https://go.googlesource.com/go • https://groups.google.com/group/golang-nuts • https://github.com/golang/go/wiki Preface | ix

📄 Page 12

Conventions Used in This Book The following typographical conventions are used in this book: Italic Indicates new terms, URLs, email addresses, filenames, and file extensions. Constant width Used for program listings, as well as within paragraphs to refer to program ele‐ ments such as variable or function names, databases, data types, environment variables, statements, and keywords. Constant width bold Shows commands or other text that should be typed literally by the user. Constant width italic Shows text that should be replaced with user-supplied values or by values deter‐ mined by context. This icon signifies a tip, suggestion, or general note. This icon indicates a warning or caution. Using Code Examples All of the code contained in this book can be found on the landing page for the book, http://katherine.cox-buday.com/concurrency-in-go. It is released under the MIT license and may be used under those terms. O’Reilly Safari Safari (formerly Safari Books Online) is a membership-based training and reference platform for enterprise, government, educators, and individuals. x | Preface

📄 Page 13

Members have access to thousands of books, training videos, Learning Paths, interac‐ tive tutorials, and curated playlists from over 250 publishers, including O’Reilly Media, Harvard Business Review, Prentice Hall Professional, Addison-Wesley Profes‐ sional, Microsoft Press, Sams, Que, Peachpit Press, Adobe, Focal Press, Cisco Press, John Wiley & Sons, Syngress, Morgan Kaufmann, IBM Redbooks, Packt, Adobe Press, FT Press, Apress, Manning, New Riders, McGraw-Hill, Jones & Bartlett, and Course Technology, among others. For more information, please visit http://oreilly.com/safari. How to Contact Us Please address comments and questions concerning this book to the publisher: O’Reilly Media, Inc. 1005 Gravenstein Highway North Sebastopol, CA 95472 800-998-9938 (in the United States or Canada) 707-829-0515 (international or local) 707-829-0104 (fax) We have a web page for this book, where we list errata, examples, and any additional information. You can access this page at http://bit.ly/concurrency-in-go. To comment or ask technical questions about this book, send email to bookques‐ tions@oreilly.com. For more information about our books, courses, conferences, and news, see our web‐ site at http://www.oreilly.com. Find us on Facebook: http://facebook.com/oreilly Follow us on Twitter: http://twitter.com/oreillymedia Watch us on YouTube: http://www.youtube.com/oreillymedia Acknowledgments Writing a book is a daunting and challenging task. What you have before you would not have been possible without a team of people supporting me, reviewing things, writing tools, and answering questions. I am deeply grateful to everyone who helped, and they have my sincerest thanks. We did this together! One swallow does not a summer make... —Proverb Preface | xi

📄 Page 14

• Alan Donovan, who helped with the original proposal and also helped set me on my way. • Andrew Wilkins, who I had the great fortune of working with at Canonical. His insight, professionalism, and intelligence influenced this book, and his reviews made it better. • Ara Pulido, who helped me see this book through a new gopher’s eyes. • Dawn Schanafelt, my editor, who played a large part in making this book read as clearly as possible. I especially appreciate her (and O’Reilly’s) patience while life placed a few difficulties on my path while writing this book. • Francesc Campoy, who helped ensure I always kept newer gophers in mind. • Ivan Daniluk, whose attention to detail and interest in concurrency helped ensure this is a comprehensive and useful book. • Yasushi Shoji, who wrote org-asciidoc, a tool that I used to export AsciiDoc artifacts from Org mode. He didn’t know he was helping to write a book, but he was always very responsive to bug reports and questions! • The maintainers of Go: thank you for your dedication. • The maintainers of Org mode, the GNU Emacs mode with which this book is written. My entire life is in org; seriously, thanks all. • The maintainers of GNU Emacs, the text editor I wrote this book in. I cannot think of a tool that has served as more of a lever in my life. • The St. Louis public libraries where most of this book was written. xii | Preface

📄 Page 15

CHAPTER 1 An Introduction to Concurrency Concurrency is an interesting word because it means different things to different peo‐ ple in our field. In addition to “concurrency,” you may have heard the words, “asyn‐ chronous,” “parallel,” or “threaded” bandied about. Some people take these words to mean the same thing, and other people very specifically delineate between each of those words. If we’re to spend an entire book’s worth of time discussing concurrency, it would be beneficial to first spend some time discussing what we mean when we say “concurrency.” We’ll spend some time on the philosophy of concurrency in Chapter 2, but for now let’s adopt a practical definition that will serve as the foundation of our understand‐ ing. When most people use the word “concurrent,” they’re usually referring to a process that occurs simultaneously with one or more processes. It is also usually implied that all of these processes are making progress at about the same time. Under this defini‐ tion, an easy way to think about this are people. You are currently reading this sen‐ tence while others in the world are simultaneously living their lives. They are existing concurrently to you. Concurrency is a broad topic in computer science, and from this definition spring all kinds of topics: theory, approaches to modeling concurrency, correctness of logic, practical issues—even theoretical physics! We’ll touch on some of the ancillary topics throughout the book, but we’ll mostly stick to the practical issues that involve under‐ standing concurrency within the context of Go, specifically: how Go chooses to model concurrency, what issues arise from this model, and how we can compose primitives within this model to solve problems. In this chapter, we’ll take a broad look at some of the reasons concurrency became such an important topic in computer science, why concurrency is difficult and war‐ 1

📄 Page 16

rants careful study, and—most importantly—the idea that despite these challenges, Go can make programs clearer and faster by using its concurrency primitives. As with most paths toward understanding, we’ll begin with a bit of history. Let’s first take a look at how concurrency became such an important topic. Moore’s Law, Web Scale, and the Mess We’re In In 1965, Gordon Moore wrote a three-page paper that described both the consolida‐ tion of the electronics market toward integrated circuits, and the doubling of the number of components in an integrated circuit every year for at least a decade. In 1975, he revised this prediction to state that the number of components on an inte‐ grated circuit would double every two years. This prediction more or less held true until just recently—around 2012. Several companies foresaw this slowdown in the rate Moore’s law predicted and began to investigate alternative ways to increase computing power. As the saying goes, necessity is the mother of innovation, and so it was in this way that multicore processors were born. This looked like a clever way to solve the bounding problems of Moore’s law, but computer scientists soon found themselves facing down the limits of another law: Amdahl’s law, named after computer architect Gene Amdahl. Amdahl’s law describes a way in which to model the potential performance gains from implementing the solution to a problem in a parallel manner. Simply put, it states that the gains are bounded by how much of the program must be written in a sequential manner. For example, imagine you were writing a program that was largely GUI based: a user is presented with an interface, clicks on some buttons, and stuff happens. This type of program is bounded by one very large sequential portion of the pipeline: human interaction. No matter how many cores you make available to this program, it will always be bounded by how quickly the user can interact with the interface. Now consider a different example, calculating digits of pi. Thanks to a class of algo‐ rithms called spigot algorithms, this problem is called embarrassingly parallel, which —despite sounding made up—is a technical term which means that it can easily be divided into parallel tasks. In this case, significant gains can be made by making more cores available to your program, and your new problem becomes how to combine and store the results. Amdahl’s law helps us understand the difference between these two problems, and can help us decide whether parallelization is the right way to address performance concerns in our system. 2 | Chapter 1: An Introduction to Concurrency

📄 Page 17

For problems that are embarrassingly parallel, it is recommended that you write your application so that it can scale horizontally. This means that you can take instances of your program, run it on more CPUs, or machines, and this will cause the runtime of the system to improve. Embarrassingly parallel problems fit this model so well because it’s very easy to structure your program in such a way that you can send chunks of a problem to different instances of your application. Scaling horizontally became much easier in the early 2000s when a new paradigm began to take hold: cloud computing. Although there are indications that the phrase had been used as early as the 1970s, the early 2000s are when the idea really took root in the zeitgeist. Cloud computing implied a new kind of scale and approach to appli‐ cation deployments and horizontal scaling. Instead of machines that you carefully curated, installed software on, and maintained, cloud computing implied access to vast pools of resources that were provisioned into machines for workloads on- demand. Machines became something that were almost ephemeral, and provisioned with characteristics specifically suited to the programs they would run. Usually (but not always) these resource pools were hosted in data centers owned by other compa‐ nies. This change encouraged a new kind of thinking. Suddenly, developers had relatively cheap access to vast amounts of computing power that they could use to solve large problems. Solutions could now trivially span many machines and even global regions. Cloud computing made possible a whole new set of solutions to problems that were previously only solvable by tech giants. But cloud computing also presented many new challenges. Provisioning these resour‐ ces, communicating between machine instances, and aggregating and storing the results all became problems to solve. But among the most difficult was figuring out how to model code concurrently. The fact that pieces of your solution could be run‐ ning on disparate machines exacerbated some of the issues commonly faced when modeling a problem concurrently. Successfully solving these issues soon led to a new type of brand for software, web scale. If software was web scale, among other things, you could expect that it would be embarrassingly parallel; that is, web scale software is usually expected to be able to handle hundreds of thousands (or more) of simultaneous workloads by adding more instances of the application. This enabled all kinds of properties like rolling upgrades, elastic horizontally scalable architecture, and geographic distribution. It also intro‐ duced new levels of complexity both in comprehension and fault tolerance. And so it is in this world of multiple cores, cloud computing, web scale, and problems that may or may not be parallelizable that we find the modern developer, maybe a bit overwhelmed. The proverbial buck has been passed to us, and we are expected to rise to the challenge of solving problems within the confines of the hardware we’ve been handed. In 2005, Herb Sutter authored an article for Dr. Dobb’s, titled, “The free lunch Moore’s Law, Web Scale, and the Mess We’re In | 3

📄 Page 18

is over: A fundamental turn toward concurrency in software”. The title is apt, and the article prescient. Toward the end, Sutter states, “We desperately need a higher-level programming model for concurrency than languages offer today.” To know why Sutter used such strong language, we have to look at why concurrency is so hard to get right. Why Is Concurrency Hard? Concurrent code is notoriously difficult to get right. It usually takes a few iterations to get it working as expected, and even then it’s not uncommon for bugs to exist in code for years before some change in timing (heavier disk utilization, more users logged into the system, etc.) causes a previously undiscovered bug to rear its head. Indeed, for this very book, I’ve gotten as many eyes as possbile on the code to try and mitigate this. Fortunately everyone runs into the same issues when working with concurrent code. Because of this, computer scientists have been able to label the common issues, which allows us to discuss how they arise, why, and how to solve them. So let’s get started. Following are some of the most common issues that make working with concurrent code both frustrating and interesting. Race Conditions A race condition occurs when two or more operations must execute in the correct order, but the program has not been written so that this order is guaranteed to be maintained. Most of the time, this shows up in what’s called a data race, where one concurrent operation attempts to read a variable while at some undetermined time another con‐ current operation is attempting to write to the same variable. Here’s a basic example: 1 var data int 2 go func() { 3 data++ 4 }() 5 if data == 0 { 6 fmt.Printf("the value is %v.\n", data) 7 } In Go, you can use the go keyword to run a function concurrently. Doing so cre‐ ates what’s called a goroutine. We’ll discuss this in detail in the section, “Gorou‐ tines” on page 37. 4 | Chapter 1: An Introduction to Concurrency

📄 Page 19

Here, lines 3 and 5 are both trying to access the variable data, but there is no guaran‐ tee what order this might happen in. There are three possible outcomes to running this code: • Nothing is printed. In this case, line 3 was executed before line 5. • “the value is 0” is printed. In this case, lines 5 and 6 were executed before line 3. • “the value is 1” is printed. In this case, line 5 was executed before line 3, but line 3 was executed before line 6. As you can see, just a few lines of incorrect code can introduce tremendous variability into your program. Most of the time, data races are introduced because the developers are thinking about the problem sequentially. They assume that because a line of code falls before another that it will run first. They assume the goroutine above will be scheduled and execute before the data variable is read in the if statement. When writing concurrent code, you have to meticulously iterate through the possible scenarios. Unless you’re utilizing some of the techniques we’ll cover later in the book, you have no guarantees that your code will run in the order it’s listed in the source‐ code. I sometimes find it helpful to imagine a large period of time passing between operations. Imagine an hour passes between the time when the goroutine is invoked, and when it is run. How would the rest of the program behave? What if it took an hour between the goroutine executing successfully and the program reaching the if statement? Thinking in this manner helps me because to a computer, the scale may be different, but the relative time differentials are more or less the same. Indeed, some developers fall into the trap of sprinkling sleeps throughout their code exactly because it seems to solve their concurrency problems. Let’s try that in the pre‐ ceding program: 1 var data int 2 go func() { data++ }() 3 time.Sleep(1*time.Second) // This is bad! 4 if data == 0 { 5 fmt.Printf("the value is %v.\n" data) 6 } Have we solved our data race? No. In fact, it’s still possible for all three outcomes to arise from this program, just increasingly unlikely. The longer we sleep in between invoking our goroutine and checking the value of data, the closer our program gets to achieving correctness—but this probability asymptotically approaches logical correct‐ ness; it will never be logically correct. In addition to this, we’ve now introduced an inefficiency into our algorithm. We now have to sleep for one second to make it more likely we won’t see our data race. If we Why Is Concurrency Hard? | 5

📄 Page 20

utilized the correct tools, we might not have to wait at all, or the wait could be only a microsecond. The takeaway here is that you should always target logical correctness. Introducing sleeps into your code can be a handy way to debug concurrent programs, but they are not a solution. Race conditions are one of the most insidious types of concurrency bugs because they may not show up until years after the code has been placed into production. They are usually precipitated by a change in the environment the code is executing in, or an unprecedented occurrence. In these cases, the code seems to be behaving correctly, but in reality, there’s just a very high chance that the operations will be executed in order. Sooner or later, the program will have an unintended consequence. Atomicity When something is considered atomic, or to have the property of atomicity, this means that within the context that it is operating, it is indivisible, or uninterruptible. So what does that really mean, and why is this important to know when working with concurrent code? The first thing that’s very important is the word “context.” Something may be atomic in one context, but not another. Operations that are atomic within the context of your process may not be atomic in the context of the operating system; operations that are atomic within the context of the operating system may not be atomic within the con‐ text of your machine; and operations that are atomic within the context of your machine may not be atomic within the context of your application. In other words, the atomicity of an operation can change depending on the currently defined scope. This fact can work both for and against you! When thinking about atomicity, very often the first thing you need to do is to define the context, or scope, the operation will be considered to be atomic in. Everything follows from this. Fun Fact In 2006, the gaming company Blizzard successfully sued MDY Industries for $6,000,000 USD for making a program called “Glider,” which would automatically play their game, World of Warcraft, without user intervention. These types of pro‐ grams are commonly referred to as “bots” (short for robots). At the time, World of Warcraft had an anti-cheating program called “Warden,” which would run anytime you played the game. Among other things, Warden would scan the memory of the host machine and run a heuristic to look for programs that appeared to be used for cheating. 6 | Chapter 1: An Introduction to Concurrency