services/horizon: Update txsub queue to account for new CAP-21 preconditions

[Shaptic]

The rules that make a transaction’s sequence number valid have changed considerably. As such, the transaction submission queue will need changes. Horizon will have a harder time “helping” submitters by ordering their transactions, waiting for particular sequence numbers, etc. However, this only happens in the case in which transactions have the minSeqNum condition set, which is not expected to be a large portion.

Today Horizon orders transactions by sequence, then submits the lowest one in that queue if it equals the next expected sequence on the account. With CAP-21 loosening the validity conditions, Horizon needs to allow gaps in sequence numbers (rather than strict increments), though it should still order them in ascending order.

The necessary changes are minor: if the next transaction in the queue has a minSeqNum condition set, we also check if:

account.seqNum < tx.seqNum && account.seqNum >= tx.minSeqNum - 1

[2opremio]

though it should still order them in ascending order.

Do you mean we should still order them by tx.seqNum regardless of whether tx.minSeqNum is defined?

That doesn't really make sense to me.

[Shaptic]

What's the issue you see, @2opremio? I think we want there to be as few gaps as is possible, so we should order by tx.seqNum whenever we can, and execute/submit the queue earlier if a minSeqNum condition is present and met.

Consider the following set of transactions:

• A: seqNum = 1
• B: seqNum = 3
• C: seqNum = 4, minSeqNum = 2
• D: seqNum = 2

Ordering it as

A, D, C, B

will cause tx2 to fail, while ordering it as

A, D, B, C

results in all of them succeeding. However, we can't know ahead of time that B exists, so if the transactions arrive as ADC, then we would execute them immediately and B would eventually fail. If ADB arrive first, we can execute them (since they're sorted and incrementing) and C later.

[leighmcculloch]

Is it correct, that we order by tx.seqNum today? I believe that is correct, from a clients perspective, even if it is by happenstance of the existing seqnum constraint. We should preserve that behavior so that we don't break clients relying on it.

[2opremio]

Is it correct, that we order by tx.seqNum today? I believe that is correct, from a clients perspective, even if it is by happenstance of the existing seqnum constraint.

It is correct, we should maintain the semantics but not necessarily the internal order, which is what I am referring to.

What's the issue you see, @2opremio?

If you use a priority queue ordered by tx.seqNum (and leaving minSeqNum aside) your ordering maximizes the amount of transactions in the queue you can send out (due to the resulting account sequence). This, in theory, is a good thing and works well with strict ordering (without minseq) but doesn't hold when introducing minSeq.

Introducing minSeq, adds the need to traverse the full priority queue (i.e. making it not a queue anymore) in case there is a minSeq later on which allows you to send a transaction.

Let (minSeq, seq) be a transaction in the queue. Here is a transaction queue ordered strictly by seq.

[(nil, 9), (nil, 10), (1, 20)] (further left means higher prio)

Let's assume that the initial account sequence is 7.

You can no longer look at (nil, 9) (not submittable) and conclude you are done . There's (1, 20) is at the end and allows submitting, which you won't know unless you traverse the whole queue (i.e. now not a queue).

If we order by minSeq (seq if minseq is nil) we get

[(1, 20), (nil, 9), (nil, 10)]

Doing that, we can look at (1, 20) right away and submit the transaction. If successful, the account gets a sequence of 20. (nil, 9) and (nil, 10) will end up getting a badseqnum error, since they cannot be submitted.

Things turn around if we set the initial account sequence to 8:

If we order by seq, we get [(nil, 9), (nil, 10), (1, 20)] which is the sequence we expect since it makes all transactions submit-table.

But ... if we order by minSeq we get [(1, 20), (nil, 9), (nil, 10)] which unfortunately doesn't allow sending (nil, 9) and (nil, 10) since after sending (1, 20) the account sequence gets bumped to 20.

So, either I am missing something or using a transaction priority queue ordered by seqNum doesn't really cut it.

[2opremio]

Anyways, it's an implementation detail, but I don't see other way but to traverse the full queue every time :S

[2opremio]

Implemented here: #4301

[Shaptic]

Closed by #4301 👏