Skip to content

Implement resizable semaphore data structure

Quang-Minh Nguyen requested to merge qmnguyen0711/implement-resizable-semaphore into master

For #5523 (closed), extracted from !6353 (closed).

This MR is the re-implementation of !6183 (merged), which was reverted due to a memory-leak incident.

This MR re-implement resizable semaphore, which is the core of the adaptive concurrency limit. Instead of using a dedicated Goroutine for state management like the prior MR, the new version uses a mutex and a double-linked list to manage the waiters. When a caller wants to acquire a full semaphore, it is pushed to the last of the list. As all operations are synchronized, there is no need for spawning new goroutine.

The new semaphore implementation also determines the official FIFO order of the queue. The current implementation uses buffered channels, hence the queue order is not guaranteed when the "concurrency" one is full. In the future, we are looking to apply LIFO order for more effectiveness during catastrophic events.

This MR contains a pure implementation without integrating anywhere. It also contains some isolated changes to make the integration into the concurrency limiter a bit easier later (!6353 (closed) for references).

Benchmark

Benchmarking a semaphore is tough. I added some benchmark tests to verify the speed of acquiring the semaphore when it's idle and it's full. A realistic semaphore on production has a size of 100-1000.

goos: darwin
goarch: arm64
pkg: gitlab.com/gitlab-org/gitaly/v16/internal/limiter
BenchmarkResizableSemaphore
BenchmarkResizableSemaphore/100
BenchmarkResizableSemaphore/100/acquire_then_release_immediately
BenchmarkResizableSemaphore/100/acquire_then_release_immediately-10             1000000000               0.0001521 ns/op               0 B/op          0 allocs/op
BenchmarkResizableSemaphore/100/acquire_then_release_after_done
BenchmarkResizableSemaphore/100/acquire_then_release_after_done-10              1000000000               0.0001680 ns/op               0 B/op          0 allocs/op
BenchmarkResizableSemaphore/100/acquire_after_waiting
BenchmarkResizableSemaphore/100/acquire_after_waiting-10                        1000000000               0.0004323 ns/op               0 B/op          0 allocs/op
BenchmarkResizableSemaphore/1000
BenchmarkResizableSemaphore/1000/acquire_then_release_immediately
BenchmarkResizableSemaphore/1000/acquire_then_release_immediately-10            1000000000               0.001163 ns/op        0 B/op          0 allocs/op
BenchmarkResizableSemaphore/1000/acquire_then_release_after_done
BenchmarkResizableSemaphore/1000/acquire_then_release_after_done-10             1000000000               0.001467 ns/op        0 B/op          0 allocs/op
BenchmarkResizableSemaphore/1000/acquire_after_waiting
BenchmarkResizableSemaphore/1000/acquire_after_waiting-10                       1000000000               0.004272 ns/op        0 B/op          0 allocs/op
BenchmarkResizableSemaphore/10000
BenchmarkResizableSemaphore/10000/acquire_then_release_immediately
BenchmarkResizableSemaphore/10000/acquire_then_release_immediately-10           1000000000               0.01210 ns/op         0 B/op          0 allocs/op
BenchmarkResizableSemaphore/10000/acquire_then_release_after_done
BenchmarkResizableSemaphore/10000/acquire_then_release_after_done-10            1000000000               0.01756 ns/op         0 B/op          0 allocs/op
BenchmarkResizableSemaphore/10000/acquire_after_waiting
BenchmarkResizableSemaphore/10000/acquire_after_waiting-10                      1000000000               0.04383 ns/op         0 B/op          0 allocs/op
Edited by Quang-Minh Nguyen

Merge request reports