Fast Positive Tuples, aka "Позитивные Кортежи" by Positive Technologies.
Машинно-эффективный формат линейного представления небольших структур данных для (де)сериализации, обмена сообщениями и размещения в разделяемой памяти. "Позитивные Кортежи" спроектированы в соответствии с минималистическим тезисом "Лучше меньше, да лучше".
Machine-handy format for linear representation of small data structures for (de)serialization, messaging and placement in shared memory. "Fast Positive tuples" is designed according to the "Less is more" idiom. English translation by Google and by Yandex.
The Future will (be) Positive. Всё будет хорошо.
"Позитивные Кортежи" - это простой формат представления небольших структур данных в линейном, удобном для машины виде. Библиотека libfptu реализует поддержку формата "Позитивных кортежей", предоставляя интерфейс C++14 и выше.
Можно сказать, что libfptu предлагает гибкость JSON, скорость нативных структур языка C с возможностями boost::optional и boost::variant. В актуальной версии libfptu появилась поддержка схемы данных и предварительно размещенных полей (aka preplaced) для привязки к нативным структурам языка C, а также возможность размещения и совместного использования (чтения) кортежей в разделяемой памяти.
Однако, в некоторых сценариях библиотека libfptu может оказаться неудобной и несколько суровой, так как не старается предлагать возможностей, которые ведут к потере эффективности при обработке машиной или требуют дополнительных служебных данных.
1. Легковесность и удобство для машины. Ничего лишнего. Объём кода минимален, а внутренняя структура линейна и проста.
"Позитивные кортежи" не предлагают лишнего, в том числе IDL и кодогенератор, но могут быть эффективными как нативные структуры, поддерживая строки, коллекции и опциональные поля в линейном участке памяти.
2. Непосредственная (де)сериализация. Кортеж формируется в виде линейной последовательности байт, к которой просто дописываются данные. Поэтому (де)сериализация в "Позитивные Кортежи" магически быстрая.
Заполнение кортежа происходит без лишних операций, преимущественно простым однократным копированием данных в заранее выделенный буфер. При этом сериализованное представление всегда готово, достаточно получить размер данных и указатель на их начало.
3. Очень быстрый доступ. libfptu позволяет сочетать скорость прямого доступа к полям фиксированных структур и подход разреженных множеств с эффективным поиском в индексе.
Для эффективного доступа к полям кортежа достаточно его "сырого" представления "как есть" в линейном участке памяти, без какой-либо подготовки, без каких-либо преобразований, изменений и манипуляций. Получения поля из кортежа, в худшем случае сводится, к SIMD-поиску его дескриптора в заголовке. Что требует чтения лишь одной кэш-линии для первых 15 полей и на каждые 16 последующих.
4. Изменения данных дешевы. В отличии от традиционных кортежей, поля можно также добавлять и удалять.
При этом в линейном представлении могут образовываться неиспользуемые зазоры, а у вас появляется выбор: пожертвовать местом или запросить дефрагментацию, которая, в худшем случае, не дороже однократного копирования содержимого кортежа.
5. Немного объёмнее чем MessagePack. Данные хранятся в нативном машинном представлении, без сжатия. Поэтому для каждого поля может потребоваться на 3-4 байта больше.
Тем не менее, следует аккуратно интерпретировать эти цифры. В предельном случае, когда в данных много 64-битных целочисленных полей с близкими к нулю значениями, представление в libfptu может потребовать до 12 раз больше памяти в сравнении с MessagePack (1 байт в MessagePack, против 12 байт в libfptu).
Однако, "Позитивные Кортежи" не являются серебряной пулей и не подойдут для случаев:
- Требуется человекочитаемый формат данных.
- Требуется IDL и/или кодогенератор.
- Требуется полностью самоописывающийся формат данных.
- В структурах более 2000 полей.
- Размер одной структуры более 250 килобайт.
- Минимизация объема важнее скорости доступа и затрат на (де)сериализацию.
"Позитивные кортежи" ориентированы на эффективную машинную обработку и компактное представление структурно простых данных. Поэтому:
-
Не содержат имен полей и другой информации, которая не требуется машине. Соответственно "Позитивные кортежи" нельзя отнести к само-описывающимся форматам представления данных.
-
Не используют полноценную схему данных, а только опциональный минималистический справочник. При этом, по выбору программиста, можно сочетать без-схемные сценарии использования с полностью и/или частично зафиксированной схемой.
-
Не предусматривает обязательных встроенных полей, идентификаторов или TypeId для различения структурных типов.
Размер кортежей ограничен 250 килобайтами и 8 тысячами экземпляров полей. Поля внутри кортежей строго типизированы и идентифицируются легковесными токенами, которые используются для доступа к полям через API. Можно сказать, что токены являются компактными именами полей в удобной для машины форме. В свою очередь, справочник схемы обеспечивает трансляцию имен полей в токены.
Поля предлагаются двух видов: предварительно размещенные (preplaсed) и свободные (loose). Основное отличие между ними в разных компромиссах между скоростью доступа и расходуемым местом. Доступ к полям производится единообразно, вне зависимости от вида поля.
Предварительно размещенные или preplaced-поля аналогичны полям в
структурах языка C
, физически всегда присутствуют и однозначно
определяются схемой.
В кортеже, соответствующим некоторой схеме, координаты preplaced-поля всегда известны и зависят только от схемы. Поэтому обращение к preplaced-полю предполагает наличие схемы данных, но не требует какого-либо поиска и равнозначно чтению данных по фиксированному смещению. В свою очередь, токен доступа любого preplaced-поля содержит такое смешение.
Preplaced-поля физически всегда располагаются в начале кортежей. При этом для типов c переменной длинной данных (например строк) непосредственно внутри поля хранится лишь смещение к данным, которые располагаются вместе с другими вариативными элементами в конце кортежа.
Накладные расходы доступа к preplaced-полям могут быть сведены к нулю посредством генерации кода привязанного к схеме данных, которая полностью или частично фиксируется. Технически это сводится к использованию статических токен-классов, при использовании которых компилятор способен сгенерировать inline-код непосредственного доступа к данным.
При необходимости libfptu может эмулировать отсутствие preplaced-полей. Для этого, в зависимости от типа данных, одно из возможных значений поля резервируется для обозначения логической "пустоты". Например, для целочисленных типов со знаком в качестве таких DENIL-значению (designated NIL) используется крайнее отрицательное значение (INT_MIN).
Свободные или loose-поля всегда опциональны и занимают место только при присутствии в кортеже. Для присутствующих loose-полей в начале кортежа поддерживается компактный индекс, в котором идентифицируется номером поля и типом данных. Таким образом, loose-поля всегда несут информации о типе своих данных, являются частично само-описывающимися и позволяют без-схемные сценарии использования.
При необходимости loose-поля могут многократно повторяться в
кортеже, образую таким образом неупорядоченные итерируемые коллекции,
подобно repeated fields
в Protocol Buffers. Для этого поле должно быть
определено в схеме как "коллекция".
Для поиска loose-полей в индексе libfptu использует как последовательное сканирование с акселерацией SSE2/AVX/AVX2/AVX512, так и сортировку с двоичным поиском.
Внутри libfptu добавление loose-поля в кортеж приводит к дозаписи дескриптора в начало индекса и дозаписи данных в конец кортежа. Обращение к loose-полю сводится к поиску соответствующего дескриптора в индексе, а затем чтению его значению по хранимому в дескрипторе смещения.
Удаление loose-полей, а также обновление значений полей вариативной длины (строки, бинарные строки, вложенные кортежи), может приводить к образованию внутри кортежа неиспользуемых участков, которые ликвидируются дефрагментацией. Такая дефрагментация не дороже однократного копирования кортежа и не является обязательной.
Набор типов зафиксирован и включает все распространенные нативные (машинные) типы, а также строки, дата/время, произвольные последовательности байт, IP-адреса, IP-сети, MAC-адреса и дайджесты.
Полный набор типов зафиксирован в определении enum fptu::genus
, здесь же стоит
упомянуть некоторые особенности:
-
text
= Строки UTF8 длиной до 262129 байт. Во внутреннем представлении длина строк хранится в явном виде, терминирующий ноль не используется, но допустим внутри строк. -
varbin
= Произвольные последовательности байт (бинарные строки) размером до 262128 байт. -
nested
= Вложенный кортеж. -
property
= Пара из однобайтового идентификатора и небольшого бинарного объекта (последовательность байт) размером до 253 байт. -
datetime_utc
= Дата/время в форме 32-битного беззнакового целого числа секунд с начала Unix-эпохи 1970-01-01 00:00:00 +0000 (UTC). -
datetime_h100
= Дата/время в форме фиксированной точки 32-dot-32 унифицированной с "Positive Hiper100re". -
decimal
= 64-битное дробное в форме плавающей точки с десятичной экспонентой. -
bin96
..bin512
= Бинарный блоки размером 96/128/160/192/224/256/320/384/512 бит. -
app_reserved_64
иapp_reserved_128
= зарезервированные за приложением типы размером 64 и 128 бит.
Предусматривается вложенность кортежей, но в угоду легковесности и производительности не предлагает для этого элегантного автоматизма. В целом, для представления вложенных структур возможны два подхода:
-
Проекция, проще говоря, расширение имен: делаем
{ "ФИО.Имя": "Иван", "ФИО.Фамилия": "Петров" }
вместо{ "ФИО": { "Имя": "Иван", "Фамилия": "Петров" } }
-
Вложенная сериализация, когда сначала отдельно формируется кортеж с
"ФИО"
, а затем целиком вкладывается в родительский кортеж.
Токены являются компактными, удобными для машины идентификаторами полей и включают всю необходимую информацию для организации доступа к ним. Токены могут быть получены из "Справочника схемы", в том числе по символическим именам полей, либо созданы вручную при наличии необходимой информации.
Каждый токен содержит тип данных и признак "заметности пустоты", позволяющий управлять поведением подставляя нулевые значение при чтении отсутствующих loose-полей, а также эмулировать отсутствие preplaced-полей (см далее раздел "Обязательные и опциональные поля").
Кроме общих обязательных атрибутов, токены содержат разную информацию в зависимости от вида поля. Так токены preplaced-полей содержат смещение для непосредственно доступа к полю внутри кортежа. А токены loose-полей содержат тэг для поиска поля в индексе и признак коллекции (флажок повторяемости поля).
С точки зрения C++
токены являются экземплярами классов с необходимым
набором методов. При этом следует различать динамические токены и
статические токен-классы:
-
Динамические токены хранят собственные не-статические значения всех атрибутов в каждом экземпляре класса
fptu::token
. Разные экземпляры этого класса могут соответствовать разным полям. Соответственно, динамические токены можно присваивать, получать от справочника схемы и конструировать при выполнении программы.Доступ к полям через такие токены унифицирован, но реализуется функциями с несколькими условными ветвлениями внутри.
-
Статические токен-классы не хранят какие-либо значения, а являются "пустотелыми" классами, состоящими только из inline-методов, которые возвращают константные значения одинаковые для всех экземпляров. Каждый статический токен-класс и все его экземпляры всегда соответствует только одному полю. Соответственно, статические токен-классы нельзя присваивать, а определять можно только в исходном коде и/или во время компиляции программы посредством макроса
FPTU_TOKEN
или шаблона fptu::token_static<>.Доступ к полям через статические токен-классы внешне выглядит также как и для динамических токенов. Однако, в случае статических токен-классов, libfptu предоставляет шаблонные inline-методы, что позволяет компилятору сгенерировать оптимальный код без лишних проверок и условных переходов, в том числе с непосредственным доступом к данным для preplaced-полей.
Кроме статических и динамических токенов доступны шаблоны
cast_typecheck<TOKEN>
, cast_preplaced<TOKEN>
и cast_loose<TOKEN>
позволяющие получить из динамических токенов частично статические, что
также позволяет использовать шаблонную генерацию кода с меньшим
количеством условных ветвлений.
Следует отметить, что динамические и статические токены можно сравнивать, а динамические создать из статических. В целом это позволят выбрать желаемый компромисс между гибкостью и производительность, сочетая фиксирование части схемы на стадии компиляции с динамическим до-определением во время выполнения. При этом рекомендуется использовать следующий поэтапный подход:
-
Формируется внешнее формальное описание схемы.
-
Аналитически формируется список "горячих" полей, для доступа к которым требуется предельная эффективность.
-
На основании списка "горячих" полей, непосредственно в исходном коде, формируются декларация соответствующих структур. Для всех определенных таким образом полей, при помощи макроса
FPTU_TOKEN
генерируются статические токен-классы. Доступ к этим полям производится либо через статические токен-классы, либо посредством получения указателей на поля нативных структур языка C. -
Во время выполнения, на основании загружаемого формального описания схемы, строится внутренний справочник схемы, а ранее сгенерированные статические-токен классы сверяются (сравниваются) с соответствующими токенами полей в справочнике схемы.
Таким образом, используются все преимущества фиксированной схемы и нативной генерации кода, одновременно с верификацией соответствия скомпилированного кода и актуального загруженного описания схемы данных.
В актуальной версии "Позитивных кортежей" справочник схемы фактически является просто словарём токенов доступа и выполняет утилитарные функции:
-
Получение списка полей, их типов и остальной информации: loose или preplaced, признаках повторяемости и заметности пустоты, суммарному размеру preplaced полей и их инициализирующих значений.
-
Трансляцию человеко-читаемых символических имен полей в токены доступа (машинные идентификаторы) и обратно.
-
(TODO) Трансляцию значений enumeration-типов в строковые значения и обратно при экспорте/импорте данных в JSON и YAML.
"Позитивные кортежи" не предлагают какого-либо языка для описания схемы или формата хранения (сериализации) справочника. Справочник схемы существует только во время выполнения программы, создается и наполняется пользователем (программистом) также по время выполнения программы.
Достаточно важный аспект, который лучше проговорить отдельно. В "Позитивных кортежах" в явном виде поля не делятся на обязательные и опциональные. Вместо этого libfptu предлагает не замечать отсутствие loose-полей, либо наоборот эмулировать отсутствие preplaced-полей, которые физически всегда присутствуют. Такой подход не создает протекающих абстракций и позволяет работать с полями разных видов единообразно, сконцентрировавшись на компромиссе между скоростью доступа и занимаемым местом.
Признак "заметности пустоты" является частью токена и упрощенно действует следующим образом:
-
Если
discernible_null == FALSE
то libfptu будет при чтении скрывать отсутствие loose-полей, подставляя естественные нулевые значения. Таким образом, внешне устраняется различие между отсутствием поля и его нулевым значением. Другими словами, у таких полей нет NIL-значений, мы всегда можем прочитать их, не получив исключенияfptu::field_absent
. -
Когда
discernible_null == TRUE
мы будем "видеть" физическое отсутствие loose-полей, а для preplaced-полей, которые физически всегда присутствуют, libfptu будет эмулировать их отсутствие. При этом для preplaced-полей, для типов данных фиксированного размера, одно из возможных значений типа резервируется для обозначения "пустоты":Тип данных Зарезервированное DENIL значение i8, int8_t, boolean -128 (INT8_MIN) u8, uint8_t, bin8 0 i16, int16_t, enumeration -32768 (INT16_MIN) u16, uint16_t, bin16 0 i32, int32_t -2147483648 (INT32_MIN) u32, uint32_t, bin32 0 f32, float -QNaN (все единицы) t32, datetime_uts 1970-01-01 (машинный 0) i64, int64_t -9223372036854775808 (INT64_MIN) u64, bin64 0 f64, double -QNaN (все единицы) d64, decimal64_t -QNaN (все единицы) t64, datetime_h100, timestamp 1970-01-01 (машинный 0) bin96..bin512 0 (все нули) mac, ip, ipnet 0 (все нули) Встречая соответствующее значение в preplaced-поле libfptu будет эмулировать его отсутствие: метод
is_present()
будет возвращатьFALSE
, а при чтении будет вброшено исключениеfptu::field_absent
.
Полное описание признака discernible_null
можно найти
в описании метода token_operations<>::is_discernible_null()
.
Коллекция в "Позитивных кортежах" - это неупорядоченный набор
нескольких экземпляров поля. Проще говоря, чтобы получить коллекцию
достаточно несколько добавить в кортеж одно и тоже поле. В свою очередь,
в справочнике схеме и токене, такое поле должно быть помечено как
"повторяемое", аналогично полям с атрибутом repeated
в Protocol
Buffers).
Только loose-поля могут образовывать коллекции, так как preplaced-полей в кортеже всегда по одному экземпляру, для которых резервируется место и фиксируется смещение. Однако, preplaced-полем может быть массив фиксированного размера или плоская структура.
libfptu не переставляет элементы коллекций после их добавления, поэтому их физический порядок детерминирован. Тем не менее, порядок определяется всей историей операций, а не только порядком добавления элементов в конкретную коллекцию. Поэтому настоятельно рекомендуется считать, что коллекции не упорядоченны. Иначе говоря, считать что порядок итерирования и расположения в памяти элементов коллекций не определены, и не зависят от порядка их создания.
В libpftu есть два вида итераторов: итераторы коллекций, итераторы присутствующих в кортеже полей. Оба вида итераторов имеют сходные свойства: не гарантируется какой-либо порядок для итерируемых сущностей, а сами итераторы однонаправленные (Forward iterator category) и хрупкие (инвалидируются при изменении кортежа). Эти свойства и причины нуждаются в пояснении:
-
Неупорядоченность. При итерировании присутствующих полей и элементов коллекций не гарантируется какой-либо порядок. Отсутствие таких гарантий позволяет не жертвовать эффективностью операций изменения данных и снизить стоимость итерирования. При этом порядок элементов детерминирован и в большинстве случаев сначала будут проитерированы элементы добавленные последними. Однако, порядок определяется всей историей операций, а не только порядком добавления.
-
Хрупкость или Инвалидация при изменении кортежа. Любое изменение кортежа, иногда даже удаление поля, может привести к перераспределению места внутри кортежа или к выделению нового буфера. В этом случае инвалидируются все связанные с кортежем итераторы. Поэтому, ради простоты и надежности, рекомендуется считать, что итераторы всегда инвалидируются при любом изменении кортежа. В чувствительных случаях вы можете погрузиться в детали:
-
итераторы НЕ инвалидируются:
- При удалении loose-полей.
- При изменении значений полей фиксированной длины, вне зависимости от типа поля loose/prelaced.
-
в результате других изменений итераторы могут стать невалидными:
- Удаление или обнуление значения preplaced-поля переменной длины (например строки) приведет к образованию зазора внутри данных кортежа. Сохранение информации об этом зазоре может потребовать отдельной позиции в индексе дескрипторов в начале кортежа. В такой ситуации libfptu придется либо вбросить исключение, либо перераспределить место используемое кортежем, что придёт к инвалидации итераторов.
- Добавление loose-поля, либо увеличение размера данных любого поля переменной длины, может приводить к перераспределению используемого кортежем места или к пере-сортировке дескрипторов в индексе. Что влечет инвалидацию итераторов.
- Если добавление элементов коллекций, новых полей или изменение изменений существующих не приводят к инвалидации итераторов, то это изменения могут быть как заметны через ранее полученные итераторы, так и нет.
-
TBD
TBD
TBD
TBD
TBD
TBD
TBD
TBD
TBD
TBD
TBD
С целью расширения этих возможностей в актуальную версию libfptu была импортирована часть инфраструктуры управления разделяемыми буфера проекта 1Hippeus.
Постоянная проверка корректности данных слишком дорога и как-правило избыточна. С другой стороны, любые нарушениях в десериализуемых данных не должны приводить к авариям.
Поэтому в libfptu эксплуатируется следующий принцип:
-
Доступны функции верификации сериализованной и изменяемой форм кортежа, которые вы используете по своему усмотрению.
-
В угоду производительности, основные функции выполняют только минимальный контроль корректности аргументов и предоставляемых данных. Поэтому при мусорных (не валидных) данных их поведение не определено.
-
Гарантируется, что прошедшие проверку данные не вызовут нарушений при дальнейшей работе с ними.
Физически кортеж представляет собой линейный участок памяти, в начале которого расположен компактный индекс для быстрого доступа к опциональным полям. Сразу за индексом располагаются полезные данные, т.е. собственно значения полей кортежа. Таким образом, как сериализация, так десериализация кортежа равноценны однократному чтению/записи/копированию линейного участка памяти.
Формат представления кортежей ориентирован на машину. Все данные в бинарном машинном виде, порядок байт строго нативный (определяется архитектурой или режимом работы CPU):
-
Сначала идет "заголовок" кортежа, в котором указано количество loose-полей (размер индекса) и служебные признаки.
-
Затем следует индекс loose-полей, представляющий собой массив из 32-битных дескрипторов присутствующих в кортеже loose-полей. Каждый элемент-дескриптор в индексе содержит идентификатор поля, тип данных и смещение к ним относительно дескриптора.
-
После индекса следуют preplaced-поля, строго согласно схеме, которой соответствует кортеж.
-
За индексом после preplaced-полей следуют данные loose-полей и prepaced-полей переменного размера. При этом в данных допустимы зазоры, как они образовались в ходе формирования кортежа при изменении значений и удалении полей, если пользователь счет ненужным запросить дефрагментацию.
-
Каждый loose-дескриптор и связанные с ним данные выровнены на 4х-байтовую границу. Выравнивание preplaced-полей определяется схемой.
Для коротких типов данных, которые помещается в 16 бит, значения хранятся непосредственно в дескрипторе вместо смещения.
Для всех полей переменной длины (строк, вложенных кортежей и т.д.), в первом 32-битном слове кодируется их размер, но способ кодировки зависит от типа данных.
Строки хранятся только в кодировке UTF-8 с явным указанием длины.
Терминирующий '\0'
не используется, но допустим внутри строк.
Формат первого слова для вложенных кортежей и корневого кортежа полностью совпадает с небольшой оговоркой:
-
В самостоятельном виде пустой кортеж может быть представлен как
ноль байт
(пустой строкой байт), так и минимальным заголовком, в котором указаноноль элементов
. -
Вложенный кортеж является полем, поэтому при присутствии поля всегда обязан иметь заголовок с информацией о своем нулевом размере.
Сериализованная форма кортежа libfptu - это линейный участок памяти, который одновременно является массивом 32-битных ячеек. В начале располагается информация о количестве полей/колонок и общем размере кортежа. Далее следует список дескрипторов. Затем располагаются preplaced-поля, а за ними значения полей, включая значения preplaced-полей переменного размера.
Создание и наполнение кортежа происходит в слегка отличающейся "изменяемой" форме - это также линейный участок памяти, но выделенный с учетом ожидаемого размера кортежа и дополнительного места для нескольких служебных счетчиков. Проще говоря, изменяемая форма кортежа является "обложкой" создаваемого сериализованного кортежа, но с резервирования дополнительного места:
-
изменяемая форма кортежа живет в буфере, который выделяется в расчете на ожидаемый размер (как по количеству элементов, так и по их данным);
-
внутри выделенного буфера располагаются служебные счетчики, а также растет сериализованная форма кортежа;
-
получение сериализованной формы из изменяемой сводится к формированию информации о текущем размере кортежа и возврате указателя на его начало;
-
получение изменяемой формы из сериализуемой сводится к копированию кортежа внутрь выделенного буфера, размер которого должен включать запас на служебные счетчики и добавляемые данные.
buffer of sufficient size |<=======================================================>| | | | head pivot tail | | <-----~~~~~~~~~|~~~~~~~~~~~~~~~~~~----------------> | | descriptors|payload | | #_D_C_B_A_aaa_bb_cccccc_dddd | | |<========================>| linear uint32_t sequence for serialization
Остальная информация доступна в описании функций в заголовочных файлах API и остальном исходном коде.
$ objdump -f -h -j .text libfptu.so
libfptu.so: file format elf64-x86-64
architecture: i386:x86-64, flags 0x00000150:
HAS_SYMS, DYNAMIC, D_PAGED
start address 0x00000000000168e0
Sections:
Idx Name Size VMA LMA File off Algn
13 .text 0002880e 00000000000168e0 00000000000168e0 000168e0 2**4
CONTENTS, ALLOC, LOAD, READONLY, CODE
$ ldd libfptu.so
linux-vdso.so.1 (0x00007fffb5b3d000)
libstdc++.so.6 => /usr/lib/x86_64-linux-gnu/libstdc++.so.6 (0x00007fdbfcd29000)
libm.so.6 => /lib/x86_64-linux-gnu/libm.so.6 (0x00007fdbfc98b000)
libgcc_s.so.1 => /lib/x86_64-linux-gnu/libgcc_s.so.1 (0x00007fdbfc773000)
libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007fdbfc382000)
/lib64/ld-linux-x86-64.so.2 (0x00007fdbfd34d000)