Открытое интервью на Go разработчика | Эйч Навыки

23 июля 2024 г. · 40 мин. чтения

Сегодня мы разберём открытое собеседование на позицию Go-разработчика, в ходе которого кандидат продемонстрировал уверенное владение базовыми концепциями языка — слайсами, горутинами, каналами и планировщиком, а также показал способность решать задачи на конкурентность и проектирование структур данных. Особое внимание было уделено глубокому обсуждению внутреннего устройства Go runtime, включая модель планировщика и механизмы синхронизации, что позволило оценить как практические навыки кодирования, так и понимание системных аспектов языка.

Вопрос 1. Расскажи, что ты знаешь о слайсах (slices) в Go.

Таймкод: 00:10:04

Ответ собеседника: Правильный. Слайс — это динамически расширяемый массив. Состоит из трёх полей: len (текущая длина), cap (ёмкость — сколько элементов может вместить) и data (ссылка на массив с данными). При добавлении элементов, если место есть — просто добавляем в data и увеличиваем len; если нет — происходит реаллокация с увеличением ёмкости. Стратегия роста: до 256 элементов ёмкость удваивается, потом рост идёт с меньшим коэффициентом (1.25 и т.д.).

Правильный ответ:

Ответ собеседника правильный и достаточно полный. Дополню некоторые важные детали.

Внутренняя структура слайса

Слайс в Go — это структура из трёх полей:

type slice struct {
    array unsafe.Pointer  // указатель на базовый массив
    len   int            // текущая длина
    cap   int            // ёмкость (максимальная длина без реаллокации)
}

Стратегия роста ёмкости

До Go 1.18 ёмкость удваивалась при каждой реаллокации. Начиная с Go 1.20+ стратегия стала более сложной:

До ~256 элементов: ёмкость удваивается
После 256 элементов: рост с коэффициентом ~1.25

Важные нюансы

Слайс — ссылочный тип. При передаче в функцию копируется заголовок (len, cap, pointer), но данные остаются общими.
Подслайсы делят память с оригиналом:

original := []int{1, 2, 3, 4, 5}
sub := original[1:3]  // sub и original делят один базовый массив
sub[0] = 99           // original[1] тоже станет 99

Реаллокация при append:

a := make([]int, 0, 4)
b := append(a, 1)  // a.len=0, b.len=1, но cap общий
c := append(a, 2)  // перезапишет b[0]!

make vs литерал:

s1 := make([]int, 5, 10)  // len=5, cap=10, нулевые значения
s2 := []int{1, 2, 3}      // len=3, cap=3

nil слайс vs пустой слайс:

var s1 []int        // nil, len=0, cap=0
s2 := []int{}       // не nil, len=0, cap=0
// Оба работают с len(), append(), но отличаются при сравнении с nil

Операции со слайсами

// Копирование
dst := make([]int, len(src))
copy(dst, src)

// Удаление элемента (без сохранения порядка)
s[i] = s[len(s)-1]
s = s[:len(s)-1]

// Удаление с сохранением порядка
s = append(s[:i], s[i+1:]...)

// Вставка
s = append(s[:i], append([]T{val}, s[i:]...)...)

Производительность

Доступ по индексу: O(1)
Добавление в конец (без реаллокации): O(1) амортизированно
Вставка/удаление в начало или середину: O(n) из-за сдвига элементов

Вопрос 2. Если взять срез от слайса и изменить элемент в срезе, изменится ли исходный слайс?

Таймкод: 00:11:46

Ответ собеседника: Правильный. Да, изменится. Срез создаёт новый заголовок слайса, но указатель на данные остаётся тем же, поэтому мутация через подслайс видна в оригинале.

Правильный ответ:

Ответ полностью верен. Дополню примерами и важными следствиями.

Механизм

Операция среза s[low:high] создаёт новый заголовок слайса (len, cap, pointer), но указатель array ссылается на ту же область памяти, что и оригинал.

original := []int{1, 2, 3, 4, 5}
sub := original[1:3]  // sub = [2, 3]

sub[0] = 99
fmt.Println(original) // [1 99 3 4 5]

Изменение cap подслайса

s := make([]int, 5, 10)
sub := s[1:3]
// sub.len = 2, sub.cap = 9 (10 - 1)
// sub может "видеть" больше элементов базового массива, чем s

Опасный сценарий с append

original := []int{1, 2, 3, 4, 5}
sub := original[1:3]     // sub = [2, 3], cap=4

sub = append(sub, 99)     // место есть, реаллокации нет
// original = [1 2 3 99 5] — перезаписали original[3]!

sub = append(sub, 88, 77) // ёмкости не хватает, реаллокация
// Теперь sub и original — разные массивы, изменения независимы

Как избежать побочных эффектов

Если нужна независимая копия:

// Явное копирование
sub := make([]int, len(original[1:3]))
copy(sub, original[1:3])

// Или ограничение cap при срезе (Go 1.2+)
sub := original[1:3:3]  // cap = 3, append вызовет реаллокацию сразу

Третий индекс в s[low:high:max] ограничивает ёмкость подслайса, что защищает от случайной перезаписи оригинала при append.

Вопрос 3. Если передать слайс в функцию, которая добавит в него элемент, будет ли видна эта мутация в исходной функции (например, main)?

Таймкод: 00:12:26

Ответ собеседника: Правильный. Нет, не будет. Слайс передаётся по значению — копируется структура с len, cap и data. Когда функция добавляет элемент и len увеличивается, это изменение происходит в локальной копии структуры. Вызывающая сторона не видит увеличения len, хотя сами данные в underlying array могут быть общими (если не произошла реаллокация).

Правильный ответ:

Ответ верен. Разберём подробнее с примерами.

Что происходит при передаче в функцию

func addElement(s []int) {
    s = append(s, 99)  // s — локальная копия заголовка
    fmt.Println(len(s)) // 4
}

func main() {
    s := []int{1, 2, 3}
    addElement(s)
    fmt.Println(len(s)) // 3 — не изменилось!
}

Два сценария при append

Без реаллокации — данные общие, но len не синхронизирован:

func modify(s []int) {
    s = append(s, 4)      // cap хватает, реаллокации нет
    s[0] = 99             // изменит оригинал
}

func main() {
    s := make([]int, 3, 5)  // [0, 0, 0], cap=5
    modify(s)
    fmt.Println(s)       // [99, 0, 0] — s[0] изменился
    fmt.Println(len(s))  // 3 — но len не изменился
}

С реаллокацией — полная независимость:

func modify(s []int) {
    s = append(s, 4, 5)   // cap не хватает, реаллокация
    s[0] = 99             // уже другой массив
}

func main() {
    s := []int{1, 2, 3}   // cap=3
    modify(s)
    fmt.Println(s)        // [1, 2, 3] — ничего не изменилось
}

Как правильно добавлять элементы

Вариант 1 — возвращать новый слайс:

func addElement(s []int, val int) []int {
    return append(s, val)
}

s = addElement(s, 99)

Вариант 2 — передавать указатель на слайс:

func addElement(s *[]int, val int) {
    *s = append(*s, val)
}

addElement(&s, 99)

Вариант 3 — изменять существующие элементы без append:

func modify(s []int) {
    for i := range s {
        s[i] *= 2
    }
    // Изменения видны вызывающей стороне
}

Ключевое правило

Мутация существующих элементов (s[i] = val) — видна вызывающей стороне
Изменение заголовка (len, cap, pointer через append) — не видна, если не использовать указатель или возврат

Вопрос 4. Что не так в коде с каналами и горутинами, где создаётся небуферизированный канал, запускается горутина-читатель, а запись в канал происходит в main?

Таймкод: 00:13:51

Ответ собеседника: Правильный. Код заблокируется (deadlock), потому что небуферизированный канал требует, чтобы и писатель, и читатель были готовы одновременно. Горутина-читатель не успеет стартовать до того, как main заблокируется на записи. Кроме того, main завершится и не дождётся горутин.

Правильный ответ:

Ответ верен. Разберём проблему детально.

Проблема с небуферизированным каналом

func main() {
    ch := make(chan int)  // небуферизированный канал
    
    go func() {
        val := <-ch       // читатель
        fmt.Println(val)
    }()
    
    ch <- 42              // запись в main — блокировка!
}

Небуферизированный канал работает по принципу рукопожатия (handshake): отправитель и получатель должны быть готовы одновременно. Запись ch <- 42 в main заблокирует горутину до тех пор, пока кто-то не прочитает. Но main заблокирован и не может планировать другие горутины — deadlock.

Решения

Вариант 1 — буферизированный канал:

ch := make(chan int, 1)  // буфер на 1 элемент
ch <- 42                  // не блокируется, запись в буфер

Вариант 2 — писать из горутины:

go func() {
    ch <- 42
}()
val := <-ch  // main ждёт данные

Вариант 3 — читать в main, писать в горутине:

go func() {
    defer close(ch)
    ch <- 42
}()

for val := range ch {
    fmt.Println(val)
}

Проблема завершения main

Даже если решить проблему блокировки, main завершится раньше, чем горутины отработают. Нужна синхронизация:

// Через WaitGroup
var wg sync.WaitGroup
wg.Add(1)
go func() {
    defer wg.Done()
    // работа
}()
wg.Wait()

// Или через канал завершения
done := make(chan struct{})
go func() {
    defer close(done)
    // работа
}()
<-done

Правильный паттерн producer-consumer:

func main() {
    ch := make(chan int)
    done := make(chan struct{})
    
    // consumer
    go func() {
        defer close(done)
        for val := range ch {
            fmt.Println(val)
        }
    }()
    
    // producer (в main)
    for i := 0; i < 5; i++ {
        ch <- i
    }
    close(ch)  // сигнал завершения
    
    <-done  // ждём завершения consumer
}

Ключевые правила

Небуферизированный канал = синхронная передача, требует готовности обеих сторон
Запись в небуферизированный канал из той же горутины, которая читает — deadlock
Всегда закрывайте канал на стороне отправителя
Синхронизируйте завершение горутин через WaitGroup или каналы

Вопрос 5. Что такое deadlock в контексте Go?

Таймкод: 00:15:35

Ответ собеседника: Правильный. Deadlock — это ситуация, когда горутина (или несколько горутин) заблокированна навсегда и не может продолжить выполнение. В Go это происходит, когда все горутины заблокированы (например, ждут данных из канала, которые никогда не придут), и runtime выбрасывает ошибку fatal error: all goroutines are asleep - deadlock!

Правильный ответ:

Ответ верен. Дополню примерами и важными нюансами.

Определение

Deadlock — состояние, при котором все горутины в программе заблокированы и ни одна не может продолжить выполнение. Go runtime детектирует эту ситуацию и паникует с сообщением:

fatal error: all goroutines are asleep - deadlock!

Классические примеры deadlock

Чтение из пустого канала без отправителя:

func main() {
    ch := make(chan int)
    <-ch  // блокировка навсегда, никто не пишет
}

Запись в небуферизированный канал без читателя:

func main() {
    ch := make(chan int)
    ch <- 42  // блокировка навсегда, никто не читает
}

Взаимная блокировка горутин:

func main() {
    ch1 := make(chan int)
    ch2 := make(chan int)
    
    go func() {
        <-ch1  // ждём из ch1
        ch2 <- 1
    }()
    
    go func() {
        <-ch2  // ждём из ch2
        ch1 <- 1
    }()
    
    select {}  // блокируем main
}

Mutex без разблокировки:

var mu sync.Mutex

mu.Lock()
mu.Lock()  // deadlock — mutex уже заблокирован этой же горутиной

Отличие от livelock

Deadlock — горутины заблокированы и не выполняют работу. Livelock — горутины активно работают, но не продвигаются к цели (например, бесконечно пересылают друг другу сообщения).

Как избежать deadlock

Всегда закрывайте каналы на стороне отправителя
Используйте select с default для неблокирующих операций
Используйте context с таймаутами
Соблюдайте порядок блокировки мьютексов
Используйте инструменты анализа: go run -race, go vet

Неблокирующие операции с каналами:

select {
case val := <-ch:
    fmt.Println(val)
default:
    fmt.Println("канал пуст")
}

Вопрос 6. Исправь код с каналами и горутинами, чтобы он выводил 1, 2, 3 и корректно завершался.

Таймкод: 00:16:33

Ответ собеседника: Правильный. Нужно перенести запись в канал в горутину, после записи закрыть канал, а в main читать из канала с помощью range. Это обеспечит корректную синхронизацию и завершение программы.

Правильный ответ:

Ответ верен. Приведу конкретные варианты исправлений.

Исходный проблемный код (предположительно):

func main() {
    ch := make(chan int)
    
    go func() {
        for val := range ch {
            fmt.Println(val)
        }
    }()
    
    ch <- 1
    ch <- 2
    ch <- 3
    // канал не закрыт, горутина будет ждать вечно
}

Исправленный вариант 1 — запись в горутине:

func main() {
    ch := make(chan int)
    
    go func() {
        defer close(ch)
        ch <- 1
        ch <- 2
        ch <- 3
    }()
    
    for val := range ch {
        fmt.Println(val)
    }
}

Исправленный вариант 2 — запись в main с закрытием:

func main() {
    ch := make(chan int)
    
    go func() {
        for val := range ch {
            fmt.Println(val)
        }
    }()
    
    ch <- 1
    ch <- 2
    ch <- 3
    close(ch)  // сигнал завершения
    
    time.Sleep(time.Millisecond) // или лучше — синхронизация
}

Исправленный вариант 3 — с WaitGroup (рекомендуемый):

func main() {
    ch := make(chan int)
    var wg sync.WaitGroup
    
    wg.Add(1)
    go func() {
        defer wg.Done()
        for val := range ch {
            fmt.Println(val)
        }
    }()
    
    for _, v := range []int{1, 2, 3} {
        ch <- v
    }
    close(ch)
    
    wg.Wait()
}

Исправленный вариант 4 — буферизированный канал:

func main() {
    ch := make(chan int, 3)  // буфер на 3 элемента
    
    go func() {
        for val := range ch {
            fmt.Println(val)
        }
    }()
    
    ch <- 1
    ch <- 2
    ch <- 3
    close(ch)
    
    time.Sleep(time.Millisecond)
}

Ключевые принципы

Закрывайте канал на стороне отправителя после всех записей
Используйте range для чтения — автоматически завершается при закрытии канала
Синхронизируйте завершение горутин через WaitGroup или каналы
Не используйте time.Sleep для синхронизации в production-коде

Вопрос 7. Что такое горутина (goroutine) и какие у неё преимущества перед потоками ОС?

Таймкод: 00:17:34

Ответ собеседника: Правильный. Горутина — это легковесный поток, управляемый планировщиком Go runtime. Преимущества перед потоками ОС: стек горутины начинается с 2 КБ и динамически расширяется (у потоков ОС стек статический, обычно 1-8 МБ); переключение контекста между горутинами значительно быстрее, чем между потоками ОС; можно создавать сотни тысяч горутин, ограничения — только объём оперативной памяти.

Правильный ответ:

Ответ верен. Дополню деталями о планировщике и сравнением.

Что такое горутина

Горутина — функция, выполняемая параллельно с другими горутинами, управляемая планировщиком Go runtime (а не ОС). Запускается ключевым словом go.

Сравнение с потоками ОС

Характеристика	Горутина	Поток ОС
Размер стека	2-8 КБ (динамический)	1-8 МБ (статический)
Создание	~200 нс	~10-100 мкс
Переключение контекста	~200 нс	~1-10 мкс
Максимальное количество	сотни тысячи	тысячи
Планировщик	Go runtime (M:N)	ОС (1:1)

Архитектура планировщика Go (M:P:G)

M (Machine) — поток ОС
P (Processor) — процессор (контекст выполнения)
G (Goroutine) — горутина

M потоков ОС обслуживают P процессоров
Каждый P имеет локальную очередь горутин (до 256)
Горутины распределяются между P
Количество P по умолчанию = GOMAXPROCS (число CPU)

Преимущества

Масштабируемость:

// Можно запустить 100K+ горутин
for i := 0; i < 100000; i++ {
    go func() {
        // работа
    }()
}

Дешёвое переключение контекста:

Планировщик Go переключает горутины на кооперативных точках (channel ops, syscalls, function calls)
Не требуется переключение в режим ядра
Сохраняется только состояние регистров (PC, SP, несколько других)

Динамический стек:

Начинается с 2 КБ
Автоматически растёт и сжимается
Исключает проблему stack overflow

Недостатки и ограничения

Горутины не имеют приоритетов
Нет гарантии порядка выполнения
CPU-bound задачи не параллелятся без нескольких P
Блокирующие syscall могут заблокировать поток ОС

Пример использования:

func main() {
    var wg sync.WaitGroup
    
    for i := 0; i < 10; i++ {
        wg.Add(1)
        go func(id int) {
            defer wg.Done()
            fmt.Printf("goroutine %d\n", id)
        }(i)
    }
    
    wg.Wait()
}

Вопрос 8. Какие способы коммуникации между горутинами существуют? Расскажи про каналы — что они из себя представляют изнутри.

Таймкод: 00:20:33

Ответ собеседника: Правильный. Основной способ коммуникации — каналы. Канал — это структура данных внутри runtime, работающая с помощью мьютекса. Есть два вида: буферизированные и небуферизированные. В небуферизированном канале данные передаются напрямую от отправителя к получателю — если отправитель видит, что кто-то уже ждёт чтения, он сразу передаёт данные. В буферизированном канале данные помещаются во внутренний кольцевой буфер, и отправитель блокируется только когда буфер полон.

Правильный ответ:

Ответ верен. Дополню внутренней структурой и другими способами коммуникации.

Способы коммуникации между горутинами

Каналы (channels) — основной и рекомендуемый способ:

ch := make(chan int)
ch := make(chan int, 10)  // буферизированный

Общая память с синхронизацией:

var mu sync.Mutex
var data int

mu.Lock()
data++
mu.Unlock()

sync.WaitGroup — для ожидания завершения:

var wg sync.WaitGroup
wg.Add(1)
go func() {
    defer wg.Done()
    // работа
}()
wg.Wait()

sync.Cond — для сигнализации:

cond := sync.NewCond(&mu)
cond.Wait()    // ждём сигнал
cond.Signal()  // отправляем сигнал

sync/atomic — для атомарных операций:

var counter int64
atomic.AddInt64(&counter, 1)

Внутренняя структура канала (hchan)

type hchan struct {
    qcount   uint           // текущее количество элементов в буфере
    dataqsiz uint           // размер буфа (0 для небуферизированного)
    buf      unsafe.Pointer // указатель на кольцевой буфер
    sendx    uint           // индекс для записи
    recvx    uint           // индекс для чтения
    
    recvq    waitq          // очередь ожидающих читателей (sudog)
    sendq    waitq          // очередь ожидающих писателей (sudog)
    
    lock     mutex          // мьютекс для защиты структуры
}

type sudog struct {
    g    *goroutine  // горутина в очереди
    elem unsafe.Pointer // указатель на данные
    // ...
}

Как работают операции

Запись в небуферизированный канал:

Если в recvq есть ожидающий читатель — данные копируются напрямую, читатель пробуждается
Иначе — текущая горутина добавляется в sendq и блокируется

Запись в буферизированный канал:

Если буфер полон — горутина блокируется в sendq
Иначе — данные помещаются в buf[sendx], sendx увеличивается
Если в recvq есть ожидающий читатель — он пробуждается

Чтение:

Если в sendq есть ожидающий писатель — данные берутся напрямую от него
Иначе если буфер не пуст — данные берутся из buf[recvx]
Иначе — горутина блокируется в recvq

Закрытие канала:

Пробуждаются все горутины в recvq — получают zero value
Горутины в sendq получают panic

Паттерны использования каналов

// Fan-out: один канал → несколько читателей
for i := 0; i < workers; i++ {
    go func() {
        for val := range input {
            process(val)
        }
    }()
}

// Fan-in: несколько каналов → один читатель
func merge(channels ...<-chan int) <-chan int {
    // ...
}

// Pipeline: последовательная обработка
generator -> filter -> mapper -> consumer

Вопрос 9. Расскажи про планировщик Go — как он работает изнутри, какие очереди использует, что такое work stealing, как обрабатываются системные вызовы и сетевой поллинг (network poller)?

Таймкод: 00:22:08

Ответ собеседника: Неполный. Планировщик Go использует модель GMP. Есть локальные очереди горутин, привязанные к каждому процессору (P), и глобальная очередь. Реализован механизм work stealing. Горутины из системных вызовов обрабатываются отдельным потоком (network poller). Каждый 61-й тик планировщик проверяет глобальную очередь. При блокировке горутины на syscall она снимается с потока и передаётся на отдельный поток из пула, а после завершения syscall возвращается в глобальную очередь.

Правильный ответ:

Ответ в целом верен, но требует дополнений и уточнений.

Модель GMP

G (Goroutine) — горутина (стек, состояние, функция)
M (Machine) — поток ОС (kernel thread)
P (Processor) — логический процессор (контекст выполнения)

GOMAXPROCS определяет количество P (по умолчанию = число CPU)
Количество M может быть больше GOMAXPROCS
Каждый P имеет локальную очередь горутин (до 256 элементов)

Очереди горутин

Локальная очередь (runq):

Каждый P имеет свою локальную очередь
Работает по принципу FIFO с оптимизацией для последнего элемента
Новые горутины добавляются в локальную очередь создавшего P

Глобальная очередь (sched.runq):

Защищена мьютексом
Используется когда локальная очередь переполнена
Проверяется каждые 61 вызов schedule() для fairness

Work Stealing

Когда у P заканчиваются горутины в локальной очереди:

// Упрощённая логика
func schedule() {
    // 1. Проверить локальную очередь
    if gp := runqget(_p_); gp != nil {
        return gp
    }
    
    // 2. Проверить глобальную очередь (каждые 61 тик)
    if gp := globrunqget(_p_, 0); gp != nil {
        return gp
    }
    
    // 3. Work stealing — украсть у другого P
    for i := 0; i < 4; i++ {
        for _, p2 := range allp {
            if gp := runqsteal(_p_, p2); gp != nil {
                return gp
            }
        }
    }
    
    // 4. Проверить network poller
    // 5. Заблокироваться
}

Алгоритм кражи:

Случайно выбирает жертву (victim P)
Берёт половину горутин из локальной очереди жертвы
Если не удалось — пробует ещё 3 раза с другими жертвами

Network Poller

Сетевые операции (read, accept, connect) обрабатываются асинхронно:

Goroutine → epoll/kqueue/IOCP → Network Poller → готовая горутина → очередь P

Механизм:

Горутина вызывает conn.Read()
Runtime регистрирует fd в epoll (Linux) / kqueue (macOS) / IOCP (Windows)
Goroutine блокируется (состояние Gwaiting)
Network poller (отдельный поток) опрашивает epoll
Когда данные готовы — горутина переходит в Grunnable и добавляется в очередь

Блокирующие syscall

Fast path (network):

Горутина не блокирует M
M продолжает выполнять другие горутины
После завершения — горутина возвращается в очередь

Slow path (file I/O, sleep):

Горутина блокирует M
M снимается с P (P и M разъединяются)
Создаётся новый M (или берётся из пула) для P
После завершения syscall горутина добавляется в глобальную очередь

// Когда горутина блокирует M
func entersyscall() {
    // Отвязать P от M
    p_.m = nil
    m_.p = 0
    
    // Передать P другому M или создать новый
    handoffp(p_)
}

Состояния горутины

Gidle → Grunnable → Grunning → Gwaiting → Grunnable
                      ↓
                   Gdead

Точки переключения контекста

Операции с каналами (send, receive, select)
System calls
runtime.Gosched() — явная передача управления
time.Sleep() — блокировка с таймером
GC (STW — stop the world)
Вызов функций (stack growth check)

Пример работы

func main() {
    runtime.GOMAXPROCS(2)  // 2 P
    
    for i := 0; i < 10; i++ {
        go func(id int) {
            time.Sleep(time.Second)  // блокирующая операция
            fmt.Println(id)
        }(i)
    }
    
    time.Sleep(2 * time.Second)
}

В этом примере:

10 горутин распределяются между 2 P
При time.Sleep горутины блокируются, M продолжает работу
Network poller отслеживает таймеры
После истечения секунды горутины возвращаются в очереди

Оптимизации

Run queue stealing: случайный выбор жертвы для балансировки
Netpoller integration: сетевые операции без блокировки M
Timer management: иерархические таймеры для эффективности
Spinning threads: M может некоторое время spin в ожидании работы

Вопрос 10. Напиши свой аналог Redis: реализуй потокобезопасный кэш (Set/Get) и логику вытеснения наименее используемых элементов (LRU). Объясни, зачем нужен LRU, и предложи улучшения интерфейса.

Таймкод: 00:36:04

Ответ собеседника: Неполный. Потокобезопасность реализована с sync.RWMutex. Обсуждался алгоритм LRU на двусвязном списке + мапа, но реализация не была завершена.

Правильный ответ:

Зачем нужен LRU

LRU (Least Recently Used) — алгоритм вытеснения из кэша элементов, которые дольше всего не использовались. Основан на принципе локальности: недавно использованные данные с большей вероятностью будут запрошены снова.

Полная реализация LRU-кэша

package cache

import (
    "container/list"
    "context"
    "errors"
    "time"
)

var (
    ErrKeyNotFound = errors.New("key not found")
    ErrKeyExpired  = errors.New("key expired")
)

// Cache — потокобезопасный LRU-кэш
type Cache struct {
    mu       sync.RWMutex
    capacity int
    items    map[string]*list.Element
    order    *list.List // самые свежие в конце
}

// entry — элемент кэша
type entry struct {
    key    string
    value  interface{}
    expiry time.Time // zero value = без TTL
}

// New создаёт новый кэш с заданной ёмкостью
func New(capacity int) *Cache {
    if capacity <= 0 {
        panic("capacity must be positive")
    }
    return &Cache{
        capacity: capacity,
        items:    make(map[string]*list.Element),
        order:    list.New(),
    }
}

// Set добавляет или обновляет элемент
func (c *Cache) Set(ctx context.Context, key string, value interface{}) error {
    return c.SetWithTTL(ctx, key, value, 0)
}

// SetWithTTL добавляет элемент с TTL
func (c *Cache) SetWithTTL(ctx context.Context, key string, value interface{}, ttl time.Duration) error {
    c.mu.Lock()
    defer c.mu.Unlock()

    // Если ключ уже существует — обновляем и перемещаем в конец
    if elem, ok := c.items[key]; ok {
        c.order.MoveToBack(elem)
        elem.Value.(*entry).value = value
        if ttl > 0 {
            elem.Value.(*entry).expiry = time.Now().Add(ttl)
        }
        return nil
    }

    // Если кэш полон — вытесняем LRU-элемент
    if c.order.Len() >= c.capacity {
        c.evict()
    }

    // Добавляем новый элемент
    e := &entry{
        key:   key,
        value: value,
    }
    if ttl > 0 {
        e.expiry = time.Now().Add(ttl)
    }
    elem := c.order.PushBack(e)
    c.items[key] = elem
    return nil
}

// Get возвращает значение по ключу
func (c *Cache) Get(ctx context.Context, key string) (interface{}, error) {
    c.mu.Lock()
    defer c.mu.Unlock()

    elem, ok := c.items[key]
    if !ok {
        return nil, ErrKeyNotFound
    }

    e := elem.Value.(*entry)

    // Проверяем TTL
    if !e.expiry.IsZero() && time.Now().After(e.expiry) {
        c.removeElement(elem)
        return nil, ErrKeyExpired
    }

    // Перемещаем в конец (самый свежий)
    c.order.MoveToBack(elem)
    return e.value, nil
}

// Delete удаляет элемент по ключу
func (c *Cache) Delete(ctx context.Context, key string) error {
    c.mu.Lock()
    defer c.mu.Unlock()

    if elem, ok := c.items[key]; ok {
        c.removeElement(elem)
        return nil
    }
    return ErrKeyNotFound
}

// Len возвращает текущее количество элементов
func (c *Cache) Len() int {
    c.mu.RLock()
    defer c.mu.RUnlock()
    return c.order.Len()
}

// evict удаляет LRU-элемент (из начала списка)
func (c *Cache) evict() {
    elem := c.order.Front()
    if elem != nil {
        c.removeElement(elem)
    }
}

// removeElement удаляет элемент из списка и мапы
func (c *Cache) removeElement(elem *list.Element) {
    e := elem.Value.(*entry)
    delete(c.items, e.key)
    c.order.Remove(elem)
}

Расширенный интерфейс для продакшена

package cache

import (
    "context"
    "sync"
    "time"
)

// Cache — продакшн-версия кэша
type Cache struct {
    mu       sync.RWMutex
    capacity int
    items    map[string]*list.Element
    order    *list.List
    
    // Метрики
    hits   uint64
    misses uint64
    
    // Фоновая очистка
    cleanupInterval time.Duration
    stopCleanup     chan struct{}
}

// Stats — статистика кэша
type Stats struct {
    Size    int
    Hits    uint64
    Misses  uint64
    HitRate float64
}

// Options — опции для создания кэша
type Options struct {
    Capacity        int
    DefaultTTL      time.Duration
    CleanupInterval time.Duration
    OnEvict         func(key string, value interface{})
}

// NewWithOptions создаёт кэш с опциями
func NewWithOptions(opts Options) *Cache {
    c := &Cache{
        capacity: opts.Capacity,
        items:    make(map[string]*list.Element),
        order:    list.New(),
        stopCleanup: make(chan struct{}),
    }
    
    if opts.CleanupInterval > 0 {
        c.cleanupInterval = opts.CleanupInterval
        go c.cleanupLoop()
    }
    
    return c
}

// cleanupLoop периодически удаляет просроченные элементы
func (c *Cache) cleanupLoop() {
    ticker := time.NewTicker(c.cleanupInterval)
    defer ticker.Stop()
    
    for {
        select {
        case <-ticker.C:
            c.purgeExpired()
        case <-c.stopCleanup:
            return
        }
    }
}

// purgeExpired удаляет все просроченные элементы
func (c *Cache) purgeExpired() {
    c.mu.Lock()
    defer c.mu.Unlock()
    
    now := time.Now()
    for elem := c.order.Front(); elem != nil; {
        next := elem.Next()
        e := elem.Value.(*entry)
        if !e.expiry.IsZero() && now.After(e.expiry) {
            c.removeElement(elem)
        }
        elem = next
    }
}

// Stats возвращает статистику
func (c *Cache) Stats() Stats {
    c.mu.RLock()
    defer c.mu.RUnlock()
    
    total := c.hits + c.misses
    hitRate := 0.0
    if total > 0 {
        hitRate = float64(c.hits) / float64(total)
    }
    
    return Stats{
        Size:    c.order.Len(),
        Hits:    c.hits,
        Misses:  c.misses,
        HitRate: hitRate,
    }
}

// Close останавливает фоновые процессы
func (c *Cache) Close() {
    close(c.stopCleanup)
}

Использование

func main() {
    ctx := context.Background()
    
    cache := cache.NewWithOptions(cache.Options{
        Capacity:        1000,
        DefaultTTL:      5 * time.Minute,
        CleanupInterval: time.Minute,
        OnEvict: func(key string, value interface{}) {
            log.Printf("Evicted: %s", key)
        },
    })
    defer cache.Close()
    
    // Установка с TTL
    cache.SetWithTTL(ctx, "user:123", user, 10*time.Minute)
    
    // Получение
    val, err := cache.Get(ctx, "user:123")
    if err != nil {
        log.Printf("Cache miss: %v", err)
    }
    
    // Статистика
    stats := cache.Stats()
    log.Printf("Hit rate: %.2f%%", stats.HitRate*100)
}

Сложность операций

Операция	Время	Память
Set	O(1)	O(1)
Get	O(1)	O(1)
Delete	O(1)	O(1)
Evict	O(1)	O(1)

Возможные улучшения

Sharding — разделение на шарды для уменьшения contention
TTL-куча — для эффективного удаления просроченных элементов
LFU — алгоритм Least Frequently Use для другого паттерна доступа
W-TinyLFU — гибридный алгоритм, используемый в Caffeine
Persistence — сохранение на диск
Pub/Sub — уведомления об изменениях

Вопрос 11. Реализуй функцию mergeChannels, которая принимает произвольное количество каналов и возвращает один канал, в который сливаются все значения из входящих каналов. Результирующий канал должен закрываться, когда все входящие каналы закрыты.

Таймкод: 00:55:49

Ответ собеседника: Правильный. Создаётся результирующий канал. Для каждого входного канала запускается горутина, которая читает и пишет в результирующий канал. Используется атомарный счётчик для отслеживания открытых каналов. Когда счётчик достигает нуля — результирующий канал закрывается.

Правильный ответ:

Ответ верен. Приведу полную реализацию с вариантами.

Реализация с атомарным счётчиком

package main

import (
    "sync"
    "sync/atomic"
)

// mergeChannels сливает произвольное количество каналов в один
func mergeChannels[T any](channels ...<-chan T) <-chan T {
    if len(channels) == 0 {
        out := make(chan T)
        close(out)
        return out
    }

    out := make(chan T)
    var wg sync.WaitGroup

    // Запускаем горутину для каждого входного канала
    for _, ch := range channels {
        wg.Add(1)
        go func(c <-chan T) {
            defer wg.Done()
            for val := range c {
                out <- val
            }
        }(ch)
    }

    // Закрываем out, когда все каналы прочитаны
    go func() {
        wg.Wait()
        close(out)
    }()

    return out
}

Реализация с буферизацией (для высокой нагрузки)

func mergeChannelsBuffered[T any](bufSize int, channels ...<-chan T) <-chan T {
    if len(channels) == 0 {
        out := make(chan T)
        close(out)
        return out
    }

    out := make(chan T, bufSize)
    var wg sync.WaitGroup

    for _, ch := range channels {
        wg.Add(1)
        go func(c <-chan T) {
            defer wg.Done()
            for val := range c {
                out <- val
            }
        }(ch)
    }

    go func() {
        wg.Wait()
        close(out)
    }()

    return out
}

Реализация с контекстом (с возможностью отмены)

func mergeChannelsWithContext[T any](ctx context.Context, channels ...<-chan T) <-chan T {
    if len(channels) == 0 {
        out := make(chan T)
        close(out)
        return out
    }

    out := make(chan T)
    var wg sync.WaitGroup

    for _, ch := range channels {
        wg.Add(1)
        go func(c <-chan T) {
            defer wg.Done()
            for {
                select {
                case val, ok := <-c:
                    if !ok {
                        return
                    }
                    select {
                    case out <- val:
                    case <-ctx.Done():
                        return
                    }
                case <-ctx.Done():
                    return
                }
            }
        }(ch)
    }

    go func() {
        wg.Wait()
        close(out)
    }()

    return out
}

Реализация с select (без горутин на канал)

func mergeChannelsSelect[T any](channels ...<-chan T) <-chan T {
    out := make(chan T)
    var closedCount int32
    total := int32(len(channels))

    go func() {
        defer close(out)

        for {
            select {
            case val, ok := <-channels[0]:
                if !ok {
                    atomic.AddInt32(&closedCount, 1)
                    channels[0] = nil // исключаем из select
                    if atomic.LoadInt32(&closedCount) == total {
                        return
                    }
                    continue
                }
                out <- val
            case val, ok := <-channels[1]:
                if !ok {
                    atomic.AddInt32(&closedCount, 1)
                    channels[1] = nil
                    if atomic.LoadInt32(&closedCount) == total {
                        return
                    }
                    continue
                }
                out <- val
            }
        }
    }()

    return out
}

Использование

func main() {
    ch1 := make(chan int)
    ch2 := make(chan int)
    ch3 := make(chan int)

    // Отправляем данные в горутинах
    go func() {
        defer close(ch1)
        for i := 0; i < 3; i++ {
            ch1 <- i
        }
    }()

    go func() {
        defer close(ch2)
        for i := 10; i < 13; i++ {
            ch2 <- i
        }
    }()

    go func() {
        defer close(ch3)
        for i := 20; i < 23; i++ {
            ch3 <- i
        }
    }()

    // Сливаем каналы
    merged := mergeChannels(ch1, ch2, ch3)

    // Читаем все значения
    for val := range merged {
        fmt.Println(val)
    }
    // Вывод: 0, 1, 2, 10, 11, 12, 20, 21, 22 (порядок не гарантирован)
}

Тестирование

func TestMergeChannels(t *testing.T) {
    ch1 := make(chan int, 3)
    ch2 := make(chan int, 3)

    ch1 <- 1
    ch1 <- 2
    ch1 <- 3
    close(ch1)

    ch2 <- 4
    ch2 <- 5
    ch2 <- 6
    close(ch2)

    merged := mergeChannels(ch1, ch2)

    var results []int
    for val := range merged {
        results = append(results, val)
    }

    if len(results) != 6 {
        t.Errorf("expected 6 values, got %d", len(results))
    }
}

Ключевые моменты

Каждый входной канал читается в отдельной горутине
sync.WaitGroup гарантирует закрытие результирующего канала после завершения всех входных
Функция не закрывает входящие каналы — это ответственность отправителя
Для пустого списка каналов возвращается уже закрытый канал

Вопрос 12. Что выведет код с fmt.Println, если GOMAXPROCS=1 и если GOMAXPROCS>1? Код запускает 3 горутины, каждая пишет строку в слайс, затем WaitGroup.Wait() и печать слайса.

Таймкод: 00:59:00

Ответ собеседника: Правильный. Это undefined behavior — результат не определён в обоих случаях. Горутины могут выполняться в произвольном порядке, и планировщик не даёт гарантий последовательности исполнения.

Правильный ответ:

Ответ верен. Дополню деталями о причинах и последствиях.

Пример кода

func main() {
    runtime.GOMAXPROCS(1) // или > 1
    
    var wg sync.WaitGroup
    var mu sync.Mutex
    results := make([]string, 0, 3)
    
    for i := 0; i < 3; i++ {
        wg.Add(1)
        go func(id int) {
            defer wg.Done()
            mu.Lock()
            results = append(results, fmt.Sprintf("goroutine %d", id))
            mu.Unlock()
        }(i)
    }
    
    wg.Wait()
    fmt.Println(results)
}

Почему результат не определён

Порядок выполнения горутин:

Планировщик Go не гарантирует порядок выполнения горутин
При GOMAXPROCS=1 горутины выполняются последовательно, но порядок зависит от планировщика
При GOMAXPROCS>1 горутины могут выполняться параллельно

Точки переключения контекста:

Вызовы функций
Операции с каналами
System calls
runtime.Gosched()
Проверка роста стека

Возможные результаты

[goroutine 0 goroutine 1 goroutine 2]
[goroutine 2 goroutine 0 goroutine 1]
[goroutine 1 goroutine 2 goroutine 0]
// ... любая перестановка

Проблемы в коде

Race condition без мьютекса:

// НЕПРАВИЛЬНО — data race
go func(id int) {
    defer wg.Done()
    results = append(results, fmt.Sprintf("goroutine %d", id))
}(i)

Без mu.Lock() — race condition при конкурентном append к слайсу.

Как получить детерминированный порядок

Вариант 1 — каналы:

func main() {
    ch := make(chan string, 3)
    var wg sync.WaitGroup
    
    for i := 0; i < 3; i++ {
        wg.Add(1)
        go func(id int) {
            defer wg.Done()
            ch <- fmt.Sprintf("goroutine %d", id)
        }(i)
    }
    
    go func() {
        wg.Wait()
        close(ch)
    }()
    
    for s := range ch {
        fmt.Println(s)
    }
}

Вариант 2 — предвыделенный слайс с индексом:

func main() {
    var wg sync.WaitGroup
    results := make([]string, 3) // предвыделяем с нужным размером
    
    for i := 0; i < 3; i++ {
        wg.Add(1)
        go func(id int) {
            defer wg.Done()
            results[id] = fmt.Sprintf("goroutine %d", id)
        }(i)
    }
    
    wg.Wait()
    fmt.Println(results)
    // Всегда: [goroutine 0 goroutine 1 goroutine 2]
}

Вариант 3 — явная синхронизация:

func main() {
    var wg sync.WaitGroup
    ch := make(chan struct{})
    
    wg.Add(1)
    go func() {
        defer wg.Done()
        fmt.Println("first")
        close(ch)
    }()
    
    <-ch // ждём завершения
    
    wg.Add(1)
    go func() {
        defer wg.Done()
        fmt.Println("second")
    }()
    
    wg.Wait()
}

Ключевые правила

Не полагайтесь на порядок выполнения горутин
Используйте каналы или примитивы синхронизации для координации
Для параллельной записи в общую память — всегда используйте мьютексы
Запускайте с -race для обнаружения race conditions

Вопрос 13. Что такое консистентное хеширование (consistent hashing) и зачем оно нужно? Какую проблему шардирования оно решает?

Таймкод: 01:01:06

Ответ собеседника: Неполный. Проблема обычного шардирования в том, что при изменении количества шардов данные окажутся не на тех шардах. Консистентное хеширование решает эту проблему — при добавлении/удалении шарда перемещается только часть данных. Кандидат знал про виртуальные шарды, но не смог подробно объяснить классический алгоритм.

Правильный ответ:

Проблема обычного хеширования

При шардировании через hash(key) % N:

shard := hash(key) % numShards

При изменении количества шардов (N → N+1) почти все ключи попадают на другие шарды:

N=3: key1 → shard 1, key2 → shard 2, key3 → shard 0
N=4: key1 → shard 1, key2 → shard 2, key3 → shard 3  // key3 переместился

~N/(N+1) данных нужно переместить — катастрофа для распределённых систем.

Классический алгоритм консистентного хеширования

Хеш-окружность (hash ring):

Хеш-функция отображает ключи и узлы на окружность [0, 2^32)
Ключ назначается на ближайший узел по часовой стрелке
При добавлении/удалении узла затрашиваются только соседние ключи

Реализация

package consistenthash

import (
    "hash/crc32"
    "sort"
    "strconv"
)

type Hash func(data []byte) uint32

type Map struct {
    hash     Hash
    replicas int   // количество виртуальных узлов на реальный
    keys     []int // отсортированные хеши на окружности
    hashMap  map[int]string // хеш → имя узла
}

func New(replicas int, fn Hash) *Map {
    m := &Map{
        replicas: replicas,
        hash:     fn,
        hashMap:  make(map[int]string),
    }
    if m.hash == nil {
        m.hash = crc32.ChecksumIEEE
    }
    return m
}

// Add добавляет узлы на окружность
func (m *Map) Add(keys ...string) {
    for _, key := range keys {
        for i := 0; i < m.replicas; i++ {
            hash := int(m.hash([]byte(strconv.Itoa(i) + key)))
            m.keys = append(m.keys, hash)
            m.hashMap[hash] = key
        }
    }
    sort.Ints(m.keys)
}

// Get возвращает узел для ключа
func (m *Map) Get(key string) string {
    if len(m.keys) == 0 {
        return ""
    }

    hash := int(m.hash([]byte(key)))
    
    // Бинарный поиск первого узла с хешем >= hash
    idx := sort.Search(len(m.keys), func(i int) bool {
        return m.keys[i] >= hash
    })
    
    // Если дошли до конца — берём первый (закольцовывание)
    if idx == len(m.keys) {
        idx = 0
    }
    
    return m.hashMap[m.keys[idx]]
}

Виртуальные узлы (replicas)

Без виртуальных узлов распределение неравномерное:

Узел A (хеш 10)  ← большой сегмент
Узел B (хеш 50)  ← маленький сегмент
Узел C (хеш 55)  ← маленький сегмент

С виртуальными узлами (replicas=150):

A1(5) A2(15) A3(25) ... A150(300)
B1(35) B2(45) ... B150(350)
C1(55) C2(65) ... C150(380)

Распределение становится равномернее.

Пример использования

func main() {
    hash := consistenthash.New(150, nil)
    
    // Добавляем узлы
    hash.Add("shard-1", "shard-2", "shard-3")
    
    // Определяем шард для ключа
    tests := []string{"user:123", "user:456", "product:789"}
    for _, key := range tests {
        fmt.Printf("%s → %s\n", key, hash.Get(key))
    }
    
    // Добавляем новый узел
    hash.Add("shard-4")
    
    // Проверяем — большинство ключей остались на месте
    for _, key := range tests {
        fmt.Printf("%s → %s\n", key, hash.Get(key))
    }
}

Сравнение подходов

Подход	Перемещение данных при добавлении узла	Сложность Get
hash % N	~N/(N+1) всех данных	O(1)
Consistent Hashing	~1/N данных	O(log V)

где V = количество виртуальных узлов.

Где используется

Amazon DynamoDB — партиционирование данных
Apache Cassandra — распределение по нодам
Redis Cluster — хеш-слоты (16384 слота)
CDN — маршрутизация запросов к серверам
Load balancers — распределение соединений

Ограничения

Неравномерное распределение без виртуальных узлов
Нет учёта веса узлов (можно добавить через разное количество replicas)
При малом количестве узлов — статистические отклонения

Улучшения

Bounded loads — ограничение нагрузки на узел
Rendezvous hashing — альтернатива с лучшим распределением
Jump consistent hash — O(1) без хранения состояния

Вопрос 14. Что такое паттерн Raft и как он решает проблему выбора нового мастера при падении текущего в репликации?

Таймкод: 01:06:34

Ответ собеседника: Неполный. Кандидат не смог вспомнить Raft. После подсказки описал процесс выбора нового мастера, но не знал алгоритма выборов.

Правильный ответ:

Что такое Raft

Raft — консенсус-алгоритм для управления реплицированным логом. Разработан для понятности (в отличие от Paxos). Обеспечивает выбор лидера и репликацию данных в распределённой системе.

Состояния узлов

Follower → Candidate → Leader
    ↑          ↓           ↓
    └──────────┴───────────┘

Follower — пассивный, отвечает на запросы лидера
Candidate — кандидат на роль лидера во время выборов
Leader — обрабатывает все клиентские запросы, реплицирует лог

Термы (terms)

Term 1    Term 2    Term 3
|---------|---------|------→
 LeaderA   LeaderB   LeaderC

Каждый терм начинается с выборов
Узлы хранят currentTerm — монотонно возрастающий номер
При получении сообщения с большим термом — обновляют свой

Алгоритм выборов

1. Инициация выборов:

Follower не получает heartbeat от лидера
         ↓
  Таймаут истёкает (150-300ms, рандомизированный)
         ↓
  Переходит в Candidate
         ↓
  Увеличивает currentTerm
         ↓
  Голосует за себя
         ↓
  Отправляет RequestVote RPC всем узлам

2. Голосование:

type RequestVoteArgs struct {
    Term         int    // терм кандидата
    CandidateId  int    // ID кандидата
    LastLogIndex int    // индекс последней записи в логе
    LastLogTerm  int    // терм последней записи
}

type RequestVoteReply struct {
    Term        int  // текущий терм узла
    VoteGranted bool // true если голос отдан
}

Узел голосует за кандидата если:

Терм кандидата >= текущий терм
Узел ещё не голосовал в этом терме
Лог кандидата не менее актуален

3. Результат:

Candidate получает голоса большинства (N/2 + 1)
         ↓
  Становится Leader
         ↓
  Отправляет heartbeat всем узлам

Candidate получает голоса от нового лидера
         ↓
  Возвращается в Follower

Никто не получает большинства (split vote)
         ↓
  Таймаут → новый терм → новые выборы

Репликация лога

type AppendEntriesArgs struct {
    Term         int        // терм лидера
    LeaderId     int        // ID лидера
    PrevLogIndex int        // индекс предыдущей записи
    PrevLogTerm  int        // терм предыдущей записи
    Entries      []LogEntry // записи для репликации
    LeaderCommit int        // commitIndex лидера
}

type AppendEntriesReply struct {
    Term    int  // текущий терм узла
    Success bool // true если запись принята
}

Процесс:

Клиент → Leader: запись данных
         ↓
  Leader добавляет запись в свой лог
         ↓
  Leader отправляет AppendEntries всем Follower
         ↓
  Follower проверяет: PrevLogIndex и PrevLogTerm совпадают?
         ↓ да                    ↓ нет
  Добавляет запись        Отклоняет, Leader
  Отвечает Success        откатывает PrevLogIndex
         ↓
  Большинство подтвердило?
         ↓ да
  Leader применяет запись к state machine
  Отвечает клиенту
         ↓
  В следующем heartbeat увеличивает commitIndex

Безопасность (Safety)

Election Safety — в каждом терме не более одного лидера
Leader Append-Only — лидер не удаляет и не перезаписывает записи
Log Matching — если два лога имеют запись с одинаковым индексом и термом, они идентичны до этой записи
Leader Completeness — если запись закоммичена, она будет в логах будущих лидеров
State Machine Safety — если узел применил запись, другой узел не может применить другую запись на том же индексе

Пример реализации на Go

package raft

import (
    "math/rand"
    "sync"
    "time"
)

type NodeState int

const (
    Follower NodeState = iota
    Candidate
    Leader
)

type Node struct {
    mu sync.Mutex
    
    id          int
    peers       []*Node // другие узлы
    state       NodeState
    currentTerm int
    votedFor    int // ID узла, за который голосовали
    
    log         []LogEntry
    commitIndex int
    lastApplied int
    
    // Для лидера
    nextIndex  map[int]int // следующий индекс для каждого узла
    matchIndex map[int]int // последний подтверждённый индекс
    
    // Таймеры
    electionTimeout  time.Duration
    heartbeatTimeout time.Duration
    lastHeartbeat    time.Time
}

type LogEntry struct {
    Term    int
    Command interface{}
}

func NewNode(id int, peers []*Node) *Node {
    n := &Node{
        id:               id,
        peers:            peers,
        state:            Follower,
        votedFor:         -1,
        electionTimeout:  randomTimeout(150, 300),
        heartbeatTimeout: 50 * time.Millisecond,
        lastHeartbeat:    time.Now(),
    }
    go n.run()
    return n
}

func (n *Node) run() {
    for {
        switch n.getState() {
        case Follower:
            n.runFollower()
        case Candidate:
            n.runCandidate()
        case Leader:
            n.runLeader()
        }
    }
}

func (n *Node) runFollower() {
    for n.getState() == Follower {
        if time.Since(n.lastHeartbeat) > n.electionTimeout {
            n.becomeCandidate()
            return
        }
        time.Sleep(10 * time.Millisecond)
    }
}

func (n *Node) becomeCandidate() {
    n.mu.Lock()
    defer n.mu.Unlock()
    
    n.state = Candidate
    n.currentTerm++
    n.votedFor = n.id
    n.electionTimeout = randomTimeout(150, 300)
    
    // Запрашиваем голоса
    votes := 1 // голос за себя
    for _, peer := range n.peers {
        go func(p *Node) {
            reply := p.RequestVote(n.currentTerm, n.id, n.lastLogIndex(), n.lastLogTerm())
            if reply.VoteGranted {
                votes++
                if votes > len(n.peers)/2 {
                    n.becomeLeader()
                }
            }
        }(peer)
    }
}

func (n *Node) becomeLeader() {
    n.mu.Lock()
    defer n.mu.Unlock()
    
    n.state = Leader
    n.nextIndex = make(map[int]int)
    n.matchIndex = make(map[int]int)
    
    for _, peer := range n.peers {
        n.nextIndex[peer.id] = len(n.log)
        n.matchIndex[peer.id] = 0
    }
}

func (n *Node) runLeader() {
    for n.getState() == Leader {
        n.sendHeartbeats()
        time.Sleep(n.heartbeatTimeout)
    }
}

func (n *Node) sendHeartbeats() {
    for _, peer := range n.peers {
        go func(p *Node) {
            p.AppendEntries(n.currentTerm, n.id, n.lastLogIndex(), n.lastLogTerm(), nil, n.commitIndex)
        }(peer)
    }
}

func randomTimeout(min, max int) time.Duration {
    return time.Duration(min+rand.Intn(max-min)) * time.Millisecond
}

Где используется

etcd — распределённое хранилище для Kubernetes
Consul — service discovery от HashiCorp
CockroachDB — распределённая база данных
TiKV — распределённое key-value хранилище

Сравнение с другими алгоритмами

Алгоритм	Сложность понимания	Производительность	Где используется
Paxos	Высокая	Высокая	Chubby, Spanner
Raft	Средняя	Высокая	etcd, Consul
ZAB	Средняя	Высокая	ZooKeeper
PBFT	Высокая	Низкая	Blockchain

Вопрос 15. Объсни разницу между репликацией и шардированием. К какому типу масштабирования относится каждый из них — вертикальному или горизонтальному?

Таймкод: 01:09:55

Ответ собеседника: Правильный. Репликация — создание копий данных для отказоустойчивости и распределения нагрузки на чтение. Шардирование — разделение данных между серверами для увеличения скорости. Кандидат верно объяснил оба понятия, но путался в классификации типов масштабирования.

Правильный ответ:

Ответ верен по сути. Дополню классификацией и деталями.

Репликация (Replication)

Создание и поддержание копий одних и тех же данных на нескольких узлах.

        Master
       /   |   \
    Slave Slave Slave

Типы репликации:

Master-Slave (Primary-Replica):

Клиент → Master → репликация → Slave 1, Slave 2, Slave 3
         (запись)              (только чтение)

Master-Master (Multi-Master):

Клиент → Master 1 ←→ Master 2
         (запись)      (запись)

Цели репликации:

Отказоустойчивость — при падении мастера реплика принимает на себя роль
Масштабирование чтения — распределение read-запросов между репликами
Географическое распределение — данные ближе к пользователям

Тип масштабирования: Вертикальное (scale up) для записи, горизонтальное (scale out) для чтения.

Шардирование (Sharding)

Разделение данных на части (шарды), каждый шард хранится на отдельном узле.

Shard 1: users 1-1000    → Node A
Shard 2: users 1001-2000 → Node B
Shard 3: users 2001-3000 → Node C

Стратегии шардирования:

По диапазону (Range-based):

func getShard(key string) int {
    hash := hash(key)
    if hash < 1000 { return 0 }
    if hash < 2000 { return 1 }
    return 2
}

По хешу (Hash-based):

func getShard(key string, numShards int) int {
    return hash(key) % numShards
}

По словарю (Directory-based):

shardMap := map[string]int{
    "users":    0,
    "products": 1,
    "orders":   2,
}

Цели шардирования:

Масштабирование записи — каждый шард обрабатывает свою часть записей
Масштабирование чтения — параллельное выполнение запросов
Уменьшение объёма данных на узел — быстрее индексы, меньше памяти

Тип масштабирования: Горизонтальное (scale out).

Сравнение

Характеристика	Репликация	Шардирование
Данные на узлах	Одинаковые	Разные
Масштабирование записи	Нет (только master)	Да
Масштабирование чтения	Да (replicas)	Да
Отказоустойчивость	Высокая	Зависит от реплик
Сложность	Средняя	Высокая
Тип масштабирования	Вертикальное (запись), горизонтальное (чтение)	Горизонтальное

Комбинированный подход

В реальности используются вместе:

Master 1 → Replica 1a, Replica 1b  (Shard 1)
Master 2 → Replica 2a, Replica 2b  (Shard 2)
Master 3 → Replica 3a, Replica 3b  (Shard 3)

Примеры в базах данных

MySQL — репликация master-slave, шардирование на уровне приложения
PostgreSQL — репликация streaming, шардирование через Citus
MongoDB — встроенный шардирование + replica sets
Redis — Redis Cluster с шардированием и репликацией
Cassandra — шардирование через consistent hashing + репликация

Проблемы шардирования

Cross-shard запросы — сложные и медленные
Rebalancing — перемещение данных при изменении количества шардов
Hot spots — неравномерная нагрузка на шарды
Транзакции — распределённые транзакции сложны

Вопрос 16. Что такое паттерн Transactional Outbox и как он решает проблему атомарности при отправке событий в брокер сообщений?

Таймкод: 01:15:53

Ответ собеседника: Правильный. Transactional Outbox — паттерн, при котором событие записывается в таблицу БД в той же транзакции, что и основная операция. Затем отдельный воркер читает неотправленные события и отправляет их в брокер. Гарантирует at-least-once delivery.

Правильный ответ:

Ответ верен. Дополню схемой и деталями реализации.

Проблема

Сервис A                    Брокер сообщений
    |                              |
    |-- 1. Записать в БД --------->| ✓ успех
    |                              |
    |-- 2. Отправить событие ----->| ✗ ошибка!
    |                              |
    ↓                              ↓
  Данные обновлены,              Событие потеряно
  но никто не знает

Невозможно атомарно выполнить запись в БД и отправку в брокер — это разные системы.

Решение: Transactional Outbox

┌─────────────────────────────────────────────────────────────┐
│                      Сервис A                                │
│                                                             │
│  ┌─────────────┐    ┌─────────────┐    ┌─────────────────┐  │
│  │  Основная   │    │   Outbox    │    │    Воркер       │  │
│  │   таблица   │    │   таблица   │    │  (poller)       │  │
│  │             │    │             │    │                 │  │
│  │ 1. UPDATE   │    │ 2. INSERT   │    │ 3. SELECT       │  │
│  │   accounts  │    │   event     │    │   pending       │  │
│  │             │    │             │    │ 4. PUBLISH      │  │
│  └─────────────┘    └─────────────┘    │ 5. UPDATE status│  │
│         │                │             └─────────────────┘  │
│         └────────────────┘                    │              │
│              Одна транзакция                 ↓              │
│                                      Брокер сообщений       │
└─────────────────────────────────────────────────────────────┘

Схема базы данных

-- Основная таблица
CREATE TABLE accounts (
    id SERIAL PRIMARY KEY,
    user_id INT NOT NULL,
    balance DECIMAL(10, 2) NOT NULL,
    updated_at TIMESTAMP DEFAULT NOW()
);

-- Outbox таблица
CREATE TABLE outbox (
    id SERIAL PRIMARY KEY,
    aggregate_type VARCHAR(255) NOT NULL,  -- 'account'
    aggregate_id VARCHAR(255) NOT NULL,    -- '123'
    event_type VARCHAR(255) NOT NULL,      -- 'balance_deducted'
    payload JSONB NOT NULL,
    status VARCHAR(50) DEFAULT 'pending',  -- pending, sent, failed
    created_at TIMESTAMP DEFAULT NOW(),
    sent_at TIMESTAMP,
    retry_count INT DEFAULT 0
);

CREATE INDEX idx_outbox_status ON outbox(status, created_at);

Реализация на Go

package outbox

import (
    "context"
    "encoding/json"
    "time"

    "github.com/jmoiron/sqlx"
)

type Event struct {
    ID            int       `db:"id"`
    AggregateType string    `db:"aggregate_type"`
    AggregateID   string    `db:"aggregate_id"`
    EventType     string    `db:"event_type"`
    Payload       string    `db:"payload"`
    Status        string    `db:"status"`
    CreatedAt     time.Time `db:"created_at"`
    SentAt        time.Time `db:"sent_at"`
    RetryCount    int       `db:"retry_count"`
}

type Service struct {
    db     *sqlx.DB
    broker Broker
}

type Broker interface {
    Publish(ctx context.Context, topic string, event []byte) error
}

// DeductBalance — основная бизнес-логика с outbox
func (s *Service) DeductBalance(ctx context.Context, userID int, amount float64) error {
    tx, err := s.db.BeginTxx(ctx, nil)
    if err != nil {
        return err
    }
    defer tx.Rollback()

    // 1. Обновляем баланс
    _, err = tx.ExecContext(ctx, `
        UPDATE accounts 
        SET balance = balance - $1, updated_at = NOW()
        WHERE user_id = $2 AND balance >= $3
    `, amount, userID, amount)
    if err != nil {
        return err
    }

    // 2. Создаём событие в outbox (той же транзакцией)
    payload, _ := json.Marshal(map[string]interface{}{
        "user_id": userID,
        "amount":  amount,
    })
    _, err = tx.ExecContext(ctx, `
        INSERT INTO outbox (aggregate_type, aggregate_id, event_type, payload)
        VALUES ($1, $2, $3, $4)
    `, "account", string(userID), "balance_deducted", payload)
    if err != nil {
        return err
    }

    // 3. Коммитим обе операции атомарно
    return tx.Commit()
}

// OutboxPoller — фоновый воркер для отправки событий
func (s *Service) StartOutboxPoller(ctx context.Context, interval time.Duration) {
    ticker := time.NewTicker(interval)
    defer ticker.Stop()

    for {
        select {
        case <-ctx.Done():
            return
        case <-ticker.C:
            s.processPendingEvents(ctx)
        }
    }
}

func (s *Service) processPendingEvents(ctx context.Context) {
    events, err := s.fetchPendingEvents(ctx, 100)
    if err != nil {
        log.Printf("Failed to fetch pending events: %v", err)
        return
    }

    for _, event := range events {
        if err := s.sendEvent(ctx, &event); err != nil {
            log.Printf("Failed to send event %d: %v", event.ID, err)
            s.markFailed(ctx, event.ID)
        } else {
            s.markSent(ctx, event.ID)
        }
    }
}

func (s *Service) fetchPendingEvents(ctx context.Context, limit int) ([]Event, error) {
    var events []Event
    err := s.db.SelectContext(ctx, &events, `
        SELECT id, aggregate_type, aggregate_id, event_type, payload, status, created_at
        FROM outbox
        WHERE status = 'pending' AND retry_count < 5
        ORDER BY created_at
        LIMIT $1
        FOR UPDATE SKIP LOCKED
    `, limit)
    return events, err
}

func (s *Service) sendEvent(ctx context.Context, event *Event) error {
    topic := fmt.Sprintf("%s.%s", event.AggregateType, event.EventType)
    return s.broker.Publish(ctx, topic, []byte(event.Payload))
}

func (s *Service) markSent(ctx context.Context, eventID int) error {
    _, err := s.db.ExecContext(ctx, `
        UPDATE outbox 
        SET status = 'sent', sent_at = NOW()
        WHERE id = $1
    `, eventID)
    return err
}

func (s *Service) markFailed(ctx context.Context, eventID int) error {
    _, err := s.db.ExecContext(ctx, `
        UPDATE outbox 
        SET status = 'failed', retry_count = retry_count + 1
        WHERE id = $1
    `, eventID)
    return err
}

Гаратии доставки

At-least-once — событие будет доставлено минимум один раз:

Если сервис упадёт после коммита транзакции — событие в outbox
Если брокер недоступен — повторные попытки

Exactly-once — требует дополнительных мер:

Идемпотентность на стороне потребителя
Дедупликация по уникальному ID события

Варианты реализации

Polling (опрос):

Периодический SELECT из outbox
Простота, но задержка

CDC (Change Data Capture):

Чтение WAL/binlog базы данных
Debezium, Maxwell
Минимальная задержка

Transactional Outbox + CDC:

Service → Outbox table → Debezium → Kafka

Проблемы и решения

Проблема	Решение
Дублирование событий	Идемпотентность потребителя
Порядок событий	Партиционирование по aggregate_id
Мёртвые события	Retry с exponential backoff
Рост outbox таблицы	Архивация отправленных событий

Вопрос 17. Зачем нужны индексы в базах данных? Какие типы индексов существуют и какие у них плюсы и минусы?

Таймкод: 01:24:51

Ответ собеседника: Неполный. Индексы нужны для ускорения поиска. Упомянуты B-tree и хеш-индексы. Плюс — быстрое чтение. Минусы — медленная запись и раздувание индексов при частых обновлениях (MVCC в PostgreSQL). Не раскрыты полностью типы индексов и их характеристики.

Правильный ответ:

Зачем нужны индексы

Без индекса база выполняет полное сканирование таблицы (Sequential Scan):

-- Seq Scan: O(n)
SELECT * FROM users WHERE email = 'test@example.com';
-- Сканирует все 1 000 000 строк

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

-- Index Scan: O(log n)
SELECT * FROM users WHERE email = 'test@example.com';
-- Находит за ~20 операций (log2(1000000) ≈ 20)

Типы индексов

B-Tree (Balanced Tree)

              [50]
            /      \
        [20, 35]    [70, 90]
       /   |   \    /   |   \
    [10] [25] [40] [60] [80] [95]

Сбалансированное дерево, все листья на одном уровне
Сложность поиска: O(log n)
Поддерживает: =, >, <, BETWEEN, LIKE 'prefix%'
По умолчанию в PostgreSQL, MySQL (InnoDB)

CREATE INDEX idx_users_email ON users(email);

Hash Index

hash('alice@example.com') → bucket 42 → pointer to row
hash('bob@example.com')   → bucket 17 → pointer to row

Хеш-функция отображает значение в корзину
Сложность поиска: O(1) в среднем
Поддерживает только: =
Не поддерживает диапазонные запросы

CREATE INDEX idx_users_email ON users USING hash(email);

GiST (Generalized Search Tree)

Обобщённое дерево поиска
Для геоданных, полнотекстового поиска, диапазонов
PostGIS использует GiST для пространственных индексов

CREATE INDEX idx_locations ON locations USING gist(coordinates);

GIN (Generalized Inverted Index)

Инвертированный индекс для составных значений
Для JSONB, массивов, полнотекстового поиска

CREATE INDEX idx_users_tags ON users USING gin(tags);
CREATE INDEX idx_docs_content ON documents USING gin(to_tsvector('english', content));

BRIN (Block Range Index)

Индекс по диапазонам блоков
Компактный, для больших таблиц с физическим порядком
Для временных рядов, логов

CREATE INDEX idx_logs_created ON logs USING brin(created_at);

Сравнение типов индексов

Тип	Поиск	Диапазон	Размер	Использование
B-Tree	O(log n)	✓	Средний	Универсальный
Hash	O(1)	✗	Малый	Точный поиск
GiST	O(log n)	✓	Большой	Геоданные, полнотекст
GIN	O(log n)	✗	Большой	JSONB, массивы
BRIN	O(n/k)	✓	Очень малый	Временные ряды

Плюсы индексов

Ускорение SELECT запросов
Ускорение JOIN, ORDER BY, GROUP BY
Уникальные индексы обеспечивают целостность

Минусы индексов

Замедление записи:

-- Без индекса: O(1) — просто добавить строку
INSERT INTO users (name, email) VALUES ('Alice', 'alice@example.com');

-- С 3 индексами: O(log n) × 3 — обновить каждую структуру
INSERT INTO users (name, email) VALUES ('Alice', 'alice@example.com');
-- Обновить idx_users_email (B-Tree)
-- Обновить idx_users_name (B-Tree)
-- Обновить idx_users_created (B-Tree)

Раздувание (bloat) в PostgreSQL:

UPDATE users SET name = 'Bob' WHERE id = 1;

-- MVCC создаёт новую версию строки:
-- Old: (id=1, name='Alice') → помечается как dead
-- New: (id=1, name='Bob') → добавляется

-- Индекс содержит указатели на ОБЕ версии:
-- idx_users_name: 'Alice' → dead_tuple, 'Bob' → new_tuple

Покрывающие индексы (Covering Index)

-- Индекс содержит все нужные столбцы
CREATE INDEX idx_users_email_name ON users(email, name);

-- Index Only Scan — не нужно читать таблицу
SELECT name FROM users WHERE email = 'test@example.com';

Составные индексы (Composite Index)

CREATE INDEX idx_users_status_created ON users(status, created_at);

-- Использует индекс:
SELECT * FROM users WHERE status = 'active' AND created_at > '2024-01-01';
SELECT * FROM users WHERE status = 'active';

-- НЕ использует индекс (нарушен порядок):
SELECT * FROM users WHERE created_at > '2024-01-01';

Правило префикса: составной индекс (a, b, c) работует для запросов по a, (a, b), (a, b, c), но не для b, c, (b, c).

Частичные индексы (Partial Index)

-- Индекс только для активных пользователей
CREATE INDEX idx_active_users_email ON users(email) WHERE status = 'active';

-- Меньше размер, быстрее обновление

Когда индексы не используются

Маленькие таблицы (seq scan быстрее)
Запрос возвращает >10-20% строк
Функции над индексированным столбцом: WHERE lower(email) = 'test@example.com'
Неявное приведение типов: WHERE id = '123' (id — int)

Анализ использования

-- PostgreSQL
EXPLAIN ANALYZE SELECT * FROM users WHERE email = 'test@example.com';

-- MySQL
EXPLAIN SELECT * FROM users WHERE email = 'test@example.com';

Вопрос 1. Расскажи, что ты знаешь о слайсах (slices) в Go.​

Вопрос 2. Если взять срез от слайса и изменить элемент в срезе, изменится ли исходный слайс?​

Вопрос 3. Если передать слайс в функцию, которая добавит в него элемент, будет ли видна эта мутация в исходной функции (например, main)?​

Вопрос 4. Что не так в коде с каналами и горутинами, где создаётся небуферизированный канал, запускается горутина-читатель, а запись в канал происходит в main?​

Вопрос 5. Что такое deadlock в контексте Go?​

Вопрос 6. Исправь код с каналами и горутинами, чтобы он выводил 1, 2, 3 и корректно завершался.​

Вопрос 7. Что такое горутина (goroutine) и какие у неё преимущества перед потоками ОС?​

Вопрос 8. Какие способы коммуникации между горутинами существуют? Расскажи про каналы — что они из себя представляют изнутри.​

Вопрос 12. Что выведет код с fmt.Println, если GOMAXPROCS=1 и если GOMAXPROCS>1? Код запускает 3 горутины, каждая пишет строку в слайс, затем WaitGroup.Wait() и печать слайса.​

Вопрос 13. Что такое консистентное хеширование (consistent hashing) и зачем оно нужно? Какую проблему шардирования оно решает?​

Вопрос 14. Что такое паттерн Raft и как он решает проблему выбора нового мастера при падении текущего в репликации?​

Вопрос 15. Объсни разницу между репликацией и шардированием. К какому типу масштабирования относится каждый из них — вертикальному или горизонтальному?​

Вопрос 16. Что такое паттерн Transactional Outbox и как он решает проблему атомарности при отправке событий в брокер сообщений?​

Вопрос 17. Зачем нужны индексы в базах данных? Какие типы индексов существуют и какие у них плюсы и минусы?​

Вопрос 1. Расскажи, что ты знаешь о слайсах (slices) в Go.

Вопрос 2. Если взять срез от слайса и изменить элемент в срезе, изменится ли исходный слайс?

Вопрос 3. Если передать слайс в функцию, которая добавит в него элемент, будет ли видна эта мутация в исходной функции (например, main)?

Вопрос 4. Что не так в коде с каналами и горутинами, где создаётся небуферизированный канал, запускается горутина-читатель, а запись в канал происходит в main?

Вопрос 5. Что такое deadlock в контексте Go?

Вопрос 6. Исправь код с каналами и горутинами, чтобы он выводил 1, 2, 3 и корректно завершался.

Вопрос 7. Что такое горутина (goroutine) и какие у неё преимущества перед потоками ОС?

Вопрос 8. Какие способы коммуникации между горутинами существуют? Расскажи про каналы — что они из себя представляют изнутри.

Вопрос 12. Что выведет код с fmt.Println, если GOMAXPROCS=1 и если GOMAXPROCS>1? Код запускает 3 горутины, каждая пишет строку в слайс, затем WaitGroup.Wait() и печать слайса.

Вопрос 13. Что такое консистентное хеширование (consistent hashing) и зачем оно нужно? Какую проблему шардирования оно решает?

Вопрос 14. Что такое паттерн Raft и как он решает проблему выбора нового мастера при падении текущего в репликации?

Вопрос 15. Объсни разницу между репликацией и шардированием. К какому типу масштабирования относится каждый из них — вертикальному или горизонтальному?

Вопрос 16. Что такое паттерн Transactional Outbox и как он решает проблему атомарности при отправке событий в брокер сообщений?

Вопрос 17. Зачем нужны индексы в базах данных? Какие типы индексов существуют и какие у них плюсы и минусы?