Home

Awesome

<!-- Required extensions: pymdownx.betterem, pymdownx.tilde, pymdownx.emoji, pymdownx.tasklist, pymdownx.superfences -->

libfptu

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.

License GithubCI AppveyorCI CircleCI CirrusCI Coverity Scan

The Future will (be) Positive. Всё будет хорошо.

Кратко

"Позитивные Кортежи" - это простой формат представления небольших структур данных в линейном, удобном для машины виде. Библиотека libfptu реализует поддержку формата "Позитивных кортежей", предоставляя интерфейс C++14 и выше.

Можно сказать, что libfptu предлагает гибкость JSON, скорость нативных структур языка C с возможностями boost::optional и boost::variant. В актуальной версии libfptu появилась поддержка схемы данных и предварительно размещенных полей (aka preplaced) для привязки к нативным структурам языка C, а также возможность размещения и совместного использования (чтения) кортежей в разделяемой памяти.

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

Содержание

Отличия от MessagePack, Protocol Buffers, BJSON

1. Легковесность и удобство для машины. Ничего лишнего. Объём кода минимален, а внутренняя структура линейна и проста.

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

2. Непосредственная (де)сериализация. Кортеж формируется в виде линейной последовательности байт, к которой просто дописываются данные. Поэтому (де)сериализация в "Позитивные Кортежи" магически быстрая.

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

3. Очень быстрый доступ. libfptu позволяет сочетать скорость прямого доступа к полям фиксированных структур и подход разреженных множеств с эффективным поиском в индексе.

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

4. Изменения данных дешевы. В отличии от традиционных кортежей, поля можно также добавлять и удалять.

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

5. Немного объёмнее чем MessagePack. Данные хранятся в нативном машинном представлении, без сжатия. Поэтому для каждого поля может потребоваться на 3-4 байта больше.

Тем не менее, следует аккуратно интерпретировать эти цифры. В предельном случае, когда в данных много 64-битных целочисленных полей с близкими к нулю значениями, представление в libfptu может потребовать до 12 раз больше памяти в сравнении с MessagePack (1 байт в MessagePack, против 12 байт в libfptu).

Однако, "Позитивные Кортежи" не являются серебряной пулей и не подойдут для случаев:

Обзор

"Позитивные кортежи" ориентированы на эффективную машинную обработку и компактное представление структурно простых данных. Поэтому:

Размер кортежей ограничен 250 килобайтами и 8 тысячами экземпляров полей. Поля внутри кортежей строго типизированы и идентифицируются легковесными токенами, которые используются для доступа к полям через API. Можно сказать, что токены являются компактными именами полей в удобной для машины форме. В свою очередь, справочник схемы обеспечивает трансляцию имен полей в токены.

Поля предлагаются двух видов: предварительно размещенные (preplaсed) и свободные (loose). Основное отличие между ними в разных компромиссах между скоростью доступа и расходуемым местом. Доступ к полям производится единообразно, вне зависимости от вида поля.

Preplaced Fields

Предварительно размещенные или preplaced-поля аналогичны полям в структурах языка C, физически всегда присутствуют и однозначно определяются схемой.

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

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

Накладные расходы доступа к preplaced-полям могут быть сведены к нулю посредством генерации кода привязанного к схеме данных, которая полностью или частично фиксируется. Технически это сводится к использованию статических токен-классов, при использовании которых компилятор способен сгенерировать inline-код непосредственного доступа к данным.

При необходимости libfptu может эмулировать отсутствие preplaced-полей. Для этого, в зависимости от типа данных, одно из возможных значений поля резервируется для обозначения логической "пустоты". Например, для целочисленных типов со знаком в качестве таких DENIL-значению (designated NIL) используется крайнее отрицательное значение (INT_MIN).

Loose Fields

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

При необходимости loose-поля могут многократно повторяться в кортеже, образую таким образом неупорядоченные итерируемые коллекции, подобно repeated fields в Protocol Buffers. Для этого поле должно быть определено в схеме как "коллекция".

Для поиска loose-полей в индексе libfptu использует как последовательное сканирование с акселерацией SSE2/AVX/AVX2/AVX512, так и сортировку с двоичным поиском.

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

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

Типы данных

Набор типов зафиксирован и включает все распространенные нативные (машинные) типы, а также строки, дата/время, произвольные последовательности байт, IP-адреса, IP-сети, MAC-адреса и дайджесты.

Полный набор типов зафиксирован в определении enum fptu::genus, здесь же стоит упомянуть некоторые особенности:

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

  1. Проекция, проще говоря, расширение имен: делаем { "ФИО.Имя": "Иван", "ФИО.Фамилия": "Петров" } вместо { "ФИО": { "Имя": "Иван", "Фамилия": "Петров" } }

  2. Вложенная сериализация, когда сначала отдельно формируется кортеж с "ФИО", а затем целиком вкладывается в родительский кортеж.

