Stellar
Pipelining SCP: k ledgers in consensus at once (idea, prototype and data) #2066
Replies: 1 comment
|
The fee payer class stops two open ledgers from charging fees against the same old balance, but the fee payer's balance can still move in a ledger of another class. Account A can be the source of a payment op, or sign a Soroban auth entry, inside a transaction someone else pays for in N−1, while A's own transaction in N was validated against N−k. At apply, processFeeSeqNum charges std::min(acc.balance, fee) and leaves the failure to commonValid, so A's transaction keeps its place and pays whatever is left. A payment can't take A below its reserve, so with today's fees this rarely matters. In a class under surge pricing, with a clearing fee above the reserve, it lets someone hold inclusion slots for less than the other bidders pay. The Monad reserve balance rules you link are aimed at this case, and the same idea would have to cover op sources and auth entries, not only fee payers. |
Uh oh!
There was an error while loading. Please reload this page.
Hi all,
I want to share an idea I have been testing and get some feedback on it. I am not a core
developer and there is a lot about stellar-core and SCP that I don't know, so if nobody has done
this, there is probably a reason, and I would like to hear it.
In short: validators could run consensus on k ledgers at the same time, each one built on ledger
N−k, so that the time spent waiting for messages between continents is used for the next
ledgers. I built a prototype and tested it on an emulated WAN with an apply cost taken from
mainnet. With k = 2 throughput went up 1.9× for 5–8% more median latency, and k = 3 gave 2.5–2.7×
for 12–18% more. Apply is sequential and sets the ceiling: at about 1.25 ms per transaction nothing went
past about 800 tx/s.
On mainnet, consensus takes about 0.54 s (median, from a watcher node). SDF's planned overlap of
consensus and apply would bring the ledger interval down to about that. On top of it, k = 2 would
add between 1.15× and 1.55×, and k = 3 between 1.37× and 2.3×, depending on how fast validators
apply (estimates from the measured times, not runs on mainnet).
The idea
I have worked on real-time simulators, and among other things I redesigned the core that runs
the models distributed: physics, inputs and outputs run on several machines and have to stay in
sync and refresh with the right data. Some models took 20–30 ms and we needed to run at
100–200 Hz. We did it with pipelining: start the next cycle before the previous one has
finished, and make each model wait only for the data it reads, so models that don't read each
other, like the electrics and the hydraulics, also run at the same time. An example from a train
simulator (the numbers are only an example, and there were many more models):
Each result still took about as long as before, which stayed below what a person can react to,
but there were many more of them per second: an input was picked up within one short cycle
instead of waiting for the next long one, so the simulator reacted sooner and ran more smoothly.
A Stellar ledger goes through consensus (C), apply (E) and completion (S), and a validator only
starts nominating N after applying N−1, so the interval can't be shorter than C + E + S. SDF has
described plans to vote on N+1 while N is being applied
(Parallelizing stellar-core,
The road to 5000 TPS),
which brings the limit down to max(C, E). Pipelining goes one step further: a validator starts
nominating N before N−1 has externalized, so up to k ledgers are in consensus at once and the
limit becomes max((C + E + S) / k, E). It is meant to go on top of SDF's plan, not to replace it.
How it works
Everything is behind one option,
EXPERIMENTAL_LIVE_PIPELINE_DEPTH(k), that all validators setto the same value at a restart. The rules, and why each one is there:
can vote on N has applied N−k, so they all get the same answer whatever their last closed
ledger is.
modulo k), and ledger N only takes class N mod k. Otherwise an account could be charged in two
open ledgers validated against the same old balance. The key modulo k needs no state, and every
node computes the same class.
waiting for it to externalize. The target sets the pace and k the most ledgers in flight.
already has.
doesn't follow N−1's, it is raised at apply, the same way on every node.
empty, because they were validated under the old rules.
ledger only takes 1/k of them.
How I tested it
The validators run on one machine, each in its own network namespace, with
netemdelays fromapproximate public cloud round trips between seven regions on four continents (12–325 ms), plus
10% jitter, 0.1% loss and 100 Mbit/s per link. One machine makes the runs repeatable, and all
nodes share one clock, so I can follow each ledger across nodes. Two networks: seven validators
with a flat quorum (5 of 7), and twelve in four organizations of three, each organization on
three continents. Four non-validating nodes submit payments at 2,000 tx/s, more than the network
can take, so the numbers are its capacity and the validators don't spend time generating load.
The target close time is 200 ms, below consensus / k, so it is not what limits.
The disk is in RAM and payments are cheap, so apply would be almost free and pipelining would look
better than it is. So I sized each step from mainnet data:
The testbed stretches each ledger's apply to 1.25 ms per operation with a sleep (a testing option
stellar-core already has), which gives apply mainnet's duration without competing for CPU with the
extra nominations. That is also a limit of these tests, along with: one machine with 8 physical cores (host CPU at most 71%, with twelve validators at k = 3), payments instead
of real Soroban or DEX work, and network delays I chose myself.
Results
300 transactions per ledger, against the same network without pipelining (k = 1). Seven
validators: means of three runs; twelve: one run.
Latency is from when a transaction reaches a validator to the externalize of its ledger; "to
applied" adds the mean wait before apply and the
apply time.
This is how ledgers go through one validator, one row per ledger, the same 5 s of each run. Today
(k = 1) each ledger starts when the previous one has been applied. With k = 2 the consensus of
each ledger runs while the previous one is still in consensus or applying. With k = 3 apply
becomes the limit:
The interval follows, roughly,
At k = 2 it is 572 ms against 547 predicted; at k = 3, 427 ms against 375, since consensus gets a
bit slower with more ledgers in flight. From k = 4 it stays near the apply time, about 380 ms,
because apply needs the state of the previous ledger. Latency goes up because a transaction waits
for a ledger of its class whose consensus hasn't started yet, and from k = 4 ledgers also wait to
be applied. p99 grows faster than the median (4.7 s at k = 3 against 3.0 s at k = 1).
Choosing k
The target only works as a minimum, so k and the target go together: target ≈ consensus time / k.
From these runs, k = 2 with the target at about half the consensus time gives 1.9× for 5–8% more
latency, and k = 3 at about a third gives 2.5–2.7× for 12–18% more. k = 3 costs more: fee payers get
one ledger out of three, upgrades cost two empty ledgers, and more ledgers have predictable
leaders at once. Past k = 3 the gain is small and latency grows fast. And a target above
consensus / k wastes the extra ledgers: with a 500 ms target the gain stops at about 2.1× from
k = 3, and only latency grows.
Compared with bigger ledgers and with SDF's overlap
A ledger twice as big (600 transactions) without pipelining gave 402 tx/s (1.47×) with 17% more
latency, because apply also doubles and adds to the interval; k = 2 with 300 transactions gave
more with less latency. The fair comparison is SDF's overlap, which I haven't built. As an
estimate, with the interval at max(C, E): about 420 tx/s at 300 transactions against 520 with
k = 2, and about 800 tx/s at 600 transactions, the ceiling. So with the overlap a
bigger ledger also gets near the ceiling, and from my data I can't tell which has less latency.
With the mainnet numbers (C ≈ 541 ms, E between 149 and 394 ms), the formula gives, against the
overlap at about 541 ms:
These are estimates, not runs on mainnet, but they show where the gain would be: with validators
that apply fast compared with consensus.
Predictable leaders
With k ≥ 2 the nomination leaders of a ledger are known about one consensus round in advance, so
an attacker has time to target them. I can't measure how much easier that makes the attack, but I
measured what it costs when it works: each validator stays silent in the first nomination round of
every ledger where it is the top leader, as if it had been taken down for that round.
Two leaders per round mean the attacker has to take down both, and a nomination timeout close to
the measured round time (300 ms instead of 1 s) makes each lost round cheaper. Both are local
changes. A secret leader priority (a VRF) would remove the predictability itself.
What it would change for users
A transaction can wait about one consensus round for a ledger of its class. An account that pays
fees only gets into one ledger out of k, so fee sponsors and relayers would need k paying accounts
to keep their rate, and each class has its own fee market. Account keys are free, so anyone can
pile demand on one class; that only raises fees in that class. If two transactions in different
open ledgers debit the same account and there is only balance for one, the second is included and
fails (and pays), where today it would not be included; this matters for channel accounts. And
there are more ledgers per second for Horizon, RPC, indexers and archives, and for anything
measured in ledgers, like Soroban TTL or
ledgerBounds.Not done yet: protocol upgrades (the ledgers already in consensus would need checking with the
protocol they were nominated under), what the other open ledgers do if one gets stuck, catchup
and history archives with the base at N−k, and time bounds with a raised close time.
In the simulators each model waited only for the data it read; here every ledger depends on the
one k before it. Soroban transactions declare the keys they touch, so in principle a transaction
could depend only on the ledgers that touch the same keys, but all validators would have to agree
on that while those ledgers are still in consensus. I don't see how yet.
Related work
Overlapping consecutive blocks is not new. Chained HotStuff (paper,
section 5) overlaps the phases of consecutive blocks. Monad checks transactions against state
three blocks old, with "reserve balance" rules so included transactions can still pay
(asynchronous execution).
Mir-BFT (arXiv) and ISS (arXiv)
split the requests into buckets for parallel leaders, where the fee payer class comes from. I
haven't found this done with SCP's federated quorums, but I may have missed it.
Open questions
apply is close to consensus, SDF's overlap already gets most of the gain.
much does a fixed k lose?
Reports, data and a draft CAP: https://github.com/bnogalm/stellar-consensus-pipelining. The
prototype: https://github.com/bnogalm/stellar-core/tree/live-pipelining.
Thanks for reading,
Benjamín Nogal Muñoz
All reactions