-
Notifications
You must be signed in to change notification settings - Fork 7
NKDS Binary Format
The NKitDataStore is a content-addressed block storage engine built on a custom binary index format and flat binary shard files. It is the persistence layer for the NKit dedupe pipeline and the NKit DataStore virtual filesystem (NKDS). Its design goals are: maximum cross-image deduplication, minimum on-disk size, and fast random-access reads for virtual filesystem serving.
The binary index format stores all metadata (images, areas, offsets, block locations) in a single
compact file with zstd-compressed sections, enabling fast per-image loading without reading the
entire index. A standalone converter tool (NKDS.Converter) provides bidirectional conversion
between the legacy SQLite format and the binary format.
A DataStore directory contains one or more sets. Each set is represented by two kinds of file:
<datastore-dir>/
<setname>.nkds ← Binary index file (metadata, block index, image sections)
<setname>_0000.nkds ← shard 0: raw block data
<setname>_0001.nkds ← shard 1: raw block data (created when shard 0 is full)
<setname>_0002.nkds ← …
The .nkds extension is shared by both kinds of file. The binary index has no numeric suffix;
the shard files are zero-padded four-digit sequence numbers.
When a set is created with --shard-size 0, the finished on-disk layout is a single file:
[raw block data (shard)] [binary index] [12-byte footer: IndexSize(8 bytes LE) + Magic "NKDS"(4 bytes)]
During any write operation the embedded format is transparently extracted to the standard two-file layout (separate index + shard) and re-embedded on commit. The NKDS magic bytes at the end of the file act as the detection sentinel. If a crash occurs while writing, the two-file layout is left on disk and the engine recovers automatically on next open.
The binary index file contains all metadata previously stored in SQLite, organized into independently-readable compressed sections for fast per-image access.
Offset 0x000: Primary Header (256 bytes)
Offset 0x100: Secondary Header (256 bytes, redundant copy)
Offset 0x200: Directory Region (reserved, typically 4096 bytes)
Data Region: Image_Metadata_Sections + Image_BlockMap_Sections (per image)
Block_Index (global, sectioned zstd)
The header contains pointers to all major sections:
| Field | Description |
|---|---|
| Magic |
0x4E4B4453 ("NKDS") |
| MajorVersion / MinorVersion | Format version |
| ImageDirectoryOffset / Size | Location of the compressed Image_Directory |
| BlockIndexOffset / Size | Location of the Block_Index |
| BlockIndexDeltaHeadOffset / Count | Delta chain for incremental updates |
| FileEndOffset | Total index size |
| ShardSize | Maximum shard file size (0 = embedded mode) |
| BlockSize | Deduplication block size (default 65536) |
| MaxOffsetBlocks | Maximum block references per offset record |
| ImageCount | Total number of images |
| DirectoryRegionCapacity | Reserved space for directory growth |
A compressed (zstd) array of ImageDirectoryEntry records, one per image. Each entry contains:
- Image metadata: id, name, size, crc32, xxhash64, system, format, rollback info, removed flag
- Section pointers: metadata section offset/size, block map section offset/size
The directory is loaded once on open and provides O(1) lookup by image ID.
A zstd-compressed section containing:
- AreaRecords: offset, size, stride parameters, crc32, xxhash64, metadata blob
- FileRecords: auxiliary files (filesystem.yaml, tmd, tik, cetk) with shard locations
A zstd-compressed section containing:
- OffsetRecords: byte offset, size, type, block key lists
- BlockLocations: dictionary mapping each BlockKey → (FileId, Offset, Size) in the shard
This section is self-contained — it has everything needed to read an image's blocks without loading the global Block_Index. This enables fast per-image loading during mount/read operations.
A sectioned zstd-compressed structure used only during write operations for deduplication lookups. It is NOT loaded during normal read operations.
[StructureVersion: uint16 = 2]
[SectionCount: uint32]
[Section 0: CompressedSize(8 BE), UncompressedSize(8 BE), ZstdData...]
[Section 1: CompressedSize(8 BE), UncompressedSize(8 BE), ZstdData...]
...
Each section header is 16 bytes: CompressedSize(int64 BE) + UncompressedSize(int64 BE).
The int64 size fields support block indexes larger than 4 GB.
Each section's uncompressed data is a flat array of 28-byte entries:
XxHash64(8 BE) + Crc32(4 BE) + FileId(4 BE) + Offset(8 BE) + Size(4 BE)
Entries are sorted by (XxHash64, Crc32) ascending, enabling binary search. The sectioned compression allows random access without decompressing the entire index.
Incremental updates appended after writes. Deltas are merged with the main index on read (during write operations only). When the same BlockKey appears in both the main index and a delta, the delta entry is retained (newer entry wins).
The delta header is 30 bytes:
Version(2 BE) + EntryCount(4 BE) + NextDeltaOffset(8 BE) + CompressedSize(8 BE) + UncompressedSize(8 BE)
Followed by byte[CompressedSize] of zstd-compressed entry data (28-byte entries, same layout
as the main Block_Index). Deltas form a reverse linked list via NextDeltaOffset.
Compaction retains all entries — block removal is handled by per-image BlockLocations, not by the global Block_Index.
Block reads use a tiered resolution strategy that avoids loading the global Block_Index:
-
Per-image BlockLocations cache (
_blockMapCache): When an image's offsets are loaded (viaGetOffsetsForImage), the Image_BlockMap_Section is decompressed and both the offset records and the BlockLocations dictionary are cached. Subsequent block reads look up locations directly from this cache. -
Already-cached Block_Index (no load triggered): If the global Block_Index was previously loaded (e.g., during a write transaction), it remains in memory and is checked as a secondary source. This handles edge cases like reading blocks immediately after writing.
-
Cold-start LoadBlockIndex (direct API usage only): For direct
GetBlockDatacalls without a prior image open (e.g., aux block lookups, test scenarios), the global Block_Index is loaded on demand. This path is never hit during normal mount/read operations.
The global Block_Index is loaded only for:
-
Write operations:
BeginTransactionloads it for deduplication lookups - Compaction: Rebuilding the index requires the full block set
-
Direct API calls:
BlockExists, aux block resolution
The legacy SQLite format is supported via the NKDS.Converter tool for bidirectional conversion.
The schema is documented here for reference.
Schema version 0.1.0 is packed into a 64-bit SQLite INTEGER:
(major << 32) | (minor << 16) | revision → 0x0000000000010000.
| Column | Type | Description |
|---|---|---|
version |
INTEGER | Packed schema version (0x0000000000010000 = 0.1.0) |
shard_size |
INTEGER | Maximum shard file size in bytes (0 = unlimited) |
block_size |
INTEGER | Deduplication block size in bytes (default 65 536 = 64 KiB) |
max_offset_blocks |
INTEGER | Maximum block references per offset row (default 336) |
store_fs |
INTEGER | 1 = persist filesystem.yaml per image, 0 = disabled |
max_offset_blocks = 336 was chosen because it fills exactly one 4 KiB SQLite page when the
12-byte hash BLOB array is serialised, giving optimal page utilisation.
| Column | Type | Description |
|---|---|---|
id |
INTEGER PK AUTOINCREMENT | Unique image identifier within this set |
name |
TEXT | Image name (no file extension) |
size |
INTEGER | Total logical image size in bytes |
crc32 |
INTEGER | CRC-32 of the full image |
xxhash64 |
INTEGER | xxHash-64 of the full image |
system_id |
INTEGER | System enum value (NULL if unknown) |
format_id |
INTEGER | Output format enum value |
rollback_file_id |
INTEGER | Shard file ID at write completion (NULL until committed) |
rollback_offset |
INTEGER | Shard byte offset at write completion (NULL until committed) |
Two indexes accelerate the most frequent lookups:
-
idx_image_crc32on(crc32)— fast existence check during dedupe -
idx_image_crc32_xxhash_nameon(crc32, xxhash64, name)— composite lookup used during verify and DataStore open
rollback_file_id and rollback_offset record the shard state after all blocks for the image
have been written to disk. They are set by UpdateImageMetadata at write completion, not at write
start. Querying the maximum image.id and reading its rollback columns gives the exact truncation
point needed to cleanse a partial write left behind by a crash during a subsequent image.
system_id values (System enum — NULL stored when unknown):
| Value | System | Value | System |
|---|---|---|---|
| 0 | Default (ISO 9660) | 8 | Xbox |
| 1 | GameCube | 9 | Xbox 360 |
| 2 | Wii | 10 | Dreamcast |
| 3 | Wii U | 11 | Saturn |
| 4 | PS1 | 12 | Sega CD |
| 5 | PS2 | 13 | CD-i |
| 6 | PS3 | 14 | PC Engine |
| 7 | PSP |
format_id values (ImageFormat enum):
| Value | Name | Extension | Value | Name | Extension |
|---|---|---|---|---|---|
| 0 | Unknown |
.iso | 3 | App |
.app |
| 1 | Iso |
.iso | 4 | Cdn |
.cdn |
| 2 | Bin |
.bin | 5 | Gdi |
.gdi |
| Column | Type | Description |
|---|---|---|
id |
INTEGER PK AUTOINCREMENT | Area identifier |
image_id |
INTEGER FK → image(id) ON DELETE CASCADE | Owning image |
offset |
INTEGER | Byte offset within the logical image |
size |
INTEGER | Logical size in bytes |
stride_block_size |
INTEGER | Physical sector size (e.g. 0x8000 for Wii) |
stride_data_offset |
INTEGER | Offset of clean data within a physical sector |
stride_data_length |
INTEGER | Length of clean data within a physical sector |
section_size |
INTEGER | Section granularity for fast VFS offset lookup |
crc32 |
INTEGER | CRC-32 of the area data |
xxhash64 |
INTEGER | xxHash-64 of the area data |
metadata |
BLOB | Format-specific metadata (system-dependent) |
Areas model the internal structure of a disc image. The stride columns describe how clean data is packed inside physical sectors. For example, Wii optical sectors contain 0x400 bytes of hash data preceding every 0x7C00 bytes of user data. The stride model strips those hashes on write and reconstructs them transparently on read, storing only the clean payload.
ON DELETE CASCADE means deleting an image row automatically removes all its areas (and offsets,
via the same cascade on the offset table).
| Column | Type | Description |
|---|---|---|
image_id |
INTEGER | Owning image (composite PK) |
offset |
INTEGER | Byte offset of this segment within the logical image (composite PK) |
size |
INTEGER | Logical size of this segment in bytes |
type_id |
INTEGER |
BlockType enum value |
offset_start |
INTEGER | Offset of the first chunk in the logical file group |
blocks |
BLOB | Packed array of 12-byte hash BLOBs (zero-length for virtual data) |
The table has a composite primary key (image_id, offset) with a standard SQLite rowid. All
lookups go through the composite index; the rowid is not used directly.
type_id values (BlockType enum):
| Value | Name | Description |
|---|---|---|
| 0 | Other |
Other verifiable virtual data |
| 1 | File |
Standard file data |
| 2 | FormatData |
Format-specific structural metadata (partition headers, volume descriptors) |
| 3 | FileSystem |
Filesystem tables and metadata |
| 4 | BlockPadding |
Stride-only padding — excluded from ImageReadStream reads |
| 5 | NJunk |
NKit algorithmically generated junk (no shard bytes) |
| 6 | XFiller |
Xbox verifiable random filler (no shard bytes) |
blocks encoding — Each 12 bytes is [xxhash64: 8 bytes LE][crc32: 4 bytes LE]. A single
offset row can reference up to max_offset_blocks blocks, so a 64 KiB block size with 336
references covers 21 MiB per row — large enough for any realistic contiguous file in one row while
keeping blob sizes page-aligned.
Virtual data — Segments that are algorithmically reconstructable (NJunk, XFiller, or
Other verifiable data) are stored with an empty blocks BLOB and a type_id that identifies
the generation algorithm. No shard bytes are consumed for these segments.
offset_start groups multiple offset rows belonging to the same logical file. During read,
all rows with the same (image_id, offset_start) are concatenated in offset order to produce
a continuous file stream.
Two indexes support efficient access patterns:
-
idx_offset_image_sortedon(image_id, offset)— sequential scan in image order -
idx_offset_fileon(image_id, offset_start)— grouping all chunks of a single file
| Column | Type | Description |
|---|---|---|
image_id |
INTEGER | Owning image (composite PK) |
name |
TEXT | File name (e.g. filesystem.yaml) (composite PK) |
file_id |
INTEGER | Shard file ID |
offset |
INTEGER | Byte offset within the shard file |
size |
INTEGER | Stored (compressed) size in bytes |
uncompressed_size |
INTEGER | Original size in bytes |
Declared WITHOUT ROWID on (image_id, name).
Auxiliary files such as filesystem.yaml are written directly to the shard binary data stream
(not through the block deduplication pipeline) and tracked here. They are distinguished from block
data by using negative offsets in the offset table, which ensures they are never mixed with
logical image content during reads.
| Column | Type | Description |
|---|---|---|
hash |
BLOB(12) PRIMARY KEY | [xxhash64: 8 bytes LE][crc32: 4 bytes LE] |
file_id |
INTEGER | Shard file sequence number |
offset |
INTEGER | Byte offset within the shard file |
size |
INTEGER | Stored (compressed) size in bytes |
Declared WITHOUT ROWID. The 12-byte BLOB is the B-tree key, so a lookup by hash requires a
single B-tree descent with no secondary page fetch — optimal for the dedupe hot path.
The two-hash design serves two purposes:
- xxHash-64 is extremely fast (single-pass SIMD on modern CPUs); it is the first filter
- CRC-32 is the compatibility hash used by NKit verification and disc integrity checking
- The combination gives collision resistance equivalent to a 96-bit hash space
Shard files are raw binary files with no internal structure — they are a flat stream of variable-length compressed block payloads, one immediately after the next.
ShardFileManager manages shard lifecycle:
-
Write path: protected by an internal
_writeLock. A new shard is opened before writing if the block would cause the current shard to exceedshard_size(no block ever spans two shards).WriteBlockreturns(fileId, offset, length)which is immediately stored in theblocktable. -
Read path: a
ConcurrentDictionary<int, FileStream>keeps one long-lived openFileStreamper shard, perShardFileManagerinstance. Reads use per-shard locks from a parallelConcurrentDictionary<int, object>to avoidFileStream.Seek/Readinterleaving. Pre-opening all existing shards at construction time amortisesFileStreamcreation cost. -
Write buffer:
max(256 KiB, block_size)— covers a full block in one kernel call. -
Read buffer:
max(64 KiB, block_size)— matches the typical block size. -
Rollback:
RollbackToSize(fileId, targetSize)truncates the current shard and resets the size counter. Used when dedupe detects a block already exists after it was written but before the block table was updated.
The write path for a single image:
-
DataStore.AddImagebegins a SQLite transaction and creates anImageWriter. - The caller opens a write stream via
ImageWriter.BeginWriteStream(offset, type)and pipes data intoImageWriteStream. -
ImageWriteStreamaccumulates incoming bytes into 64 KiB (orblock_size) chunks. - For each complete chunk:
a. Compute xxHash-64 and CRC-32 of the uncompressed data.
b. Look up the
BlockKeyin theblocktable — if found, record the existing shard location in theoffsetrecord and move on (zero extra shard bytes). c. If not found: compress with Zstandard. If the compressed payload + 1 prefix byte is smaller than the original, store compressed; otherwise store raw. Write to the current shard. Insert the new row into theblocktable. - On stream
Dispose,OffsetsManagercreatesoffsetrows grouping all the block references for that segment. - When all streams are disposed,
ImageWriter.FinalizeImagecallsUpdateImageMetadatawhich writes the finalsize,crc32,xxhash64,rollback_file_id, androllback_offset. - The transaction is committed.
Compression selection — BlockCompressor tries each codec in preference order. A compressed
result is only accepted when compressed_size + 1 < original_size. The extra byte is the
compression-type prefix stored before the payload in the shard. Uncompressed blocks are stored
without the prefix byte — there is no byte overhead for incompressible data.
ImageReadStream presents a single seekable Stream over a logical image:
-
Offset list is loaded once from the Image_BlockMap_Section (zstd-compressed per image),
sorted by offset, with
BlockPaddingentries excluded (they exist only for stride reconstruction) and auxiliary negative-offset entries filtered out. - BlockLocations are loaded alongside offsets from the same Image_BlockMap_Section. This dictionary maps each BlockKey to its shard location (FileId, Offset, Size), enabling block reads without loading the global Block_Index.
- Cumulative prefix sums over the offset list are computed at construction time, enabling O(log N) binary search to locate the offset record for any given stream position.
-
Run read-ahead — blocks within a single
offsetrecord were written contiguously to the shard during dedupe.ReadBlockRundetects this locality by resolving shard locations for consecutive blocks from the per-image BlockLocations cache, then issues one large I/O call covering the entire contiguous run. This converts many small random reads into one sequential I/O operation. -
Per-stream decompression buffer — each
ImageReadStreamallocates its own_decompressionBufferequal toblock_size. Concurrent streams on the sameImageReadernever share decompression state, so no locking is needed during the decompress step. -
Block cache — the last decompressed block is cached in
_currentBlockData. Re-reads of the same block (e.g., seeks within a 64 KiB window) avoid redundant decompression.
When an image has an associated .aux set (containing update/DLC data), the AuxBlockProvider
implements a two-tier resolution chain:
- Try the primary image's blocks (via per-image BlockLocations)
- Fall back to the aux image reader (which has its own BlockLocations from the aux set)
This is transparent to the mount/read layer — the ImageBuilder base class uses IBlockProvider
which handles the primary→aux fallback automatically.
When store_fs = 1, each image has a filesystem.yaml auxiliary file written to the shard data
and tracked in the file table. It describes the full disc filesystem tree in a compact,
dependency-free YAML dialect:
version: 1.0
fs:
Game:
DATA:
default.dol: [4096, 6291456, 11223344556677889, 1234ABCD]
opening.bnr: [10387456, 98304, AABBCCDDEEFF0011, DEADBEEF]
/System:
boot.bin: [0, 1088, ...]- Directories are plain keys with no value and indented children.
-
Files are keys whose value is a 4-element list:
[offsetStart, size, xxhash64, crc32]. -
System entries (headers, format metadata) use a
/prefix on the directory or file name. These are hidden from normal VFS views and only shown in--systemmode.
The format is generated and parsed without any external YAML library (AOT-safe).
| Concern | Mechanism |
|---|---|
| Block lookup (read) | Per-image BlockLocations dictionary — O(1) hash lookup, no global index load |
| Block lookup (dedupe/write) | Global Block_Index with sectioned zstd — binary search within decompressed section |
| Image metadata access | Image_Directory loaded once on open — O(1) by image ID |
| Per-image section load | Single zstd decompress per section — only loaded when image is accessed |
| Sequential image read | Run read-ahead via contiguous shard detection — one I/O per block run |
| Random seek within image | O(log N) binary search over pre-computed cumulative prefix sums |
| Concurrent VFS reads | Per-stream decompression buffers; per-shard read locks; no global lock |
| Incompressible data | Stored uncompressed with zero prefix-byte overhead |
| Algorithmically reproducible data | Zero shard bytes — virtual offset rows only |
| Shard rotation | No-spillover: block never split across two shards |
| Crash recovery (embedded format) | NKDS footer detection; two-file layout left intact on crash |
| Crash recovery (write failure) |
rollback_file_id/rollback_offset marks the safe truncation point |
| Filesystem YAML loading | Lazy-loaded on demand via LRU cache (no eager loading during mount) |
| Stats calculation | Per-image BlockLocations used for block sizes — no global index load required |