#25: Buffer pools: почему БД реализуют часть ОС

[00:21] Здарова! Меня зовут Саша Пахомов, и я инженер, который любит своё дело. Вы слушаете подкаст, в котором разработчик современной базы данных изучает, как они работают, и делится знаниями со слушателями. В этом выпуске вы узнаете, как в течение 20 лет в Postgres жил баг, который приводил к безвозвратной потере данных, и почему инженеры хранилищ пишут часть операционной системы сами. Это выпуск про то, как базы данных управляют памятью. Поехали!

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

[01:26] Чтобы комфортно следовать за моими мыслями, нам с вами нужно синхронизировать картинки в голове — чтобы у вас было единое представление, вокруг которого будет строиться повествование. Это несложно! Представьте жёсткий диск с магнитной головкой. Медленный такой, зато надёжный. С ним мы взаимодействуем, чтобы обеспечить долговечность данных. Единица чтения и записи — это страница. Что внутри страницы, нас на этом уровне абстракции в целом не интересует. Для простоты пусть у нас будет большое B-дерево из огромного количества страниц, которое не вмещается в оперативную память. Но мы часто читаем данные из B-дерева, добавляем новые страницы и модифицируем существующие — в общем, делаем то, что обычно делает база данных.

[02:18] Чтобы не ходить за одной и той же страницей два раза на медленный диск, мы её кэшируем в оперативной памяти, в специальном месте, которое называется buffer pool. Таким образом, наши запросы идут не напрямую на диск, а обращаются в buffer pool и получают страницы оттуда. Если страница уже есть внутри пула, то указатель на неё сразу возвращается — это очень быстро. А если такой страницы нет, то она подгружается с диска, сохраняется в buffer pool, и только потом указатель возвращается процессу.

[02:46] Итак, общая картинка у нас такая. Есть диск, на нём хранится огромное B+-дерево в виде набора страниц. Напрямую с диском взаимодействует buffer pool, который кэширует страницы. Наши запросы всегда идут через buffer pool и спрашивают у него адреса страниц в оперативной памяти. Помимо чтения страниц, мы их модифицируем, а это значит, что buffer pool не только читает с диска, но и пишет туда.

[03:18] На первый взгляд реализовать это довольно просто. Пришёл в buffer pool запрос на обновление страницы. Buffer pool говорит «окей», обновляет её состояние в оперативной памяти и перезаписывает новую версию страницы на диск. Дело сделано. Но не тут-то было. Ходить на диск при каждом обновлении страницы очень дорого и невыгодно. А что если ту же страницу попросят обновить ещё 10 раз в следующую секунду? Почему бы не обновить страницу в оперативной памяти 10 раз и записать её финальную версию на диск один раз?

[03:46] На самом деле примерно так buffer pool и работает. Он помечает страницы в оперативной памяти специальным флагом, который говорит, что состояние страницы в памяти отличается от её состояния на диске. Ещё такие страницы называют dirty pages, или грязными страницами. И раз в какое-то время buffer pool сбрасывает грязные страницы на диск, и они перестают быть грязными.

[04:06] Внимательный слушатель заметит, что такое поведение не обеспечивает долговечность. Ведь мы можем записать страницу в buffer pool, она станет грязной, и запрос завершится успехом — но в этот момент отключается электричество. Получается, на диске осталась старая версия страницы, и мы потеряли информацию. Базы данных научились обходить это ограничение, но как именно — узнаем позже, в следующих выпусках. А пока давайте представим, что есть некоторый способ восстановить незаписанные грязные страницы даже в случае сбоя электричества.

[04:42] Помимо периодической записи грязных страниц на диск, buffer pool занимается ещё одной нетривиальной задачей — это вытеснение существующих страниц из оперативной памяти. Ведь рано или поздно место внутри пула закончится, а у него попросят страницу, которая не загружена в память. Придётся выбрать жертву для вытеснения из кэша и подгрузить на её место нужную страницу. Позже мы рассмотрим алгоритмы вытеснения поподробнее.

[05:07] Итак, мы познакомились с buffer pool как с концепцией. И эта концепция реализована в операционных системах на уровне файлового API. То есть когда мы работаем с файлами в Linux, мы уже делаем это через кэш: Linux сам кэширует страницы, и получается, что нам как разработчикам баз данных думать об этом не нужно. Красота. Некоторые базы данных действительно используют buffer pool операционной системы — например, Postgres. Но большинство баз данных реализуют свой собственный buffer pool, то есть делают часть работы операционной системы, а на диск ходят в обход Linux buffer pool с помощью специального флага O_DIRECT.

