deadlock in route calculation #643
Comments
|
The per-peer locks always seemed like overkill to me, and that kind of fine-grained locking is hard to get right. What about just having a router-wide lock covering all routing information? |
|
I did consider that but such a lock would be on the critical path for everything, and would have very high contention. I'm not ruling out such an approach, but atm I'm not giving up on the peer locks just yet. |
I guess I'm missing something here - what's the reason to be concerned about contention? I can imagine that read contention could be high. But with a RW lock, we shouldn't need to be too concerned about that. I had assumed that write operations are mostly in response to topology changes, and so are not terribly frequent. And if the lock in question just guards routing and peer information, write critical sections shouldn't be able to block on anything else. And I'd guess that even the main routing calculation takes microseconds for networks of the maximum size we are concerned with at present. |
|
Weave is meant to cope fairly well with a fairly high churn rate in the topology. With a single lock, all topology changes would stall the data path. No idea how much a problem that is. |
|
What's a fairly high rate? I'm guessing that means thousands of changes a second, not millions. That's actually a modest level of contention if the critical sections are short. I might well be overlooking something, but the only area that springs to my mind as a critical section that wuodln't be short is the routing calculation. If we are genuinely aiming for high-performance concurrency, it might be worth looking at how the Linux kernel handles this kind of read-mostly situation: not through conventional locking, but through RCU (read-copy-update). In RCU, readers don't need to take a lock, because they just read an immutable data structure. Writers update a copy of that data structure, and publish it with an atomic pointer update (this needs to be done with a little care, due to CPU memory ordering models; this is what (The implementation of RCU in the Linux kernel is a lot more involved than that, because there is no garbage collection to clean up old copies. The details of this and many other low-level concurrency techniques are described in Paul McKenney's work-in-progress book at https://kernel.org/pub/linux/kernel/people/paulmck/perfbook/perfbook.html ) The kernel does have RW locks, but RCU is often preferred for two reasons:
That second point is particularly relevant to the issue you raised of avoiding stalling weave's data path while topology changes and routing calculations are occurring. |
|
Weave does not hold write locks during routing calculations. Re alternative concurrency features...I have little appetite to complete revamp weave's entire concurrency control as part of this issue. Anyway, I will see how hideous usage of a single lock gets. Lack of re-entrancy on golang's locks is one obstacle, which either requires a set of parallel APIs or breaking of encapsulation. But perhaps we are lucky and few methods on Peer and Connection are called in both contexts with and without the single lock. |
|
@dpw btw, there is only one place in the code where we acquire locks on multiple peers - the route calculation. |
- get rid of individual Peer locks - hold Peers read (or write) lock and LocalPeer read lock while performing route calculations This eliminates the deadlock resulting from the inconsistent lock acquisition order in route calculcation. Fixes weaveworks#643.
- get rid of individual Peer locks - hold Peers read (or write) lock and LocalPeer read lock while performing route calculations This eliminates the deadlock resulting from the inconsistent lock acquisition order in route calculcation. Fixes weaveworks#643.
eliminate route calculcation deadlock Fixes #643.
I came across this when running
NUM_WEAVES=50 bin/multiweave launch -connlimit 100...The pertinent part of the stack trace is
The 1st goroutine is the
LocalPeeractor, which performs a route calculation in order to figure out which peers to gc after a connection got deleted. The 2nd goroutine is theRoutesactor, which is performing one of its several route calculations. Both goroutines are stuck in the same place, attempting to acquire a read lock on a (different)Peer. The reason they can't get the lock is that there are pending write lock acquisitions on the two peers, by the last two goroutines, which are terminating connection actors attempting to decrement the reference count.Why don't the write lock acquisitions succeed? The reason must be that some other goroutine(s) hold a read lock. We cannot see that from the stack traces, but by far the most likely candidates are the first two goroutines holding a read lock on the peer the other is attempting to acquire.
The issue here then is that the two route calculations attempt to acquire the locks in a different order. Partially by accident - due to golang's random map traversal (of connection maps, in this case) - and partially by design (since different route calculations perform different traversals of the topology).
The easiest way to fix this is probably to prevent concurrent route calculations, especially since there are only two goroutines - the ones we are seeing here - that ever perform these. It is also worth observing that the route calculation performed by the peer gc is identical to the
unicastAllroute calculation performed by theRoutesactor.The text was updated successfully, but these errors were encountered: