TransactionQueue improvements

[gavofyork]

• Keep transactions in persistent storage
• Future becomes a fixed-size rotating pool
• Current retains present priority mechanism
• RPC for rebroadcasting (a) transaction(s)
• RPC for inspecting queue contents txpool API
• RPC for getting effective next nonce, taking into account queue

[tomusdrw]

My thoughts:

// List of all transactions
transactions: HashMap<Address, BTreeMap<U256, Rc<VerifiedTransaction>>>

// Transaction and it's location.
// We store copies of handles to easily find transactions in queues (for removal / re-insertion)
LocalizedTransaction {
    transaction: Rc<VerifiedTransaction>, // Seems it's not needed.
    location: Current(TransactionHandle)/Future(FutureTransactionHandle)
}

// Current (with limit)
// Ordered by:
// 1. Sender priority (local transactions / reimported transactions / penalized transactions)
// 2. Nonce Height (nonce - state_nonce)
// 3. Gas Price
// 4. Hash
current: PriorityQueue<TransactionHandle>

TransactionHandle {
    transaction: Rc<VerifiedTransaction>,
    nonce_height: U256,
    priority: Local/RetractedBlock/External/GasLimitReached,
}

// Future (with limit)
// Ordered by:
// 1. Sender priority
// - stalled senders (occupies future, but transactions were not moved to Current for a long time) should be penalized
// 2. Nonce Height
// 3. Gas Price
// 4. Hash
future: PriorityQueue<FutureTransactionHandle>

FutureTransactionHandle {
    transaction: Rc<VerifiedTransaction>,
    nonce_height: U256,
    priority: u64 //(block number at insertion time; higher is better)
}
/*
Notes:
1. Priorities (in C & F) always have to be updated for all transactions from particular sender.
2. Each import/removal needs to update `nonce_heights` (perhaps could be optimized if it doesn't change).
*/

[ghost]

+1. (Following closely the issue). Need an implementer?

[gavofyork]

help always welcome :)

[rphmeier]

Going to tackle point 1 (fixed storage). I think this would be a good opportunity to include a "node_data" column in the database for storing stuff like node sync security level and the state of the transaction queue on shutdown/startup. Our 1.6 database can already become incompatible with previous versions (as seen with the change in receipts format), so this will only serve to solidify an implicit one-way migration.

[dot-punto-dot]

+1

[eira-fransham]

Idea:

Current available queue is HashMap<Sender, Vec<Rc<Run>>>, where each Run is a struct containing a tx and some information about the previous txs. So building a Run looks like this:

Run {
    tx: some_tx,
    run_number: previous_run.run_number + 1,
    previous_cost: previous_run.total_cost(),
}

where total_cost is self.tx.cost + self.previous_cost. We can then order Runs by average_cost(), which is total_cost() / run_number. This handles the case where bringing N sequential txs may give a high payout but the first tx may be very cheap.

To order the Runs in a quickly-accessible way we can use a priority queue of Weak<Run>s. We can probably store the Sender on the Run so that when it's pulled out of the transaction queue we can index into the HashMap and drain the Vec until we reach the correct Run, using try_unwrap to take ownership of each in turn so that the Rc gets dropped and the Weaks get invalidated. We might want to write an Rc replacement that only allows a single strong reference, so that we don't have to handle try_unwrap failing (because it never can).

[eira-fransham]

Dirty hacky O(bad) implementation of my idea here. Seems to work well, I don't know if I'm missing something or misunderstanding the requirements.

EDIT: Slightly less awful implementation here, it's still got serious problems though. From talking on IRC it looks like BTreeMap's not getting drain any time soon.

[tomusdrw]

@Vurich If I understand correctly implemenetation of Ord might change with time (some transactions get removed and Weak<> pointers invalid. If I'm not mistaken this will lead to a invalid queue - in that case the Heap property won't be satisfied. Also some methods implementations are missing (like cull(user_id, nonce) removing all transactions from particular user with <nonce)

[eira-fransham]

Yeah, it's dirty and hacky to prove the concept. I think the right way would be to store the average when it's created, since they're not edited after creation. I want to be able to drain the transactions when you pop, but BTreeMap doesn't have a drain method.

[debris]

I'm closing it, cause the new transaction queue was merged in #8074