Skip to main content

SSTable Format & Persistence (v1.0.0)

When an ImmutableMemTable is flushed to persistent storage, it is serialized into an SSTable (Sorted String Table) .sgdb file containing a header, contiguous record data, a Sparse Index, and an embedded Bloom Filter.

SSTable File Binary Layout​

┌──────────────────────────────────────────────────────────────┐
│                    1. Header Block (256 Bytes)               │
│  Magic (0x47534442) | Version (1) | Record Count | Data Offset│
│  Bloom Filter Offset | Sparse Index Offset | Tombstone Count │
├──────────────────────────────────────────────────────────────┤
│                    2. Data Block (Sorted Records @ 256)      │
│  Record 1 [Seq (8) | Flag (1) | KeyLen | ValLen | Key | Val] │
│  Record 2 [Seq (8) | Flag (1) | KeyLen | ValLen | Key | Val] │
│  ...                                                         │
├──────────────────────────────────────────────────────────────┤
│                    3. Sparse Index Block ($K = 16$)          │
│  Entry Count (4)                                             │
│  Index Entry 0 [KeyLen | KeyBytes | RecordOffset (8)]       │
│  Index Entry 1 ...                                           │
├──────────────────────────────────────────────────────────────┤
│                    4. Bloom Filter Block ($1\%$ FPR)         │
│  BitCount (8) | HashCount (4) | BitArrayBytes                │
└──────────────────────────────────────────────────────────────┘

Header Fields​

  1. Magic Number (0x47534442): 4-byte integer magic identifier (GSDB).
  2. Version (1): 4-byte integer layout version.
  3. Table ID & Timestamps: 8-byte sequence ID and creation timestamp.
  4. Record Count & File Size: 4-byte record count and total file byte size.
  5. Data Offset (256): Byte offset where record payload data begins.
  6. Bloom Filter Offset: Byte offset pointing to embedded Bfilter bit array.
  7. Sparse Index Offset: Byte offset pointing to SstSparseIndex array.

Indexed Read Path in v1.0.0​

  1. Bloom Filter Probe (O(1)): Probes embedded Bfilter bit array. Non-existent keys are rejected in nanoseconds without reading disk record blocks.
  2. Sparse Index Binary Search (O(log(N/16))): Binary searches SstSparseIndex sampled entries (K=16) to locate the exact 16-record chunk interval [startOffset, endOffset].
  3. Positional Reading: SstReader reads target block records positionally, guaranteeing zero OS memory leaks and deterministic Windows file handle release.