глобалы

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

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

На глобалы можно смотреть с разных точек зрения. Мы будем смотреть на них как на деревья. Или как на иерархические хранилища данных.

Упрощённо говоря, глобал — это персистентный массив. Массив, который автоматически сохраняется на диск - трудно представить что-то более примитивное для хранения данных.

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


set ^a("+7926x") = "John Sidorov"
set ^a("+7916y") = "Sergey Smith"

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

  • сохранение данных на диск
  • индексация (то, что в скобках, выступает ключом, а справа — значением)
  • сортировка (по ключу)

    В дальнейшем при обходе массива первым элементом станет «Sergey Smith», а вторым «John Sidorov». При получении списка пользователей из глобала база не тратит времени на сортировку. Причём можно запросить вывод отсортированного списка, начиная с любого ключа, даже несуществующего (вывод начнётся с первого реального ключа, который идёт за несуществующим).


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

    
    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
    

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

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

    В глобалах

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

    Пустые кружки — это узлы, которым не присвоено значение.

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

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

    
    Kill ^a("+7926X")
    

    Варианты структур при использовании глобалов

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

     

    Частный случай 1. Один узел без ветвей

    Глобалы можно использовать не только подобно массиву, но и как обычные переменные. Например как счётчик:

    
    Set ^counter = 0            ;  установка счётчика
    Set id=$Increment(^counter) ;  атомарное инкрементирование
    

    При этом глобал, кроме значения, может ещё иметь и ветви - одно не исключает второго.

    Частный случай 2. Одна вершина и множество ветвей

    Вообще — это классическая key-value база. А если в качестве значения мы будем сохранять кортеж, то получим самую обыкновенную таблицу с первичным ключом.

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

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

    Частный случай 3. Двухуровневое дерево, у каждого узла второго уровня фиксированное число ветвей

    Вы, наверное, догадались: это альтернативная реализация таблиц на глобалах. Сравним эту реализацию с предыдущей.

    Минусы

    Медленнее на вставку, так как нужно устанавливать число узлов равное числу колонок.

    Больше расход дискового пространства. Так как индексы глобала (в понимании как индексы у массивов) с названиями колонок занимают место на диске и дублируются для каждой строки.

    Плюсы

    Быстрее доступ к значениям отдельных колонок, так как не нужно парсить строку. По моим тестам быстрее на 12% на 2-х колонках и более на большем числе колонок.

    Проще менять схему данных

    Нагляднее код

    Вывод: на любителя. Поскольку скорость — одно из самых ключевых преимуществ глобалов, то почти нет смысла использовать эту реализацию, так как она скорее всего будет работать не быстрее таблиц на реляционных базах данных.

    Общий случай. Деревья и упорядоченные деревья

    Любая структура данных, которая может быть представлена в виде дерева, прекрасно ложится на глобалы.

    Объекты с подобъектами

    Это область традиционного применения глобалов. В медицинской сфере огромно число болезней, лекарств, симптомов, методов лечения. Создавать на каждого пациента таблицу с миллионом полей нерационально. Тем более, что 99% полей будут пустыми.

    Представьте SQL БД из таблиц: «пациент» ~ 100 000 полей, «Лекарство» — 100 000 полей, «Терапия» — 100 000 полей, «Осложнения» — 100 000 полей и т.д. и т.п. Либо можно создать БД из многих тысяч таблиц, каждая под определённый тип пациента (а ведь они могут пересекаться!), лечения, лекарства, и ещё тысячи таблиц для связей между этими таблицами.

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

    На глобалах удобно делать БД с данными, когда важно накопить и систематизировать максимум разнообразной информации об обьекте. Это востребовано в медицине, банковской сфере, маркетинге, архивном деле. Изменение структуры данных, если мы используем глобалы, нам ничего не стоят. В любой момент мы можем добавить любые нужные нам новые свойства к любому объекту, на любом уровне иерархии.

    Изменения связанные с переименованием ветвей можно запускать в фоновом режиме на работающей БД. Поэтому, когда речь идёт о хранении объектов с огромным количеством необязательных свойств, глобалы — отличный выбор. Причём, напомню, доступ к любому из свойств — моментален, так как в глобале все пути представляют собой B-tree.

    Базы данных на глобалах, в общем случае, это разновидность документно-ориентированных БД, со возможностью хранения иерархической информации. Поэтому в сфере хранения медицинских карт с глобалами могут конкурировать документно-ориентированные БД.

    Ассоциативные массивы (даже с вложенными массивами) прекрасно ложатся на глобалы

    Иерархические документы: XML, JSON также легко хранятся в глобалах.

    Для хранения можно разложить разными способами.

    Одинаковые структуры, связанные иерархическими отношениями

    Примеры: структура офисов продаж, расположение людей в МЛМ-структуре

    База дебютов. Можно в качестве значения индекса узла глобала использовать оценку силы хода.

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

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

    JSON. На картинке показано отражение этого JSON-документа:

    
    var document = {
      "name": "Vince Medvedev",
      "city": "Moscow",
      "threatments": {
        "surgeries": ["apedicectomy", "biopsy"],
        "radiation": ["gamma", "x-rays"],
        "physiotherapy": ["knee", "shoulder"]
      },
      };

    рассмотрим глобалы как разреженные массивы.

    Разреженный массив — это разновидность массива, в котором большинство значений принимает одинаковое значение. На практике часто встречаются настолько огромные разреженные массивы, что нет никакого смысла занимать память одинаковыми элементами. Поэтому есть смысл разреженные массивы реализовывать так, чтобы память не расходовалась на хранение одинаковых значений. В некоторых языках программирования разреженные массивы входят в сам язык. В других языках программирования есть специальные библиотеки, которые позволяют реализовать их. Глобалы — хорошие кандидаты для реализации разреженных массивов, потому что:

    Хранят значения только определённых узлов и не хранят значения неопределённых; Интерфейс доступа к значению узла чрезвычайно похож на то, как во многих языках программирования реализован доступ к элементу многомерного массива.

    
    Set ^a(1, 2, 3) = 5
    Write ^a(1, 2, 3)
    

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

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

    Это можно реализовать, используя функцию $GET. В данном примере рассмотрен 3-х мерный массив.

    
    SET a = $GET(^a(x,y,z), defValue)
    

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

    Матрица смежности (связности). Такие матрицы используются для представления графов. Очевидно, что чем больше граф, тем больше нулей будет в матрице. Если, например, взять граф социальной сети и представить его в виде подобной матрицы, то он почти весь будет состоять из нулей, т.е. будет разреженным массивом.

    
    Set ^m(id1, id2) = 1 
    Set ^m(id1, id3) = 1 
    Set ^m(id1, id4) = 1 
    Set ^m(id1) = 3 
    Set ^m(id2, id4) = 1 
    Set ^m(id2, id5) = 1 
    Set ^m(id2) = 2
    ....
    

    В данном примере мы сохраняем в глобале ^m матрицу связности, а также число ребёр у каждого узла (кто с кем дружит и число друзей).

    Если же число элементов в графе не более 29 миллионов (это число берётся как произведение 8 * максимальный размер строки), то есть ещё более экономичный способ хранения таких матриц — битовые строки, так как в их реализации специальным образом оптимизируются большие пропуски.

    Таблица переходов конечного автомата

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

    Клеточные автоматы

    Самый известный клеточный автомат — игра «Жизнь», который из-за своих правил (когда у клетки много соседей — она умирает) представляет собой разреженный массив.

    Стивен Вольфрам, считает что клеточные автоматы — это новая область науки. В 2002 году он публикует 1280-страничную книгу «A New Kind of Science», где широко аргументирует, что достижения в области клеточных автоматов не являются изолированными, но весьма устойчивы и имеют большое значение для всех областей науки.

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

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

    Картография

    Как правило на картах очень много пустого пространства. Разреженный массив. Конечно, никто не хранит карты в виде растровых массивов, используется векторное представление. Но что из себя представляют векторные карты? Это некая рамка и состоящие из точек полилинии и полигоны. Фактически база данных точек и связей между ними.

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

    Бонусы, которые мы получаем при хранении многомерных матриц в глобалах

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

    Командой Kill мы можем удалить как отдельный элемент, так и строку, и даже целую плоскость. Благодаря свойствам глобалов, это происходит очень быстро — в тысячи раз быстрее, чем поэлементное удаление.

    Выборка столбца матрицы в переменную Column:

    
      ; Зададим трёхмерный разреженный массив 3x3x3
      
      Set ^a(0,0,0) = 1,
          ^a(2,2,0) = 1,
          ^a(2,0,1) = 1,
          ^a(0,2,1) = 1,
          ^a(2,2,2) = 1,
          ^a(2,1,2) = 1
      
      Merge Column = ^a(2,2)
      
      ; Выведем переменную Column
      
      Zwrite Column
    

    Вывод:

    
      Column(0)=1
      Column(2)=1
    

    Что интересно в переменной Column у нас тоже получился разреженный массив, к которому обращаться нужно тоже через $GET, так как значения по умолчанию в нём не хранятся.

    Выборка кусков пространства также может делаться через небольшую программу с использование функции $Order. Это в особенности удобно на пространствах, индексы которых неквантованы (картография).