Библиотека и банк

Прошлая глава кончилась опытом: миллион показаний сейсмостанций, вопрос о показаниях одной станции занимает десятки миллисекунд, а после одной команды CREATE INDEX — сотые доли миллисекунды. Запрос не изменился ни на букву, данные те же. Что построила эта команда? И второй вопрос, который мы там отложили: как база не теряет деньги, когда их одновременно переводят двое, а посреди перевода гаснет свет? Ответы мы будем искать в двух местах: сначала в библиотеке, потом в банке.

Сцена первая. Библиотека без каталога

Представьте библиотеку, где книги стоят на полках в том порядке, в каком поступали. Читатель спрашивает книги Толстого. Библиотекарю ничего не остаётся, кроме как пройти вдоль всех полок и посмотреть на каждый корешок. Так и работает база без индекса: строки таблицы лежат в порядке поступления, и на вопрос о станции 4242 она читает их все. Это называют полным просмотром. Как именно база собирается выполнить запрос, она расскажет по команде EXPLAIN QUERY PLAN; такой рассказ называют планом запроса.

План из одного слова: SCAN readings — просмотреть всё. Время растёт вместе с таблицей: вдвое больше строк — примерно вдвое дольше. Это линейный поиск из главы 20, только написанный внутри базы на языке C. Для миллиона строк в памяти это десятки миллисекунд; на диске и для миллиарда строк — минуты.

Каталожный ящик

Библиотеки решили эту задачу задолго до компьютеров: завели каталог. Для каждой книги — карточка с фамилией автора и номером полки, а карточки стоят в ящиках по алфавиту. Чтобы найти Толстого, не нужно обходить полки: открываем ящик на «Т», листаем — и вот номер полки. Каталог ничего не знает о самих книгах, кроме ключа и адреса. Так же устроен индекс базы данных: значения столбца station по порядку, и при каждом — номер строки, rowid, по которому её можно достать.

Как устроить упорядоченные карточки в памяти машины? Мы знаем три способа, и у каждого своя беда. Отсортированный список ищется двоичным поиском за двадцать сравнений на миллион, как в главе 20, но вставка в середину сдвигает хвост — это $O(n)$ из главы 14, а карточки прибывают каждую секунду. Хеш-таблица из главы 16 находит ключ за одно действие, но не умеет «все станции от 4000 до 4999» и не отдаёт ключи по порядку. АВЛ-дерево из главы 17 умеет всё: поиск, вставку, порядок, — за $O(\log n)$. Для миллиона ключей в нём двадцать с лишним этажей — не больше 28, как мы доказали в той главе.

Двадцать с лишним этажей — это двадцать с лишним узлов, разбросанных по памяти. Пока дерево в оперативной памяти, это пустяк. Но индексы больших баз живут на диске, а диск, как мы видели в главе 40, читает блоками по 4096 байт, и каждое чтение с жёсткого диска стоит миллисекунды. Для процессора, как мы считали в главе 34, это вечность. Двадцать чтений по десять миллисекунд — пятая часть секунды на один поиск. А ведь из каждого прочитанного блока АВЛ-дерево использует один узел: ключ и две ссылки, несколько десятков байт из четырёх тысяч. Остальное прочитано впустую.

Boeing, 1970. Широкие ящики

Байер и Маккрейт рассудили так: если диск всё равно читает по блоку, пусть узел дерева занимает целый блок. Тогда в узел помещаются сотни ключей, по порядку, а между ними — ссылки на детей: всё, что меньше первого ключа, — в первом ребёнке, всё, что между первым и вторым, — во втором, и так далее. Это каталожный ящик с разделителями: на разделителях написано «А–Бе», «Бе–Ви», и вы сразу знаете, какой ящик открыть следующим. B-дерево — дерево поиска, в котором у каждого узла много детей, а все листья лежат на одной глубине.

Двоичное дерево делит ключи на два на каждом этаже, и на миллион ключей ему нужно двадцать этажей. Узел на сотню ключей делит на сотню, и тот же миллион укладывается в три этажа: $100^3 = 10^6$. Высота B-дерева — $\log_m n$, где $m$ — ширина узла: тот же логарифм, только по большому основанию.

Миллиард ключей — всего четыре этажа. Корень и второй этаж нужны каждому поиску, поэтому они почти всегда лежат в кэше в памяти, и с диска остаётся прочитать один-два блока.

Вставка: ящик делится пополам

