#23: SSD и HDD: устройство дисков и слотированные страницы

[00:21] Здарова! Меня зовут Саша Пахомов, и я инженер, который любит своё дело. Вы слушаете подкаст, в котором разработчик современной базы данных изучает то, как они работают, и делится знаниями со слушателями. Представьте меня шесть лет назад: сижу в офисе одной компании и решаю свою первую производственную задачу. Я только что прибежал с пар по матанализу, и мне не терпится открыть рабочий ноутбук Asus, чтобы приступить к делу. Нужно было написать адаптер между BI-системой Tableau и дико современной на тот момент базой данных — ClickHouse. За пару недель танцев с бубном вокруг JavaScript я с этой задачей справился. Получив похвалу от начальника, я не мог сдержать эмоций — думаю, все видели, насколько я был счастлив и как ярко светили мои горящие глаза.

[01:12] После того как я проявил себя хорошим стажёром, мне начали давать скучные, рутинные задачи на Scala в движке Apache Spark. Вспоминая те времена сейчас, я могу сказать, что был прослойкой между аналитиками и Spark’ом — переводил ТЗ на язык программирования. Но тогда мне казалось, что я самый современный разработчик в мире: ведь это функциональный язык Scala и Spark! Единственное, что отделяло меня от передовых технологий, — мой рабочий ноутбук. Сам по себе он был неплох, но диск в нём стоял жёсткий, то есть медленный. Спасти ситуацию мог твердотельный накопитель, SSD, который был установлен у большинства разработчиков.

[01:53] И вот ко мне подходит начальник, кладёт заветную плашку на стол и говорит: «Вставляй в ноутбук». Я был счастлив. Смена диска предполагала переустановку операционной системы и полную настройку окружения — для студента второго курса задача интересная, хоть и не самая лёгкая. Потратив весь выходной, я таки поставил себе свеженькую Ubuntu 16 на новый диск и был поражён скоростью работы системы. Переход с жёсткого диска на SSD можно сравнить с покупкой нового iPhone — очень приятное чувство. И такой качественный скачок повлиял не только на меня, но и на современные базы данных. Это подкаст «Тысяча фичей», и сегодня мы поговорим о том, как внутреннее устройство дисков влияет на то, какими примитивами оперируют современные хранилища. Поехали!

[02:49] Самый дешёвый и распространённый способ хранить биты информации на сегодняшний день — это жёсткие диски. Несмотря на то что почти во всех современных устройствах стоят SSD, на серверах используются и те, и другие. Представьте себе музыкальный проигрыватель со считывающей головкой и пластинкой: поставив головку в нужное место, можно воспроизвести звуки, записанные именно там. Такая дорожка записана последовательно, и дорожки располагаются одна за другой. Жёсткий диск работает очень схожим образом. Это магнитный диск и записывающая головка, причём таких пар «головка — диск» внутри одного устройства несколько. Диск крутится очень быстро, а головка может менять положение в зависимости от того, откуда мы хотим читать биты или куда записывать. Само представление бита — это намагниченность или, наоборот, ненамагниченность конкретной ячейки на диске.

[03:38] Процесс чтения с такого диска выглядит так. Предположим, диск уже раскручен, и мы указываем место, с которого нужно начать читать. Головка перемещается по заданным координатам и начинает считывать намагниченные ячейки, интерпретируя их в электрические заряды, знакомые компьютеру. Узким местом здесь является перемещение головки — это очень медленная механическая операция по меркам современных компьютеров. Такая особенность значительно повлияла на алгоритмы и структуры данных, которые используют базы данных. А именно: во-первых, последовательное чтение и запись; во-вторых, минимизация случайных чтений, так называемых random seek, ведь они приводят к перемещению считывающей головки, что значительно замедляет работу.

[04:20] SSD-диски решают проблему медленной головки — её там попросту нет. Устроены они гораздо сложнее, чем жёсткие диски. Чтобы понять, как они работают, нужен целый выпуск подкаста длиной не менее часа. К счастью, нам не нужно так глубоко разбираться в их устройстве — достаточно знать некоторые особенности их работы. Итак, единицы информации, то есть биты, хранятся в ячейке. Одна ячейка может хранить один, два или три бита — в зависимости от реализации. Ячейки объединены в строки, строки — в массивы, массивы — в страницы, а страницы — в блоки. То есть, от самого маленького: ячейка, строка, массив, страница, блок. Размер страницы — 4 килобайта. Минимальная единица записи и чтения — как раз-таки она, страница. А минимальная единица удаления — это блок. То есть, ещё раз: считываем мы страницы, записываем страницы, а удаляем — блоки.

[05:13] Эти особенности влияют на то, как мы работаем с диском. Мы используем страницы фиксированного размера в качестве контейнеров для данных, и размер страницы чаще всего всё те же 4 килобайта. Иногда мы можем помечать страницы как удалённые, но фактически их не удалять — ведь удаление происходит блоками, а лежащая в том же блоке соседняя страница не всегда готова к удалению.

[05:37] Как вы поняли, эффективная работа с диском — сложная инженерная задача, и по возможности её лучше избегать. К сожалению, нам приходится иногда взаимодействовать с дисками, ведь это единственный способ гарантировать долговечную запись. Оперативная память, увы, забывает всё, что на ней было записано, в случае выключения компьютера. Зато работать с ней гораздо удобнее. Благодаря операционной системе мы можем не думать о страницах и блоках, о том, как и когда их удалить, и о том, что данные лучше бы лежали последовательно. Мы воспринимаем оперативную память как условно бесконечную область: можем попросить операционную систему выделить нужное количество свободной памяти и получить на неё указатель, а когда память больше не нужна — попросить её освободить. Вот и всё.

[06:19] Бегать по указателям в оперативной памяти мы можем почти без потерь производительности. А на диске это будет проблемой — даже если это SSD, потому что загружать в память мы будем всё равно страницы целиком, а это накладные расходы. Структуры, которыми оперируют базы данных, представлены в оперативной памяти, но сохраняются на диск, поэтому к ним есть некоторые требования. А именно: минимальное обращение к диску, и указатели на данные должны лежать рядом с самими данными — по сути, являться смещениями на диске.

[06:49] А насколько оперативная память быстрее, чем жёсткий диск? Чтобы разобраться в этом вопросе, давайте сначала посмотрим на так называемую иерархию хранилищ — всего, с чем работают наши программы, и как эти хранилища расположены друг относительно друга. На вершине этой пирамиды находятся регистры процессора. Это то, что непосредственно расположено на кристалле вычислительного устройства, и оно, конечно, самое быстрое. Дальше по скорости идёт CPU cache — такие маленькие-маленькие оперативки, которые тоже лежат рядом с процессором, и доступ к ним супербыстрый. Ещё дальше — оперативная память, наш RAM. Эти три вида хранилища — регистры, процессорные кэши и оперативная память — так называемая volatile-память: она не сохраняется при выключении компьютера. Выключили компьютер — и она стёрлась. Зато там random access, то есть побайтовая, случайная адресация, которая работает быстро и предсказуемо.

[07:45] А вот дальше идут SSD, HDD и сеть. Там доступ у нас уже не рандомный, а последовательный: мы взяли какой-то адрес, какое-то смещение на диске — и читаем его последовательно, причём адресация идёт поблоковая. Зато после отключения компьютера эти хранилища сохраняют информацию, то есть являются non-volatile. Если посмотреть сверху вниз, у нас получается: снизу сеть, над ней HDD, SSD, оперативная память, кэши процессора, регистры. И если смотреть снизу вверх, то мы идём от самого дешёвого к самому дорогому, от самого большого по размеру к самому маленькому и от самого медленного к самому быстрому. Вот такая зависимость.

