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

Кэширование в ОС

Каждую секунду современный компьютер делает миллиарды обращений к памяти. Без кэшей процессор простаивал бы 99% времени, ожидая данных из RAM. Без page cache каждое чтение файла занимало бы миллисекунды вместо микросекунд. **Кэширование - это причина, почему современные системы работают.** RAM быстрее диска в 100,000 раз, но L1 кэш быстрее RAM в 100 раз. Эти слои - невидимые, но абсолютно критичные для производительности.

**Почему PostgreSQL требует огромный RAM?** База на 100 GB с 16 GB RAM работает в 10x быстрее, чем с 4 GB. Page cache держит горячие данные в памяти - повторные запросы мгновенны. Сервер с 512 GB RAM может кэшировать всю БД целиком.
**Как Redis достигает миллион операций/сек?** Вся БД в RAM, нулевые дисковые обращения. Плюс CPU cache locality: ключи в hash table расположены компактно. L1/L2 cache hit rate > 95% → латентность < 1 микросекунда.
**Почему huge pages критичны для виртуализации?** VM с 64 GB памяти генерирует миллионы TLB miss'ов. Huge pages (2 MB) сокращают TLB записи в 512 раз → TLB miss rate падает с 20% до 0.1%. Производительность VM: +30-50%.

Цели урока

Знать иерархию по латентности: L1 ~1ns, L2 ~3ns, L3 ~12ns, RAM ~100ns
TLB: hit rate >99%, miss → page table walk на десятки ns
Page cache: Linux кеширует все read/write через RAM по умолчанию
Buffer cache: метаданные FS (inodes, directory entries)
Применять fadvise/madvise для подсказок ядру о паттерне доступа

CPU Cache: иерархия памяти

**CPU cache** - это сверхбыстрая память внутри процессора, которая скрывает латентность доступа к RAM. Без кэша каждое обращение к памяти занимало бы ~100 наносекунд (сотни тактов CPU). С кэшем - 1-4 наносекунды. Разница в **100 раз**.

Процессор работает на частоте ~4 GHz (один такт = 0.25 наносекунды). Обращение к RAM занимает ~300 тактов. Если бы каждая инструкция ждала данных из памяти - CPU простаивал бы 99% времени!

**Cache line (строка кэша)** - минимальная единица кэширования. Обычно 64 байта. При чтении одного байта процессор загружает в кэш целую строку (64 байта). Это spatial locality: соседние данные часто используются вместе.

Cache miss penalty в реальной жизни

Запустим бенчмарк: обход массива 1 GB. **Sequential access:** 4 GB/s. **Random access:** 200 MB/s. Разница в **20 раз** - это цена cache misses. Процессор простаивает, ждёт данных из RAM.

**Cache associativity (ассоциативность).** Где разместить блок памяти в кэше? - **Direct-mapped:** каждый адрес → строго определённая cache line. Быстро, но конфликты. - **Fully associative:** можно в любую строку. Нет конфликтов, но медленный поиск. - **N-way set associative:** компромисс. Например, 8-way: блок может быть в любой из 8 строк набора.

False sharing: скрытый враг производительности

Два потока работают с разными переменными, но они в одной cache line (64 байта). Каждое изменение инвалидирует кэш другого ядра → постоянные cache misses. **Решение:** паддинг, чтобы переменные попали в разные cache lines. Это даёт прирост 5-10x в многопоточном коде.

Программа обходит массив int[1024][1024]. Row-major порядок даёт 100 MB/s, column-major - 10 MB/s. В чём причина?

TLB: кэш таблицы страниц

**TLB (Translation Lookaside Buffer)** - это кэш для адресной трансляции виртуальный адрес → физический адрес. Без TLB каждое обращение к памяти требовало бы 3-4 дополнительных чтения RAM (обход page table). TLB сокращает это до нуля.

Когда программа обращается по адресу `0x7fff1234`, процессор должен: 1. Взять старшие биты (номер страницы): `0x7fff` 2. Найти в page table физический адрес страницы 3. Сложить с offset'ом (`0x1234`) Page table - это многоуровневая структура в RAM. Обход занимает 3-4 чтения памяти (~400 наносекунд)!

**TLB - это кэш для Page Table Entries (PTE).** Размер: 64-512 записей. Каждая запись: виртуальная страница → физическая страница. **TLB hit** (попадание): трансляция за 1 такт. **TLB miss:** процессор делает page table walk в RAM.

**TLB miss penalty** огромен: если TLB miss rate вырос с 1% до 5%, программа может замедлиться на **50%**. Это происходит при работе с большими объёмами памяти (базы данных, научные вычисления).

TLB thrashing в реальном мире

База данных сканирует таблицу размером 10 GB. Страница памяти = 4 KB. Нужно 2.5 миллиона записей в TLB, но в процессоре их всего 512. **Результат:** TLB miss на каждое обращение → производительность падает в 3-5 раз. **Решение:** huge pages (2 MB вместо 4 KB) - нужно в 512 раз меньше TLB записей!

**TLB shootdown** - дорогая операция в многоядерных системах. Когда OS меняет page table (например, unmaps страницу), она должна инвалидировать TLB на **всех CPU ядрах**. Это требует межпроцессорного прерывания (IPI).

Оптимизация: PCID избегает TLB flush

Раньше context switch (переключение процесса) сбрасывал весь TLB - все 512 записей выбрасывались. Современные CPU (Intel с 2010) поддерживают **PCID (Process Context ID)**: каждая TLB запись помечается ID процесса. Переключение контекста больше не требует TLB flush - записи разных процессов сосуществуют в TLB. Ускорение context switch: 20-30%.

База данных работает с 20 GB памяти, TLB вмещает 512 записей, размер страницы 4 KB. TLB miss rate = 98%. Что улучшит производительность?

Page Cache: дисковый кэш в RAM

**Page cache** (или disk cache) - это кэш содержимого файлов в оперативной памяти. Чтение с диска занимает ~10 миллисекунд (HDD) или ~100 микросекунд (SSD). Чтение из RAM - 100 наносекунд. Разница в **100,000 раз** (HDD) или **1000 раз** (SSD).

При чтении файла через `read()` OS не идёт на диск напрямую. Сначала проверяет page cache: может, эти данные уже в памяти? Если да - мгновенный ответ. Если нет - читает с диска и кэширует на будущее.

**Page cache использует всю свободную RAM.** В Linux команда `free` покажет: ``` total used free buff/cache available Mem: 16GB 2GB 1GB 13GB 14GB ``` 13 GB в **buff/cache** - это page cache. Он не "занят" безвозвратно: если приложению нужна память, OS мгновенно освободит кэш.

Page cache для баз данных

PostgreSQL читает таблицу размером 10 GB. Первый полный скан: 100 секунд (чтение с SSD). Второй скан: 5 секунд (из page cache) - **20x быстрее**. Поэтому production БД всегда держат на серверах с огромным RAM: page cache - это бесплатное ускорение. Сервер с 256 GB RAM может кэшировать всю рабочую выборку БД.

**Read-ahead (упреждающее чтение)** - OS угадывает, какие данные будут запрошены дальше. При последовательном чтении файла ядро автоматически загружает следующие страницы в кэш **до фактического запроса**. Это скрывает latency диска.

**Write-back (отложенная запись)** - при записи в файл через `write()` данные идут в page cache, а на диск записываются **позже** (асинхронно). Это даёт огромное ускорение, но рискованно: если система упадёт до flush - данные потеряны.

Оптимизация записи: батчинг

Программа пишет лог: 1000 строк/сек, каждая с `fsync()`. HDD делает 100 IOPS → **10x overload**. Решение: батчинг - собрать 10 строк, один `fsync()`. Пропускная способность: 100 строк/сек → 1000 строк/сек. Это основа write-ahead log (WAL) в БД: группировать транзакции, один fsync на батч.

Приложение записывает 10,000 строк лога в файл, каждая запись с fsync(). HDD поддерживает 100 IOPS. Сколько времени займёт запись?

Buffer Cache: метаданные файловой системы

**Buffer cache** - это кэш метаданных файловой системы: inodes, directory entries, block bitmaps. Раньше (до Linux 2.4) buffer cache был отдельным от page cache. Сейчас они объединены, но концептуально различаются по назначению.

**Page cache** хранит содержимое файлов. **Buffer cache** хранит структуры самой файловой системы: где файл расположен на диске, какие блоки свободны, права доступа. Без buffer cache каждый `ls`, `stat()`, `open()` требовал бы чтения метаданных с диска.

**Dentry cache (dcache)** - это кэш путей файлов. При открытии `/home/user/file.txt` OS запоминает: `"/home/user/file.txt" → inode 12345`. Следующий `open()` того же файла мгновенен - не нужно обходить директории.

Buffer cache для git operations

Запускаем `git status` в репозитории с 10,000 файлами. Первый запуск: 2 секунды (чтение всех inodes/dentries с диска). Второй запуск сразу после: 0.1 секунда - **20x быстрее**. Dentry cache запомнил структуру директорий. Это почему IDE и git так быстро работают с повторными операциями.