Как сохранить все листья на одной глубине, когда ключи прибывают в любом порядке? В главе 17 для этого понадобились повороты, а B-дерево обходится без них. Новый ключ всегда кладут в лист, на своё место по порядку. Пока в листе есть место, на этом всё. Если лист переполнился, его делят пополам, а средний ключ поднимают в родителя — он становится разделителем между двумя половинами. Если от этого переполнился родитель, делят и его. Если делится корень, над ним появляется новый корень с одним ключом. Дерево растёт не вниз, как обычное, а вверх, от корня, — и поэтому все листья всегда на одной глубине.

То же самое на Python. Узел — список ключей и список детей; у листа детей нет. Функция bisect_left из модуля bisect — двоичный поиск из главы 20: она возвращает место, куда ключ встал бы в отсортированный список. Во внутреннем узле это место и будет номером ребёнка, в которого надо спуститься.

_insert возвращает None, если узел не переполнился, или пару «средний ключ и новая правая половина», если пришлось делить, — и родитель принимает эту пару к себе. Ползунок под картинкой проходит по всем шестнадцати вставкам. Дерево подросло на этаж всего один раз, на пятой вставке, когда разделился корень. Ширину проверим на трёхстах тысячах ключей.

При четырёх ключах в узле дереву из трёхсот тысяч ключей нужно десять этажей, при 32 — четыре, при 255 — три. Цикл for M in … меняет глобальную переменную, которую читает _insert, поэтому одно и то же дерево строится трижды с разной шириной. Поиск читает столько узлов, сколько этажей, и ни одним больше: длинных веток в B-дереве не бывает.

Заглянем внутрь SQLite

SQLite хранит в B-деревьях и индексы, и сами таблицы. Таблица — это дерево, где ключ — rowid, а строки лежат в листьях; индекс — дерево, где ключи — значения столбца вместе с rowid. В песочнице SQLite собран с виртуальной таблицей dbstat, которая рассказывает о каждой странице базы: на каком она этаже и сколько в ней записей. Построим журнал из миллиона показаний с индексом и пересчитаем этажи.

Столбец path у каждой страницы — её адрес в дереве: / у корня, /000/ у его первого ребёнка, /000/003/ у четвёртого ребёнка первого ребёнка, — поэтому этаж равен числу косых черт. И таблица, и индекс — три этажа. В корне индекса — около десятка ключей, на втором этаже — около одиннадцати страниц по двести пятьдесят ключей, в листьях — почти три тысячи страниц по три с половиной сотни. Чтобы найти показания станции, SQLite спускается на три страницы по индексу; там, в одном листе, рядом лежат все её записи — в среднем двадцать — с их rowid. За каждой строкой он спускается ещё на три страницы по дереву таблицы, но корень и второй этаж к этому времени уже в кэше. Выходит несколько десятков страниц и двадцать строк вместо всех пяти тысяч страниц таблицы и миллиона строк в них. По страницам это разница раз в сто с лишним; остальное добавляет работа со строками: полный просмотр разбирает и проверяет каждую из миллиона. Вместе и выходит разница в сотни и тысячи раз из прошлой главы.

Второй спуск, по дереву таблицы, нужен, чтобы достать столбцы, которых нет в индексе, — здесь value. Если все нужные запросу столбцы лежат в самом индексе, второй спуск не нужен. Такой индекс называют покрывающим, а SQLite пишет в плане USING COVERING INDEX.

Как база выбирает путь

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

Первое: индекс по нескольким столбцам упорядочен, как телефонная книга, — сначала по фамилии, внутри фамилии по имени. Индекс (station, day) мгновенно найдёт «станция 7 с первого по седьмое марта» и просто «станция 7», но не поможет с вопросом «все станции первого марта»: в телефонной книге не найти всех Иванов, не пролистав её всю. Второе: функция от столбца прячет его от индекса. WHERE substr(time, 1, 10) = '2021-03-01' заставит базу вычислить substr для каждой строки, а WHERE time >= '2021-03-01' AND time < '2021-03-02' спрашивает о том же, но по индексу на time ответит сразу. Третье: индекс отвечает не только на «равно», но и на «от и до». Двумя спусками по дереву база находит начало и конец отрезка, а между ними ключи идут по порядку, — то, что мы делали двумя двоичными поисками в главе 20.

Слова от «мир» до «мис» — тридцать штук — найдены за сотые доли миллисекунды: SEARCH … (word>? AND word<?), спуск к началу отрезка и проход до конца. Тот же вопрос через substr превращается в SCAN: база читает весь индекс подряд. Он хотя бы покрывающий, поэтому в саму таблицу она не ходит, но просматривает все пятьдесят с лишним тысяч слов. И LIKE 'мир%' индексом здесь не воспользовался: по умолчанию LIKE в SQLite не различает заглавные и строчные латинские буквы, а индекс их различает, и планировщик не может обещать, что ответ будет тем же. Проверяйте план, прежде чем надеяться на индекс.

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