Токены доступа

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

Каждый токен содержит тип данных и признак "заметности пустоты", позволяющий управлять поведением подставляя нулевые значение при чтении отсутствующих loose-полей, а также эмулировать отсутствие preplaced-полей (см далее раздел "Обязательные и опциональные поля").

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

С точки зрения C++ токены являются экземплярами классов с необходимым набором методов. При этом следует различать динамические токены и статические токен-классы:

Кроме статических и динамических токенов доступны шаблоны cast_typecheck<TOKEN>, cast_preplaced<TOKEN> и cast_loose<TOKEN> позволяющие получить из динамических токенов частично статические, что также позволяет использовать шаблонную генерацию кода с меньшим количеством условных ветвлений.

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

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

Справочник схемы

В актуальной версии "Позитивных кортежей" справочник схемы фактически является просто словарём токенов доступа и выполняет утилитарные функции:

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

Обязательные и опциональные поля

Достаточно важный аспект, который лучше проговорить отдельно. В "Позитивных кортежах" в явном виде поля не делятся на обязательные и опциональные. Вместо этого libfptu предлагает не замечать отсутствие loose-полей, либо наоборот эмулировать отсутствие preplaced-полей, которые физически всегда присутствуют. Такой подход не создает протекающих абстракций и позволяет работать с полями разных видов единообразно, сконцентрировавшись на компромиссе между скоростью доступа и занимаемым местом.

Признак "заметности пустоты" является частью токена и упрощенно действует следующим образом:

Полное описание признака discernible_null можно найти в описании метода token_operations<>::is_discernible_null().

Коллекции

Коллекция в "Позитивных кортежах" - это неупорядоченный набор нескольких экземпляров поля. Проще говоря, чтобы получить коллекцию достаточно несколько добавить в кортеж одно и тоже поле. В свою очередь, в справочнике схеме и токене, такое поле должно быть помечено как "повторяемое", аналогично полям с атрибутом repeated в Protocol Buffers).

Только loose-поля могут образовывать коллекции, так как preplaced-полей в кортеже всегда по одному экземпляру, для которых резервируется место и фиксируется смещение. Однако, preplaced-полем может быть массив фиксированного размера или плоская структура.

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

Итераторы

В libpftu есть два вида итераторов: итераторы коллекций, итераторы присутствующих в кортеже полей. Оба вида итераторов имеют сходные свойства: не гарантируется какой-либо порядок для итерируемых сущностей, а сами итераторы однонаправленные (Forward iterator category) и хрупкие (инвалидируются при изменении кортежа). Эти свойства и причины нуждаются в пояснении:

Использование

TBD

Схема данных

TBD

Preplaced или Loose

TBD

NIL или не-NIL

TBD

Операции с насыщением

TBD

Заполнение справочника

TBD

Изменяемая и сериализованная формы

TBD

(Де)Сериализация

TBD

Создание и наполнение

TBD

Чтение полей

TBD

Разделяемая память и взаимодействие между процессами

TBD

С целью расширения этих возможностей в актуальную версию libfptu была импортирована часть инфраструктуры управления разделяемыми буфера проекта 1Hippeus.

Устойчивость к некорректным данным

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

Поэтому в libfptu эксплуатируется следующий принцип:

  1. Доступны функции верификации сериализованной и изменяемой форм кортежа, которые вы используете по своему усмотрению.

  2. В угоду производительности, основные функции выполняют только минимальный контроль корректности аргументов и предоставляемых данных. Поэтому при мусорных (не валидных) данных их поведение не определено.

  3. Гарантируется, что прошедшие проверку данные не вызовут нарушений при дальнейшей работе с ними.

Внутри

Формат

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

Формат представления кортежей ориентирован на машину. Все данные в бинарном машинном виде, порядок байт строго нативный (определяется архитектурой или режимом работы CPU):

Для коротких типов данных, которые помещается в 16 бит, значения хранятся непосредственно в дескрипторе вместо смещения.

Для всех полей переменной длины (строк, вложенных кортежей и т.д.), в первом 32-битном слове кодируется их размер, но способ кодировки зависит от типа данных.

Строки хранятся только в кодировке UTF-8 с явным указанием длины. Терминирующий '\0' не используется, но допустим внутри строк.

Формат первого слова для вложенных кортежей и корневого кортежа полностью совпадает с небольшой оговоркой:

Изменяемая и сериализованная формы

Сериализованная форма кортежа libfptu - это линейный участок памяти, который одновременно является массивом 32-битных ячеек. В начале располагается информация о количестве полей/колонок и общем размере кортежа. Далее следует список дескрипторов. Затем располагаются preplaced-поля, а за ними значения полей, включая значения preplaced-полей переменного размера.

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

Остальная информация доступна в описании функций в заголовочных файлах 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)

This is a mirror of the origin repository that was moved to abf.io because of discriminatory restrictions for Russian Crimea.