[08:39] Но как понять, насколько что быстрее? Ну да, мы знаем, что регистры процессора очень быстрые, что оперативная память быстрее диска. А насколько? Как представить себе эту разницу? Небезызвестный Эндрю Павлу (Andy Pavlo), лекции которого я смотрю и черпаю оттуда знания, приводит так называемую таблицу Latency Numbers Every Programmer Should Know — «цифры задержек, которые должен знать каждый программист». Идём от самого быстрого. Если мы хотим прочитать что-то из регистра — это одна наносекунда. Наносекунда — это очень быстро. Дальше, обращение к кэш-линиям — около 4 наносекунд, что тоже быстро, четыре мгновения. Обращение к оперативной памяти — уже 100 наносекунд, что несколько дольше: то есть на порядок, а то и на два дольше, чем читать из кэшей. За оперативной памятью идёт SSD, и обращение к нему длится 16 000 наносекунд — а это уже на несколько порядков выше, чем предыдущее, но всё равно ещё довольно быстро. А вот обращение к HDD будет длиться 2 миллиона наносекунд, а обращение по сети — 50 миллионов наносекунд. Это уже огромные цифры.

[09:47] Но всё ещё довольно сложно представить в голове, каково это. Давайте переведём эти наносекунды в привычную нам систему исчисления — обычные секунды, часы, недели и годы, — и тогда поймём относительное расположение этих времён задержки. Итак, кэши — одна наносекунда — это у нас будет 1 секунда. Четыре наносекунды — это 4 секунды: мы понимаем, что эти два числа очень близки, это очень быстро и очень рядом. Оперативная память, 100 наносекунд, — это 100 секунд, почти две минуты, тоже относительно недолгое время, если смотреть дальше. А дальше идёт SSD — 16 000 наносекунд — это уже 4,5 часа: по сравнению со 100 секундами очень долго, прямо ощутимо. Но что ещё более ощутимо долго — это чтение из HDD: 2 миллиона наносекунд — это 3,5 недели. То есть у нас была секунда, 4 секунды, 100 секунд, 4,5 часа, 3,5 недели. Но и это ещё не предел: обращение по сети к какому-нибудь network storage — это будет полтора года. Ребята, полтора года! Это очень долго. Такие вот порядки — и всё это к тому, чтобы понять, чем мы жертвуем, когда идём в сеть, или когда идём читать по HDD или SSD, вместо того чтобы всё расположить в оперативной памяти. Вот такие разрывы, такие trade-off. А мы идём дальше.

[11:15] Теперь давайте поговорим о том, как именно базы данных представляют информацию, которую хранят на дисках. Большинство баз данных оперируют таким примитивом хранения информации, как страницы, или, по-английски, page. Страница — это блок памяти, по сути просто отрезок байтов или битов фиксированного размера. Внутри себя она может содержать записи данных, какие-то метаданные, индексы, записи лога. Большинство систем не миксует типы страниц, поэтому в одной странице, скорее всего, будут лежать данные одного и того же типа. Сами страницы идентифицируются специальным айдишником, а потом этот айдишник мапится на физическую локацию на диске — то есть на смещение той самой головки, по которому нужно сходить, чтобы по этому айдишнику считать страницу.

[12:04] Вообще, когда мы говорим про страницы в базах данных, там есть три типа страниц. Первая — страница хардверная, та, которая лежит на диске, которую мы уже обсудили; её размер обычно 4 килобайта, и это та страница, которую мы пишем и читаем на SSD. Вторая — страница в операционной системе: по сути один в один та же самая страница, что и на диске. Операционная система может гарантировать нам атомарную запись или чтение страницы — как раз если эта страница 4 килобайта: это тот размер, которым оперируют хардвер и операционная система. А базы данных иногда могут иметь страницы поменьше, иногда побольше, но в среднем по больнице это тоже 4 килобайта. Поэтому, когда мы говорим «страница», можно в целом пренебречь тем, о чём именно речь — о дисковой странице или о странице базы данных: пусть будет одно и то же.

[12:54] Дальше эти страницы нужно как-то объединить между собой, положить в какой-то файл. Часто это так называемый heap-файл, но не только — есть куча разных форматов файлов, мы их ещё рассмотрим. Давайте для простоты возьмём heap-файл — это просто коллекция страниц, внутри которых лежат тюплы, хранящиеся там в случайном порядке. Мы можем делать с ними CRUD-операции по айдишнику: create, read, update, delete. И ещё этот файл позволяет итерироваться по всем страницам, потому что full scan — довольно частый кейс доступа к данным.

