Реализация уровня изоляции Read Committed для древовидных структур данных Федотовский Павел Валерьевич 345 группа Научный руководитель: Чернышев Г.А., ассистент кафедры информатики СПбГУ Санкт-Петербург, 2012

Транзакционная система Решение для обеспечения: – Параллельного доступа (правильность и производительность) – Надежность и доступность системы Правильность определяется через уровень изоляции (4 классических) Примеры: – Финансовые системы (банковские операции со средствами) – Электронная коммерция (интернет-магазины)

Постановка задачи Многомерный индекс с поддержкой транзакций – Менеджер блокировок – Подсистема обработки транзакций – Древовидная структура данных (в данном случае GiST) – R-дерево, B+-дерево – Менеджер памяти ACM SIGMOD Programming Contest 2012 – Команда SPbSU, Павел Федотовский, Георгий Ерохин, Кирилл Чередник

Операции Точечный запрос, запрос на диапазон (n- мерный прямоугольник) Вставка, обновление, поиск Подробнее на сайте соревнования

Реализация (1/2) Generalized Search Tree (обобщенное дерево поиска) Hellerstein et al., 1995

Реализация (2/2) Менеджер блокировок – Потерянное обновление – Поиск тупиков Храним состояние записи – грязное чтение

Результаты Построен прототип многомерного транзакционного индекса (READ COMMITTED) – Реализован менеджер блокировок – Реализована подсистема обработки транзакций – Реализован GiST Пройдены тесты на корректность место на публичных тестах Статья на конференции СПИСОК-2012