Concurrency in Go

Concurrency in Go involves two main synchronization mechanisms: Locks and Channels. This allows for limiting access to critical sections and passing information across processes using a queue. To ensure atomicity and avoid race conditions, it's crucial to handle critical sections properly with appropriate synchronization techniques. Go provides tools like mutex locks from the sync package to manage shared resources effectively.

• Concurrency
• Synchronization
• Locks
• Channels
• Golang

raaelde Follow

Uploaded on Feb 23, 2025 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

Presentation Transcript

1. Concurrency in Go 9/15/22

2. Go Resources https://tour.golang.org/list https://play.golang.org https://gobyexample.com 2

3. Todays Precept 1. Two synchronization mechanisms a. Locks b. Channels 2. Mapreduce 3

4. Two synchronization mechanisms Locks - limit access to a critical section Channels - pass information across processes using a queue 4

5. Example: Bank account Bank Account Alice Bob 100 Read b = 100 b = b + 10 Write b = 110 110 Read b = 110 b = b + 10 Write b = 120 120 5

6. Example: Bank account Bank Account Alice Bob 100 Read b = 100 b = b + 10 Read b = 100 Write b = 110 110 b = b + 10 Write b = 110 110 6

7. What went wrong? Changes to balance are not atomic func Deposit(amount) { lock balanceLock read balance balance = balance + amount write balance unlock balanceLock } 7

8. What went wrong? Changes to balance are not atomic func Deposit(amount) { lock balanceLock read balance balance = balance + amount write balance unlock balanceLock } Critical section 8

9. Locks in Go func (a *Account) CheckBalance() int { a.mu.Lock() defer a.mu.Unlock() return a.balance } package account import "sync" func (a *Account) Withdraw(v int) { a.mu.Lock() defer a.mu.Unlock() a.balance -= v } type Account struct { balance int mu sync.Mutex } func NewAccount(init int) Account { return Account{balance: init} } func (a *Account) Deposit(v int) { a.mu.Lock() defer a.mu.Unlock() a.balance += v } 9

10. Locks in Go func (a *Account) CheckBalance() int { a.mu.Lock() defer a.mu.Unlock() return a.balance } package account import "sync" func (a *Account) Withdraw(v int) { a.mu.Lock() defer a.mu.Unlock() a.balance -= v } type Account struct { balance int mu sync.Mutex } func NewAccount(init int) Account { return Account{balance: init} } func (a *Account) Deposit(v int) { a.mu.Lock() defer a.mu.Unlock() a.balance += v } 10

11. Read Write Locks in Go func (a *Account) CheckBalance() int { a.rwLock.RLock() defer a.lock.RUnlock() return a.balance } package account import "sync" func (a *Account) Withdraw(v int) { a.rwLock.Lock() defer a.rwLock.Unlock() a.balance -= v } type Account struct { balance int rwLock sync.RWMutex } func NewAccount(init int) Account { return Account{balance: init} } func (a *Account) Deposit(v int) { a.rwLock.Lock() defer a.rwLock.Unlock() a.balance += v } 11

12. Read Write Locks in Go func (a *Account) CheckBalance() int { a.rwLock.RLock() defer a.rwLock.RUnlock() return a.balance } package account import "sync" func (a *Account) Withdraw(v int) { a.rwLock.Lock() defer a.rwLock.Unlock() a.balance -= v } type Account struct { balance int rwLock sync.RWMutex } func NewAccount(init int) Account { return Account{balance: init} } func (a *Account) Deposit(v int) { a.rwLock.Lock() defer a.rwLock.Unlock() a.balance += v } 12

13. Two Solutions to the Same Problem Locks: Channels: Multiple threads can reference same memory location Data item initially stored in channel Threads must request item from channel, make updates, and return item to channel Use lock to ensure only one thread is updating it at any given time T1 T2 T3 T1 T2 T3 100 C 13 0x1000: 100 100 110

14. Bank Account Code (using channels) package account func (a *Account) CheckBalance() int { // What goes Here? } type Account struct { // Fill in Here } func (a *Account) Withdraw(v int) { // ??? } func NewAccount(init int) Account { // Fill in Here } func (a *Account) Deposit(v int) { // ??? } 14

15. Bank Account Code (using channels) package account func (a *Account) CheckBalance() int { // What goes Here? } type Account struct { balance chan int } func (a *Account) Withdraw(v int) { // ??? } func NewAccount(init int) Account { a := Account{ balance: make(chan int, 1) } a.balance <- init return a } func (a *Account) Deposit(v int) { // ??? } 15

16. Bank Account Code (using channels) package account func (a *Account) CheckBalance() int { bal := <-a.balance a.balance <- bal return bal } type Account struct { balance chan int } func NewAccount(init int) Account { a := Account{ balance: make(chan int, 1) } a.balance <- init return a } func (a *Account) Withdraw(v int) { // ??? } func (a *Account) Deposit(v int) { //??? } 16

17. Bank Account Code (using channels) package account func (a *Account) CheckBalance() int { bal := <-a.balance a.balance <- bal return bal } type Account struct { balance chan int } func NewAccount(init int) Account { a := Account{ balance: make(chan int, 1) } a.balance <- init return a } func (a *Account) Withdraw(v int) { bal := <-a.balance a.balance <- (bal - v) } func (a *Account) Deposit(v int) { //??? } 17

18. Bank Account Code (using channels) package account func (a *Account) CheckBalance() int { bal := <-a.balance a.balance <- bal return bal } type Account struct { balance chan int } func NewAccount(init int) Account { a := Account{ balance: make(chan int, 1) } a.balance <- init return a } func (a *Account) Withdraw(v int) { bal := <-a.balance a.balance <- (bal - v) } func (a *Account) Deposit(v int) { bal := <-a.balance a.balance <- (bal + v) } 18

19. Select statement select allows a goroutine to wait on multiple channels at once for { select { case money := <-dad: buySnacks(money) case money := <-mom: buySnacks(money) } } 21

20. Select statement select allows a goroutine to wait on multiple channels at once for { select { case money := <-dad: buySnacks(money) case money := <-mom: buySnacks(money) case default: starve() time.Sleep(5 * time.Second) } } 22

21. Handle timeouts using select // Asynchronously request an answer // from server, timing out after X // seconds result := make(chan int) timeout := make(chan bool) // Wait on both channels select { case res := <-result: handleResult(res) case <-timeout: // Ask server go func() { response := // ... send RPC result <- response }() fmt.Println("Timeout!") } // Start timer go func() { time.Sleep(5 * time.Second) timeout <- true }() 23

22. Exercise: Implementing a mutex using channels type Lock struct { // ??? } func NewLock() Lock { // ??? } func (l *Lock) Lock() { // ??? } func (l *Lock) Unlock() { // ??? } 24

23. Exercise: Implementing a mutex using channels type Lock struct { ch chan bool } func NewLock() Lock { // ??? } func (l *Lock) Lock() { // ??? } func (l *Lock) Unlock() { // ??? } 25

24. Exercise: Implementing a mutex using channels type Lock struct { ch chan bool } func NewLock() Lock { lock := Lock{make(chan bool, 1)} lock.ch <- true return lock } func (l *Lock) Lock() { // ??? } func (l *Lock) Unlock() { // ??? } 26

25. Exercise: Implementing a mutex using channels type Lock struct { ch chan bool } func NewLock() Lock { lock := Lock{make(chan bool, 1)} lock.ch <- true return lock } func (l *Lock) Lock() { <-lock.ch } func (l *Lock) Unlock() { // ??? } 27

26. Exercise: Implementing a mutex using channels type Lock struct { ch chan bool } func NewLock() Lock { lock := Lock{make(chan bool, 1)} lock.ch <- true return lock } func (l *Lock) Lock() { <-lock.ch } func (l *Lock) Unlock() { lock.ch <- true } 28

27. Outline Two synchronization mechanisms Locks Channels Mapreduce 30

28. Application: Word count How much wood would a woodchuck chuck if a woodchuck could chuck wood? how: 1, much: 1, wood: 2, would: 1, a: 2, woodchuck: 2, chuck: 2, if: 1, could: 1 31

29. Application: Word count Locally: tokenize and put words in a hash map How do you parallelize this? Partition the document into n partitions. Build n hash maps, one for each partition Merge the n hash maps (by key) 32

30. How do you do this in a distributed environment? 33

31. When in the Course of human events, it becomes necessary for one people to dissolve the political bands which have connected them with another, and to assume, among the Powers of the earth, the separate and equal station to which the Laws of Nature and of Nature's God entitle them, a decent respect to the opinions of mankind requires that they should declare the causes which impel them to the separation. Input document 34

32. When in the Course of human events, it becomes necessary for one people to dissolve the political bands which have connected them with another, and to assume, among the Powers of the earth, the separate and equal station to which the Laws of Nature and of Nature's God entitle them, a decent respect to the opinions of mankind requires that they should declare the causes which impel them to the separation. Partition 35

33. When in the Course of human events, it becomes necessary for one people to dissolve the political bands which have connected them with another, and to assume, among the Powers of the earth, the separate and equal station to which the Laws of Nature and of Nature's God entitle them, a decent respect to the opinions of mankind requires that they should declare the causes which impel them to the separation. Partition 36

34. requires that they should declare the causes which impel them to the separation. When in the Course of human events, it becomes necessary Nature and of Nature's for one people to God entitle them, a decent respect to the opinions of mankind among the Powers of the dissolve the political earth, the separate and bands which have equal station to which connected them with the Laws of another, and to assume, 37

35. requires: 1, that: 1, they: 1, should: 1, declare: 1, the: 1, causes: 1, which: 1 ... when: 1, in: 1, the: 1, course: 1, nature: 2, and: 1, of: 2, of: 1, human: 1, god: 1, entitle: 1, them: 1, events: 1, it: 1 decent: 1, respect: 1, mankind: 1, opinion: 1 ... dissolve: 1, the: 2, among: 1, the: 2, political: 1, bands: 1, powers: 1, of: 2, which: 1, have: 1, earth: 1, separate: 1, connected: 1, them: 1 ... equal: 1, and: 1 ... Compute word counts locally 38

36. requires: 1, that: 1, they: 1, should: 1, declare: 1, the: 1, causes: 1, which: 1 ... when: 1, in: 1, the: 1, course: 1, nature: 2, and: 1, of: 2, of: 1, human: 1, Now what How to merge results? god: 1, entitle: 1, them: 1, events: 1, it: 1 decent: 1, respect: 1, mankind: 1, opinion: 1 ... dissolve: 1, the: 2, among: 1, the: 2, political: 1, bands: 1, powers: 1, of: 2, which: 1, have: 1, earth: 1, separate: 1, connected: 1, them: 1 ... equal: 1, and: 1 ... Compute word counts locally 39

37. Merging results computed locally Several options requires additional computation for correct results Don t merge Send everything to one node what if data is too big? Too slow Partition key space among nodes in cluster (e.g. [a-e], [f-j], [k-p] ...) 1. Assign a key space to each node 2. Split local results by the key spaces 3. Fetch and merge results that correspond to the node s key space 40

38. requires: 1, that: 1, they: 1, should: 1, declare: 1, the: 1, causes: 1, which: 1 ... when: 1, in: 1, the: 1, course: 1, nature: 2, and: 1, of: 2, of: 1, human: 1, god: 1, entitle: 1, them: 1, events: 1, it: 1 decent: 1, respect: 1, mankind: 1, opinion: 1 ... dissolve: 1, the: 2, among: 1, the: 2, political: 1, bands: 1, powers: 1, of: 2, which: 1, have: 1, earth: 1, separate: 1, connected: 1, them: 1 ... equal: 1, and: 1 ... 41

39. [a-e] [f-j] causes: 1, declare: 1, [k-p] requires: 1, should: 1, [q-s] that: 1, they: 1, the: 1, [t-z] which: 1 when: 1, the: 1, in: 1, it: 1, human: 1, nature: 2, of: 2, course: 1, events: 1, mankind: 1, opinion: 1, of: 1 entitle: 1, and: 1, decent: 1, god: 1, them: 1, respect: 1, bands: 1, dissolve: 1, among: 1, and: 1, connected: 1, have: 1, equal: 1, earth: 1, political: 1, the: 1, separate: 1, the: 2, them: 1, which: 1 powers: 1, of: 2 Split local results by key space 42

40. [q-s] [t-z] [f-j] [a-e] [k-p] All-to-all shuffle 43

41. [a-e] [f-j] [k-p] requires: 1, should: 1, [q-s] respect: 1, separate: 1 [t-z] when: 1, the: 1, that: 1, they: 1, the: 1, which: 1, god: 1, have: 1, them: 1, the: 2, the: 1, in: 1, it: 1, them: 1, which: 1 human: 1, bands: 1, dissolve: 1, powers: 1, of: 2, connected: 1, course: 1, nature: 2, of: 2, events: 1, among: 1, and: 1, mankind: 1, of: 1, equal: 1, earth: 1, entitle: 1, opinion: 1, political: 1 and: 1, decent: 1, causes: 1, declare: 1 Note the duplicates... 44

42. requires: 1, should: 1, respect: 1, separate: 1 when: 1, the: 4, that: 1, they: 1, god: 1, have: 1, which: 2, them: 2 in: 1, it: 1, human: 1, bands: 1, dissolve: 1, connected: 1, course: 1, powers: 1, of: 5, events: 1, among: 1, and: 2, nature: 2, mankind: 1, equal: 1, earth: 1, opinion: 1, political: 1 entitle: 1, decent: 1, causes: 1, declare: 1 Merge results received from other nodes 45

43. Mapreduce Partition dataset into many chunks Map stage: Each node processes one or more chunks locally Reduce stage: Each node fetches and merges partial results from all other nodes 46

44. Mapreduce Interface map(key, value) -> list(<k , v >) Apply function to (key, value) pair Outputs list of intermediate pairs reduce(key, list<value>) -> <k , v > Applies aggregation function to values Outputs result 47

45. Mapreduce: Word count map(key, value): // key = document name // value = document contents for each word w in value: emit (w, 1) reduce(key, values): // key = the word // values = number of occurrences of that word count = sum(values) emit (key, count) 48

46. Mapreduce: Word count map combine shuffle reduce 49

47. Why is implementing MapReduce hard? Failure is common Even if each machine is available p = 99.999% of the time, a datacenter with n = 100,000 machines still encounters failures (1-pn) = 63% of the time Data skew causes unbalanced performance across cluster Problems occur at scale. Hard to debug! 50

48. MapReduce 2004 2007 2011 2012 2015 Dryad 51