[13:34] Итак, файл состоит из страниц, а из чего состоит сама страница? То, что в них лежит непосредственно, определяется реализацией базы данных или форматом, которым она оперирует. Но если взять среднее представление страницы, то давайте представим себе, что страница — это, по сути, лента, у которой есть начало и конец. Для простоты, так как мы говорим «страница», я себе представляю её как квадратик, как реальную тетрадную страницу. И вот вверху этой страницы есть заголовок, или хедер, как его часто называют. В нём располагается метаинформация о самой странице. Так как хедер в начале, мы можем сначала считать его кусок, понять, что это за страница, что в ней лежит, какие типы данных, есть ли там какие-то транзакционные вещи, которые запрещают нам сейчас что-то смотреть, — и дальше данные не считывать, если они нам не нужны. Это, с одной стороны, оптимизация, а с другой — необходимость.

[14:30] Что именно может лежать в хедере? Например, размер страницы — чтобы мы просто знали, где её конец. Чек-суммы — чтобы сверить, что данные не покорраптились. Версия базы данных: если старая версия записала эту страницу, а мы обновились до новой, которая не поддерживает старый формат, мы просто не сможем эту страницу прочитать и десериализовать данные. Какие-то транзакционные данные, компрессия — вообще много всего может лежать в хедерах, это зависит от реализации. Такой хедер занимает процентов пять-десять — маленькую часть страницы; основная её часть — это всё-таки данные. Данные тоже могут быть разными, но давайте условимся, что данные — это записи, тюплы. Например, если мы говорим про row-based storage — какой-нибудь Postgres — и у нас таблица юзеров, то данные — это записи про одного юзера: айдишник, имя, фамилия, адрес, email. Все эти штуки будут лежать в одном так называемом тюпле, или записи, которая представляет собой единицу внутри страницы. И страница хранит в себе много-много таких записей.

[15:32] Как расположить эти записи? Самая наивная реализация — сразу за хедером. Берём хедер, он занял несколько байт, и дальше записи фиксированного размера: первая, вторая, третья, четвёртая. У каждой записи есть символ начала и символ конца — или у каждой записи могут быть свои хедеры, которые хранят её длину. Вообще, как расположить данные внутри записи — это тоже задача не самая тривиальная. Например, если записи у нас все фиксированного размера, то что делать со строками, такими как имена? Ведь имена могут быть разные — короткие, длинные. Зарезервировать под имя сразу большое количество байт и думать, что никогда не будет имени длиннее, можно, но это наивный подход.

[16:16] Тут начинаются тонкости. Например, одна запись может разделяться на несколько записей: она говорит «я не полная запись, у меня есть продолжение — вот моё начало». Ты считываешь начало, получаешь ссылку на продолжение, считываешь продолжение, смотришь — это не конец, идёшь дальше: получается такой связанный список. Ты этот связанный список вычитываешь и только потом десериализуешь все байты в осознанные значения. Это один из примеров реализации. Так же могут быть устроены и сами страницы: страница может сказать «во мне столько всего, что я неполная, а вот страница — моё продолжение». Мы это разберём дальше, на конкретных структурах данных, но такое тоже может быть. Сейчас же для простоты давайте условимся, что тюплы могут быть переменного размера — размер записи меняется из-за того, что там могут быть, например, изменяемые строки. А это накладывает некоторые ограничения на то, как мы их храним.

[17:13] Допустим, мы начинаем писать записи сразу за хедером: первая, вторая, третья, четвёртая, пятая. Записали, отлично, и мы знаем их адресацию: сама запись идентифицируется айдишником страницы, в которой она лежит, и смещением внутри страницы. То есть, допустим, по смещению 10 мы скипаем хедер и попадаем на первую запись; длина этой записи — 5, соответственно, по смещению 15 будет вторая запись, и так далее. А что делать, если мы удаляем одну запись, причём из середины? Например, удаляем ту, что была по смещению 10. Запись по смещению 15 остаётся, а по смещению 10 у нас теперь пустое пространство. И в следующий раз, когда мы будем что-то туда записывать, нам нужно принять непростое решение. Будем ли мы записывать на позицию с 10 до 15? Тогда вопрос: а вместится ли туда запись, которую мы сейчас вписываем? Что, если её длина не 5, а 6? Её придётся поместить в конец, и у нас останется пустое пространство. А что, если длина 3? Тогда мы её туда впишем, но останутся ещё 2 байта, которые уже, по сути, никто потом не заполнит — потому что нет подходящих записей такого маленького размера.

[18:20] И если мы долго-долго занимаемся только удалением, страница начинает фрагментироваться. Это фрагментация в чистом виде: размер страницы, например, 4 килобайта, а реальных данных там лежит на 3 килобайта, потому что остальной 1 килобайт распределён в промежутках между записями, и мы ничего не можем с этим сделать — не можем подобрать, что туда записать, потому что слишком маленькие эти размеры. Такая вот фрагментированная вещь — это потеря производительности и потеря полезного пространства. Что с этим делать? Ну, с фрагментацией принято бороться дефрагментацией — специальным процессом, который запускается в момент, когда мы понимаем, что пора. А когда пора — каждый алгоритм решает по-разному. Например, в заголовке страницы хранится её размер, а ещё может храниться доступная и занятая память. Если мы понимаем, что доступной памяти для нашей записи хватает, но страница фрагментирована настолько, что цельного места для записи нет, — вот тогда нужно сделать дефрагментацию и уже потом записать новую запись.

[19:27] Происходит дефрагментация следующим образом. Мы берём все записи и укомпоновываем их плотненько-плотненько, одну за другой: сдвигаем, сдвигаем, сдвигаем — и получаем свеженькую, хорошую, оптимальную страницу, где всё свободное место оставлено в конце. И в этот конец мы можем дописывать — но до поры до времени, пока опять не настанет фрагментация. Это рабочий подход, но на практике он показал себя не очень, и инженеры придумали несколько другой, более оптимальный, чем обычное расположение записей внутри страницы.

[19:53] Это слотированные страницы — есть прямо такой термин, slotted pages. Всё, чем слотированная страница отличается от неслотированной, — это, по сути, две вещи. Первое: сразу за хедером следуют не записи, не тюплы, а так называемый слот-аррей, массив слотов. Это просто массив смещений следующих за ним записей — такое адресное пространство. Слот за слотом туда добавляется, и добавляется он сразу за хедером, растёт вот так, от начала к концу. По сути, это список смещений, а само смещение — одна цифра, один интежер или даже меньше — смещение тюпла внутри страницы. Поэтому места это занимает очень мало. И когда мы читаем записи, мы сначала смотрим в этот массив, в слот-аррей: говорим «мне нужна запись под номером 4» — это будет слот под индексом 4, — и по нему находим конкретное смещение внутри страницы, идём по нему, обращаемся и считываем четвёртую запись.

[20:58] Штука в том, что сами записи мы пишем не с начала, вместе со слот-арреем (иначе был бы хаос), а с конца страницы. То есть у нас пустая страница, и мы начинаем писать с конца: в самый-самый конец пишем первую запись, а в самое-самое начало — её слот. В конец, после первой, пишем вторую запись, то есть данные растут справа налево, а слот-аррей растёт слева направо. И они двигаются навстречу друг другу — двигаются, двигаются, пока слева записи, а справа слот-аррей не встретятся и места между ними не останется. Вот когда они встретились, мы говорим: всё, страница заполнена.

[21:35] Но как обстоят дела, например, с тем же удалением? Ведь фрагментация в записях, которые в конце, тоже может возникнуть. Так вот, наш слот-аррей позволяет делать дефрагментацию довольно мягко и безболезненно. Во-первых, мы всегда можем дописывать в конец, не парясь, пока у нас есть место. А как только оно закончилось, мы можем подвигать тюплы так, как нам удобно, — но ссылки в слот-аррее, то, на что записи ссылаются снаружи, не изменятся: их адресация внутри страницы слотов, записанных в начале, не поменяется. Это значит, что все клиенты — другие таблицы, ключи, какие-то процессы, которые ссылаются на записи внутри страницы, но делают это через слот-аррей, — во время дефрагментации не будут вынуждены менять свои ссылки, потому что расположение слотированных элементов в начале не меняется. Меняется только относительное внутреннее расположение тюплов, то есть той правой части страницы, которая с конца, а потом просто перезаписывается значение внутри этих слотиков.

[22:42] Поэтому дефрагментация незаметна для клиентов, что сильно облегчает саму задачу дефрагментации: никого не нужно блокировать, не нужно синхронизироваться. И, как показала практика, подход слотированных страниц оказался намного более эффективным, чем просто страниц. Сами тюплы, или записи, о которых мы говорили, тоже могут содержать в себе заголовок. Внутри него может быть информация про видимость этой записи — для конкурентного доступа, чтобы понять, какой транзакции запись видна, а какой ещё нет (об этом мы тоже поговорим позже), — и какие-то битмапы, где налы, а где не налы. То есть тоже метаинформация: сама запись — тоже не элементарная единица. Более того, некоторые базы данных могут делать такие оптимизации, как преджойн, или денормализация записи, и хранить записи, связанные внешним ключом с другой таблицей, в одном тюпле. Это значит, что, когда мы будем делать джойн, считается просто одна страница, где записи уже хранят в себе все данные из обеих таблиц. То есть данные в записи не обязательно даже из одной таблицы, как я приводил пример вначале. Так что сама запись тоже может быть довольно сложной, хитро устроенной вещью.

[23:59] Давайте ещё раз проговорим, как мы представляем себе слотированные страницы. Это страница, в начале которой идёт заголовок, а внутри заголовка — метаинформация. Дальше за заголовком располагаются слоты, слот-аррей, — это относительные смещения записей внутри конкретной страницы. Все клиенты снаружи обращаются сначала в слот-аррей, берут оттуда offset и только потом читают запись. Слот-аррей растёт слева направо, то есть от заголовка в свободную сторону страницы. А сами записи, сами данные, растут справа налево, от конца страницы к середине — тоже к свободному месту. Они растут навстречу друг другу, и когда встречаются, мы либо говорим, что страница заполнена, либо, если есть место для дефрагментации, делаем дефрагментацию: переписываем внутри слотов смещения тех записей, которые были сдвинуты, и продолжаем работать дальше. Вот так устроены слотированные страницы.

[24:56] В этом выпуске мы поговорили о том, чем между собой отличаются SSD-диски и жёсткие диски, поняли, как их работа влияет на представление данных на диске, и разобрались, как устроены слотированные страницы. В следующем выпуске поговорим про B-деревья. Кстати, у истории с жёстким диском из начала выпуска есть не хэппи-энд. Через два-три месяца тот самый начальник, который дал мне SSD, подошёл ко мне и сказал, что я должен вернуть ему этот диск. Сначала я воспринял это как сарказм и шутку и не обратил внимания — ведь возврат диска подразумевал переустановку системы и, что гораздо хуже, возврат к медленному компьютеру. К сожалению, это был не сарказм, и в итоге мне пришлось вернуть диск обратно. Я до сих пор не понимаю, какая у начальника была мотивация так поступить. Но прекрасно помню, как, выйдя из кабинета, я твёрдо решил уволиться, и ничто не могло меня остановить. Так я попал в стартап, где мы использовали Apache Ignite 2 как основную платформу для вычислений. А сейчас я являюсь коммитером в новую версию этой системы — Apache Ignite 3. Так что можно сказать тому начальнику спасибо: ведь кто знает, сколько бы я ещё просидел на месте с мыслью, что разрабатываю что-то крутое, так и не попробовав действительно крутое. Это был подкаст «Тысяча фичей». Не забывайте рассказывать о нём друзьям и коллегам. Давайте прокачивать себя и людей вокруг. Ну а на этом всё. Услышимся!