CAP теорема

Техсовет компании Петер-Сервис

1. CAP теорема и ее
применение в
распределенных системах
PCCM + DRA как распределенная система
Сушков Алексей
Начальник группы "PCCM, RBSM"

2. billing.ru
Содержание
DRA + PCCM
CAPтеорема
Распределенные системы
2

3. billing.ru
Важность понимания распределенных систем
Интернет
Поисковики (Google)
Интернет магазины (Amazon)
Облачные сервисы/ вычисления
RAID
Суперкомпьютеры
Распределенные DB
3

4. billing.ru
Распределенные системы
Независимость узлов
Снаружи –как целое
Масштабируемость -следствие
первого
4

5. billing.ru
Как думали устроен мир
5

6. billing.ru
Как на самом деле устроен мир
6
Узел 1 Узел 2 Узел N
Промежуточное звено
Клиент 1 Клиент 2 Клиент M
…
…

7. billing.ru
Проблемы масштабируемости
Проблема Решения
Значительное
время ожидания
ответа от
удаленного узла
1.Применение децентрализованных алгоритмов :
•Работа в условиях отсутствия полной
информации о системе
•Принятие решения на основе локальной
информации
2.Сокрытие времени ожидания :
•Асинхронное выполнение
•Выполнение на клиенте
Распределение
нагрузки
1. Применениеалгоритмов:
•Хешфункция (mod)
•Случайноераспределение
•Round robin
•Распределениев зависимости от нагрузки, % CPU
и т.п.
2. Shared Nothing Architecture
Падение узлов
/штатный
рестарт узлов
1. Репликация
2. Кеширование
7

8. billing.ru
Репликация данных
8
Узел Узел
Клиент
Узел Узел
Клиент
Узел Узел
Клиент
Между узлами Данные на
клиенте
Дублирование
с клиента

9. billing.ru
Распределенная архитектура PCCM
9
DRA
PCCM
(M)
PCCM
(S)
PCCM
(M)
PCCM
(S)……
PCCM
(S) …
Группа IMSI NГруппа IMSI 1

10. billing.ru
Надежная архитектура PCCM + DRA
10
DRA1
PCCM
(M)
PCCM
(S)
PCCM
(M)
PCCM
(S)…
Группа IMSI NГруппа IMSI 1
DRA2

11. billing.ru
Внутренняя архитектура PCCM
11
Event Processor Manager
КЕШ
IMSI 1
КЕШ
IMSI 2
КЕШ
IMSI N
…

12. billing.ru
Модели целостности системы
ACID BASE
•Atomicity—Атомарность
•Consistency—Согласованность
•Isolation—Изолированность
•Durability —Надежность
•BasicAvailability–базовая
доступность
•Soft-state–неустойчивое
состояние
•Eventualconsistency–
согласованностьв конечном
итоге
RDBMS •NoSQL(не всегда)
•Распределенные DB
MySQL, Oracle Cassandra, Dynamo, MongoDB
•Согласованность данных за
счет доступности
•Доступность данных за счет
согласованности
•Большаянадежность •Лучшая производительность
•Пессимистичная стратегия •Оптимистичная стратегия

13. billing.ru
CAP Теорема
13
Consistency Availability
CP AP
CA
ПрофессорЭрикБрюер(Eric A. Brewer) ~ 2000 год

14. billing.ru
CAP Теорема
В любой реализации распределѐнных
вычислений возможно обеспечить не более двух
из трѐх следующих свойствConsistency
(согласованность данных), Availability
(доступность)и Partitiontolerance(устойчивость
к разделению).
Дополнение к теореме:любая распределенная
система должна быть P(устойчивой к
разделению)!
Уточнение теоремы: при отсутствии Pсистема
может (должна)быть CA

15. billing.ru
CAP Теоремадоказательство
A V0
Node 1
V1
B V0
Node 2
A V1
B V0
A V1
V1B V1
V1
1 2 3

16. billing.ru
CAP Теоремадоказательство
A V0
Node 1
V1
B V0
Node 2
A V1
B V0
A V1
V0B V0
1 2 3

17. billing.ru
CAP Теорема –применение
17
Думать о своих данных: разные данные –
разные нужды(книжный магазин vsторговля
акциями);
Может лучше согласованность в конечном
итоге, но 100% доступность?
В высоконагруженных системах массового
обслуживания лучше доступность, чем
согласованность.
Объяснять заказчикам, что при падении
(рестарте) узлов системы возможно обеспечить
только ―согласованность в конечном итоге‖.

18. billing.ru
Чего в презентации не было
Event-DrivenArchitecture
AMQP (Advanced Message Queuing Protocol)
RabbitMQ
Паттерны масштабирования(Scalability Patterns)
Google–поставщик инноваций:
MapReduce
GFS (Google File System)
LevelDB
Применение NoSQL DB
Facebook: Cassandra
LinkedIn: Voldemort
Amazon: DynamoDB
Yahoo: Hbase
Распределенные файловыесистемы
Распределенные хранилища данных RAID
18

19. © 2010ПЕТЕР-СЕРВИС Все права защищены
Алексей Сушков
Начальник группы "PCCM, RBSM"
[email protected]
www.billing.ru
Спасибо за внимание!