© Георгиевский Анатолий, 04.11.2005 - 02.08.2008

Перемещаемый формат данных

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

Постановка задачи

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

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

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

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

Сериализация структурированных данных

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

  1. На разных архитектурах, разных операционных системах, при сборке программ разными компиляторами применяются различные правила выравнивания данных.
  2. На разных архитектурах порядок следования байтов в слове может оказаться разным.
  3. Форматы хранения базовых типов, например, вещественных чисел, в разных языках программирования, при компиляции разными компиляторами, с различными опциями одного компилятора, на разных аппаратных платформах могут отличаться.
  4. Данные переменной длины, например, строки представляются в структурах данных, как ссылки на динамически выделяемую память.
  5. Структуры данных могут содержать ссылки (указатели) на динамические данные. Ссылка содержит адрес динамической структуры в памяти. При передаче объекта по сети, для сохранения связи между объектами, нужно создавать "символьные" ссылки, описывающие связи между объектами в последовательном потоке данных. "Символьная" ссылка может быть уникальным именем, идентификатором или индексом объекта.
  6. Значения по умолчанию. Нет смысла передавать по сети значения переменных, если переменная осталась без имзменения.
  7. Упаковка данных. Нет смысла передавать массив данных, если большая часть элементов обращается в нуль. В таком случае выгоднее передавать только ненулевые элементы массива. Во многих случаях бывает выгоднее потратить время на упаковку данных, если это ведет к существенному снижению объема передаваемой информации.

Выбор способа сериализации данных - личное дело разработчика. Мы можем предложить ряд форматов пригодных для платформо-независимого хранения и передачи структурированных данных. Ниже мы приводим краткое описание некторых текстовых форматов, однако реализовать предложенные идеи можно и в бинарном формате.

XML - Обобщенный язык разметки

Принцип организации формата: каждый объект может состоять из нескольких дочерних объектов. Каждая запись "нода" обозначается открывающим и закрывающим "тегом", "тег" - обозначает тип объекта, может содержать список атрибутов и список вложенных (дочерних объектов) "нод". Таким образом, задается древовидная структура объекта. Каждая "нода" может иметь специальный атрибут - уникальный символьный идентификатор "ноды", на который можно сослаться из другой "ноды". Атрибуты, которые имеют предопределенное значение, значение по умолчанию, не указываются.

XML очень не эффективный формат, если дело касается передачи данных по сети, поскольку очень много места тратится на повторяющиеся имена тегов и атрибутов. Особенно это заметно при передаче множества однотипных объектов, когда размер XML файла в десятки раз может превышать размер бинарных данных. Формат безусловно удобен для представления текстовых данных, для хранения в "человеческом" формаете исходных и промежуточных данных. Критерием выбора формата является: необходимость представления структурированных данных в форме пригодной для редактирования. На формате XML основываются современные форматы офисных документов. Чтобы хоть как-то компенсировать раздутость текстовых пометок, применяется упаковка данных.

Стандартные библиотеки для разбора XML: GLib и libxml2.

TLV - принцип представления бинарных данных

TLV (type-length-value, тип длина значение) представляет собой принцип упаковки любых структурированных бинарных данных. Частным случаем "типа" является структура - контейнер включающий несколько полей TLV в поле "значение". Для каждого типа необходимо определить способ сериализации/десериализации. На практике, бывает просто определить правила сериализации для всех типов данных, кроме указателей. Для разрешения указателей необходимо завести ассоциативный массив (словарь), где ардесу сопоставяется идентификатор объекта. И наоборот, при распаковке данных должны динамически создаваться бинарные данные с привязкой указателей к идентификаторам объектов.

BER - набор правил кодирования бинарных данных

BER (basic encoding rules) - формат базируется на принципе TLV, используется для кодирования и сериализации бинарных данных. Формат предлагается в качестве примера реализации принципа TLV. На примере BER рассмотрим ряд способов представления различных типов данных.

Типы. Типы, в частности поле "тип", кодируются одним или несколькими байтами. В первом байте три старшие бита выделены для классификации идентификатора типа: базовый, прикладной, контекстно-зависимый, личный (private); тип может быть составным или примитивным. Для представления собствено идентификатора типа используется пять младших бит в байте. Если требуется закодировать идентификатор со значением более 30, то первый байт в поле идентификатора содержит число 31, а значение кодируется в последующих байтах...

Длина. Поле "длина" кодируется одним или несколькими байтами. Одним байтом кодируется длина от нуля до 127. Большая длина кодируется несколькими байтами. При разборе формата, если в старшем бите превого байта длины указана 1, то длина кодируется несколькиим байтами, в битах 7-1 первого байта содержится количество последующих байт, в которых закодирована длина.

Строки. Строки могут быть символьные или бинарные. С упаковкой строк всё просто. в поле L - записывается длина строки в байтах. А сама строка в формате UTF-8 записывается в поле V.

Числа. Целые числа кодируются минимальным количеством байт. Старшие байты со значением 0XFF или 0х00 могут опускаться.

Идентификаторы объектов. В терминологии формата, ссылки на объекты называются идентификаторами объектов. Чтобы лучше понять принцип кодирования идентификаторов объектов надо представить структурированные данные в виде единого дерева, содержащего все объенкты которые используются в программе. В качестве аналогии можно представить дерево документа в формате XML. Каждый узел дерева имеет свой идентификатор, например, это может быть порядковый номер дочернего объекта. Ссылкой на объект в дереве будет являться список идентификаторов (или порядковых номеров) вложенных объектов от корня дерева до интересующего нас узла. Например, такая ссылка может быть записана в виде "root1→grandparent3→parent1→child(34)→..." или идентификаторами соответствующих объектов "1,3,1,34,...". При использовании числовых идентификаторов, каждое число составляющее идентификатор должено уникальным образом идентифицировать один из объектов внутри списка дочерних объектов.

