Transaction queue eviction policy

[thejohnfreeman]

This is an issue to continue two conversations started in PR #4022.

Randomized order within fee level

We might want dequeue transactions from the same fee level in a random order to defeat efforts to mine transaction IDs that will move transactions to the front of the queue. I'm not too worried about this for the reasons mentioned by @ximinez, but if we decide to implement this, right now I favor the idea to use the parent ledger hash to choose a random "cut" position to start iterating.

Making space in full queues

The previous question can be thought of as "how to evict transactions to be applied in the open ledger?", but this question is about how to evict transactions in the traditional sense, to be discarded. First, read the question from @mDuo13.

Now, here's one way to look at it. Imagine a global transaction queue, presiding across the entire network, with infinite size. When a transaction is submitted to the network from anywhere, it is instantly pushed into this queue. We want all validators chose the exact same first proposal by dequeuing transactions from this queue in the same deterministic, fair order. But we live in the real world, where transactions take time to propagate across the network, and queues must have finite size. The transaction queue size is an implementation detail, customizable according to the available resources of individual validators. To not let that detail disrupt our abstraction of the ideal global transaction queue, we must evict transactions that arrived earlier but appear later in the ordering we decide.

Here's another way to look at it. If the queue order changes with each parent ledger according to our answer to the first question, then a displaced transaction we discard this ledger might be first in line for the next ledger, and we'll wish we had it back. If all validators happened to see the displacing transaction last ledger, then the displaced transaction will be lost to all validators, and the submitter will have to resubmit, and they'll have to figure that out without any notification from the validators. For this reason, I think we should not displace transactions that already made it into the queue.