## User
Я создаю key-value базу данных на Rust, которая:
- use `rustix-uring` library
- use `seize` library
- without WAL
- keys are arrays with compile time length
- key type: just array bytes
- values are two types: with static length and variable length
- value type: shared bytes? like Bytes
- variable length values aligned 8 bytes
- in memory collection type: BTree or HashMap? need prefix search
- read - always sync methods
- write/update/delete - sync or async?
- multiple process read access?
Нужно помочь спроектировать ее.
Мне не нужна гарантия записи на диск, можно допускать потерю данных, если будут ошибки на диске. Но нужна CAS операция в рамках изменения данных для одного значения, чтобы не было гонки данных. Вообще лучше для записи оставить только один thread. Можно базу данных проектировать под одну таблицу, чтобы было проще.
Можешь для начала задать уточняющие и направляющие вопросы. Потом вместе будем проектировать базу данных шаг за шагом.
Может быть можно позаимствовать идеи из https://github.com/sweet-security/candystore.
Может быть нам не нужна LSM архитектура. Но точно не хочу использовать mmap.
## Gemini
Привет! Я готов помочь тебе в создании этой базы данных. Задача звучит амбициозно и интересно, особенно с учетом использования современных инструментов вроде `io_uring` и требований к производительности.
Твой выбор технологий (`rustix-uring`, `seize`) и ограничений (фиксированные ключи, отсутствие WAL) уже задает определенный вектор архитектуры. Давай разберем это.
### Мое понимание задачи
Ты строишь встраиваемое Key-Value хранилище:
1. **Производительность:** `io_uring` для ввода-вывода, отсутствие лишних гарантий (no WAL).
2. **Конкурентность:** Lock-free чтение (благодаря `seize`), CAS для атомарности изменений, желательно один поток на запись.
3. **Структура данных:** Префиксный поиск обязателен (значит, HashMap отпадает, смотрим в сторону деревьев).
4. **Хранение:** Ключи фиксированной длины, значения (static/variable), выравнивание.
### Уточняющие вопросы (Design Review)
Прежде чем мы перейдем к коду, давай проясним несколько критических моментов, которые определят архитектуру.
**1. Доступ из нескольких процессов (Multi-process read)**
> *multiple process read access?*
> Это самый сложный пункт в сочетании с *without mmap*.
> Если ты не используешь `mmap`, то разделить память между процессами (shared memory) для индекса (BTree) будет крайне сложно без использования системных вызовов `shm_open` и написания своего аллокатора.
* **Вопрос:** Действительно ли нужен доступ из *разных процессов ОС* к одному файлу БД одновременно? Или достаточно многопоточного доступа (Multi-thread) внутри *одного процесса*?
* *Совет:* Если это библиотека (embedded DB), лучше начать с **Single Process / Multi-thread**. Межпроцессное взаимодействие без mmap потребует архитектуры клиент-сервер или очень сложной работы с shared memory.
**2. Синхронное чтение vs `io_uring**`
`io_uring` по своей природе асинхронный (submission queue -> completion queue).
* **Вопрос:** Когда ты говоришь "read - always sync methods", ты имеешь в виду API для пользователя (`db.get(key) -> Value`)?
* Если да, то мы будем внутри использовать `io_uring`, но блокировать поток (или использовать `submit_and_wait`), пока данные не придут? Или для чтения мелких данных мы будем использовать обычный `pread` (так как syscall overhead на современных ядрах сопоставим с submit/wait для одиночных операций)?
**3. Индекс: BTree vs HashMap**
> *need prefix search*
* **Решение:** Однозначно **BTree** (или Adaptive Radix Tree - ART). HashMap не позволяет эффективно искать по префиксу.
* **Вопрос:** Индекс (само дерево) должно жить полностью в оперативной памяти (RAM)?
* Если **Да**: Это сильно упрощает дело (как в Bitcask). Ключи в памяти, значения на диске.
* Если **Нет**: Нам нужно страничное дерево (B+Tree), где узлы подгружаются с диска. Учитывая требование "without WAL" и простоту, я предлагаю вариант: **Индекс полностью в RAM, данные на диске**. Согласен?
**4. CAS (Compare-And-Swap) и Data Layout**
Ты хочешь CAS и отсутствие гонок. При одном писателе (Single Writer thread) CAS реализовать легко — писатель просто проверяет текущее значение перед записью нового.
* **Вопрос по формату файла:**
* *Append-only (Log Structured):* Новые данные всегда пишутся в конец файла. Старые остаются "мусором" до момента уплотнения (compaction). Это идеально для SSD и `io_uring`.
* *Update-in-place:* Мы перезаписываем данные поверх старых по смещению. Это сложнее с переменной длиной значения (фрагментация) и рискованно без WAL (если питание пропадет во время записи, получим битые данные).
* *Предложение:* Использовать **Append-only**. Это отлично ложится на идею `candystore` и упрощает восстановление (просто читаем файл до конца).
**5. `seize` и Garbage Collection**
`seize` — это библиотека для epoch-based memory reclamation (сбора мусора). Она идеальна для lock-free структур в памяти.
* **Уточнение:** Мы будем использовать `seize` для защиты узлов нашего BTree в памяти, чтобы читатели могли читать старую версию узла, пока писатель подменяет его на новый?
---
### Предлагаемый план архитектуры (Черновик)
Если ты согласен с моими предположениями выше, архитектура вырисовывается такая:
1. **Storage Engine (Диск):**
* Один открытый файл данных.
* Режим записи: Append-only.
* Формат записи: `[Header (CRC, Key, ValueLen, ...)] [Value]`.
2. **Indexing (Память):**
* `Concurrent BTree` (или `SkipList`), защищенный через `seize`.
* Ключ: `[u8; N]` (фиксированный массив).
* Значение в индексе: `u64` (смещение в файле) + `u32` (длина).
3. **Concurrency:**
* **Readers:** Много потоков. Читают BTree (lock-free), получают смещение, делают `pread` (или uring) из файла.
* **Writer:** Один поток (через канал или Mutex). Обрабатывает CAS логику, пишет в конец файла, обновляет BTree.
---
**Что делаем дальше?**
Ответь, пожалуйста, на вопросы (особенно про Multi-process и помещается ли индекс в RAM). После этого я напишу структуру проекта (`struct`'ы) и мы начнем реализацию.
## User
По вопросам:
1. доступ из разных процессов не нужен. упрощаем.
2. api для пользователя должен быть синхронным, как в sled и fjall. как они этого достигают?
3. Да - индексы полностью в RAM.
4. Можно ли сделать оба варианта - для значений переменной длины - Append-only, для фиксированной - Update-in-place? или лучше остановиться на одном? сильно ли будет влиять compaction?
5. Да, для чтения с нескольких потоков. Есть ли вариант записи с нескольких потоков с последующей отправкой в отдельный поток записи на диск?
По архитектуре:
А читать значение будет всегда из диска? Можно хранить все данные в оперативной памяти если помещаются, и часть из них, если не помещаются в RAM?
## Gemini
Отлично, мы значительно сузили круг задач. Это упрощает архитектуру и позволяет сосредоточиться на производительности.
Давай разберем твои вопросы и утвердим финальную схему перед тем, как писать код.
### Ответы на вопросы и технические решения
**1. Синхронный API (как в Sled/Fjall)**
> *Как они этого достигают?*
> В большинстве случаев движки типа Sled или RocksDB для **чтения** (random read) используют обычные системные вызовы `pread` (позиционное чтение) или `mmap`. Это синхронные операции ОС. Блокировка потока происходит только на время копирования данных из ядра в буфер пользователя.
* **Наше решение:** Так как `io_uring` имеет накладные расходы на submit/completion (особенно для одиночных операций), для *синхронного чтения* (`get`) эффективнее и проще использовать обычный `pread` (через `rustix::fs::pread`). Это даст минимальную латентность.
* `io_uring` мы задействуем там, где он сияет: в **Writer Thread** (группировка записей, fsync) и в **Compaction** (фоновая пересборка базы).
**2. Append-only vs Update-in-place**
> *Можно ли смешивать?*
> Технически можно, но **Update-in-place без WAL — это риск потери данных**.
> *Сценарий:* Ты обновляешь значение фиксированной длины. Записал половину байт, и вырубили электричество. Старое значение затерто, новое не дописано. У тебя "битая" запись.
* **Решение:** Используем **Append-only для ВСЕГО** (и фикс, и переменной длины).
* *Плюсы:* Атомарность (мы просто дописываем новую версию в конец, старая остается валидной до компакции), простота восстановления, последовательная запись (быстро на HDD/SSD).
* *Влияние Compaction:* Да, старые данные ("мусор") будут копиться. Нам нужен фоновый процесс, который чистит старые файлы. Но это стандартная плата за надежность и скорость записи.
**3. Запись: Multi-thread -> Single Writer**
> *Есть ли вариант записи с нескольких потоков с отправкой в отдельный поток?*
> Да, это паттерн **"Actor"** или **"Serializer"**.
* Клиентские потоки кидают задачу `(Key, Value, ResponseChannel)` в MPSC очередь (например, `crossbeam-channel` или `flume`).
* Один поток-писатель разгребает очередь, пишет в файл (batch write через `io_uring`), обновляет индекс в памяти и отправляет "ОК" клиентам.
* Это автоматически решает проблему гонки данных (CAS) при записи, так как писатель у нас один.
**4. Кэширование (RAM + Disk)**
> *Можно хранить все данные в оперативной памяти если помещаются?*
> Конечно.
* **Архитектура:** `Index (RAM)` -> `Block Cache (RAM)` -> `Disk`.
* При чтении мы сначала смотрим в кэш значений (например, `moka` или простой `LruCache`). Если там нет — идем на диск.
* При старте можно "прогреть" кэш, если нужно.
---
### Финальная Архитектура
Мы строим систему, похожую на **Bitcask**, но с современным стеком.
#### 1. Структуры данных
**В памяти (Index & Cache):**
* **Index:** Concurrent Radix Tree или BTree.
* Используем `seize` для lock-free чтения узлов.
* Ключ: `[u8; N]` (фиксированный).
* Значение (Metadata): Структура `EntryLocation { file_id: u32, offset: u64, len: u32 }`.
* **Cache:** LRU кэш, хранящий "горячие" значения `Bytes`.
**На диске (Storage):**
* **Active File:** Файл, в который пишет Writer. Только Append.
* **Immutable Files:** Старые файлы, доступные только для чтения.
* **Формат записи:**
```text
[Header (CRC32, Timestamp, KeyLen, ValueLen)] [Key] [Value]
```
*Выравнивание:* Если Value переменной длины, добавляем padding до 8 байт, как ты просил.
#### 2. Потоки данных (Data Flow)
**Чтение (`get`):**
1. Поиск в Индексе (lock-free). Получили `Location`.
2. Проверка в Кэше значений. Если есть -> возврат.
3. Если нет -> `pread` из файла по смещению -> десериализация -> вставка в Кэш -> возврат.
**Запись (`put` / `cas`):**
1. Поток-клиент создает `Request`.
2. Отправляет в канал `Sender`.
3. Блокируется на `Receiver` (ждет ответа).
4. **Writer Thread**:
* Берет пачку запросов из канала.
* Формирует буфер для записи.
* Пишет на диск (можно `io_uring` для батчинга).
* Обновляет Индекс (это критическая секция, но быстрая, так как в памяти).
* Отвечает клиентам.
### Вопрос перед реализацией Storage Engine:
Согласен ли ты с подходом **"Writer Thread via Channel"**? Это сделает запись чуть медленнее, чем прямой write под мьютексом (из-за переключения контекста), но зато идеально линеаризует операции и позволяет делать сложные CAS-проверки без блокировки читателей.
## User
Еще немного уточнений:
- Мы ориентируемся на NVME диски
- нам нужна эффективная репликация на низком уровне, чтобы пользователю не пришлось ее реализовывать самому
- кажется отправлять в очередь изменение данных для другого потока не оптимально? может обновлять данные в памяти, как это сделано в scc для TreeIndex (https://docs.rs/scc/latest/scc/) и потом как то синхронизировать изменения на диск?
## Gemini
Это отличный поворот. Переход на NVMe и требование встроенной репликации меняют правила игры.
Ты абсолютно прав: схема "один поток-писатель через канал" станет узким местом (bottleneck) для NVMe диска, который способен переваривать сотни тысяч IOPS параллельно. Также очередь неэффективна для CAS, так как увеличивает латентность (время отклика).
Давай пересоберем архитектуру под **High-Performance NVMe + Replication**.
### Основные изменения концепции
1. **Отказ от "Actor Model" в пользу "Concurrent Writing".** NVMe любит параллелизм. Нам нужно писать в файл(ы) из нескольких потоков или использовать `io_uring` максимально агрессивно.
2. **Global Index + Sharded Log.** Чтобы утилизировать NVMe, мы не будем писать в один файл. Мы будем писать в несколько "страйпов" (stripes/shards) параллельно, но индекс оставим глобальным для удобства поиска.
3. **Replication Stream.** Репликация должна работать на уровне передачи байтов, записанных в лог (Log Shipping).
Вот разложенная по полочкам архитектура:
---
### 1. Топология хранения (Storage Layout)
Вместо одного файла используем концепцию **Log Striping** (Секционирование лога).
* **Virtual Log:** Логически это один бесконечный поток записей.
* **Physical Files (Partitions):** Физически данные пишутся в $N$ файлов одновременно (где $N$ — количество ядер или очередей NVMe, например, 8-16).
* **Routing:** Какой файл выбрать для записи?
* *Вариант А (Round-robin):* Просто пишем по очереди во все файлы. Обеспечивает идеальную балансировку нагрузки на диск.
* *Вариант Б (Hash-based):* `Hash(Key) % N`. Это гарантирует, что версии одного ключа всегда в одном "шарде". Это **критически важно для CAS и порядка операций**. Выбираем этот вариант.
### 2. Структура памяти (In-Memory Index)
Ты упомянул `scc::TreeIndex`. Это отличный выбор для B+Tree, который поддерживает конкурентный доступ.
* **Global Index:** Один большой `scc::TreeIndex<Key, EntryLocation>`.
* **EntryLocation:** `{ shard_id: u8, offset: u64, length: u32 }`.
* **Особенность `scc`:** Он позволяет делать атомарные операции (`update`, `entry`). Это решает половину проблемы CAS.
### 3. Процесс записи (Write Path & CAS)
Вот здесь магия. Как сделать CAS (Compare-And-Swap) без единого потока-писателя, но с гарантией порядка?
Мы используем подход **Sharded Locks + Group Commit**.
У нас есть $N$ шардов (Log Partitions). У каждого шарда есть:
1. Свой файл на диске (открытый через `io_uring`).
2. Свой буфер в памяти (Ring Buffer).
3. Свой `Mutex` (или RwLock) для сериализации записи *внутри этого шарда*.
**Алгоритм `CAS(key, expected_val, new_val)`:**
1. **Map:** Вычисляем `shard_id = hash(key) % N`.
2. **Lock:** Блокируем этот конкретный шард (другие шарды работают параллельно!).
3. **Verify (In-Memory):**
* Идем в Global Index.
* Проверяем, совпадает ли текущее значение с `expected_val`. (Если значение на диске, возможно, придется прочитать, но если мы держим кэш или хеши значений в памяти — это мгновенно).
* Если не совпало -> возвращаем ошибку (CAS failed).
4. **Append to Buffer:**
* Копируем `new_val` в буфер записи этого шарда.
* Получаем будущее смещение `file_offset`.
5. **Update Index (Optimistic):**
* Обновляем Global Index, указывая на новый `file_offset`.
* *Важно:* Мы обновляем индекс *до* физической записи на диск (так как ты разрешил потерю данных при сбое диска). Это дает "Memory speed" для чтений.
6. **Unlock:** Отпускаем шард.
7. **Flush (Async/Group Commit):**
* Если буфер шарда заполнился или прошел тайм-аут (например, 100мс), отправляем батч через `io_uring` на диск.
### 4. Репликация (Low-Level Replication)
Репликация встроена в архитектуру шардов.
* **Role:** Узел может быть `Leader` или `Follower`.
* **Механизм:** Log Shipping.
* **Процесс:**
1. На Лидере каждый шард — это Append-only поток.
2. Реплика подключается и говорит: "Дай мне данные шарда #3, начиная со смещения 1024".
3. Лидер просто стримит (используя `sendfile` или zero-copy из буферов) новые данные по мере их появления.
4. **Follower:** Получает байты, пишет их в свой диск (в тот же шард) и параллельно обновляет свой In-Memory Index.
**Почему это эффективно?**
* Нет перекодирования JSON/Protobuf. Мы шлем "сырые" байты с диска.
* Многопоточность: Репликация шарда #1 не блокирует репликацию шарда #2.
### 5. Архитектурная схема
```text
[ Client Requests ]
|
v
+-----------------------+
| Global Index | <-- scc::TreeIndex (Prefix Search)
| (Key -> Shard+Offset) |
+-----------------------+
|
| Маршрутизация по Hash(Key)
v
+==============+ +==============+ +==============+
| Shard #1 | | Shard #2 | ... | Shard #N |
+==============+ +==============+ +==============+
| Write Lock | | Write Lock | | Write Lock |
| Log Buffer | | Log Buffer | | Log Buffer |
+------+-------+ +------+-------+ +------+-------+
| | |
| io_uring | io_uring | io_uring
v v v
[ NVMe File #1 ] [ NVMe File #2 ] [ NVMe File #N ]
| | |
+--------+---------+ |
| |
Replication Stream (TCP/QUIC) ---------+
|
v
[ Follower Node ]
```
### Ответы на твои опасения
> *кажется отправлять в очередь изменение данных для другого потока не оптимально?*
Да. В новой схеме поток, который делает CAS, сам захватывает "легкий" лок конкретного шарда, копирует данные в буфер и уходит. Саму запись на диск делает либо он же (если буфер полон), либо фоновый тред `io_uring`. Это убирает переключения контекста.
> *обновлять данные в памяти... и потом как то синхронизировать изменения на диск?*
Именно так мы и поступим (пункт 3.5 выше).
**Риск:** Если свет мигнет, в памяти будет значение `X`, а на диске `Y`.
**Решение:** При рестарте мы читаем файлы с конца и восстанавливаем индекс. Последние "незаписанные" данные просто исчезнут, что укладывается в твои требования. CAS работает корректно, пока процесс жив.
> *нам нужна эффективная репликация*
Так как данные у нас иммутабельные (Append-only), репликация становится тривиальной задачей синхронизации хвостов файлов. Не нужно реализовывать сложные машины состояний.
### Итоговый чек-лист архитектуры:
1. **Engine:** Sharded Bitcask (Log-Structured).
2. **Concurrency:** Shared-Nothing Writing (по шардам), Global Reading (по индексу).
3. **Index:** `scc::TreeIndex` (поддерживает range scan для префиксного поиска).
4. **IO:** `rustix-uring` с режимом `SQPOLL` (polling mode) для максимальной скорости на NVMe.
5. **Replication:** Async Log Shipping per shard.
Что думаешь насчет разделения на **Шарды (Partitions)**? Это стандартный паттерн для High-Performance БД (используется в ScyllaDB, Kafka и т.д.).
## User
Отличная архитектура! Я за шарды (Partitions)! Еще вопрос: по этой архитектуре мы вычисляем шард по ключу, получается несколько потоков могут писать в один шард и поэтому нужны блокировки (Mutex или RwLock). Но это гарантирует что версии одного ключа всегда в одном "шарде". А если мы будет создавать/использовать шард на поток, тогда не нужны синхронизации/блокировки вроде Mutex, но какой недостаток для CAS операций? Будет логическая ошибка если два потока одновременно обновит данные для одного значения, и порядок записи в шарды на диск перепутается? или придется синхронизировать записи в шарды по точному timestamp, который не должен повторяться для разных шардов?
## Gemini
Это фундаментальный вопрос архитектуры баз данных. Ты нащупал классический компромисс между **Shared-Nothing** (где каждый поток пишет в свой файл) и **Shared-State** (где мы делим данные по ключам).
Давай разберем, почему для задачи **с CAS** вариант "Шард на Поток" (Thread-Local Shards) является **опасным**, и почему "Шард по Хешу Ключа" (Hash-Based Sharding) — это правильный выбор.
### Анализ: Шард на Поток (Thread-Local)
Представь архитектуру: у нас 4 потока, и каждый пишет в свой файл (`thread_1.log`, `thread_2.log`...). Блокировок на запись нет. Скорость записи — сумасшедшая.
**Проблема 1: Сломанный CAS (Race Condition)**
CAS операция звучит так: *"Запиши 5, только если сейчас там 3"*.
1. **Исходное состояние:** Ключ `balance` = 3. Индекс указывает на `thread_1.log`.
2. **Поток А** хочет сделать CAS (3 -> 5). Он читает индекс: "Ага, сейчас 3".
3. **Поток Б** (одновременно) хочет сделать CAS (3 -> 9). Он читает индекс: "Ага, сейчас 3".
4. **Поток А** пишет `balance=5` в свой `thread_A.log` и обновляет индекс.
5. **Поток Б** пишет `balance=9` в свой `thread_B.log` и перезаписывает индекс.
**Результат:** Мы потеряли обновление от Потока А. В базе лежит 9, хотя должно было быть (3 -> 5 -> ошибка для Б). Или, что хуже, у нас в логах лежат две "актуальные" версии, и непонятно, какая победила.
Чтобы это исправить, нам пришлось бы блокировать **запись в Глобальном Индексе** на время всей операции. А это убивает весь смысл разделения файлов.
**Проблема 2: Восстановление (Recovery) и Порядок**
> *придется синхронизировать записи в шарды по точному timestamp?*
Да. При старте базы тебе придется прочитать все N файлов потоков и слить их (Merge Sort) в хронологическом порядке.
* Если использовать системное время (`SystemTime`), то на современных CPU оно может "скакать" между ядрами или иметь недостаточную точность. Две записи могут получить одинаковое время.
* Нам нужен **Global Atomic Counter** (Sequence Number), чтобы выдавать уникальные ID для каждой записи. Но инкремент этого атомика станет тем самым "бутылочным горлышком", от которого мы пытались уйти.
---
### Анализ: Шард по Хешу Ключа (Hash-Based Sharding) — Наш выбор
Здесь мы вычисляем `ShardID = Hash(Key) % Count`.
Все изменения ключа `user_123` **всегда** попадают в один и тот же шард (файл + буфер).
**Преимущества для CAS:**
1. **Естественная сериализация:** Поскольку все запросы к одному ключу идут в одну очередь (один шард), они выстраиваются в линию. Нам достаточно простого `Mutex` на уровне шарда.
2. **Линеаризуемость:** Если Поток А захватил мьютекс Шарда №5, Поток Б будет ждать. Когда А закончит, Б увидит уже новое состояние.
3. **Простое восстановление:** Внутри одного файла порядок записей всегда правильный. Не нужно сверять время между файлами.
**Миф о блокировках:**
> *получается несколько потоков могут писать в один шард и поэтому нужны блокировки...*
Да, блокировка нужна, но давай оценим её стоимость.
Мы **не делаем I/O под блокировкой**.
Под блокировкой `Mutex` происходит только:
1. Проверка условия (сравнение двух чисел/строк).
2. `memcpy` данных в буфер в оперативной памяти (Ring Buffer).
Это занимает **наносекунды**. Даже при высокой нагрузке вероятность того, что два потока столкнутся на *одном и том же* шарде (из, скажем, 64 шардов) — низкая. `parking_lot::Mutex` в таких условиях работает почти как спинлок и не вызывает дорогого переключения контекста ядра ОС.
### Итоговая рекомендация
Остаемся на схеме **Partition by Key**.
Для NVMe дисков и High-load систем обычно делают количество шардов равным или кратным количеству ядер CPU (например, `num_cpus` или `num_cpus * 2`). Это дает отличную параллелизацию.
## User
Меня интересует в архитектуре compaction - логи будут расти, их нужно сжимать. как это делать?
## Gemini
Компакция (уплотнение данных) — это критически важный процесс для "Append-only" баз данных. Без неё диск заполнится устаревшими версиями данных ("мусором").
Поскольку у нас архитектура **Sharded Bitcask** (данные разбиты на шарды), компакцию нужно делать **по-шардово**. Это огромный плюс: пока один шард уплотняется, остальные 63 (условно) работают без нагрузки.
Вот архитектура процесса компакции (Compaction Strategy).
---
### 1. Жизненный цикл файлов в Шарде
Внутри каждой папки шарда (например, `/data/shard_05/`) файлы будут иметь три состояния:
1. **Active File (Активный):** Единственный файл, в который прямо сейчас пишет Writer. Он открыт на запись. Компактор его **не трогает**.
2. **Immutable Files (Запечатанные):** Файлы, которые заполнились (например, достигли 1 ГБ) и были закрыты. Они доступны только для чтения. Это "пища" для компактора.
3. **Compacted Files (Уплотненные):** Результат работы компактора. Они тоже Immutable.
### 2. Алгоритм "Merge & Splash" (Слияние)
Компакция должна работать в отдельном фоновом потоке (или пуле потоков), чтобы не тормозить `get/put` операции.
**Шаги алгоритма:**
1. **Выбор жертв (Selection):**
* Компактор смотрит на список Immutable файлов в шарде.
* Выбирает файлы, где процент "мусора" высок (например, > 30%) или просто самые старые файлы.
* Допустим, выбрали файлы `log_1.dat` и `log_2.dat`.
2. **Итерация и Фильтрация:**
* Компактор открывает новый файл `log_merged_v1.dat`.
* Он последовательно читает записи из `log_1` и `log_2`.
* Для каждой записи (Ключ, Значение) он делает проверку в **Глобальном Индексе**:
* *"Эй, Индекс, где сейчас актуальные данные для этого Ключа?"*
* **Логика решения:**
* Если Индекс говорит: *"Актуальные данные в `log_1.dat`, смещение 100"* (то есть указывает на то, что мы сейчас читаем) — значит, запись **ЖИВАЯ**.
* Если Индекс говорит: *"Актуальные данные в `log_active.dat`"* (или другом файле) — значит, запись устарела (была перезаписана). Мы её **ПРОПУСКАЕМ**.
3. **Перенос (Copying):**
* Если запись живая, мы копируем её (Header + Key + Value) в новый файл `log_merged_v1.dat`.
* Мы запоминаем новое смещение.
4. **Атомарное переключение (The CAS Switch):**
* Это самый опасный момент. Пока мы копировали, пользователь мог обновить этот ключ.
* Мы должны обновить Индекс, чтобы он указывал на новый файл.
* Используем операцию `Compare-And-Swap` на записи в Индексе:
* *Задача:* Установить адрес = `(log_merged, new_offset)`.
* *Условие:* Только если текущий адрес всё ещё равен `(log_1, old_offset)`.
* **Если CAS успешен:** Отлично, ключ переехал.
* **Если CAS провалился:** Значит, пока мы возились, пришел Writer и записал новую версию в Активный файл. Наша копия в `merged` файле мгновенно стала мусором. Это нормально, мы просто ничего не делаем с индексом.
5. **Очистка:**
* Когда все ключи обработаны, файлы `log_1.dat` и `log_2.dat` удаляются с диска.
* Файл `log_merged_v1.dat` становится обычным Immutable файлом.
### 3. Нюанс: "Value Log Separation" (Опционально)
Ты упомянул *variable length values*. Если значения очень большие (например, картинки по 1МБ), а ключи маленькие, классическая компакция (Bitcask) может быть дорогой, так как придется постоянно гонять большие куски данных из файла в файл.
**Оптимизация (WiscKey подход):**
Если мы видим, что Value очень большое, мы можем хранить его в отдельном "Value Log", а в основном логе хранить только ссылку. Но для начала я рекомендую **не усложнять** и хранить всё вместе. Современные NVMe выдают 3-5 ГБ/сек, они легко переварят копирование данных при компакции, если база не петабайтного размера.
### 4. Взаимодействие с удалением (Tombstones)
Как работает `delete(key)` в такой схеме?
1. Writer пишет в Активный файл специальную запись: `[Header: Type=TOMBSTONE] [Key] [Value=Empty]`.
2. Обновляет Индекс: удаляет запись о ключе или ставит метку "deleted".
3. **При компакции:** Если мы встречаем Tombstone, и видим, что более старых версий этого ключа в *еще более старых* файлах не осталось, мы можем просто **выкинуть** этот Tombstone и не писать его в новый файл. Ключ исчезает физически.
### 5. Резюме по архитектуре Компакции
* **Изоляция:** Компакция работает на уровне одного шарда. Не блокирует всю базу.
* **Чтение:** Используем `pread` (или `mmap` на чтение, это безопасно), чтобы быстро сканировать старые файлы.
* **Запись:** Пишем в новый файл большими кусками (через буфер), чтобы не убивать SSD мелкими I/O.
* **Синхронизация:** Единственная точка пересечения с "живым" трафиком — это момент `CAS` в Глобальном Индексе.
**Вопрос на засыпку:**
Как ты планируешь хранить список файлов для каждого шарда?
* *Вариант А:* Хранить в памяти `Vec<FileMetadata>`.
* *Вариант Б:* Создать файл-манифест (как в LevelDB/RocksDB), где записано, какие файлы составляют базу.
Учитывая требование "без WAL" и простоту, я предлагаю при старте просто сканировать директорию шарда (`readdir`), сортировать файлы по ID и восстанавливать структуру. Манифест не нужен.