search

kaspanet / rusty-kaspa

Kaspa full-node and related libraries in the Rust programming language. This is a stable version at the initial rollout phases.
ISC License
371 stars 118 forks source link

Optimized Rothschild performance on high TPS #371

Closed coderofstuff closed 5 months ago

coderofstuff commented 6 months ago

Two bottlenecks were found:

  1. Hashing of TX ID causes the generation of txs (which is done serially) to significantly slow down the entire loop
  2. UTXO Selection - currently for each run of select_utxo, it will:
    • loop over all UTXOs, filtering out those that are pending
    • then select the UTXOs it hasn't used yet
    • this causes each TX generation iteration to run in O(N) time where N = # of utxos. Effectively, this means that each iteration runs an O(N x M) time, where M is the passed TPS.

Solutions implemented: Executed with --tps=1000

  1. Parallelize TX generation - hashing is a bottleneck so generating TXs seriallize will slow the entire loop down significantly. Instead of creating 1 TX per loop iteration, make the loop iteration tick ever 1 second and for each iteration create all the TXs needed in parallel.
  2. Optimize UTXO selection: Since we need to ensure we use a UTXO only once anyway, use an index tracker to track which UTXO index we should use next. This index is monotonically increasing, so it never tries to re-use the UTXOs from earlier. It only resets when the UTXO set is also refreshed.

Sample performance of new implementation:

2023-12-28 21:44:39.327-07:00 [INFO ] Tx rate: 982.6/sec, avg UTXO amount: 788482289, avg UTXOs per tx: 1, avg outs per tx: 2, estimated available UTXOs: 743223
2023-12-28 21:44:49.506-07:00 [INFO ] Tx rate: 982.4/sec, avg UTXO amount: 489091181, avg UTXOs per tx: 1, avg outs per tx: 2, estimated available UTXOs: 733223
2023-12-28 21:44:59.646-07:00 [INFO ] Tx rate: 986.2/sec, avg UTXO amount: 489082566, avg UTXOs per tx: 1, avg outs per tx: 2, estimated available UTXOs: 723223
2023-12-28 21:45:09.681-07:00 [INFO ] Tx rate: 996.5/sec, avg UTXO amount: 489081965, avg UTXOs per tx: 1, avg outs per tx: 2, estimated available UTXOs: 713223
2023-12-28 21:45:19.703-07:00 [INFO ] Tx rate: 997.8/sec, avg UTXO amount: 489081965, avg UTXOs per tx: 1, avg outs per tx: 2, estimated available UTXOs: 703223
2023-12-28 21:45:29.818-07:00 [INFO ] Tx rate: 988.6/sec, avg UTXO amount: 489079501, avg UTXOs per tx: 1, avg outs per tx: 2, estimated available UTXOs: 693223