Всем привет! Для начала давайте разберем что такое вообще Алгоритмы для работы с большими данными, основная суть алгоритмов для работы с большими данными  — это эффективная обработка огромных объёмов информации при минимальных вычислительных ресурсах (памяти, CPU, диске). Их суть — жертвовать точностью ради скорости и масштабируемости. Примеры:

• Потоковая обработка

• Распределённые системы (агрегация на многих узлах).

• Реал‑тайм аналитика (быстрые ответы на лету).

Главные алгоритмы и их суть

В этой статье я разбираю HyperLogLog и Count-Min Sketch.

HyperLogLog

Алгоритм HyperLogLog стал одним из наиболее эффективных инструментов для оценки количества уникальных элементов в больших наборах данных . Его ключевое преимущество заключается в способности обеспечивать высокую точность при минимальном использовании памяти.

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

В стандартной библиотеке Go используется функция crc32 из пакета hash, которая служит базовым инструментом для генерации хэшей. Например, если необходимо оценить количество уникальных IP‑адресов пользователей на высокотрафиковых сайтах, можно использовать эту функцию для расчета хэшей каждого адреса. Тем не менее, для более производительных решений предпочтение отдается современным хэш‑функциям, таким как murmur3 или xxhash, которые обеспечивают лучшее распределение данных и меньшую вероятность коллизий.

Одним из ключевых преимуществ реализации является ее гибкость: пользователи могут выбирать между различными уровнями точности, изменяя количество регистров от 2^4(16 байт) до 2^18(256 КБ). Современные улучшения алгоритма HyperLogLog, такие как HyperLogLog++, предлагают дополнительные преимущества, включая использование 64-битной хэш‑функции вместо 32-битной, что снижает вероятность коллизий и позволяет оценивать множества, содержащие миллиарды элементов.

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

package main

import (
	"fmt"
	"hash/fnv"
	"math"
	"math/rand"
	"strconv"
)

const (
	m = 1024 // количество регистров. Это основной параметр, влияющий на точность.
	b = 8  // число бит, используемых для определения индекса регистра из хэша.
)

type HyperLogLog struct {
    // при асинхронном взаимодействии стоит подумать о мьютексах
	registers [m]byte
}

func NewHyperLogLog() *HyperLogLog {
	return &HyperLogLog{}
}

// hash возвращает два 32-битных числа из строки
func hash(s string) (uint32, uint32) {
	h := fnv.New64a()
	h.Write([]byte(s))
	v := h.Sum64()

	// Перемешиваем биты, чтобы улучшить распределение
	w := uint32(v >> 32)
	z := uint32(v)

	// Добавляем перемешивание, улучшает качество случайности и помогает избежать проблем с плохим распределением хэшей
	w ^= z<<13 | z>>(32-13)
	z ^= w<<7 | w>>(32-7)
	w ^= z<<17 | z>>(32-17)

	return w, z
}

// Считает количество нулей слева в двоичной записи числа,
// eсли все биты — нули, возвращается 32.
func countLeadingZeros(x uint32) byte {
	for i := 0; i < 32; i++ {
		if (x>>(31-i))&1 == 1 {
			return byte(i)
		}
	}
	return 32
}

// Хэшируем строку.
// Берём часть хэша h1, чтобы определить, в какой регистр попадёт элемент.
// По второй части h2 считаем, сколько ведущих нулей (rho), прибавляем 1.
// Если это значение больше, чем уже есть в регистре — обновляем его.
func (hll *HyperLogLog) Add(s string) {
	h1, h2 := hash(s)

	// определяем индекс регистра
	idx := h1 % m

	// вычисляем значение для обновления регистра
	rho := countLeadingZeros(h2) + 1

	if rho > hll.registers[idx] {
		hll.registers[idx] = rho
	}
}

// Сложные формулы, по сути эта функция
// делает оценку количества уникальных элементов
func (hll *HyperLogLog) Estimate() float64 {
	sum := 0.0
	for _, val := range hll.registers {
		sum += 1 / math.Pow(2, float64(val))
	}
	estimate := alpha(m) * m * m / sum

	// коррекция для малых значений, используется метод
	// Linear Counting : чем больше нулевых регистров — тем
	// меньше реальная кардинальность.
	if estimate <= 5*m/2 {
		zeros := 0
		for _, val := range hll.registers {
			if val == 0 {
				zeros++
			}
		}
		if zeros != 0 {
			estimate = float64(m) * math.Log(float64(m)/float64(zeros))
		}
	}

	return estimate
}

// alpha — поправочный коэффициент, компенсирующий систематическую ошибку
func alpha(m int) float64 {
	switch m {
	case 16:
		return 0.673
	case 32:
		return 0.697
	case 64:
		return 0.709
	default:
		return 0.7213 / (1 + 1.079/float64(m))
	}
}

