Глобалы — мечи-кладенцы для хранения данных. Деревья. Часть 1

a4789de7ca7f417cacfb660843e09455.jpg Настоящие мечи-кладенцы баз данных — глобалы — давно известны, но до сих пор немногие умеют эффективно ими пользоваться или вовсе не владеют этим супероружием.

Если использовать глобалы в решении тех задач, в которых они действительно хороши, то можно добиться выдающихся результатов. Либо в производительности, либо в упрощении решения задачи (1, 2).

Глобалы — это специальный способ хранения и обработки данных, совершенно другой, чем таблицы в SQL. Они появились в 1966 году в языке M (UMPS) (эволюционное развитие — Caché ObjectScript, далее COS) в медицинских БД и до сих пор там активно используются, а также проникли в некоторые другие области, где требуется надёжность и высокая производительность: финансы, трейдинг и т.д.

Глобалы в современных СУБД поддерживают транзакции, журналирование, репликацию, партиционирование. Т.е. на них можно строить современные, надёжные, распределённые и быстрые системы.

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

Глобалы как способ хранения данных можно использовать во многих современных языках программирования, как высокоуровневых, так и низкоуровневых. Поэтому в этой статье я сфокусируюсь именно на глобалах, а не на языке, из которого они когда-то вышли.

2. Как работают глобалы


Давайте вначале разберёмся, как работают глобалы, и в чём их сильные стороны. На глобалы можно смотреть с разных точек зрения. В этой части статьи мы будем смотреть на них как на деревья. Или как на иерархические хранилища данных.

Упрощённого говоря, глобал — это персистентный массив. Массив, который автоматически сохраняется на диск.
Трудно представить что-то более простое для хранения данных. В коде (на языках COS/M) от обычного ассоциативного массива он отличается только символом ^ перед именем.

Для сохранения данных в глобале не нужно изучать язык запросов SQL, команды для работы с ними очень просты. Их можно выучить за час.

Начнём с самого простого примера. Одноуровневое дерево с 2-мя ветвями. Примеры написаны на COS.

d0bf27a8ca4742329c647f999c8c8279.png

Set ^a("+7926X") = "John Sidorov"
Set ^a("+7916Y") = "Sergey Smith"


При вставке информации в глобал (комaнда Set) автоматически происходят 3 вещи:

  1. Сохранение данных на диск.
  2. Индексация. То что в скобках выступает ключом (в англоязычной литературе — «subscript»), а справа от равно — значением («node value»).
  3. Сортировка. Данные сортируются по ключу. В дальнейшем при обходе массива первым элементом станет «John Sidorov», а вторым «Sergey Smith». При получении списка пользователей из глобала база не тратит времени на сортировку. Причём можно запросить вывод отсортированного списка, начиная с любого ключа, даже несуществующего (вывод начнётся с первого реального ключа, который идёт за несуществующим).


Все эти операции происходят невероятно быстро. На домашнем компьютере я получал значения до 750 000 вставок/сек в одном процессе. На многоядерных процессорах значения могут достигать десятков миллионов вставок/сек.

Конечно, сама по себе скорость вставки мало о чём говорит. Можно, например, очень быстро записывать информацию в текстовые файлы — так по слухам работает процессинг Visa. Но в случае глобалов мы получаем на выходе структуризованное проиндексированное хранилище, с которым можно в дальнейшем просто и быстро работать.

62920bf366bf4c91b80891286c7adcb1.png

  • Самая сильная сторона глобалов — это скорость вставки новых узлов.
  • Данные в глобале всегда проиндексированы. Их обход как на одном уровне, так и вглубь дерева, всегда быстр.


Добавим в глобал ещё несколько ветвей второго и третьего уровня.

Set ^a("+7926X", "city") = "Moscow"
Set ^a("+7926X", "city", "street") = "Req Square"
Set ^a("+7926X", "age") = 25
Set ^a("+7916Y", "city") = "London"
Set ^a("+7916Y", "city", "street") = "Baker Street"
Set ^a("+7916Y", "age") = 36


