Kdouja Direct I/O Embedded Storage Core

Kdouja (Module 3) 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, persisting raw encrypted 4KB pages to physical NVMe media with microsecond-level latency and zero managed heap allocations.

1. 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 small 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 application memory, inflating memory consumption and triggering non-deterministic OS dirty-page flushes.

2. Core Subsystems of Kdouja

 Write Path:
 [ Put / Delete Page ]
        │
        ├──────────────────────────┐
        ▼ (Sequential Append)      ▼ (Lock-Free Insert)
┌──────────────┐            ┌──────────────┐
│  Write-Ahead │            │   MemTable   │
│   Log (WAL)  │            │ (Arena List) │
└──────────────┘            └──────┬───────┘
                                   │ (Threshold: 64MB Capacity)
                                   ▼
                            ┌──────────────┐
                            │  Immutable   │
                            │   MemTable   │
                            └──────┬───────┘
                                   │ (Flushed via Direct I/O)
                                   ▼
                            ┌──────────────┐
                            │ SSTable L0   │ <───┐
                            └──────┬───────┘     │ (Leveled Compaction
                                   │             │  L0 -> L1 -> L2...)
                                   ▼             │
                            ┌──────────────┐     │
                            │ SSTable L1   │ ────┘
                            └──────────────┘

A. GC-Free Arena SkipList MemTable

In-memory writes are stored inside a thread-safe MemTable backed by a SkipList. Rather than allocating individual node objects on the managed heap, Kdouja uses a growable MemoryArena block. SkipList node links are simple 32-bit primitive integer offsets. This completely eliminates .NET Garbage Collection overhead during intensive write bursts.

B. Durability & Recovery (Write-Ahead Log)

Before writing to memory, data is logged to the WriteAheadLog (WAL) for durability:

• Fsync Control: EnableWalFsync controls whether the engine calls a physical disk sync after every operation.
• CRC32C Digests: Prevents replaying corrupted or partially written transactions during crash recovery by verifying every record header with CRC32C.

C. Segment-Consolidated PageStore (256MB Segments)

Kdouja packs 4KB data pages into large, pre-allocated 256MB segment files (.seg):

• Zero Inode Exhaustion: Storing 1 Petabyte of data requires fewer than 4 million filesystem entries instead of 250 billion discrete files.
• Sub-Millisecond Indexing: An in-memory sparse index maps PageId -> (SegmentId, Offset, Length, CRC32C) for microsecond point lookups.
• Pure Sequential Streaming: Client random writes are consolidated into sequential streaming disk appends, maximizing NVMe flash endurance.

D. Algorithm-Aware Page IO (Authenticated Encryption)

Kdouja supports dual page-level encryption schemes: AES-256-GCM and ChaCha20-Poly1305. Every 4KB page is serialized with its dedicated 12-byte IV and 16-byte authentication tag in the page header, ensuring cryptographic integrity verification before any byte enters memory.

E. SSTable Layout with Delta Prefix Key Compression

When a MemTable flushes to disk, it creates an immutable Sorted String Table (SSTable):

• Delta Prefix Compression: Adjacent keys share common prefixes, significantly reducing index memory footprints.
• Restart Points: Placement of restart points every 16 keys allows binary search over a sparse restart array followed by forward linear scans, bounding search complexity to \(\mathcal{O}(\log R + R)\).

3. 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: FILE_FLAG_NO_BUFFERING | FILE_FLAG_WRITE_THROUGH via FileOptions.
• Linux: O_DIRECT | O_SYNC via low-level POSIX file descriptors.

// Unbuffered Direct I/O FileHandle 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
);

// Memory buffer allocation aligned to 4096-byte hardware sector boundaries
byte* alignedBuffer = (byte*)NativeMemory.AlignedAlloc(
    byteCount: 4096,
    alignment: 4096
);

4. Downward Zero-Dependency Boundary Principle

Architectural decoupling is strictly enforced at the compiler and project level:

• Zero Knowledge of Ahmodi or Codecs: Kdouja operates exclusively on raw numerical PageId primitives (\(\text{PageId} = (\text{NodeId} \ll 48) \mid \text{LocalPageId}\)). It has no concept of whether a page is primary data or Cauchy parity.
• Zero Web or SQL Dependencies: Pure native I/O kernel without ASP.NET, Entity Framework, or relational database libraries.
• Encapsulated inside Rokka: Each Rokka.StorageNode daemon hosts one or more isolated Kdouja engine instances (one per physical NVMe mount), guaranteeing that volume stalls never cause cross-volume cascading failures.