去比赛检测器错误

Question

Here's my code for a concurrent cache:

package cache

import (
    "sync"
)

// Func represents a memoizable function, operating on a string key, to use with a Cache
type Func func(key string) (interface{}, error)

// FuncResult stores the value of a Func call
type FuncResult struct {
    val interface{}
    err error
}

// Cache is a cache that memoizes results of an expensive computation
//
// It has a traditional implementation using mutexes.
type Cache struct {
    // guards done
    mu   sync.RWMutex
    done map[string]chan bool
    memo map[string]*FuncResult
    f    Func
}

// New creates a new Cache and returns its pointer
func New(f Func) *Cache {
    return &Cache{
        memo: make(map[string]*FuncResult),
        done: make(map[string]chan bool),
        f:    f,
    }
}

// Get a string key if it exists, otherwise computes the value and caches it.
//
// Returns the value and whether or not the key existed.
func (c *Cache) Get(key string) (*FuncResult, bool) {
    c.mu.RLock()
    _, ok := c.done[key]
    c.mu.RUnlock()
    if ok {
        return c.get(key), true
    }

    c.mu.Lock()
    _, ok = c.done[key]
    if ok {
        c.mu.Unlock()
    } else {
        c.done[key] = make(chan bool)
        c.mu.Unlock()

        v, err := c.f(key)
        c.memo[key] = &FuncResult{v, err}

        close(c.done[key])
    }
    return c.get(key), ok
}

// get returns the value of key, blocking on an existing computation
func (c *Cache) get(key string) *FuncResult {
    <-c.done[key]
    fresult, _ := c.memo[key]
    return fresult
}

When I run this program with the race detector, I get no errors:

package main

import (
    "fmt"
    "log"
    "sync"
    "time"

    "github.com/yangmillstheory/go-cache/cache"
)

var f = func(key string) (interface{}, error) {
    log.Printf("Computing value for key %s
", key)
    time.Sleep(1000 * time.Millisecond)
    return fmt.Sprintf("value for %s", key), nil
}

func main() {
    var wg sync.WaitGroup

    c := cache.New(f)
    n := 10
    k := "key1"

    start := time.Now()
    for i := 0; i < n; i++ {
        wg.Add(1)
        go func() {
            defer wg.Done()
            c.Get(k)
        }()
    }

    wg.Wait()
    log.Printf("Elapsed: %s
", time.Since(start))
}

However, when I launch two different goroutines within the loop body each getting a different keys, I get an error:

The way to fix this is to add another mutex c.nu to guard memo, but it makes the program a bit slower, and more complex

func (c *Cache) Get(key string) (*FuncResult, bool) {
    c.mu.RLock()
    _, ok := c.done[key]
    c.mu.RUnlock()
    if ok {
        return c.get(key), true
    }

    c.mu.Lock()
    _, ok = c.done[key]
    if ok {
        c.mu.Unlock()
    } else {
        c.done[key] = make(chan bool)
        c.mu.Unlock()

        v, err := c.f(key)
        c.nu.Lock()
        c.memo[key] = &FuncResult{v, err}
        c.nu.Unlock()

        close(c.done[key])
    }
    return c.get(key), ok
}

// get returns the value of key, blocking on an existing computation
func (c *Cache) get(key string) *FuncResult {
    <-c.done[key]
    c.nu.RLock()
    fresult, _ := c.memo[key]
    c.nu.RUnlock()
    return fresult
}

Is there in fact a race condition here to worry about? If different goroutines are accessing different keys in the same data structure concurrently, it doesn't seem like it should be an issue as long as synchronization happens within an access for a given key?

Put another way, do you have to synchronization across all keys, or just across the same key? The use case for a concurrent memo seems to suggest the latter would suffice?

Answer 1

maps require synchronization, in particular you can not read it while writing to it, regardless of if it's the same or distinct keys, so you need your lock around the meno map.