Описание проблемы
Как известно, основная задача IT - это хранение, обработка и передача данных. И одна из главнейших проблем - это проблема совместимости форматов данных. И эта проблема возникает на всех уровнях:
I. Уровень железа
Главным образом, это порядок байт: Big Endian и Little Endian.
II. Уровень одного процесса
Есть логические типы, которые могут быть представлены в памяти множеством разных вариантов:
1) Коллекция: массив (статический / динамический); связный список (в виде контейнера или интрузивный); разбитый на части массив, например, список массивов
2) Array of structures (AoS) vs Structure of arrays (SoA), а также их всевозможные гибриды
2) Словарь: сортированный по ключу массив пар (AoS) или пара отдельных массивов ключей и значений (SoA); сортирующее дерево, хеш-таблицы с бесконечным множеством их всевозможных вариаций.
3) Графы: коллекции вершин и рёбер, матрица смежности, вершины с ссылками на соседей и т.п.
Для этого обычно нет стандартных библиотек и графы чаще всего возникают в кастомных классах, которые не совместимы между собой, что не позволяет применить к ним существующие общепринятые алгоритмы работы с графами в готовом виде, а требует изобретения велосипеда каждый раз для каждой комбинации.
4) Изображения с разным форматом пикселя: RGB565, RGB8, RGBA8, RGB16F, RGB16I и т.п. - более полный список можно найти например в спецификации OpenGL.
Например, в C++ ситуация осложняется тем, что на каждый из этих вариантов ещё и делают кучу несовместимых друг с другом классов-контейнеров (STL, Qt, другие библиотеки и велосипеды), что приводит к экспоненциальному росту комбинаций и приводит к необходимости руками писать цикл, который приведёт из одного вида в другой, либо делать разные версии алгоритма для каждого из них. Немного облегчают жизнь итераторы, но кардинально решает этот вопрос моя библиотека Intra благодаря наличию в ней диапазонов - пока в основном только для категории коллекций. Но это только коллекции и только C++, в то время как проблема актуальна также для других языков, а также для других, более высоких уровней, о которых речь пойдёт дальше.
А если приложение написано на нескольких языках, то число возможных комбинаций вырастает ещё на порядки - одни и те же структуры данных нужно описывать и синхронизировать на каждом из языков, делать обёртки, маршаллинг данных и прочее.
III. Обмен данными между приложениями
а) Посредством файлов:
Разные программы могут поддерживать разные форматы для хранения данных одного и того же логического типа (изображения, аудио, 3D-модели, видео, числовые ряды, конфиги, логи, таблицы, текст), но при этом не уметь общаться друг с другом. Часто для ПО создают кастомные проприетарные форматы, потому что они лучше подходят под конкретные задачи и дают большую производительность, чем использование стороннего формата, особенно, если он текстовый.
Но эти задачи имеют свойство меняться и форматы устаревают. Получается так, что приходится поддерживать новые и старые ветки кода, а старые версии ПО не могут читать файлы в формате более новой версии. Всё это приводит к огромным трудозатратам и неизбежным багам, с которыми потом приходится сталкиваться пользователям.
К примеру, родной формат 3DS Max .max не поддерживается в Blender и наоборот .blend не поддерживается в 3DS Max. Как костыль используются популярные форматы 3DS, OBJ, FBX, COLLADA, как промежуточные. И нередка ситуация, когда при экспорте и импорте они криво отображаются, потому что при этом теряются важные данные. Или потому что в экспортере или импортере баги, так как их написание - непростое дело. А использовать их в игровых движках и вовсе не оптимально. Поэтому практически каждый движкописатель приходит к тому, что делает свой собственный формат моделей, который заточен под его движок и с которым никто кроме него работать не умеет.
б) Посредством общения по сетевым протоколам:
Эта же проблема стоит в протоколах общения между сервером и клиентом. Когда добавляются новые фичи или меняются существующие, API общения между ними может измениться. Так плодятся версии REST API v1, v2, v3, может быть, кастомные бинарные протоколы и т.п., что приводит к необходимости поддерживать все ветки кода, хотя вроде как логически во всех версиях передаётся одна и та же информация, пусть и немного в другом представлении.
Сложно представить себе проект ПО, в котором не нужно было бы сохранять и загружать данные. А это значит, что каждый разработчик сталкивается с тем, в каком формате эти данные хранить, как их в него сериализовать и десериализовать обратно. Хорошо, если данных немного, они все текстовые, они не имеют сложных логических связей и ссылок, а в языке есть встроенная рефлексия - берём JSON или XML и не паримся. Но, к сожалению, такая удачная комбинация встречается очень редко, и перед разработчиком стоит мучительный выбор компромисса между удобством, простотой реализации, гибкостью и эффективностью.
Если же данных много, то может встать вопрос эффективности, и приходится использовать что-нибудь бинарное вроде protobuf или даже изобретать свой кастомный формат со своей сериализацией и десериализацией, при этом жертвуя простотой и человекочитаемостью.
Если же есть какие-то логические связи, которые не ложатся на структуру JSON или другого выбранного формата, то приходится их каким-то образом кодировать в данных и реализовывать в коде.
Описание моего решения
Я поставил перед собой цель решить задачу хранения и обработки данных в общем виде - раз и навсегда, что позволит решить сразу все проблемы, описанные выше. Больше никому и никогда не придётся писать свои сериализаторы, конвертеры и парсеры бинарных файлов. Не нужны станут JSON, XML, ProtocolBuffers, FlatBuffers и все остальные форматы хранения данных, потому что любой за пять минут сможет создать свой собственный формат, идеально заточенный под его конкретную задачу по всем параметрам: неограниченная расширяемость, эффективность, простота реализации и даже человекочитаемость. При этом этот формат будет автоматически распознаваться всеми программами, которые используют мою технологию. И самой первой такой программой будет моя утилита, которая позволит открыть любой бинарник, увидеть текстовое описание его формата, данные, а также извлечь оттуда изображения, аудио, видео, которые могут в нём содержаться.
Что определяет логическую структуру:
1) Имена полей
2) Свойства и их имена
3) Категория, к которой относится тип поля - число, массивы, словари, структуры, кортежи
4) Некоторые типы могут иметь несколько логических типов: например структура, описывающая связный список, может быть десериализована не только в структуру, но и в массив или в любой другой контейнер-коллекцию
5) Свойства-теги, которые говорят, что эта структура хранит контент определённого типа. Например наличие свойства "#Image" будет означать, что это картинка, и приложению надо искать свойства или поля Format, Data, Width и Height, в которых будет вся необходимая информация о том, как эту картинку загрузить и прочитать. Аналогично с другими типами контента.
Свойства - очень полезная вещь для поддержания совместимости между разными форматами и версиями одного формата. Допустим, у нас были только квадратные изображения и мы сделали Width полем, а Height свойством, которое всегда равно Width. Таким образом, высоту хранить не нужно, она будет вычисляться из свойства Width при десериализации. Потом в новой версии формата мы решаем убрать ограничение квадратности и заменяем свойство Height на поле с тем же названием. Для программы всё прозрачно - она не отличает свойства от полей, библиотека умного формата сама всё преобразует, если надо, сверив формат файла с форматом данных, в который она десериализует.
Что определяет физическую структуру:
1) Подробные типы полей. Можно с точностью до бита указывать их расположение в структуре, устанавливать любое выравнивание, порядок байт и т.п.. Хотим хранить число как 32-битное Big-Endian и без выравнивания - ок, используем соответствующий тип. Логически между числами с разным количеством бит, порядком байт, наличием знака и выравниванием нет никакой разницы до тех пор, пока не происходит переполнения при преобразовании. Можно использовать даже variadic числа, длина которых не ограничена, и они ничем логически не будут отличаться от простого инта.
2) Поле или свойство. Поле занимает место в структуре, а свойства нет - это выражение, которое либо константа, либо вычисляется от других полей. А логически с точки зрения программы разницы нет. Можно даже делать более сложные штуки, когда в зависимости от какого-то условия в структуре нечто является полем или свойством.
Как это будет работать. Допустим, пользователь имеет объект, массив или структуру в коде, которую он хочет сохранить. Если в языке, на котором он пишет, нет рефлекшена, ему придётся описать поля его структуры. Библиотека позаботится о том, чтобы это можно было сделать максимально простым способом, который возможен в его языке. Если рефлекшен есть, но разработчик хочет сохранить поля под другими именами, он также может их задать.
1) Самый простой вариант. Переданный объект сохраняется в файл в нативном формате как он есть. Если он POD, то вообще бит-в-бит. Если он содержит указатели или ссылки, то они тоже сериализуются корректно и транслируются в указатели как смещение относительно начала файла. Все вложенные объекты сериализуются рекурсивно. При этом в заголовке файла в бинарном виде будут описаны все задействованные при сериализации типы.
2) На специальном языке, синтаксис которого я сейчас продумываю, разработчик описывает физическую и логическую структуру данных, которые он хочет хранить - будем называть это спецификацией его формата. В спецификации можно описывать числа переменной длины, битовые поля, структуры с опциональными полями, свойства и многое другое, что не умеет большинство языков программирования, но что позволит хранить данные более компактно. При сериализации разработчик указывает свою спецификацию в библиотеке и именно она попадает в заголовок сериализуемого файла, но уже в бинарном представлении. Все поля сериализуемого объекта преобразуются в соответствующие спецификации типы.
3) То же самое с клиентом и сервером. Клиент спрашивает у сервера описание протокола, по которому они будут общаться, а дальше с помощью библиотеки преобразует все свои данные в формат, описание которого он получил. Таким образом, даже устаревшая версия клиента сможет общаться с сервером по новому протоколу без обновления кода.
План решения
reserved
STL уже закончил?
Бабер
> STL уже закончил?
Не знаю, при чём тут STL.
Но если ты про мою библиотеку Intra, то её можно писать вечно, и она собирает все мои наработки. Именно на её базе я буду реализовывать свой формат и язык, а уже потом портировать на другие языки.
протобуф достаточно умный?
1 frag / 2 deaths
> протобуф достаточно умный?
Нет, он вообще не умный:
https://developers.google.com/protocol-buffers/docs/encoding
gammaker
> Клиент спрашивает у сервера описание протокола, по которому они будут общаться,
> а дальше с помощью библиотеки преобразует все свои данные в формат, описание
> которого он получил. Таким образом, даже устаревшая версия клиента сможет
> общаться с сервером по новому протоколу без обновления кода.
звучит утопично. Протокол же не только структуру данных включает - протокол, обычно, это набор возможных команд и ответов на них. Соответственно если команды поменялись (или у старых команд поменялись параметры) и обратной совместимости нет, то клиент сможет только развести руками.
> Допустим, у нас были только квадратные изображения и мы сделали Width полем, а
> Height свойством, которое всегда равно Width.
нет, если у нас были только квадратные изображения, то нам разумеется не могло прийти в голову что они могут быть неквадратными, соответственно поле было Size и означало и ширину и высоту. Зато вместо этого мы предусмотрели бы кучу полей для битности каналов R\G\B\A (а также CMYK и HSV), а в итоге все равно никто не пользуется ничем кроме R8G8B8[A8].
Ну т.е. расширяется формат всегда в сторону о которой при разработке никто не мог и подумать. Закладывать в первую версию вычисляемые поля бесполезно.
kipar
> Соответственно если команды поменялись (или у старых команд поменялись
> параметры) и обратной совместимости нет, то клиент сможет только развести
> руками.
Если поменялись сами команды, то поменялась логическая структура, а это уже вне компетенции формата. Если поменялись параметры, но эти различия можно выразить через старые параметры, то это реализуется через вычисляемые свойства.
kipar
> нет, если у нас были только квадратные изображения, то нам разумеется не могло
> прийти в голову что они могут быть неквадратными, соответственно поле было Size
> и означало и ширину и высоту.
Если ты хочешь, чтобы твой формат распознавался как картинка другими программами тоже, то ты по общему соглашению должен сделать свойство #Image и поля или свойства Width и Height. Если тебе это не нужно и ты этого не сделал сразу, то тоже не беда - потом можно добавить поля Width и Height, а для обратной совместимости Size сделать свойством, которое вычислимо только тогда, когда Width == Height и равно Width. Тогда старая версия программы сможет читать новые файлы, хранящие квадратные картинки, а новая сможет читать любые картинки из нового файла. А что делать со старыми файлами с Size, действительно, надо подумать. Наверное всё-таки в программе надо будет оставить проверку на Size, если Width и Height не найдены. Но конкретно для случая с изображениями, если бы пользователь с самого начала следовал соглашению, такого бы и не случилось.
kipar
> Зато вместо этого мы предусмотрели бы кучу полей для битности каналов R\G\B\A
> (а также CMYK и HSV), а в итоге все равно никто не пользуется ничем кроме
> R8G8B8[A8].
Такие поля не нужны. Битность каналов реализуется средствами системы типов бинарного формата. А цветовое пространство можно по идее вычисляемыми свойствами сделать, хотя наверное неэффективно и лучше делать через типы-расширения формата, которые у меня тоже будут предусмотрены.
Классный формат, хочу использовать его в своих программах.
Только никак не пойму, когда я картинку пишу, что делать с шириной и высотой понятно, а вот как описать разбитое на квадратики 16х16 и сжатое после перевода в другое цветовое пространство с потерей (4:2:2) данных, преобразованное дискретным косинусным преобразованием основное содержимое? Общее качество сжатия пусть 95 из 100 в GIMP, если это о чем-то говорит. Вот как это в твоем формате описывается? JPG все пользуются, не надо рассказывать, что это никому не нужно.
А еще мне будет нужно mp3 и ogg vorbis для музыки и h264 для видеотекстур. Но тупо класть прямо h264 не хотелось бы, хотелось бы пользоваться умным форматом.
gammaker
Чем BSON не нравится ?
1 frag / 2 deaths
> протобуф достаточно умный?
https://google.github.io/flatbuffers/flatbuffers_benchmarks.html
KILLJOY
> Классный формат, хочу использовать его в своих программах.
Отлично, значит я не зря его придумываю)
KILLJOY
> как описать разбитое на квадратики 16х16 и сжатое после перевода в другое
> цветовое пространство с потерей (4:2:2) данных, преобразованное дискретным
> косинусным преобразованием основное содержимое?
На уровне системы типов. Будут специальные преобразующие типы @HSV, @DCT, @deflate и т.п., которые оборачивают другие типы и говорят о том, как они закодированы. Часть таких типов будут встроены, а остальные будут подключаться как расширения. Возможно, они смогут прямо из DLL дёргать нужные функции при преобразованиях. Надо продумать этот вопрос.
Я на этих выходных ещё пораздумываю над языком и позже напишу примеры, как будет выглядеть спецификация BMP, PNG, JPG на нём.
0iStalker
> Чем BSON не нравится ?
Всем тем же, чем и JSON. Структура хранения у него та же самая с теми же ограничениями: например, там нет ссылок. И весит он столько же, так как дублируется информация о полях объектов в массивах. И замапить в память их напрямую нельзя. Конечно, если сериализовать в SoA, то будет компактно, но это руками нужно делать.
gammaker
> например, там нет ссылок.
Вот только не хватало превращать бинарник в лапшу типа XSLT/XML (вон чуваки из IEC додумались до ссылок в своём формате описания цифровой электроподстанции... парсинг этого дерьма превращается в ад, ну или если ограничиваться конкретными выхлопом конкретной SCADA, - получается 100% vendor lock (а ведь хотели универсальный, кросплатформенный формат). Короче, о чём я, - умные вещи должны быть через расширения, средствами основного формата, который должен быть по возможности минималистичным.
0iStalker
> парсинг этого дерьма превращается в ад
Так в том и смысл моего формата, что он позволяет описать структуру чего угодно, даже всяких запутанных форматов, и мой парсер всё это автоматически пережуёт. Свой парсер больше никому писать не надо.
Кстати, мой формат можно использовать и для перехода от старых форматов к новым. Например вот я опишу на нём структуру png файла и сделаю внутри ссылку на отдельный png-файл как на продолжение текущего. Программа открывает мой файл и автоматически её становится доступна декодированная картинка в png файла. То есть сам формат png "глупый", программа ничего не знает о PNG, потому что в ней даже нет парсера PNG. Но она может его прочитать, потому что рядом лежит описание формата.
Я сейчас не дома, с телефона понятнее сложно описать. Я планирую написать в виде псевдокода, как это будет выглядеть с точки зрения пользователя, чтобы было лучше понятно, о чём я.
Тема в архиве.