Skip to content

Improved sourcing first sequence scan with filter-aware walk#7553

Merged
neilalexander merged 1 commit intomainfrom
neil/sourcingwalk2
Nov 18, 2025
Merged

Improved sourcing first sequence scan with filter-aware walk#7553
neilalexander merged 1 commit intomainfrom
neil/sourcingwalk2

Conversation

@neilalexander
Copy link
Copy Markdown
Member

This PR implements LoadPrevMsgMulti, which allows us to do an efficient subject-filtered walk backwards using subject tree intersection where possible.

We then use an iterative approach for finding the sourcing starting sequences where we:

  1. Start off with sublists containing the subject filters and transform destinations of all of the sources
  2. Walk back from the last sequence using this sublist as a filter set
  3. For each source that we find the last known sourced sequence for, we can then rebuild the sublist excluding that source
  4. The search for the next source gets more efficient as the sublist gets more specific

In the included benchmark, which publishes 1000 messages, sources 1 message and then publishes a further 100,000 messages, the difference is noticeable with around a 98% improvement:

Before:

BenchmarkJetStreamScanForSources/StartingSequenceForSources-24       1	   4431625 ns/op

After:

BenchmarkJetStreamScanForSources/StartingSequenceForSources-24       1      63667 ns/op

Signed-off-by: Neil Twigg neil@nats.io

Signed-off-by: Neil Twigg <neil@nats.io>
@neilalexander neilalexander requested a review from a team as a code owner November 14, 2025 17:25
@neilalexander neilalexander requested review from a team and derekcollison and removed request for a team November 14, 2025 17:25
Copy link
Copy Markdown
Member

@MauriceVanVeen MauriceVanVeen left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

LGTM

@neilalexander neilalexander merged commit d5b3225 into main Nov 18, 2025
68 of 70 checks passed
@neilalexander neilalexander deleted the neil/sourcingwalk2 branch November 18, 2025 10:07
neilalexander added a commit that referenced this pull request Nov 26, 2025
Includes the following:

- #7553
- #7540
- #7555
- #7579
- #7578

Signed-off-by: Neil Twigg <neil@nats.io>
neilalexander added a commit that referenced this pull request Dec 18, 2025
Includes the following:

- #7553
- #7555
- #7579
- #7578
- #7581
- #7585
- #7586
- #7588
- #7593
- #7594
- #7595
- #7596
- #7597
- #7598
- #7601
- #7604
- #7605
- #7610
- #7616
- #7614
- #7622
- #7619
- #7624
- #7625
- #7627
- #7636
- #7637
- #7643
- #7648
- #7634
- #7655
- #7656

Signed-off-by: Neil Twigg <neil@nats.io>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants