Solving it without loops and locks
A simple implementation may look like this:
const Max = 8
var index int64
func Inc() int64 {
value := atomic.AddInt64(&index, 1)
if value < Max {
return value // We're done
}
// Must normalize, optionally reset:
value %= Max
if value == 0 {
atomic.AddInt64(&index, -Max) // Reset
}
return value
}
How does it work?
It simply adds 1 to the counter; atomic.AddInt64()
returns the new value. If it's less than Max
, "we're done", we can return it.
If it's greater than or equal to Max
, then we have to normalize the value (make sure it's in the range [0..Max)
) and reset the counter.
Reset may only be done by a single caller (a single goroutine), which will be selected by the counter's value. The winner will be the one that caused the counter to reach Max
.
And the trick to avoid the need of locks is to reset it by adding -Max
, not by setting it to 0
. Since the counter's value is normalized, it won't cause any problems if other goroutines are calling it and incrementing it concurrently.
Of course with many goroutines calling this Inc()
concurrently it may be that the counter will be incremented more that Max
times before a goroutine that ought to reset it can actually carry out the reset, which would cause the counter to reach or exceed 2 * Max
or even 3 * Max
(in general: n * Max
). So we handle this by using a value % Max == 0
condition to decide if a reset should happen, which again will only happen at a single goroutine for each possible values of n
.
Simplification
Note that the normalization does not change values already in the range [0..Max)
, so you may opt to always perform the normalization. If you want to, you may simplify it to this:
func Inc() int64 {
value := atomic.AddInt64(&index, 1) % Max
if value == 0 {
atomic.AddInt64(&index, -Max) // Reset
}
return value
}
Reading the counter without incrementing it
The index
variable should not be accessed directly. If there's a need to read the counter's current value without incrementing it, the following function may be used:
func Get() int64 {
return atomic.LoadInt64(&index) % Max
}
Extreme scenario
Let's analyze an "extreme" scenario. In this, Inc()
is called 7 times, returning the numbers 1..7
. Now the next call to Inc()
after the increment will see that the counter is at 8 = Max
. It will then normalize the value to 0
and wants to reset the counter. Now let's say before the reset (which is to add -8
) is actually executed, 8 other calls happen. They will increment the counter 8 times, and the last one will again see that the counter's value is 16 = 2 * Max
. All the calls will normalize the values into the range 0..7
, and the last call will again go on to perform a reset. Let's say this reset is again delayed (e.g. for scheduling reasons), and yet another 8 calls come in. For the last, the counter's value will be 24 = 3 * Max
, the last call again will go on to perform a reset.
Note that all calls will only return values in the range [0..Max)
. Once all reset operations are executed, the counter's value will be 0
, properly, because it had a value of 24
and there were 3 "pending" reset operations. In practice there's only a slight chance for this to happen, but this solution handles it nicely and efficiently.