Implementing non re-entrant functions in Golang

January 4, 2018

A non re-entrant function is a function that could only be executing once at any point in time, regardless of how many times it is being invoked and by how many goroutines.

This post illustrates blocking non re-entrant functions and yielding non re-entrant functions implementations in golang.

A use case

A service is polling for some conditions, monitoring some statuses once per second. We want each status to be checked independently of others without blocking. An implementation might look like:

func main() {
    tick := time.Tick(time.Second)
    go func() {
        for range tick {
            go CheckSomeStatus()
            go CheckAnotherStatus()
        }
    }()
}

We choose to run each status check in its own goroutine so that CheckAnotherStatus() doesn't wait upon CheckSomeStatus() to complete.

Each of these checks typically take a very short amount of time, and much less than a second. What happens, though, if CheckAnotherStatus() itself takes more than one second to run? Perhaps there's an unexpected network or disk latency affecting the execution time of the check.

Does it make sense for the function to be executed twice at the same time? If not, we want it to be non re-entrant.

Blocking, non-reentrant functions

The simple way to prevent a function from operating multiple times concurrently is using a sync.Mutex.

Assuming we only care about calling this function from the loop above, we can implement the lock from outside the function:

import (
    "sync"
    "time"
)

func main() {
    tick := time.Tick(time.Second)
    var mu sync.Mutex
    go func() {
        for range tick {
            go CheckSomeStatus()
            go func() {
                mu.Lock()
                defer mu.Unlock()
                CheckAnotherStatus()
            }()
        }
    }()
}

The above ensures CheckAnotherStatus() is not executed by multiple iterations of our loop concurrently. Any subsequent iterations of the loop whilst a previous execution of CheckAnotherStatus() is still running, will be blocked by the mutex.

The blocking solution has the following properties:

  • It ensures as many `CheckAnotherStatus()` invocations as the number of loop iterations.
  • Assuming one execution of `CheckAnotherStatus()` stalls, subsequent iterations make for a pileup of requests to invoke same function.

Yielding, non re-entrant functions

In our status check story, it may not make sense for some 10 subsequent calls to pile up. One the stalled CheckAnotherStatus() execution completes, all 10 calls suddenly execute, sequentially, and possibly all complete within the next second, making for 10 identical checks at that same second.

Another solution would be to yield. A yielding solution will:

  • Abort execution of `CheckAnotherStatus()` if it is already being executed.
  • Will run at most one execution of `CheckAnotherStatus()` per second.
  • May in effect run less `CheckAnotherStatus()` invocations than the number of loop iterations.

The solution is achieved via:

import (
    "sync/atomic"
    "time"
)

func main() {
    tick := time.Tick(time.Second)
    var reentranceFlag int64
    go func() {
        for range tick {
            go CheckSomeStatus()
            go func() {
                if atomic.CompareAndSwapInt64(&reentranceFlag, 0, 1) {
                    defer atomic.StoreInt64(&reentranceFlag, 0)
                } else {
                    return
                }
                CheckAnotherStatus()
            }()
        }
    }()
}

atomic.CompareAndSwapInt64(&reentranceFlag, 0, 1) will return true only when reentranceFlag == 0, and will atomically set it to 1. In such case, entry is allowed and the function can be executed. reentranceFlag is kept at 1 until CheckAnotherStatus() completes, at which time it is reset. When CompareAndSwapInt64(...) returns false that means reentranceFlag != 0, meaning the function is already being executing by another goroutine. The code yields and silently exits the function.

We have chosen to implement the non re-entrant code outside the function in question; we could have implemented it within the function itself. Also, I have a thing for int64. An int32 will of course suffice.

 
Powered by Wordpress and MySQL. Theme by openark.org