Feature Request: Fully Deterministic produce_events

[carlaKC]

⚠ This will be a non-trivial refactor ⚠

Describe desired feature

SimLN can currently be run with a fixed seed for its random activity setting, but payments produced by the simulator will not be fully deterministic.

This is because we have a single DestinationGenerator which is used across many produce_events tasks*. We can hit the following sequence of events:

• We have an RNG that produces values 1, 2, 3 then 4
• We have two produce_events tasks A and B that will both sleep for 5 seconds in between payments**
• Both A and B are competing for the same lock on our Arc<Mutex<DestinationGeneartor>>

First run:

• A gets lock first: A gets value 1, B gets value 2
• A gets lock first: A gets value 3, B gets value 4

Second run:

• A gets lock first: A gets value 1, B gets value 2
• B gets lock first: A gets value 4, B gets value 3

Across the two runs, the nodes get different destinations based on the order in which they acquire the lock. This averages out across multiple runs, but isn't properly deterministic. We should fix that.

* this was intentional, we don't want to have to store our lightning graph many times over
** the sleep time is random, so it's not that likely that they sleep for exactly the same time, but not impossible (especially if we start to speed up the clock)

Use case for feature

Fully deterministic runs are important for reproducible simulations.

Design Considerations

Part of this issue will be proposing a solution for this issue and discussing it here before opening up a PR, because it'll likely be a larger change to the codebase.

Incomplete thoughts that I have had about this are:

1. Bite the memory bullet and copy the network graph for each node so that they have a distinct DestinationGenerator

This gets rid of the locking issue, as each will lock their own destination and always get the same fixed values.

2. Have a single produce_events loop that deterministically queues events for each node

Rather than spinning up a task for each node to produce its own events, have one master task that's responsible for dispatching events for each of the nodes. This would look something like:

• Get the next payment time for each node
• Drop them in a sorted heap
• Pull the next item off the heap, get the destination from the shared DestinationGenerator
• Once dispatched, get the next payment time for the node and push it onto the heap

3. There are probably better ways to do this, but my potato-brain hasn't thought of them.

Would you like to contribute code for this feature?

I'll collaborate on design + contribute review, but won't be able to champion it myself.

[Onyekachukwu-Nweke]

I would like to pick this up

[carlaKC]

I would like to pick this up

#253 has unaddressed review comments and failing CI - I'd recommend getting one PR done at a time when you're getting started in a new repository.

[f3r10]

After reviewing the current approach of consumers and producers, I agree with the second option proposed by @carlaKC.

Although I am probably wrong regarding this 😅 , I've been considering an alternative approach for network_generator. Instead of being an Arc<Mutex<dyn DestinationGenerator>>, perhaps it could simply be a Vec<(PubKey, Amount)>. Currently, the consumers only seem to utilize the SendPayment event, specifically the dest.pubkey and amt_msat parameters within node.send_payment(...). It appears the remaining information in NodeInfo isn't being actively used. 🤔.

CC @sangbida @carlaKC What are your thoughts on this?

[carlaKC]

Instead of being an Arc<Mutex>, perhaps it could simply be a Vec<(PubKey, Amount)>.

Interesting! Did a quick back of envelope for this:

• Each node stores 41 bytes: 33 pubkey + 8 u64
• Each node will have to store this for n nodes (just including itself to keep it simple)

So our footprint is 41n^2. Taking some example values of n:

• 500: ~10 MB
• 15000: 8.80 GB
• 50000: ~95.5 GB

I think that 15k is an interesting number to be concerned with because that's approx the size of today's network. I can run the mainnet graph rn with around 400 MB so I think we should stick with the shared graph solution.

Seems like option (2) is the way to go unless we can think of something smarter.

[f3r10]

I have an additional question @carlaKC: why is it necessary to use an Arc<Mutex<dyn DestinationGeneartor>> and not a Arc<dyn DestinationGeneartor> + pub trait DestinationGenerator: Send + Sync ?
As I understand, the shared network graph is Immutable, and a Mutex (lock) would not be necessary.
Using Sync makes it safe for multiple nodes (threads) to access the shared network concurrently.

[sangbida]

I have an additional question @carlaKC: why is it necessary to use an Arc<Mutex<dyn DestinationGeneartor>> and not a Arc<dyn DestinationGeneartor> + pub trait DestinationGenerator: Send + Sync ? As I understand, the shared network graph is Immutable, and a Mutex (lock) would not be necessary. Using Sync makes it safe for multiple nodes (threads) to access the shared network concurrently.

I was wondering if we use Send + Sync, multiple threads could concurrently call DestinationGenerator which would change the state of the RNG?

I like Option 2 as well, it seems like it solves the determinism issue which maintaining memory usage.

[carlaKC]

I have an additional question @carlaKC: why is it necessary to use an Arc<Mutex> and not a Arc + pub trait DestinationGenerator: Send + Sync ?

It's not! It should be Arc<dyn DestinationGeneartor> + pub trait DestinationGenerator: Send + Sync

When things look weird in sim-ln, it's (embarrassingly) often the case that I just didn't really know what I was doing when I started writing it (my first real rust project).

I was wondering if we use Send + Sync, multiple threads could concurrently call DestinationGenerator which would change the state of the RNG?

The RNG is mutexed under the hood (that makes it Sync), but yeah that would otherwise be a problem! This is sort of the problem we're having here - threads are grabbing the mutex in different orders each time we run, which makes things non-deterministic.

[f3r10]

Right, the RngCore trait inherently requires mutable access (&mut self), so a Mutex is necessary for shared use. Refactoring to Arc<dyn DestinationGenerator> (even with Send + Sync) doesn't change this fundamental requirement, as DestinationGenerator would still need a method taking &mut self to generate values. 👀

I am going to start with the design of option 2.