Нереляционные решения БД.

Причины возникновения

Главной проблемой реляционных БД достаточно давно считается так называемое “несовпадение бремени” (impedance mismatch) между реляционной и объектно-ориентированной моделями данных.

При рассуждении о данных с точки зрения ООП (объекно-ориентированного подхода), вы представляете себе схему данных в виде дерева, или документов, или чего-то подобного.

При этом, реляционная модель оперирует отношениями (или “таблицами”).

NoSQL так же часто называются документо-ориентированными БД, и отчасти решают эту проблему.

Другой проблемой является производительность в условиях современного мира.

В современном обществе, количество информации растет экспоненциально, и банальные требования к хранению этой информации становится трудно выполнять в рамках одной или нескольких машин. К тому же, с очень большими объемами данных сложно работать: сложно добавлять новые, сложно читать старые.

Сейчас существуют такие вещи, как социальные сети, коллективные блоги, последние годы стало популярно говорить про “семантический веб”. Все эти вещи оперируют огромными объемами взаимосвязанных данных, которые постоянно читаются и обновляются.

К сожалению, реляционные СУБД значительно теряют в производительности с ростом количества данных. Большинство современных корпоративных БД (учет товаров, сотрудников, клиентов, etc) и БД веб-приложений укладываются в диапазон объема данных, при которых производительность РСУБД остается “хорошей”. Однако, скажем, объем данных того же Facebook уже находится за рамками применимости РСУБД.

Для решения проблемы хранения и обработки больших объемов данных, используется подход кластеризации: данные разносятся по многим машинам, и доступ к ним осуществляется при помощи некого балансировщика нагрузки.

Однако, при использовании РСУБД, добавление еще одного узла в кластер не сильно улучшает производительность. Соответственно, на рынке возник некий вакуум, требующий СУБД с высокой, что называется, горизонтальной масштабируемостью.

Нереляционные (NoSQL) решения так же стремятся решить и эту проблему.

Основные особенности NoSQL

Википедия определяет NoSQL-БД как “нереляционные хранилища данных, не нуждающиеся в фиксированной схеме и которые обычно избегают операций соединения (join)”.

Разных нереляционных решений существует великое множество, и объединяет их в значительной мере то, что они не используют реляционную модель.

Другой характерной чертой является высокая горизонтальная масштабируемость.

Третий фактор – отсутствие жестко заданных схем данных.

В качестве примеров NoSQL решений можно привести:

  • Redis
  • mongoDB
  • H-Base
  • Cassandra
  • riak
  • Neo4j
  • CouchDB
  • VoldemortDB
  • и др.

Иными словами, сейчас на рынке великое множество нереляционных СУБД.

Большинство NoSQL БД по схеме данных ориентированы на агрегаты данных, другими словами, на вложенные структуры данных. Эта особенность радикально отличает NoSQL от реляционных БД, в которых модель данных ориентированна, напротив, на нормализованные данные.

Нормализованные данные имеют несколько достоинств по сравнению с агрегатами:

  • Нормализованные данные гарантируют целостность при обновлении
  • Широкий спектр запросов к нормализованным данным относительно эффективен

Агрегированные данные

  • Поскольку не являются нормализованными, целостность при обновлении не гарантируют
  • Возможна оптимизация только под определенный вид запросов. Для оптимизации под другие запросы необходимо перепроектирование всей базы.

С другой стороны, нормализованные данные имеют свои недостатки:

  • Неэффективны в кластеризованной среде
  • Необходимость использования сравнительно неэффективных соединений (join) для получения данных
  • “Несовпадение бремени”

Агрегированные данные же

  • Хорошо подходят для распределенной среды
  • Позволяют хранить данные в том виде, в котором с ними работает приложение

Пример:

Сущности “заказ” (№, дата), “товар” (№, название, цена), “платеж” (№, сумма, дата). Атрибуты указаны в скобках.

В реляционной модели это может выглядеть так:

Заказы
id date
100 2008-04-15
Товары
id name price
10 Ваза цветочная 600
11 Картина “море” 500
Платежи
id orderId sum date
100 100 1000 2008-04-17
101 100 100 2008-04-18
Товары в заказе
orderId productId Number
100 10 1
100 11 1

В то же время, документно-ориентированная БД может представлять это в виде:

// Order
{
  "id": 100,
  "date": "2008-04-15",
  "products": [
    {
      "id": 10,
      "number": 1
    },
    {
      "id": 11,
      "number": 1
    }
  ],
  "payments": [
    {
      "sum": 1000,
      "date": "2008-04-17"
    },
    {
      "sum": 100,
      "date": "2008-04-18"
    }
  ]
}

// Product
{
  "id": 10,
  "name": "Ваза цветочная",
  "price": 600
}

//Product
{
  "id": 11,
  "name": "Картина \"море\"",
  "price": 500
}

Модели данных

С практической точки зрения, существуют разные нереляционные модели данных.

