1 of 46

​

Технологии и разработка СУБД

Введение в распределенные системы

Анастасия Лубенникова

Александр Алексеев

2 of 46

В этой лекции

  • Движения NoSQL и NewSQL
  • Распределенные транзакции
  • Векторные часы
  • CRDT
  • Gossip
  • И всякое такое
  • Также см лекцию про репликацию и фейловер

3 of 46

Материала много

4 of 46

Движение NoSQL

Johan Oskarsson, then a developer at Last.fm, reintroduced the term NoSQL in early 2009 when he organized an event to discuss "open source distributed, non relational databases".

​

© https://en.wikipedia.org/wiki/NoSQL

5 of 46

В чем идея NoSQL баз данных

  • Распределенные;
  • Отказоустойчивые;
  • Зачастую - жертвуя консистентностью или переопределяя ее значение;
  • Упрощение схемы или полное ее отсутствие;

6 of 46

PACELC (a.k.a CAP-теорема)

To me, CAP should really be PACELC --- if there is a partition (P) how does the system tradeoff between availability and consistency (A and C); else (E) when the system is running as normal in the absence of partitions, how does the system tradeoff between latency (L) and consistency (C)?

​

​

http://dbmsmusings.blogspot.ru/2010/04/problems-with-cap-and-yahoos-little.html

7 of 46

CAP: неправильное объяснение

8 of 46

CRDT & Eventual Consistency

Сonflict-free replicated data type (CRDT) is a data structure which can be replicated across multiple computers in a network, where the replicas can be updated independently and concurrently without coordination between the replicas, and where it is always mathematically possible to resolve inconsistencies which might result.

​

​

https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type

9 of 46

Is it better to be alive and wrong or right and dead?

— Jay Kreps, A Few Notes on Kafka and Jepsen (2013)

​

10 of 46

Векторные часы

11 of 46

Gossip Protocol

12 of 46

Jepsen

https://aphyr.com/tags/Jepsen

13 of 46

Пара слов о современном железе: RAM

  • В один физический сервер влезает до 3 TB оперативы;
  • AWS инстансы x1.32xlarge (128 vCPU, 1952 GB RAM, 2 x 1920 GB SSD) стоят 9603$ в месяц [1];
  • Также AWS анонсировал новые инстансы с 4-16 TB RAM [2][3].

​

[1]: https://aws.amazon.com/ec2/pricing/on-demand/

[2]: https://aws.amazon.com/ec2/instance-types/x1e/

[3]: https://www.theregister.co.uk/2017/05/16/aws_ram_cram/

​

14 of 46

Пара слов о современном железе: жесткие диски

  • Сегодня можно купить 1 TB SSD за ~300$ [1];
  • В один физический сервер можно запихнуть до 900 TB данных;
  • В следующем году - до 1.5 PB.

​

​

​

[1]: Samsung MZ-75E1T0BW, https://market.yandex.ru/product/11929060

​

15 of 46

Виды NoSQL баз данных

  • Key-value (Memcached, Redis, Riak, …)
  • Документо-ориентированные (MongoDB, Cochbase, CouchDB, RethinkDB)
  • Колоночные (ClickHouse)
  • Графовые (Neo4j)
  • Для полнотекстового поиска (ElasticSearch, Solr, Sphinx)
  • Гибридные (Cassandra, Tarantool)
  • Сюда же: месседж брокеры / очереди сообщений (RabbitMQ, Kafka)

16 of 46

Чуть подробнее: Memcached

  • Key-Value
  • Язык программирования: C
  • Автор: Брэд Фитцпатрик
  • Данные хранятся только в памяти
  • Длина ключа до 250 байт, значения - до 1 Мб
  • Fun fact! Ключ можно “расширить” с помощью хэш-функций, значения можно нарезать на части
  • Данные вытесняются по алгоритму LRU
  • Ввод-вывод осуществляется при помощи libevent
  • Поддерживается TCP и UDP
  • Есть текстовый и бинарный протокол

17 of 46

Чуть подробнее: Redis

  • Key-Value
  • Язык программирования: C
  • Автор: Salvatore Sanfilippo (a.k.a. antirez)
  • Данные хранятся в памяти + опционально снапшоты и WAL
  • Есть репликация
  • Есть поддержка массивов, множеств, словарей, bitmaps, можно указать TTL, также есть механизм publish / subscribe
  • Сервер однопоточный
  • Есть поддержка транзакций и пакетного выполнения команд
  • См также Redis Cluster

​

18 of 46

Чуть подробнее: Riak

  • Key-Value
  • Язык программирования: Erlang (в основном)
  • Основан на Dynamo-пейпере [1]
  • Отсутствует единая точка отказа
  • Все обмазано CRDT, векторными часами, gossip’ом, read-repair’ами и антиэнтропией
  • Есть два протокола на выбор: REST API и Protobuf
  • Есть несколько бэкендов: Bitcask, LevelDB, Memory
  • Есть репликация между ДЦ a.k.a. XDC (была платной, теперь открыта)

[1]: http://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf

​

19 of 46

Protobuf (1 / 2)

message Person {

required string user_name = 1;

optional int64 favorite_number = 2;

repeated string interests = 3;

}

​

20 of 46

Protobuf (1 / 2)

message Person {

required string user_name = 1;

optional int64 favorite_number = 2;

repeated string interests = 3;

}

​

Fun fact! В Protobuf 3 все

поля всегда optional.

21 of 46

Protobuf (2 / 2)

22 of 46

Protobuf (2 / 2)

Fun fact! Поле можно сделать�repeated, не сломав обратную�совместимость

23 of 46

See Also

  • Thrift
  • Avro
  • MessagePack
  • Cap’n Proto
  • ???