Правила кодирования идентификаторов объектов. Если числовой идентификатор мньше или равен 127, то число кодируется одним байтом, в старшем бите 0. Число больше 127 кодируется набором байт, в которых 7 бит отведено для хранения числа, а старший бит (1) указывает на расширение числа в следующем байте.

Формат PER (packed encoding rules) - основан на принципах кодирования TLV, но без выравнивания данных на байт, представляет собой битовый поток данных. PER позволяет достичь более плотной упаковки данных в сравнении с BER.

Принцип упаковки данных TLV широко применяется при построении бинарных форматов сетевых протоколов.
[ITU-T X.680, X.690 - X.693] Подробнее о форматах BER, PER и XER. А также язык ASN.1 для описания структур данных и идентификаторов объектов.

XDR - Стандарт бинарного представления данных

Стандарт XDR (External Data Representation) [IETF RFC 4506, STD67] представляет способ описания и кодирования бинарных данных для передачи между различными архитектурами. В отличие от BER предлагает более простые способы кодирования бинарных данных и более естественные для передачи между программами наприсанными на языках С/C++ или Pascal.

PDF - переносимый формат документов

Каждая запись - объект, может состоять из двух частей: списка параметров и бинарного потока данных. Формат и длина потока определяются в списке параметров. Определены типы параметров: строки, массивы, списки, числовые значения, имена констант. Имена параметров и констант начинаются специальным символом, который служит для выделения имен, например, "косая черта". Специальные символы используются для выделения начала и конца списка или массива. Значения параметров выделяются пробелами или спец.символами. Значением параметра может быть ссылка на объект. Ссылка на объект состоит из спец символа и индекса объекта в таблице ссылок.

В реализации такого формата применительно к параллельной обработке данных видится одна сложность: надо где-то запрашивать очередной свободный индекс (идентификатор объекта).

Создание файла PDF

При создании потока данных необходимо, по мере добавления объектов в выходной поток, создавать таблицу ссылок для прямого доступа к элементам данных. Ссылка содержит смещение от начала файла, длину и признаки (блокировки, удаление, готовность, разрешения использования). На момент готовности данных, таблица ссылок будет сформирована. Количество объектов, равно как и количество ссылок в таблице известно, длина сегмента данных то же известна. Таблица ссылок добавляется в конец файла данных, последняя запись в файле указывает на начало таблицы ссылок. Таким образом данные и индексы могут быть представлены одним файлом.

Разбор файла PDF

Разбор начинается с конца файла. В самом конце файла содержится ссылка на таблицу ссылок (смещение таблицы от начала файла). Длина строки ссылки фиксирована, поэтому по таблице ссылок можно быстро найти начало и длину объекта с нужным серийным номером. Дальше функцией fseek запрашивается необходимый фрагмент файла, который содержит в себе последовательное представление объекта. Объект может содержать в себе структурированные данные и ссылки на другие объекты.

База данных

В ряде случаев способ организации данных должен допускать непрерывное пополнение, изменение и удаление записей. От файла в формате PDF можно плавно перейти к системе управления базой данных (СУБД). Для одновременного пополнения и изменения содержимого файла данных надо разделить файл данных и файл индексов (таблицу ссылок). Сбор "мусора" по файлу данных, дефрагментация базы, сортировка и прочие операции обслуживания в первом приближении не требуются, их можно производить в свободное от основной работы время, требуется только централизованное управление, чтобы можно было организовать одновременную работу нескольких процессов с одними и теми же данными.

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

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

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

Язык простых запросов

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

SQL - язык простых запросов... Стандартизованный синтаксис языка запросов, применяется при обращении к базе данных. Язык простых запросов позволяет формулировать команды добавления данных, выборки и систематизации данных, формулировать задачи обновления полей в базе. При этом все действия по работе с данными осуществляются на стороне сервера, по сети пересылаются запросы.

Relational Data Base Management System

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

Реляционные базы данных концептуально означают таблицы данных, именовынне коллекции данных. Под таблицей в таких случаях подразумевается коллекция "relations" - элементов данных. Каждая строка таблицы представляет собой запись. Все операции производятся над записями. Колонки таблицы имеют заранее заданный тип данных. Всякая система управляения базами данных, в которой можно определять собственные типы и действия над ними имеет право называться объектно-ориентрованной или объектно-реляционной.

Современные системы управления базами данных позволяют организовывать распределенную обработку и храниение данных. Процесс синхронизации содержимого базы между копиями базы называется репликацией базы. Часто для организации распределенных высокопроизводительныех вычислений используется СУБД PostgreSQL для промежуточного храннения и систематизации данных. PostgreSQL предлагает развернутый программный интерфейс для создания прикладных программ. На СУБД MySQL принято строить информационные базы данных. Для реализации встроенных баз данных чаще всего используют Berkeley DB.

Заключение

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


  • MySQL - быстрая, надежная и самая распространенная система обработки простых запросов
  • PostgreSQL - система управления базами данных, имеет массу интересных особенностей реализации
  • Berkeley DB - открытое программное обеспечение для создания приложений со встроенной базой данных

    (4 ноября 2005 г. - 2 августа 2008 г.)

  •