144bb26562ca427da6272422700085e8.png

Очевидно, что на основе глобалов можно строить многоуровневые деревья. Причём доступ к любому узлу практически мгновенный из-за автоиндексирования при вставке. И на любом уровне дерева все ветви отсортированы по ключу.

Как видно информацию можно хранить как в ключе, так и значении. Общая длина ключа (сумма длин всех индексов) может достигать 511 байт, а значения 3.6 МБ для Caché. Число уровней в дереве (число измерений) — 31.

Ещё интересный момент. Можно построить дерево, не задавая значений узлов верхний уровней.

002795a5f35a4c6a8a777f76eab971bc.png

Set ^b("a", "b", "c", "d") = 1
Set ^b("a", "b", "c", "e") = 2
Set ^b("a", "b", "f", "g") = 3


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

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

1fd0d7eec1b048b298e1fa29dc3dab2c.png

Как мы видим у садовых деревьев листья и плоды находятся только на концах ветвей.
Файловые системы — информация хранится только на концах ветвей, которые являются полными именами файлов.

А вот структура данных глобала.

d769ffadbe4247e9b311be105f6a7b50.pngОтличия:

  1. Внутренние узлы: информация в глобале может храниться в каждом узле, а не только на концах ветвей.
  2. Внешние узлы: у глобала обязательно должны быть определены значения на концах ветвей, у деревьев ФС и садовых — нет.


В части внутренних узлов, можно сказать, что структура глобала является надмножеством структуры деревьев имён в файловых системах и садовых деревьев. Т.е. более гибкой.

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

Чтобы лучше понять работу глобалов представим, что было бы, если создатели файловых систем использовали для хранения информации подход аналогичный глобалам?

  1. При удалении единственного файла в директории автоматически бы удалялась директория, а также все вышележащие директории содержащие только одну только что удалённую директорию.
  2. Надобность в директориях бы отпала. Просто были бы файлы с подфайлами и файлы без подфайлов. Если сравнить с обычным деревом, то каждая ветвь стала бы плодом.

    d277388b4663496d920e96d2476c4263.png

  3. Такие вещи как файлы README.txt, возможно, отпали бы. Всё что нужно было сказать о содержимом директории можно было записать в сам файл директории. В пространстве путей имя файла неотличимо от имени директории, поэтому можно было обойтись одними файлами.
  4. Скорость удаления директорий с вложенными поддиректориям и файлами резко увеличилась бы. Много раз на хабре проскакивали статьи о том, как долго и трудно удалять миллионы мелких файлов (1, 2). Однако, если сделать псевдофайловую систему на глобале, то это будет занимать секунды или их доли. Когда я тестировал удаление поддеревьев на домашнем компьютере, то за 1 секунду удалялось более 200 000 ветвей на HDD (не SSD). Причём речь идёт об удалении части дерева, а не просто всего файла с глобалами.


62920bf366bf4c91b80891286c7adcb1.png
Удаление поддеревьев — ещё одна сильная сторона глобалов. Для этого не нужна рекурсия. Это происходит невероятно быстро.

В нашем дереве это можно было бы сделать командой Kill.

Kill ^a("+7926X")


30f1784729ef4329bdfd4d0411d09f68.png

Для лучшего понимания того, какие действия нам доступны над глобалами, приведу краткую таблицу.

Основные команды и функции по работе с глобалами в COS
Set Установка ветвей до узла (если ещё неопределены) и значения узла
Merge Копирование поддерева
Kill Удаление поддерева
ZKill Удаление значения конкретного узла. Поддерево выходящее из узла не трогается
$Query Полный обход дерева с заходом вглубь
$Order Обход веток конкретного узла
$Data Проверка определён ли узел

Спасибо за внимание, готовы ответить на ваши вопросы.

Продолжение на следующей неделе. Вы узнаете какие типы данных можно отобразить на глобалах и на каких задачах они дают максимальный выигрыш.

© Habrahabr.ru