**Block bitmaps и allocation metadata** - ещё один тип буферизуемых данных. Когда файловая система выделяет новый блок для файла, она читает block bitmap (битовая карта свободных блоков). Эти структуры часто модифицируются, поэтому критично держать их в RAM.

**Journal/Log в файловых системах** (ext4, XFS) тоже буферизуется. Журнал - это циклический лог изменений метаданных. Транзакции сначала пишутся в journal (последовательно, быстро), потом асинхронно применяются к основным структурам. Journal в RAM → транзакции мгновенны.

Оптимизация: tmpfs для временных файлов

Компиляция крупного проекта создаёт 100,000 `.o` файлов в `/tmp`. На обычной FS: каждый файл → inode allocation, block allocation, directory update. Огромная нагрузка на buffer cache и диск. **Решение:** `tmpfs` - файловая система в RAM. Никаких дисковых операций, всё в памяти. Компиляция ускоряется в 2-3 раза. После перезагрузки tmpfs очищается - идеально для /tmp.

Page cache и buffer cache - это одно и то же, разные названия одной сущности

Page cache и buffer cache концептуально различны: page cache хранит содержимое файлов, buffer cache - метаданные файловой системы (inodes, dentries, bitmaps)

Хотя в современном Linux (с ядра 2.4) они объединены в одну подсистему (unified page cache), семантически они решают разные задачи. **Page cache:** при вызове `read(fd, buf, 1024)` - данные кэшируются здесь. Это содержимое файла. **Buffer cache:** при вызове `open("/path/file")` - OS должна пройти по пути, прочитать inodes, directory entries. Эти метаданные кэшируются в dentry/inode cache (часть buffer cache). Без buffer cache даже простой `ls` требовал бы десятков обращений к диску для чтения структур директорий. Разделение концепций важно для понимания, какие части кэша сбрасывать (`echo 1` vs `echo 2` в `/proc/sys/vm/drop_caches`), и как тюнить FS для разных нагрузок.

Ключевые идеи

**CPU cache скрывает латентность RAM.** L1/L2/L3 кэши дают доступ к данным за 1-12 ns вместо 100 ns (RAM). Cache miss penalty огромен: разница в 100x. Оптимизация кода под cache locality даёт прирост 10-20x.
**TLB кэширует виртуальную → физическую трансляцию.** Без TLB каждое обращение к памяти требовало бы 3-4 дополнительных чтений RAM (page table walk). TLB hit rate 95-99% - критичен для производительности. Huge pages (2 MB) сокращают TLB pressure в 512 раз.
**Page cache превращает диск в RAM.** Повторное чтение файла из page cache в 1000x быстрее (SSD) или 100,000x быстрее (HDD). OS использует всю свободную RAM под page cache - это не "потраченная" память, а ускоритель. Read-ahead и write-back скрывают latency диска.
**Buffer cache ускоряет метаданные FS.** Inodes, dentries, block bitmaps в RAM → операции с файлами (open, stat, ls) мгновенны. Создание 10,000 файлов: 40,000 дисковых IO без buffer cache, ~10 IO с кэшем. Разница: 100 секунд vs 1 секунда.

Связанные темы

Кэширование - это фундаментальная идея, применимая на всех уровнях стека:

Виртуальная память — Page table walk кэшируется через TLB. Без TLB виртуальная память была бы в 3-5x медленнее. Huge pages снижают TLB pressure для больших приложений
Файловые системы — Page cache и buffer cache - основа производительности FS. Journaling, block allocation, directory lookups - всё зависит от кэширования метаданных
Системное программирование — Понимание кэшей критично для оптимизации: когда использовать mmap vs read, как избегать false sharing, зачем aligned allocations по cache line (64 bytes)
Архитектура процессоров — CPU cache hierarchy (L1/L2/L3), cache coherence протоколы (MESI), prefetching - всё это аппаратные механизмы, которыми управляет OS

Вопросы для размышления

Если приложение обрабатывает 1 TB данных, а RAM всего 16 GB, как page cache всё равно может дать ускорение? Подсказка: hot data vs cold data.
TLB на процессоре вмещает 512 записей. Программа работает с 10 GB памяти. Как huge pages (2 MB) помогут, если страницы выбираются случайно (random access)?
База данных делает fsync() после каждой транзакции для надёжности, но это убивает производительность (10 ms на HDD). Как совместить скорость и надёжность? Подсказка: group commit.

Связанные уроки