dragonflydb / dragonflydb/dragonfly

serialize segment directory during full sync / dfs snapshotting

Open
#5,355 0 comments 0 reactions 0 assignees View on GitHub
enhancement
Dominant language
C++
Stars
31.5k
Forks
1.3k
Avg merge
1d 10h
Merged PRs (30d)
137

Description

## Background

Currently we do not have the ability to preallocate DashTable segments during the snapshot load or the full sync load on replica side because segment directory in DashTable is in fact a binary tree of depth `k` encoded into an array of size `2^k`.
See here how segments are split:
https://docs.google.com/presentation/d/1w6KyMmPVfgEN7kYiCf7wOw2U_XfsSdad1bVq0RKWsBE/edit?usp=sharing

Consider the following case: table with 8 segments overall, 4 distinct.
S1, S1, S1, S1, S2, S3, S4, S4
/* This corresponds to the tree:
```
R
/ \
S1 /\
/\ S4
S2 S3
```

but of course there are many other variations of trees. Therefore a single number of elements does not allow us to preallocate the original tree on the destination server.

## Goal
Encode Segment tree information for DFS snapshot (not rdb) or the replication so that the loader will be able to recreate the tree.

1. `DashTable::IterateDistinct` (bad name - should be renamed to `IterateDistinctSegments`) iterates over all the unique segments. Segment::local_depth() and Segment::segment_id() are enough to serialize the tree.
So in the example above: `(S1, 1), (S2, 3), (S3, 3), (S4, 2) ` are enough to encode the tree topology.
2. We should introduce an additional `RDB_` opcode to pass all the unique segments and their local depths on the save side.
3. We should support this on the loader side.
4. DashTable currenty lacks the ability to grow itself based on the series of segments and their local depths. We should add this API and allow the loader to preallocate the segments.

## Notes
* (2) should be under flag that is disabled by default as we do not want to break snapshot compatibility with the older versions.
* For replication we manage compatibility automatically using `DflyVersion` that is communicated by replica.

While this improvement helps with Load performance in general, it's very important for tiering algorithms that need to decide which items to offload during the snapshot load and preallocating dashtable is important for them.

Contributor guide

Open the contributing guide

Research direction

Start with DashTable::IterateDistinct and the Segment::local_depth() and Segment::segment_id() APIs to understand the tree representation. Trace the DFS snapshot and replication save/load paths, including the RDB_ opcode and DflyVersion compatibility handling. Done means the loader can recreate and preallocate the segment tree without breaking older snapshot compatibility.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
databases, distributed-systems
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
30/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.