func main() {
	// Создаём HLL.
	hll := NewHyperLogLog()

	seen := make(map[string]struct{})
	for i := 0; i < 1_000_000; i++ {
		key := strconv.Itoa(rand.Intn(1_000_000))
		seen[key] = struct{}{}
		hll.Add(key)
	}

  	nonZero := 0
	for _, r := range hll.registers {
		if r > 0 {
			nonZero++
		}
	}
  
	fmt.Printf("Реальное количество уникальных элементов: %d\n", len(seen))
	fmt.Printf("Оценка уникальных элементов: %.2f\n", hll.Estimate())
	fmt.Printf("Заполненных регистров: %d/%d\n", nonZero, m)
}

Результаты

Для 1 000 000 вставок

Относительная ошибка: 0.84% (запускал несколько раз и это лучший результат, теоретическое значение ошибки 3.25%)

Память: 1 KB

Производительность: O(1) на добавление, O(m) на оценку

Count-Min Sketch

Count‑Min Sketch представляет собой вероятностную структуру данных, предназначенную для приближенного подсчета частот элементов в потоке данных. Она основана на использовании двухмерной таблицы счетчиков размером d строк и w столбцов, где каждое обновление увеличивает значения по индексам, рассчитанным с помощью хэш‑функций.

Процесс обновления счетчиков в Count‑Min Sketch использует несколько хэш‑функций и минимизирует влияние коллизий за счет выбора минимального значения среди всех строк для каждого элемента. Например, если элемент должен быть обновлен, его хэш‑значения вычисляются для каждой строки, и соответствующие счетчики увеличиваются. При запросе частоты элемента алгоритм выбирает минимальное значение среди всех строк, связанных с этим элементом, чтобы минимизировать влияние коллизий. Это обеспечивает высокую эффективность использования памяти, особенно для больших потоков данных, где точные методы подсчета становятся непрактичными.

Count‑Min Sketch активно предлагает три метода запросов: минимум (наиболее точный), среднее (полезно при удалении элементов) и count‑mean‑min (учитывает смещение). Первый метод берет минимальное значение из всех строк, второй вычисляет среднее значение по всем строкам, а третий корректирует шум для каждой строки и затем вычисляет медиану значений.

Одним из примеров применения Count‑Min Sketch является анализ сетевого трафика, где требуется отслеживать частоты IP‑адресов или URL в реальном времени. Другой пример — анализ текстовых данных, таких как корпус новостных статей большим объемом в десятки миллионов слов, где Count‑Min Sketch помогает определить частоту слов с ограниченным использованием памяти.

Пример реализации в GO

package main

import (
    "fmt"
    "hash/fnv"
    "math"
)

type CountMinSketch struct {
    width  int
    depth  int
    // при асинхронном взаимодействии стоит подумать о мьютексах
    table  [][]int
    hashes []uint64
}

func NewCountMinSketch(width, depth int) *CountMinSketch {
    return &CountMinSketch{
        width:  width,
        depth:  depth,
        table:  make([][]int, depth),
        hashes: make([]uint64, depth),
    }
}

func (cms *CountMinSketch) Init() {
    for i := range cms.table {
        cms.table[i] = make([]int, cms.width)
        cms.hashes[i] = uint64(i+1) // простые соли для разных хэшей
    }
}

// getHashIndex генерирует хэш и возвращает индекс в таблице
func (cms *CountMinSketch) getHashIndex(s string, seed uint64) int {
    h := fnv.New64a()
    h.Write([]byte(s))
    v := h.Sum64()

    // Перемешиваем биты с seed
    mixed := v ^ seed ^ (seed << 32)

    return int(mixed % uint64(cms.width))
}

// Add увеличивает счетчик для элемента
func (cms *CountMinSketch) Add(s string, count int) {
    for i := 0; i < cms.depth; i++ {
        idx := cms.getHashIndex(s, cms.hashes[i])
        cms.table[i][idx] += count
    }
}

// Count возвращает оценочное число вхождений элемента
func (cms *CountMinSketch) Count(s string) int {
    min := math.MaxInt32
    for i := 0; i < cms.depth; i++ {
        idx := cms.getHashIndex(s, cms.hashes[i])
        if cms.table[i][idx] < min {
            min = cms.table[i][idx]
        }
    }
    return min
}

func main() {
    width := 10_000
    depth := 5

    cms := NewCountMinSketch(width, depth)
    cms.Init()

    seen := make(map[string]int)
	for i := 0; i < 5_000_000; i++ {
		key := fmt.Sprintf("item-%d", i%1100)
		seen[key]++
		cms.Add(key, 1)
	}

  
    // выводим частоты
    for _, word := range []string{"item-1", "item-0", "item-1000", "item--1"} {
        fmt.Printf("Согласно cms слово '%s' встречается примерно %d раз\t По факту: %d\n", word, cms.Count(word), seen[word])
    }
}

Результаты

Для 5 000 000 вставок

Память: 200 KB

Производительность: O(depth) на добавление, O(depth) на запрос частоты

Итоги

Сравнение HLL и CMS

➕ Когда использовать

➖ Когда не использовать