Casandra

Cassandra uses LSM trees for complete data storage, not just secondary indexing. Every row, column, and cell is stored through the LSM chain. There is no traditional B-tree for primary data; the entire column family (table) resides in the LSM tree hierarchy

Partitions are stored in token order (by the hash of the partition key), and within each partition, rows are stored in clustering column order (ascending or descending as defined by the schema).

Cassandra’s LSM-Based Storage Enginengine

Full Data Storage (Not Just Indexing)Cassandra uses LSM trees for complete data storage, not just secondary indexing. Every row, column, and cell is stored through the LSM chain. There is no traditional B-tree for primary data; the entire column family (table) resides in the LSM tree hierarchy.

JSON Parsing and Internal RepresentationWhen you insert a JSON object into Cassandra using INSERT INTO table JSON '...', the system performs the following stages:

Stage 1: CQL Parser

The CQL parser recognizes the INSERT JSON syntax and validates the JSON text against the table schema. The JSON string is tokenized and checked for syntactic correctness.

Stage 2: JSON Deserializer

The JSON text is parsed into a map structure:

Map<String, Object> = {
  "column_name_1": value_1,
  "column_name_2": value_2,
  ...
}

Stage 3: Schema Resolution

For each key-value pair in the JSON map:

Lookup the column definition from System.Schema_Columns.
Match JSON key names to column names (case-sensitive by default).
Retrieve the column’s type codec (e.g., TextType, Int32Type, TimestampType).
Validate that the JSON value is compatible with the expected Cassandra type.

Stage 4: Key Extraction and Partition Computation

The partition key columns are identified from the PRIMARY KEY definition. If the table is:

CREATE TABLE users (
  user_id text,
  event_time timestamp,
  name text,
  age int,
  PRIMARY KEY (user_id, event_time)
);

Then user_id is the partition key, and event_time is the clustering column. The value of user_id from the JSON object is extracted and hashed using the configured Partitioner (typically Murmur3Partitioner). This produces a token (a 64-bit signed integer).

Token = Murmur3(serialize(user_id_value))
Example: Murmur3("alice123") = -7639649877256983472

The result is a DecoratedKey:

DecoratedKey {
  token: -7639649877256983472,
  key: "alice123" (encoded as bytes)
}

Stage 5: Clustering Key Extraction

The clustering columns are identified from the PRIMARY KEY definition (all columns after the partition key). In this example, event_time is the clustering column. The clustering key values are serialized in the order they appear in the schema and stored as a list:

clustering_prefix =

Stage 6: Cell Creation

Each non-key column becomes a Cell. For the JSON input:

{
  "user_id": "alice123",
  "event_time": "2025-11-06T06:00:00Z",
  "name": "Alice",
  "age": 30
}

Cells are created for name and age:

Cell 1: {
  name_bytes: "name" (variable-length encoded),
  timestamp: 1730862000000000 (microseconds, from USING TIMESTAMP or current time),
  ttl: null (no TTL specified),
  value_bytes: "Alice" (UTF-8 encoded),
  is_tombstone: false
}

Cell 2: {
  name_bytes: "age" (variable-length encoded),
  timestamp: 1730862000000000,
  ttl: null,
  value_bytes: 0x0000001E (32-bit big-endian int: 30),
  is_tombstone: false
}

Stage 7: MemTable Insertion

A Partition object is constructed and inserted into the active MemTable:

Partition {
  partitionKey: DecoratedKey(-7639649877256983472, "alice123"),
  staticRow: StaticRow(cells=),  // for static columns, if any
  rows: [
    Row {
      clusteringPrefix: ,
      cells: 
    }
  ]
}

The MemTable’s skip list is updated to include this partition, keyed by the DecoratedKey. The skip list maintains sorted order by token, so partitions are organized by their hash value, not by their logical key.

Stage 8: Commit Log Write

Simultaneously with the MemTable insert, the entire mutation is appended to the commit log as a sequence of bytes. The commit log entry includes:

{
  type: MUTATIONS,
  table_id: UUID (identifying the table),
  mutations: [
    {
      partition_key: "alice123",
      clustering_key: ,
      cells: [
        {name: "name", value: "Alice", timestamp: 1730862000000000},
        {name: "age", value: 30, timestamp: 1730862000000000}
      ]
    }
  ],
  version: 4  // SSTable version for forward compatibility
}

Write Path in Detail

The write path is meticulously optimized for sequential I/O:

Append to Commit Log (sequential disk write, ~1-2 microseconds per operation)
Write to MemTable (in-memory skip list insertion, O(log n) but entirely in RAM)
Acknowledge to client (indicates both steps 1 and 2 are complete)

The client’s write is considered durable as soon as it is both in the commit log and MemTable. No further disk I/O is required for acknowledgment.

When the MemTable exceeds its size threshold:

MemTable marked read-only (no new writes to this MemTable)
New MemTable created (subsequent writes go to the new MemTable)
Background flush (the frozen MemTable is written to disk as a new SSTable at Level 0)
Commit log segment discarded (only when all its mutations have been flushed)

SSTable Internal Structure and On-Disk LayoutAn SSTable consists of multiple component files, each serving a specific purpose:

Component	Purpose	Content
Data.db	Raw data	Partitions in token order; within each partition, rows sorted by clustering columns
Index.db	Partition index	Entries mapping DecoratedKey → byte offset in Data.db; includes row indices for wide partitions
Summary.db	Sparse index	Sampling of Index.db (default: 1 entry per 128 keys); enables binary search with O(log 128) ≈ O(7) operations
Filter.db	Bloom filter	Probabilistic set for partition keys; one bit per key
Statistics.db	Metadata	Min/max timestamps, tombstone counts, TTL distribution, repair markers, compaction history
CompressionInfo.db	Compression map	Offsets and lengths of compressed blocks in Data.db
Digest.crc32	Checksum	CRC-32 digest of Data.db for integrity verification
TOC.txt	Manifest	Plain text list of all component files

Data.db Layout

The Data.db file is structured as a sequence of partitions:

Each partition contains:

Partition Header:
  - partition_key_length (2 bytes)
  - partition_key_bytes (variable)
  - partition_deletion_time (4 bytes)
  - static_row_size (4 bytes)
  - static_row_bytes (variable, if present)

Row 1:
  - clustering_key_length (2 bytes)
  - clustering_key_bytes (variable)
  - row_deletion_time (4 bytes)
  - cell_count (variable-length int)
  
  Cell 1:
    - column_name_length (2 bytes)
    - column_name_bytes (variable)
    - timestamp (8 bytes, microseconds)
    - ttl (4 bytes, 0 if no TTL)
    - value_length (4 bytes)
    - value_bytes (variable)
    - is_tombstone (1 bit in flags)

Row 2:
  ...

Partitions are sorted by their token (the hash of the partition key). Within each partition, rows are sorted by clustering column values in the order specified in the CREATE TABLE statement. This sorting is critical for the efficient read and merge operations we’ll discuss below.

Index.db Layout

Index.db stores entries in sorted order, mapping partition keys to their byte offsets:

IndexEntry 1: (DecoratedKey_1, offset_1)
IndexEntry 2: (DecoratedKey_2, offset_2)
...
IndexEntry N: (DecoratedKey_N, offset_N)

When reading a partition, the system uses the index to find the offset, performs a single seek to that position in Data.db, and begins reading sequentially.

Summary.db (Sparse Index)

To avoid storing the entire index in memory, Cassandra creates a Summary that samples the index:

SummaryEntry 0: (DecoratedKey at position 0, offset_0)
SummaryEntry 1: (DecoratedKey at position 128, offset_128)
SummaryEntry 2: (DecoratedKey at position 256, offset_256)
...

The summary is loaded into memory and allows Cassandra to perform a binary search with O(log 128) granularity. Once the summary identifies a block (e.g., “the key is between positions 128 and 256”), Cassandra performs a linear scan or another binary search within that block of the index.

Read Path in Detail

The read path is designed to minimize disk I/O through layered checking:

Parse partition key from WHERE clause
- Extract the partition key value from the CQL query.
Hash partition key to token
- Apply Murmur3: token = Murmur3(serialize(partition_key_value))
- This token determines which SSTables might contain the partition.
Check MemTable (active)
- Search the active MemTable’s skip list for the DecoratedKey(token, key).
- If found, check if the requested clustering keys / columns are present.
- MemTable contains the most recent data, so if found here, return immediately (memory access, typically < 1 microsecond).
For each SSTable (from newest to oldest):

a. Bloom filter check
- Check the partition key against the SSTable’s Bloom filter (stored in RAM, off-heap).
- If Bloom filter says “definitely not”, skip this SSTable entirely (O(1) memory lookup).
b. Partition summary lookup
- If Bloom filter says “might exist”, use the partition summary to locate an approximate block in the index.
- Binary search on the summary: O(log 128) ≈ O(7) operations.
c. Index binary search
- Read the full partition index for the identified block from Index.db.
- Perform binary search on the index to find the exact offset of the partition in Data.db.
d. Data block seek and read
- Seek to the offset in Data.db.
- Read the partition header and row data sequentially.
Merge multiple versions
- Collect the partition from the MemTable and all SSTables that contain it.
- For each row (determined by clustering key), keep only the latest version (highest timestamp).
- If a row has a tombstone marker with the highest timestamp, mark it as deleted.
- Deserialize and combine the cells into the final row.
Return merged result to client
- Construct the final result set with only the latest, non-deleted cells.

Optimization: Partition Key Cache and Index Cache

Cassandra maintains in-memory caches to accelerate repeated reads:

Partition Key Cache: Caches the offsets of partitions from frequently-accessed SSTables.
Index Cache: Caches portions of Index.db in memory.

These caches significantly reduce disk I/O for popular partitions.

Compaction Strategies

Cassandra supports multiple compaction strategies, each with different tradeoffs:

**1. Size-Tiered Compaction Strategy (STCS) **

STCS triggers compaction when the number of SSTables at a level reaches min_threshold (default: 4). All SSTables at that level are merged into a single SSTable at the next level.

Characteristics:

Write-heavy workloads benefit most.
Read amplification can be high when many SSTables accumulate.
Space amplification is high (old SSTables persist until much later compaction).
Simple to understand and tune.

2. Leveled Compaction Strategy (LCS)

LCS maintains a stricter level structure. Each level is approximately 10× the size of the previous level. When a level exceeds its size target, one SSTable from that level is merged with all overlapping SSTables from the next level.

Characteristics:

Mixed read/write workloads.
Predictable read performance: any partition is present in at most ~11 SSTables (across all levels).
Higher write amplification due to continuous compaction.
Lower space amplification; levels remain balanced.

3. Date-Tiered and Time-Window Compaction Strategies

These strategies organize SSTables by the time they were written, with each time window compacting separately.

Characteristics:

Ideal for time-series data.
Old time windows can be compacted fully and deleted as a unit.
Tombstones from different time windows don’t interfere with each other.

K-Way Merge Algorithm

When compacting, Cassandra merges K sorted SSTables using the k-way merge algorithm. This algorithm maintains a min-heap of one entry per input SSTable, always processing the globally smallest entry next.

Algorithm Overview:

Initialize: Create a min-heap with the first entry from each input SSTable.
Process: While the heap is not empty:
- Extract the smallest entry (by partition key, then clustering key).
- If it’s a new partition, write the previous partition to the output.
- If it’s a new clustering key within a partition, write the previous row.
- Compare timestamps with pending rows to keep only the latest version.
- Add the next entry from the same SSTable to the heap.
Finalize: Write remaining rows and close output.

Time Complexity: O(N × log K), where N is the total number of entries and K is the number of SSTables. For 4 SSTables with 1M entries each, this is approximately 8M heap operations—extremely efficient.

Timestamp-Based Deduplication: When the same partition + clustering key appears in multiple SSTables:

