Создание базы данных на Rust

Мне всегда было интересно внутреннее устройство баз данных. Недавно наткнулся на курс CMU, где для практического обучения используется написанная на C++ система баз данных Bustub. И приступил к реализации Bustub на Rust, при выполнении заданий курса восполняя недостающее в ней. Поделюсь своими наработками и идеями, переключаясь между внутренними механизмами базы данных, кодом Rust и объяснением. Вот код незавершенной работы.

Анатомия системы баз данных

В дисковой реляционной СУБД выделяют такие уровни:

1. Дисковый диспетчер.
2. Диспетчер буферного пула.
3. Метод доступа.
4. Выполнение оператора.
5. Планирование запросов.

Создавая базу данных от нижнего уровня к верхнему, опишем роль каждого из них с возможным применением функционала Rust, изучим планировщик дисков, политику вытеснения данных из кэша и диспетчер буферного пула.

Планировщик дисков

В современных базах данных применяются различные стратегии хранения: у БД наподобие Redis данные хранятся полностью в памяти, другими используется дисковое хранилище, третьими вроде ClickHouse  —  облачное. Сфокусируемся на дисковом хранилище.

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

Начнем с такого определения для считывания и записи:

type PageId = usize;
trait PageAccessor {
   // Запись «data_buf» в ячейку памяти «page_id»
   fn write_page(&mut self, page_id: PageId, data_buf: Box<[u8; PAGE_SIZE]) -> io::Result<()>;
   // Считывание из ячейки памяти «page_id» в буфер данных.
   fn read_page(&mut self, page_id: PageId, data_buf: Box<[u8; PAGE_SIZE]) -> io::Result<()>;
}

Функционал этих методов описывается их названиями. Поговорим о нем применительно к Rust. Здесь используется типаж, аналог которого в других языках  —  интерфейс. Типажом предоставляется возможность разных реализаций функционала, например хранения данных БД в памяти, на диске или в облачном хранилище.

Имеется также Result, которым показывается успех или неудача выполнения того или иного метода. Для представления возможных состояний значения в Rust применяются алгебраические типы, известные как перечисления. У Result имеется два состояния: Ok, если операция успешна, и Err, если случается сбой.

Наверху обычно располагается уровень планирования DiskScheduler. Им вызываются эти самые вызовы для считывания и записи. Этот уровень  —  то, с чем осуществляется взаимодействие диспетчера буферного пула. В Bustub оно реализовано в виде фонового потока, которым о завершении задачи сообщается по каналу. Они используются в блокирующей или неблокирующей манере.

Роль ОС и управления памятью БД

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

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

В частности, задача управления памятью решается им в системе баз данных эффективным кэшированием в памяти данных с диска. Как и с любым ограниченным ресурсом, кэширование связано с необходимостью вытеснения. На курсе CMU внимание акцентируется на LRU-K. Разберемся, как эта политика вытеснения данных кэша реализуется в системе баз данных.

Фреймы, страницы и вытеснение

Прежде чем переходить к политикам вытеснения, проясним два ключевых термина: фреймы и страницы.

Страница  —  это область дискового хранилища фиксированного размера, в которой данные сохраняются базой данных длительное время. Выбор правильного размера страницы  —  отчасти наука, отчасти искусство. Для этого проекта выберем 4 Кб. Кроме того, что диспетчером буферного пула обрабатываются данные в памяти, она делится им на области фиксированного размера  —  фреймы. Загружаемая в память страница назначается диспетчером доступному фрейму.

Если в свободном пуле доступных нет, диспетчером вытесняется сопоставленная с фреймом страница и освобождается место для новой. Здесь и приходятся кстати алгоритмы вытеснения. Среди них выделяются такие:

• FIFO, то есть «первым пришел, первым вышел»: сначала вытесняется старейший фрейм.
• MRU, то есть вытеснение недавно использованных: вытесняется фрейм, использованный последним.
• LRU, то есть вытеснение давно использованных: вытесняется фрейм, неиспользованный дольше всех.

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

