Skip to content

Git designed for AI agents.

9.7 KB
Raw Blame
package mvcc

import (
	"context"
	"sync"
	"sync/atomic"
	"testing"
	"time"

	"github.com/stretchr/testify/require"
)

// cacheLen reports the number of entries currently held by the keyedRunner.
func cacheLen[K comparable](c *KeyedRunnerCache[K]) int {
	c.mu.Lock()
	defer c.mu.Unlock()
	return len(c.items)
}

// waitForConsumers blocks until the entry for key has exactly want consumers. It
// is used to deterministically wait for followers to attach to a leader's
// in-flight work before letting the work complete.
func waitForConsumers[K comparable](t *testing.T, c *KeyedRunnerCache[K], key K, want int) {
	t.Helper()
	require.Eventually(t, func() bool {
		c.mu.Lock()
		defer c.mu.Unlock()
		item, ok := c.items[key]
		return ok && item.consumers == want
	}, time.Second, time.Millisecond)
}

func TestKeyedRunnerCache_RunsWorkOnceAndEvictsEntry(t *testing.T) {
	t.Parallel()

	c := NewKeyedRunnerCache[string]()

	var runCount int32
	do := func(context.Context) error {
		atomic.AddInt32(&runCount, 1)
		return nil
	}

	require.NoError(t, c.Run(context.Background(), "key", do))
	require.Equal(t, int32(1), atomic.LoadInt32(&runCount))

	// The caller's reference is dropped when Run returns, so the completed entry
	// is evicted without the caller having to do anything.
	require.Equal(t, 0, cacheLen(c))
}

func TestKeyedRunnerCache_CoalescesConcurrentCallers(t *testing.T) {
	t.Parallel()

	c := NewKeyedRunnerCache[string]()

	started := make(chan struct{}, 1)
	proceed := make(chan struct{})

	// This value should be set to 1, as we expect `do` to
	// be run only once no matter how many callers
	var runCount int32
	do := func(context.Context) error {
		atomic.AddInt32(&runCount, 1)
		started <- struct{}{}
		<-proceed
		return nil
	}

	// One caller becomes the leader and starts the work; the rest attach to it.
	const callers = 6
	errs := make([]error, callers)
	var wg sync.WaitGroup
	for i := range callers {
		wg.Add(1)
		go func(i int) {
			defer wg.Done()
			errs[i] = c.Run(context.Background(), "key", do)
		}(i)
	}

	// The work started, and every caller attached to the single entry.
	<-started
	waitForConsumers(t, c, "key", callers)
	require.Equal(t, 1, cacheLen(c))

	// Let the work finish; every caller observes success.
	close(proceed)

	// This code block here is a way to wait for the WaitGroup to unblock
	// while timing out after 1 second just in case, to avoid hanging the
	// tests unnecessarily.
	{
		done := make(chan struct{})
		go func() {
			defer close(done)
			wg.Wait()
		}()

		select {
		case <-done:
		case <-time.After(time.Second):
			t.Fatal("timed out waiting for callers")
		}
	}

	// Validate the `op` only run once
	require.Equal(t, int32(1), atomic.LoadInt32(&runCount))

	// Validate the results of every caller
	for i := range callers {
		require.NoError(t, errs[i], "caller %d", i)
	}

	// Every caller dropped its reference on return, so the entry is gone.
	require.Equal(t, 0, cacheLen(c))
}

func TestKeyedRunnerCache_WorkContinuesAfterCallerCanceled(t *testing.T) {
	t.Parallel()

	c := NewKeyedRunnerCache[string]()

	started := make(chan struct{}, 1)
	proceed := make(chan struct{})
	finished := make(chan struct{})

	var runCount int32
	do := func(ctx context.Context) error {
		atomic.AddInt32(&runCount, 1)
		started <- struct{}{}
		<-proceed
		close(finished)
		return nil
	}

	leaderCtx, cancelLeader := context.WithCancel(context.Background())

	// The leader (first caller for the key) runs an operation in the cache
	leaderCh := make(chan error, 1)
	go func() {
		leaderCh <- c.Run(leaderCtx, "key", do)
	}()

	// Wait for the `do` to start
	<-started

	// A follower with a live context attaches to the in-flight work.
	followerCh := make(chan error, 1)
	go func() {
		followerCh <- c.Run(context.Background(), "key", do)
	}()

	// Here we wait to have 2 consumers of the item:
	// 1. The leader
	// 2. The follower
	waitForConsumers(t, c, "key", 2)

	// Cancel the leader. It stops waiting and observes its context error, but the
	// background work keeps running.
	cancelLeader()
	require.ErrorIs(t, <-leaderCh, ErrTimeoutWaitingOnFetch)

	// The leader dropped its reference when Run returned, but the follower still
	// holds one so the entry stays in the cache.
	waitForConsumers(t, c, "key", 1)
	require.Equal(t, 1, cacheLen(c))

	// The follower is still waiting: the work has not been abandoned.
	select {
	case <-followerCh:
		t.Fatal("follower returned before the work finished")
	case <-time.After(100 * time.Millisecond):
		// This case should trigger, because the followerCh should not return yet
		// since the work for `op` is not done yet.
	}

	// Let the work finish.  This unblocks `op` and runs it to completion.
	close(proceed)
	select {
	case <-finished:
	case <-time.After(time.Second):
		t.Fatal("background work did not finish after the leader was canceled")
	}

	// ...and the follower observes the successful result.
	require.NoError(t, <-followerCh)

	require.Equal(t, int32(1), atomic.LoadInt32(&runCount))
	require.Equal(t, 0, cacheLen(c))
}