24 of 46

Riak: ring & vnodes

25 of 46

Riak: Merkle Tree (a.k.a. Hash Tree)

26 of 46

Чуть подробнее: MongoDB

  • Документо-ориентированная СУБД
  • Языки программирования: C++ и JavaScript
  • Документы имеют JSON-подобную структуру
  • Атомарность обеспечивается на уровне одного документа
  • Buffer manager сделан на основе mmap
  • Есть поддержка репликасетов с автофейловером
  • Шардинг из коробки по диапазону, используется специальный shard key
  • Есть сжатие, вторичные индексы и другие навороты
  • В свое время прославилась склонностью терять данные и не проходить Japsen (но вроде сейчас с этим стало получше)

27 of 46

MongoDB: примеры запросов

> db.urls.insert({ code: 123, url: "https://google.com/" });

> db.urls.find();

> db.urls.ensureIndex({ code: 1 }, { unique: true });

> db.urls.getIndexes();

> db.urls.dropIndex({ code: 1 });

> db.urls.update({ code: 123 }, { url: "http://example.ru/" });

> db.urls.remove({ code: 123 });

​

28 of 46

Чуть подробнее: Couchbase

  • Документо-ориентированная СУБД (на самом деле, ближе к Key-Value)
  • Языки программирования: Erlang и C++
  • Данные хранятся в vBuckets, по умолчанию их число равно 1024
  • Каждый узел в кластере является мастером и репликой неких vBucket’ов
  • Номер vBucket’а документа определяется по хэшу от ключа
  • Горячие данные кэшируются в памяти по принципу LRU
  • Есть поддержка Memcached-бакетов, хранящихся только в памяти
  • Есть репликация между ДЦ
  • Есть очень красивая веб-админка!
  • См также N1QL, Couchbase Lite и другие навороты

​

29 of 46

Чуть подробнее: ClickHouse

  • Честная колоночная СУБД
  • Язык программирования: C++
  • Разрабатывается в Яндексе
  • Поддерживает некий диалект SQL
  • На ACID забили
  • Есть сжатие колонок
  • Есть распараллеливание и векторизация запросов
  • Репликация данных зависит от ZooKeeper [1]

[1]: https://github.com/yandex/ClickHouse/issues/479

30 of 46

Чуть подробнее: Cassandra

  • “Колоночно-ориентированная” СУБД
  • Язык программирования: Java
  • Создана в 2008-м году в Facebook
  • Как и Riak, основана на Dynamo-пейпере
  • Данные хранятся в виде троек (column_name, value, timestamp)
  • Last Write Wins по умолчанию
  • Поддерживает упрощенный SQL (Cassandra Query Language)
  • Есть эффективные вторичные индексы, primary key разбивается на partition key (для шардинга) и clustering key (для сортировки внутри шарда).
  • Данные хранятся в LSM-tree
  • См также ScyllaDB, Seastar, Pedis

31 of 46

Seastar (1 / 2)

32 of 46

Seastar (2 / 2)

Пока что не занесли нормальной поддержки CMake :(

​

33 of 46

Чуть подробнее: ElasticSearch

  • Приложение для полнотекстового поиска
  • Язык программирования: Java
  • Основан на движке Apache Lucene
  • Имеет довольно запутанный HTTP/JSON API
  • Не очень хорошо переживает нетсплиты и падения узлов
  • Часто используется в сочетании с Logstash и Kibana, так называемый ELK-стэк

34 of 46

Kibana

35 of 46

Чуть подробнее: RabbitMQ

  • Брокер сообщений
  • Язык программирования: Erlang
  • Реализует протокол AMQP
  • Умеет хранить сообщения в памяти и персистентно (бэкенд - Mnesia)
  • Как показывает опыт, в последнем случае не очень хорошо ведет себя при нетсплитах
  • Области применения:
    • Раздача задач воркерам - например, рассылка SMS или Email, тяжелые вычисления и тд;
    • Подписка на события в системе - например, входящие сообщения для заданного пользователя;
    • Remote Procedure Call;

36 of 46

RabbitMQ: иллюстрация

37 of 46

Транзакции в мире NoSQL

Можно сделать разными способами.

  • Вести лог идемпотентных операций;
  • Использовать Percolator-like подход [1];

​

​

​

[1]: http://rystsov.info/2012/09/01/cas.html

38 of 46

Чем плох 2PC?

39 of 46

NewSQL базы данных

Как традиционные РСУБД, только распределенные и шардированные.

40 of 46

Примеры NewSQL баз данных

  • CockroachDB
  • TiDB
  • Amazon Aurora
  • Google Spanner

41 of 46

Чуть подробнее: CochroachDB

  • ACID с прозрачным фейловером, шардингом и распределенными транзакциями;
  • Анонсирован в 2014, написан на Go, разрабатывается экс-гугловцами;
  • Бесплатное и открытое ПО;
  • Совместимо с PostgreSQL на уровне протокола;
  • Проходит Jepsen [*];
  • Основывается на пейпере о Spanner [*];

​

42 of 46

Чуть подробнее: Amazon Aurora

  • ACID с прозрачным фейловером и всяким таким;
  • Анонсирована в 2014;
  • Существует только в AWS;
  • Совместима с MySQL и PostgreSQL [1] на уровне протокола;
  • Есть пейпер [2];

​

[1]: с ноября 2016 https://news.ycombinator.com/item?id=13072861

[2]: http://www.allthingsdistributed.com/files/p1041-verbitski.pdf

43 of 46

Дополнительные материалы

​

44 of 46

Рекомендуемые книги

45 of 46

Рекомендуемые блоги

46 of 46

Вопросы и ответы.