This post was written after I finished 6.824 Lab2: Raft. I have been working on this Lab for five days, and I feel very happy and lively. I believe that a programmer has experienced multithreaded programming, but for me, this is the first time to write such a complex state, so many cases to consider the parallel program. The network is unbelievable. all requests may be lost and may arrive late. Programs don’t run for long and can be killed at any time. The core of the program is a complex state machine. Once the code is not fully considered, race conditions will appear, resulting in deadlocks, live locks, and various logic errors. The complexity of parallel programs also makes debugging difficult. Most of the time, it is necessary to check the run log for clues, and sometimes the bug cannot be reproduced. These may have been very common for senior engineers, but for me, what I do at ordinary times is nothing more than to look at the knowledge points on the back of books, write about stateless servers, make some small toys, at most brush topics burn brain. So it’s really exciting to have a chance to implement a system like this. I applaud Mit faculty and students for providing us with such a complete infrastructure.

Lab needs to be implemented with GO, and GO is a language suitable for parallel programming. Its syntax is simple enough, gc with excellent performance and the standard library is powerful, which is also the reason why Morris chooses GO. However, most people actually have no contact with GO, novice road will inevitably step on a little pit. I will not talk about the common case, you can find some common language pits from the lab home page to provide guide and other information and code tips. Here are some of the parallel problems I will encounter in the process of implementation, and my solution.

Common parallel problems in the process of implementing Lab2

1. How to use time.Timer correctly?

Timers are an integral part of implementing raft processes. For example, the implementation of election Timeout uses timer triggering and resetting. AppendEntries Rpc also needs to send periodically to maintain leader authority. Therefore, we need a tool that can reset the time and trigger a timeout. Time.timer fits this requirement.

But the Lab’s home page clearly states:

Don’t use Go’s time.Timer or time.Ticker, which are difficult to use correctly.

The Timer functions, such as Stop and Reset, are annotated with instructions for their use, but can be confusing. Therefore, Lab recommends the combination of for + sleep to check some variables when waking up to achieve the purpose of timer. In other words, completely disable the Reset Timer function, so that the Timer must be triggered, so as to avoid the confusing behavior of the Reset/Stop Timer.

However, the above implementation is not elegant enough, and we still want to reset the timeout correctly so that the program behaves as described by the algorithm.

So what are the possible ways to use it? Take election Timeout as an example

func (m *timeoutManager) start(a) {
	t := time.NewTimer(m.random())
	defer t.Stop()
	expired := false
	for {
		select {
      // channel for resetting this timer
		case <-m.rChan:
			if! t.Stop() && ! expired {// drain the channel
				<-t.C
			}
			expired = false
			t.Reset(m.random())
		case <-t.C:
			// timeout event fired
			expired = true
			m.rf.mu.Lock()
			ifm.rf.state ! = Leader { m.rf.convertToCandidate() } m.rf.mu.Unlock() t.Reset(m.random())case <-m.rf.cancel:
			return
		case <-m.cancel:
			return}}}Copy the code

To understand the above code, you should first understand the timer’s working logic. From the very surface Api provided by Timer, the way a Timer is used is by adding a Timer to the system after New. The user code listens for a channel within the timer, and once the timeout occurs, the Runtime sends a signal (an empty structure) to C, making the user aware of the event.

If t. top terminates the timer and Reset resets the timer, this is not a problem. The Time package requires that Reset be called only on stopped timers, which is fine.

If an event occurs, it enters the processing logic. If no event occurs, and there is no default, it blocks on these channels.

That is, after entering one of these cases, other events may or may not have occurred. For our raft logic, if a reset event occurs then the timer should be reset and the timeout event that has occurred should be treated as if it did not occur because the race did not succeed. We definitely don’t want to have expired timeout events processed just after we have converted to follower or candidate (which is when resetTimer is called), so that we can transition to the next term without a new timeout event occurring. Why can expired timeout events still be processed? Because the timeout event is sent through a buffered channel, we consider the timeout as long as there is a value in the channel. Therefore, the value should be consumed when there is a value in the channel to prevent the event from being triggered incorrectly.

So we use t.top () to check the status of the timer. If it hasn’t happened yet, that’s good. T.top () returns the correct result. If t.top () returns an error indicating that the timer has been triggered or stopped, then we should consume any possible values in the channel as stated above.

Some students might complete this logic with the following code

if! t.Stop(){// drain the channel
  select{
  case <-t.C:
  default:}}Copy the code

If there is a value in the channel, it will be consumed. If there is no value in the channel, it will go to default and return. But this is the wrong logic, because sending values to t.C is a coroutine that is completely parallel to the user code, and there is no lock to serialize the logic. In other words, the following conditions will occur:

  1. Over time, go sends a coroutine to t.C.
  2. The user code calls t.top and returns an error because the timer has timed out
  3. The user code enters SELECT, but the coroutine responsible for sending values has not yet been executed, so it enters default.
  4. The coroutine responsible for sending the value sends the value to the channel, completing the task and exiting.
  5. In the next for, entering the logic of timeout processing, Raft mistakenly increases her tenure just moments after resetting the time and becomes a candidate.

