Building a Thread-Safe Cache in Go

Concurrency is a fundamental aspect of modern software development, and Go excels at it with its goroutines and channels. However, when multiple goroutines access shared data, race conditions can occur, leading to unpredictable behavior and bugs. This challenge will test your understanding of Go's synchronization primitives by requiring you to implement a thread-safe cache.

Problem Description

Your task is to create a generic, thread-safe cache data structure in Go. This cache should support basic operations like Set (adding or updating a key-value pair), Get (retrieving a value by key), and Delete (removing a key-value pair). The primary requirement is that all these operations must be safe to call concurrently from multiple goroutines without introducing data races.

Key Requirements:

• Thread-Safety: All methods (Set, Get, Delete) must be callable from multiple goroutines simultaneously without data corruption or race conditions.
• Genericity: The cache should be able to store and retrieve values of any type. You can use Go's generics for this.
• Key Type: Keys should be comparable (e.g., strings, integers).
• Eviction (Optional but Recommended): Consider how you might handle a cache that grows indefinitely. For this challenge, a simple unlimited cache is acceptable, but thinking about eviction strategies is a good exercise.

Expected Behavior:

• Set(key K, value V): Stores value associated with key. If key already exists, its value should be updated.
• Get(key K) (V, bool): Returns the value associated with key and a boolean indicating whether the key was found. If the key is not found, it should return the zero value of V and false.
• Delete(key K): Removes the key-value pair associated with key if it exists.

Edge Cases:

• Accessing a cache with no elements.
• Concurrent Set, Get, and Delete operations on the same key.
• Concurrent operations on different keys.

Examples

Example 1: Basic Usage

cache := NewCache[string, int]() // Assuming NewCache is your constructor

// Goroutine 1
go func() {
    cache.Set("apple", 1)
    cache.Set("banana", 2)
}()

// Goroutine 2
go func() {
    val, ok := cache.Get("apple")
    if ok {
        fmt.Printf("Got apple: %d\n", val) // Expected: Got apple: 1
    }
    cache.Delete("banana")
}()

// Allow goroutines to finish (in a real test, use sync.WaitGroup)
time.Sleep(100 * time.Millisecond)

val, ok := cache.Get("banana")
if !ok {
    fmt.Println("Banana not found") // Expected: Banana not found
}

Explanation: This example demonstrates concurrent setting and getting of values, followed by deleting a key. The expectation is that apple is retrieved correctly, and banana is successfully deleted.

Example 2: Concurrent Updates and Deletes

cache := NewCache[string, int]()

// Start multiple goroutines performing operations
var wg sync.WaitGroup
for i := 0; i < 100; i++ {
    wg.Add(1)
    go func(id int) {
        defer wg.Done()
        cache.Set(fmt.Sprintf("key%d", id), id)
        if id%2 == 0 {
            cache.Delete(fmt.Sprintf("key%d", id-1)) // Delete previous key if exists
        }
    }(i)
}
wg.Wait()

// Verify some values
for i := 0; i < 100; i++ {
    val, ok := cache.Get(fmt.Sprintf("key%d", i))
    if i%2 != 0 { // Odd keys should generally be present (unless overwritten by a later Set)
        if ok {
            fmt.Printf("Key %d found with value %d\n", i, val)
        } else {
            fmt.Printf("Key %d not found\n", i)
        }
    } else { // Even keys should have been deleted by the next goroutine
        if !ok {
            fmt.Printf("Key %d correctly deleted\n", i)
        } else {
            fmt.Printf("Key %d unexpectedly found\n", i)
        }
    }
}

Explanation: This example stresses the cache with many concurrent Set and Delete operations. The goal is to ensure that even with rapid, interleaved operations, the cache remains consistent. For example, an even-numbered key keyX is set, and then immediately after, keyX-1 (which would be an odd number) is potentially deleted by the next goroutine. The verification checks that expected keys are present or absent.

Constraints

• The cache implementation must not use sync.Map from the standard library. You should implement the synchronization mechanism yourself using lower-level primitives.
• The cache can store an unbounded number of elements (no explicit size limit or eviction policy required for this challenge).
• Keys must be of a type that supports comparison (i.e., implement the comparable constraint).
• Values can be of any type.
• The solution should be reasonably efficient; avoid excessive locking that would serialize all operations unnecessarily.

Notes

• Consider Go's built-in synchronization primitives like sync.Mutex or sync.RWMutex. Which one is more appropriate for a cache and why?
• Think about how to protect the underlying data structure (e.g., a map) from concurrent access.
• Go's generics are a powerful tool for creating reusable, type-safe data structures. You'll need to define your Cache type with type parameters for keys and values.
• For testing the thread-safety, you will want to use sync.WaitGroup to ensure all goroutines have completed their work before checking the final state of the cache.