Случай с этого сайта: 745 миллисекунд

Планировщик оценивает, сколько строк прочитает каждый способ, но самих данных не видит. Пока его не попросили, он не знает, сколько в таблице разных магнитуд, и по умолчанию считает, что на каждое значение первого столбца индекса приходится около десяти строк. При таком предположении оба индекса выглядят одинаково хорошими. ANALYZE обходит индексы, считает и записывает статистику в служебную таблицу sqlite_stat1. Из неё планировщик узнаёт, что разных магнитуд всего несколько десятков — 4,0, 4,1, 4,2… — и на каждую приходятся тысячи строк. Тогда становится выгоден приём, который без статистики SQLite не применяет никогда: пройти по составному индексу прыжками — для магнитуды 4,0 найти в нём отрезок нужных широт, потом для 4,1, и так далее. Воспроизведём историю в песочнице на шестистах тысячах толчков.

Магнитуды здесь распределены, как в природе: каждая следующая единица магнитуды встречается примерно вдесятеро реже. Это закон Гутенберга — Рихтера, а формула 3 - log10(1 - random()) — его простейшая модель. До ANALYZE план — USING INDEX quakes_mag (mag>?): пройти по всем шестидесяти с лишним тысячам толчков от четвёрки, для каждого спуститься в таблицу. После — ANY(mag) AND lat>? AND lat<?: прыжки по магнитудам, а внутри — отрезок широт. Когда писалась глава, это давало 40–50 миллисекунд до и 2–3 после; на сайте, где строк в семь с половиной раз больше и таблица лежит на диске, разница вышла почти стократной. В последней строке — сама статистика: в таблице 600 тысяч строк, на одну магнитуду приходится около десяти тысяч, а на пару «магнитуда и широта» — одна.

Цена индекса

Строить индексы на всех столбцах подряд мешает запись: каждый индекс — ещё одно B-дерево, и каждую новую строку приходится вставлять во все деревья.

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

Сцена вторая. Банк

Из библиотеки — в банк. Здесь скорость подождёт: нельзя потерять ни тенге. В главе 12 мы писали счёт Ады и Грейс и требовали, чтобы операция либо проходила целиком, либо не меняла ничего. Пока счёт живёт в памяти одной программы, это нетрудно: проверить, потом менять. Но перевод — это две записи в базу: списать у одного и зачислить другому. Что, если касса упадёт между ними? Устроим такую аварию. Банк лежит в файле, касса — отдельная программа, которая списывает деньги и умирает, не дойдя до зачисления: os._exit завершает процесс мгновенно, как выдернутый шнур, ничего не дописывая и не закрывая.

Без транзакции из банка пропали тридцать тенге: у Ады списано, Грейс не зачислено. Во втором прогоне касса упала в том же месте, но перед списанием сказала BEGIN — «начинаю одно целое дело». Когда базу открыли снова, всё было как до перевода. В последнем столбце вывода видно, что после падения рядом с базой остался файл bank.db-journal. В него SQLite перед изменением страницы кладёт её старую копию. Если дело дошло до COMMIT, журнал стирают. Если нет, первый, кто откроет базу, найдёт журнал и вернёт старые страницы на место. Журнал файловой системы из главы 40 тоже спасал от выдернутого шнура, но хранил не старое, а задуманное новое; к такому журналу мы ещё вернёмся.

Группа команд, которая выполняется целиком или не выполняется вовсе, называется транзакцией. Её начинают командой BEGIN, а заканчивают COMMIT — «зафиксировать» — или ROLLBACK — «откатить всё, что сделано с начала». В Python удобно писать with con: — блок, который сам зафиксирует транзакцию, если всё прошло, и откатит, если вылетело исключение.

Джим Грей: всё или ничего

Эти четыре буквы — договор, который база заключает с программистом. Расшифруем их на нашем банке. ACID — это:

• атомарность (atomicity) — перевод не может выполниться наполовину; за это отвечает журнал, который мы только что видели;
• согласованность (consistency) — правила базы соблюдены и до, и после: если в схеме написано CHECK (balance >= 0), транзакция, которая уводит счёт в минус, будет отвергнута целиком;
• изоляция (isolation) — два одновременных перевода не видят половин друг друга и не затирают друг друга; о ней — раздел о кассирах ниже;
• долговечность (durability) — если база ответила «зафиксировано», запись переживёт и падение программы, и выключение света: перед ответом база ждёт fsync из главы 40.

