Скачать презентацию
Идет загрузка презентации. Пожалуйста, подождите
1
Об организации кэша распределённой графовой базы данных А.А. Демидов, Институт программных систем им. А.К. Айламазяна РАН RCDL 2011
2
2 Наша главная задача – снизить синхронизационные издержки Распределённая база данных – это сеть одноранговых серверов Данные разделяются на части и распределяются по серверам системы Клиент подключается к ближайшему серверу и через него имеет доступ ко всем данным в целом Сервер подключения направляет запросы удалённым серверам системы
3
3 Организация взаимодействия в распределённой среде Клиент обращается к ближайшему серверу через свой кэш Сервер разделяет запрос по узлам, а затем объединяет результаты Любой объект данных имеет постоянный узел приписки с доской объявлений, которая используется для синхронизации изменений Возможно создание копий объекта на промежуточных узлах с целью кэширования
4
4 Нарушение структуры связей при конкурирующем доступе Во время работы с кэшем те же объекты могут изменяться в БД конкурирующими транзакциями Доски объявлений разрешают конфликты запись/запись, для чтение/запись - неэффективны Варианты решения: 1. Использование среза в длинных транзакциях уровня Snapshot 2. Контроль по формальным правилам (Amazon Dynamo) 3. Контроль неизменности при подтверждении (STM - Хаскель) 4. Контроль по непрерывности - необходимо задание топологии
5
5 Недостатки методов обеспечения непротиворечивости данных Недостатки: 1. Длинные транзакции Snapshot – потеря актуальности кэша по завершении транзакции 2. Набор формальных признаков – узкая специализация, сложность изменения системы 3. Транзакционная память – невозможно учесть влияние добавляемых записей 4. Непрерывность – нужен явный граф структуры данных Важно! Подходы 2-4 позволяют кэшу использовать данные различной степени актуальности
6
6 Отношение обусловленности – обобщение функциональной зависимости Если при изменении одного элемента данных a значение другого элемента b теряет смысл в рамках принятой модели данных, то имеется направленная зависимость: ab Множество всех пар зависимых элементов базы данных назовём непосредственным отношением обусловленности элементов. Классификация связей: Зависимость от ключа Внешняя зависимость Внутренняя зависимость
7
7 Задание топологии через отношение обусловленности Отношение обусловленности задаёт топологию зависимостей в пространстве данных всех серверов Непосредственные зависимости формируют классические объекты со связями Учёт опосредованных зависимостей приводит к независимым друг от друга объектам- замыканиям
8
8 Два вида объектов - классические и замкнутые
9
9 Замкнутые объекты – основа ослабления синхронизации Атомарность операций с замкнутым объектом гарантирует отсутствие противоречий Концепция замкнутых объектов бесполезна в системах реального времени: не должно быть разницы, какой из узлов обновил БД первым – задачи моделирования Замкнутые объекты имеют свойство разрастаться при усложнении связей, необходимо применять классические + вводить синхронизацию
10
10 Работа кэша клиента с данными различной степени актуальности Кэш не очищается – можно использовать данные, загруженные предыдущими транзакциями Каждый объект имеет две метки: время загрузки в кэш t TR и время модификации на сервере t CH Если при загрузке нового объекта a выясняется, что ab и t CH (a) t TR (b), то старый объект b перегружается, либо происходит откат
11
11 Software Transactional Memory++ запись незамкнутых объектов При изменении объекта a достаточно установить метку версии на сам a и все непосредственно влияющие на него объекты: xa При изменении метки сервер контролирует совпадение текущего значения и значения, видимого транзакции
12
12 Оценка эффективности кэша (T 1/2 = 120, K сложности = 1..10) Пусть общее число объектов БД равно N, в транзакции в среднем участвует K объектов, а в каждый период времени T происходит изменение N/2 объектов. Вероятность встретить изменённую область: P(t) ~ 1 – 2 -tK/T
13
13 Вопросы?
14
14 Спасибо за внимание
Еще похожие презентации в нашем архиве:
