How LevelDB Compaction Works

Basic LevelDB constraints

With the default options, LevelDB follows these basic constraints:

LevelDB has 7 levels: 0, 1, 2, 3, 4, 5, and 6.
SSTables on level 0 are about 4 MB each.
On level i (i > 0), each SSTable is at most 2 MB.
Level 0 ideally has 4 SSTables, should stay within 8, and must not exceed 12.
The total storage used by all SSTables on level i (i > 0) should stay around 10^i MB. Here, control means rough overall control, not strict enforcement.

Compaction definitions

minor compaction
Take an immtable out of memory, dump it directly into an SSTable file, then place it on level i (i >= 0) according to a placement policy. Call that policy function PickLevelForMemTableOutput().
majar compaction
From level i (i >= 0), pick one or more SSTables using a scoring function. Call that set up(i). Find SSTables on level i+1 that overlap with up(i); call that set down(i). Multi-way merge all SSTables in up(i) and down(i), then write the output SSTables entirely to level i+1. This process is called majar compaction. Call the scoring function that picks up(i) PickCompaction(i).

When minor compaction is triggered

Minor compaction runs only when all of the following are true:

During a put/delete API call, the memtable has grown beyond 4 MB.
The current immtable has already been dumped to an SSTable — that is, immtable = NULL.

When both conditions hold, the write thread blocks: the memtable is moved into the immtable, a new memtable is created for writes, and compaction of the imm table is handed off to a background thread.

When majar compaction is triggered

Major compaction is triggered when any of the following is true:

The CompactRange API is called to trigger compaction manually.
During a Get call, the first SSTable reached by the seek has exhausted its AllowedSeeks budget.
Level 0 has more than 8 SSTables.
Total storage on level i (i > 0) exceeds 10^i MB.

Case 4 usually happens after a compaction on level i leaves level i+1 violating basic LevelDB constraint 5, which triggers another compaction.

Minor compaction flow

1. sstable = MemtableDumpToSSTable(immtable);
2. i = PickLevelForMemTableOutput(sstable);
3. place SSTable to level i;
3. edit= getVersionEdit();
4. updateVersionSet();

The level-selection function PickLevelForMemTableOutput() works like this:

int PickLevelForMemTableOutput(sst){
    if( (sst overlap with Level[0])  OR (sst overlap with level[1])) 
        return 0;
    else{
        overlapBytes := calculateOverlapBytes(sst, level[2]);
        if( overlapBytes > 20M ) 
           return 0 ; 
        else 
           return 1 ;
    }
}

Majar compaction flow

MajarCompaction()

c, i := PickCompaction(); // i is level
if( up(i).size() == 1  AND down(i).size() == 0) {  // down(i) is empty set.
   overlapBytes := calculateOverlapBytes(up(i), Level[i+2]);
   if( overlapBytes <= 20M ){
      Just place up(i) to (i+1) level. 
      return;
   }
}
DoCompactionWork;  // Each merge handles about 26 MB of data.
edit = updateEdit();
updateVersionSet(edit);

DoCompactionWork(up(i), down(i))

iter: = MergeIterator(up(i), down(i));
sst := NewSStable();
while(iter.Next()){
   sst.Add(iter);
   if( (sst.bytesSize() > 2M) OR calculateOverlapBytes(sst, Level[i+2]) > 20M){
       Place sst to level i+1;
       sst := NewSSTable();
   }
}
Place sst to level i+1;

Why compaction?

miniorCompatcion() and majarCompaction() together maintain one constraint: the amount of data involved in each compaction stays around 25–26 MB.

Why 25–26 MB? I think LevelDB expects level i (i > 0) to have on the order of 10^i SSTables. If keys span [1..10^6], and keys are fairly uniform, each SSTable on level i should cover about 10^(6-i) keys. Overlap between an SSTable on level i and SSTables on level i+1 is then roughly 10 SSTables. That keeps each compaction within a controllable range: one SSTable from level i, about 10 overlapping SSTables from level i+1, plus 2 boundary SSTables — 13 SSTables in total. With a 2 MB cap per SSTable, total data is about 26 MB.

But why compaction at all?

In LevelDB’s design, writes only touch memory and append to the log sequentially. Without compaction, each full memtable would be dumped straight to level 0. Level 0 would keep accumulating SSTables — say up to 10^6. Any two SSTables on level 0 may overlap in key range, which makes reads painful: once a key might live in an SSTable on level 0, you seek the matching block, read it, and binary-search. Imagine 10^6 SSTables and 10^3 of them whose ranges contain the key. One read could require 10^3 seeks (ignoring the LRU cache) — unbearably slow.

Compaction keeps level 0 small and arranges non-zero levels into SSTables with non-overlapping ranges. GET can bound the cost of searching level 0, and on level i (i > 0) at most one random I/O is needed to tell whether the key is in that level. So the conclusion is: compaction exists to improve Get performance.

Another issue: background compaction may fall far behind writes, so level 0 can still fill up and destroy Get performance. LevelDB slows writes when level 0 reaches 8 SSTables, and blocks writes entirely when level 0 exceeds 12 SSTables until compaction catches up. So compaction trades write throughput for better GET performance.

Compaction must not break data uniformity (by which I mean: for level i (i > 0), each SSTable should overlap at most about 10 SSTables on level i+1 — or, if all keys lie in [smallest, largest], each SSTable on level i (i > 0) should cover a fair share of that range). Skewed data makes later compactions very expensive.

In short, compaction sacrifices write performance to improve get performance, and LevelDB constantly rebalances the two.

Basic LevelDB constraints#

Compaction definitions#

When minor compaction is triggered#

When majar compaction is triggered#

Minor compaction flow#

Majar compaction flow#

Why compaction?#