↶ Машина на глиняних ногах
8 / 18

Розділ 7. Брехня плоскої пам'яті

Велика ілюзія

Відкрий будь-який підручник з C, Python, Java, Go. Ось, наприклад, твоя перша програма в C:

int main() {
    int x = 5;
    int y = 10;
    int z = x + y;
    return z;
}

Підручник пояснить тобі: змінні x, y, z живуть у пам’яті. Пам’ять — це великий рівний масив байтів, кожен з яких має свою адресу. Програма пише і читає ці байти. Просто, чисто, зрозуміло.

Усе це — брехня.

Точніше — це абстракція, яку процесор, операційна система і компілятор спільно підтримують для тебе, щоб ти міг зосередитись на алгоритмі, а не на тому, як насправді працює залізо. Але якщо ти системний адміністратор, програміст чи хтось, хто колись захоче дебажити повільну програму — тобі треба знати, що відбувається під капотом.

А під капотом — щонайменше п’ять рівнів абстракції, кожен з яких бреше тобі по-своєму.

Брехня перша: твоя програма має всю пам’ять

Коли ти запускаєш програму, з її точки зору пам’ять виглядає так: великий рівний адресний простір від адреси 0 до 2⁶⁴ (на 64-бітному комп’ютері). Усі 18 квінтильйонів байтів — твої. Можеш писати, можеш читати.

Звісно, у твоїй машині немає 18 квінтильйонів байтів. У твоїй машині, скажімо, 16 ГБ — це 16 мільярдів байтів, тобто в мільярд разів менше, ніж адресний простір.

Як же кожна програма має “всю пам’ять”? Через віртуальну пам’ять.

Ось як це працює. Усі адреси, з якими програма працює — це віртуальні адреси. Не реальні. Коли програма звертається до адреси, скажімо, 0x7ffe12340000, процесор не йде безпосередньо в RAM. Він спочатку звертається до сторінкових таблиць (page tables) — структури в пам’яті, яку підтримує операційна система. У цій таблиці записано: “адреса 0x7ffe12340000 у віртуальному просторі цієї програми відповідає реальній адресі 0x000a3450 у фізичній RAM”.

Тільки після цього перетворення — трансляції адреси — процесор іде в RAM.

Кожна програма має свою сторінкову таблицю. Це означає, що адреса 0x7ffe12340000 у програмі А і у програмі Б відповідають різним фізичним сторінкам пам’яті. Програми ізольовані. Жодна не може випадково зачепити чужі дані.

Це — фундаментальна основа безпеки і стабільності сучасних систем. Без віртуальної пам’яті ми б досі жили у світі MS-DOS, де одна програма могла впасти і потягти за собою всю систему.

Але це коштує. Кожне звернення до пам’яті вимагає трансляції, тобто додаткового пошуку у сторінкових таблицях. Якщо робити це щоразу — програма буде у 100 разів повільніша.

Тому існує TLB (Translation Lookaside Buffer) — спеціальний кеш, який зберігає недавні трансляції. Якщо адреса вже була перетворена нещодавно — її переклад береться з TLB за один такт. Якщо ні — треба йти у сторінкові таблиці, що значно повільніше.

Великі бази даних, JIT-компілятори, віртуальні машини — всі вони мають проблеми з TLB. Проблема настільки відома, що операційні системи дають змогу використовувати великі сторінки (huge pages, на Linux — 2 МБ або 1 ГБ замість стандартних 4 КБ). Менше сторінок — більше пам’яті покривається TLB — менше промахів.

Брехня друга: пам’ять — це масив

Ми вже говорили про кеш у Розділі 4, але в контексті простоти. Тепер копнімо глибше.

Реальна структура того, що ти називаєш “пам’ять”:

  1. Регістри процесора (16-32 64-бітних регістрів) — найшвидші, доступ за пів такту.
  2. L1-кеш (32-128 КБ, окремо для коду і даних) — 3-5 тактів.
  3. L2-кеш (512 КБ – 2 МБ на ядро) — 10-20 тактів.
  4. L3-кеш (8-128 МБ, спільний для всіх ядер) — 30-60 тактів.
  5. DRAM (системна пам’ять) (16-512 ГБ) — 200-400 тактів.

Тобто коли ти пишеш int x = arr[i];, процесор робить таке:

  1. Перевіряє, чи arr[i] у регістрі. Якщо так — береш звідти. Готово, 0 тактів.
  2. Якщо ні — перевіряє, чи у L1. Якщо так — 4 такти.
  3. Якщо ні — перевіряє L2. 12 тактів.
  4. Якщо ні — L3. 40 тактів.
  5. Якщо ні — RAM. 300 тактів.

Між кроком 1 і кроком 5 — різниця у 300 разів. Програма, яка масово промахується по кешу, працює буквально у сотні разів повільніше за програму, яка точно потрапляє.

І це ще не все. Кеш організований у рядки (cache lines) — зазвичай 64 байти. Коли процесор завантажує одне число, він завантажує цілий рядок. Якщо твої числа лежать у пам’яті близько одне до одного — наступне число вже у кеші. Якщо далеко — кожне нове звертання це холодний промах.

Звідси випливає просторова локальність: дані, які ти використовуєш разом, повинні лежати поруч у пам’яті. Тоді кеш працює ефективно.

Але це не все, що приховано. Кеш має ще одну особливість, яка ламає інтуїцію.

False sharing: коли два потоки б’ються за нічого

Уяви: ти пишеш паралельну програму. Маєш два потоки. Один збільшує лічильник counterA. Другий — counterB. Лічильники незалежні. Логічно, ніяких конфліктів немає.

Запускаєш — програма повільна.

Перевіряєш — два потоки б’ються між собою, ніби вони працюють із спільною змінною.

Що сталося? Ти оголосив:

int counterA;
int counterB;

Компілятор поклав їх у пам’яті поруч. Обидва — у одному 64-байтному кеш-рядку. Коли ядро 1 пише в counterA, воно блокує цей кеш-рядок. Ядро 2 хоче писати в counterB — мусить чекати. І навпаки. Постійна війна за рядок, який обом потрібен, але кожному з різних причин.

Це називається false sharing — фальшивий розподіл. Дві змінні, які логічно незалежні, фізично пов’язані через кеш-рядок.

Розв’язок — подушка. Розставити змінні в пам’яті так, щоб вони не лежали в одному кеш-рядку:

struct {
    int counterA;
    char padding[60];  // заповнення
    int counterB;
} counters;

Тепер counterA і counterB у різних рядках. Жодних конфліктів. Програма прискорюється у 5-50 разів на типових задачах.

Жоден підручник із “Введення в C” не розповість тобі про це. А це — фундаментальний закон швидкого паралельного коду.

Брехня третя: усі ядра однаково близькі до пам’яті

У сучасному сервері з двома процесорними сокетами (наприклад, два Intel Xeon або AMD EPYC) на материнській платі дві окремі групи RAM — по одній біля кожного сокета. CPU 1 має свою RAM “поруч”. CPU 2 — свою.

Якщо програма працює на CPU 1 і звертається до RAM біля CPU 1 — швидко (200 тактів). Якщо звертається до RAM біля CPU 2 — повільно (400-600 тактів), бо запит мусить пройти через спеціальну шину між сокетами (Intel називає її UPI, AMD — Infinity Fabric).

Це називається NUMA (Non-Uniform Memory Access) — нерівномірний доступ до пам’яті. На однопроцесорних машинах цього немає. Але на серверах і робочих станціях з кількома сокетами — це фундаментальна реальність.

Нерозуміння NUMA коштувало багатьом компаніям мільйони. У 2010-х якась велика база даних бувало “повільнішала вдвічі при апгрейді на новіший сервер” — і причина крилася в тому, що новий сервер мав два сокети, а програма не вміла розуміти NUMA. Випадково розподіляла потоки, і половина з них тягнулася через міжсокетну шину.

Сучасні Linux-ядра і Windows-сервери мають NUMA-aware планувальники — намагаються тримати потік і його дані на одному сокеті. Але це працює тільки якщо програма теж добре поводиться.

Системному адміністратору, який ставить серверну СУБД, NGINX або Kafka, треба знати про NUMA. Команда numactl на Linux показує топологію. numastat показує промахи. Прив’язування процесів до конкретних сокетів (taskset, numactl --cpunodebind) часто дає 2-5x прискорення.

Брехня четверта: інструкції виконуються по порядку

Ще одна абстракція, яка тече.

Коли ти пишеш:

a = 5;
b = 10;
c = a + b;

Ти думаєш: процесор виконає рядок 1, потім 2, потім 3. Послідовно. Як написано.

Не виконає. Сучасний процесор виконує багато інструкцій паралельно і не за порядком (out-of-order execution, OOO). Він дивиться вперед на десятки інструкцій, шукає незалежні, виконує їх раніше, потім переставляє результати у “правильний” порядок з погляду видимих ефектів.

Більше того, процесор спекулятивно виконує інструкції за гілками умовних переходів, ще не знаючи, яка з гілок буде взята. Якщо вгадав — швидкість. Якщо ні — викидає результат і починає правильну гілку.

Це все було невидимо для програмістів — поки в 2018 році не з’явилися Spectre і Meltdown.

Spectre, Meltdown, і ціна швидкості

У січні 2018-го світ здригнувся. Дослідники з Google Project Zero, Грацького університету і Cyberus Technology оголосили про вразливості, які зачіпають майже всі процесори, випущені за останні 20 років.

Спрощено суть така.

Процесор спекулятивно виконує інструкції неправильної гілки коду. Потім розуміє, що помилився, і скасовує результати. Видимо — нічого не сталося.

