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

Проблематика

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

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

Закон Мура

Гордон Мур

Химик, специалист по полупроводникам

Закон Му́ра, 1965

  • Количество транзисторов в СБИС за два года удваивается

Пределы

Факты:

  • 22-core Xeon Broadwell-E5 — 2016 — 14 нм — $7,2\cdot10^9$

  • SPARC M7 — 2015 — 20 nm — $10^{10}$

Физико-технологические пределы:

Комментарии

А зачем вообще транзистор? Может ну его?

С сайта Ремонт и настройка компьютера своими силами для девочек (на самом деле из кучи книжек):

Больше транзисторов $\not\Rightarrow$ хорошо само по себе

Масштабируемость

Мы заметили, что процессоры из примера многоядерные? А зачем?

Примеры восхитительных плодов безудержного стремления к распараллеливанию:

Параллелизм

Джин Амдал

Главный архитектор IBM System/360

Закон Амдала

$T(1)$ время вычисления на одном вычислителе, $T(n)$ — на $n$, $E(n) = \frac{T(1)}{T(n)}$

$\alpha$ последовательно, $1 - \alpha$ параллельно

Ускорение при распараллеливании:

$$S(n) \underset{n\rightarrow\infty}{\rightarrow} \frac{1}{\alpha}$$

Почему

$$S(n) = \frac{T(1)}{T(n)} =$$

$$= \frac{T(1)}{\alpha T(1) + (1 - \alpha) \frac{T(1)}{n}} < \frac{1}{\alpha}$$

А.Н. Терехов (не дословно)

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

Распределённость

Зачем

  • Закон Мура

  • Даже если бы не он — память общая, шины общие

  • Если память и шины не общие, значит уже сдались

    • У GPGPU внутренняя память и шины у шейдеров свои, отдельные

Топология

Происхождение термина

Следует

  • Передавать меньше

  • Передавать ближе

  • По возможности, считать и хранить рядом

Топология должна быть достаточной, но не избыточной

Пример: задачи на плоскости

  • Волновые уравнения

  • Уравнения теплопроводности

Пример решения — Транспьютер (Inmos, UK, 1980-е)

Пример: задачи на сфере

  • Метеорология

Пример топологии — додекаэдр или другой вписанный многогранник

Пример: Станция управления лифтом

Вызов или приказ куда: наверх или вниз?

  • Централизованная система — винтовой селектор — масштабируется тяжело, точка отказа, зато элегантно

  • Распредеделённая система — инверсия направления этажным переключателем — можно развесить по шахте, но пыльно и обслуживать тяжело

Базы данных

Форматированные файлы: COBOL

DATA DIVISION.

   FILE SECTION.

   FD STUDENT.

   01 STUDENT-FILE.

      05 STUDENT-ID PIC 9(5).

      05 NAME PIC A(25).



   WORKING-STORAGE SECTION.

   01 WS-STUDENT.

      05 WS-STUDENT-ID PIC 9(5).

      05 WS-NAME PIC A(25).

   01 WS-EOF PIC A(1).

Форматированные файлы: Pascal

Type anketa1=record

   fio: string[45];

   alg: integer;

   phis: integer;

   him: integer;

end;



Var stud:anketa1;

Gr:array[1..30] of anketa1;



ff:file of anketa1;

Пример менее олдскульный, но более трогательный =)

Иерархические БД

Пример — IBM IMS, 1960-е

Форматированные файлы старше компьютеров

Табулятор — 1890 (Hollerith (BTM)) – 1976 (IBM 407)

  • Сортировка (поразрядная, время близко к линейному)

  • Разбиение на классы эквивалентности

  • BTM — уже практически компьютеры, с памятью на магнитном барабане

РБД

  • Очень строгая система типов

  • Очень хорошие алгебра и логика в основе системы типов

РБД: НО

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

    • Многие поддерживают ссылки на ROWID — грязный хак

  • ACID — благословение и проклятие

    • Явная фиксация транзакций

    • Сериализуемость транзакций тяжело проверить в распределённой системе

РБД: Масштабируемость

  • Распределённые индексы — сложно $\implies$ легче таблицу держать на одном узле

  • Распределённые JOIN — медленно $\implies$ легче соединяемые таблицы тоже держать на одном узле

РБД: Доступность

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

РБД: ORM

O-R impedance mismatch, особенно:

  • Structural and integrity differences — логические языки подошли бы лучше, чем объектно-ориентированные

  • Manipulative differences — объектно-ориентированные языки обычно императивные и часто довольно низкоуровневые (в

    плане выразительной силы и встроенного уровня абстракции)

  • Разные свойства транзакций, и, по-хорошему, отсутствие транзакций в языках

Современные попытки

Действительно современные (в активной разработке) и пока довольно робкие,

например, Clustrix.

Любая конкретная методология

Я привык гвозди забивать молотком, поэтому и забор буду красить молотком

Спасибо