Нужен потокобезопасный кеш строк по заданному интерфейсу. Под нагрузкой один
мьютекс на всю карту становится узким местом, поэтому данные делятся на
партиции (шарды), у каждой своя блокировка.
type ShardedCache interface {
Set(k, v string)
Get(k string) (v string, ok bool)
}
// NewSharded создаёт кеш из shards партиций (shards < 1 считается как 1).
func NewSharded(shards int) *Sharded
func (c *Sharded) Set(k, v string)
func (c *Sharded) Get(k string) (v string, ok bool)
func (c *Sharded) Delete(k string)
func (c *Sharded) Len() int
// ShardIndex — номер партиции, в которой живёт ключ k, в диапазоне [0, shards).
func (c *Sharded) ShardIndex(k string) int
Требования
Set добавляет или перезаписывает значение, Get возвращает его, Delete
удаляет (удаление отсутствующего ключа ничего не делает), Len — число
записей.- Ключ всегда попадает в партицию
ShardIndex(k). Индекс детерминирован в
пределах одного кеша и лежит в [0, shards). Ключи распределяются по
партициям равномерно: на 16 партиций и 16 000 разных ключей ни одна
партиция не получает меньше 500 или больше 1500.
- У каждой партиции своя блокировка. Чтения одной партиции не мешают друг другу
(
RWMutex), а операции над разными партициями друг друга не ждут.
- Код проходит
go test -race, только стандартная библиотека.
Пример
c := NewSharded(16)
c.Set("alice", "alice@example.com")
c.Get("alice") // "alice@example.com", true
c.Delete("alice")
c.Get("alice") // "", false
// NewShardedTTL — то же, но запись живёт ttl с момента последнего Set (ttl <= 0 — вечно).
// now — источник времени; nil означает time.Now.
func NewShardedTTL(shards int, ttl time.Duration, now func() time.Time) *Sharded
// DeleteExpired физически удаляет истёкшие записи и возвращает, сколько удалено.
func (c *Sharded) DeleteExpired() int
- Запись, у которой с момента последнего
Set прошло ttl или больше, для Get
и Len не существует, даже если физически ещё лежит в памяти.
- Повторный
Set продлевает жизнь записи.
DeleteExpired проходит по партициям по очереди и не блокирует весь кеш
целиком.
Устно: чтение ~70 000 RPS, запись ~4 000 RPS. Сколько партиций взять и
почему? Как выбрать хеш и почему число партиций часто берут степенью двойки?
Сколько памяти займёт кеш на 10 млн пар «логин → email» и как его прогревать?
Какие ещё есть способы инвалидации, кроме TTL?