Модуль 21 ⏱ ~14 мин чтения 📐 1 Mermaid диаграмм

1. Теория. Потоковые алгоритмы

«В потоке данных вы не можете позволить себе роскошь оглянуться назад: либо вы поняли суть на лету, либо она потеряна навсегда».
— Брайан Керниган

Потоковые алгоритмы: обработка бесконечных данных в ограниченной памяти

Потоковые алгоритмы (Streaming Algorithms) предназначены для обработки непрерывных потоков данных, размер которых $N$ заранее неизвестен или настолько колоссален, что данные физически невозможно сохранить на диске или в оперативной памяти.

Ключевые ограничения потоковой модели:

  1. Строго однопроходный режим (One-Pass Processing): каждый входящий элемент считывается ровно один раз.
  2. Сублинейная память: расход оперативной памяти ограничен константой $O(1)$ либо логарифмической шкалой $O(\text{polylog}(N))$ или $O(\varepsilon^{-1})$.
  3. Минимальная латентность: обработка каждого элемента обязана укладываться в единицы или десятки наносекунд.

В современной инфраструктуре потоковые алгоритмы лежат в фундаменте систем мониторинга (Prometheus, VictoriaMetrics), распределенных брокеров (Apache Kafka), брокеров сетевой безопасности (детекция DDoS, L7 rate-limiting) и аналитических СУБД (ClickHouse).

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{"Требуется ли 100% точность?"}:::warning
    B -->|"Да"| C["Детерминированные алгоритмы<br/>Скользящее окно, Two Heaps, Misra-Gries"]:::process
    B -->|"Нет"| D["Вероятностные скетчи<br/>HyperLogLog, Count-Min, t-Digest"]:::process
    C --> E["Память: O(K) или O(N/k)<br/>Строгие математические гарантии"]:::success
    D --> F["Память: O(1/eps)<br/>Контролируемая погрешность с дельта-вероятностью"]:::success

1. Фундаментальные задачи потоковой обработки

В потоковой обработке выделяют четыре классические задачи:

Задача Наивный подход Потоковое решение Потребление RAM Точность
Cardinality (Уникальные элементы) Хеш-таблица всех уникальных ключей (map[K]struct{}) HyperLogLog (HLL) 1.5 КБ (при ошибке $\approx 1\%$) Вероятностная ($\pm \varepsilon$)
Heavy Hitters (Частые элементы) Счётчик по каждому ключу (map[K]int) Misra-Gries / Count-Min Sketch Несколько килобайт Гарантированное превышение порога
Frequency Estimation (Оценка частоты) Полный словарь частот Count-Min Sketch (CMS) Фиксированная матрица $d \times w$ Никогда не занижает частоту
Quantiles & Percentiles (p50, p95, p99) Сохранение и сортировка массива ($O(N \log N)$) Two Heaps (точная медиана) / t-Digest / P² $O(K)$ или $O(1)$ Зависит от алгоритма

2. Архитектура Go: потоковый ввод-вывод и сборщик мусора

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

Буферизация и предотвращение аллокаций

Наивное чтение через bufio.Scanner с вызовом scanner.Text() выделяет новую строку в куче на каждой строке:

Go 
// ❌ ПЛОХО: 1 000 000 аллокаций в секунду вызовет деградацию GC
for scanner.Scan() {
    process(scanner.Text())
}

// ✅ ОТЛИЧНО: Zero-allocation потоковая обработка
for scanner.Scan() {
    lineBytes := scanner.Bytes() // Срез указывает на внутренний буфер scanner
    processBytes(lineBytes)      // Обработка без выделения памяти в куче
}

Итераторы Go 1.23+ (iter.Seq)

Начиная с Go 1.23, в язык встроена поддержка стандартных итераторов (iter.Seq), позволяющая создавать чистые конвейеры потоковой обработки без накладных расходов каналов (chansend/chanrecv) и блокировок планировщика:

Go 
package stream

import (
    "bufio"
    "io"
    "iter"
)

// ScanLinesSeq возвращает pull-итератор по строкам без создания горутин
func ScanLinesSeq(r io.Reader) iter.Seq[[]byte] {
    return func(yield func([]byte) bool) {
        scanner := bufio.NewScanner(r)
        for scanner.Scan() {
            if !yield(scanner.Bytes()) {
                return
            }
        }
    }
}

3. Backpressure и устойчивость систем

В распределенных потоковых системах критически важен механизм обратного давления (Backpressure).
Если генератор событий (Kafka, TCP-сокет) поставляет данные со скоростью $200\,000$ сообщений/сек, а процессор способен обработать только $100\,000$, буферы неизбежно переполнятся, вызвав аварийное завершение по OOM (Out Of Memory).

Способы управления давлением потока:

  1. Синхронное торможение (TCP Flow Control): приостановка чтения из сетевого сокета (net.Conn), заставляющая операционную систему заполнить TCP Receive Window и замедлить отправителя.
  2. Буферизованные каналы ограниченной емкости: блокировка горутины-продюсера при заполнении очереди.
  3. Вероятностное прореживание (Load Shedding): контролируемый сброс входящих пакетов при превышении порогового SLA очереди.

4. Вопросы для собеседования

Резюме

  1. Потоковые алгоритмы решают задачи анализа данных за один последовательный проход в условиях жестких ограничений памяти.
  2. Вероятностные скетчи жертвуют абсолютной точностью ради фиксированного расхода оперативной памяти ($O(1)$ или $O(\text{polylog} N)$).
  3. В Go потоковая производительность зависит от исключения лишних аллокаций (scanner.Bytes(), отсутствие упаковки в интерфейсы) и управления обратным давлением (Backpressure).

В следующей статье мы разберем поиск наиболее частых элементов в потоке с помощью алгоритмов Misra-Gries и Count-Min Sketch: 2. Heavy hitters.