[05:43] И вот что на эту тему писал Линус Торвальдс в 2007 году. «Правильных способов использования флага O_DIRECT ноль. Вся идея о direct I/O, о прямом доступе к файлам, — абсолютно мозговыносящая. Просто скажи нет. Представь: вот твой мозг — большой, наполненный. А вот твой мозг, когда он думает про O_DIRECT, — маленькая точка, сжавшаяся в крохотное пространство. Вопросы есть? Мне надо было сопротивляться жёстче, когда мы придумывали O_DIRECT. Нет ни одной причины его использовать. Буфер тебе нужен в любом случае. Есть хорошие способы контролировать page cache вместо того, чтобы играть в игры и думать, будто page cache вам не нужен».

[06:28] Обратите внимание на уровень токсичности письма. Сейчас Линус вроде бы общается повежливее. Но если попытаться вникнуть в суть, она понятна: нет ни одной причины использовать флаг O_DIRECT, а его использование опасно. Забегая вперёд — Линус был неправ. К его сожалению, был неправ. Хотя в чём-то и прав.

[06:53] Чтобы проще было понять, давайте быстро посмотрим, как работает buffered I/O в Linux — тот, за который топит Линус. Это знакомый нам buffer pool, который предоставляет интерфейс чтения и записи: мы можем писать и читать блоки памяти. Штука в том, что, вызвав метод write, мы можем быть уверены только в том, что блок памяти записался в кэш. А вот когда он попадёт на диск, мы понятия не имеем. Однако есть способ заставить операционную систему сбросить все грязные страницы на диск — это метод fsync. То есть чтобы записать блок памяти на диск и быть уверенными в его долговечности, нам нужно вызвать два метода: сначала write, затем fsync.

[07:36] Такой паттерн записи очень неоптимален, ведь fsync сбрасывает на диск все страницы в кэше — точнее, все грязные страницы в кэше. Получается, чтобы записать одну страницу, мы постоянно пишем несколько. Это глупо. Помимо очевидных проблем с производительностью, есть ещё и неочевидные, упущенные проблемы. Например, база данных знает, что работает с B+-деревом, и хочет кэшировать внутренние страницы всё время, а листовые — вытеснять, ведь кэш не бесконечный. Это своего рода оптимизация, которую может сделать база данных, но не операционная система: для операционки мы просто пишем байты, и она совершенно не знает, что это страница B-дерева.

[08:14] Но если и это для вас недостаточная мотивация реализовать свой кэш, то вот вам последний гвоздь в гроб файловых кэшей операционной системы. Знали ли вы, что примерно 20 лет в Postgres существовал код, который неправильно обрабатывал вызовы fsync? И мало того что неправильно — эта обработка ошибок вызовов fsync приводила к тому, что Postgres перезаписывал на диск неправильные страницы, то есть, грубо говоря, стирал их, и это приводило к потере данных. Сейчас расскажу, как это происходило. Следите за руками.

[08:51] Мы знаем, что Postgres использует buffer pool, который предоставляет операционная система. Он работает с ним и пишет туда страницы, они какое-то время остаются грязными. И раз в какое-то время в Postgres приходит процесс — называется он там что-то вроде перезаписи чек-сумм — суть в том, что в какой-то момент эти грязные страницы нужно сбросить на диск. Всё очень просто. Во время сбрасывания этих грязных страниц через вызов fsync может произойти ошибка. Если всё прошло хорошо — мы перезаписали страницы, вызвали fsync, они флашнулись на диск, всё долговечно, отлично. Но иногда бывает так, что fsync возвращает ошибку, причём ошибку супернетривиальную: если мы открыли несколько файловых дескрипторов, там будет вообще другое поведение с ошибками.

[09:32] Но допустим, мы даже про это не думаем. У нас есть, например, три грязные страницы, мы вызываем fsync: первая страница сбросилась, вторая начинает сбрасываться — и что-то происходит, свет моргнул или коротнуло, и fsync вернул ошибку, то есть сказал: «я не смог сбросить кэш на диск». Postgres понимает, что что-то пошло не так. И как он обрабатывал эту ошибку раньше? Он вызывал fsync ещё раз, то есть делал retry — там прямо натурально был цикл, который дёргал fsync, fsync, fsync, пока всё это дело не выполнится.

[10:04] Штука в том, что после того, как произошла ошибка при первом вызове fsync, все страницы в буфере очищались — и очищаются, вроде бы, до сих пор. То есть если мы с первого раза не смогли выполнить fsync, то, вызвав его второй раз, мы перезатрём страницы — даже старые версии страниц перезатрём просто пустыми, потому что операционная система сбрасывает грязные страницы, которые держались в памяти, уже после первой ошибки.

