proposal: x/sync/semaphore: make semaphore resizable

[sherifabdlnaby]

Hello,

Semaphores are often used to bound concurrency, for example I was implementing a goroutines pool pattern with weighted jobs, so a weighted semaphore is better and more performant than channel-based semaphore. a common functionality in goroutines pool is to be resizable, however the current sync/x/semaphore doesn't allow resizing the semaphore.

There is another implementation of a non-channel-based semaphores that supports resizing, but I found many bugs/deadlocks using them and they're all less performant than x/sync/semaphore.

The current implementation of x/sync/semaphore can be easily extended to be resizable, without affecting performance by any means.

[bcmills]

CC @jba @Sajmani

[bcmills]

This proposal needs more detail.

• What are some concrete use-cases for resizable semaphores? (Links to existing code that could be replaced or improved by this change would be ideal.)

• What is the specific API being proposed?

  • Does it add and remove capacity, or set the capacity to an absolute quantity?
  • If it sets the absolute quantity, what happens if that capacity is lower than the number of outstanding tokens?

[bcmills]

Note that if you have some upper bound, you can already “resize” a semaphore.Weighted by acquiring and releasing surplus tokens:

const (
	maxCap = […]
	initialCap = […]  // ≤ maxCap
)
sem := semaphore.NewWeighted(maxCap)
sem.Acquire(ctx, maxCap - initialCap)
// Effective capacity of sem is now initialCap,
// but it can be “resized” up to maxCap by releasing tokens.

[sherifabdlnaby]

@bcmills

Example:

cockroachdb uses a semaphore for rate limiting, I found a bug (cockroachdb/cockroach#33554) in the semaphore package they were using that has potential to deadlock.
They decided to keep using this semaphore implementation because the bug was not currently reachable in their code and there aren't many alternative resizable semaphores. cockroachdb/cockroach#33554 (comment)

fixing the bug in that mentioned semaphore implementation halved its performance (300% slower than x/sync/semaphore) according to benchmarks.

---

What is the specific API being proposed?

Does it add and remove capacity, or set the capacity to an absolute quantity?

It sets the capacity to an absolute quantity.

If it sets the absolute quantity, what happens if that capacity is lower than the number of outstanding tokens?

If semaphore is resized to a number lower than the current acquired tokens it will not acquire any new tokens until a release that brings down current capacity to be lower or equal to the new semaphore capacity.

---

More details

What happens to the Aquire of N that was marked impossible and not added to waiters list ? and what happens if an Aquire of N that was already in the waiting list when a resize lower the capacity to be < N ?

In the current Implementation an Aquire of N where N is > capacity will not be added to the waiters' linked list because It is impossible to get acquired. and will block forever unless cancelled by its ctx.

In the PR, I've added a new linked-list for the impossible waiters, when Acquire(N) is impossible it will be added to the impossible waiters list, Impossible waiters can become possible if a resize of the semaphore was big enough.

So now when Resize(N) is called this is what happens:

1. Set a new size for the semaphore.
2. Will loop through the waiters list removing the now-impossible waiters to the impossible waiters.
3. Will loop through the Impossible Waiters list adding the now-possible ones to the waiters list.
4. Will signal possible waiters from the front of the waiters list to unblock ( same as Release() mechanism).

A resize is O(W+I), W = length of waiters list, I = length of impossible waiters list.

[sherifabdlnaby]

Note that if you have some upper bound, you can already “resize” a semaphore.Weighted by acquiring and releasing surplus tokens:

const (
	maxCap = […]
	initialCap = […]  // ≤ maxCap
)
sem := semaphore.NewWeighted(maxCap)
sem.Acquire(ctx, maxCap - initialCap)
// Effective capacity of sem is now initialCap,
// but it can be “resized” up to maxCap by releasing tokens.

Yes, this will work effectively if you have an upper-bound.
I believe a simple .Resize(N) will be simpler to use.

[bcmills]

math.MaxInt64 is always a valid upper bound.

So it seems the only behavioral difference today is the FIFO behavior of “impossible” tasks. Those are not generally something you want to have in a well-behaved system anyway, since they consume resources while waiting for cancellation; so, how often does that difference matter?

[sherifabdlnaby]

@bcmills

math.MaxInt64 is always a valid upper bound.

Yes it's, but this will allow impossible tasks to be added to waiters list and will block other waiters when that impossible task is at the front of the list thus causing a deadlock which is unexpected semaphore behavior.

I understand your point that it is not generally something you want to have in a well-behaved system anyway.

But my opinion is a Resize() would be simpler to use than an ad-hoc way to resize the semaphore that may have unexpected deadlocks because of the semaphore implementation.

[rsc]

/cc @jba

[rsc]

This proposal has been added to the active column of the proposals project
and will now be reviewed at the weekly proposal review meetings.
— rsc for the proposal review group