NoSQL Movement

Термин

• Впервые встречается в 1998 применительно к реляционной СУБД без поддержки SQL

• Снова появляется только в 2009 году (современное применение весьма новое)

  • Eric Evans (Rackspace): The whole point of seeking alternatives is that you need to solve a problem that relational databases are a bad fit for

Мотивы I

• Снижение излишней сложности

  РСУБД очень функциональны и строги (напр., ACID). Для конкретных приложений в этом часто нет необходимости.

• Производительность

  Часто выше, чем у РСУБД

• Масштабируемость и неприхотливость

  У РСУБД тяжело с:

  1. Масштабированием данных

  2. Производительностью центрального сервера (мощного и дорогого)

  3. Негибкой схемой

• Исключение дорогого ORM

  Особенно у документо-ориентированных СУБД — модель данных в базе очень блиска к модели данных бизнес-логики

• Упрощение развёртывания кластеров

  У реляцонных действительно сложно

Мотивы II

• Отказ от излишней надёжности в пользу производительности

  Shalom: Different scenarios where applications would be willing to compromise reliability for better performance

• Отказ от ошибочного подхода One size fits it all

  Объём данных часто непредсказуем, и, в основном, растёт. А вместе с ним и требования к производительности.

• Нецелесообразность децентрализации данных с изначально централизованной моделью: миф или реальность?

  • Трудно, но целесообразность определяется необходимостью

  • Лучше изначально модель хранения данных проектировать с прицелом на распределённость в будущем

  • Луцив Д.В.: И не только модель хранения данных, но и код. Хотя бы на многопоточность.

• Языки программирования и библиотеки

  • Программы $\rightarrow$ SQL — (N)Hibernate, Entity Framework, RoR Active Record, ...

  • NoSQL $\rightarrow$ Программы — CouchDB, MongoDB, ...

Мотивы III

• Актуальное для облачных платформ

  • Настолько хорошая масштабируемость, насколько возможно

    • Хорошо бы вообще автоматическая

  • Желательно небольшой оверхед при администрировании

  В облаках хорошо работают:

  • Data Warehouse, заточенные под Map-Reduce

  • Хранилища ключ-значение

  • М.б. и что-то посложнее, но не настолько сложное, как RDBMS

• Кеширование и ввод/вывод вообще

  • РСУБД (особенно хорошо нормализованные) выполняют сложные операции при чтении $\implies$ для нагруженных сайтов не очень,

    а у NoSQL данные представлены уже в агрегированном виде

  • Приложения ждут ввода/вывода, это типично для протоколов и драйверов РСУБД

Мотивы IV

James Gosling: говорит нам:

Essentially everyone, when they first build a distributed application, makes the following eight assumptions. All prove to be false in the long run and all cause big trouble and painful learning experiences.

1. The network is reliable

2. Latency is zero

3. Bandwidth is infinite

4. The network is secure

5. Topology doesn’t change

6. There is one administrator

7. Transport cost is zero

8. The network is homogeneous

Michael Stonebraker

Тоже на самом деле очень много что говорит, подробнее об этом — Christof Strauch в NoSQL Databases.

А NoSQL ли? И что это означает?

А много ли мы сказали про SQL?

Strozzi: Current NoSQL movement departs from the relational model altogether; it should therefore have been called more appropriately 'NoREL', referring to 'No Relational'

Not only SQL — ничего конкретного, скорее вектор развития IT

ACID vs BASE

ACID vs BASE I

ACID

• Atomicity — Атомарность

• Consistency — Согласованность

• Isolation — Изолированность

• Durability — Долговечность

BASE

Согласованность в конечном счёте

• Basically Available

• Soft state

• Eventual consistency

Основной принцип: в отсутствии изменений данных, через какой-то промежуток времени после последнего обновления («в конечном счёте») все запросы будут возвращать последнее обновлённое значение

Пример — DNS.

Сильная согласованность в конечном счёте

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

ACID vs BASE II

Консенсус

Paxos

Протокол достижения консенсуса в распределённой системе. Лесли Лэмпорт, 1989.

Популярно (вероятно просто хороший вдумчивый и слегка дополненный перевод Википедии) здесь.

Paxos: Роли

• Client – клиент, может отправить запрос и получить на него ответ

• Proposer – компонент, отвечает за организацию процесса голосования

• Acceptor – компонент, имеет право голоса за принятие или отклонение конкретного предложения от Proposer

• Learner – компонент, запоминает принятое решение

Paxos: Базовый алгориѳм

• Prepare («предложение») Proposer генерирует «предложение» с порядковым номером $N$ и отправляет его всем acceptor. Для каждого из последующих «предложений» номер $N$ должен быть больше выбранного ранее данным proposer.

• Promise («обещание») Каждый acceptor получает «предложение» с порядковым номером $N$ и значением $V$. Если номер «предложения» больше чем все принятые ранее данным acceptor, он обязан ответить на это сообщение «обещанием» не принимать более «предложений» с порядковым номером меньше $N$. Если данный acceptor уже принимал какое-либо «предложение», он должен вернуть номер $N_i$ этого «предложения» и принятое значение $V_i$, в противном случае он возвращает пустое значение.

• Accept! («принять») Если proposer получил «обещания» от кворума acceptor, он считает запрос готовым к дальнейшей обработке. В случае, если с «обещаниями» от acceptor пришли также значения $N_i$ и $V_i$, proposer выбирает $V$ равное значению $V_i$ «обещания» с максимальным $N_i$. Затем proposer отправляет запрос «принять» всем acceptor, который содержит значения $N$ и $V$.

• Accepted («принято») Когда acceptor получает сообщение «принять» со значениями $N$ и $V$, он принимает его только в том случае, если ранее он не «обещал» принимать предложения с номерами строго больше $N$. В противном случае он принимает значение и отвечает сообщением «принято» всем learner.

• Learner получает сообщение «принято» со значением $V$ и запоминает его.

Raft

Diego Ongaro, John Ousterhout: Raft is a consensus algorithm that is designed to be easy to understand Stanford University, 2013

• Статья

• Подробно, популярно и с мультиком

• Популярно и интерактивно про голосование

• По-русски здесь

Виды популярных СУБД

Кратко о популярных типах СУБД

• Реляционные

  Типично хранение по строкам или по строкам из коротких отрезков колонок

• Ключ-значение

  Хеш без знаний о структуре значений

• Документо-ориентированные

  Структурированные объекты с индексами по полям

• Колоночно-ориентированные

  Могут быть и реляционными, и SQL; хранят данные по колонкам $\implies$ быстрее поиск и анализ на клиенте, эффективнее сжатие, но тяжелее со сложными запросами

CAP

Теорема CAP

Эвристическое утверждение. Eric Brewer, Berkeley, 1998–1999

В любой реализации распределённых вычислений возможно обеспечить не более двух из трёх следующих свойств:

• Согласованность данных (consistency) — во всех вычислительных узлах в один момент времени данные не противоречат друг другу;

• Доступность (availability) — любой запрос к распределённой системе завершается корректным откликом;

• Устойчивость к разделению (partition tolerance) — расщепление распределённой системы на несколько изолированных секций не приводит к некорректности отклика от каждой из секций

Доказательство

Доказательство

• Seth Gilbert, Nancy Lynch. Brewer's Conjecture and the Feasibility of Consistent Available Partition-Tolerant Web Services. In ACM SIGACT News, 2002

Пояснение

А что с нашими любимыми СУБД?

PACELC

PACELC

Daniel J. Abadi, Yale University, 2010 (блог), 2012 (статья):

In case of network partitioning (P) in a distributed computer system, one has to choose between availability (A) and consistency (C) (as per the CAP theorem), but else (E), even when the system is running normally in the absence of partitions, one has to choose between latency (L) and consistency (C)

• В случае с разделённой вычислительной системой можно выбирать между доступностью и согласованностью

• В случае со связной и доступной — между допустимыми задержками и согласованностью

Чем плоха CAP

Менее уместна, чем теорема MIT, также предлагающая выбрать 2/3:

• Диплом

• Друзья

• Сон

Явно намекает на приоритет доступности над согласованностью

• Статья

• Слайды

А что с нашими любимыми СУБД?