---
title: Конспект материала 31 — system-design-algorithms (resumejob)
source: https://github.com/resumejob/system-design-algorithms
author: resumejob — «System design algorithms»: один README — чек-лист из 18 алгоритмов/структур «для подготовки к SD-интервью»; каждый пункт — определение в 1–2 предложения + 1–3 ссылки на бесплатные тексты; критерий отбора — «алгоритм отвечает на вопрос интервью» (пример: статья Twitter «Building a complete Tweet index» = ответ на «как сделать Twitter search/hashtag»)
конспект: подготовлено 2026-09-18, TASK-45.35; README прочитан целиком, все 18 позиций сверены с KB / articles / classic-designs / конспектами серии 45.12–45.34
статус: как учебник — P3, почти всё покрыто сильнее; уникальный жанр — **двухуровневый чек-лист владения алгоритмом**: «know when to use» (☑️, 5 позиций) и «know how it works» (✅, 13 позиций). Готовый трекер самопроверки «алгоритм → домен-вопрос → трейдофф» на 15–20 минут. Сверка: 14/18 уже в базе, 3 лакуны внесены в KB (§13.6, §14.5, §14.6), 1 (frugal streaming) — P3-академика, оставлена в этом конспекте
---

# Материал 31: system-design-algorithms — чек-лист алгоритмов

## 1. Что это (и что это НЕ)

Репозиторий-каталог: README с 18 алгоритмами и структурами, которые автор считает обязательными для SD-интервью. Каждый пункт: короткое определение + ссылки (текст ценится выше видео, всё бесплатное). Три правила отбора заявлены в README: алгоритм должен **отвечать на конкретный вопрос интервью** («How to design Uber?» → geohash/S2), быть бесплатным и предпочтительно текстовым. Кода и разборов в репо нет — это индекс, не учебник.

Главная ценность для нас — **уровневая маркировка владения**: ☑️ «know when to use» (узнавать ситуацию и назвать алгоритм) против ✅ «know how it works» (объяснить механику и трейдофф). Это готовая шкала самооценки: на секции достаточно ☑️-уровня почти для всего, ✅ — только для того, что попадает в наш бриф (rate limiting, хранение, консенсус, гео).

## 2. Список: 18 позиций и где они у нас

### 2.1 ✅ Know how it works (13) — уметь объяснить механику

| # | Алгоритм | Суть одной строкой | Интервью-домен («отвечает на вопрос») | Где у нас |
|---|---|---|---|---|
| 1 | **Bloom filter** | «элемент в множестве?» быстро и дёшево; ложные срабатывания, удалений нет | дедуп URL в краулере; отсечение чтения несуществующих ключей в LSM | ✅ KB §3.1, §14.2 (29 % дублей) |
| 2 | **Consistent hashing** | кольцо + виртуальные ноды: при уходе/добавлении узла переезжает ~1/N ключей | перекладка шардов/кэша без даунтайма; stateful-роутинг | ✅ KB §6, §13.2; кейсы Discord/Slack (45.33) |
| 3 | **Geohash / S2 Geometry** | гео-ячейки: nearby-поиск и «точка → ячейка → шард» | «design Uber»: ближайшие водители, гео-шардирование | ✅ KB §13.6; S2 — добавлен (§3 ниже) |
| 4 | **2PC** | prepare/commit через координатора: все коммитят или все абортят | «а как транзакция на два сервиса?» — сказать и сразу про саги | ✅ KB §7 (+ saga, NewSQL, in-doubt) |
| 5 | **Exponential backoff** | пауза ретрая растёт экспоненциально (+ jitter), не добиваем упавшего | ретраи, retry storm, metastable failure | ✅ KB §9, articles/08 |
| 6 | **SSTable** | иммутабельные отсортированные файлы на диске + компактация | «почему Cassandra пишет быстро?» — LSM-семейство | ✅ KB §3.1, DDIA гл. 4 (45.39) |
| 7 | **Leaky / token bucket** | корзина-скорость: ровный поток vs burst с двумя параметрами | rate limiter — классика этапа 4 | ✅ KB §14.1 (таблица 5 алгоритмов + Redis+Lua) |
| 8 | **Inverted index** | term → список документов с ним | поиск, хэштеги, Twitter search | ✅ KB §2 (Search), §14.4; Tweet index — тот же жанр |
| 9 | **Distributed consensus (Paxos/Raft)** | кворум + эпохи: узлы договариваются о значении несмотря на отказы | leader election, координация, реплицированный лог | ✅ KB §7 (механика + ZooKeeper/etcd/fencing) |
| 10 | **Cache eviction (LRU/LFU/FIFO)** | кого выкидывать при переполнении | «а что если кэш переполнен?» | ✅ KB §4 (LRU дефолт, LFU неравномерные) |
| 11 | **Rsync algorithm** | rolling checksum: передать только отличающиеся блоки файла | дельта-синхронизация файлов (Dropbox/Drive) | ⚠️ §14.5 есть «дельта» без механики → **внесено** (§3) |
| 12 | **HyperLogLog** | счёт уникальных приближённо: ~0,8 % ошибки при 12 КБ на ключ | уникальные посетители/запросы/DAU без гигантских счётчиков | ❌ лакуна → **внесено в KB §14.6** |
| 13 | **Trie** | префиксное дерево: поиск за O(длина ключа) | автодополнение/typeahead | ✅ KB §14.4 (+ топ-k в узлах) |