Keep the version with the highest timestamp (microsecond precision).
If timestamps are equal, pick one deterministically (e.g., by SSTable ID).
Discard older versions.

Tombstone Handling: A tombstone (a deletion marker) is removed during compaction only if:

Its timestamp is older than gc_grace_seconds (default: 10 days).
All other SSTables containing that key participate in the compaction.

This ensures that if a replica is temporarily offline, the delete can be replayed to it during repair without resurrecting the data.

Part 4: Complete Write and Read Path

Concrete Example: Inserting a JSON ObjectTable Definition:

CREATE TABLE users (
  user_id text,
  event_time timestamp,
  name text,
  age int,
  email text,
  PRIMARY KEY (user_id, event_time)
);

Insert Statement:

INSERT INTO users JSON '{"user_id": "alice123", "event_time": "2025-11-06T06:00:00Z", 
  "name": "Alice", "age": 30, "email": "alice@example.com"}' 
  USING TIMESTAMP 1730862000000000;

Step-by-Step Processing:

CQL Parser validates the INSERT JSON syntax.
JSON Deserializer converts the JSON string into a map.
Schema Resolution matches JSON keys to column names and validates types:
- user_id (text) → “alice123” ✓
- event_time (timestamp) → 1730862000000 milliseconds ✓
- name (text) → “Alice” ✓
- age (int) → 30 ✓
- email (text) → “alice@example.com” ✓

Partition Key Extraction:

Partition key: user_id = "alice123"
Token = Murmur3("alice123") = -7639649877256983472
DecoratedKey = Token + key_bytes

Clustering Key Extraction:

Clustering columns: 
Clustering value: 1730862000000 (microseconds)

Cell Creation:

Cell(name="name", timestamp=1730862000000000, ttl=null, value="Alice", is_tombstone=false)
Cell(name="age", timestamp=1730862000000000, ttl=null, value=30, is_tombstone=false)
Cell(name="email", timestamp=1730862000000000, ttl=null, value="alice@example.com", is_tombstone=false)

MemTable Insert:

MemTable.put(
  DecoratedKey(-7639649877256983472, "alice123"),
  Partition {
    rows: [Row {
      clusteringPrefix: ,
      cells: 
    }]
  }
)

Commit Log Write: Append mutation bytes to CommitLog-*.log.
Acknowledge: Return success to client.

Data Organization in MemTableThe skip list maintains sorted order:

MemTable Skip List (sorted by token):
  
  │
  ├─ Token: -7639649877256983472, Key: "alice123"
  │  └─ Partition {
  │       rows: [{
  │         clusteringPrefix: ,
  │         cells: 
  │       }]
  │     }
  │
  ├─ Token: -6234567890123456789, Key: "bob456"
  │  └─ Partition { ... }
  │
  └─

MemTable Flush to SSTable

When the MemTable reaches its size threshold, it is flushed to disk:

Index.db Output:

DecoratedKey(token=-7639649877256983472, key="alice123") → offset_1
DecoratedKey(token=-6234567890123456789, key="bob456") → offset_2
...

Summary.db Output (sparse, every 128th entry):

Entry 0: DecoratedKey(-7639649877256983472) → offset_1
Entry 1: DecoratedKey(token_128) → offset_128
...

Filter.db Output: Bloom filter with bits set for partition keys present in this SSTable.

Statistics.db Output:

{
  min_timestamp: 1730862000000000,
  max_timestamp: 1730862000000000,
  tombstone_count: 0,
  sstable_level: 0,
  ...
}

Read Path: Retrieving a RowQuery:

SELECT * FROM users WHERE user_id = 'alice123' AND event_time = 1730862000000;

Step-by-Step Read:

Parse partition key: user_id = 'alice123'
Hash: token = Murmur3('alice123') = -7639649877256983472
Check MemTable: Search skip list for DecoratedKey(-7639..., "alice123")
- Found in MemTable! Check if clustering key matches.
- Clustering key: event_time = 1730862000000 ✓ Match
- Return cells: “

Since the data is in the MemTable, no SSTable I/O occurs. Latency is < 1 microsecond.

Read Path:

After MemTable Flush (Data in SSTable)Now suppose several hours have passed, and the MemTable with Alice’s row was flushed to SSTable-0, and compaction has moved it to SSTable-5 in Level 2.

Same Query:

Parse and Hash: token = -7639649877256983472
Check MemTable: Not found (new MemTable is active).
Check Bloom filters (for each SSTable, newest first):
- SSTable-10 (Level 2): Bloom filter says “probably doesn’t exist” → skip
- SSTable-9 (Level 2): Bloom filter says “definitely doesn’t exist” → skip
- SSTable-8 (Level 2): Bloom filter says “definitely doesn’t exist” → skip
- SSTable-7 (Level 2): Bloom filter says “definitely doesn’t exist” → skip
- SSTable-6 (Level 2): Bloom filter says “definitely doesn’t exist” → skip
- SSTable-5 (Level 2): Bloom filter says “might exist” → check this SSTable ✓
Partition Summary (for SSTable-5):
- Use binary search to locate approximate block containing this token.
- Summary says: “token is between entry 128 (token=-8000…) and entry 256 (token=-6000…)”
Index Binary Search (SSTable-5’s Index.db):
- Seek to the block identified by summary.
- Binary search within that block to find exact offset of partition.
- Index says: partition is at byte offset 102400 in Data.db.
Data.db Seek and Read:
- Seek to offset 102400.
- Read partition header and row data.
- Deserialize cells: “
Merge: Only SSTable-5 contains this partition, so return its cells directly.

Total I/O: One seek to Index.db, one seek to Data.db, approximately 2-3 disk operations.

Data Flow in Cassandra’s LSM EngineWrite Flow:

JSON Input 
  → CQL Parser 
    → JSON Deserializer 
      → Schema Resolution 
        → Partition Key Hash (DecoratedKey) 
          → Clustering Key Extraction 
            → Cell Creation 
              → MemTable Insert (skip list) 
                → Commit Log Append 
                  → Acknowledge Client

Memory Representation:

ConcurrentSkipListMap<DecoratedKey, Partition>
  └─ DecoratedKey: (token, key_bytes)
    └─ Partition:
      └─ rows: Row
        └─ Row: clustering_prefix + cells
          └─ Cell: (name, timestamp_μs, ttl_sec, value_bytes, is_tombstone)

Disk Organization:

SSTable (Level L):
  ├─ Data.db: Partitions sorted by token → rows sorted by clustering
  ├─ Index.db: (DecoratedKey → offset in Data.db)
  ├─ Summary.db: Sparse sampling (1/128 entries)
  ├─ Filter.db: Bloom filter (partition keys)
  └─ Statistics.db: Metadata (timestamps, tombstones, TTLs)

Read Flow:

Query (partition key + clustering key)
  → Hash partition key to token
    → Search MemTable (O(log n) skip list)
      → If not found: Check Bloom filters (O(SSTables))
        → If positive: Partition Summary binary search (O(7))
          → Index.db binary search (O(log block_size))
            → Data.db seek (1 disk I/O)
              → Deserialize and merge versions (keep latest timestamp)
                → Return result to client

Compaction Flow:

Multiple SSTables (Level L)
  → K-way merge (min-heap algorithm, O(N log K))
    → For duplicate keys: keep highest timestamp
      → For expired tombstones: remove if gc_grace_seconds expired
        → Write merged SSTable to Level L+1
          → Delete old SSTables from Level L

Casandra

Table of Contents

Write Path in Detail

SSTable Internal Structure and On-Disk LayoutAn SSTable consists of multiple component files, each serving a specific purpose:

Data.db Layout

Index.db Layout

Summary.db (Sparse Index)

Read Path in Detail

Optimization: Partition Key Cache and Index Cache

Compaction Strategies

K-Way Merge Algorithm

Part 4: Complete Write and Read Path

Data Organization in MemTableThe skip list maintains sorted order:

MemTable Flush to SSTable

Read Path: Retrieving a RowQuery:

Read Path:

Graph View