Сначала в журнал

Журнал отката, который мы видели, хранит старые копии страниц. Есть и обратный способ — тот, что у журнала файловой системы из главы 40, — и сегодня им пользуется большинство баз: журнал упреждающей записи, по-английски write-ahead log, WAL. Изменения сначала дописывают в конец журнала, а файл базы пока не трогают. Транзакция подтверждена, когда в журнал легла её отметка «готово». Время от времени база устраивает контрольную точку — переносит накопленное из журнала на место. Дописывать в конец файла быстро, а читатели тем временем спокойно читают старые страницы из самой базы. В SQLite этот режим есть с 2010 года, и его включают одной командой.

Двадцать тысяч строк после COMMIT лежат только в журнале: файл базы не изменился ни на байт, а журнал вырос до полумегабайта. Транзакция при этом уже подтверждена — если сейчас выключить свет, при следующем открытии SQLite прочтёт журнал и всё восстановит. Контрольная точка переносит страницы на место, и журнал пустеет. В этом режиме работает и база трекера землетрясений на этом сайте: программа, которая регулярно дописывает свежие толчки, не мешает посетителям читать страницы.

Кассиры

Осталась буква I — изоляция. Атомарность защищает от падений, а изоляция — от соседей. В банке два кассира. К первому Ада пришла внести 50, ко второму, в ту же минуту, — снять 30. Каждый кассир читает остаток, считает новый и записывает. Если их шаги перемешаются, повторится гонка из главы 39: оба прочтут 100, первый запишет 150, второй — 70, и пятьдесят тенге исчезнут. Опасность вполне житейская: так устроен любой код, который читает значение из базы, меняет его у себя в программе и записывает обратно. Кассирами в опыте будут два соединения с одной базой.

Без транзакций остаток стал 70 вместо 120: запись первого кассира затёрта, будто её не было. Это потерянное обновление. Во втором прогоне первый кассир начинает с BEGIN IMMEDIATE — «начинаю транзакцию и сразу беру право на запись». SQLite разрешает писать только одному соединению за раз, и второй кассир получает отказ database is locked: в рабочей программе он подождал бы и попробовал снова (у connect для этого есть параметр timeout; здесь мы поставили ноль, чтобы отказ был виден). Когда первый зафиксировал свои 150, второй начал заново, прочёл 150 и записал 120. Есть и способ проще: не выносить арифметику из базы. Команда UPDATE accounts SET balance = balance + 50 читает и пишет внутри одной операции, и потерять её нельзя — как если бы counter += 1 из главы 39 выполнялся одной неделимой командой процессора, вроде тех, на которых там строили замок.

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

Вторая история — грязное чтение. Аудитор складывает остатки, пока перевод ещё не закончен и, как потом окажется, будет отменён. Он видит деньги, ушедшие с одного счёта и не пришедшие на другой, и пишет в отчёт недостачу, которой никогда не было. Третья — перекос записи, самая коварная. У Ады и Грейс общий кредитный лимит: каждый счёт может уйти в минус, лишь бы сумма двух оставалась неотрицательной. Обе одновременно проверяют сумму — 100, хватает — и снимают по сотне каждая со своего счёта. Каждая трогала только свою запись и по отдельности правило соблюла, а вместе они его нарушили.

От каких аномалий защищаться, решает настройка, которую называют уровнем изоляции. Стандарт SQL описывает четыре уровня, от «читать даже неподтверждённое» до «сериализуемости» — гарантии, что результат будет таким, как если бы транзакции выполнялись строго по очереди. Чем строже уровень, тем чаще транзакциям приходится ждать друг друга или начинать заново, поэтому многие базы по умолчанию выбирают компромисс: PostgreSQL — «чтение подтверждённого», MySQL — «повторяемое чтение». SQLite проще и строже: писать в неё может только одно соединение за раз, и все её транзакции сериализуемы.

Задачи

Три задачи — по одной на каждое ремесло главы: подобрать индексы под нагрузку, написать перевод, который не теряет денег, и пройти по B-дереву самому.

Куда дальше

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

Текст «Войны и мира» ужимается почти вчетверо, архив — в два с половиной раза, а три мегабайта случайных байтов не ужимаются ни на байт. Значит, в тексте и в таблицах есть что-то лишнее, что можно выбросить и потом точно восстановить, а в случайных байтах этого нет. Что именно? И как ZIP находит это лишнее за доли секунды и сжимает четыре гигабайта текста в один? Об этом — следующая глава, конкурс упаковки.