[Proposal] Review locking practices in snarkOS

[cbeck88]

💥 Proposal

In many parts of the snarkOS primary (gateway, storage, telemetry), the most common synchronization primitive that I see is RwLock<HashMap<..., ...>>.

snarkOS/node/bft/src/helpers/cache.rs

Line 31 in 9db1492

pub struct Cache<N: Network> {

snarkOS/node/bft/src/helpers/telemetry.rs

Line 78 in 9db1492

/// Note: none of the locks below may be acquired inside a parallel iterator, and none of them may

snarkOS/node/bft/src/helpers/pending.rs

Line 64 in 9db1492

pending: RwLock<HashMap<T, HashMap<SocketAddr, Vec<(oneshot::Sender<V>, i64, bool)>>>>,

snarkOS/node/bft/src/gateway.rs

Line 200 in 9db1492

peer_pool: RwLock<HashMap<SocketAddr, Peer<N>>>,

snarkOS/node/bft/src/bft.rs

Line 66 in 9db1492

dag: Arc<RwLock<DAG<N>>>,

For example:

Naively, RwLock seems very attractive especially when rapid prototyping, because if you don't really know whether the value will be heavily written or rarely written yet, the choice shouldn't be too terrible.

However, RwLock can also cause nasty problems, because it turns out that it's very difficult to design a generically good RwLock, and competing concerns cause it to behave in ways that aren't often expected.

1. Users of RwLock expect that it should satisfy eventual fairness. If a writer attempts to lock it, the implementation should guarantee that even if new readers show up and want to read concurrently with existing readers, they eventually have to get shut out so that the writer is guaranteed to get a turn.

If the implementation doesn't guarantee this, then it's possible that a writer tries to lock and then is blocked for an unbounded amount of time. If your program is broken because the writer just never gets a turn, it's not clear what you can do as a developer to fix it, so it's viewed as a defect in the RwLock implementation.

2. This design consideration produces different foot guns though. One of them is, if you have a reader lock, and then you call into a function that tries to acquire another reader lock, it can cause a very rare deadlock. This is because if a writer shows up in the middle, the implementation must prevent the reader from taking a second lock, to ensure that the writer will eventually get a turn. However, if the reader already has a reader lock and the code is written so that it needs to take a second lock to make progress, then blocking that reader also prevents the writer from ever getting a lock. Nevertheless your program will appear to work unless a writer actually shows up in the middle between these two locks.

A related issue is, if you used lock structures like this in C or C++, you may be used to "reentrant" mutexes, which you are allowed to lock multiple times from the same thread, and it simply increments a counter whenever you relock it to keep track of this. Some developers I worked with were of the opinion that all mutexes should be re-entrant, because the only behavior difference is that you don't deadlock when you re-enter, and that's (arguably) strictly an improvement in behavior, since you cannot truly recover from a deadlock but you might be able to do something good if the mutex is re-entrant. There are some low-level cases where making a particular mutex re-entrant is the best solution -- for example if your logging infrastructure relies on some ring buffer construction, but the ring buffer code also wants to be able to log errors, you may be able to fix a deadlock and get the desired behavior using this approach.

In rust you simply cannot have re-entrant mutexes, because it's not compatible with the borrow checker. The second time you would lock the mutex, you are getting another mutable reference to the underlying data, which is automatically UB.

However, via an RwLock, it appears that you can get around this at least if you only need a reader reference. The type signatures do allow you to take multiple reader locks, and you might think that this is safe. Unfortunately, as mentioned, if you actually do that, you get a really nasty rare dead-lock scenario if a writer shows up.

3. For similar reasons, there is no good way to promote a reader lock to a writer lock atomically. A lot of times, when you have an RwLock, you naively want to read the data, check if it satisfies some condition, and then only if it does, take a write lock. Because there is no way to atomically promote the reader lock to a writer lock, you have to release the reader lock, and then the condition might change underneath. If the developer doesn't think carefully about that, they can create a race condition and a bug (for example here: fix(bft): clear the proposed batch under a single lock #4370). So even though it's counterintuitive, usually the right thing to do is take a writer lock in situations like this.

(parking_lot::RwLock does support a special "upgradable_reader" mode distinct from the general reader mode. But unfortunately, it has complex semantics -- in particular, two upgradable readers cannot be obtained concurrently, and they always queue behind other writers. So in this implementation, an upgradable_reader is not much different from a writer, and this is a very niche feature.)

4. The actual performance of an RwLock can be a lot worse than a Mutex. If you end up in the situation where writers do appear frequently, you might be better off just using a regular mutex. Additionally, the semantics are simpler. Problems are easier to spot and it's harder to misuse.

Review comments that I see on PRs mention that we have often gotten bitten by our use of locks. (#4367 (review))

I can also see that we have a dependency called locktick that can be used to tell us about contention on all of these RwLocks.

---

I'd like to suggest that there are some other patterns we can consider in some of these cases to try to alleviate some of this.

1. In some situations like rate limiting, you might have RwLock<HashMap<... , ...> mapping Peer id's to counters used for rate limiting. These counters could be changed to AtomicI64, and then we can safely read them or increment them without taking a writer lock. The RwLock HashMap doesn't change, but now in the hot path we only take reader locks, and a writer lock is only necessary when a new peer appears, which should truly be very rare.

More generally, if you rarely need to actually modify which keys are in the map, and you can make the values threadsafe to modify (perhaps by making things atomic, or perhaps putting a smaller lock around them), then you can make it so that the outer RwLock needs a writer lock only very rarely, e.g. when the peer group actually changes. It seems to me that a lot of our RwLock<HashMap are keyed on peer ids so this pattern could apply in many cases in this code base.

2. For examples like telemetry, we're trying to keep track of things like how many certificates we've seen per round, how many signatures we've seen per round, how many certificates we've seen for a given validator. So we construct a state machine that receives updates from the bft code when new certificates or signatures come in and when, and can then compute participation scores from this. Because it needs to be threadsafe, we just wrap everything in this statemachine in RwLock.

However this creates a problem, which is that now, telemetry background work can take locks that block the "hot path" of BFT. And we've determined that if any of these telemetry functions are called from Rayon parallel iterators, it can cause a deadlock, as the code comments indicate.

Another pattern I've seen used successfully for telemetry is, don't use a lock for this statemachine. Instead, the bft code enqueues messages into mpsc queues, which are drained by a background worker that drives this telemetry computations and runs the state machine in a single threaded manner. Depending on how you ultimately get the metrics out, it could take the updated participation scores and send them to the metrics framework, or if you implement a prometheus scrape endpoint directly, the telemetry background worker could use something like tokio::sync::Watch to share a value such that the "latest" published value can be read asynchronously by anyone

This would prevent BFT from ever being blocked if telemetry is slow. Instead if the telemetry worker can't drain the queue fast enough, BFT could simply drop what it was going to enque and log a warning. Since the telemetry worker doesn't have to do very much and no longer has any locks, it most likely won't have a problem draining the queue.

3. For more complex examples where we truly do need a concurrent hashmap, some very standard advice would be to try using https://github.com/xacrimon/dashmap, which bills itself as (often) a replacement for RwLock<HashMap<..., ...>>. This project is very well supported and the way it works is fairly simple. Instead of having one RwLock guarding the whole hashmap, they use a hash function to "shard" the key space, arbitrarily dividing it into, say, 16 pieces. Then each of these pieces becomes its own RwLock<HashMap<...>>. If your original RwLock<HashMap<...>> was highly contended, i.e. there were often simultaneously readers and writers showing up, now these are divided randomly among the 16 pieces and on average there is hopefully much less contention. The writers are less often blocked by readers and when they are there are on average fewer readers they have to wait for. There's very little downside as long as the API for dashmap is enough for your use case (you only need to read or modify one hashmap entry at a time).

4. For some cases, like rate limiting, it's okay for access to different rate limiting counters to be independent because rate limiting is somewhat approximate anyways. For cases like this:

snarkOS/node/bft/src/bft.rs

Line 66 in 9db1492

dag: Arc<RwLock<DAG<N>>>,

#[derive(Clone)]
pub struct BFT<N: Network> {
    /// The primary for this node.
    primary: Primary<N>,
    /// The DAG of batches from which we build the blockchain.
    dag: Arc<RwLock<DAG<N>>>,
    /// The batch certificate of the leader from the current even round, if one was present.
    leader_certificate: Arc<RwLock<Option<BatchCertificate<N>>>>,
    /// The timer for the leader certificate to be received.
    leader_certificate_timer: Arc<AtomicI64>,
    /// The consensus sender.
    consensus_sender: Arc<OnceCell<ConsensusSender<N>>>,
    /// Ensures only one call to `commit_leader_certificate` runs at a time.
    ///
    /// Without this, a second certificate crossing the availability threshold while the consensus
    /// callback for a prior commit is still in-flight would re-walk already-committed rounds
    /// (because `last_committed_round` hasn't been updated yet), causing duplicate subdag commits.
    commit_lock: Arc<Mutex<()>>,
}

it's very unclear (to me) why it's okay for dag to be under one lock, and leader_certificate under another, because presumably, how we update the DAG depends on who we think the leader is in a particular round, and so we would not want that to be changing while we would be updating the DAG. If we would have to take both locks to do an update while maintaining soundness invariants, it suggests that actually they should both be under the same lock.

The code comments rarely speak to considerations like this and so I'm left wondering if these are bugs and someone just wrapped everything in Arc<RwLock to make the code compile and hoped for the best, or if it's actually okay for some reason.

My hope is that in some cases we can discuss changing a naive use of RwLock to either reduce contention or reduce the total number of locks, and in other cases we can discuss merging two locks if we can't construct an argument that it's safe for two pieces of data to be changing concurrently, and measuring performance changes to help decide. And try to document in the some of this considerations more explicitly in the BFT code.

[ljedrz]

Some initial thoughts:

In rust you simply cannot have re-entrant mutexes, because it's not compatible with the borrow checker. The second time you would lock the mutex, you are getting another mutable reference to the underlying data, which is automatically UB.

parking_lot does have a ReentrantMutex, with the caveat that it needs to be bundled with a RefCell for mutability; std is planning to support one too.

There's very little downside as long as the API for dashmap is enough for your use case

I'm not sure I agree here - it's a potential speed boost in case the used keys are spread out, but buys little in case of hot keys; also, if I'm not mistaken, it deadlocks if a reference to a key is held across a lookup.

I'm left wondering if these are bugs and someone just wrapped everything in Arc<RwLock to make the code compile and hoped for the best, or if it's actually okay for some reason.

This design hadn't crystallized immediately - this is a product of iterative work, so what may seem obvious in retrospect may not have always been that way - if that were the case, everything would be lock-free and built around finite state machines.

I can also see that we have a dependency called locktick that can be used to tell us about contention on all of these RwLocks.

Indeed, and it has been used to detect both contention and deadlocks, none of which are apparent with the current code and the workloads tested.

All that aside, it is quite likely that we might be able to refactor some of the objects so that they share locks according to common functionality, and it's possible that there are performance gains to be had by swapping some of the RwLocks for Mutex or using sharded hash maps, though that should be contingent on specific measurements.

[ljedrz]

There are a few good suggestions in this issue:

• using atomics where it can remove locking (e.g. for simple counters)
• using channels for telemetry when it's in a hot path
• upgrading a read guard to a write guard where it might otherwise be a footgun
• verifying suspected lock contention (probably most likely in stress tests) using locktick, and acting on a per-case basis

Any of these would warrant individual, dedicated issues/PRs.

What I wouldn't do:

• apply dashmap or switch to Mutex indiscriminately
• assume the choice of the object, or a split between locks is random - it's entirely possible that the setup can be improved, but that doesn't mean the current one is unsound (e.g. DAG and leader_certificate are under separate locks, but right next to them there's a commit_lock, which is a dedicated safeguard)