Send, Sync , RefCell, Mutex and RwLock. How rust ensures thread safety.

I am working on bifrost, in the whole month. Expected it to be the foundation of my future projects. Although Raft algorithm itself it simple for everyone to understand, to achieve a usable library like Zookeeper and etcd still required efforts.

In the process of implementing this algorithm with read ability from state machines, which can be executed on both leader and updated follower concurrently to improve read performance, I figured out how rust ensures thread safety by myself.

Let's rehearse how to mutate a variable and what happened under the hood.

First, every mutable variable should have a prefix 'mut' to tell the compiler it is mutable. Then the compiler will keep eyes on those kind of variable to avoid potential inconsistent behavior likely to happen.

For example, in Java you can do this without get an error from compiler. But it is a very bad practice, don't do this at work.

List numbers = new ArrayList();
for int i : numbers {
  numbers.add(i + 1);

You may expect you can get 1 and 2 in the number list. But in rust, this code even cannot been compiled.

let mut numbers = vec!(1);
for i in &numbers {
    numbers.push(i + 1);

You will get error like this:

error[E0502]: cannot borrow `numbers` as mutable because it is also borrowed as immutable
--> src/raft/
443 |         for i in &numbers {
    |                   ------- immutable borrow occurs here
444 |             numbers.push(i + 1);
    |             ^^^^^^^ mutable borrow occurs here
445 |         }
    |         - immutable borrow ends here

As you can see, you borrowed number as immutable in the beginning of the loop. In the loop block, you will no longer able to mutate 'number'. You may be get annoyed when switching from other PL based on GC or ARC to manage memory like Java/Python/Ruby or even Swift, seeing this kind of 'Error' which used to be at most 'Warning', fight with the compiler just to get the your code to been compiled.

The very essence of Rust is it's zero-cost abstraction. Just like it is advertised, rust cost no more than malloc and free call to manage memory in run time unlike mark and sweep from GC or reference counting from ARC. Which means Rust still use raw pointer under the hood and raw pointer is unsafe.

How can rust ensures memory safety only in compile time with raw pointer? It checks how data flows and when a piece of memory is no longer required, it will be freed instantly.


The figure above shows how a variable was mutated. After the mutate occurred (green box turned into purple), the memory for green box will be freed.

Why will the green box been freed and allocate new spaces for purple rather than reuse it? Thinking about C++, when there is no resizeable array list data structure exists, you can only allocate an arbitrary amount of memory and cannot expand it afterwards. The only way to expand the array literally, is to allocate another memory with larger space, copy the contents from the old one and free the memory for the old. This is how array list works in standard library. That means the memory address to the array may be changed in the mutation. In the example above, the address to number is unstable in the loop due to mutable function push, which have risk to produce dangling pointer.

Although you can presume the memory preserved for the Vector is always sufficient by invoking with_capacity, but the compiler will never accept any assumption like that because it is dumb and does not trust it's users.

In the concurrency programming scope, things gets more complicated. I used to chat with one of my friend after we watched another round of the greatest movie in 2016 <Your Name.>.

Good story, great graphics.

He mentioned some unexpected behavior encountered when dealing with threads, shared pointers, data races etc, on C++ programming, which cost him a lot of time to figure out what really happened at that time. I have my own experience when do such things on Java, but it may go worse on bare-metal. A pointer shared between threads may get freed when other threads are still using it.

Rust provided some mechanisms to prevent you from data races even you do not realized what you are doing and the consequences. In the doc there is an example for you to make sense on how to work with threads.

use std::sync::{Arc, Mutex};
use std::thread;

let five = Arc::new(Mutex::new(5));

for _ in 0..10 {
    let five = five.clone();

    thread::spawn(move || {
        let mut number = five.lock().unwrap();

        *number += 1;

        println!("{}", *number); // prints 6

Although this is not what an efficient concurrent hit counter should really been designed, but it demonstrated how to share data with threads. Let's decomposite to see what's really in there.

First we use Arc and Mutex from the std::sync. You may familiar with the term Mutex, which is the lock, but Arc is the new thing in rust world. Arc stands for atomic reference counting. It looks and behave like the ARC from Apple , which required to be used explicitly in rust, is for memory management. Arc will monitor references been used in threads and free the memory when all threads ended.

You can imagine the rectangles are the threads, reference the same data (the green box)

There is also another reference counter named Rc which have the same interfaces with Arc, but cannot been used with multi-thread. You will get another compile error if you replace Arc with Rc instead. Because Rc is not designed for multi-thread, it is not safe to be shared between threads. Arc can be shared because it use an atomic counter under the hood. Rust ensures you will never messed with with Rc and Arc by using two traits, Send and Sync. The two traits usually appears in pair, but they represent different meaning.  Send means you can send the data to threads safely without trigger a copy, like what we use Arc for. It use clone function to create another reference for counting and add one to the counter, when the clone dropped, the counter will minus one. Sync means every modification to the data will be synchronized between the threads, it is what we use Mutex for. If there is no any mutation on the data, we don't really need Sync. In the example above, if we don't add on the number, but only print out the value for the number, Mutex is not required.

Mutex is a lock. Threads trying to acquire the lock for read or write the data exclusively. This is how Mutex ensures the safety when there is data race, it also responsible for tracking memory address changes when mutating the data. Arc can't do such job alone because it is only responsible for sharing the data by sending address to the threads by clone. Every time lock() function is invoked and lock is acquired, it will return a MutexGuard as the entry point to the data and the monitor to ensure the lock will be released when it is out of scope or dropped. In the example above, if developer need to do any mutation to the number in the reference, Mutex is required.

Another alternative lock is read write lock, RwLock in rust standard library. In this lock, read will not block each other but write lock will block both read and write. In bifrost, when implementing read for state machines, read lock is the best practice. Because when there is no mutation in the process, blocking read is undesired. Although RwLock is similar to Mutex by providing extra feature to avoid unnecessary blocking, RwLock and Mutex are not interchangeable. RwLock cannot been used alone because read() provided a window for unsafety, thus it does not implemented Sync trait unless every member in the data implemented Sync as well. In my practice, when I put a threadpool in the RwLock, it cannot send to threads even if the RwLock is wrapped by Arc. The compiler will throw an error complain about Sync trait missing. If I replace RwLock with Mutex, it will be fine. My final solution is to wrap the threadpool by Mutex, which passed the compiler. You see, using the threadpool is a potential mutation to the data structures in the object. Even read() cannot stop you from doing this because the threadpool functions are not tagged as mutable for compiler (it is common when the library rely on unsafe operations). When the threadpool itself cannot ensure memory safety, it have to rely on others, like Mutex.

In this scenario, RefCell is also not allowed in RwLock. RefCell is like the combination of Rc and RwLock, without the actual lock part. It was used as a work around for interior mutability, with some run time cost. Because it cannot ensure safety by itself, I use another RwLock as replacement. I spent hours on figuring out the difference between Mutex and RwLock, finding countermeasures. Thread safety is ensured even if I did not know the whole story in the beginning, avoid potential crash defects.

Although rust is still in its early stage to be used as a productive system programming language because of lacking mature libraries, it demonstrated that it is worthwhile to setup a steep learning cure to ensure even the newbie to this technique are still able to write safe code without blow up anything in run time. When it also have potential to build high performance software, makes it the perfect system programming language to me.