В одной из предыдущих лекций обсуждали, почему невозможно сделать идеальное распределенное хранилище. Сейчас докажем, почему:
Теорема CAP гласит, что в распределенной системе хранения данных невозможно соблюсти все эти три свойства:
Consistency - Согласованность
Availability - Доступность
Partition tolerance - Устойчивость к разбиению
Согласованность - во всех узлах в один момент времени данные не противоречат друг другу
Доступность - любой запрос к распределенной системе завершается корректным откликом в пределах заданного интервала времени, однако без гарантии, что ответы узлов совпадают
Под корректным откликом подразумевается то, что база данных не ответила “не знаю” или “ошибка сервера” - в этом случае корректным откликом будут считаться неправильные данные от базы
Устойчивость к разбиению - расщепление системы на несколько изолированных секций не приводит к некорректности отклика от каждой из секций
Принцип CAP сформулирован в 2000 году профессором Брюером, а позже в 2002 году был доказан как теорема
Так как доказательство нудное, продемострируем CAP теорему на таком примере:
Есть телефонный сервис, позвонив на который, можно совершить три операции:
Записать на дату в будущем какое-то событие
Изменить запись (в том числе удалить)
Узнать все события на конкретную дату
Для реализации данного сервиса покупается блокнотик, на каждого клиента есть бесконечный листочек в блокнотике. В ходе звонка специальный человек делает операции с блокнотом
Данный сервис становится очень востребованным
Заметим, что в этом случае блокнотик - централизованная система, поэтому клиенты вынуждены стоять в очереди, пока работник делает записи. Наружается Availability. К тому же эту систему попросту нельзя обслужить
Но зато в этой системе соблюдаются Consistency (потому что блокнотик один) и Partition tolerance (потому что блокнотик один)
В ходе расширения бизнес покупается второй блокнотик, а телефонная очередь делится на две части
При помощи теории вероятности мы можем определить сколько нам нужно таких блокнотиков, чтобы быть достаточно эффективными и не потратить все состояние
Первое время все хорошо, но потом выясняется, что клиент позвонил в первый блокнотик, потом телефонная очередь направила его ко второму блокнотику, но они имеют разные данные - мы их никак не синхронизируем
Такая система называется систему с независимыми узлами с балансировкой нагрузки. В ней соблюдаются Availability и Partition tolerance
Тогда есть третий вариант: распределенная система с транзакционной репликацией данных
В ходе звонка клиента, требуемое изменение вносится в первый блокнотик, потом вносится во второй блокнотик (и так далее), а клиенту сообщается, что все хорошо, трубка вешается
Здесь соблюдаются Consistency и Partition tolerance
Так как блокнотики общаются между собой, производительность (а значит доступность) немного пострадала - увеличение узлов приводит к увеличению нужных запросов к другим участникам для соблюдения целостности
С помощью теории вероятности мы можем понять, какое максимальное число узлов можем поставить, чтобы соблюдать поддерживать Availability на нужном нам уровне
Также на каждой связи между двумя узлами можем сделать очередь запросов. Таким образом, если человек за каким-то блокнотиком внезапно умер, целостность данных не нарушится
Но если нет связи со вторым узлом, как понять: умер ли сервер либо нарушилась ли связь?
Мы можем сделать 3 варианта:
CA, тогда P будет нарушаться с какой-то вероятностью
CP, тогда ждем таймаут от другого узла
AP, тогда заранее даем клиент какие-то данные (пусть даже неправильные)
Почти все централизованные SQL-решения соблюдают CA, большинство NoSQL-решений соблюдают AP. Разберем их поподробнее:
Key-Value
В классическом значении база данных хранит пары ключ-значения и имеет операции добавления пары и удаления пары (изменение можно сделать как удаление+добавление). В этой тривиальной модели производительность очень высока
Одним и примеров Key-Value базы данных является Amazon DynamoDB
Document
В Document базы данных похожи на Key-Value, но в них Value - это структура, в которой тоже могут быть ключ-значения - получается иерархия
Document-решения могут соблюдать Consistency
Например, Document база данных MongoDB может быть или CA, или AP
Column Based (или же Wide-column store):
В колоночных базах данных формат столбца для двух строк в таблице может быть разным. Такой формат может быть полезен для создания описанного раньше маркетплейса, где товары могут иметь разные атрибуты
Также можно заметить, что колоночные базы являются двухмерными Key-Value хранилищами. Также они соблюдают CA
Графовые СУБД
Обычно сущности доменной области и атрибуты можно представить в виде графа. В графовых базах данных мы можем наделять связи какими-то свойствами. А также в них мы можем сделать комплементарный граф, где ребра -> узлы, а узлы -> ребра
Таким образом, мы можем сделать запросы по типу “сколько есть связей такого типа”
Пример: язык GraphQL используется для формирования запросов к графовым базам данных
В конечном итоге можем заметить, что все NoSQL-решения похожи на Key-Value модель. SQL требует строгой структуры, тогда как Key-Value не формализована
На следующей лекции будем разбирать базы знаний, чем отличаются знания от данных