Базы данных 2/simpledb
Содержание
Задания
Задание 1
- В СУБД есть чтение доступных таблиц (схем) при старте сервера.
- При выполнении запроса создается (на данном шаге можно не парсить запрос, а забить предустановленные значения) QueryPlan с операцией чтения из таблицы. QueryPlan содержит операцию full_scan.
- BufferManager, получив QueryPlan, начинает считывать поблочно из файла с данными и формировать список кортежей для результата.
Замечания:
- В QueryResult атрибут schema указан как список, но на самом деле в результате выполнения запроса нужно иметь только одну схему.
- Для перехода к следующему блоку можно также использовать и смещение в текущем файле данных.
- Так как схема отношения уже определена, дополнительно не нужно хранить ее в блоках или картежах данных. Минимально достаточные данные в блоке: указатель/смещение на следующий блок, внутренняя таблица смещения кортежей, кортежи. В кортежах только данные. Для данных переменной длины (VARCHAR) допустимо использовать любой из методов хранения: указание в первом байте размера поля или указание управляющего символа в конце записи.
Задание до 14 февраля.
Если есть вопросы, то пишите на почту преподавателю: acccko@gmail.com
Для сдачи задания используйте форму: https://goo.gl/forms/81yE6BcY7tZP3wVm2
Задание 2
- Реализовать вставку кортежей (формирование страниц) и запись страниц на диск. Для операции добавления нового кортежа достаточно считать в память последний страницу отношения (или реализовать поиск достаточного свободного места в страницах), добавить в него кортеж и записать страницу на диск.
- Реализовать поддержку В-дерева: операции добавление, удаление, поиск по дереву.
- Реализовать поддержку некластерного индекса (кластерного опционально)
Замечания:
- Для вставки достаточно брать случайные данные, не парсить запрос. Например, исходя из того, встречается ли в запросе слово insert или select, выполнять операции добавления или выборки.
- Количество ссылок в узле/листе дерева определяется исходя из размера страницы на диске.
Информацию об индексах можно хранить в отдельном файле или файлах.
Задание до 1 марта.
Для сдачи задания используйте форму: https://goo.gl/forms/gWhAi0fkObLA1uov2
Задание 3
Парсинг запроса, составление плана. Возможно, будет пропущено.
Задание 4
Добавить менеджера транзакций, журнал и менеджера восстановления. Реализация поддержки транзакций.
- Запись журнала в режиме undo/redo для списка запросов, обозначенных как одна транзакция
- Алгоритм восстановления по журналу
Пояснения:
- Для обозначения транзакции нужно передать в BufferManager последовательно запросы: BEGIN, UPDATE ..., UPDATE ..., COMMIT. Можно использовать предустановленные результаты разбора запросов (не парсить).
- BufferManager прежде чем совершить запрос, должен обратиться к TransactionManager и передать ему запрос и идентификатор клиента (можно использовать номер треда). В свою очередь TransactionManager, получив команду BEGIN, должен зафиксировать начало транзакции и затем обрабатывать все последующие операции. Как только TransactionManager успешно выполнит свою работу с запросов, BufferManager может выполнять свои действия (саму операцию). Как только BufferManager выполнил операцию, он обращается к TransactionManager, чтобы тот мог завершить действия по логированию операции.
- Лог транзакций можно вести в текстовом виде, указывая простые команды типа START transaction_id, WRITE disk_address_to_field old_value new_value, COMMIT transaction_id
- Во время запуска сервера должна быть возможность указать, что этот запуск в режиме восстановления. При этом RecoverManager должен считать журнал и выполнить операции согласно алгоритму восстановления.
Замечания:
- Механизм контрольных точек можно не реализовывать
- Файл журнала можно хранить там же где данные, например, в файле transactions.log
Задание до 14 марта
Для сдачи задания используйте форму: https://docs.google.com/forms/d/e/1FAIpQLSek7ffoAvyeErRCXFkong4dvpqKbV4OLJ8KkgJ1inePig2fGw/viewform?usp=sf_link
Задание 5
Параллельная обработка запросов.
- Реализовать планировщик выполнения операций с блокированием: обработку транзакций перед отправкой к BufferManager для исполнения, таблицу блокировок с очередью из операций.
Пояснения:
- Нужно добавить SchedulePlanner, получающий операции транзакций от TransactionManager, переформировывающий расписание операций, и отправляющий его в BufferManager. SchedulePlanner также должен использовать таблицу блокировок и очередь транзакций для блокировки конкретных элементов данных (кортежей или отношений).
- Используйте типы блокировок: shared, exclusive, update и сооветствующую матрицу возможностей блокировки.
Задание до 24 марта
Для сдачи задания используйте форму: https://docs.google.com/forms/d/e/1FAIpQLSfEayeVldmsxDjk2NlSU7DaicnlSnJWWhj8LBE0ZpbAa0y3Nw/viewform?usp=sf_link
Описание
Описание пока что может отличаться от реального кода (какие-то взаимодействия еще не дописаны), но концепция скорее всего менять не будет.
Есть Server (SocketServer), который может принять и обработать запрос (RequestHandler), затем отправить клиенту ответ. Запрос предварительно парсится на: управляюдище команды, DDL, DML.
Если управляющая команда, то запрос уходит в ControlManager (там можно завершить соединение с клиентом exit)
Если DDL, то запрос отправляется в SchemaManager (там можно запросить список отношений с колонками и индексами, а в будущем создавать и удалять их).
Если запрос DML, то отправляется в QueryManager, который парсит запрос (с помощью QueryParser) и возвращает QueryPlan (список операций, типы операций и отношения, над которыми нужно их делать). Пример операции: table1, full_scan, condition. Результат работы QueryParser QueryManager отправляет в BufferManager, в котором происходят все операции. Если BufferManager нужны данные, которых нет в оперативной памяти, он используя SchemaManager отправляет запросы в DiskManager, который возвращает блоки с диска. Получив блоки (и записи в них) в BufferManager, тот считывает записи оттуда с помощью Row и отправляет наверх к QueryParser, тот в свою очередь отправляет результаты назад к CommandManager, который интерпретирует их и выводит в виде строки пользователю.
При старте Server говорит SchemaManager, чтобы тот запустил свою инициализацию, по умолчанию это значит попросит BufferManager записать в оперативную мапять доступные схемы из файлов.
SchemaManager работает с Schema, который состоит из Column, у которых есть название, тип и размер.
Код
- Стартовый код расположен в git-репозитории: https://bitbucket.org/qs/simpledb
Описание взаимодействия
На данном этапе нужно реализовать подгрузку схемы отношения и взаимодействие менеджера памяти с диском.
Предлагается использовать следующую структуру файловой системы:
Корень базы
--- table.data - файл со страницами с данными
--- table.meta - файл со схемой отношения
Формат схемы отношений
Можно ограничиться читабельным форматом, например, перечислить через точку с запятой имя поля, тип и размер (если он есть):
id;int name;varchar;10 dt;datetime
Можно также хранить тип в виде числа объявленного в Const.
Для данного задания точкой входа является BufferManager.executeQuery, который принимает queryPlan - список из операций (Операция определяется как отношение, тип операции (на данном этапе это full_scan) и предикат).
Адресацию в таблице трансляции в BufferManager можно сделать относительно просто воспринимаемой: в качестве ключа в bufferTable нужно указать имя файла данных и смешение относительно начала файла, например:
table1.data:32
executeQuery запрашивает у SchemaManager файл с данными. Так как нужно выполнить операцию full_scan, то первоначальный адрес страницы, которую нужно загрузить в память будет table1.data:0, нужно проверить, загружена ли она в таблицу трансляции, и если нет, то с помощью DiskManager считать ее.
Также нужно, чтобы у страницы (Page) была ссылка на следующую страницу.
1. BufferManager должен использовать свое адресное пространство при загрузке данных с диска (строить таблицу трансляции). Физический адрес - путь к файлу и смещение для перехода к нужному блоку.
2. Добавить команду добавления записей в таблицу. При этом расположение записей на блоке должно быть оптимальным для схемы.
Как только блок заполнен, его нужно сохранить на диск. Если блок изменен, то через несколько операций (или по таймеру) он также долже быть сохранен на диск.
Блок должен относиться к одному отношению. В блоке должны быть: ссылка на схему отношения, ссылка на следующий блок, бит переполнения (используется, если запись не поместилась в блок целиком)
Схема отношения должна содержать адрес файла, в котором находятся блоки с записями.
