Redesign of block-producer
#480
Replies: 8 comments 16 replies
-
Fault toleranceI think this requires having a dependency graph which associates transactions, batches and notes together in a way that they are reversible. This should be possible to implement without really affecting the design of anything else. In a way this could be an extension of the current inflight constraints system. Something that does bother me though - is it possible for a submitted transaction to fail after we've accepted it? e.g. a transaction/note that must be consumed within |
Beta Was this translation helpful? Give feedback.
-
This was (briefly) touched on here, and of course success isn't possible to guarantee. |
Beta Was this translation helpful? Give feedback.
-
|
Requiring a dependency graph implies to me that we need centralized logic to orchestrate things, but maybe these can be encoded into the types somehow instead of stored in a central location. e.g. creating the graph using smart pointers which travel alongside the data. |
Beta Was this translation helpful? Give feedback.
-
Yes, this is possible, and I'm actually thinking this may be a "recommended practice" for the clients. For example, when the client sends a transaction to the network, it could indicate that a transaction must be included in the next 10 blocks or not included at all. This way, if a transaction is not included in the next 10 blocks, the client can safely assume that it has been canceled (and maybe retry the transaction with a higher fee or something). If a transaction does not have an "expiration time", then it may be difficult for the client to tell if a transaction has been dropped by the network for some reason or if it is stack in the queue. But maybe I'm overthinking this. |
Beta Was this translation helpful? Give feedback.
-
Block building costs & latencyWhat parts are expensive to perform? For example, if we have a bundle of batches ready to submit as a block, do we expect the block sealing to be quick enough that we just do it inline before submitting it to the store? Or is that something to spawn as a task and await elsewhere before submitting it to the store? Similarly for the batch processing. If we want to minimize latency then we probably want to pipeline things as much as possible? |
Beta Was this translation helpful? Give feedback.
-
|
The really expensive parts of this is batch/block proving (we don't have these implemented, but maybe we should simulate them somehow). My current assumption is that it would take about 3 - 5 seconds to prove batches/blocks - though, it depends on the number of transactions included in a batch and the number of batches included in a block. Here are my "back of the envelop" calculations:
In the above setup, I'm assuming we have multiple "prover" machines running to build batches and make them ready for the block builder. And then there is a single block builder machine that selects up to 16 batches and builds the next block. |
Beta Was this translation helpful? Give feedback.
-
[Design] Stages, pipelines & channelsThis is an attempt at using separate tasks / processes connected via channels. These processes are long-lived and are spawned once-off i.e. these are not short futures but instead a stage/subsystem. This tends to have nice properties:
The biggest stumbling block for me is usually the error propagation. How are errors communicated, and what happens to any existing data within the pipelines. In our case these would all need to be reverted / unwound somehow, which if we're careful could be possible. The main issue is that stage N assumes that all of its previous outputs were processed successfully. I'll lay out a design below and we can see if it might hold water: On 1st glance this looks quite nice, simple and is easy to configure each stage to our liking. Some concerns though:
Mostly I'm concerned that there is some state that needs locking between the different stages which would somewhat negate the benefits, but maybe its not the end of the world. |
Beta Was this translation helpful? Give feedback.
-
|
I was really hoping this approach would pan out but I think at this stage I have to face reality - the process of building blocks isn't truly a pipeline and therefore this model isn't the right one. The system has feedback effects from failed batches (solvable) and invalidated transactions (less solvable). Transactions can become invalid e.g. due to preconditions such as a block height limit being exceeded. This transaction and all of its dependents need to be removed from all the systems state. Dependent transactions could be anywhere in the system. We could add a This is somewhat solvable by adding a Another annoyance is that while going through the death marking, new transactions can still be added which needs to be prevented somehow. This would require a mutex syncing the add txn and death marking somehow. Its possible but this sounds complicated.. I think at this point its probably a good idea to drop this design as it is no longer "simple". A centralized controller doesn't have these issues since it can simply lock the entire data set and yank the dead data. |
Beta Was this translation helpful? Give feedback.
-
|
Hmm actually hold that thought. What if we define a transaction item as something like /// A wrapped transaction that can be marked as invalid.
enum MaybeAliveTxn {
Alive {
tx: Transaction,
dependents: Vec<Weak<Mutex<MaybeAliveTxn>>>,
},
Dead,
}
impl MaybeAliveTxn {
fn mark_dead(&mut self) {
// this isn't quite right as it could lead to long recursive locks,
// but this should be possible to implement by separating out the dependents.
for dep in self.dependents {
dep.upgrade().lock().mark_dead();
}
}
}
/// This is what gets used everywhere in the system.
///
/// The mutex will be uncontested for conventional usage since a transaction
/// is only ever accessed by a single stage and occasionally `add_transaction` if the
/// new txn depends on this one.
Arc<Mutex<MaybeAliveTxn>>For stages to access the actual transaction they'll have to check its status before making any changes. Conceptually only stage (1) and the current stage will have access to the transaction at any point. Stage (1) only uses it to perform dependency management, whereas the other stage would be responsible for invalidating it. Stage (1) would still need its state reset, but that can be done in the form of a separate event. |
Beta Was this translation helpful? Give feedback.
-
|
I was thinking about something similar - though, in a "central repository" setting. A few comments, questions:
|
Beta Was this translation helpful? Give feedback.
-
|
Yeah I think this can be used regardless of the overall design choices/architecture - just the internal nuances will differ slightly based on access requirements/concurrency.
|
Beta Was this translation helpful? Give feedback.
-
|
Re point 2, I'm wondering if we could track all note dependencies in a single map. Something like: pub enum NoteStatus {
Created(TransactionId),
Transient {
created_by: TransactionId,
consumed_by: TransactionId,
}
}
pub struct InFlightNotes(BTreeMap<NoteId, NoteStatus>);
impl InFlightNotes {
/// Returns transactions which consume notes produces by the specified transaction.
pub fn get_dependents(&self, tx: Arc<Transaction>) -> Vec<TransactionId> {
...
}
/// Returns transactions which produce notes consumed by the specified transaction.
pub fn get_parents(&self, tx: Arc<Transaction>) -> Vec<TransactionId> {
...
}
/// Adds output notes of the transaction to the inflight notes.
///
/// Also, for each unauthenticated input note in the transaction:
/// - If the note is in the `notes_in_store` list, returns its nullifier.
/// - If the note has `Created` status, updates the note to `Transient` status.
/// - If the note is not in flight or is already `Transient`, returns an error.
pub fn add_transaction(
&mut self,
tx: Arc<Transaction>,
in_store_notes: &[NoteId]
) -> Result<Vec<Nullifier>> {
...
}
/// Removes all output notes of the provided transaction from the in-flight notes.
///
/// For notes that are marked as `Transient`:
/// - If the note was created and consumed within this set of transactions, we don't do anything
/// special (i.e., just remove it).
/// - If the note was consumed but not created within this set of transactions, we return an error.
/// - If the note was created but not consumed, we remove the note and return its nullifier.
pub fn commit_transactions(
&mut self,
txs: IntoIter<Item = Arc<Transaction>>
) -> Result<Vec<Nullifier>> {
...
}
/// Removes all output notes of the transaction from the in-flight notes.
///
/// For notes that are marked as `Transient`:
/// - If the transaction created the note, returns the ID of the transaction which consumed the note
/// (this transaction is now invalid).
/// - If the transaction consumed the note, converts the note to `Created`.
pub fn drop_transaction(&mut self, tx: Arc<Transaction>) -> Result<Vec<TransactionId> {
...
}
} |
Beta Was this translation helpful? Give feedback.
-
[Design] Event loopThese are often used in rust based systems where concurrency, flexibility and extensibility are required. E.g. Core of the system is looping over a receiver of the system events, processing one event at a time like a state machine. The benefits are that code becomes a simple matter of writing if this then that, and that you have Downsides are that the "processing" in the loop must be kept to a minimum which is hard to enforce. And that the event enum can grow to be pretty unwieldy if one isn't careful. Biggest downside imo is that it becomes quite difficult to debug or reason about the order of events without have good traces. I'll try describe the design using the event enum: enum Event {
/// Time for a new block to be sealed. Should check for weird conditions for blocks still being sealed/stored.
BlockTick,
/// Spawn task to store the block. Ensure that previous block was already stored.
BlockSealed(Block),
BlockStored(Block),
/// via RPC, spawn task to verify it.
TxnReceived(Txn),
/// txn inputs validated, add to mempool, maybe submit a set of txns for batching
TxnValidated(Txn),
/// Batch worker produced a new batch and is ready for another set.
BatchProduced(Batch),
}Something that might be painful here is the book keeping between different events. For example, knowing when to submit a set of transactions for batching might occur when a batch has been produced, when a block has been sealed or persisted or when a txn has been added to the mempool. Or all of the above. Additionally, back-pressure is also painful as you will have to manually check before submitting unless you design additional cleverness into the tasks somehow. |
Beta Was this translation helpful? Give feedback.
-
|
This is probably the simplest to implement but just how much throughput one can expect is difficult to gauge. That said, one can go a long way with just a single thread that does minimal work itself, especially since it doesn't require any locks - only bookkeeping. |
Beta Was this translation helpful? Give feedback.
-
[Design] Central logic unitSimilar to the event based loop, but instead of smaller event transitions we rely more on mutex's and different collections of futures. This is probably the closest to what we currently have and described in #191. I don't have a clear picture in my head for this yet tbh, so this is just a verbal vomit of thoughts.. The transaction receiver should be a separate task with rpc submitting new txns via a channel. This simplifies rpc but also allows for easy back-pressure. It could still use the locks it currently holds to "communicate" with the main system. The main system will
Honestly though the more I fiddle with this idea at the moment, the more I seem to morph it into one of the other options. Might need some more time to percolate 🧠. |
Beta Was this translation helpful? Give feedback.
-
|
If we want to have all data stored in a central repository, we could have something like a impl TransactionPool {
/// Tries to add a transaction to the pool.
///
/// Internally, this will get all required data from the store to verify that the transaction
/// is valid against the current stored + in-flight state.
pub fn add_transaction(&mut self, tx: ProvenTransaction) -> Result<()> {
...
}
/// Returns a set of transactions to combine into a batch, or None if the transaction pool is
/// empty.
///
/// Internally, this will reach out to the store to get all the required data for building
/// the the proposed batch.
///
/// This will also mark all the selected transactions as being batched (so as not to put them
/// into another batch).
pub fn select_batch(&mut self) -> Option<ProposedBatch> {
...
}
/// Adds the constructed batch to the pool.
///
/// This will mark all the involved traction as having been batched. If this method is not
/// called within some interval after `select_batch()`, the transactions selected for this
/// batched will be released.
pub fn add_batch(&mut self, batch: TransactionBatch) -> Result<()> {
...
}
/// Returns a set of batches to combine into a block, or None if there are no ready batches.
///
/// Internally, this will reach out to the store to get all the required data for building
/// the block.
///
/// This will also mark all selected batches as in the process of being put into a block.
pub fn select_block(&mut self) -> Option<ProposedBlock> {
...
}
/// Marks all transactions in the provided block (and corresponding batches) as committed
/// and persists the block to the store.
pub fn apply_block(&mut self, block: Block) -> Result<()> {
...
}
}Things would be pretty simple if we could put a mutex around this struct but, unfortunately, many of its methods need to access the store and so we cannot block when calling them. But the basic idea is this:
A few thoughts on concurrency:
|
Beta Was this translation helpful? Give feedback.
-
|
I have a rough design that I think minimizes state lock contention. The design centers around decoupling incoming transaction state, both from each other and from the block/batch processing. Starting with incoming transactions, we use an optimistic/latest state view only for validating and updating inputs: /// The latest state of the chain, including inflight transactions.
///
/// Right now it is simplified by assuming all state can be stored in-memory.
/// If this becomes prohibitively large then it is possible to drop some of it
/// back to disk/cold-storage but this would require more care/complexity which
/// I suggest we defer.
struct RwLock<StateView> {
/// The inner mutex provides allows incoming txns to take a read-only lock of the entire
/// structure, allowing concurrent access by multiple txns at once.
account: Map<AccountId, Mutex<AccountState>>
/// Only active notes - does not include notes already nullified by a block
/// though we could also track those if we cared to for some reason.
notes: Map<NoteId, Mutex<NoteState>>,
}
enum AccountState {
Inflight(Arc<Txn>),
Storage(StateDigest)
}
enum NoteState {
Inflight(Arc<Txn>),
Storage,
/// Was from storage, but already consumed by an inflight txn.
/// Ideally we would remove this note from the pool instead, but
/// that would require write access to the mapping.
Consumed,
}
impl StateView {
/// A transaction is only accepted once it can lock and verify all of its inputs
/// at the same time.
///
/// The new transaction is also added as a child to all existing inflight transactions in
/// the required inputs.
fn add_txn(&self, tx: Txn) -> Result<()> {..}
/// Aquire write lock and update/remove the mappings. We need an exclusive lock because
/// we want all of this to happen at once.
fn block_update(&mut self, block: Block, dead_txns: Vec<Arc<Txn>> {..}
}Lastly we have the transaction pool which is where batch selection strategies can be performed on. I'm leaving out the stuff required for batch creation and management. struct TransactionPool {
/// Transactions which have no child dependencies i.e. all of its inputs are
/// on-disk/in-blocks already. The roots of the transaction graph.
roots: Mutex<Vec<Arc<Txns>>>,
}
impl TransactionPool {
/// Called by `add_txn` only when it creates a txn with no inflight deps.
fn add_root(&self, tx: Arc<Txn>) {..}
/// Write locks StateView and roots before mutating them with the block changes.
fn apply_block(&self) ...
} |
Beta Was this translation helpful? Give feedback.
-
I think putting all account hashes into memory may work, but doing the same for notes will be problematic. Specifically:
And if we are willing to push things to disk/cold-storage, might as well make a request to the store. So, I still think to figure out if a given transaction can be added to the pool, we'll need to:
|
Beta Was this translation helpful? Give feedback.
-
|
But maybe we can still use the core of your proposal - specifically, keep some more data in memory to remove potential race conditions. Here is what I think we can do: Assuming a transaction is internally consistent, there are 3 reasons why it can be rejected:
The way I see it, the main challenge for checking these conditions is that we need to go to the store to get the required data and while we are getting the data from the store, the in-flight state may change (i.e., a new block may get committed). But what if we keep extra data in the block producer that covers, say, last 10 blocks. Then, we can do something like this:
The lock in step 2 should be OK because we need it for a very short time (probably microseconds). The only potential complication could be due to unauthenticated transactions - but I think that should be solvable as well. |
Beta Was this translation helpful? Give feedback.
-
|
I like this idea. Its simple and I think even close enough to the current model that we can arrive there incrementally (maybe). Blending store + in-memory should be straight-forward. The only error condition is the race condition between store response and acquiring the lock. This is easy to detect by comparing the block height between the two, and also easy to trivialize the odds of this by increasing the block depth we store in-memory as you suggest. I think your suggestion will make it easy for us to spot bottle-necks by logging store, tx locking and apply block locking times. If/when we arrive at this stage we can dream up some improvements here. e.g. add more fine grained locks, minimize disk hits by using caching in store. i.e. recently created/accessed accounts are more likely to get accessed again shortly. Trivial to add these using lru caches. What could also be interesting is bloom filters.. somehow for notes, though I'm unsure just how yet. Generally though this is probably premature thinking without hard data showing access patterns. |
Beta Was this translation helpful? Give feedback.
-
|
One option for this is your suggestion here, though I think we should go with an interior mutex instead of an external one - this lets all methods become Two concerns I see with this
These make me consider something closer to the centralized logic which handles everything. At minimum we should consider changing If we minimize the time it takes to handle an event we should be able to have a central loop that progresses things one at a time. This also removes the need for a mutex (it effectively moves into the event/transaction channel instead). Testing would also be fairly straight-forward as we could inject the event channel and control event inputs one at a time. |
Beta Was this translation helpful? Give feedback.
-
|
Closing as this has largely been completed and merged into The implementation uses a mempool based on a dependency graph, and synchronisation is maintained using the classical |
Beta Was this translation helpful? Give feedback.
-
Background
The
block-producercomponent is responsible for receiving new transactions and sequencing them into blocks. The existing code gets the job done but was written to get up and going quickly. We want to redesign this more meticulously to allow for better abstractions and trying out different sequencing strategies.Transactions are grouped together into batches which in turn form a block. These batches enable concurrency and recursive proving which increases throughput.
Open issues #185, #191 and #196 would be superseded this new design.
Goals
Design a system where we can freely change transaction batching and batch selection strategies without causing the system to be reworked constantly.
As an example, if should be possible to go from a FIFO model to a fee-based strategy without worrying overly about correctness.
Additional considerations
block-producer.Beta Was this translation helpful? Give feedback.
All reactions