CS Notes

index

6 min read

Компьютерные науки от бит до распределённых систем

Предпосылки: нет.

Компьютер работает с двумя состояниями электрического сигнала. Из этого ограничения вырастает всё остальное: числа и текст, процессор и оперативная память, операционная система, сети, базы данных, распределённые системы. На каждом новом уровне возвращаются одни и те же компромиссы — скорость против надёжности, последовательный доступ против случайного, простота против параллелизма, — но уже в другом масштабе и с другой ценой ошибки.

Эти материалы показывают связи между уровнями. Каждая заметка объясняет, какую задачу решает концепция, какой ценой и где она ломается. Порядок внутри домена выстроен так, чтобы следующая тема отвечала на вопрос, который создала предыдущая.

Как читать

Предпосылки — контракт знания. В начале каждой заметки перечислено всё, что текст считает известным. Если термин встречается в заметке, но его нет ни в Предпосылки, ни в самом тексте — это ошибка, а не скрытое знание. Всё техническое, чего в Предпосылки нет, заметка обязана ввести сама.

Ссылки стоят на каждом содержательном упоминании термина, а не только на первом. Это делает каждую точку текста входом: можно открыть заметку с середины и сразу перейти к нужному контексту. Для длинных страниц ссылка ведёт на конкретный заголовок, а не на файл целиком.

Навигация между заметками. Граф в правом верхнем углу показывает связи текущей заметки с соседями. Backlinks в конце заметки показывают, откуда на неё ссылаются.

Карта доменов

flowchart LR
    F["Основы представления<br/>данных"]
    P["Программирование"]
    A["Алгоритмы и<br/>структуры данных"]
    C["Архитектура<br/>компьютера"]
    N["Компьютерные сети"]
    L["Linux"]
    SQL["SQL"]
    PG["PostgreSQL"]
    MIG["Миграции"]
    RD["Redis"]
    SD["System Design"]
    MSG["Messaging"]
    RB["Ruby (WIP)"]
    RBI["Ruby VM<br/>внутреннее устройство"]
    RL["Rails"]

    F --> P
    P --> A
    P --> C
    P --> SQL
    P --> RB
    C --> L
    C --> RBI
    L --> RBI
    RB --> RBI
    SQL --> PG
    SQL --> MIG
    A --> RD
    L --> RD
    L --> PG
    A --> SD
    N --> SD
    PG --> SD
    RD --> SD
    SD --> MSG
    RB --> RL
    RD --> RL

Стрелки — направление «что читать до чего». Некоторые ветки независимы и могут идти параллельно: сети не требуют архитектуры компьютера или Linux; Ruby-язык (Ruby (WIP)) и Rails стоят поверх базового программирования, а Ruby VM внутреннее устройство дополнительно опирается на архитектуру компьютера и Linux; ACID — общий фундамент для PostgreSQL и Redis, читается до обеих.

Порядок изучения

Представление данных

Почему компьютер хранит числа именно так, откуда берётся 0.1 + 0.2 ≠ 0.3, как один и тот же байт может значить разное.

Программирование

Базовая модель программы: данные в памяти, управление, функции, объекты. Весь материал строго однопоточный — без async и без параллельных потоков, чтобы сначала закрепилась простая модель.

  • Программирование — от «что такое программа» через переменные, циклы, функции и коллекции до компиляции и обработки ошибок

Алгоритмы и структуры данных

Почти всё сводится к двум вопросам: по чему ищем элемент (по позиции или по ключу) и чем платим за скорость (копированием, указателями, промахами кэша процессора).

  • Алгоритмы и структуры данных — линейные структуры (массив, список, хеш-таблица, LRU), нелинейные (дерево, BST, куча, B-tree, skip list), динамическое программирование

Как компьютер выполняет программу

Две оси: путь данных (регистры, кэш, оперативная память, диск, шины) и программная модель процессора (набор команд, соглашения о вызовах, атомарные инструкции).

Операционная система

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

  • Linux — процессы и потоки, виртуальная память, файловые дескрипторы, планировщик, сокеты, мультиплексирование ввода-вывода, контейнеры

Сети

Путь пакета снизу вверх: от битов в проводе до HTTP-запросов и инфраструктуры интернета.

Базы данных

SQL как язык доступа к реляционной модели, общая теория транзакций и две конкретные СУБД с принципиально разной архитектурой.

  • ACID — контракт транзакции: атомарность, согласованность, изоляция, надёжность
  • SQL — реляционная модель, запросы, DDL, модификация, PG-специфика
  • PostgreSQL — физическое хранение, WAL, MVCC, буферный кэш, индексы, планировщик
  • Redis — однопоточный event loop, структуры данных в памяти, атомарность, персистентность, распределение, паттерны
  • Миграции — безопасные изменения схемы под трафиком, expand-contract, backfilling

Распределённые системы

Что ломается, когда данные перестают помещаться в один процесс, и какие компромиссы появляются взамен.

  • System Design — CAP, модели консистентности, репликация, шардинг, load balancing, кэширование, гарантии доставки, API, микросервисы, event-driven architecture
  • Messaging — Kafka как распределённый лог событий

Ruby и Rails

Конкретный язык, на котором написаны примеры в разделе «Программирование», и фреймворк, сводящий вместе Redis, фоновые задачи и практические сценарии.

  • Ruby (WIP) — системного описания языка ещё нет; два готовых раздела ниже — про реализацию VM
  • Ruby VM внутреннее устройство — парсер, YARV, объектная модель, методы, коллекции, GC, JIT, конкурентность (GVL, Fiber, Ractor); опирается на computer и linux
  • Rails — Redis в Rails-приложении, Sidekiq (архитектура, жизненный цикл задачи, гарантии, retry)

Как всё связано

Латентность против надёжности. Один и тот же компромисс возвращается на каждом уровне. В файловой системе fsync гарантирует запись на диск, но стоит миллисекунды. В PostgreSQL WAL пишется до изменения страниц, и каждый COMMIT платит за fsync журнала. В распределённых очередях подтверждение доставки превращает at-most-once в at-least-once, но каждое сообщение стоит дополнительного round-trip. Цена одинакова по смыслу, хотя отличается на порядки величин.

Последовательный доступ против случайного. В оперативной памяти последовательный доступ на порядок быстрее случайного из-за предсказания и открытых банков. В хранилище разрыв вырастает до двух-трёх порядков. Базы данных строятся вокруг этого факта: WAL — журнал, который пишется последовательно, чтобы не платить за seek при каждом COMMIT; Kafka — распределённый лог, где sequential I/O обеспечивает throughput, сопоставимый с in-memory решениями, при retention в терабайты.

Изоляция против совместного использования. Одна и та же задача — «пусть несколько единиц работы идут параллельно, не ломая данные друг друга» — решается на трёх масштабах. Процессы и потоки в операционной системе: процесс изолирован виртуальной памятью, поток дешевле, но разделяет адресное пространство и требует синхронизации. Транзакции в базе: уровни изоляции — это спектр компромиссов между строгостью и стоимостью. Микросервисы в распределённой системе: независимость команд ценой сетевых вызовов вместо методов и saga вместо транзакции.

Стоимость чтения против стоимости записи. Индексы ускоряют чтение, но замедляют каждую запись. Кэш делает то же самое на другом уровне. Read replicas масштабируют чтение, sharding — запись. B-tree оптимизирован под чтение, LSM-tree — под запись. Каждый выбор сдвигает баланс в одну сторону, и вопрос «что оптимизировать» определяется профилем нагрузки, а не эстетикой.

Graph View