Proposal: Range-free Compaction

[silentred]

Summary

We propose a new compaction method that reduces the time required for etcdserver compaction and decreases I/O consumption during the compaction process.

Motivation

Thanks to performance optimizations in freepage allocation within BoltDB, etcdserver now supports database sizes of up to approximately 100 GB. However, large databases are highly unfavorable for compaction: each compaction operation must traverse all revisions in the entire database, regardless of how much data has actually been updated. This leads to two major issues:

1. Traversing the entire database generates substantial I/O load—monitoring tools often show I/O utilization approaching 100%, which negatively impacts concurrent read and write requests.
2. After traversing every CompactionBatchLimit number of revisions, the compaction process sleeps for a duration of CompactionSleepInterval. This can result in significant unnecessary sleep periods, as many traversed revision ranges may contain no historical data requiring cleanup.

We introduce a novel compaction implementation that avoids these problems while preserving data correctness.

Proposal

Overview of range-free compaction

The current compaction logic consists of two parts:

• treeIndex executes the Compact method, traverses all keyIndex objects, determines the set of revisions that need to be retained in the current state, and returns this set.
• store traverses all revisions in the database, checks each revision against the retained set, deletes unreferenced revisions, and commits the deletions in batches.

The proposed Range-free Compaction logic works as follows:

• The Index directly computes the set of revisions to be deleted and returns this set.
• The store receives this set of revisions, sorts them, deletes them sequentially, and commits the deletions in batches.

Details

Changes of keyIndex

Modify the compact method signature to add a new return parameter: delete map[Revision]struct{}, which represents the set of revisions to be deleted for a single keyIndex after compaction.

-func (ki *keyIndex) compact(lg *zap.Logger, atRev int64, available map[Revision]struct{}) {

+func (ki *keyIndex) compact(lg *zap.Logger, atRev int64, available map[Revision]struct{}, delete map[Revision]struct{}) {

Changes of Index interface

Update the Index interface’s Compact method to include an additional parameter that carries the set of revisions to be deleted after treeIndex compaction.

-func (ti *treeIndex) Compact(rev int64) map[Revision]struct{} {

+func (ti *treeIndex) Compact(rev int64) (map[Revision]struct{}, map[Revision]struct{}) {

Changes of db compaction

Add a new method *store.scheduleCompactionRangeFree with the following logic.

func (s *store) scheduleCompactionRangeFree(compactMainRev, prevCompactRev int64) (KeyValueHash, error) {
	// Use Compact to get revisions to delete and perform index compaction
	_, toDelete := s.kvindex.Compact(compactMainRev)

	// Convert toDelete map to sorted slice for deterministic iteration
	revs := toSlice(toDelete)
    sort(revs)

	// Process deletions in batches
	for _, rev := range revs {
		// Delete the revision directly
		tx.UnsafeDelete(schema.Key, keyBytes)
		
		// Commit in batches
		if deletedCount%batchNum == 0 {
			s.b.ForceCommit()
			//sleep some time
		}
	}

	UnsafeSetFinishedCompact(tx, compactMainRev)
	return hash, nil
}

Backward Compatibility

Incompatibable KeyValueHash

Since range-free compaction does not traverse revision data, the hash computation logic is incompatible with the previous approach. This incompatibility is a significant issue if the user has enabled corrupt check.

Correctness

We need to update certain unit tests to ensure the correctness of compaction in keyIndex, treeIndex, and store. We also need to verify that the results of the new compaction method are consistent with those of the current implementation. The test logic is as follows:

1. Create a new store.
2. Write a fixed set of data, randomly triggering compaction operations during the process.
3. Perform a final compaction, iterate through all data, compute a hash, and then close the store.
4. Create another new store that uses range-free compaction.
5. Repeat steps 2 and 3 to obtain a new hash, and compare it with the previous hash to ensure data consistency.

FeatureGate

This new feature can be enabled via a FeatureGate, allowing users to opt in or out at their discretion.
Performence

Performence

conditions:

• Total 2M keys, each value size is 4K
• total dbsize 40GB

server flags:

--auto-compaction-retention=5m 
--backend-batch-interval=100ms
--backend-batch-limit=1000

client write command:

while true; do _build/benchmark put --endpoints=http://127.0.0.1:3379,http://127.0.0.1:23379,http://127.0.0.1:33379 --clients 100 --conns 20 --key-size 128 --val-size 4000 --total 2000000 --key-space-size 2000000 --key-prefix aa --rate 7000 --sequential-keys ; done

TPS of Put	cost time of original compact	cost time of range-free compact	improvement
1K/s	32.140923178s	6.051189144s	72%
2K/s	38.630751905s	12.803279511s	68%
5K/s	1m0.072742644s	31.387194197s	48%
7K/s	1m20.295984944s	42.799126317s	47%

[serathius]

The sleeps are critical to maintain availability during compaction. Please read previous issues discussing compaction.

[silentred]

The sleeps are critical to maintain availability during compaction. Please read previous issues discussing compaction.

I agree. This proposal is talking about meaningless sleep and IO.

[silentred]

cc @ahrtr @fuweid , would like to hear suggestions from you guys.

[serathius]

My understanding is the proposal is split the compaction, and move the identification of keys for deletion outside the delete for loop. The expected result is better performance because we stop batching reads and just execute one read at the beginning.

Overall I think it might work as the compaction implementation is very naive, there should be a lot of potential to optimize it.. The scope of changes is pretty small, mostly scheduleCompaction so I don't have anything against trying to optimize it.

My recommendation would be to start from preparing tests and microbenchmarks for scheduleCompaction function. Benchmark should provide accurate representation of real scenarios so we can measure impact on real production performance. Then we can go bonkers with optimizing it.

[ahrtr]

The proposed Range-free Compaction logic works as follows:

• The Index directly computes the set of revisions to be deleted and returns this set.
• The store receives this set of revisions, sorts them, deletes them sequentially, and commits the deletions in batches.

I think this is a good improvement for compaction only. But it breaks the CompactHash as you already mentioned. Essentially it decouples the two operations: compaction and hash calculation. We can move the compaction based hash calculation into a separate goroutine, which needs some coordination.

Also it may increase the memory usage if there is no compaction for a long time. This should be fine to K8s as the default compaction interval is 5 min.

[silentred]

We can move the compaction based hash calculation into a separate goroutine

Thanks, got what you meant.

[serathius]

Also it may increase the memory usage if there is no compaction for a long time.

I was not concerned by memory as the key sizes stored are small (just revision) compared to the whole database and whether we track entries to keep vs entries to delete should not matter, their number depends on traffic. For clients that reuse 1 key, delete will have all revisions while keep will be empty. For clients that use unique keys, delete will be empty and keep will have all keys.

[ahrtr]

But it breaks the CompactHash as you already mentioned. Essentially it decouples the two operations: compaction and hash calculation. We can move the compaction based hash calculation into a separate goroutine, which needs some coordination.

Caveats:

• It may increase the overall complexity, as we need to maintain compatibility with older versions. In particular, we must ensure that deleted K/V pairs are still included when calculating the hash; otherwise, it may generate false alarms.

• It also introduces additional coordination complexity. For example, what happens if the hash calculation triggered by compaction has not finished before the next compaction starts? These edge cases need to be carefully handled.

If this change introduces significant complexity, we may ultimately decide not to proceed with it. We’ll evaluate it further if a draft PR is available.

[silentred]

@ahrtr Thanks for the advice. I am working on a draft PR.