### 2.2 ☑️ Know when to use (5) — достаточно узнать ситуацию и назвать

| # | Алгоритм | Когда применять одной строкой | Где у нас |
|---|---|---|---|
| 14 | **Lossy counting** | частые элементы потока (частота > порога) за O(1/ε) памяти; Cloudflare так считает rate limiting на миллионы доменов | ⚠️ Count-Min назван в articles/10 → **внесено в KB §14.6** |
| 15 | **Frugal streaming** | квантиль на группу одной ячейкой памяти | ❌ академика, вне брифа — оставлено здесь (P3) |
| 16 | **Operational transformation** | коллаборативное редактирование (Google Docs): операции с трансформацией против параллельных правок | ✅ articles/11 («OT vs CRDT — назвать трейдофф»), 45.31; вне брифа |
| 17 | **Quadtree / Rtree** | пространственный индекс: рекурсивное деление плоскости / дерево объёмов | ✅ KB §13.6 (geohash/QuadTree + R-деревья) |
| 18 | **Ray casting** | point-in-polygon: чётность пересечений луча — «точка → страна/регион» | ❌ лакуна → **внесено в KB §13.6** |

## 3. Сверка с базой знаний — что добавлено в 45.1

14 из 18 позиций уже покрыты KB/articles на уровне глубже этого репо (колонка «Где у нас»). Реальные лакуны — три, все внесены малыми правками:

1. **HyperLogLog + sketch-счётчики (главная лакуна)** — в KB нигде не было приближённых счётчиков. Добавлен §14.6 «Приближённые счётчики»: HLL (12 КБ / ~0,8 % / Redis PFADD-PFCOUNT), Count-Min + lossy counting (частоты и топ-k на потоке; кейс Cloudflare — rate limiting миллионов доменов), правило «деньги/аудит — точный счёт, метрики/лимиты — sketch с известной ошибкой». Стыкуется с §14.1 (лимиты) и §14.4 (топ-k агрегаторы).
2. **Механика дельта-синхронизации (rsync)** — §14.5 говорил «передаём изменённые блоки» без «как». Добавлено: rolling checksum + хеши блоков; content-defined chunking делает границы блоков устойчивыми к вставкам (иначе вставка в начало файла инвалидирует все блоки).
3. **Ray casting + S2** — §13.6 дополнен: реверс-геокодинг «точка → страна» = point-in-polygon через ray casting; S2 (Google) назван рядом с geohash как тот же жанр ячеек на сфере.

Не внесено сознательно: **frugal streaming** (квантили одной ячейкой — академика, вне брифа, достаточно названия из этого конспекта) и **OT** (уже закрыт articles/11 одной фразой «назвать трейдофф, не углубляться»).

## 4. Что взять в подготовку

**Прогон таблицы §2 как трекера (15–20 минут)**: по каждой строке вслух — «вопрос-домен, где применяю, как работает, чем плачу». Шкала репо помогает честно разделить: что умею объяснить (✅) и что только узнаю (☑️). До слотов достаточно ☑️ везде и ✅ на позициях 1–2, 4–7, 9, 13 (ядро брифа: хранение, лимиты, консистентность, автодополнение).

Свежие для нас факты, которые приятно назвать на секции:
- HLL в Redis: PFADD/PFCOUNT/PFMERGE, 12 КБ на ключ, ошибка ~0,8 % — готовый ответ на «посчитать уникальных посетителей за месяц» вместо гигантского set.
- Cloudflare (lossy counting): подсчёт для rate limiting миллионов доменов без точных счётчиков на каждый домен — связка «sketch + лимиты» звучит как опыт.
- CDC/rsync: «вставка в начало файла не должна инвалидировать всё» — тонкость, которая отличает понимание от заучивания.

## 5. Чего не брать

- **Репо как план чтения** — ссылки дублируют то, что уже разобрано сильнее (Dropbox caching → KB §4; Tweet index → жанр инвертированного индекса; Trie-статьи → KB §14.4). Единственная стоит отдельного взгляда после секций: **«Building a complete Tweet index»** (Twitter Engineering, 2014) — цельный кейс «поиск по 400 млн твитов/день»: инвертированный индекс + early bird-шардирование.
- **Frugal streaming и Git-bloom-фильтры** — академика/экзотика, вне брифа.
- **Считать репо учебником по механике** — определения в 1–2 предложения; глубина у нас в KB и DDIA.

## Связанные документы

- `../knowledge-base.md` — §3.1 (Bloom/SSTable/LSM), §4 (eviction), §6 (consistent hashing), §7 (2PC/консенсус), §9 (backoff), §13.6 (гео: + ray casting, S2), §14.1 (buckets), §14.4 (trie), §14.5 (rsync-механика), **§14.6 (sketch-счётчики — новый)** 
- `../articles/10-components-patterns.md` — Count-Min для топ-k (теперь продублирован в KB §14.6)
- `lsd-interviewready-resources.md` (45.31) — там же ссылка на OT + HLL из списка InterviewReady
- `lsd-master-plan.md` (45.34) — второй чек-лист серии: темы (здесь — алгоритмы); удобен общий прогон перед слотом