Implements the communication protocol change logic.
Design
The algorithm to change the communication protocol is roughly as follows:
1. Start buffering the node's outgoing messages.
2. Wait until all the node's outgoing messages have been delivered.
3. Modify the node's communication protocol version.
4. Stop buffering the node's outgoing messages and send any messages
buffered in step (1).
Implementing the algorithm requires synchronising user threads, which send messages, with the GCS thread, which performs communication protocol changes.
The high level view of the synchronisation protocol between the user and GCS threads is the following:
when send-message(m) from user thread:
atomically:
if protocol_changing:
wait until protocol_changing = false
nr_msgs_in_transit++
...
when change-protocol(v) from GCS thread:
atomically:
protocol_changing := true
wait until nr_msgs_in_transit = 0
...
We expect that communication protocol changes are rare events, especially when compared to sending messages. As such, the actual implementation strives to minimise the overhead on the code path that sends messages.
To do this, we use an optimistic synchronisation protocol on the send message side, that works as follows:
Algorithm #0, User thread:
- If no protocol change is ongoing, the user thread will optimistically increment the number of messages in transit. 2.a If a protocol change did not start meanwhile, we are good to go. 2.b If a protocol change started meanwhile: 2.b.1. Rollback the increment to the number of messages in transit 2.b.2. Wait for the protocol change to finish.
There is an additional action that needs to be performed on step (2.b), but we will describe that action when we have the necessary context to understand it.
On the protocol change side, it works as follows:
Algorithm #1, GCS thread:
- Store that a protocol change is ongoing.
- When the number of messages in transit is zero: 2.1. Change the protocol version 2.2. Wake up any user threads waiting for the protocol change 2.3. Deem the protocol change finished
The central part of the Algorithm #1 is step (2). The question is: who triggers, and where, step (2)'s condition, i.e. the number of in-transit messages is zero? Well, the obvious place is that it is the GCS thread itself, when it is processing an incoming message. If that message comes from us, then we decrease the number of in-transit messages, which may set it to zero.
However, recall that the user threads employ an optimistic synchronisation protocol that "acts first, and asks for forgiveness later." If the user thread rolls back its increment to the number of in-transit messages, it may be the one to set it to zero—see Algorithm #0, step (2.b). In this situation, it is the user thread that hits the condition required by the GCS thread in Algorithm #1, step (2). In order for the GCS thread to finish the protocol change, the user thread must somehow signal the GCS thread to trigger its step (2). This is the missing action of Algorithm #0, step (2.b).
So, the final synchronisation protocol of the user thread's side looks like this:
Algorithm #2, User thread:
- If no protocol change is ongoing, the user thread will optimistically increment the number of messages in transit. 2.a If a protocol change did not start meanwhile, we are good to go. 2.b If a protocol change started meanwhile: 2.b.1. Rollback the the increment to the number of messages in transit 2.b.2. If our rollback set the number of messages in transit to zero, signal the GCS thread 2.b.3. Wait for the protocol change to finish.
Implementation
The implementation attempts to add as little overhead as possible to the common case, which is that no protocol change is ongoing. This is the fast path of Algorithm #2, step (2.a). To achieve this goal, it employs a tagged lock. For more details on the tagged lock implementation, see Gcs_tagged_lock.
In a nutshell, the tagged lock is a read-write spin lock which offers the following API:
try_lock() -> bool
unlock()
optimistic_read() -> tag
validate_optimistic_read(tag) -> bool
For the write-side section, one uses it as a typical spin lock, e.g.:
do:
lock_acquired := try_lock()
while (not lock_acquired)
write-side section
unlock()
For the read-side section, one can use it as follows:
done := false
while (not done):
tag := optimistic_read()
unsynchronised read-side section
done := validate_optimistic_read(tag)
if (not done):
rollback unsynchronized read-side section
The idea is to allow an optimistic read-side section that does not perform any memory stores. This is in contrast with a typical read-write lock, where the read side performs some memory stores to account for the reader, e.g. keeping a reader counter. The trade off is that:
a. the execution of the read-side of a tagged lock may be concurrent with the write-side section if meanwhile the tagged lock is acquired b. the read-side of a tagged lock may fail if meanwhile the tagged lock is acquired, in which case one may want to rollback the effects of the failed read-side section
The algorithms of the design are implemented as follows:
Algorithm #1 implementation, GCS thread:
- Lock the tagged lock
- When the number of messages in transit is zero: 2.1. Change the protocol version 2.2. Unlock the tagged lock, signal a condition variable to wake up any user threads waiting for the protocol change 2.3. Deem the protocol change finished
Algorithm #2 implementation, User thread:
- If the tagged lock is unlocked: 1.1. Start an optimistic read-side section 1.2. Atomically increment the number of messages in transit 2.a If the optimistic read-side section validates, we are good to go. 2.b If the optimistic read-side section fails validation: 2.b.1. Atomically rollback the increment to the number of messages in transit 2.b.2. If our rollback set the number of messages in transit to zero, signal the GCS thread 2.b.3. Wait on a condition variable for the protocol change to finish.
Note that we have concurrent access to the number of messages in transit which needs to be synchronised. This is done by using an std::atomic to implement the number of messages in transit.
Some final implementation pointers:
a. Algorithm #1: see the code path that starts on set_protocol_version and finish_protocol_version_change. b. Algorithm #2: see the code paths that start on atomically_increment_nr_packets_in_transit, adjust_nr_packets_in_transit, and decrement_nr_packets_in_transit.
1.9.2