Распределённая обработка информации и NoSQL СУБД

Обзор парадигм NoSQL СУБД

Луцив Дмитрий Вадимович

ЗАО «Ланит-Терком», СПбГУ

Графовые СУБД

Основы

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

  • Узлы

    • Значения

  • Дуги

    • Значения (необязательно)

Типизация обычно динамическая

Языки

На примере Neo4j

  • Описания базы знаний

  • Описания служебных структур, например, индексов

  • Запросов

    • Часто наглядно изображают графы

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

    • Могут использовать алгоритмы из теории графов

Особенности

  • Структура произвольной глубины

  • Связи хранят больше информации, нежели атрибуты

Области

  • Социальные графы

  • Лингвистические базы данных

  • Маршрутные базы данных

Слайды Ильи Малиновского

Здесь

Пример с Хоббитом

Дедуктивные СУБД

Prolog

База фактов

родитель('Жучка','Шарик').

родитель('Жучка','Бобик').

родитель('Барбос','Шарик').

родитель('Барбос','Бобик').

родитель('Мушка','Тишка').

родитель('Барбос','Тишка').

База правил

родной_сиб(X, Y) :-

    родитель(A, X), родитель(B, X),

    A \== B,

    !,

    родитель(A, Y), родитель(B, Y),

    X \== Y.

Попробуйте с отсечением и без

Datalog

Базы фактов и правил

Так же, но без

  • отсечения

  • сложных термов вида p(a) в значениях переменных

Отсутсвие отсечения

Делает язык полностью декларативным, облегчает оптимизацию и генерацию плана выполнения запроса

Примеры реализации

Prolog+CG

Пример:

    [Man : x]<-agnt-[Begin]-srce->[Proposition = 

        [Person]<-pat-[Look]-dest->[Person : x] ]

Напоминает что-то? =)

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

Berkley DB

  • 1980-е

  • встраиваемая

    • но многопоточная/многопроцессная

Примеры использующих систем

  • Subversion

  • Bitcoin

  • Postfix

  • MySQL (в качестве одной из альтарнатив)

Примет Berkley DB (Питон)

    data = mydb.get(key)

    if data:

        doSomething(data)

или

    rec = cursor.first()

    while rec:

        print(rec)

        rec = cursor.next()

Project Voldemort

Факты

  • 2009, LinkedIn

  • AP в терминах CAP

Свойства

  • Автоматическая репликация

  • Автоматическое разделение

  • Механизмы для сериализации сложных ключей и значений (но не в «ядре», плагины)

  • Механизмы для использования разных сисиетм хранения

  • Версионирование

  • Оптимизирована для SSD

Примеры использующих систем

Пример Voldemort (Java)

String bootstrapUrl = "tcp://localhost:6666";

StoreClientFactory factory = new SocketStoreClientFactory(

    new ClientConfig().setBootstrapUrls(bootstrapUrl)

);

StoreClient<String, String> client =

    factory.getStoreClient("my_store_name");

// do some random pointless operations

Versioned<String> value = client.get("some_key");

value.setObject("some_value");

client.put("some_key", value);

X M L

XML Everywhere

Зачем?

  • Everywhere =)

    • Очень корпоративно™

    • API, стандартные форматы передачи данных

    • Популярен для метаданных

      • Semantic web в том числе

  • Хорош для разреженных данных, древовидных

  • Сравнительно человекочитаем

XML-Enabled (реляционные)

Варианты

  1. XML хранится при помощи CLOB (Character Large Object)

  2. XML хранится по таблицам в соответствии с схемой

  3. Для XML заводится специальный домен в соответствии со стандартом ISO 9075-14

Пример — поддержка XML IBM DB2

  • Конечно же поддерживается КОБОЛом =)

  • Позволяет создавать индексы

  • Знает XML-схему

  • Запросы к XML d SQL

    select

      id, vol, xmlquery('$j/name', passing journal as "j") as name

    from

      journals

    where 

      xmlexists('$j[licence="CreativeCommons"]', passing journal as "j")

Урождённые XML

Кто они?

  • NoSQL

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

    • Только документы большие, и иерархические ссылки эффективные

Языки

  • XPath, примеры
    bookstore//book/excerpt//emph

    (book/author)[last()]

    book[/bookstore/@specialty=@style]
  • XQuery, пример
    for $x in doc("books.xml")/bookstore/book

    where $x/price>30

    order by $x/title

    return $x/title
  • XUpdate (менее популярен)

Sedna

Документо-ориентированные JSON-СУБД

Основы

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

  • Объекты JSON

  • Опционально — индексы по полям

Хранение данных

Хороший тон — поддерживать шардинг

Аналитические возможности

Хороший тон — поддерживать Map-Reduce (о нём позже)

Шардинг

CouchDB

  • Схемы нет

  • Есть индексы

  • Написана на Erlang

  • Поддерживает репликацию

  • Поддерживает шардинг

    • Строится (заранее, дальше не расширяется) специальный индекс по диапазонам значений поля

    • Классы этого индекса разбивают данный по локальным хранилищам, которые вручную можно переносить на реплики

CouchDB

  • Высокая производительность

  • Развитый язык (на самом деле не язык) запросов

    • На самом деле его вообще нет, а есть View и JavaScript или Erlang

      • И Map-Reduce с описанием на JavaScript или Erlang

CouchDB: пример запроса (view)

function find_users_whose_last_names_start_with(db, query) {

    var matches;

    matches = db.view('users/last_names',

                      { startkey: query,

                        endkey:   query + "\u9999" });

    return matches.rows.map(dot('value'));

}

MongoDB

  • Схемы нет

  • Есть индексы

  • Есть запросы по значениям [вложенных] полей

  • Написана на С++

  • Хранит данные в формате BSON в memory-mapped-файле

    • Закладывается на оптимизацию виртуальной памяти ОС

    • $\implies$ на 32-битных машинах базы $\le$ 2 ГиБ

  • Поддерживает репликацию (довольно много вариантов настройки кластера)

  • Поддерживает шардинг

MongoDB: основные свойства

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

x2 = db.contact.aggregate([

     { $match: { "hiredate": {"$lt": new ISODate("20130601") }}},

     { $unwind: "$phones"},

     { $group: { "_id": "$phones.type",

                 "n": {$sum: 1},

                 "who": {$push: "$name"},

               }},

     { $match: { "n": {"$gt": 1}} },

     { $sort: { "n": -1, "_id": 1} }

     ]);

x2.forEach(function(r) { printjson(r); });

Колоночно-ориентированные СУБД

История

TAXIR, 1969 — биологическая, встраиваемая (вообще в 1969 встраиваемые от не встраиваемых тяжело было отделить)

Преимущества

  • Сжатие

    • Сортировка помогает

  • Быстрый поиск

  • Быстрая аналитика

Примеры

Обе реляционные

Спасибо