Нужно написать thread-safe структуру данных с методами:

• Get(k string) interface{},
• Put(k string, v interface{})
• Delete(k string)
• ForEach(f func(v interface{}))

Можно ли как-нибудь спровоцировать data race в такой сигнатуре, где хотя бы одно обращение будет из имплементации? А если гарантировать, что под интерфейсами нет указателей? Далее независимые усложнения, модифицирующие код:

• Оптимизация под чтение
• Оптимизация под запись (интересная часть)
• (Бонус) Если число записей конечно, можно ли решить лучше?

Для начала хватит наивной реализации, использующей обычный мьютекс c мапой. Можно ли как-нибудь спровоцировать data race в такой сигнатуре, где хотя бы одно обращение будет из имплементации?

Ответ - да, например, если в значение мы положили указатель, потом меняем его извне и в ForEach . При этом если под интерфейсами не лежит ни одного указателя, то нельзя.

• Оптимизация под чтение - использование sync.RWMutex
• Оптимизация под запись - шардирование.

Нужно выбрать подходящий хэш (главное быстрый, совсем не обязательно криптографический, в последних версиях го добавили пакет со стандартным хэшом мапы). Они используются не так часто, чтобы помнить все сигнатуры, так что не вижу смысла снижать оценку.

Если хэш хранит стейт и имеет метод Reset() (для переиспользования аллоцированной памяти), то можно ли переиспользовать структуру?

Ответ - да, проще и быстрее всего использовать sync.Pool - встроенная имплементация hazard pointers

Нужно ли гарантировать, что никто не будет записывать в другие шарды, пока идем через ForEach? Нет, так как либо тот, кто использует структуру упорядочивает Put (или Delete ) и ForEach через happens before, либо не имеет гарантии, что произойдет сначала, не используя время (что скорее всего плохая попытка упорядочить)

код примерно такой, некоторые детали можно опустить

 package main

import (
	"hash/maphash"
	"sync"
)


type Map struct {
	seed     maphash.Seed
	hashPool sync.Pool
	lock     sync.RWMutex
	buckets []*Bucket
}


type Bucket struct {
	mp   map[string]interface{}
	lock sync.RWMutex
}


func NewMap(numBuckets int) *Map {
	seed := maphash.MakeSeed()
	buckets := make([]*Bucket, numBuckets)
	for i := range buckets {
		buckets[i] = &Bucket{
			mp: make(map[string]interface{}),
		}
	}


	return &Map{
		buckets: buckets,
		hashPool: sync.Pool{
			New: func() interface{} {
				var hash maphash.Hash
				hash.SetSeed(seed)
				return &hash
			},
		},
	}
}

func (m *Map) Get(k string) interface{} {
	bucket := m.getBucketForKey(k)
	bucket.lock.RLock()
	defer bucket.lock.RUnlock()
	return bucket.mp[k]
}


func (m *Map) Put(k string, v interface{}) {
	bucket := m.getBucketForKey(k)
	bucket.lock.Lock()
	defer bucket.lock.Unlock()
	bucket.mp[k] = v
}


func (m *Map) Delete(k string) {
	bucket := m.getBucketForKey(k)
	bucket.lock.Lock()
	defer bucket.lock.Unlock()
	delete(bucket.mp, k)
}


func (m *Map) ForEach(f func(v interface{})) {
	for _, bucket := range m.buckets {
		bucket.lock.RLock()
		for _, v := range bucket.mp {
			f(v)
		}
		bucket.lock.RUnlock()
	}
}


func (m *Map) keyHash(k string) uint64 {
	hash := m.hashPool.Get().(*maphash.Hash)
	defer m.hashPool.Put(hash)
	_, _ = hash.WriteString(k)
	key := hash.Sum64()
	hash.Reset()
	return key
}


func (m *Map) getBucketForKey(k string) *Bucket {
	keyHash := m.keyHash(k)
	return m.buckets[keyHash%uint64(len(m.buckets))]
}

(Бонус) Если число записей конечно, можно ли решить лучше?

sync.Map предназначен для этой цели, хотя конечно нужно проверять через бенчмарки.