Наиболее распространенные из них это:

Модель ключ-значение

Представляют собой множество бинарных кортежей, причем первый элемент кортежа считается “ключом” и имеет строковой тип данных, а второй считается “значением”, и имеет “какой-то” тип данных (то есть, СУБД не знает, что за данные в значении).

Примеры:

  • Voldemort
  • Redis
  • Riak
Документо-ориентированная модель

Представляют собой множество множеств бинарных кортежей ключ-значение. При этом значение само по себе есть множество множеств кортежей ключ-значение, либо скалярный тип (скажем, строка или число).

Примеры:

  • CouchDB
  • mongoDB
Колоночно-ориентированная модель

Смысл этой модели в том, что данные хранятся в виде множества “колонок”, вместо множества “строк”, как в реляционной модели.

При этом, в качестве ключей для данных в “колонке” используется само значение, которое уже определяет, к какой “строке” относится эта колонка.

Подобная организация позволяет эффективно реализовывать статистические запросы и запросы агрегатов.

Примеры:

  • HBase
  • Cassandra
  • Hypertable
Графовые БД

Данные представляются в виде графа, где узлы и ребра имеют атрибуты.

Примеры:

  • Neo4j
  • AllegroGraph

CAP-теорема

Вся суть NoSQL-решений описывается так называемой CAP-теоремой.

В вольной формулировке, она звучит так:

СУБД должна обеспечивать:

  • Доступность данных (availability): все клиенты могут читать и писать данные в любой момент
  • Целостность данных (consistency): все клиенты всегда “видят” одинаковые данные
  • Устойчивость к разделению (partition tolerance): система работает даже при сбоях физической сети.

СУБД может обеспечивать не более двух из трех вышеперечисленных.

CAP-теорема

Из примеров:

Реляционные БД обеспечивают доступность и целостность (CA).

Cassandra, Voldemort, CouchDB обеспечивают доступность и устойчивость.

Hypertable, HBase, MongoDB, Redis обеспечивают целостность и устойчивость.

MapReduce

Основным инструментом для работы с нереляционными данными является разработанный в Google фреймворк mapReduce или его аналог.

Само понятие mapReduce происходит из функционального программирования, и это попросту композиция отображений и редукции. Сила гугловского фреймворка в том, что он эффективно работает на высокораспределенных системах.

Смысл mapReduce в том, что если есть много относительно простых вычислений, то, пользуясь mapReduce, достаточно определить две функции:

  • map(k1, v1) → [(k2, v2)]
  • reduce(k2, [v2]) → v3

Функция map вызывается один раз для каждого ключа входных данных k1. Функция reduce вызывается один раз для каждого ключа результов map.

Обеспечение целостности в распределенной среде

Если у нас есть один узел с данными, то мы можем в общем-то достаточно уверенно гарантировать целостность. В распределенной среде это не совсем так. Поэтому, большинство NoSQL-СУБД гарантируют целостность “рано или поздно” (eventual consistency), то есть, если данные в системе не изменяются, то рано или поздно они станут согласованными на всех узлах.

EC обеспечивается при помощи так называемых “анти-энтропийных алгоритмов”, которые основаны на моделях распространения сплетен и эпидемиологических моделях.

Смысл алгоритма в том, что каждый узел распределенной сети по таймеру случайным образом выбирает другой узел и обменивается с ним информацией. Для этого может быть три стратегии:

  • push. Узел A отправляет некий хэш своих данных узлу B, узел B запрашивает у A данные, отличающиеся на A и B. Обновляется таким образом только узел B.

  • pull. Узел A отправляет некий хэш своих данных узлу B, а узел B отправляет узлу A данные, которые у него отличаются. Обновляется таким образом только узел A.

  • push-pull. Происходит и то, и другое.

Последний в среднем в 2 раза более эффективен, чем первые два.

Другие стратегии могут выбирать один из узлов кластера в качестве “арбитра”, который будет обеспечивать целостность (опять же, рано или поздно)

Недостатки существующих систем

mongoDB

  • MapReduce однопоточный, имеет блокировки чтения/записи, написан на JavaScript
  • Молодой продукт, бывают баги
  • Есть ограничения на максимальный размер объекта (по умолчанию – 16 МБ)
  • Есть ограничения на размер базы данных на 32-битной архитектуре (2 ГБ).

Redis

  • Все данные (или по крайней мере ключи) содержатся в оперативной памяти.
  • Достаточно медленная запись на диск
  • Сохранения требуют до удвоенного объема оперативной памяти, могут временно заблокировать базу
  • Поиск только по ключам
  • Нет встроенной масштабируемости – возможно только на стороне приложения

Neo4j

  • Нет встроенной масштабируемости
  • Неудобное лицензирование

Cassandra

  • Слабые гарантии целостности
  • Нет индексации
  • Невозможно делать запросы, которые не предусмотрены архитектурой БД
  • Написана на Java, следовательно, возможны задержки при сборе мусора