Зачем вообще «потокобезопасные» структуры

Представьте обычную хеш-таблицу (map) или счётчик. Пока к ним лезет один поток — всё хорошо. Но как только два потока (или две горутины на разных ядрах) начинают одновременно читать и писать, начинается хаос: один читает значение, второй в этот момент его меняет, третий видит наполовину обновлённое состояние. Получаем race condition (гонку) — баг, который воспроизводится раз в неделю в проде и никогда на твоей машине.

Потокобезопасная (thread-safe) структура — это структура данных, которой можно безопасно пользоваться из нескольких потоков сразу, не получая порчи данных.

Самый прямой способ сделать структуру потокобезопасной — обернуть её мьютексом (mutex, «замок»: кто захватил — тот один внутри, остальные ждут). Про мьютекс как устройство мы говорили в главе locks-hardware, а как API в Go — в курсе sync-primitives. Здесь вопрос глубже: мьютекс — это правильно, но часто медленно, и важно понимать почему.

   Наивная потокобезопасная map:
 
   ┌──────────────────────────────┐
   │  type SafeMap struct {       │
   │      mu  sync.Mutex          │   ← один замок на ВСЮ структуру
   │      m   map[K]V             │
   │  }                           │
   └──────────────────────────────┘
 
   Get/Set:  mu.Lock() → работаем → mu.Unlock()

«Что нарисовано»: один общий замок защищает всю таблицу. Любая операция, даже чтение одного ключа, должна сначала захватить этот замок целиком.

Проблема: contention (борьба за замок)

Contention (контеншн, «состязание») — это ситуация, когда много потоков хотят один и тот же замок одновременно, и большинство просто стоит в очереди, ничего не делая. Чем больше ядер у сервера, тем хуже: 32 ядра дерутся за один мьютекс — и 31 из них простаивает. Параллельности нет, хотя процессоров полно.

   ОДИН БОЛЬШОЙ ЛОК (global lock)
 
   ядро0 ──┐
   ядро1 ──┤
   ядро2 ──┼──►  [ MUTEX ]  ──►  данные
   ядро3 ──┘        ▲
                    │
            только ОДИН проходит,
            остальные ждут (spin/sleep)

«Что нарисовано»: бутылочное горлышко. Сколько бы ядер ни было, в каждый момент работает одно. Это называют сериализацией — параллельный код выродился в последовательный.

Гранулярность блокировок: striped / sharded locks

Решение — не один замок на всё, а много замков на части. Это называется гранулярность блокировки (lock granularity): крупная гранулярность = один лок на всё (просто, но contention); мелкая = много мелких локов (сложнее, но потоки реже сталкиваются).

Приём striped locks (полосатые/секционные локи), он же sharding: делим структуру на N независимых кусков (шардов), у каждого свой замок. Ключ попадает в шард по хешу. Два потока, работающие с разными ключами, скорее всего попадут в разные шарды — и не столкнутся вообще.

   STRIPED LOCKS (16 шардов)
 
   ключ "user:42"  ─hash%16─►  shard[5]   [lock5][bucket5]
   ключ "order:7"  ─hash%16─►  shard[12]  [lock12][bucket12]
 
   ┌───────┬───────┬───────┬─────┬────────┐
   │shard0 │shard1 │shard2 │ ... │shard15 │
   │[lock] │[lock] │[lock] │     │[lock]  │
   └───────┴───────┴───────┴─────┴────────┘
        ▲       ▲
     ядро0   ядро1   ← работают ПАРАЛЛЕЛЬНО, локи разные

«Что нарисовано»: вместо одного замка — 16 независимых. Потоки, попавшие в разные шарды, не мешают друг другу. Это даёт почти линейный рост с числом ядер, пока ключи распределены равномерно.

Lock-free: CAS-цикл вместо замка

Можно вообще без замка? Иногда да — через атомарную операцию CAS.

CAS (Compare-And-Swap, «сравни-и-поменяй») — это одна машинная инструкция, которую процессор выполняет неделимо (атомарно). Смысл: «сравни значение в памяти с тем, что я ожидаю; если совпало — запиши новое и верни успех; если кто-то успел поменять — верни неудачу, ничего не трогая». Подробно про атомики — в atomic.

Бытовая аналогия: ты редактируешь Google-документ. CAS — это «сохрани, только если с момента, когда я открыл, никто другой не сохранял; иначе скажи мне, и я перечитаю и попробую снова».