Это ограничение устраняется в LRU-K отслеживанием последних K обращений к каждой записи. Если у записи еще нет K зарегистрированных обращений, недостающие записи считаются бесконечно старыми. Такие записи вытесняются с большей вероятностью, и в памяти остается больше важных страниц.

Основные операции определяются так:

pub type FrameId = usize;
///Осуществляется обращение к фрейму записей.
pub fn record_access(&self, frame_id: FrameId);
///Если фрейм имеется, вытесняемый флаг меняется по запросу.
pub fn set_evictable(&self, frame_id: FrameId, is_evictable: bool);
///Возвращается фрейм, который вытесняется из кэша.
///Если его нет, возвращается «None».
pub fn evict(&self) -> Option<FrameId>;

Как избежать ошибки на миллиард долларов

Рассмотрим в кэше LRU-K метод evict(), которым возвращается тип Option. Этим Option в Rust указывается, что методом может возвращаться значение, а может и не возвращаться. В данном случае так обозначается, что методом может и не обнаружиться вытесняемый frame_id, в таких сценариях возвращается None. Во многих языках возвращается значение Null, что чревато ошибкой времени выполнения, называемой ошибкой на миллиард.

Внутренняя изменяемость в Rust

Все методы в кэше LRU-K работают с общей ссылкой &self, но ими изменяется внутреннее состояние кэша. Это поведение  —  признак внутренней изменяемости как шаблона проектирования Rust, согласно которому изменения осуществляются через общую ссылку.

Внутренняя изменяемость обычно достигается в конкурентном Rust применением таких типов, как Arc  —  сокр. от Atomic Reference Counting атомарный подсчет ссылок, в сочетании с примитивами синхронизации вроде Mutex. Этим обеспечивается, что при внесении изменений разделяемое состояние остается потокобезопасным.

В контексте кэша LRU-K базовая структура данных получается примерно такой:

type History = Vec<Timestamp>; 
// Для реализации использовано время, отсчитываемое с инициализации кэша.
cache: Arc<Mutex<HashMap<FrameId, History>>>

Диспетчер буферного пула

Задача диспетчера буферного пула проста: поддерживать пул фреймов памяти в готовности сохранять страницы с диска в виде фреймов. Когда в базе данных выполняется операция, например запрос или транзакция, и появляется страница в виде фрейма, диспетчером этот фрейм считывается и/или записывается.

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

На Rust много способов получения общего или монопольного доступа. Попробуем четыре из них.

Способ 1

Вернем тип ссылки &  —  проблема в том, что как только обзаводишься им, в игру включается время жизни. И начинается жестокая битва конкурентности.

Сложнее битва за тип изменяемой ссылки ask &mut:

const PAGE_SIZE : usize = 4096;
struct FrameData {
   buffer: Box<[u8; PAGE_SIZE]>
}
frame_holder : Arc<Mutex<Vec<FrameData>>>;
fn read_page(&self, page_id: PageId) -> &[u8; PAGE_SIZE];
fn write_page(&self, page_id: PageId) -> &mut[u8; PAGE_SIZE];
// Каково время жизни возвращаемого «buffer» для обоих методов.
// В конкурентной среде значению нужно пересечь границу потока, а значит, необходимо иметь
// статичное время жизни. В Rust «статичное» — это способ указать, что из памяти необходимо выходить, пока
// это нужно Rust. Так здесь решается проблема обращения к удаленной
// области памяти.

Способ 2

В исходной базе данных CMU, написанной на C++, используется shared_mutex. Согласно рекомендациям по выделению ресурсов, блокировка освобождается при помощи guard из RAII, как только переменная оказывается вне области видимости.

Для конкурентного сценария на Rust это не совсем возможно. Чтобы перемещаться по потоку, значение должно иметь тип Send. Но guard, возвращаемый методами read() и write() из RwLock, помечается как !Send, то есть не send.