Of course, the above description is actually a difficult case to encounter, it will not be a big problem if it happens, but it is just a re-election. The solution is as simple as using a expired variable to indicate whether the value in the timer is actually processed. If not, block and wait and empty t.C, then enter the logic below. This will ensure that there will be no problems.

Having written the above, I can see why Morris recommends not using timers. There is a lot to consider in proper use, and it has nothing to do with lab itself. But it’s nice to understand how a component works and be able to use it properly with the runtime

2. How do I communicate with Channel for Raft application scenarios

2.1 How do I gracefully exit all backend coroutines after calling the Kill() command?

There are two types of backbench coroutines. One is similar to timeout and heartbeat, which are triggered periodically. In this case, you only need to check whether the end flag is set. One is an applier-like method that blocks on a channel or condition variable. If you use a channel, you just initialize a zero-buffered Cancel channel when raft is created and when kill() is called By closing this channel, all coroutines listening on this channel will receive a signal and exit gracefully.

2.2 How to make better use of both buffered and unbuffered channels?

Channel is the implementation of CSP in go language.

According to the go language specification formulated by Uber, the capacity of a channel is either 0 or 1. If the capacity is 0, both sender and receiver block on the channel until it is readable/writable.

What is the use of these two channels? I take a usage scenario in Lab2 as an example.

  1. Applier. This back-desk coroutine listens for changes to commitIndex (via channel). No matter how many commitIndex changes occur before the applier actually applies (that is, accepts information from a channel into the case branch), the applier will not be affected. So the solution is to use a channel with one buffer, and when sending messages to this channel (i.e., signal operations), use the select non-blocking mode with a default branch. Note some logical parallelization with locks. The advantage of this design is that sending is always non-blocking and the logic is completely correct.
  2. Cancel. As stated in 2.1, the 0 buffer is designed to cancel. This is a common way to use context packages.

3. How to deal with the calculation problem of MatchIndex

In Raft, if you are the Leader, you are responsible for calculating whether or not new entries can be submitted based on the matchIndex of each server (which of course involves judging the term for the submitted entries). The matchIndex may be modified after the AppendEntries Rpc returns, at which point the waiting Committer coroutine should be woken up and the committer should decide whether to modify the commitIndex.

What about committer logic? Note that many of the properties in raft are monotonically increasing and monotonically increasing provides a lot of convenience. Committer maintains a curMatch that represents the maximum current match value. This value may be smaller than commitIndex, because curMatch is initialized to 0 upon the leader’s election, indicating that the leader does not know the match status of other servers.

Each time a matchIndex change occurs, committers will try their best to increase curMatch to the maximum. If curMatch cannot be added any more, then start comparing commitIndex and curMatch to see if they can change the commitIndex. The next change event comes directly from the current value.

There is also a minor optimization in comparing commitIndex and curMatch, where you can cache commitIndex instead of locking read every time. This also takes advantage of the fact that both are monotonically increasing.

4. How to reduce the granularity of locks

We can’t just add a global lock every time we have an operation. We need to split locks properly to reduce lock preemption. Here are a few ideas.

  • The Leader’s nextIndex and matchIndex arrays are unrelated to other RAFT states and are reinitialized each time the Leader is elected. What I did was split the leader out in its entirety, with its own state, locks, methods and a pointer to RAFT. This way, reading and writing nextIndex and matchIndex doesn’t have to grab the raft lock at all. That is, the resource group is locked.
  • Bucket locking, which I’m not using here, but if the number of servers is large, matchIndex reads and writes should be prone to lock preemption. You can use a hash function to spread read and write to the matchIndex array over several buckets, each with its own lock, reducing preemption. This is also a very, very common optimization.

Some other insights

There are a lot of experiences and reflections from this Lab, but they are not systematic. Let’s write a little bit here and there.

  • One of the things that really exercised me in this Lab was that I really thought about fault tolerance in programming, considering various possible situations, and then serialized it in my mind with synchronization primitives, which I rarely did before. Or very rarely in memory, since there have been some consistency issues associated with concurrent reads and writes to storage components.
  • This is the first time to use a lot of logs to debug, and I can really find a lot of problems. This struck me as someone who has never used an IDE to find bugs
  • Raft had a lot of decisions to make and accidentally wrote if else hell. My solution was to use the flexibility of Go’s defer function to process it uniformly before returning and apply the early exit pattern. Early exit with some necessary comments can bring strong code readability, which I think is very important for me to sort out the logic and debug later.
  • Split the state appropriately. Some of the implementations I’ve seen online have all the state and functions written in the raft main class. However, I chose to separate the leader, Timeout, election, etc implementations from the main class and store them in different files. This makes it easy to wrap, name, find where the logic is and so on during programming, which (for me) greatly increases readability.
  • Of course, THERE is a bit of Raft feeling, but I’ve been so immersed in the implementation these days that I haven’t had a chance to savor it. Check back tomorrow!