Memory Layout

Зачем свой формат в памяти

Традиционные структуры данных (ArrayList в Java, Vec в Rust, list в Python) хранят объекты поштучно — каждый элемент может лежать в произвольном месте кучи. Для аналитики это катастрофа: SIMD-инструкции процессора работают с непрерывными блоками, а кэш-линейка (64 байта) загружает мусор вместо полезных данных.

Apache Arrow определяет формат колоночных данных в памяти — фиксированную раскладку буферов, одинаковую для любого языка и рантайма. Один и тот же массив Arrow можно передать из Python в Rust без сериализации — просто через указатель.

Validity Bitmap

Любой Arrow-массив может содержать NULL-значения. Вместо sentinel-значений (NaN, -1, пустая строка) Arrow использует отдельный validity bitmap — по одному биту на каждый элемент массива.

Правила:

• Бит 1 — значение валидно, бит 0 — NULL
• Биты упакованы least-significant bit first (LSB): бит 0 элемента i находится в байте i / 8, позиция i % 8
• Размер bitmap: ceil(N / 8) байт, дополненный нулями до кратности 8 байт
• Если массив не содержит NULL — bitmap может отсутствовать (null_count = 0)

Проверка NULL для элемента i:

is_valid = (bitmap[i / 8] >> (i % 8)) & 1

Операция O(1) — никакого сканирования, никаких хэш-таблиц. Один сдвиг и одно побитовое AND.

Массивы фиксированной ширины

Простейший случай — примитивные типы: Int32, Int64, Float64, Boolean. Каждый элемент занимает одинаковое количество байт.

Буферная раскладка массива Int32:

1. Validity bitmap — ceil(N / 8) байт, padded до 64 байт
2. Data buffer — N × 4 байт (4 байта на Int32), padded до 64 байт

Доступ к элементу i:

value = *(int32_t*)(data_buffer + i * 4)

O(1) — прямое вычисление адреса. Нет индексов, нет B-деревьев, нет хэш-таблиц. Процессор загружает одну кэш-линейку (64 байта = 16 элементов Int32) — соседние элементы уже в кэше.

Массивы переменной ширины

Строки и бинарные данные не имеют фиксированного размера. Arrow использует три буфера:

1. Validity bitmap — как для фиксированных типов
2. Offsets buffer — массив из N + 1 смещений (Int32 для Utf8/Binary, Int64 для LargeUtf8/LargeBinary)
3. Data buffer — конкатенация всех значений без разделителей

Значение элемента i — это срез data[offsets[i]..offsets[i+1]]. Длина = offsets[i+1] - offsets[i].

Выравнивание и padding

Arrow требует выравнивания каждого буфера по 64 байтам. Это не произвольное число:

• Кэш-линейка x86/ARM: 64 байта
• AVX-512 регистр: 64 байта
• Выравнивание устраняет unaligned access penalties и позволяет SIMD обрабатывать данные без копирования

Правила padding:

• Начало каждого буфера выровнено по 64 байтам
• Конец каждого буфера дополнен нулями до кратности 64 байт
• Между буферами — padding до следующей 64-байтовой границы

O(1) Random Access

Вся конструкция Arrow оптимизирована под одну операцию: прямой доступ к элементу по индексу за O(1).

Для фиксированного типа (Int32):

address = base + buffer_offset + i * element_size

Для переменного типа (Utf8):

start = offsets[i]
end = offsets[i + 1]
value = data[start..end]

Никаких linked list, B-tree, hash table. Два умножения и одно сложение — даже без branch prediction miss.

Сравнение с другими форматами:

Boolean Array: особый случай

Boolean в Arrow — не массив байтов. Каждое значение занимает 1 бит, упакованный так же, как validity bitmap (LSB-first).

Буферная раскладка:

1. Validity bitmap — ceil(N / 8) байт
2. Data buffer — ceil(N / 8) байт (значения, не байты)

Array: [true, false, true, true, NULL, false, true, true]

Validity: 0b 1110_1111 = 0xEF (бит 4 = 0 → NULL)
Data: 0b 1110_1101 = 0xED (бит 4 undefined)

Ключевые выводы

1. Validity bitmap хранит NULL-маску по 1 биту на элемент (LSB-first), проверка NULL — O(1) побитовая операция
2. Фиксированная ширина (Int32, Float64) — один data buffer, доступ за O(1) через base + i × size
3. Переменная ширина (Utf8, Binary) — offsets buffer (N+1 элементов) + data buffer, доступ за O(1) через data[offsets[i]..offsets[i+1]]
4. 64-байтовое выравнивание обеспечивает SIMD-совместимость и совпадение с кэш-линейкой процессора
5. Boolean упакованы по 1 биту — не 1 байт, что даёт 8× плотность хранения