Skip to content

Git designed for AI agents.

14.3 KB
Raw Blame
package limiter

import (
	"context"
	"errors"
	"fmt"
	"sync"
	"time"

	"github.com/feder-cr/git-ai/internal/helper"
	"github.com/feder-cr/git-ai/internal/structerr"
	"github.com/feder-cr/git-ai/internal/tracing"
	"github.com/feder-cr/git-ai/proto/go/gitalypb"
	"go.opentelemetry.io/otel/attribute"
	"google.golang.org/protobuf/types/known/durationpb"
)

// semaphorer is an interface of a specific-purpose semaphore used for concurrency control.
type semaphorer interface {
	Acquire(ctx context.Context) error
	TryAcquire() error
	Release()
	Count() int
}

const (
	// TypePerRPC is a concurrency limiter whose key is the full method of gRPC server. All
	// requests of the same method shares the concurrency limit.
	TypePerRPC = "per-rpc"
	// TypePackObjects is a dedicated concurrency limiter for pack-objects. It uses request
	// information (RemoteIP/Repository/User) as the limiting key.
	TypePackObjects = "pack-objects"

	// GlobalLimitingKey is the limiting key reported for a global limit. It appears in the
	// `limit.limiting_key` log field and in tracing spans, and is named to make clear that no
	// per-request attribution is available there.
	GlobalLimitingKey = "global"
)

// ErrMaxQueueTime indicates a request has reached the maximum time allowed to wait in the
// concurrency queue.
var ErrMaxQueueTime = errors.New("maximum time in concurrency queue reached")

// ErrMaxQueueSize indicates the concurrency queue has reached its maximum size
var ErrMaxQueueSize = errors.New("maximum queue size reached")

// QueueTickerCreator is a function that provides a ticker
type QueueTickerCreator func() helper.Ticker

// keyedConcurrencyLimiter is a concurrency limiter that applies to a specific keyed resource.
type keyedConcurrencyLimiter struct {
	refcount              int
	monitor               ConcurrencyMonitor
	maxQueueWait          time.Duration
	setWaitTimeoutContext func() context.Context

	// concurrencyTokens is the counting semaphore to control available concurrency tokens, where every token
	// allows one concurrent call to the concurrency-limited function.
	concurrencyTokens semaphorer
	// queueTokens is the counting semaphore to control available queue tokens, where every token allows one
	// concurrent call to be admitted to the queue.
	queueTokens semaphorer
}

// acquire tries to acquire the semaphore. It may fail if the admission queue is full or if the max
// queue-time ticker ticks before acquiring a concurrency token.
func (sem *keyedConcurrencyLimiter) acquire(ctx context.Context, limitingKey string) (returnedErr error) {
	if sem.queueTokens != nil {
		// Try to acquire the queueing token. The queueing token is used to control how many
		// callers may wait for the concurrency token at the same time. If there are no more
		// queueing tokens then this indicates that the queue is full and we thus return an
		// error immediately.
		if err := sem.queueTokens.TryAcquire(); err != nil {
			return err
		}
		// We have acquired a queueing token, so we need to release it if acquiring
		// the concurrency token fails. If we succeed to acquire the concurrency
		// token though then we retain the queueing token until the caller signals
		// that the concurrency-limited function has finished. As a consequence the
		// queue token is returned together with the concurrency token.
		//
		// A simpler model would be to just have `maxQueueLength` many queueing
		// tokens. But this would add concurrency-limiting when acquiring the queue
		// token itself, which is not what we want to do. Instead, we want to admit
		// as many callers into the queue as the queue length permits plus the
		// number of available concurrency tokens allows.
		defer func() {
			if returnedErr != nil {
				sem.queueTokens.Release()
			}
		}()
	}

	// We are queued now, so let's tell the monitor. Furthermore, even though we're still
	// holding the queueing token when this function exits successfully we also tell the monitor
	// that we have exited the queue. It is only an implementation detail anyway that we hold on
	// to the token, so the monitor shouldn't care about that.
	sem.monitor.Queued(ctx, limitingKey, sem.queueLength())
	defer sem.monitor.Dequeued(ctx)

	if sem.maxQueueWait != 0 {
		if sem.setWaitTimeoutContext != nil {
			ctx = sem.setWaitTimeoutContext()
		} else {
			var cancel context.CancelFunc
			ctx, cancel = context.WithTimeout(ctx, sem.maxQueueWait)
			defer cancel()
		}
	}

	// Try to acquire the concurrency token now that we're in the queue.
	return sem.concurrencyTokens.Acquire(ctx)
}

