caching
Кеширование
Как ускорять приложения, запоминая результаты вместо повторного вычисления — и самое сложное: понимать, когда запомненная копия устарела.
Начать трек →С нуля
Перед senior-материалом: что вообще такое кеш и горстка слов, которые остальной трек считает уже знакомыми.Уровни кэширования: от CPU до CDN
Как кэши выстраиваются от L1/L2/L3 через RAM, кэши приложений и CDN — и зачем нужен каждый уровень.Инвалидация кэша: самая сложная задача в CS
Стратегии вытеснения устаревших записей — TTL, event-driven purge, write-through, write-behind — и почему ошибка здесь портит состояние пользователя.Cache stampede: когда одно TTL истечение превращается в тысячи SQL-запросов
Почему одно истечение TTL превращает горячий ключ кеша в flash-DDoS против origin, и четыре механизма — локи, single-flight, XFetch и stale-while-revalidate — удерживающие БД в живых.ETag: условные запросы и ответы без тела
Как entity-теги включают conditional GET — сервер возвращает 304 Not Modified при неизменном контенте, экономя трафик и снижая задержку.Cache-Control: управление браузерами и CDN
Директивы — max-age, s-maxage, no-store, stale-while-revalidate — которые говорят каждому кэшу в цепочке, как долго хранить ответ.Stale-while-revalidate: отдать устаревшее, обновить в фоне
Как SWR разделяет свежесть и задержку — немедленно отдаёт закэшированную версию, а затем обновляет её тихо, устраняя пик tail-latency от синхронной ревалидации.Dogpile-эффект: одновременные промахи кэша, которые убивают origin
Когда популярный ключ истекает, все параллельные запросы промахиваются одновременно и нагружают базу данных — паттерн, отличие от stampede и как mutex-блокировки и вероятностное раннее истечение его предотвращают.Проектирование системы кэширования: объединение всех уровней
Как скомпоновать CDN, reverse-proxy, кэши приложения и базы данных в единую стратегию — выбор TTL, триггеров инвалидации и путей отказа, которые выдержат реальный трафик.Проекты по этому треку
Guided-проекты, которые закрепляют изученное здесь.
Фильтр Блума
Собери пространственно-эффективное вероятностное множество, отвечающее на запросы членства за O(1) с настраиваемой вероятностью ложных срабатываний, — и разберись, почему ложных отрицаний в нём быть не может принципиально.
Лаборатория cache stampede
Воспроизведи thundering-herd промах кэша под нагрузкой, затем убей его через single-flight и пересчёт с ранним истечением.
Прерыватель цепи
Собери прерыватель цепи, который прекращает долбить падающую зависимость, безопасно прощупывает её в состоянии half-open и автоматически восстанавливается — именно этот паттерн не даёт каскаду микросервисов превратить один плохой узел в полный простой.
Кольцо consistent hashing
Собери кольцо на виртуальных узлах, которое перераспределяет минимальный набор ключей при появлении или уходе узла — базовый примитив за Dynamo, Cassandra и каждым шардированным кэшем, который должен пережить ротацию узлов без полного перебалансирования.
Кодирование Хаффмана
Собери lossless-компрессор с нуля: постройте оптимальное дерево prefix-free кодов снизу вверх, выведи битовые строки и докажи, что round-trip точен, а результат короче кодирования фиксированной шириной.
LRU-кэш
Собери LRU-кэш с вытеснением за O(1) на связке хешмапы и двусвязного списка — та самая задача, которая показывает, почему вытеснение из кэша сложнее, чем кажется.
Распределённый rate limiter
Собери token-bucket лимитер, который держится поперёк многих инстансов приложения за счёт счётчика в Redis, а не в памяти процесса.
Список с пропусками
Реализуй вероятностную упорядоченную структуру данных, которая обеспечивает O(log n) поиск, вставку и удаление без балансировочной бухгалтерии деревьев — только слоистые «экспресс-полосы» через отсортированный связный список.
Текстовый diff — алгоритм Майерса
Реализуй алгоритм diff Майерса с нуля: вычисли наибольшую общую подпоследовательность, построй edit script обратным ходом, докажи минимальность и применяй патчи так, чтобы любой round-trip был побайтово точным.
Планировщик сборки на топологической сортировке
Собери планировщик задач на основе DAG — как Make или CI-пайплайн — который упорядочивает задачи по зависимостям, обнаруживает циклы до дедлока и определяет, какие задачи можно выполнять параллельно.
Движок автодополнения на основе trie
Собери префиксное дерево для ранжированного автодополнения — вставляй слова с весами, проходи каждый префикс за O(длина_префикса + результаты) и детерминированно разрешай ничьи без базы данных.
Union-Find (система непересекающихся множеств)
Построй структуру непересекающихся множеств от наивного массива родителей до почти константного амортизированного времени — и прими на ней алгоритм Краскала для поиска минимального остовного дерева.
URL-сокращатель под нагрузкой
Собери URL-сокращатель, который выдерживает настоящий трафик, — а потом эксплуатируй его: задеплой, наблюдай и разберись с инцидентом, когда одна горячая ссылка плавит твой кэш.
Очереди, потоки, события
Как части системы передают работу через очереди сообщений, а не ждут друг друга — чтобы оставаться быстрыми и пережить сбой, не потеряв ни одного сообщения.