Fix unbounded heap growth in the priority mempool.#8944
Merged
creachadair merged 17 commits intov0.35.xfrom Jul 7, 2022
Merged
Fix unbounded heap growth in the priority mempool.#8944creachadair merged 17 commits intov0.35.xfrom
creachadair merged 17 commits intov0.35.xfrom
Conversation
5d9dc66 to
74c70b7
Compare
Author
|
I think one of these test failures is real. I'll take a closer look in the morning. |
cmwaters
reviewed
Jul 6, 2022
Contributor
cmwaters
left a comment
There was a problem hiding this comment.
Nice work on this so far 🎉 . Left a few comments.
866c76c to
efb70ea
Compare
Author
Ok, this should be fixed now. |
Author
|
@cmwaters Thanks for all the comments! I believe all should be addressed now, please take another look to see if you agree with the adjustments. |
tychoish
reviewed
Jul 6, 2022
6b7d1ec to
1a266e5
Compare
added 13 commits
July 6, 2022 15:34
The primary effect of this change is to simplify the implementation of the priority mempool to eliminate an unbounded heap growth observed by Vega team when it was enabled in their testnet. It updates and fixes #8775. The main body of this change is to remove the auxiliary indexing structures, and use only the concurrent list structure (the same as the legacy mempool) to maintain both gossip order and priority. This means that operations that require priority information, such as block updates and insert-time evictions, require a linear scan over the mempool. This tradeoff greatly simplifies the code and eliminates the long-term heap load, at the cost of some extra CPU and short-lived working memory during CheckTx and Update calls. Rough benchmark results: - This PR: BenchmarkTxMempool_CheckTx-10 486373 2271 ns/op - Original priority mempool implementation: BenchmarkTxMempool_CheckTx-10 500302 2113 ns/op - Legacy (v0) mempool: BenchmarkCheckTx-10 364591 3571 ns/op These benchmarks are not a good proxy for production load, but at least suggest that the overhead of the implementation changes are not cause for concern. In addition: - Rework synchronization so that access to shared data structures is safe. Previously shared locks were used to exclude block updates during calls that update mempool state. Now access is properly exclusive where necessary. - Fix a bug in the recheck flow, where priority updates from the application were not correctly reflected in the index structures. - Eliminate the need for separate recheck cursors during block update. This avoids the need to explicitly invalidate elements of the concurrent list, which averts the dependency cycle that led to objects being pinned. - Clean up, clarify, and fix inaccuracies in documentation comments throughout the package.
6d9f145 to
4631f69
Compare
Contributor
williambanfield
left a comment
There was a problem hiding this comment.
Looks good. There are a few edge cases on adding a new transaction with priority / size / gas that may be worth ensuring there's a test for.
Co-authored-by: William Banfield <4561443+williambanfield@users.noreply.github.com>
Author
Yes, I plan to add tests for all those corners. Nothing so far is really exercising those conditions at all. |
williambanfield
approved these changes
Jul 7, 2022
This was referenced Jul 8, 2022
This was referenced Jul 8, 2022
creachadair
pushed a commit
that referenced
this pull request
Jul 20, 2022
This is a manual forward-port of #8944 and related fixes from v0.35.x. One difference of note is that the CheckTx response messages no longer have a field to record an error from the ABCI application. The code is set up so that these could be reported directly to the CheckTx caller, but it would be an API change, and right now a bunch of test plumbing depends on the existing semantics.
creachadair
pushed a commit
that referenced
this pull request
Jul 20, 2022
This is a manual forward-port of #8944 and related fixes from v0.35.x. One difference of note is that the CheckTx response messages no longer have a field to record an error from the ABCI application. The code is set up so that these could be reported directly to the CheckTx caller, but it would be an API change, and right now a bunch of test plumbing depends on the existing semantics.
creachadair
pushed a commit
that referenced
this pull request
Jul 20, 2022
This is a manual forward-port of #8944 and related fixes from v0.35.x. One difference of note is that the CheckTx response messages no longer have a field to record an error from the ABCI application. The code is set up so that these could be reported directly to the CheckTx caller, but it would be an API change, and right now a bunch of test plumbing depends on the existing semantics. Also fix up tests relying on implementation-specific mempool behavior. - Commit was setting the expected mempool size incorrectly. - Fix sequence test not to depend on the incorrect size.
creachadair
pushed a commit
that referenced
this pull request
Jul 20, 2022
This is a manual forward-port of #8944 and related fixes from v0.35.x. One difference of note is that the CheckTx response messages no longer have a field to record an error from the ABCI application. The code is set up so that these could be reported directly to the CheckTx caller, but it would be an API change, and right now a bunch of test plumbing depends on the existing semantics. Also fix up tests relying on implementation-specific mempool behavior. - Commit was setting the expected mempool size incorrectly. - Fix sequence test not to depend on the incorrect size.
creachadair
pushed a commit
that referenced
this pull request
Jul 20, 2022
This is a manual forward-port of #8944 and related fixes from v0.35.x. One difference of note is that the CheckTx response messages no longer have a field to record an error from the ABCI application. The code is set up so that these could be reported directly to the CheckTx caller, but it would be an API change, and right now a bunch of test plumbing depends on the existing semantics. Also fix up tests relying on implementation-specific mempool behavior. - Commit was setting the expected mempool size incorrectly. - Fix sequence test not to depend on the incorrect size.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
4 participants
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Description
The primary effect of this change is to simplify the implementation of the
priority mempool to eliminate an unbounded heap growth observed by Vega team
when it was enabled in their testnet. It updates and fixes #8775.
The main body of this change is to remove the auxiliary indexing structures,
and use only the concurrent list structure (the same as the legacy mempool) to
maintain both gossip order and priority.
This means that operations that require priority information, such as block
updates and insert-time evictions, require a linear scan over the mempool.
This tradeoff greatly simplifies the code and eliminates the long-term heap
load, at the cost of some extra CPU and short-lived working memory during
CheckTx and Update calls.
Rough benchmark results:
BenchmarkTxMempool_CheckTx-10 486373 2271 ns/op
BenchmarkTxMempool_CheckTx-10 500302 2113 ns/op
BenchmarkCheckTx-10 364591 3571 ns/op
These benchmarks are not a good proxy for production load, but at least suggest
that the overhead of the implementation changes are not cause for concern.
In addition:
Rework synchronization so that access to shared data structures is safe.
Previously shared locks were used to exclude block updates during calls that
update mempool state. Now access is properly exclusive where necessary.
Fix a bug in the recheck flow, where priority updates from the application
were not correctly reflected in the index structures.
Eliminate the need for separate recheck cursors during block update. This
avoids the need to explicitly invalidate elements of the concurrent list,
which averts the dependency cycle that led to objects being pinned.
Clean up, clarify, and fix inaccuracies in documentation comments throughout
the package.
Note to Reviewers
This change passes all the existing tests in the package (other than those eliminated by removal of the data structures they exercised). However, the existing test coverage is relatively weak, and should be improved before this code is put into production.