1. Теория. Рандомизированные алгоритмы

«Случайность — слишком важная вещь, чтобы оставлять её на волю случая».
— Брайан Керниган

Философия рандомизации: детерминизм против вероятности в бэкенде

Рандомизированные алгоритмы — это не «случайный код», а строгий математический инструмент для усреднения худших случаев, распределения нагрузки, защиты от атак и создания эффективных вероятностных структур данных. В бэкенд-разработке они встречаются повсеместно: от QuickSort и Consistent Hashing до Bloom Filters, Rate Limiting с jitter и A/B-тестирования. Понимание того, как генераторы псевдослучайных чисел (ГПСЧ) работают под капотом, как они влияют на кэш процессора, системные вызовы ядра Linux и сборщик мусора, отличает инженера, который «вызывает rand.Int()», от архитектора, который проектирует предсказуемые высоконагруженные системы.

flowchart TD
    classDef process fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef success fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
    classDef error   fill:#7f1d1d,stroke:#f87171,stroke-width:1px,color:#f8fafc
    classDef warning fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
    classDef entry   fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc

    A["Алгоритмическая задача"]:::entry --> B{"Требуется ли абсолютная точность?"}:::warning
    B -->|"Да, но время варьируется"| C["Алгоритмы Лас-Вегас<br/>Всегда верный результат<br/>Сложность случайна O(1)..O(N)"]:::process
    B -->|"Нет, допустима погрешность"| D["Алгоритмы Монте-Карло<br/>Гарантированное время O(1)<br/>Вероятность ошибки < epsilon"]:::process
    C --> E["Randomized QuickSort, Skip List"]:::success
    D --> F["Bloom Filter, HyperLogLog, Count-Min"]:::success
  

В этой статье мы разберем, почему рандомизация спасает от worst-case сценариев, как устроены ГПСЧ в Go 1.22+, почему crypto/rand на порядки медленнее math/rand/v2, как избежать модульного смещения (modulo bias) и какие ловушки ждут на технических собеседованиях.

1. Источники энтропии: от аппаратного шума до пространства пользователя

Истинная случайность в цифровом компьютере невозможна без внешнего физического источника. В архитектуре операционных систем мы работаем с двумя принципиально разными категориями:

1. Аппаратная энтропия и криптографические ГСЧ:
   Сбор шума терморезисторов, джиттера сетевых прерываний и квантовых флуктуаций контроллеров (/dev/urandom в Linux, getrandom(2) syscall). В Go за это отвечает пакет crypto/rand. Он гарантирует криптографическую стойкость (невозможность предсказать следующее число по предыдущим), но требует переключения контекста в ядро (syscall overhead).
2. Псевдослучайные генераторы (PRNG):
   Детерминированный математический алгоритм, преобразующий короткое начальное состояние (seed) в длинную квазислучайную последовательность. В Go это пакеты math/rand и math/rand/v2. Работает полностью в пространстве пользователя (User Space), без системных вызовов, удерживая состояние в регистрах процессора и кэше L1.

2. Модульное смещение (Modulo Bias) и rejection sampling

Классическая ошибка многих программистов: получение случайного числа в диапазоне $[0, N)$ через взятие остатка от деления:

val := rand.Int() % N // ❌ ОШИБКА: Modulo Bias

Если диапазон генератора (например, $2^{64}$) не делится нацело на $N$, числа в начале интервала будут выпадать статистически чаще, чем в конце. При больших объемах данных в распределенных системах это приводит к неравномерному шардированию и горячим партициям (Hot Spots).

Go 1.22+ решает это на уровне рантайма через Rejection Sampling в функции rand.IntN(n):

// Логика Rejection Sampling без смещения
func IntN(n int) int {
    v := rand.Uint64()
    if n&(n-1) == 0 { // Если n — степень двойки
        return int(v) & (n - 1) // Быстрая битовая маска за 1 такт CPU
    }

    // Отбрасываем хвост диапазона, чтобы исключить смещение
    threshold := (1<<64 - 1) - (1<<64-1)%uint64(n)
    for v >= threshold {
        v = rand.Uint64() // Повторная генерация
    }
    return int(v % uint64(n))
}

3. Потокобезопасность и конкурентность генераторов

Глобальный генератор math/rand/v2 потокобезопасен (внутри используется атомарный CAS или мьютекс). Однако в горячих путях микросервисов (миллионы RPS) конкуренция за глобальный генератор порождает кэш-контеншн на ядрах CPU.

Для максимальной пропускной способности в высоконагруженных сервисах применяется пул генераторов sync.Pool:

package random

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

var rngPool = sync.Pool{
    New: func() any {
        // Инициализируем генератор с уникальным сидом из криптографического источника
        return rand.New(rand.NewPCG(rand.Uint64(), rand.Uint64()))
    },
}

func FastIntN(n int) int {
    rng := rngPool.Get().(*rand.Rand)
    res := rng.IntN(n)
    rngPool.Put(rng)
    return res
}

4. Сравнение производительности: math/rand/v2 vs crypto/rand

5. Рандомизация в системном бэкенд-дизайне

1. Jitter при повторных попытках (Exponential Backoff with Jitter):
   Если сервис падает, тысячи клиентов с детерминированным интервалом повтора штурмуют сервер синхронно (Thundering Herd Problem). Добавление случайного разброса:
   $$\text{sleep} = \text{backoff} + \text{rand.IntN}(\text{backoff})$$
   размазывает пики нагрузки по времени и предотвращает каскадные отказы.
2. Вероятностные фильтры (Bloom Filter & Cuckoo Filter):
   Используют $k$ независимых псевдослучайных хеш-функций для проверки принадлежности элемента множеству за константное время при экономии $99\%$ памяти.
3. Резервуарная выборка (Reservoir Sampling):
   Позволяет отобрать $K$ равновероятных элементов из бесконечного потока событий без сохранения потока в памяти.

Резюме

1. Рандомизация переводит алгоритмическую сложность из жесткой зависимости от худших входных данных в плоскость математического ожидания.
2. math/rand/v2 в Go 1.22+ на базе PCG работает в User Space за единицы наносекунд и не создает давления на GC.
3. Всегда используйте rand.IntN(n) вместо оператора остатка от деления % для исключения модульного смещения.
4. В конкурентных сетевых сервисах используйте sync.Pool для локальных экземпляров rand.Rand.

В следующей статье мы разберем практическую реализацию равновероятной выборки из потока неизвестного размера: 2. Reservoir sampling.