[10:28] Вот как вы думаете, зачем? Просто нахрена так делать? Ответ очень простой: потому что если этого не делать, может произойти утечка памяти. Каким образом? Объясняю. Вот мы делаем fsync не на наш жёсткий диск или SSD, который всегда вставлен в компьютер, а на флешку — ведь абстракция файловой системы нам это позволяет. Мы не знаем, с чем работаем, можем работать и с флешкой. И в момент fsync мы просто выдёргиваем флешку. Тогда последующие вызовы fsync будут всегда ошибочными: всё, мы её уже не вставим, а если вставим, то там нужно будет всё заново. А вот эти страницы в памяти останутся навсегда, они по сути зависнут — и это своего рода утечка.

[11:10] То есть смотрите: из-за того что операционная система такая широкая и думает обо всём, даже о флешках, мы как разработчики базы данных должны страдать и как-то обрабатывать эти fsync непонятно как. То есть если у нас первый fsync провалился, то мы крашимся и делаем recovery — но это, очевидно, не самый лучший способ. Хотя он хотя бы рабочий, что, кстати, в Postgres, по-моему, и сделали. Либо мы пишем свой buffer pool и используем флаг O_DIRECT, против которого топит Линус Торвальдс, — потому что тогда мы точно будем знать, что мы записали: мы пишем напрямую на диск в обход операционного кэша. Собственно, как большинство баз данных и делает.

[12:21] Помимо очевидных косяков вроде истории с флешками, свой buffer pool даёт нам ещё кое-что. Есть страницы, которые заведомо лежат почти у корня дерева и потому будут читаться очень часто — например, рут и промежуточные узлы. Их мы можем, так сказать, запинить: подгрузить в buffer pool и сказать «вот эти вообще никогда не вытесняй». Сбрасывать их на диск, когда они становятся грязными, и снимать грязный флаг — можно, но вытеснять не нужно, потому что мы точно будем их читать. Давай зарезервируем под них место. Сделать это можно, используя свой buffer pool.

[12:53] И это даёт пространство для прикольной оптимизации. Смотрите: если мы знаем, что страницу запинили — буфер сказал «я её запинил, вот тебе её адрес», — то мы точно знаем, что адрес этой страницы больше никогда не поменяется. Что это значит? Что мы можем прямо в ссылках самого B-дерева, в нашем представлении в оперативной памяти (это же часть структуры — узлы, ссылки), хранить не ID-шник страницы, а сразу её адрес. Если бы мы не знали, что страница запинена, нам пришлось бы при обходе дерева за каждой страницей ходить в buffer pool за адресом в оперативной памяти — ведь только он знает, где страницы лежат.

[13:34] А так, зная, что страница запинена, мы делаем такое in-place-сохранение прямо в дереве: раньше хранили ID-шник страницы и по нему ходили в buffer pool, получали адрес и шли по адресу, а теперь храним адрес прямо в дереве, потому что знаем, что страница не вытеснится и адрес всегда будет правильным. Это минус один поход по памяти во время обхода дерева, который случается очень часто. Крутая оптимизация — и она возможна только благодаря использованию своего buffer pool. Такие дела.

[14:08] Наверное, теперь пришло время поговорить про политики замещения страниц. Это, наверное, самая интересная с алгоритмической точки зрения часть работы и реализации buffer pool. Во-первых, их довольно много, и каждый алгоритм имеет свои преимущества и недостатки. Но давайте для начала просто разберёмся, какую проблему мы решаем этими алгоритмами.

[14:36] В какой-то момент работы buffer pool мы понимаем, что он заполнен. У него, скажем, всего 1024 фрейма, и все они заполнены, а у нас спрашивают новую страницу. Нам нужно подгрузить её с диска — это очевидно, — но нужно положить её на чьё-то место. И вот когда мы выбираем, на какое место положить страницу, перед нами встаёт довольно сложный выбор. Если мы будем, например, рандомно выбирать страницу и перезаписывать её, то можем оказаться в ситуации, когда мы всё время берём тот же самый рут пресловутого дерева и перезаписываем его очень часто. А так как мы часто его читаем, то тут же снова подгружаем — и создаём нагрузку на buffer pool своим неоптимальным выбором выгружаемой страницы.

