Kdouja LSM Storage Engine & Direct I/O

Kdouja is Aarkam’s embedded, high-throughput Log-Structured Merge-tree (LSM) key-value storage engine. It executes in-process directly within every Rokka.StorageNode daemon, responsible for persisting raw encrypted chunks to physical storage media with microsecond-level latency.

Why Traditional Filesystems Fail for Object Storage

Standard storage appliances write individual object chunks as discrete operating system files (e.g., ext4, XFS, NTFS). Under petabyte-scale workloads, this approach introduces catastrophic bottlenecks:

1. Inode & MFT Exhaustion: Writing millions of 4KB chunks consumes all available filesystem inodes long before physical disk capacity is exhausted.
2. Directory Lock Contention: OS directory structures lock under high concurrent file creation, causing write latency spikes.
3. Double-Buffering Cache Pollution: The OS page cache duplicates data already buffered in memory, inflating memory usage and triggering non-deterministic OS dirty-page flushes.

┌────────────────────────────────────────────────────────────────────────┐
│                        Traditional File Systems                        │
│   Chunk 1 (4KB) ───► /mnt/disk/c1.dat (Inode 1)                        │
│   Chunk 2 (4KB) ───► /mnt/disk/c2.dat (Inode 2)  ► Inode Exhaustion    │
│   Chunk 3 (4KB) ───► /mnt/disk/c3.dat (Inode 3)    Directory Locking   │
└────────────────────────────────────────────────────────────────────────┘

┌────────────────────────────────────────────────────────────────────────┐
│                        Kdouja Segment PageStore                        │
│   Chunk 1 (4KB) ───┐                                                   │
│   Chunk 2 (4KB) ───┼──► Pre-Allocated 256MB Contiguous Segment File    │
│   Chunk 3 (4KB) ───┘    Zero Inode Overhead · Linear Direct I/O        │
└────────────────────────────────────────────────────────────────────────┘

The Kdouja Solution: Segment PageStore

Kdouja solves these limitations by replacing discrete files with an append-only Segment PageStore:

• Contiguous 256MB Segments: Chunks are packed into large, pre-allocated 256MB container files (.seg). A 1 PB cluster requires fewer than 4 million filesystem entries instead of 250 billion discrete files.
• Microsecond Indexing: An in-memory sparse index maps PageId -> (SegmentId, Offset, Length, CRC32C) for sub-millisecond point lookups.
• Sequential Append Only: Random writes from clients are transformed into pure sequential streaming writes, maximizing the lifespan and endurance of enterprise NVMe and SSD drives.

Raw Unbuffered Direct I/O

To eliminate OS kernel cache overhead and double-buffering latency, Kdouja executes all physical disk I/O through unbuffered Direct I/O:

• Windows: Opened with FILE_FLAG_NO_BUFFERING | FILE_FLAG_WRITE_THROUGH.
• Linux: Opened with O_DIRECT | O_SYNC.

// Unbuffered Direct I/O FileStream initialization in Kdouja
var handle = File.OpenHandle(
    path: segmentPath,
    mode: FileMode.OpenOrCreate,
    access: FileAccess.ReadWrite,
    share: FileShare.Read,
    options: FileOptions.Asynchronous | (FileOptions)0x20000000 // FILE_FLAG_NO_BUFFERING
);

Direct I/O Requirements

1. Memory Buffer Alignment: All I/O buffers must be aligned to physical sector boundaries (typically 4096 bytes).
2. Zero Memory Allocation: Kdouja utilizes an unmanaged native memory pool (NativeMemory.AlignedAlloc), recycling 4KB buffers without putting pressure on the .NET Garbage Collector.

Write Path: WAL & Skip-List MemTable

Kdouja provides ACID durability using a two-tier in-memory and write-ahead log structure:

1. Write-Ahead Log (WAL): Chunks are sequentially written to an active append-only WAL on NVMe storage.
2. Arena Skip-List MemTable: Concurrently, an entry is inserted into an in-memory lock-free skip-list index.
3. Flushing & Compaction: Once the MemTable reaches its threshold (64MB), it transitions to read-only and is flushed asynchronously to a sealed immutable segment file (.seg). Background compaction merges adjacent segments and reclaims space from deleted chunks.