Generic Sequential Write Detection and split logic in FDB
- 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
Assessment
This issue has not been assessed yet.