Потому что поток, которым блокируется RwLock, должен быть потоком, которым блокировка освобождается:

frame_holder: Arc<Mutex<Vec<RwLock<FrameData>>>>;
fn read_page(&self, page_id: PageId) -> RwLockReadGurad<'_, FrameData>;
fn write_page(&self, page_id: PageId) -> RwLockWriteGuard<'_, FrameData>;
// Все бы получилось, но «RwLockReadGurad» и «RwLockWriteGuard»
// оба «!Send» и поэтому не передаются по потоку. 
// «'_» — анонимное время жизни в Rust.

Способ 3

Почему бы не вернуть сам RwLock?

Могло бы получиться, но это семантически неверно. При получении ответа от write_page я рассчитываю на монопольный доступ до нужного мне времени. Чтобы вернуть RwLock, вызывающему приходится вызывать read() и write(). Из-за чего фрейм блокируется, и это может быть очень плохо. А может и нет.

Попробуем что-то другое, где для доступа вызывающему не нужно блокироваться.

Способ 4

Было бы неплохо, если бы этим frame_holder терялось его содержимое, как только каким-либо действием в базе данных захватывался монопольный доступ? Чтобы фрейм был монопольным, его не должно быть даже во frame_holder. Предполагается, что в индексе во frame_holder может быть, а может и не быть FrameData. На наличие значения  —  Some  —  и его отсутствие  —  None  —  в Rust указывается при помощи Option. Вот как фрейм сохраняется во frame_holder:

frame_holder: Arc<Mutex<Vec<Option<Arc<FrameData>>>>>
/*
Разберем уровни этого типа.
«Arc» — чтобы передавать «frame_holder» по потоку и при необходимости совместно его использовать.
Так «frame_holder» становится «Send». Для полноценного совместного использования он должен быть «Sync».
«Mutex» — для безопасного конкурентного доступа добавляется синхронизация.
«Vec» — для управления фреймами сохраняется непрерывный блок памяти.
«Option» — для указания, что фрейм либо «Some», то есть «FrameData», либо «None»,
полезен в сценариях монопольного доступа.
«Arc» — снова для многочисленных считываний в базе данных, и нужен тип «Send». 
Поскольку общие данные не изменяются, «Mutex» не нужен.
«FrameData» — сами данные с буфером «Frame» и другими вспомогательными значениями.
Вот такими: 
«frame_id»: «FrameId» — какой именно фрейм. 
«page_id»: «PageId» — какой странице он назначается. Пригождается при вытеснении.
«pin_count»: «AtomicU32» — сколько действий БД разыскивается в этом фрейме.
Чтобы вытеснение состоялось, этот показатель должен быть нулевым.
Если фрейм обновлен, его необходимо длительно сохранить БД 
в БД.
*/

Как только операция записи возвращена, во frame_holder по выбранному frame_id появляется значение None. Так обозначается монопольный доступ.

Теперь определяем операцию считывания/записи, по-прежнему используя шаблон RAII и возвращая guard. Благодаря этому при помощи Some(_Arc<framedata>) восстанавливается _frame_holder в типаже drop в WriteGuard, и мы избавляемся от монопольного доступа. Аналогично при выполнении drop в ReadGuard уменьшаем счетчик ссылок на страницы. Хотя это делается и при помощи Arc::strong_count:

struct ReadGuard(Arc<Box<[u8; PAGE_SIZE]>>);
fn read_page(&self, page_id: PageId) -> Option<ReadGurad>;
// Возвращением с предложением типа «Arc», многочисленными действиями БД для того же «page_id»
// содержится, чтобы кромсать копию в данные.
// В Rust «Box» — это способ представления данных в куче.
struct WriteGuard(Box<[u8; PAGE_SIZE]>>);
fn write_page(&self, page_id: PageId) -> Option<WriteGuard>;
// Возвращением с простым «Box<[u8; PAGE_SIZE]>» обозначается запись с монопольным доступом.

