Реализуйте потокобезопасную map, разбитую на 32 шарда. Один мьютекс на всю map
становится узким местом: горутины, работающие с разными ключами, всё равно стоят
в одной очереди. Если у каждого шарда свой мьютекс, они друг другу не мешают.
type ShardedMap struct {
// 32 шарда, у каждого свой RWMutex
}
func NewShardedMap() *ShardedMap
func (m *ShardedMap) Set(key string, value interface{})
func (m *ShardedMap) Get(key string) (interface{}, bool)
func (m *ShardedMap) Delete(key string)
func (m *ShardedMap) Len() int
Номер шарда выбирается по хешу ключа (например, FNV-1a): один ключ всегда
попадает в один и тот же шард. Каждый шард защищён своим sync.RWMutex: чтение
берёт RLock, запись и удаление берут Lock.
m := NewShardedMap()
m.Set("a", 1)
m.Set("b", "two")
m.Set("a", 99) // перезапись
v, ok := m.Get("a") // 99, true
_, ok2 := m.Get("nope") // nil, false
fmt.Println(v, ok, ok2, m.Len()) // 99 true false 2
m.Delete("a")
m.Delete("a") // удаление отсутствующего ключа безвредно
fmt.Println(m.Len()) // 1
Len() возвращает число пар во всех шардах вместе.
- Базовое поведение:
Get отсутствующего ключа даёт ok == false, перезапись
меняет значение, Delete убирает ключ, Len это отражает.
- 1000 разных ключей записываются, все читаются обратно,
Len() == 1000.
- 64 горутины по 500 раз делают
Set, Get и (для чётных i) Delete
на своих ключах. В конце Len() равен 16000, а каждый Get сразу после
своего Set видел записанное.
- 32 горутины пишут и читают общие 50 ключей, в конце
Len() == 50.
nil как значение это нормальная запись (Get вернёт nil, true); Delete отсутствующего ключа и перезапись не меняют Len неверно.Len() вызывается параллельно с записью без гонок.- Всё идёт под детектором гонок (
-race).
Тесты не проверяют, что шардов именно 32 и что ключи действительно
расходятся по ним. Это часть условия и предмет вопросов интервьюера.
На что смотрит интервьюер: почему шардирование снижает контеншен, чем
заканчивается Get под Lock вместо RLock, не забыта ли инициализация
внутренних map, как честно посчитан Len.