Как реализовать шардирование кэша

Что проверяют

Различаете ли вы два смысла вопроса: шардирование внутри процесса ради снижения конкуренции за мьютекс и шардирование между узлами ради объёма и нагрузки. Уточнить, о каком речь, уже плюс. Следом почти всегда спрашивают, что будет при добавлении узла.

Как отвечать

Внутри одного процесса:

• зачем: один sync.RWMutex на всю map становится узким местом при десятках горутин. Кеш делят на N шардов со своей map и своим мьютексом, и операции с разными ключами почти не мешают друг другу;
• выбор шарда: хеш ключа по модулю числа шардов. Число шардов удобно брать степенью двойки и считать индекс маской h & (n-1). Хеш берут из hash/maphash или FNV-1a из hash/fnv, криптография не нужна;
• вытеснение: у каждого шарда свой LRU или TTL, шардирование не отменяет лимит памяти;
• GC: при миллионах записей с указателями сборщик тратит время на обход map. Поэтому bigcache хранит значения в больших байтовых срезах, а в map держит только смещения без указателей;
• сначала замер: бенчмарк с -cpu и профиль блокировок покажут, есть ли конкуренция вообще. sync.Map это не шардирование, он хорош для ключей, которые пишутся один раз и много читаются.

Между узлами:

• простой модуль ломается: при hash % N смена N переносит почти все ключи, кеш разом пустеет, и нагрузка падает на базу;
• консистентное хеширование: кольцо с виртуальными узлами, при добавлении узла переезжает примерно 1/N ключей. Альтернатива: rendezvous hashing;
• Redis Cluster: 16384 слота, слот считается как CRC16 от ключа, а хеш-теги в фигурных скобках вроде {user:42} кладут связанные ключи в один слот.

Где спотыкаются

Говорят, что шардирование «снижает коллизии». Коллизии хеша тут ни при чём, выигрыш в меньшей конкуренции за блокировку и в распределении объёма.

Забывают про горячий ключ: весь трафик популярного ключа всё равно идёт в один шард. Помогает локальный кеш поверх общего или реплики ключа.

Делают шардированный кеш без лимита. Доступ стал быстрее, но память растёт, пока контейнер не убьют по OOM.