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 на уровне глубже этого репо (колонка «Где у нас»). Реальные лакуны — три, все внесены малыми правками:
- 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 агрегаторы).
- Механика дельта-синхронизации (rsync) — §14.5 говорил «передаём изменённые блоки» без «как». Добавлено: rolling checksum + хеши блоков; content-defined chunking делает границы блоков устойчивыми к вставкам (иначе вставка в начало файла инвалидирует все блоки).
- 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 из списка InterviewReadylsd-master-plan.md(45.34) — второй чек-лист серии: темы (здесь — алгоритмы); удобен общий прогон перед слотом