Але сліди залишаються в кеші. Дані, які процесор завантажив під час спекуляції, залишаються в кеші, хоча офіційно “ніколи не виконувались”. І ці сліди можна виміряти: програма-зловмисник вимірює час доступу до різних адрес. Швидкий доступ означає, що адреса в кеші. Повільний — її там немає.

З цього одного непрямого сигналу можна відновити дані, які процесор обробляв спекулятивно. У тому числі — дані з пам’яті ядра ОС, із пам’яті іншого процесу, із пам’яті інших віртуальних машин на тому самому сервері.

Це — порушення фундаментальної властивості ізоляції. Усе сучасне залізо було побудовано на принципі: “процеси не можуть бачити пам’ять одне одного”. Spectre показала: можуть. Через хитрий обхідний шлях, але можуть.

Виправлення: - Програмні: операційні системи додали “isolation” режими (KPTI на Linux), які роблять перемикання між ядром і користувацьким простором повільнішим. - Апаратні: нові процесори додали захисти проти конкретних атак. Старі процесори — ні, можуть бути атаковані досі. - Продуктивні: програмні виправлення коштували 5-30% швидкості на багатьох типах робочих навантажень. Хмарні провайдери ці втрати тихо переклали на клієнтів.

Найважливіший урок Spectre: ціна швидкості — складність, а складність — атака. Сучасні процесори настільки складні, що жоден інженер не розуміє їх повністю. У них живуть тисячі дрібних особливостей, з яких хитрий зловмисник може створити вразливість.

Брехня п’ята: записи бачаться одразу

Ще одна тонка штука. Коли ти у багатопотоковій програмі пишеш:

// потік 1
x = 5;
flag = true;
// потік 2
if (flag) {
    print(x);  // що буде виведено?
}

Ти можеш очікувати: якщо flag = true, то x точно вже 5. Адже потік 1 написав їх у такому порядку.

Так не працює.

Процесор може переупорядкувати записи. Він може спочатку записати flag = true, а потім x = 5, зі своїх внутрішніх причин (наприклад, flag був у кеші, а x ні). Іншому потоку це може бути видно як “flag вже true, але x ще старий”.

Кожна архітектура має свою модель пам’яті (memory model) — формальний опис того, які переупорядкування дозволені. У x86 модель досить сильна — гарантує багато порядків. У ARM — слабша, дозволяє більше переупорядкувань (швидше, але важче програмувати).

Щоб гарантувати порядок, треба використовувати бар’єри пам’яті (memory barriers) або відповідні мовні конструкції — volatile в Java, std::atomic в C++, спеціальні синхронізаційні примітиви.

Більшість програмістів про це не знає. Тому в багатопотоковому коді живуть тисячі тонких помилок, які проявляються раз на мільйон запусків і нікого не лякають — поки не зламається продакшн в неділю о другій ночі.

Що цей рівень абстракції дає, і чим бере

Усі ці шари — віртуальна пам’ять, кеш, NUMA, OOO, спекулятивне виконання — дають програмісту простоту. Ти пишеш int x = 5; і не думаєш, де воно живе, як кешується, який сокет його обслуговує.

Ціна: - Непередбачувана продуктивність. Один і той самий код може бути в 100 разів повільнішим залежно від того, як він взаємодіє з кешем. - Тонкі баги. Race conditions, false sharing, NUMA-міграції, TLB shootdowns — всі ці слова описують реальні явища, які ламають програми. - Безпекові вразливості. Spectre — лише одна. Існують Foreshadow, ZombieLoad, RIDL, MDS — список постійно зростає. - Огидна складність налагодження. Профайлери, perf-counters, lstopo, numastat — це окремий світ інструментів для системного адміністратора.

Що системному адміністратору з цього винести

  1. Пам’ять — не плоска. Усе, що тобі сказали в школі — перше наближення. Реальність ієрархічна, нерівномірна, повна пасток.
  2. Кеш-локальність — найважливіша оптимізація. Якщо програма повільна — це майже завжди про кеш, не про алгоритм.
  3. NUMA-awareness обов’язкова на серверах. Знай свою топологію, прив’язуй процеси, моніторь міжсокетний трафік.
  4. TLB має значення. Якщо запускаєш бази даних, JIT-мови чи віртуальні машини — розглянь huge pages.
  5. Spectre/Meltdown — не залякування. Якщо твоя інфраструктура мультитенантна (хмара, спільні сервери), застосовуй патчі.
  6. Багатопотоковий код — окрема галузь науки. Не пиши його з нуля без потреби. Використовуй перевірені бібліотеки.

У наступному розділі — найвідважніший: майбутнє, яке ще не настало. Аналогові обчислення, нейроморфні процесори, квантові комп’ютери, оптика, ДНК. Усе те, що мало б замінити CMOS, але чомусь не замінило. Чому? І хто з них, можливо, нарешті стане наступним великим повстанням проти усього, про що ми досі розповідали?