mempool: Separate reactor from implementation #1043

hvanz · 2023-06-28T08:54:41Z

Closes #1042
Depends on #1010

In Mempool interface:

Add NewIterator for iterating the mempool entries
Add SetLogger

Changes in the mempool reactor:

NewReactor now takes a Mempool interface as a parameter, instead of CListMempool,
replace calls to implementation specific methods such as TxsWaitChan and TxsFront for iterating through CListMempool's entries,
remove calls to methods NextWaitChan and Next from mempoolTx.

PR checklist

Tests written/updated
Changelog entry added in .changelog (we use unclog to manage our changelog)
Updated relevant documentation (docs/ or spec/) and code comments

This reverts commit d3468a1.

mempool/reactor.go

mempool/mempool.go

lasarojc · 2023-07-03T20:51:34Z

mempool/clist_mempool.go

+	// Concurrent linked-list of valid txs.
+	// `txsMap`: txKey -> CElement is for quick access to txs.
+	// Transactions in both `txs` and `txsMap` must to be kept in sync.
+	txs    *clist.CList


When generating documentation from code, it will be confusing if the comment is related to two fields. I suggest commenting both, even if there is some redundancy.

Suggested change

// Concurrent linked-list of valid txs.

// `txsMap`: txKey -> CElement is for quick access to txs.

// Transactions in both `txs` and `txsMap` must to be kept in sync.

txs *clist.CList

// Concurrent linked-list of valid txs.

// `txs` must to be kept in sync with `txsMap` .

txs *clist.CList

// `txsMap`: txKey -> CElement is for quick access to txs.

// `txsMap` must to be kept in sync with `txs` .

mempool/clist_mempool.go

cason

I would use here the same arguments I have presented for PR #1010:
#1010 (review)

I think we should define and discuss a new mempool API before implementing the (breaking) changes in multiple PRs.

lasarojc

There seems to be a problem in the loop over the transactions, causing transactions to be skipped and violating the expected delivery order.
PR #1153 adds a test to show the problem and addresses the issue by bring the test for nil back.

mempool/reactor.go

mempool/mempool.go

mempool/reactor.go

Co-authored-by: Lasaro <lasaro@informal.systems>

* Adding a test for when peers are late * passes the test added in the previous commit * passes the test added in the previous commit * Fix iteration and typo * Making the sleep dependendant on a smaller sleep we want to wait for

otrack

I believe that changing CheckTx is necessary. The current interface is not sound: it takes as input a callback cb which will be later called by another callback. This pattern is non-stanadrd and unecessarily complex. Moreover, cb necessarily lives outside of the mempool. This should be avoided because changes against the mempool must be thread safe.

The new interface @hvanz is proposing returns a promise. The promise captures the fact that the side effects of CheckTx are applied asynchronously. This change to the interface is not breaking because mempool#CheckTx is only used internally.

On the other hand, I am not in favor of the introduction of the CListIterator, modifying the way the reactor accesses the mempool. As indicated in my review, this change is not trivial because the underlying list is a non-standard concurrent list. I recommend to add these changes in a different commit with proper testing on them. Even better, before doing that, I recommend to actually model and verify the clist abstraction.

otrack · 2023-07-24T10:37:01Z

mempool/clist_mempool.go

@@ -130,6 +152,18 @@ func (mem *CListMempool) EnableTxsAvailable() {
 	mem.txsAvailable = make(chan struct{}, 1)
 }

