apple / apple/foundationdb

Generic Sequential Write Detection and split logic in FDB

Open
#5,034 3 comments 0 reactions 1 assignee Claimed by @sfc-gh-jslocum View on GitHub
data distribution
Dominant language
C++
Stars
16.7k
Forks
1.6k
Avg merge
1d 20h
Merged PRs (30d)
126

Description

IF FDB could detect sequential write patterns in shards that need to be split, we could be much more efficient about handling sequential writes.

Detection:
The potential approaches for identifying a shard that is splitting sequentially are:
- looking at the storage server's byte sample for the shard to see if recent writes to the shard have been strictly increasing/decreasing in the retained history. This would be pretty simple to implement, but would be easily prone to false negatives as it is a time-bounded sample, and wouldn't identify semi-sequential workloads
- tracking the history of shard splits for this key range in the DD tracker, and checking if the previous shards that were splitting in this key range were always the leftmost/rightmost shard from the split. This would be more difficult to implement, but would generalize to semi-sequential or non-strictly sequential workloads.

Handling:
For example, if the key written in a sub-range is constantly increasing, with 100MB shards, splitting the shard evenly means FDB will move 50MB to a new shard, and then split again after another 50MB of writes, so it'd be moving 1MB for every 1MB of writes.

For example, if instead FDB split the shard 90/10, FDB would only move 10MB and then write another 90MB before splitting again. This would be 9MB of new writes to 1MB of moving data, and half as many shard splits in general.

This would only be helpful if the approach for identifying sequential writes had a low false positive and false negative rate, otherwise FDB would do extra unnecessary splits and movements.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.