[15:21] То есть страницы, которые часто используются, надо бы как можно дольше хранить в buffer pool, а те, что используются редко, — как можно быстрее вытеснять. По сути, это и есть задача, которая стоит перед алгоритмами замещения страниц. Первый, самый очевидный и прямолинейный алгоритм — это first in, first out. Обычная очередь, в которую мы помещаем идентификаторы страниц при чтении с диска, а когда место заканчивается — берём с другого конца, выдёргиваем ID-шник: «ага, вот ты у нас выгружаешься». И идём выгружать эту страницу.

[15:58] Такая вот тупая реализация. И она не работает в современных системах. Вот почему. Мы, опять же, затянули тот же рут, он в какой-то момент оказался в конце очереди, и мы его стопроцентно выгрузим. Или у нас какая-то специфичная нагрузка на базу: на этом шарде мы часто читаем только определённый диапазон ID-шников, и они все могут поместиться в buffer pool — то есть по сути мы работаем как с in-memory-базой. Но помимо тех ID-шников, с которыми мы работаем 95% времени, есть ещё 5% каких-то других, которые прилетают рандомными запросами. И вот эти рандомные запросы будут вымывать из кэша нужные ID-шники — просто потому, что алгоритм вообще никак не учитывает частотность. Он просто по кругу выгружает-загружает. First in, first out неоптимален, и buffer pool современных баз данных его не использует.

[16:55] Первое очевидное развитие и оптимизация FIFO — это least recently used, LRU. Та же самая очередь, представьте: мы читаем страницы и запихиваем их туда. Но помимо того чтобы просто добавить, мы кое-что делаем. Когда у нас в очередной раз спрашивают страницу — например, мы первый раз загрузили страницу с ID-шником 1 и поместили её в очередь, а потом через какое-то время её снова спрашивают, и она всё ещё в очереди, в buffer pool, — мы просто пикаем её оттуда, где она лежит, и кладём снова в конец. То есть тех, кого спрашивают по второму, третьему, десятому разу, мы не просто добавляем, а достаём и перекладываем в конец.

[17:43] Таким образом момент их вытеснения откладывается, потому что к концу очереди быстрее всего придут те, кого мы не используем, — и оттуда мы возьмём тех, кто использовался один-два раза, реже. А те, кто используется часто, будут крутиться в начале очереди, тоже создавая контеншн, но зато, скорее всего, не попадут в конец. Проблема тут как раз в этом контеншне: мы создаём нагрузку на структуру данных на ровном месте. Когда мы работаем в параллельном, распределённом мире, когда у нас много потоков и они все это делают, — эта очередь стопроцентно становится узким местом.

[18:21] Есть способы оптимизации этого узкого места. Называется этот алгоритм 2Q, или LRU с двумя очередями. Первая очередь — это просто first in, first out. Но вместо того чтобы доставать из неё и класть в конец, то есть создавать нагрузку горячими страницами на одну структуру данных, у нас есть вторая, как бы горячая очередь, в которую мы перекладываем страницу из первой, если её попросили второй раз. И последующие обращения — второй, третий, десятый, двадцать пятый, сорок третий раз — будут крутиться уже в этой горячей очереди и не нагружать основную, на которой мы принимаем решение вытеснять или нет. Поэтому она работает чуть лучше, но, вроде бы, особо и этот алгоритм никто не использует, потому что есть ещё лучше. И вот они.

[19:11] Самый, наверное, френдли для подкаста и простой для объяснения алгоритм называется Clock. Его очень просто понять. Давайте представим себе часы — обычный циферблат: 1, 2, 3 и так далее до 12. 12 вверху, 6 внизу, 3 справа, 9 слева. И есть у этого циферблата всего одна стрелка. Циферки 1, 2, 3, 4, 5 — это ID-шники наших страниц, которые мы загружаем. Вот так, в кольцо, в ринг, расположены наши страницы. Что мы делаем? Загружаем первую страницу на единичку, вторую — на двойку, третью — на тройку, то есть загрузили 12 страниц. Всё, для следующей, тринадцатой, страницы уже нужно выбрать из циферблата ту, которая подлежит вытеснению.

[20:04] Как мы это делаем? Во-первых, когда какой-то процесс спрашивает у нас страницу, мы, помимо того чтобы загрузить её и положить в эти часы, в этот Clock, ещё выставляем у каждой страницы атрибут, который называется бит доступа. Условно, это либо единичка, либо нолик под каждой циферкой. Единичка значит, что элемент используется: когда у нас просят страницу — «дай мне эту страницу», — мы выставляем этот битик в единичку, каждый раз, всегда. А обнуляет эти битики следующий процесс — та самая наша стрелочка посередине.

