cockroachdb / cockroachdb/cockroach
rangefeed: registration overhead within a range for is O(disjoint_subscriptions^3)
- Dominant language
- Go
- Stars
- 32.5k
- Forks
- 4.1k
- PR merge metrics
- PR metrics pending
Description
Whenever a range's subscriptions change it reconstructs a filter. It does this by looping over a tree of spans and adds them all to a linked list. This operation is O(n^2) because the linked list and the tree are sorted, so every insertion ends up having to scan to the end of the linked list. Additionally, since we run this once per registration, the total overhead for registration is O(n^3).
This typically isn't much of a problem because most rangefeeds cover the entire range or one span of the range. But it is an issue for db level changefeed with rangefeed coalescing since we can end up with many small feeds over the same range.
We already have a btree span implementation and using it in place of the linked list should make each registration O(n * log n) instead of O(n^2), which is still a little slower than it needs to be, but a significant improvement for how light the lift is. Using a btree for the span list should also help when consulting the filter, since it turns that into a O(log n) operation instead of O(n).
This was noticed while debugging https://github.com/cockroachdb/cockroach/issues/162571.
Jira issue: CRDB-60468
Epic CRDB-62481
Contributor guide
Assessment
This issue has not been assessed yet.