На CAS строят lock-free счётчик: читаем текущее значение, считаем новое, пытаемся записать через CAS. Если не вышло (кто-то опередил) — повторяем цикл.

   CAS-RETRY ЦИКЛ (инкремент счётчика)
 
   ┌─────────────────────────────────────────┐
   │ loop:                                    │
   │   old := atomic.Load(&cnt)   // прочитали│
   │   new := old + 1             // посчитали│
   │   if CAS(&cnt, old, new) {   // записали? │
   │        return    ──────────────► успех   │
   │   }                                      │
   │   // кто-то опередил → goto loop ◄──┐     │
   └────────────────────────────────────┘─────┘
 
   Поток A: old=5 new=6  CAS ok ✓
   Поток B: old=5 new=6  CAS fail ✗ (стало 6) → retry: old=6 new=7 ✓

«Что нарисовано»: цикл «прочитал → посчитал → попробовал записать». Если между чтением и записью кто-то вклинился, CAS проваливается и мы крутим цикл заново. Под капотом так работает atomic.AddInt64.

Чем это отличается от мьютекса:

• Мьютекс при провале усыпляет поток (планировщик переключает на другого).
• CAS-цикл не спит, он крутится и пробует снова (busy retry). При малой конкуренции это быстрее (нет похода в ядро), при большой — может жечь CPU впустую.

Важная ловушка lock-free — ABA-проблема: значение было A, кто-то поменял на B и обратно на A. Твой CAS видит A и думает «ничего не менялось», хотя на деле менялось дважды. Лечат счётчиками версий/тегами указателей. Для простого счётчика ABA не страшна, для стека на указателях — очень.

Барьеры памяти: почему «записал → другой увидел» не гарантировано

Вот коварная часть. Ты пишешь:

   Поток 1                 Поток 2
   data = 42               while ready == 0 {}   // ждём
   ready = 1               use(data)             // читаем

Кажется очевидным: раз ready==1, значит data уже 42. Нет. И процессор, и компилятор имеют право переупорядочить операции, если для одного потока результат не меняется. Поток 2 может увидеть ready==1, но data ещё старое.

Почему так происходит — две причины:

   ПЕРЕУПОРЯДОЧЕНИЕ (reordering)
 
   что написал программист:   data=42 ; ready=1
   ─────────────────────────────────────────────
   компилятор может выдать:    ready=1 ; data=42   (оптимизация)
   процессор может выполнить:  ready=1 ; data=42   (store buffer, OoO)
 
   Другое ядро видит порядок НЕ такой, как ты писал.

«Что нарисовано»: твой исходный порядок — не закон. Компилятор переставляет инструкции ради скорости; процессор откладывает записи в store buffer (буфер записи) и выполняет инструкции вне очереди (out-of-order). Для одного потока всё консистентно, но другое ядро видит «протёкший» порядок.

Барьер памяти (memory barrier / fence) — специальная инструкция, которая запрещает переупорядочивание через себя: «всё, что до барьера, завершится и станет видно раньше всего, что после». Это забор, через который операции не перепрыгивают.

   С БАРЬЕРОМ
 
   data = 42
   ─── BARRIER (store fence) ───   ← перелезать запрещено
   ready = 1
 
   Гарантия: увидел ready==1 ⇒ data уже 42

«Что нарисовано»: барьер фиксирует порядок. Запись data гарантированно видна до записи ready.

Связь с happens-before («происходит-до») — формальным правилом «если событие A happens-before B, то эффекты A видны в B». Барьеры — это механизм, которым happens-before реализуется на железе. В Go тебе обычно не нужно ставить барьеры руками: их вставляют атомики, мьютексы и каналы. mu.Unlock() в одном потоке happens-before mu.Lock() в другом — поэтому всё, что ты записал под локом, второй поток увидит. Подробно — в memory-model. Тут ключевая мысль: синхронизация нужна не только чтобы «не толкаться», но и чтобы записи стали видны другим ядрам в правильном порядке.

Аппаратная подоплёка: MESI и кэш-когерентность

Откуда вообще берётся видимость? У каждого ядра свой кэш (L1/L2) — быстрая локальная копия кусочков памяти. Память делится на кэш-линии (cache line), обычно 64 байта: это минимальная единица, которой ядра обмениваются.

Чтобы ядра не видели разные значения одной ячейки, они гоняют протокол когерентности MESI. Каждая кэш-линия в каждом ядре имеет одно из 4 состояний:

   MESI — состояния кэш-линии
 
   M (Modified)  — линия изменена ТОЛЬКО у меня, в памяти старьё.
   E (Exclusive) — линия только у меня, совпадает с памятью.
   S (Shared)    — линия у нескольких ядер, все читают, совпадает с памятью.
   I (Invalid)   — линия протухла, нельзя использовать.
 
   Ядро хочет ПИСАТЬ → должно получить линию в M:
     рассылает «Invalidate» всем → у других линия становится I
     ┌────────┐  invalidate   ┌────────┐
     │ ядро0  │ ────────────► │ ядро1  │
     │ line:M │               │ line:I │  (выкинул копию)
     └────────┘               └────────┘

«Что нарисовано»: чтобы записать в линию, ядро должно стать её единоличным владельцем (M) и аннулировать копии у всех остальных. Это сетевой трафик между ядрами. Чтение «протухшей» линии заставит ядро заново тянуть свежую копию.

False sharing: тихий убийца производительности

Теперь главный сюрприз. Линия — 64 байта. Если две независимые переменные (например, два счётчика, которые правят два разных ядра) случайно лежат в одной кэш-линии, то ядра дерутся за линию, хотя логически данные не пересекаются. Это и есть false sharing (ложное разделение).

   FALSE SHARING — одна линия (64 байта)
 
   ┌──────────────── cache line 64B ────────────────┐
   │ counterA(8B) │ counterB(8B) │ ...padding 48B... │
   └──────────────────────────────────────────────────┘
        ▲ ядро0 пишет       ▲ ядро1 пишет
 
   ядро0 пишет A → invalidate линии у ядра1
   ядро1 пишет B → invalidate линии у ядра0
   ... линия мечется туда-сюда (ping-pong), хотя A и B не связаны!

«Что нарисовано»: counterA и counterB логически независимы, но физически в одной линии. Каждая запись одного ядра аннулирует линию у другого. Линия «пинг-понгует» между кэшами — производительность падает в разы, а в коде «ничего подозрительного».

Лечение — padding (набивка): раздвигаем переменные так, чтобы каждая лежала в своей кэш-линии. Добавляем пустые байты-заполнители.

   ПОСЛЕ PADDING
 
   ┌──── line 0 (64B) ────┐  ┌──── line 1 (64B) ────┐
   │ counterA │ pad 56B   │  │ counterB │ pad 56B   │
   └──────────────────────┘  └──────────────────────┘
        ▲ ядро0                    ▲ ядро1
   разные линии → никаких взаимных invalidate, полный параллелизм

«Что нарисовано»: каждая переменная одна в своей линии. Записи ядер больше не конфликтуют. В Go это делают вставкой поля-набивки, например _ [56]byte, или выравнивают структуры по 64 байта (см. cpu.CacheLinePad в рантайме). Классика — шардированные счётчики/пулы: каждый шард паддят до целой линии.

Как это собрать вместе

• Начни с простого мьютекса — он корректен и понятен. Не усложняй, пока профайлер не покажет contention.
• Видишь горячий лок — переходи на striping/sharding: много мелких локов вместо одного.
• Совсем горячий счётчик/флаг — атомики/CAS (lock-free), помня про ABA.
• Любая межпоточная видимость держится на барьерах, которые дают atomic/mutex/ каналы. Без них «записал» ≠ «другой увидел».
• Замеряя многопоточный код, держи в голове кэш-линии и false sharing — иногда одно поле-набивка ускоряет код в разы.

Что спрашивают на собесе

• Чем плох один глобальный мьютекс на структуру и что такое contention? Ожидают рассказ про сериализацию и переход к striped/sharded locks.
• Что такое CAS и как на нём сделать lock-free счётчик? Опиши retry-цикл read→compute→CAS→retry и упомяни ABA-проблему.
• Зачем нужны барьеры памяти, если есть мьютекс? Объясни, что синхронизация даёт не только взаимное исключение, но и видимость/порядок записей (happens-before).
• Что такое false sharing и как его лечить? Две независимые переменные в одной 64-байтной кэш-линии, ping-pong через MESI, лечение паддингом.
• Расскажи про MESI на пальцах. Modified/Exclusive/Shared/Invalid и то, что запись требует invalidate чужих копий — отсюда стоимость межъядерной записи.
• Когда lock-free хуже мьютекса? При высокой конкуренции CAS-цикл жжёт CPU на ретраях, а мьютекс усыпит поток; плюс lock-free тяжело написать корректно.