Об организации кэша распределённой графовой базы данных А.А. Демидов, Институт программных систем им. А.К. Айламазяна РАН RCDL 2011

2 Наша главная задача – снизить синхронизационные издержки Распределённая база данных – это сеть одноранговых серверов Данные разделяются на части и распределяются по серверам системы Клиент подключается к ближайшему серверу и через него имеет доступ ко всем данным в целом Сервер подключения направляет запросы удалённым серверам системы

3 Организация взаимодействия в распределённой среде Клиент обращается к ближайшему серверу через свой кэш Сервер разделяет запрос по узлам, а затем объединяет результаты Любой объект данных имеет постоянный узел приписки с доской объявлений, которая используется для синхронизации изменений Возможно создание копий объекта на промежуточных узлах с целью кэширования

4 Нарушение структуры связей при конкурирующем доступе Во время работы с кэшем те же объекты могут изменяться в БД конкурирующими транзакциями Доски объявлений разрешают конфликты запись/запись, для чтение/запись - неэффективны Варианты решения: 1. Использование среза в длинных транзакциях уровня Snapshot 2. Контроль по формальным правилам (Amazon Dynamo) 3. Контроль неизменности при подтверждении (STM - Хаскель) 4. Контроль по непрерывности - необходимо задание топологии

5 Недостатки методов обеспечения непротиворечивости данных Недостатки: 1. Длинные транзакции Snapshot – потеря актуальности кэша по завершении транзакции 2. Набор формальных признаков – узкая специализация, сложность изменения системы 3. Транзакционная память – невозможно учесть влияние добавляемых записей 4. Непрерывность – нужен явный граф структуры данных Важно! Подходы 2-4 позволяют кэшу использовать данные различной степени актуальности

6 Отношение обусловленности – обобщение функциональной зависимости Если при изменении одного элемента данных a значение другого элемента b теряет смысл в рамках принятой модели данных, то имеется направленная зависимость: ab Множество всех пар зависимых элементов базы данных назовём непосредственным отношением обусловленности элементов. Классификация связей: Зависимость от ключа Внешняя зависимость Внутренняя зависимость

7 Задание топологии через отношение обусловленности Отношение обусловленности задаёт топологию зависимостей в пространстве данных всех серверов Непосредственные зависимости формируют классические объекты со связями Учёт опосредованных зависимостей приводит к независимым друг от друга объектам- замыканиям

8 Два вида объектов - классические и замкнутые

9 Замкнутые объекты – основа ослабления синхронизации Атомарность операций с замкнутым объектом гарантирует отсутствие противоречий Концепция замкнутых объектов бесполезна в системах реального времени: не должно быть разницы, какой из узлов обновил БД первым – задачи моделирования Замкнутые объекты имеют свойство разрастаться при усложнении связей, необходимо применять классические + вводить синхронизацию

10 Работа кэша клиента с данными различной степени актуальности Кэш не очищается – можно использовать данные, загруженные предыдущими транзакциями Каждый объект имеет две метки: время загрузки в кэш t TR и время модификации на сервере t CH Если при загрузке нового объекта a выясняется, что ab и t CH (a) t TR (b), то старый объект b перегружается, либо происходит откат

11 Software Transactional Memory++ запись незамкнутых объектов При изменении объекта a достаточно установить метку версии на сам a и все непосредственно влияющие на него объекты: xa При изменении метки сервер контролирует совпадение текущего значения и значения, видимого транзакции

12 Оценка эффективности кэша (T 1/2 = 120, K сложности = 1..10) Пусть общее число объектов БД равно N, в транзакции в среднем участвует K объектов, а в каждый период времени T происходит изменение N/2 объектов. Вероятность встретить изменённую область: P(t) ~ 1 – 2 -tK/T

13 Вопросы?

14 Спасибо за внимание