func TestKeyedRunnerCache_DifferentKeysDoNotCoalesce(t *testing.T) {
	t.Parallel()

	c := NewKeyedRunnerCache[string]()

	started := make(chan struct{}, 2)
	proceed := make(chan struct{})

	var runCount int32
	do := func(context.Context) error {
		atomic.AddInt32(&runCount, 1)
		started <- struct{}{}
		<-proceed
		return nil
	}

	// Each key gets its own execution of the work.
	errs := make([]error, 2)
	var wg sync.WaitGroup
	for i, key := range []string{"a", "b"} {
		wg.Add(1)
		go func() {
			defer wg.Done()
			errs[i] = c.Run(context.Background(), key, do)
		}()
	}

	// Both operations are in flight at the same time, each with its own entry.
	<-started
	<-started
	require.Equal(t, 2, cacheLen(c))

	close(proceed)
	wg.Wait()

	require.NoError(t, errs[0])
	require.NoError(t, errs[1])
	require.Equal(t, int32(2), atomic.LoadInt32(&runCount))
	require.Equal(t, 0, cacheLen(c))
}

func TestKeyedRunnerCache_RunAfterCompletionRunsAgain(t *testing.T) {
	t.Parallel()

	c := NewKeyedRunnerCache[string]()
	var runCount int32
	do := func(context.Context) error {
		atomic.AddInt32(&runCount, 1)
		return nil
	}

	require.NoError(t, c.Run(context.Background(), "key", do))
	require.Equal(t, 0, cacheLen(c))

	// The entry is gone, so running for the same key again triggers a fresh
	// execution.
	require.NoError(t, c.Run(context.Background(), "key", do))
	require.Equal(t, int32(2), atomic.LoadInt32(&runCount))
	require.Equal(t, 0, cacheLen(c))
}

func TestKeyedRunnerCache_RecoversPanicFromWork(t *testing.T) {
	t.Parallel()

	c := NewKeyedRunnerCache[string]()

	started := make(chan struct{}, 1)
	proceed := make(chan struct{})

	var runCount int32
	do := func(context.Context) error {
		atomic.AddInt32(&runCount, 1)
		started <- struct{}{}
		<-proceed
		panic("boom")
	}

	// The leader runs the panicking work, a follower attaches to it. Both must
	// observe the recovered panic as an error rather than crashing the process.
	leaderCh := make(chan error, 1)
	go func() {
		leaderCh <- c.Run(context.Background(), "key", do)
	}()

	<-started

	followerCh := make(chan error, 1)
	go func() {
		followerCh <- c.Run(context.Background(), "key", do)
	}()

	waitForConsumers(t, c, "key", 2)

	close(proceed)

	expectedErr := "KeyedRunnerCache.run: panic recovered: boom"
	require.EqualError(t, <-leaderCh, expectedErr)
	require.EqualError(t, <-followerCh, expectedErr)

	// The work ran only once, and the failed entry was discarded so a later call
	// for the same key starts fresh.
	require.Equal(t, int32(1), atomic.LoadInt32(&runCount))
	require.Equal(t, 0, cacheLen(c))
}

func TestKeyedRunnerCache_Drain(t *testing.T) {
	t.Parallel()

	t.Run("empty cache", func(t *testing.T) {
		t.Parallel()

		c := NewKeyedRunnerCache[string]()

		// Draining an empty cache is a no-op, and the cache stays usable.
		c.Drain()
		require.Equal(t, 0, cacheLen(c))

		require.NoError(t, c.Run(context.Background(), "key", func(context.Context) error {
			return nil
		}))
	})

	t.Run("cancels in-flight work and evicts entries", func(t *testing.T) {
		t.Parallel()

		c := NewKeyedRunnerCache[string]()

		keys := []string{"a", "b", "c"}

		started := make(chan struct{}, len(keys))

		var runCount int32
		// The work only returns once its own context is canceled, so the only way
		// for the callers below to return is for Drain to cancel it.
		do := func(ctx context.Context) error {
			atomic.AddInt32(&runCount, 1)
			started <- struct{}{}

			// The context gets canceled with calling Drain()
			<-ctx.Done()
			return ctx.Err()
		}

		// Execute one operation per key in keys
		errs := make([]error, len(keys))
		var wg sync.WaitGroup
		for i, key := range keys {
			wg.Add(1)
			go func() {
				defer wg.Done()
				errs[i] = c.Run(context.Background(), key, do)
			}()
		}

		// Every key has its work in flight and its own entry in the cache.
		for range keys {
			<-started
		}
		require.Equal(t, len(keys), cacheLen(c))

		// This should cancel all in-flight operations
		c.Drain()

		// The entries are gone right away, without waiting for the canceled work
		// to unwind.
		require.Equal(t, 0, cacheLen(c))

		wg.Wait()

		// Each caller observes the cancellation of its operation's context. Note
		// that this is the operation's error, not ErrTimeoutWaitingOnFetch: the
		// callers' own contexts are still live.
		for i, key := range keys {
			require.ErrorIs(t, errs[i], context.Canceled, "caller for key %q", key)
			require.NotErrorIs(t, errs[i], ErrTimeoutWaitingOnFetch, "caller for key %q", key)
		}
		require.Equal(t, int32(len(keys)), atomic.LoadInt32(&runCount))

		// The drained entries were discarded, so the cache is still usable and a
		// call for a drained key triggers a fresh execution.
		require.NoError(t, c.Run(context.Background(), keys[0], func(context.Context) error {
			return nil
		}))
		require.Equal(t, 0, cacheLen(c))
	})
}