// Этим «Option» и там и там обозначается, что фрейм может быть не высвобожден.
// Пора увеличить размер памяти или просто выжидать.

// И в «ReadGuard», и в «WriteGuard» будет реализован типаж «Drop» для RAII.
// Метод «drop(&mut self)» типажа «Drop» выполняется, когда значение оказывается вне области видимости.
// Это аналог деструктора на C++.

Не многовато ли типов? Расскажем еще о двух.

Условные переменные

При наличии в потоке мьютекса, которым в ожидании превращения условия в true, то есть истину, блокируется процессор либо у ОС запрашивается информирование о том, когда условие ожидания будет соблюдено и таким образом ЦП высвободится.

В контексте диспетчера буферного пула условные переменные приходятся кстати в таких сценариях:

• Поток записи, которым ожидается завершение всех активных потоков считывания, после чего получается монопольный доступ к фрейму.
• Поток считывания, которым ожидается, когда обновляемый потоком записи фрейм снова станет доступным.

while frame_lock.as_ref().is_none()
 || (is_write && Arc::strong_count(frame_lock.as_ref().unwrap()) != 1)
 {
    frame_lock = cond
        .wait_timeout(frame_lock, Duration::from_micros(100))
        .unwrap()
        .0;
    // ЦП не удерживается, всеми строчками выше ожидается уведомление для одной и той же условной переменной.
    // В этом примере при помощи «drop()» потока «WriteGuard» уведомляется, что
    // «FrameData» возвращается во «frame_holder».
}
// Взято прямо из реализации, использовано ожидание с тайм-аутом.
// Благодаря этому удалось вырваться из ситуации, когда потоком было упущено уведомление
// от переменной условия в другом месте.

Deref: упрощение доступа к вложенным типам на Rust

Во многих языках программирования доступ к глубоко вложенным типам выполняется по цепочке операторов доступа ., например, для получения самого внутреннего значения [i8; PAGE_SIZE] , обернутого многочисленными слоями вроде ReadGuard, напишем вот это:

readGuard.as_ref().as_ptr(); // Псевдокод, нерабочий.

Этот подход рабочий, но с увеличением вложенности цепочка загромождается. На Rust эта проблема решается элегантно  —  типажом Deref.

Типаж Deref

Благодаря типажу Deref определяется способ разыменования типа. Автоматическим «разворачиванием» вложенных слоев им упрощается доступ при реализации. С Deref доступ к самому внутреннему значению получается так легко, будто других слоев и нет.

impl Deref for ReadGuard {
    type Target = [u8; PAGE_SIZE];

    fn deref(&self) -> &Self::Target {
        self.frame.get_readable()
    }
}
/*
let guard: ReadGuard = ...;
guard. -> Здесь обращаемся напрямую к «[u8;PAGE_SIZE]»
*/

// Этот типаж вместе с его изменяемым аналогом «DerefMut» при необходимости
// реализуется большинством типов-оберток «Box», «Arc», «Mutex». Поэтому доступ к вложенному
// типу на Rust не так утомителен, если выполняется правильно.

Заключение

Мы изучили базовые концепции фреймов, страниц, а также внутренние механизмы диспетчера буферного пула, включая политику LRU-K вытеснения данных из кэша. Этими строительными блоками закладывается основа системы для управления памятью базы данных.

Дальше логично разобрать индексы с акцентом на структуре данных B⁺-дерево  —  важном компоненте для эффективного запроса данных в реляционных БД. Продолжайте учиться и не теряйте любознательности.

Читайте также:

• Построение потоков событий с Rust и Kafka: практическое руководство
• Асинхронная опасность: mmap неявно блокирует ввод-вывод
• 5 функций CLI на Rust для оптимизации привычных инструментов

Читайте нас в Telegram, VK и Дзен

---

Перевод статьи Vishal Kumar: Building Database in Rust — Part I