needs_cleanup(), used by SSTable cleanup, is SLOW #6730
Comments
|
Not a regression, performance impact only. Not backporting. |
|
This is also related to #6662, which is a 16-second stall! So will backport. |
|
Backported to 4.0, 4.1, 4.2. |
avikivity
pushed a commit
that referenced
this issue
Aug 27, 2020
needs_cleanup() returns true if a sstable needs cleanup. Turns out it's very slow because it iterates through all the local ranges for all sstables in the set, making its complexity: O(num_sstables * local_ranges) We can optimize it by taking into account that abstract_replication_strategy documents that get_ranges() will return a list of ranges that is sorted and non-overlapping. Compaction for cleanup already takes advantage of that when checking if a given partition can be actually purged. So needs_cleanup() can be optimized into O(num_sstables * log(local_ranges)). With num_sstables=1000, RF=3, then local_ranges=256(num_tokens)*3, it means the max # of checks performed will go from 768000 to ~9584. Fixes #6730. Signed-off-by: Raphael S. Carvalho <raphaelsc@scylladb.com> Message-Id: <20200629171355.45118-2-raphaelsc@scylladb.com> (cherry picked from commit cf352e7)
avikivity
pushed a commit
that referenced
this issue
Aug 27, 2020
needs_cleanup() returns true if a sstable needs cleanup. Turns out it's very slow because it iterates through all the local ranges for all sstables in the set, making its complexity: O(num_sstables * local_ranges) We can optimize it by taking into account that abstract_replication_strategy documents that get_ranges() will return a list of ranges that is sorted and non-overlapping. Compaction for cleanup already takes advantage of that when checking if a given partition can be actually purged. So needs_cleanup() can be optimized into O(num_sstables * log(local_ranges)). With num_sstables=1000, RF=3, then local_ranges=256(num_tokens)*3, it means the max # of checks performed will go from 768000 to ~9584. Fixes #6730. Signed-off-by: Raphael S. Carvalho <raphaelsc@scylladb.com> Message-Id: <20200629171355.45118-2-raphaelsc@scylladb.com> (cherry picked from commit cf352e7)
avikivity
pushed a commit
that referenced
this issue
Aug 27, 2020
needs_cleanup() returns true if a sstable needs cleanup. Turns out it's very slow because it iterates through all the local ranges for all sstables in the set, making its complexity: O(num_sstables * local_ranges) We can optimize it by taking into account that abstract_replication_strategy documents that get_ranges() will return a list of ranges that is sorted and non-overlapping. Compaction for cleanup already takes advantage of that when checking if a given partition can be actually purged. So needs_cleanup() can be optimized into O(num_sstables * log(local_ranges)). With num_sstables=1000, RF=3, then local_ranges=256(num_tokens)*3, it means the max # of checks performed will go from 768000 to ~9584. Fixes #6730. Signed-off-by: Raphael S. Carvalho <raphaelsc@scylladb.com> Message-Id: <20200629171355.45118-2-raphaelsc@scylladb.com> (cherry picked from commit cf352e7)
asias
pushed a commit
to asias/scylla
that referenced
this issue
Apr 15, 2021
needs_cleanup() returns true if a sstable needs cleanup. Turns out it's very slow because it iterates through all the local ranges for all sstables in the set, making its complexity: O(num_sstables * local_ranges) We can optimize it by taking into account that abstract_replication_strategy documents that get_ranges() will return a list of ranges that is sorted and non-overlapping. Compaction for cleanup already takes advantage of that when checking if a given partition can be actually purged. So needs_cleanup() can be optimized into O(num_sstables * log(local_ranges)). With num_sstables=1000, RF=3, then local_ranges=256(num_tokens)*3, it means the max # of checks performed will go from 768000 to ~9584. Fixes scylladb#6730. Signed-off-by: Raphael S. Carvalho <raphaelsc@scylladb.com> Message-Id: <20200629171355.45118-2-raphaelsc@scylladb.com> (cherry picked from commit cf352e7)
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
needs_cleanup() is a procedure used for cleanup to determine whether a SSTable needs cleanup.
The problem is that it iterates through all owned ranges for each SSTable.
A node can have thousands of SSTables and number of ranges for a given node can be 756 with a RF of 3 ((RF / NODES) * (NODES * NUM TOKENS).
The complexity is O(NUM_SSTABLES * NUM_RANGES), but we can make it O(NUM_SSTABLES * LOG(NUM_RANGES)), given that ranges are sorted and non-overlapping.
The text was updated successfully, but these errors were encountered: