Войти
ФлеймФорумПроЭкты

Умный бинарный формат

Advanced: Тема повышенной сложности или важная.

Страницы: 1 2 Следующая »
#0
(Правка: 23:53) 23:49, 23 ноя. 2018

Описание проблемы
Как известно, основная задача 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 или другого выбранного формата, то приходится их каким-то образом кодировать в данных и реализовывать в коде.


#1
(Правка: 23:55) 23:49, 23 ноя. 2018

Описание моего решения
Я поставил перед собой цель решить задачу хранения и обработки данных в общем виде - раз и навсегда, что позволит решить сразу все проблемы, описанные выше. Больше никому и никогда не придётся писать свои сериализаторы, конвертеры и парсеры бинарных файлов. Не нужны станут 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) То же самое с клиентом и сервером. Клиент спрашивает у сервера описание протокола, по которому они будут общаться, а дальше с помощью библиотеки преобразует все свои данные в формат, описание которого он получил. Таким образом, даже устаревшая версия клиента сможет общаться с сервером по новому протоколу без обновления кода.

#2
(Правка: 23:50) 23:49, 23 ноя. 2018

План решения
reserved

#3
23:52, 23 ноя. 2018

  STL уже закончил?

#4
23:59, 23 ноя. 2018

Бабер
> STL уже закончил?
Не знаю, при чём тут STL.
Но если ты про мою библиотеку Intra, то её можно писать вечно, и она собирает все мои наработки. Именно на её базе я буду реализовывать свой формат и язык, а уже потом портировать на другие языки.

#5
0:39, 24 ноя. 2018

протобуф достаточно умный?

#6
0:54, 24 ноя. 2018

1 frag / 2 deaths
> протобуф достаточно умный?
Нет, он вообще не умный:
https://developers.google.com/protocol-buffers/docs/encoding

As you know, a protocol buffer message is a series of key-value pairs. The binary version of a message just uses the field's number as the key – the name and declared type for each field can only be determined on the decoding end by referencing the message type's definition (i.e. the .proto file).

То есть там даже схемы внутри нет. И обратная совместимость только на уровне новых и опциональных полей.
И в принципе тут сильно структура ограничена, любой формат на нём не опишешь.
#7
1:42, 24 ноя. 2018

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

> Допустим, у нас были только квадратные изображения и мы сделали Width полем, а
> Height свойством, которое всегда равно Width.
нет, если у нас были только квадратные изображения, то нам разумеется не могло прийти в голову что они могут быть неквадратными, соответственно поле было Size и означало и ширину и высоту. Зато вместо этого мы предусмотрели бы кучу полей для битности каналов R\G\B\A (а также CMYK и HSV), а в итоге все равно никто не пользуется ничем кроме R8G8B8[A8].
Ну т.е. расширяется формат всегда в сторону о которой при разработке никто не мог и подумать. Закладывать в первую версию вычисляемые поля бесполезно.

#8
2:20, 24 ноя. 2018

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].
Такие поля не нужны. Битность каналов реализуется средствами системы типов бинарного формата. А цветовое пространство можно по идее вычисляемыми свойствами сделать, хотя наверное неэффективно и лучше делать через типы-расширения формата, которые у меня тоже будут предусмотрены.

#9
4:51, 24 ноя. 2018

Спойлер «Кросс-Файл»

#10
6:05, 24 ноя. 2018

Классный формат, хочу использовать его в своих программах.
Только никак не пойму, когда я картинку пишу, что делать с шириной и высотой понятно, а вот как описать разбитое на квадратики 16х16 и сжатое после перевода в другое цветовое пространство с потерей (4:2:2) данных, преобразованное дискретным косинусным преобразованием основное содержимое? Общее качество сжатия пусть 95 из 100 в GIMP, если это о чем-то говорит. Вот как это в твоем формате описывается? JPG все пользуются, не надо рассказывать, что это никому не нужно.
А еще мне будет нужно mp3 и ogg vorbis для музыки и h264 для видеотекстур. Но тупо класть прямо h264 не хотелось бы, хотелось бы пользоваться умным форматом.

#11
7:31, 24 ноя. 2018

gammaker

Чем BSON не нравится ?

1 frag / 2 deaths
> протобуф достаточно умный?

https://habr.com/post/310032/

https://google.github.io/flatbuffers/flatbuffers_benchmarks.html

#12
12:05, 24 ноя. 2018

KILLJOY
> Классный формат, хочу использовать его в своих программах.
Отлично, значит я не зря его придумываю)

KILLJOY
> как описать разбитое на квадратики 16х16 и сжатое после перевода в другое
> цветовое пространство с потерей (4:2:2) данных, преобразованное дискретным
> косинусным преобразованием основное содержимое?
На уровне системы типов. Будут специальные преобразующие типы @HSV, @DCT, @deflate и т.п., которые оборачивают другие типы и говорят о том, как они закодированы. Часть таких типов будут встроены, а остальные будут подключаться как расширения. Возможно, они смогут прямо из DLL дёргать нужные функции при преобразованиях. Надо продумать этот вопрос.

Я на этих выходных ещё пораздумываю над языком и позже напишу примеры, как будет выглядеть спецификация BMP, PNG, JPG на нём.

0iStalker
> Чем BSON не нравится ?
Всем тем же, чем и JSON. Структура хранения у него та же самая с теми же ограничениями: например, там нет ссылок. И весит он столько же, так как дублируется информация о полях объектов в массивах. И замапить в память их напрямую нельзя. Конечно, если сериализовать в SoA, то будет компактно, но это руками нужно делать.

#13
12:14, 24 ноя. 2018

gammaker
> например, там нет ссылок.

Вот только не хватало превращать бинарник в лапшу типа XSLT/XML  (вон чуваки из IEC додумались до ссылок в своём формате описания цифровой электроподстанции... парсинг этого дерьма превращается в ад, ну или если ограничиваться конкретными выхлопом конкретной SCADA, - получается 100% vendor lock (а ведь хотели универсальный, кросплатформенный формат). Короче, о чём я, - умные вещи должны быть через расширения, средствами основного формата, который должен быть по возможности минималистичным.

#14
13:59, 24 ноя. 2018

0iStalker
> парсинг этого дерьма превращается в ад
Так в том и смысл моего формата, что он позволяет описать структуру чего угодно, даже всяких запутанных форматов, и мой парсер всё это автоматически пережуёт. Свой парсер больше никому писать не надо.

Кстати, мой формат можно использовать и для перехода от старых форматов к новым. Например вот я опишу на нём структуру png файла и сделаю внутри ссылку на отдельный png-файл как на продолжение текущего. Программа открывает мой файл и автоматически её становится доступна декодированная картинка в png файла. То есть сам формат png "глупый", программа ничего не знает о PNG, потому что в ней даже нет парсера PNG. Но она может его прочитать, потому что рядом лежит описание формата.
Я сейчас не дома, с телефона понятнее сложно описать. Я планирую написать в виде псевдокода, как это будет выглядеть с точки зрения пользователя, чтобы было лучше понятно, о чём я.

Страницы: 1 2 Следующая »
ФлеймФорумПроЭкты