// release releases the acquired tokens.
func (sem *keyedConcurrencyLimiter) release() {
	if sem.queueTokens != nil {
		sem.queueTokens.Release()
	}
	sem.concurrencyTokens.Release()
}

// queueLength returns the length of the queue waiting for tokens.
func (sem *keyedConcurrencyLimiter) queueLength() int {
	if sem.queueTokens == nil {
		return 0
	}
	return sem.queueTokens.Count() - sem.concurrencyTokens.Count()
}

// inProgress returns the number of in-progress tokens.
func (sem *keyedConcurrencyLimiter) inProgress() int {
	return sem.concurrencyTokens.Count()
}

// ConcurrencyLimiter contains rate limiter state.
type ConcurrencyLimiter struct {
	// limit is the adaptive maximum number of concurrent calls to the limited function. This limit is
	// calculated adaptively from an outside calculator.
	limit *AdaptiveLimit
	// maxQueueLength is the maximum number of operations allowed to wait in a queued state.
	// This limit is global and applies before the concurrency limit. Subsequent incoming
	// operations will be rejected with an error immediately.
	maxQueueLength int
	// maxQueueWait is a time duration of an operation allowed to wait in the queue.
	maxQueueWait time.Duration
	// SetWaitTimeoutContext is a function for setting up timeout context. If this is nill, context.WithTimeout is
	// used. This function is for internal testing purpose only.
	SetWaitTimeoutContext func() context.Context

	// monitor is a monitor that will get notified of the state of concurrency-limited RPC
	// calls.
	monitor ConcurrencyMonitor

	// globalSem is an optional semaphore whose budget every limiting key shares. When set, a
	// call has to acquire it on top of the budget of its own key.
	globalSem *keyedConcurrencyLimiter

	m sync.RWMutex
	// limitsByKey tracks all concurrency limits per key. Its per-key entries are lazily created
	// and will get evicted once there are no concurrency-limited calls for any such key
	// anymore.
	limitsByKey map[string]*keyedConcurrencyLimiter
}

// Option configures optional behavior of a ConcurrencyLimiter.
type Option func(*ConcurrencyLimiter)

// WithGlobalLimit adds a budget shared by every limiting key on top of the per-key budget. A call
// then has to fit within the budget of its key and within the shared one, and is rejected by
// whichever of the two runs out of room first. Passing a per-key limit of zero to
// NewConcurrencyLimiter leaves the shared budget applying on its own.
//
// The monitor observes the shared budget alone, so it should be distinct from the one given to
// NewConcurrencyLimiter for the two budgets to report their own metrics.
func WithGlobalLimit(
	limit *AdaptiveLimit,
	maxQueueLength int,
	maxQueueWait time.Duration,
	monitor ConcurrencyMonitor,
) Option {
	return func(c *ConcurrencyLimiter) {
		if monitor == nil {
			monitor = NewNoopConcurrencyMonitor()
		}

		var queueTokens semaphorer
		if maxQueueLength > 0 {
			queueTokens = c.createSemaphore(uint(limit.Current() + maxQueueLength))
		}

		c.globalSem = &keyedConcurrencyLimiter{
			monitor:           monitor,
			maxQueueWait:      maxQueueWait,
			concurrencyTokens: c.createSemaphore(uint(limit.Current())),
			queueTokens:       queueTokens,
		}

		// The shared semaphore is created once and lives for as long as the limiter, so it
		// is resized in place when the adaptive calculator moves its limit.
		limit.AfterUpdate(func(val int) {
			if semaphore, ok := c.globalSem.queueTokens.(*resizableSemaphore); ok {
				semaphore.Resize(uint(val + maxQueueLength))
			}
			if semaphore, ok := c.globalSem.concurrencyTokens.(*resizableSemaphore); ok {
				semaphore.Resize(uint(val))
			}
		})
	}
}

