tool: add lsm visualizer support for range overlap #1598
Labels
Comments
|
We have marked this issue as stale because it has been inactive for |
anish-shanbhag
added a commit
to anish-shanbhag/pebble
that referenced
this issue
Jul 15, 2024
Refactors `manifest.Annotator` to use generics and a simplified API. This eliminates the need to perform pointer manipulation and unsafe typecasting when defining a new Annotator. This change also adds the concept of a "range annotation", which is a computation that aggregates some value over a specific key range within a level. Level-wide annotations are now computed internally as a range annotation with a key range spanning the whole level. Range annotations use the same B-tree caching behavior as regular annotations, so queries remain fast even with thousands of tables because they avoid a sequential iteration over a level's files. The goal of this change is to expand and improve the Annotator interface while not changing any existing behavior. However, there are a number of potential use cases for range annotations which could be added next: - Calculating the number of keys shadowed by a tombstone-dense key range, for use in the heuristic proposed at cockroachdb#3719 - Computing the total file size that a read compaction overlaps with, which is used to prevent read compactions that are too wide [here](https:/cockroachdb/pebble/blob/9a4ea4dfc5a8129937e3fdc811ea87543d88565b/compaction_picker.go#L1930) - Estimating disk usage for a key range without having to iterate over files, which is done [here](https:/jbowens/pebble/blob/master/db.go#L2249) - Calculating average value size and compression ratio for a key range, which we [currently use when estimating the potential space that compacting point tombstones would reclaim](https:/jbowens/pebble/blob/646c6bab1af3c72dc7db59a0dcc38b5955fc15cc/table_stats.go#L350). Range annotations could also be used to implement the TODO from @jbowens. - Estimating the reclaimed space from compacting range deletions, for which we also [currently use sequential iteration](https:/jbowens/pebble/blob/master/table_stats.go#L557). - Because annotations are in-memory, if we can find a way to refactor those last two without using I/O at all, then this would eliminate the need to defer table stats collection to a separate goroutine for newly written tables. - Expand/rewrite the LSM visualizer tool (cockroachdb#508) to show overlapping ranges, as recommended in cockroachdb#1598. Range annotations would allow us to efficiently compute statistics including the # of sstables, # of keys, etc. in chunks of the keyspace and visualize this on a graph showing overlapping ranges from each level. `BenchmarkNumFilesAnnotator` shows a slight speedup over master when compared to the equivalent implementation of `orderStatistic`: ``` │ old │ new │ │ sec/op │ sec/op vs base │ NumFilesAnnotator-10 1.953µ ± 1% 1.618µ ± 3% -17.15% (p=0.002 n=6) │ old │ new │ │ B/op │ B/op vs base │ NumFilesAnnotator-10 536.0 ± 0% 544.0 ± 0% +1.49% (p=0.002 n=6) │ old │ new │ │ allocs/op │ allocs/op vs base │ NumFilesAnnotator-10 7.000 ± 0% 8.000 ± 0% +14.29% (p=0.002 n=6) ``` `BenchmarkNumFilesRangeAnnotation` shows that range annotations remain fast for arbitrary length ranges: ``` BenchmarkNumFilesRangeAnnotation-10 460471 2191 ns/op 944 B/op 7 allocs/op ```
anish-shanbhag
added a commit
to anish-shanbhag/pebble
that referenced
this issue
Jul 15, 2024
Refactors `manifest.Annotator` to use generics and a simplified API. This eliminates the need to perform pointer manipulation and unsafe typecasting when defining a new Annotator. This change also adds the concept of a "range annotation", which is a computation that aggregates some value over a specific key range within a level. Level-wide annotations are now computed internally as a range annotation with a key range spanning the whole level. Range annotations use the same B-tree caching behavior as regular annotations, so queries remain fast even with thousands of tables because they avoid a sequential iteration over a level's files. The goal of this change is to expand and improve the Annotator interface while not changing any existing behavior. However, there are a number of potential use cases for range annotations which could be added next: - Calculating the number of keys shadowed by a tombstone-dense key range, for use in the heuristic proposed at cockroachdb#3719 - Computing the total file size that a read compaction overlaps with, which is used to prevent read compactions that are too wide [here](https:/cockroachdb/pebble/blob/9a4ea4dfc5a8129937e3fdc811ea87543d88565b/compaction_picker.go#L1930) - Estimating disk usage for a key range without having to iterate over files, which is done [here](https:/jbowens/pebble/blob/master/db.go#L2249) - Calculating average value size and compression ratio for a key range, which we [currently use when estimating the potential space that compacting point tombstones would reclaim](https:/jbowens/pebble/blob/646c6bab1af3c72dc7db59a0dcc38b5955fc15cc/table_stats.go#L350). Range annotations could also be used to implement the TODO from @jbowens. - Estimating the reclaimed space from compacting range deletions, for which we also [currently use sequential iteration](https:/jbowens/pebble/blob/master/table_stats.go#L557). - Because annotations are in-memory, if we can find a way to refactor those last two without using I/O at all, then this would eliminate the need to defer table stats collection to a separate goroutine for newly written tables. - Expand/rewrite the LSM visualizer tool (cockroachdb#508) to show overlapping ranges, as recommended in cockroachdb#1598. Range annotations would allow us to efficiently compute statistics including the # of sstables, # of keys, etc. in chunks of the keyspace and visualize this on a graph showing overlapping ranges from each level. `BenchmarkNumFilesAnnotator` shows a slight speedup over master when compared to the equivalent implementation of `orderStatistic`: ``` │ old │ new │ │ sec/op │ sec/op vs base │ NumFilesAnnotator-10 1.953µ ± 1% 1.618µ ± 3% -17.15% (p=0.002 n=6) │ old │ new │ │ B/op │ B/op vs base │ NumFilesAnnotator-10 536.0 ± 0% 544.0 ± 0% +1.49% (p=0.002 n=6) │ old │ new │ │ allocs/op │ allocs/op vs base │ NumFilesAnnotator-10 7.000 ± 0% 8.000 ± 0% +14.29% (p=0.002 n=6) ``` `BenchmarkNumFilesRangeAnnotation` shows that range annotations remain fast for arbitrary length ranges: ``` BenchmarkNumFilesRangeAnnotation-10 460471 2191 ns/op 944 B/op 7 allocs/op ```
anish-shanbhag
added a commit
to anish-shanbhag/pebble
that referenced
this issue
Jul 15, 2024
Refactors `manifest.Annotator` to use generics and a simplified API. This eliminates the need to perform pointer manipulation and unsafe typecasting when defining a new Annotator. This change also adds the concept of a "range annotation", which is a computation that aggregates some value over a specific key range within a level. Level-wide annotations are now computed internally as a range annotation with a key range spanning the whole level. Range annotations use the same B-tree caching behavior as regular annotations, so queries remain fast even with thousands of tables because they avoid a sequential iteration over a level's files. The goal of this change is to expand and improve the Annotator interface while not changing any existing behavior. However, there are a number of potential use cases for range annotations which could be added next: - Calculating the number of keys shadowed by a tombstone-dense key range, for use in the heuristic proposed at cockroachdb#3719 - Computing the total file size that a read compaction overlaps with, which is used to prevent read compactions that are too wide [here](https:/cockroachdb/pebble/blob/9a4ea4dfc5a8129937e3fdc811ea87543d88565b/compaction_picker.go#L1930) - Estimating disk usage for a key range without having to iterate over files, which is done [here](https:/jbowens/pebble/blob/master/db.go#L2249) - Calculating average value size and compression ratio for a key range, which we [currently use when estimating the potential space that compacting point tombstones would reclaim](https:/jbowens/pebble/blob/646c6bab1af3c72dc7db59a0dcc38b5955fc15cc/table_stats.go#L350). Range annotations could also be used to implement the TODO from @jbowens. - Estimating the reclaimed space from compacting range deletions, for which we also [currently use sequential iteration](https:/jbowens/pebble/blob/master/table_stats.go#L557). - Because annotations are in-memory, if we can find a way to refactor those last two without using I/O at all, then this would eliminate the need to defer table stats collection to a separate goroutine for newly written tables. - Expand/rewrite the LSM visualizer tool (cockroachdb#508) to show overlapping ranges, as recommended in cockroachdb#1598. Range annotations would allow us to efficiently compute statistics including the # of sstables, # of keys, etc. in chunks of the keyspace and visualize this on a graph showing overlapping ranges from each level. `BenchmarkNumFilesAnnotator` shows a slight speedup over master when compared to the equivalent implementation of `orderStatistic`: ``` │ old │ new │ │ sec/op │ sec/op vs base │ NumFilesAnnotator-10 1.953µ ± 1% 1.618µ ± 3% -17.15% (p=0.002 n=6) │ old │ new │ │ B/op │ B/op vs base │ NumFilesAnnotator-10 536.0 ± 0% 544.0 ± 0% +1.49% (p=0.002 n=6) │ old │ new │ │ allocs/op │ allocs/op vs base │ NumFilesAnnotator-10 7.000 ± 0% 8.000 ± 0% +14.29% (p=0.002 n=6) ``` `BenchmarkNumFilesRangeAnnotation` shows that range annotations remain fast for arbitrary length ranges: ``` BenchmarkNumFilesRangeAnnotation-10 460471 2191 ns/op 944 B/op 7 allocs/op ```
anish-shanbhag
added a commit
to anish-shanbhag/pebble
that referenced
this issue
Jul 15, 2024
Refactors `manifest.Annotator` to use generics and a simplified API. This eliminates the need to perform pointer manipulation and unsafe typecasting when defining a new Annotator. This change also adds the concept of a "range annotation", which is a computation that aggregates some value over a specific key range within a level. Level-wide annotations are now computed internally as a range annotation with a key range spanning the whole level. Range annotations use the same B-tree caching behavior as regular annotations, so queries remain fast even with thousands of tables because they avoid a sequential iteration over a level's files. The goal of this change is to expand and improve the Annotator interface while not changing any existing behavior. However, there are a number of potential use cases for range annotations which could be added next: - Calculating the number of keys shadowed by a tombstone-dense key range, for use in the heuristic proposed at cockroachdb#3719 - Computing the total file size that a read compaction overlaps with, which is used to prevent read compactions that are too wide [here](https:/cockroachdb/pebble/blob/9a4ea4dfc5a8129937e3fdc811ea87543d88565b/compaction_picker.go#L1930) - Estimating disk usage for a key range without having to iterate over files, which is done [here](https:/jbowens/pebble/blob/master/db.go#L2249) - Calculating average value size and compression ratio for a key range, which we [currently use when estimating the potential space that compacting point tombstones would reclaim](https:/jbowens/pebble/blob/646c6bab1af3c72dc7db59a0dcc38b5955fc15cc/table_stats.go#L350). Range annotations could also be used to implement the TODO from @jbowens. - Estimating the reclaimed space from compacting range deletions, for which we also [currently use sequential iteration](https:/jbowens/pebble/blob/master/table_stats.go#L557). - Because annotations are in-memory, if we can find a way to refactor those last two without using I/O at all, then this would eliminate the need to defer table stats collection to a separate goroutine for newly written tables. - Expand/rewrite the LSM visualizer tool (cockroachdb#508) to show overlapping ranges, as recommended in cockroachdb#1598. Range annotations would allow us to efficiently compute statistics including the # of sstables, # of keys, etc. in chunks of the keyspace and visualize this on a graph showing overlapping ranges from each level. `BenchmarkNumFilesAnnotator` shows a slight speedup over master when compared to the equivalent implementation of `orderStatistic`: ``` │ old │ new │ │ sec/op │ sec/op vs base │ NumFilesAnnotator-10 1.953µ ± 1% 1.618µ ± 3% -17.15% (p=0.002 n=6) │ old │ new │ │ B/op │ B/op vs base │ NumFilesAnnotator-10 536.0 ± 0% 544.0 ± 0% +1.49% (p=0.002 n=6) │ old │ new │ │ allocs/op │ allocs/op vs base │ NumFilesAnnotator-10 7.000 ± 0% 8.000 ± 0% +14.29% (p=0.002 n=6) ``` `BenchmarkNumFilesRangeAnnotation` shows that range annotations remain fast for arbitrary length ranges: ``` BenchmarkNumFilesRangeAnnotation-10 460471 2191 ns/op 944 B/op 7 allocs/op ```
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
The current lsm visualizer doesn't match the files across levels by their key ranges. For example, two files in two different levels, with the exact same keyrange, may not occupy the same x coordinate on the screen.
The current method of visualization is also useful, but having both methods available will aid in investigations.
The text was updated successfully, but these errors were encountered: