Share by communicating

I’ve been looking for a good explanation to the concurrency slogan:

Do not communicate by sharing memory; instead, share memory by communicating

Having found none that satisfy my requirements:

• initial problem with an example
• provide Shared Memory solution
• provide Share by Communicating solution

this post is my take on explaining the subject.

After reading it one should be able to get an idea of ‘Share by Communicating’ model, how it’s different from ‘Communicate by Sharing’ model and how they both solve problem of access and modification a shared resource.

All [examples] provided are in Go.

Prerequisites

Let’s imagine we have access to a bank account:

type Account interface {
  Withdraw(uint)
  Deposit(uint)
  Balance() int
}

type Bank struct {
  account Account
}

func NewBank(account Account) *Bank {
  return &Bank{account: account}
}

func (bank *Bank) Withdraw(amount uint, actor_name string) {
  fmt.Println("[-]", amount, actor_name)
  bank.account.Withdraw(amount)
}

func (bank *Bank) Deposit(amount uint, actor_name string) {
  fmt.Println("[+]", amount, actor_name)
  bank.account.Deposit(amount)
}

func (bank *Bank) Balance() int {
  return bank.account.Balance()
}

Since Account is an interface its simplest implementation may look like this

type SimpleAccount struct {
  balance int
}

func NewSimpleAccount(balance int) *SimpleAccount {
  return &SimpleAccount{balance: balance}
}

func (acc *SimpleAccount) Deposit(amount uint) {
  acc.setBalance(acc.balance + int(amount))
}

func (acc *SimpleAccount) Withdraw(amount uint) {
  if acc.balance >= int(amount) {
    acc.setBalance(acc.balance - int(amount))
  } else {
    panic("Not enough funds")
  }
}

func (acc *SimpleAccount) Balance() int {
  return acc.balance
}

func (acc *SimpleAccount) setBalance(balance int) {
  acc.add_some_latency()
  acc.balance = balance
}

func (acc *SimpleAccount) add_some_latency() {
  // add some latency here
  <-time.After(time.Duration(rand.Intn(100)) * time.Millisecond)
}

You may have noticed that balance is not modified directly but inside setBalance method. This is ‘by design’ to help describe the problem. It’ll be explained later on.

Having all pieces ready bank account could be used like this:

func main() {
  balance := 80

  b := bank.NewBank(bank.NewSimpleAccount(balance))

  fmt.Println("Initial balance", b.Balance())

  b.Withdraw(30, "GF")

  fmt.Println("-----------------")
  fmt.Println("Final balance", b.Balance())
}

Running above code yields:

Initial balance 80
[-] 30 GF
-----------------
Final balance 50

It’s all good!

In real life, though, a bank account has many clients: funds get withdrawn and deposited by different parties. Let’s reflect this in code:

func main() {
  balance := 80

  b := bank.NewBank(bank.NewSimpleAccount(balance))

  fmt.Println("Initial balance", b.Balance())

  done := make(chan bool)

  go func() { b.Withdraw(30, "GF"); done <- true }()
  go func() { b.Withdraw(10, "RA"); done <- true }()

  // wait until goroutines finish
  <-done
  <-done

  fmt.Println("-----------------")
  fmt.Println("Final balance", b.Balance())
}

Here 2 concurrent processes withdraw from our bank account. Which yields:

Initial balance 80
[-] 30 GF
[-] 10 RA
-----------------
Final balance 70

Wow, not too bad! Unfortunately the result is clearly incorrect, as having 40 withdrawn from 80 results in 40 and not 70 in final balance.

Something is wrong with code above. Let’s examine why it happens.

Problem

Invalid state is very likely to occur whenever a number of processes shares a resource.

In our case we ended up having wrong final balance (invalid state) of the bank account(shared resource) after 2 processes tried to withdraw funds in the same time.

Let’s visualize the process:

                        process
                    ________________
                    __GF___|__RA____

1.  get balance        80  |  80
2.  withdraw          -30  | -10
3.  new balance        50  |  70
                       ... |  ...
4.  set balance        50  ?  70
                           |
5.  last write wins        |
                     ________________
6.  final balance         70

... here describes possible latency implemented with add_some_latency method to model real-world communication delays (IE when persisting data). So final balance value becomes the one last running process sets it to.

Solutions

This post demonstrates 2 solutions to the problem described:

• Shared Memory solution
• Share by Communicating solution

All solutions work around flawed SimpleAccount by wrapping it and implementing “protection” mechanisms.

Shared Memory solution

Aka “Communicate by sharing” part of the slogan.

As name implies a locking mechanism is used to prevent simultaneous access and modification of a shared resource. Lock “communicates” to other processes that resource is being used by a process and therefore they need to wait until it’s available again.

Let’s see how LockingAccount is implemented.

type LockingAccount struct {
  lock    sync.Mutex
  account *SimpleAccount
}

// wraps around SimpleAccount
func NewLockingAccount(balance int) *LockingAccount {
  return &LockingAccoun{account: NewSimpleAccount(balance)}
}

func (acc *LockingAccount) Deposit(amount uint) {
  acc.lock.Lock()
  defer acc.lock.Unlock()
  acc.account.Deposit(amount)
}

func (acc *LockingAccount) Withdraw(amount uint) {
  acc.lock.Lock()
  defer acc.lock.Unlock()
  acc.account.Withdraw(amount)
}

func (acc *LockingAccount) Balance() int {
  acc.lock.Lock()
  defer acc.lock.Unlock()
  return acc.account.Balance()
}

Pretty straightforward.

Note lock sync.Lock, lock.Lock() and lock.Unlock().

Every time a process accesses the balance(shared resource) a lock gets set until completion.

Our LockingAccount use case may look like this now:

func main() {
  balance := 80

  b := bank.NewBank(bank.NewLockingAccount(balance))

  fmt.Println("Initial balance", b.Balance())

  done := make(chan bool)

  go func() { b.Withdraw(30, "GF"); done <- true }()
  go func() { b.Withdraw(10, "RA"); done <- true }()

  // wait until goroutines finish
  <-done
  <-done

  fmt.Println("-----------------")
  fmt.Println("Final balance", b.Balance())
}

running the code yields:

Initial balance 80
[-] 30 GF
[-] 10 RA
-----------------
Final balance 40

Yay! It’s correct now.

In this case the first process to access account gains exclusive lock preventing other processes from accessing the resource. Those processes just wait around until lock is lifted.

Let’s visualize the process, assuming “GF” gets to the resource first:

                    process
                ________________
                __GF___|__RA____
Lock()                ><
get balance        80  |
withdraw          -30  |
new balance        50  |
                   ... |
set balance        50  |
Unlock()              <>
                       |
current balance       50
                       |
Lock()                ><
get balance            |  50
withdraw               | -10
new balance            |  40
                       |  ...
set balance            |  40
Unlock()              <>
                ________________
final balance          40

Now we have processes accessing shared resource sequentially producing deterministic results.

Share by Communicating solution

Aka “Share by Communicating” part of the slogan

Now account is named ConcurrentAccount and looks like this:

type ConcurrentAccount struct {
  account     *SimpleAccount
  deposits    chan uint
  withdrawals chan uint
  balances    chan chan int
}

func NewConcurrentAccount(amount int) *ConcurrentAccount {

  acc := &ConcurrentAccount{
    account:     &SimpleAccount{balance: amount},
    deposits:    make(chan uint),
    withdrawals: make(chan uint),
    balances:    make(chan chan int),
  }
  acc.listen()

  return acc
}

func (acc *ConcurrentAccount) Balance() int {
  ch := make(chan int)
  acc.balances <- ch
  return <-ch
}
func (acc *ConcurrentAccount) Deposit(amount uint) {
  acc.deposits <- amount
}

func (acc *ConcurrentAccount) Withdraw(amount uint) {
  acc.withdrawals <- amount
}

func (acc *ConcurrentAccount) listen() {
  go func() {
    for {
      select {
      case amnt := <-acc.deposits:
        acc.account.Deposit(amnt)
      case amnt := <-acc.withdrawals:
        acc.account.Withdraw(amnt)
      case ch := <-acc.balances:
        ch <- acc.account.Balance()
      }
    }
  }()
}

Again ConcurrentAccount wraps around flawed SimpleAccount adding communication channels.

The code and results are similar to locking version except that bank gets created with concurrent account:

b := bank.NewBank(bank.NewConcurrentAccount(balance))

Running it this time yields correct results just like with locking solution:

Initial balance 80
[-] 30 GF
[-] 10 RA
-----------------
Final balance 40

Let’s get into details here.

How Share by Comminicating works

Few basic observations:

• Shared resource is encapsulated within a controlling process.

  Thus making the resource non-shared. No other processes is able to access or modify resource directly. As you can see methods to access or modify account don’t actually perform the change.

   func (acc *ConcurrentAccount) Balance() int {
     ch := make(chan int)
     acc.balances <- ch
     balance := <-ch
     return balance
   }
   func (acc *ConcurrentAccount) Deposit(amount uint) {
     acc.deposits <- amount
   }
  
   func (acc *ConcurrentAccount) Withdraw(amount uint) {
     acc.withdrawals <- amount
   }
  

• Access or modification is communicated to a controlling process with a ‘message’.

• Any access or modificaion happens sequentially within controlling process.

  Communicated access or change request gets performed once the controlling process receives it. Let’s take a closer look at the process:

  func (acc *ConcurrentAccount) listen() {
    // run controlling process
    go func() {
      for {
        select {
        case amnt := <-acc.deposits:
          acc.account.Deposit(amnt)
        case amnt := <-acc.withdrawals:
          acc.account.Withdraw(amnt)
        case ch := <-acc.balances:
          ch <- acc.account.Balance()
        }
      }
    }()
  }
  

  select constantly pulls out ‘messages’ that become available on channels which enables corresponding operation to be performed.

  Important to understand that everything within select statement is sequential (as it’s executed in the same process). Every ‘event’ (either receiving or sending on a channel) happens one at a time which guarantees synchronised access to the ‘shared resource’.

  This is both simple and tricky to grasp.

Let’s go through Balance() as example:

    A Process              | Controlling Process
    ----------------------------------------------
                           |
1.     b.Balance()         |
2.             ch -> [acc.balances]-> ch
3.             <-ch        |  balance = acc.account.Balance()
4.     return  balance <-[ch]<- balance
5                          |

What each process does

A Process

1. calls b.Balance()
2. communicates a newly created channel ch though the acc.balances channel so that Controlling Process can communicate balance back through the ch
3. waits <-ch for the balance value to be received
4. receives balance value
5. continues

Controlling process

1. idle-ing or handing smth
2. receives balance request through acc.balances channel with a channel ch to send value back into
3. gets the actual balance value
4. sends balance value down the ch pipe
5. ready to handle new requests

Controlling process processes one event at a time. That is that during steps 2-4 no other operations are performed except ones described.

Conclusion

This post describes problem and possible solutions but doesn’t go into advantages or disadvantages of each solution.

Following posts will elaborate on that matter as well as suggest improved solutions.

Feel free to point to my mistakes.

Thanks for reading this far.