+func (mem *CListMempool) SetTxRemovedCallback(cb func(txKey types.TxKey)) {
+	mem.removeTxOnReactorCb = cb


This is a very restrictive interface. Add some defensive programming here, by checking it was not set already. Document what is expected. Visibility would be package level (but this does not exist in golang.)

otrack · 2023-07-24T10:41:31Z

mempool/clist_mempool.go

-// Safe for concurrent use by multiple goroutines.
-func (mem *CListMempool) TxsWaitChan() <-chan struct{} {
-	return mem.txs.WaitChan()
+func (mem *CListMempool) NewIterator() Iterator {


Document this. As above, explain that it is a restricted interface.

otrack · 2023-07-24T10:49:55Z

mempool/clist_mempool.go

-	mem.txsMap.Store(memTx.tx.Key(), e)
-	atomic.AddInt64(&mem.txsBytes, int64(len(memTx.tx)))
-	mem.metrics.TxSizeBytes.Observe(float64(len(memTx.tx)))
+func (mem *CListMempool) addTx(entry *Entry) {


Comment this method.

I suggest to pack methods according to their visibility levels, e.g., first public ones then private ones. Mixing things makes understanding the code difficult.

I agree with sorting the methods by visibility, but this will require to change most of the file, and I don't want to do it in this PR.

otrack · 2023-07-24T15:33:02Z

mempool/clist_mempool.go

+	lastElement        *clist.CElement // last accessed element in the list
+	nextEntryAvailable chan struct{}   // channel to communicate that there is at least one entry available
+	mtx                sync.RWMutex
+}


I would move this code to CList.

There is no need to for the iterator to be thread safe. Each peer has its own iterator. Hence, the mtx field can be dropped.

Besides that, I do not understand the logic of the nextEntryAvailable field.

otrack · 2023-07-24T15:58:41Z

mempool/clist_mempool.go

+	}
+
+	return iter.lastElement.Value.(*Entry)
+}


I am concernend about this set of changes, regarding how the reactor iterates over the mempool. They should be part of a different commit.

Overall, this is non-trivial code. The underlying list is a non-standard concurrent list (not à la M. Scott). As a consequence, we should be very cautious when using it. At the very least, this new way to iterate should be tested in unit tests. I would even recommend to actually model the clist with Quint, before adding an iterator atop it.

lasarojc · 2023-07-27T11:18:47Z

Depends on #1169
This PR is intermittently failing some new tests. We moved the tests to a different branch to merge them first into main and will continue work here after that or later.
No other work is blocked by this PR, which is a nice to have.

hvanz · 2023-12-14T09:31:03Z

Closing this PR as it is not clear that the proposed solution is correct.

The main change introduced by this PR is an iterator for CListMempool. This is the main modification needed in the Mempool interface to clearly separate the reactor, which should only deal with the gossip protocol, from CListMempool, the actual pool of txs. We should revisit this issue in the context of modularising the Comet codebase (#42).

In the proposed solution, there is an iterator for each peer that reads from CListMempool. This adds to the complexity of the concurrent accesses to CListMempool and its underlying concurrent list clist. Although the intention was not to change the code logic, just to do a refactoring, it is possible that the new iterator may change the way the reactor access transactions. In a future attempt, it is advisable to clearly specify all concurrent accesses to CListMempool. As it was suggested above, a formal model of the clist implementation would also help.

hvanz and others added 22 commits June 20, 2023 18:58

Move senders from txs to txSenders

fde2cc0

Move resCbFirstTime to globalCb

ca8463a

Fix typo

ed6e965

Remove callback argument from CheckTx

90e147c

Fix lint

66d7add

make mocks

e837a60

lock isSender

99c95fe

Change sync.Map for map with lock; add test

c187130

fix lint

93a3f0b

comments

d8f0bb3

move senders to reactor and add txsRemoved channel

6f1d121

Record sender only on valid txs

7dabdb8

Merge branch 'main' into hvanz/mempool-senders

7bae8a6

fix MConnection panicked

4fa9d5b

notifyTxRemoved when removeAllTxs

e917f0e

Add TxsRemoved and EnableTxsRemoved to interface

0c58f32

Increase channel buffer size

d8a0b88

forgot emptyMempool

ec337ed

Change Mempool interface

d3468a1

Revert "Change Mempool interface"

4ff3e83

This reverts commit d3468a1.

Fix lint

9c3e197

Comments

547fec3

hvanz added the mempool label Jun 28, 2023

hvanz added this to the 2023-Q3 milestone Jun 28, 2023

hvanz self-assigned this Jun 28, 2023

hvanz removed this from the 2023-Q3 milestone Jun 29, 2023

lasarojc reviewed Jul 3, 2023

View reviewed changes

hvanz mentioned this pull request Jul 4, 2023

Consolidate existing mempool specs and documentation #1076

Closed

hvanz added 2 commits July 4, 2023 11:11

notify txRemoved even when txKey is not in txsMap

59454cc

Replace EnableTxsAvailable and EnableTxsRemoved by InitChannels

3944f74

hvanz changed the title ~~mempool: Separate reactor from implementation (WIP)~~ mempool: Separate reactor from implementation Jul 19, 2023

Merge branch 'main' into hvanz/mempool-interface

d266cae

hvanz mentioned this pull request Jul 19, 2023

mempool: Remove list of peer ids in reactor #1146

Closed

hvanz marked this pull request as ready for review July 19, 2023 15:58

hvanz requested a review from a team as a code owner July 19, 2023 15:58

hvanz requested a review from a team July 19, 2023 15:58

hvanz removed the wip Work in progress label Jul 19, 2023

cason reviewed Jul 20, 2023

View reviewed changes

lasarojc suggested changes Jul 21, 2023

View reviewed changes

mempool/reactor.go Outdated Show resolved Hide resolved

mempool/reactor.go Show resolved Hide resolved

mempool/mempool.go Outdated Show resolved Hide resolved

otrack reviewed Jul 24, 2023

View reviewed changes

mempool/reactor.go Outdated Show resolved Hide resolved

hvanz and others added 3 commits July 24, 2023 16:01

Apply suggestions from code review

f7cbf62

Co-authored-by: Lasaro <lasaro@informal.systems>

Adding a test for when peers are late (#1153)

6ff73f8

* Adding a test for when peers are late * passes the test added in the previous commit * passes the test added in the previous commit * Fix iteration and typo * Making the sleep dependendant on a smaller sleep we want to wait for

Add changelog

02b8fca

otrack suggested changes Jul 24, 2023

View reviewed changes

lasarojc and others added 8 commits July 24, 2023 17:20

adding an extra check

99e42a7

Reactor takes interface instead of CListMempool

661a9ad

Improve tests

486e0ff

Merge branch 'main' into hvanz/mempool-interface

c8d8573

Comments

1f11afd

Remove unused TxsFront function

100e852

Comments

08dc4ea

Improve tests

dd36fc4

hvanz mentioned this pull request Jul 26, 2023

mempool: test FIFO ordering when disseminating txs #1169

Closed

3 tasks

thanethomson added the wip Work in progress label Jul 31, 2023

lasarojc mentioned this pull request Aug 1, 2023

Add support for fast prototyping #1059

Closed

hvanz added a commit that referenced this pull request Aug 3, 2023

Revert #1043

a06a5bf

hvanz closed this Dec 14, 2023

hvanz deleted the hvanz/mempool-interface branch July 11, 2024 15:30

mempool: Separate reactor from implementation #1043

mempool: Separate reactor from implementation #1043

Uh oh!

Conversation

hvanz commented Jun 28, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

PR checklist

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

lasarojc Jul 3, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

cason left a comment

Choose a reason for hiding this comment

Uh oh!

lasarojc left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

otrack left a comment

Choose a reason for hiding this comment

Uh oh!

otrack Jul 24, 2023

Choose a reason for hiding this comment

Uh oh!

otrack Jul 24, 2023

Choose a reason for hiding this comment

Uh oh!

otrack Jul 24, 2023

Choose a reason for hiding this comment

Uh oh!

hvanz Jul 25, 2023

Choose a reason for hiding this comment

Uh oh!

otrack Jul 24, 2023

Choose a reason for hiding this comment

Uh oh!

otrack Jul 24, 2023

Choose a reason for hiding this comment

Uh oh!

lasarojc commented Jul 27, 2023

Uh oh!

hvanz commented Dec 14, 2023

Uh oh!

Uh oh!

hvanz commented Jun 28, 2023 •

edited

Loading

lasarojc Jul 3, 2023 •

edited

Loading