[20:38] Вот она начинает с 12 и пошла: чик — встала на единичку циферблата, смотрит на её бит доступа. Если бит равен единице — кто-то её недавно читал, — то всё, что делает стрелочка, это переставляет битик с единицы на ноль и идёт дальше. У двойки смотрит — тоже единичка, переставляет на ноль. Перешла на тройку — а там нолик. Эта же стрелка всё время ходит по кругу, и за круг у тройки остался нолик, никто заново не проставил единичку. Значит, это довольно неплохой кандидат на вытеснение: как минимум за обход циферблата его никто не использовал, иначе стояла бы единичка. Поэтому у него нолик — и эта страница выгружается. На её место загружается другая, ей ставится единичка, и пошли дальше на четвёрку. И вот так по кругу. Алгоритм простой, как часы. И он работает.

[21:36] А ещё, что самое интересное, он CAS-friendly. CAS — это compare-and-swap; я, может быть, когда-нибудь про это расскажу. В общем, это инструкция, которая атомарно проверяет значение в регистре, записывает туда другое значение и возвращает вызывающей стороне результат — было ли в регистре то значение, которое ты предполагал, или другое. Он очень эффективен в concurrency-режиме: когда у нас большой контеншн со стороны огромного количества потоков, CAS — это прямо неблокирующий способ взаимодействия. И Clock в этом плане CAS-friendly: он не становится узким местом, когда потоков много-много, и использует такую структуру данных — что очень круто. Кстати, одна из модификаций алгоритма Clock используется в buffer pool операционной системы Linux.

[22:27] Так, с Clock вроде разобрались. И, наверное, ещё один алгоритм я вам расскажу — тоже довольно популярный. Он, кстати, используется в очень знаменитой Java-библиотеке для кэширования — Caffeine. Работает он так. Вместо того чтобы какой-то процесс ходил по структуре данных или набору структур — по очередям, например — и выбирал того, кого нужно вытеснить, алгоритм LFU (а точнее, TinyLFU — то есть алгоритм, который зависит от частотности использования) ищет не кандидатов на вытеснение, а кандидатов на сохранение.

[23:08] Очень близко по концепции работает, например, garbage collector G1 в Java: он копирует объекты из одной области памяти в другую, более защищённую, из которой они точно не вытеснятся. У LFU-алгоритма ровно такая же философия. У него есть несколько очередей. Есть входная очередь — приём, — это просто очередь вновь добавленных элементов, реализованная по политике LRU, которую мы рассматривали почти в самом начале. В неё накидываются вновь прибывшие страницы. В какой-то момент страницы, которые часто в ней используются, проходят через специальный частотный фильтр — вместо той второй очереди в LRU — и попадают в очередь испытания, а потом в очередь защищённых.

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

[24:39] Но он немного как гистограмма — не точный, потому что если каждый раз точно увеличивать, это будет накладно по памяти. Условно: если мы запросили страницу тысячу раз, там будет число типа 100; а если 100 раз — число будет 10. И мы понимаем, что одна страница используется в 10 раз чаще другой, а та, другая, — ещё в 2 раза чаще, чем все остальные. Поэтому эти две страницы лучше отложить в защищённые, и там они будут долго лежать, а мы не будем их вытеснять. А вот страницы, про которые непонятно, — какие-то листовые, которые мы прочитали, посмотрели и откинули, — их уже так часто не используют. Это хорошие кандидаты на вытеснение, и они вытесняются из очереди испытания.

[25:21] В подкасте это, наверное, немного сложно, но, надеюсь, я донёс мысль: у нас есть три очереди — приём, испытание, защита. Все попадают сначала в приём, потом проходят частотный фильтр, попадают в испытание, проводят в нём какое-то время, и принимается решение — переместить их в защищённую очередь или вытеснить. Вот так работает TinyLFU-алгоритм, который есть, например, в Caffeine.

[25:43] Сегодня мы разобрались с тем, как работает buffer pool, познакомились с алгоритмами вытеснения страниц и поговорили о том, почему база данных реализует свой собственный buffer pool в обход операционной системы. Ну и, конечно же, теперь мы знаем, что и на старуху бывает проруха. Хотя в нашем случае это не старуха, а дед. Согласитесь, есть какое-то приятное чувство внутри, когда токсичные люди бывают неправы. Прямо душа радуется. В следующих выпусках обязательно продолжим смотреть на деревья. Пока!

[26:12] И помните, сегодня я упоминал, что есть способ восстановить грязные страницы, даже если они не записались на диск? Это redo log. Его тоже разберём. Не забывайте делиться подкастом с друзьями и коллегами — давайте прокачивать себя и людей вокруг. И не будьте токсиками. Ну а на этом всё. Услышимся! И до новых встреч!