Fast Positive Tuples, aka "Позитивные Кортежи" by Positive Technologies.
The kind of lightweight linearized tuples, which are extremely handy to machining, including cases with shared memory.
Легковесное линейное представление небольших JSON-подобных структур в экстремально удобной для машины форме, в том числе при размещении в разделяемой памяти.
The Future will Positive. Всё будет хорошо.
English version by Google and by Yandex.
libfptu или "Позитивные Кортежи" - это формат обмена данными и библиотека для представления и экстремально эффективной обработки машиной небольших JSON-подобных структур, в том числе при их размещении в разделяемой памяти.
В libfptu нет встроенной схемы данных. Поэтому у полей нет имен, они идентифицируются по коротким целочисленным тегам. Это очень быстро и достаточно компактно. Тем не менее, поддержка вложенных кортежей позволяет легко хранить пары имя-значение.
Целью дизайна libfptu была предельно быстрая машинная обработка небольших порций данных (до 100 элементов, до 10 килобайт) на современных процессорах. При этом совместное использование (чтение) кортежей в разделяемой памяти является одним из основных и целеполагающих сценариев (проект 1Hippeus).
-
Удобство для машины и легковесность. Объем кода минимален, а внутреннее устройство просто и прозрачно.
-
Нужно чуть больше места. Мы не сжимаем данные, а храним их в нативном машинном представлении с выравниванием. Поэтому в libfptu для каждого поля требуется примерно на 3-4 байта больше.
Тем не менее, следует аккуратно интерпретировать эти цифры. Если у вас много 64-битных целочисленных полей с близкими к нулю значениями, то может оказаться так, что представление в libfptu потребует в 12 раз больше памяти в сравнении с MessagePack (1 байт в MessagePack, против 12 байт в libfptu).
- Очень быстрый доступ. У нас есть простейший индекс. Поэтому поиск полей и доступ к данным в libfptu очень быстрый.
Для эффективного доступа к полям кортежа достаточно его "сырого" представления "как есть" в линейном участке памяти, без какой-либо подготовки, без каких-либо преобразований, изменений и манипуляций. Получения поля из кортежа сводится к поиску его дескриптора в заголовке. Что равнозначно чтению одной кэш-линии на первые 15 полей и далее на каждые 16 последующих.
- Очень дешевая сериализация. Мы формируем и растим кортеж как линейную последовательность байт, просто дозаписью данных. Поэтому сериализация в "Позитивные Кортежи" магически быстрая и дешевая.
Заполнение кортежа происходит без лишних операций, просто однократным копированием данных в заранее выделенный буфер достаточного размера. При этом сериализованное представление всегда готово, доступ к нему сводится к получению указателя и размера.
- Формируемые кортежи можно изменять. Можно удалять и перезаписывать поля, в том числе с изменением размера.
При этом в линейном представлении могут образовываться неиспользуемые фрагменты, а у вас появляется выбор: пожертвовать местом или использовать процедуру дефрагментации. При этом выполняется перемещение полезных данных с вытеснением неиспользуемых зазоров. Соответственно, в худшем случае, дефрагментация не дороже однократного копирования содержимого кортежа.
Однако, "Позитивные Кортежи" не являются серебряной пулей и вероятно не подойдут, если:
- В структурах более 1000 полей;
- Размер одной структуры более 250 килобайт;
- Минимизация объема важнее скорости доступа и затрат на сериализацию.
libfptu поддерживает кортежи размером до 256 килобайт и до 16 тысяч полей. Поля идентифицируются одновременно одним из 1000 тегов и типом данных. Набор типов зафиксирован и включает все распространенные нативные (машинные) типы, а также null (пусто), C-строки, дата/время, произвольные последовательности байт и массивы.
Физически кортеж представляет собой линейный участок памяти, в начале которого расположены дескрипторы полей/колонок, в форме удобной для быстрого поиска полей и доступа к их данным. Таким образом, как сериализация, так десериализация кортежа равноценны однократному чтению/записи/копированию линейного участка памяти.
Выборка поля из кортежа сводится к поиску соответствующего элемента в линейном массиве дескрипторов, а далее обращение к данным посредством хранимого в дескрипторе смещения.
Текущая реализация ориентирована на небольшое число полей, когда их дескрипторы помещаются в несколько кэш-линий, а двоичный поиск не дает выигрыша в сравнении с линейным. Для эффективной поддержки больших кортежей предусмотрено добавление сортировки дескрипторов полей, а также прямой доступ по их тегам в качестве индексов.
Добавление поля в кортеж сводится к дозаписи дескриптора в начало кортежа и дозаписи данных в конец. При этом резервирование места позволяет обойтись без перемещения уже размещенных в кортеже элементов.
Удаление полей, а также обновление значений полей вариативной длины (строки, бинарные строки, массивы, вложенные кортежи), может приводить к образованию внутри кортежа неиспользуемых участков, которые ликвидируются дефрагментацией. Такая дефрагментация не дороже однократного копирования кортежа и не является обязательной.
"Позитивные кортежи" состоят из типизированных полей. Каждое поле идентифицируется тэгом (номером колонки) и типом хранимых данных. Могут быть несколько полей с одинаковым тэгом, но разными типами, при этом они различаются.
Поля всегда опциональны, могут отсутствовать, а при необходимости любое
поле может многократно повторяться. Поля можно итерировать, независимо
обновлять, удалять и добавлять вновь. Проще говоря, в libfptu также
поддерживаются неупорядоченные коллекции из однотипных элементов
(аналогично repeated в Protocol Buffers).
Набор базовых типов фиксирован: null, int 32/64, float point 32/64, c-string, date/time, unsigned int 16/32/64, бинарные блоки 96/128/160/256 бит, бинарные строки, вложенные кортежи, одномерные массивы (всех базовых типов кроме null и массивов).
Текущая реализация допускает вложенность кортежей, но в угоду легковесности и производительности не предлагает для этого элегантного автоматизма. В целом, для представления вложенных структур возможны два подхода:
-
Расширение имен: делаем
{ "ФИО.Имя": "Иван", "ФИО.Фамилия": "Петров" }вместо{ "ФИО": { "Имя": "Иван", "Фамилия": "Петров" } } -
Вложенная сериализация, когда сначала отдельно сериализуется
"ФИО", а затем целиком вкладывается в родительский кортеж.
Для хранения многомерных массивов доступны три варианта:
- Коллекции, если просто добавить одномерный массив несколько раз;
- Вложенные кортежи;
- Бинарные строки.
Можно проитерировать все поля в кортеже, это быстро и дешево:
- Можно итерировать с фильтрацией по тегу/номеру и битовой маске типов;
- При итерации у каждого поля можно спросить тэг/номер, тип и значение;
- Итератор остается валидным до разрушения или до компактификации кортежа;
- При итерации любое количество полей можно как удалить, так и добавить;
- Добавленные в процессе итерации поля можно как увидеть через итератор, так и не увидеть.
Однако, следует считать, что порядок полей при итерации не определен и никак не связан с их порядком добавления или удаления. В частности, поэтому нет (и не будет) итерации в обратном порядке.
Постоянная проверка корректности данных слишком дорога и как-правило избыточна. С другой стороны, любые нарушениях в десериализуемых данных не должны приводить к авариям.
Поэтому в libfptu эксплуатируется следующий принцип:
-
Доступны функции верификации сериализованной и изменяемой форм кортежа, которые вы используете по своему усмотрению.
-
В угоду производительности, основные функции выполняют только минимальный контроль корректности аргументов и предоставляемых данных. Поэтому при мусорных (не валидных) данных их поведение не определено.
-
Гарантируется, что прошедшие проверку данные не вызовут нарушений при дальнейшей работе с ними.
Формат представления кортежей ориентирован на машину. Все данные в бинарном машинном виде, порядок байт строго нативный (определяется архитектурой или режимом работы CPU):
- сначала идет "заголовок", представляющий собой массив из 32-битных дескрипторов полей;
- за заголовком следуют данные полей/колонок;
- каждый элемент-дескриптор в массиве-заголовке содержит идентификатор колонки/поля, тип данных и смещение к ним относительно дескриптора;
- каждый дескриптор и связанные с ним данные выровнены на 4х-байтовую границу.
Для полей типа fptu_null смещение внутри дескриптора не используется,
но устанавливается в ненулевое значение. Этим исключается равенство
дескриптора нулю.
Для полей типа fptu_uint16 смещение используется для хранения
непосредственно самого значения поля.
Строки хранятся только в UTF-8 с терминирующим '\0' без явной длины.
Это позволяет иметь классический "C" API и экономить на хранении длины,
а в остальных случаях использовать бинарные строки.
Для всех полей переменной длины (массивов, бинарных строк, вложенных кортежей), за исключением C-строк, в первом 32-битном слове данных хранится их размер. Причем в первом полуслове хранится брутто-размер поля в 32-битных словах, а во втором в зависимости от типа:
- точный размер для бинарных строк;
- количество элементов для массивов и кортежей;
- дополнительные признаки для кортежей;
Массивы хранятся как линейная последовательность образующих их
элементов. При этом их элементы выравниваются на 4-байтную границу,
кроме строк и uint16. Строки в массивах располагаются в стык, а
uint16_t просто последовательно.
Формат первого слова для вложенных кортежей и корневого кортежа полностью совпадает с небольшой оговоркой:
- В самостоятельном виде пустой кортеж может быть представлен
как
ноль байт(пустой строкой байт), так и минимальным заголовком, в котором указаноноль элементов. - Вложенный кортеж является полем, поэтому всегда обязан иметь заголовок c информацией о своем нулевом размере.
Сериализованная форма кортежа libfptu - это линейный участок памяти, который одновременно является массивом 32-битных ячеек. В начале располагается информация о количестве полей/колонок и общем размере кортежа. Далее следует список дескрипторов, а за ним значения полей.
Создание и наполнение кортежа происходит в слегка отличающейся "изменяемой" форме - это также линейный участок памяти, но выделенный с учетом ожидаемого размера кортежа и дополнительного места для нескольких служебных счетчиков. Проще говоря, изменяемая форма кортежа является "обложкой" создаваемого сериализованного кортежа, но с резервирования дополнительного места:
-
изменяемая форма кортежа живет в буфере, который выделяется в расчете на ожидаемый размер (как по количеству элементов, так и по их данным);
-
внутри выделенного буфера располагаются служебные счетчики, а также растет сериализованная форма кортежа;
-
получение сериализованной формы из изменяемой сводится к формированию информации о текущем размере кортежа и возврате указателя на его начало;
-
получение изменяемой формы из сериализуемой сводится к копированию кортежа внутрь выделенного буфера, размер которого должен включать запас на служебные счетчики и добавляемые данные.
buffer of sufficient size |<=======================================================>| | | | head pivot tail | | <-----~~~~~~~~~|~~~~~~~~~~~~~~~~~~----------------> | | descriptors|payload | | #_D_C_B_A_aaa_bb_cccccc_dddd | | |<========================>| linear uint32_t sequence for serialization
fptu_bits = 16 // ширина счетчиков в битах
fptu_unit_size = 4 // размер одного юнита в байтах
fptu_max_tuple_bytes = 262140 // максимальный суммарный размер сериализованного представления кортежа
fptu_max_cols = 1022 // максимальный тег-номер поля/колонки
fptu_max_fields = 16383 // максимальное кол-во полей/колонок в одном кортеже
fptu_max_field_bytes = 65535 // максимальный размер поля/колонки
fptu_max_opaque_bytes = 65531 // максимальный размер произвольной последовательности байт
fptu_max_array = 2047 // максимальное кол-во элементов в массиве
fptu_buffer_enought = 327696 // буфер достаточного размера для любого кортежа
fptu_buffer_limit = 524280 // предельный размер для резервирования, превышение которого считается ошибкой
$ 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 0x00003aa0
Sections:
Idx Name Size VMA LMA File off Algn
11 .text 00005dda 00003aa0 00003aa0 00003aa0 2**4
CONTENTS, ALLOC, LOAD, READONLY, CODE
00003aa0 g DF .text 000000a0 Base fptu::hexadecimal[abi:cxx11](void const*, unsigned long)
00003b40 g DF .text 0000013f Base fptu::format[abi:cxx11](char const*, ...)
0000450c g DF .text 00000164 Base fptu_type_name
00004670 g DF .text 00000070 Base std::to_string[abi:cxx11](fptu_error)
00004807 g DF .text 000009d4 Base std::to_string[abi:cxx11](fptu_field const&)
00005355 g DF .text 00000119 Base std::to_string[abi:cxx11](fptu_time const&)
0000546e g DF .text 0000009f Base std::to_string[abi:cxx11](fptu_lge)
0000550d g DF .text 00000129 Base std::to_string[abi:cxx11](fptu_rw const&)
00005636 g DF .text 000000e2 Base std::to_string[abi:cxx11](fptu_ro const&)
00005718 g DF .text 00000022 Base std::to_string[abi:cxx11](fptu_type)
00005c94 g DF .text 00000033 Base fptu_take_noshrink
00005cc7 g DF .text 00000088 Base fptu_lookup
00005d4f g DF .text 0000008d Base fptu_lookup_ro
00005de0 g DF .text 00000047 Base fptu_is_ordered
00005e27 g DF .text 0000000e Base fptu_end_rw
00005e35 g DF .text 0000000d Base fptu_begin_rw
00005e42 g DF .text 0000002e Base fptu_end_ro
00005e70 g DF .text 0000002b Base fptu_begin_ro
00005e9b g DF .text 0000006a Base fptu_first_ex
00005f05 g DF .text 0000000e Base fptu_next_ex
00005f13 g DF .text 00000066 Base fptu_first
00005f79 g DF .text 0000000e Base fptu_next
00005f87 g DF .text 0000004b Base fptu_cmp_binary
00005fd2 g DF .text 000004a9 Base fptu_cmp_tuples
00006730 g DF .text 0000008f Base fptu_is_under_valgrind
000067bf g DF .text 0000007c Base fptu_insert_nested
0000683b g DF .text 0000008b Base fptu_insert_opaque
000068c6 g DF .text 0000000a Base fptu_insert_opaque_iov
000068d0 g DF .text 00000076 Base fptu_insert_string
00006946 g DF .text 00000066 Base fptu_insert_256
000069ac g DF .text 0000005c Base fptu_insert_160
00006a08 g DF .text 00000054 Base fptu_insert_128
00006a5c g DF .text 00000054 Base fptu_insert_96
00006ab0 g DF .text 0000004a Base fptu_insert_fp64
00006afa g DF .text 00000048 Base fptu_insert_fp32
00006b42 g DF .text 00000048 Base fptu_insert_datetime
00006b8a g DF .text 00000048 Base fptu_insert_uint64
00006bd2 g DF .text 00000048 Base fptu_insert_int64
00006c1a g DF .text 00000047 Base fptu_insert_uint32
00006c61 g DF .text 00000047 Base fptu_insert_int32
00006ca8 g DF .text 00000041 Base fptu_insert_uint16
00006ce9 g DF .text 000000fd Base fptu_erase_field
00006de6 g DF .text 000000cc Base fptu_erase
00006eb2 g DF .text 00000078 Base fptu_update_nested
00006f2a g DF .text 00000087 Base fptu_update_opaque
00006fb1 g DF .text 0000000a Base fptu_update_opaque_iov
00006fbb g DF .text 00000072 Base fptu_update_string
0000702d g DF .text 00000062 Base fptu_update_256
0000708f g DF .text 00000058 Base fptu_update_160
000070e7 g DF .text 00000050 Base fptu_update_128
00007137 g DF .text 00000050 Base fptu_update_96
00007187 g DF .text 00000042 Base fptu_update_fp64
000071c9 g DF .text 00000040 Base fptu_update_fp32
00007209 g DF .text 00000040 Base fptu_update_datetime
00007249 g DF .text 00000040 Base fptu_update_uint64
00007289 g DF .text 00000040 Base fptu_update_int64
000072c9 g DF .text 0000003f Base fptu_update_uint32
00007308 g DF .text 0000003f Base fptu_update_int32
00007347 g DF .text 0000003d Base fptu_update_uint16
00007384 g DF .text 0000007c Base fptu_upsert_nested
00007400 g DF .text 0000009e Base fptu_upsert_opaque
0000749e g DF .text 0000000a Base fptu_upsert_opaque_iov
000074a8 g DF .text 00000076 Base fptu_upsert_string
0000751e g DF .text 00000066 Base fptu_upsert_256
00007584 g DF .text 0000005c Base fptu_upsert_160
000075e0 g DF .text 00000054 Base fptu_upsert_128
00007634 g DF .text 00000054 Base fptu_upsert_96
00007688 g DF .text 0000004a Base fptu_upsert_fp64
000076d2 g DF .text 00000048 Base fptu_upsert_fp32
0000771a g DF .text 00000048 Base fptu_upsert_datetime
00007762 g DF .text 00000048 Base fptu_upsert_uint64
000077aa g DF .text 00000048 Base fptu_upsert_int64
000077f2 g DF .text 00000047 Base fptu_upsert_uint32
00007839 g DF .text 00000047 Base fptu_upsert_int32
00007880 g DF .text 00000041 Base fptu_upsert_uint16
000078c1 g DF .text 00000027 Base fptu_upsert_null
000078e8 g DF .text 0000019a Base fptu_check
00007a82 g DF .text 00000125 Base fptu_check_ro
00007ba7 g DF .text 0000000d Base fptu_junkspace
00007bb4 g DF .text 00000010 Base fptu_space4data
00007bc4 g DF .text 00000016 Base fptu_space4items
00007bda g DF .text 0000003d Base fptu_clear
00007c17 g DF .text 0000004f Base fptu_init
00007c66 g DF .text 0000010a Base fptu_fetch
00007d70 g DF .text 00000033 Base fptu_space
00007da3 g DF .text 0000004d Base fptu_alloc
00007df0 g DF .text 00000044 Base fptu_get_buffer_size
00007e34 g DF .text 000000ad Base fptu_check_and_get_buffer_size
00008780 g DF .text 00000011 Base fptu_time::fractional2ms(unsigned long)
000087a0 g DF .text 00000028 Base fptu_time::ms2fractional(unsigned long)
000087d0 g DF .text 00000011 Base fptu_time::fractional2us(unsigned long)
000087f0 g DF .text 00000021 Base fptu_time::us2fractional(unsigned long)
00008820 g DF .text 00000011 Base fptu_time::fractional2ns(unsigned long)
00008840 g DF .text 00000028 Base fptu_time::ns2fractional(unsigned long)
00008870 g DF .text 0000005f Base fptu_now_coarse
000088d0 g DF .text 0000005f Base fptu_now_fine
00008930 g DF .text 0000007a Base fptu_now
000089b0 g DF .text 000000bf Base fptu_tags
00008a70 g DF .text 0000008f Base fptu_field_count_ro_ex
00008aff g DF .text 00000078 Base fptu_field_count_ex
00008b77 g DF .text 00000075 Base fptu_field_count_ro
00008bec g DF .text 00000063 Base fptu_field_count
00008c4f g DF .text 00000040 Base fptu_cmp_fields
00008c8f g DF .text 00000049 Base fptu_cmp_opaque
00008cd8 g DF .text 0000000a Base fptu_cmp_opaque_iov
00008ce2 g DF .text 00000066 Base fptu_cmp_256
00008d48 g DF .text 00000066 Base fptu_cmp_160
00008dae g DF .text 00000066 Base fptu_cmp_128
00008e14 g DF .text 00000066 Base fptu_cmp_96
00008e7a g DF .text 00000035 Base fptu_get_nested
00008eaf g DF .text 00000035 Base fptu_get_opaque
00008ee4 g DF .text 00000066 Base fptu_get_fp
00008f4a g DF .text 0000006b Base fptu_get_uint
00008fb5 g DF .text 00000062 Base fptu_get_sint
00009017 g DF .text 00000034 Base fptu_get_cstr
0000904b g DF .text 00000034 Base fptu_get_256
0000907f g DF .text 00000034 Base fptu_get_160
000090b3 g DF .text 00000034 Base fptu_get_128
000090e7 g DF .text 00000034 Base fptu_get_96
0000911b g DF .text 00000035 Base fptu_get_datetime
00009150 g DF .text 00000034 Base fptu_get_fp32
00009184 g DF .text 00000034 Base fptu_get_fp64
000091b8 g DF .text 00000034 Base fptu_get_uint64
000091ec g DF .text 00000034 Base fptu_get_int64
00009220 g DF .text 00000034 Base fptu_get_uint32
00009254 g DF .text 00000034 Base fptu_get_int32
00009288 g DF .text 00000034 Base fptu_get_uint16
000092c0 g DF .text 00000024 Base fptu_field_column
000092f0 g DF .text 00000024 Base fptu_field_type
00009320 g DF .text 0000003b Base fptu_field_nested
00009360 g DF .text 0000003b Base fptu_field_opaque
000093a0 g DF .text 00000039 Base fptu_field_256
000093e0 g DF .text 00000039 Base fptu_field_160
00009420 g DF .text 00000039 Base fptu_field_128
00009460 g DF .text 00000039 Base fptu_field_96
000094a0 g DF .text 00000039 Base fptu_field_cstr
000094e0 g DF .text 00000039 Base fptu_field_datetime
00009520 g DF .text 0000003f Base fptu_field_fp32
00009560 g DF .text 0000003f Base fptu_field_fp64
000095a0 g DF .text 0000002f Base fptu_field_uint64
000095d0 g DF .text 00000041 Base fptu_field_int64
00009620 g DF .text 0000003c Base fptu_field_uint32
00009660 g DF .text 0000002f Base fptu_field_int32
00009690 g DF .text 0000003c Base fptu_field_uint16
000096d0 g DF .text 000001aa Base fptu_shrink