// NewConcurrencyLimiter creates a new concurrency rate limiter.
func NewConcurrencyLimiter(limit *AdaptiveLimit, maxQueueLength int, maxQueueWait time.Duration, monitor ConcurrencyMonitor, opts ...Option) *ConcurrencyLimiter {
	if monitor == nil {
		monitor = NewNoopConcurrencyMonitor()
	}

	limiter := &ConcurrencyLimiter{
		limit:          limit,
		maxQueueLength: maxQueueLength,
		maxQueueWait:   maxQueueWait,
		monitor:        monitor,
		limitsByKey:    make(map[string]*keyedConcurrencyLimiter),
	}

	// When the capacity of the limiter is updated we also need to update the size of both the queuing tokens as
	// well as the concurrency tokens to match the new size.
	limit.AfterUpdate(func(val int) {
		for _, keyedLimiter := range limiter.limitsByKey {
			if keyedLimiter.queueTokens != nil {
				if semaphore, ok := keyedLimiter.queueTokens.(*resizableSemaphore); ok {
					semaphore.Resize(uint(val + limiter.maxQueueLength))
				}
			}
			if semaphore, ok := keyedLimiter.concurrencyTokens.(*resizableSemaphore); ok {
				semaphore.Resize(uint(val))
			}
		}
	})

	for _, opt := range opts {
		opt(limiter)
	}

	return limiter
}

// Limit will limit the concurrency of the limited function f. There are two distinct mechanisms
// that limit execution of the function:
//
//  1. First, every call will enter the per-key queue. This queue limits how many callers may try to
//     acquire their per-key semaphore at the same time. If the queue is full the caller will be
//     rejected.
//  2. Second, when the caller has successfully entered the queue, they try to acquire their per-key
//     semaphore. If this takes longer than the maximum queueing limit then the caller will be
//     dequeued and gets an error.
//  3. Third, where a global limit is configured, the caller repeats both steps against a
//     semaphore shared by every key. The caller is rejected by whichever of the two budgets runs
//     out of room first.
func (c *ConcurrencyLimiter) Limit(ctx context.Context, limitingKey string, f LimitedFunc) (interface{}, error) {
	span, ctx := tracing.StartSpanIfHasParent(
		ctx,
		"limiter.ConcurrencyLimiter.Limit",
		[]attribute.KeyValue{
			attribute.String("key", limitingKey),
		},
	)
	defer span.End()

	// The budget of the key is acquired ahead of the shared one. A call waiting for its own
	// budget holds no tokens at all, whereas a call waiting for the shared budget holds a
	// token of its key throughout. Acquiring in the other order would let a single key occupy
	// the shared budget while waiting for room of its own.
	if c.currentLimit() > 0 {
		sem := c.getConcurrencyLimit(limitingKey)
		defer c.putConcurrencyLimit(limitingKey)

		release, err := acquire(ctx, sem, limitingKey)
		if err != nil {
			return nil, err
		}
		defer release()
	}

	if c.globalSem != nil {
		release, err := acquire(ctx, c.globalSem, GlobalLimitingKey)
		if err != nil {
			return nil, err
		}
		defer release()
	}

	return f()
}

// acquire takes a token from sem and returns the function that gives it back again. Both the wait
// and its outcome are reported to the monitor of sem, and a failure to acquire is translated into
// the error returned to the caller.
func acquire(ctx context.Context, sem *keyedConcurrencyLimiter, limitingKey string) (func(), error) {
	start := time.Now()

	if err := sem.acquire(ctx, limitingKey); err != nil {
		queueTime := time.Since(start)
		switch {
		case errors.Is(err, ErrMaxQueueSize):
			sem.monitor.Dropped(ctx, limitingKey, sem.queueLength(), sem.inProgress(), queueTime, "max_size")
			return nil, structerr.NewResourceExhausted("%w", ErrMaxQueueSize).WithDetail(&gitalypb.LimitError{
				ErrorMessage: err.Error(),
				RetryAfter:   durationpb.New(0),
			})
		case errors.Is(err, ErrMaxQueueTime):
			sem.monitor.Dropped(ctx, limitingKey, sem.queueLength(), sem.inProgress(), queueTime, "max_time")
			return nil, structerr.NewResourceExhausted("%w", ErrMaxQueueTime).WithDetail(&gitalypb.LimitError{
				ErrorMessage: err.Error(),
				RetryAfter:   durationpb.New(0),
			})
		default:
			sem.monitor.Dropped(ctx, limitingKey, sem.queueLength(), sem.inProgress(), queueTime, "other")
			return nil, fmt.Errorf("unexpected error when dequeueing request: %w", err)
		}
	}

	sem.monitor.Enter(ctx, sem.inProgress(), time.Since(start))

	return func() {
		sem.monitor.Exit(ctx)
		sem.release()
	}, nil
}

// getConcurrencyLimit retrieves the concurrency limit for the given key. If no such limiter exists
// it will be lazily constructed.
func (c *ConcurrencyLimiter) getConcurrencyLimit(limitingKey string) *keyedConcurrencyLimiter {
	c.m.Lock()
	defer c.m.Unlock()

	if c.limitsByKey[limitingKey] == nil {
		// Set up the queue tokens in case a maximum queue length was requested. As the
		// queue tokens are kept during the whole lifetime of the concurrency-limited
		// function we add the concurrency tokens to the number of available token.
		var queueTokens semaphorer
		if c.maxQueueLength > 0 {
			queueTokens = c.createSemaphore(uint(c.currentLimit() + c.maxQueueLength))
		}

		c.limitsByKey[limitingKey] = &keyedConcurrencyLimiter{
			monitor:               c.monitor,
			maxQueueWait:          c.maxQueueWait,
			setWaitTimeoutContext: c.SetWaitTimeoutContext,
			concurrencyTokens:     c.createSemaphore(uint(c.currentLimit())),
			queueTokens:           queueTokens,
		}
	}

	c.limitsByKey[limitingKey].refcount++

	return c.limitsByKey[limitingKey]
}

// putConcurrencyLimit drops the reference to the concurrency limit identified by the given key.
// This must only ever be called after `getConcurrencyLimit()` for the same key. If the reference
// count of the concurrency limit drops to zero then it will be destroyed.
func (c *ConcurrencyLimiter) putConcurrencyLimit(limitingKey string) {
	c.m.Lock()
	defer c.m.Unlock()

	ref := c.limitsByKey[limitingKey]
	if ref == nil {
		panic("semaphore should be in the map")
	}

	if ref.refcount <= 0 {
		panic(fmt.Sprintf("bad semaphore ref refcount %d", ref.refcount))
	}

	ref.refcount--
	if ref.refcount == 0 {
		delete(c.limitsByKey, limitingKey)
	}
}

func (c *ConcurrencyLimiter) countSemaphores() int {
	c.m.RLock()
	defer c.m.RUnlock()

	return len(c.limitsByKey)
}

func (c *ConcurrencyLimiter) currentLimit() int {
	return c.limit.Current()
}

func (c *ConcurrencyLimiter) createSemaphore(size uint) semaphorer {
	return NewResizableSemaphore(size)
}