# Оптимизация размера узлов SkipList — результаты реализации
## Проблема
ConstTree / ZeroTree хранят маленькие Copy-значения (8-32 байта), но каждый узел skip list добавлял ~130-152 байт инфраструктуры: SmallVec tower (40 bytes), отдельный Box для ConstData, отдельный Box для DiskLoc (VarNode), `marked: AtomicBool` с 7 байтами padding, DiskLoc с 7 байтами padding. При миллионах записей инфраструктура доминировала в потреблении памяти.
## Layout до оптимизации
### ConstNode (K=16, V=16)
```rust
pub struct ConstNode<K: Key, const V: usize> {
pub key: K, // K bytes
pub data: AtomicPtr<ConstData<V>>, // 8 bytes
height: u8, // 1 + 7 padding
marked: AtomicBool, // 1 + 7 padding
tower: SmallVec<[AtomicPtr<Self>; 2]>, // 40 bytes (24 metadata + 16 inline)
}
pub struct ConstData<const V: usize> {
pub disk: DiskLoc, // 24 bytes (17 real + 7 padding)
pub value: [u8; V], // V bytes
}
pub struct DiskLoc {
pub shard_id: u8, // 1
pub file_id: u32, // 4
pub offset: u64, // 8
pub len: u32, // 4
} // = 17 bytes, с padding = 24
```
| Компонент | Размер |
|-----------|--------|
| ConstNode struct | ~80 bytes |
| ConstData (отдельный Box) | 24 + V = 40 bytes |
| Allocator overhead (2 x Box) | ~32 bytes |
| **Итого** | **~152 bytes** (из них полезных — 32) |
### VarNode (K=16)
| Компонент | Размер |
|-----------|--------|
| VarNode struct (key + AtomicPtr + height + marked + SmallVec) | ~72 bytes |
| DiskLoc (отдельный Box) | 24 bytes |
| Allocator overhead (2 x Box) | ~24 bytes |
| **Итого** | **~120 bytes** |
### TypedNode (K=16, T=64)
| Компонент | Размер |
|-----------|--------|
| TypedNode struct | ~80 bytes |
| TypedData (отдельный Box) | 24 + T = 88 bytes, но часть overlap с node |
| Allocator overhead (2 x Box) | ~32 bytes |
| **Итого** | **~148 bytes** |
## Реализованные оптимизации
### 1. Упаковка DiskLoc: 24 -> 12 bytes
**Исходный план:** упаковать в `u64` (8 bytes) с битовыми полями (4 бита shard, 16 бит file_id, 32 бита offset, 12 бит len).
**Что сделано:** `#[repr(C)]` struct с полями фиксированных размеров:
```rust
#[repr(C)]
pub struct DiskLoc {
pub offset: u32, // 4 bytes — до 4 GB на файл
pub len: u32, // 4 bytes — до 4 GB размер значения
pub file_id: u16, // 2 bytes — до 65536 файлов
pub shard_id: u8, // 1 byte — до 256 шардов
_pad: u8, // 1 byte — выравнивание
} // = 12 bytes, без padding
```
Конструктор `DiskLoc::new(shard_id, file_id, offset, len)` с приватным полем `_pad`.
**Отличие от плана:** 12 bytes вместо 8. Причина — `len` нужен полный `u32` диапазон (до 4 GB), потому что VarTree хранит значения произвольного размера. 12-битное поле (до 4096) было бы недостаточно. Конфигурация валидирует `max_file_size <= u32::MAX`.
**Экономия:** 12 bytes на каждый узел, содержащий DiskLoc.
**Файлы:** `armdb/src/disk_loc.rs`
### 2. Tag bit вместо marked: AtomicBool
**Что сделано:** удалено поле `marked: AtomicBool` (1 byte + 7 padding = 8 bytes). Метка логического удаления хранится в младшем бите указателя `tower[0]` (всегда 0 из-за alignment указателей).
```rust
fn is_marked(&self) -> bool {
self.tower(0).load(Ordering::Acquire) as usize & 1 != 0
}
fn mark(&self) -> bool {
// AtomicPtr lacks fetch_or, so reinterpret as AtomicUsize.
let atomic_usize: &AtomicUsize =
unsafe { &*(self.tower(0) as *const AtomicPtr<Self> as *const AtomicUsize) };
let old = atomic_usize.fetch_or(1, Ordering::AcqRel);
old & 1 == 0
}
```
Вспомогательная функция `strip_mark()` в `skiplist/mod.rs` маскирует бит при загрузке указателей tower:
```rust
pub(crate) fn strip_mark<T>(ptr: *mut T) -> *mut T {
(ptr as usize & !1) as *mut T
}
```
Все загрузки tower-указателей в `SkipList` проходят через `strip_mark()`.
**Соответствие плану:** полностью совпадает с предложением.
**Экономия:** 8 bytes на узел (все три типа).
**Файлы:** `armdb/src/skiplist/node.rs`, `armdb/src/skiplist/mod.rs`, `armdb/src/skiplist/iter.rs`
### 3. VLA tower вместо SmallVec
**Что сделано:** `SmallVec<[AtomicPtr<Self>; 2]>` (40 bytes) заменён на inline-аллокацию переменной длины. Узел аллоцируется одним блоком через `std::alloc::alloc` с tower-массивом сразу после полей структуры:
```rust
fn layout_for(height: u8) -> std::alloc::Layout {
let tower_bytes = height as usize * size_of::<AtomicPtr<Self>>();
let total = Self::base_size() + tower_bytes;
let align = align_of::<Self>().max(align_of::<AtomicPtr<Self>>());
Layout::from_size_align(total, align).expect("invalid layout")
}
```
**Отличие от плана:** в структуре появилось поле `tower_ptr: *const AtomicPtr<Self>` (+8 bytes), которого не было в исходном предложении. Исходный план предполагал вычисление адреса tower через pointer arithmetic от `&self`. Проблема: Miri/Stacked Borrows — ссылка `&self` имеет provenance только на `size_of::<Self>()` байт, tower-массив расположен за пределами структуры. Чтение через `&self` + смещение — UB по Stacked Borrows.
Решение: хранить raw pointer `tower_ptr`, вычисленный при аллокации из `ptr` (аллокационный указатель имеет provenance на весь блок). Аналогично тому, как `Vec` хранит указатель на свой буфер.
```rust
tower_ptr: *const AtomicPtr<Self>,
fn tower(&self, level: usize) -> &AtomicPtr<Self> {
debug_assert!(level < self.height as usize);
unsafe { &*self.tower_ptr.add(level) }
}
```
Кастомные `dealloc_node()` и `reclaim()` в `SkipNode` trait для деаллокации VLA-блока:
```rust
unsafe fn dealloc_node(ptr: *mut Self);
unsafe fn reclaim(ptr: *mut Self, _collector: &seize::Collector);
```
Зависимость `smallvec` удалена из `Cargo.toml`.
**Экономия:** 40 - 8 (tower_ptr) - 8 (средний tower: height=1 -> 8 bytes) = 24 bytes нетто (вместо 32 по плану). Средний height ~1.33 -> средний tower ~10.7 bytes.
**Файлы:** `armdb/src/skiplist/node.rs`, `armdb/Cargo.toml`
### 4. Inline ConstData + SeqLock (только ConstNode)
**Что сделано:** `ConstData<V>` struct удалён полностью. Поля `disk` и `value` встроены непосредственно в `ConstNode` через `UnsafeCell`. Вместо RCU (AtomicPtr + Box + seize retire на каждую запись) используется SeqLock-протокол:
```rust
#[repr(C)]
pub struct ConstNode<K: Key, const V: usize> {
pub key: K,
seq: AtomicU64,
disk: UnsafeCell<DiskLoc>,
value: UnsafeCell<[u8; V]>,
height: u8,
tower_ptr: *const AtomicPtr<Self>,
}
```
SeqLock-протокол чтения:
```rust
loop {
let s1 = self.seq.load(Acquire);
if s1 & 1 != 0 { spin_loop(); continue; } // нечётное = writer active
let disk = unsafe { ptr::read(self.disk.get()) };
let value = unsafe { ptr::read(self.value.get()) };
fence(Acquire); // данные прочитаны до повторной проверки seq
let s2 = self.seq.load(Relaxed);
if s1 == s2 { return (disk, value); }
spin_loop();
}
```
SeqLock-протокол записи (под shard Mutex — один writer):
```rust
self.seq.fetch_add(1, Relaxed); // odd — writing
fence(Release); // видимость перед записью данных
unsafe {
ptr::write(self.disk.get(), disk);
ptr::write(self.value.get(), *value);
}
self.seq.fetch_add(1, Release); // even — done
```
Реализованы специализированные методы: `read_data()`, `read_disk()`, `read_value()`, `write_data()`, `write_disk()`.
**Соответствие плану:** полностью совпадает. Memory ordering для ARM: `Acquire` на обоих чтениях seq + `fence(Acquire)` между данными и вторым seq.
**Эффект:**
- Убирает heap-аллокацию `Box<ConstData>` на каждую запись
- Убирает seize retire для ConstData
- Убирает `AtomicPtr<ConstData>` (8 bytes) и замещает на `seq: AtomicU64` (8 bytes) + inline поля
- Нетто экономия: ~33 bytes (Box overhead + ConstData heap + pointer)
**Ограничение:** только ConstNode (Copy-типы, маленькие значения). TypedNode и VarNode сохраняют RCU + AtomicPtr.
**Файлы:** `armdb/src/skiplist/node.rs`, `armdb/src/const_tree.rs`, `armdb/src/const_map.rs`, `armdb/src/zero_tree.rs`, `armdb/src/zero_map.rs`
## Layout после оптимизации
### ConstNode (K=16, V=16)
```
#[repr(C)]
ConstNode {
key: [u8; 16], // 16 bytes
seq: AtomicU64, // 8 bytes
disk: UnsafeCell<DiskLoc>, // 12 bytes
value: UnsafeCell<[u8; 16]>, // 16 bytes
height: u8, // 1 byte + padding
tower_ptr: *const AtomicPtr<Self>, // 8 bytes
}
// base_size ~ 64 bytes (с учётом alignment padding)
// + tower: height x 8 bytes (среднее 1.33 x 8 ~ 11)
// Итого среднее: ~75 bytes
// Одна аллокация (std::alloc::alloc)
```
### VarNode (K=16)
```
#[repr(C)]
VarNode {
key: [u8; 16], // 16 bytes
disk: AtomicPtr<DiskLoc>, // 8 bytes
height: u8, // 1 byte + padding
tower_ptr: *const AtomicPtr<Self>, // 8 bytes
}
// base_size ~ 40 bytes (с padding)
// + tower: height x 8 ~ 11
// + Box<DiskLoc> на heap: 12 + ~16 allocator = ~28
// Итого среднее: ~76 bytes (VLA-узел + heap DiskLoc)
```
### TypedNode (K=16, T=64)
```
#[repr(C)]
TypedNode {
key: [u8; 16], // 16 bytes
data: AtomicPtr<TypedData<T>>, // 8 bytes
height: u8, // 1 byte + padding
tower_ptr: *const AtomicPtr<Self>, // 8 bytes
}
// base_size ~ 40 bytes (с padding)
// + tower: height x 8 ~ 11
// + Box<TypedData<T>> на heap: 12 + 64 + ~16 allocator = ~92
// Но TypedData меньше: DiskLoc теперь 12, не 24
// Итого среднее: ~104 bytes
```
## Результаты
### Экономия по типам (K=16)
| | ConstNode (V=16) | VarNode | TypedNode (T=64) |
|--|--:|--:|--:|
| **До** | ~152 bytes | ~120 bytes | ~148 bytes |
| Упаковка DiskLoc (24 -> 12) | -12 | -12 | -12 |
| Tag bit (-marked) | -8 | -8 | -8 |
| VLA tower (нетто, с tower_ptr) | -24 | -24 | -24 |
| Inline + SeqLock | -33 | -- | -- |
| **После** | **~75 bytes** | **~76 bytes** | **~104 bytes** |
| **Коэффициент** | **~2.0x** | **~1.6x** | **~1.4x** |
### Качественные улучшения
- ConstNode: одна аллокация вместо трёх (node + ConstData + SmallVec spill)
- VarNode: одна аллокация для node, одна для DiskLoc (вместо трёх)
- TypedNode: одна аллокация для node, одна для TypedData (вместо трёх)
- Улучшенная cache locality: tower в том же блоке памяти, что и ключ
- Убран seize retire для ConstData (ConstNode)
## Отклонения от плана
### DiskLoc: 12 bytes вместо 8
Исходный план предполагал упаковку в `u64` с битовыми полями (`len` — 12 бит, до 4096). Реализовано как `#[repr(C)]` struct 12 bytes. Причина: VarTree хранит значения произвольного размера, `len` нужен полный диапазон `u32` (до 4 GB). Это стоило 4 дополнительных байта, но обеспечило безопасные диапазоны для всех полей.
### VLA tower: нужен tower_ptr (+8 bytes)
Исходный план предполагал вычисление адреса tower через `&self` + offset. Miri/Stacked Borrows это запрещает: `&self` имеет provenance только на `size_of::<Self>()`, tower находится за пределами. Решение — хранить raw pointer `tower_ptr` в структуре. Это уменьшило экономию с 32 до 24 bytes.
### VarNode: AtomicU64 трюк отложен
Исходный план предполагал, что с DiskLoc(u64) можно заменить `AtomicPtr<DiskLoc>` на `AtomicU64` в VarNode, убирая heap-аллокацию и seize retire для DiskLoc. Это было бы самой выгодной оптимизацией для VarNode (~40 bytes экономии). Но DiskLoc = 12 bytes, не 8, поэтому в `AtomicU64` не помещается. VarNode по-прежнему использует `AtomicPtr<DiskLoc>` + `Box<DiskLoc>` + seize retire.
Из-за этого реальная экономия VarNode (1.6x) значительно меньше планировавшейся (3.0x).
## Открытые вопросы / будущая работа
1. **VarNode AtomicU64 DiskLoc** — если ограничить `offset` до 32 бит и `len` до 24 бит (16 MB макс. размер значения), DiskLoc помещается в 8 байт. Это позволит заменить `AtomicPtr<DiskLoc>` на `AtomicU64` в VarNode, убрав heap-аллокацию и seize retire. Потенциальная экономия: ~28 bytes на узел VarNode. Требует анализа реальных лимитов `len` для VarTree.
2. **SeqLock для VarNode disk** — альтернативный путь: использовать SeqLock для inline DiskLoc (12 bytes) в VarNode, аналогично ConstNode. Это убирает Box, но добавляет `AtomicU64 seq` (8 bytes) и `UnsafeCell<DiskLoc>` (12 bytes) вместо `AtomicPtr<DiskLoc>` (8 bytes) + Box(12 + 16 alloc) = ~36 bytes. Нетто экономия ~16 bytes.
3. **Loom-тестирование SeqLock** — SeqLock-протокол реализован с корректным ordering для x86 и ARM, но формальная верификация через loom пока не проведена.
4. **tower_ptr elimination** — если Stacked Borrows эволюционирует к Tree Borrows (где `&self` через `addr_of!` сохраняет allocation provenance), поле `tower_ptr` можно будет убрать, вернув 8 bytes.
## Применимость по типам
### Матрица реализованных оптимизаций
| Оптимизация | ConstNode | VarNode | TypedNode |
|-------------|:---------:|:-------:|:---------:|
| Упаковка DiskLoc (24 -> 12) | да | да | да |
| Tag bit | да | да | да |
| VLA tower | да | да | да |
| Inline + SeqLock | да | нет | нет |
| AtomicU64 DiskLoc | -- | отложено | -- |
**ConstNode** получил все 4 оптимизации. Inline + SeqLock применим только к Copy-типам фиксированного размера.
**VarNode** получил 3 из 4 оптимизаций. AtomicU64 трюк отложен из-за того, что DiskLoc = 12 bytes. По-прежнему использует RCU (`AtomicPtr<DiskLoc>` + `Box` + seize).
**TypedNode** получил 3 оптимизации. Inline + SeqLock не применим — `T` может быть произвольного размера и не-Copy (String, Vec). RCU с seize обязателен для безопасного чтения `&T`.