Forem: 👨‍💻 Dillen Meijboom

Concurrency in Go is hard

👨‍💻 Dillen Meijboom — Mon, 29 Aug 2022 07:48:18 +0000

I understand that the title might be somewhat confusing as Go is generally known for having good built-in support for concurrency. However, I don’t necessarily think it’s easy to write concurrent software in Go. Let me show you what I mean.

Using global variables

The first example is something we ran into while working on a project. Up until recently, the sarama library (Go library for Apache Kafka) contained the following piece of code (at sarama/version.go):

package sarama

import "runtime/debug"

var v string

func version() string {
    if v == "" {
        bi, ok := debug.ReadBuildInfo()
        if ok {
            v = bi.Main.Version
        } else {
            v = "dev"
        }
    }
    return v
}

At a glance, this looks fine, right? If the version isn’t set globally, it's either based on the build information or assigned to a static value (dev). Otherwise, the version is returned as is. When we run this code, it would appear to work as intended.

However, when the version function is called concurrently, the global variable v could be accessed from multiple goroutines simultaneously, resulting in a potential data race. These issues are hard to track down as they only occur at runtime at precisely the right conditions.

The solution

This issue was fixed in #2171 by using sync.Once which, according to the docs, is “an object that will perform exactly one action.” This means that we can use it to set the version once so that subsequent calls to the version function will return the result. The fix looks like this:

package sarama

import (
    "runtime/debug"
    "sync"
)

var (
    v     string
    vOnce sync.Once
)

func version() string {
    vOnce.Do(func() {
        bi, ok := debug.ReadBuildInfo()
        if ok {
           v = bi.Main.Version
        } else {
           v = "dev"
        }
    })
    return v
}

Although I think in this case, it could also have been fixed without using the sync package by using an init function to set the variable v once. As the variable v won’t change after Go runs the init function, it should be fine.

How to prevent it

You can use the data race detector (available since Go 1.1) during tests or when using go run if you only want to start the application. When it detects a potential data race, it will print a warning. To show how this works, I’ve changed the code a little bit to trigger a data race:

package main

import (
    "fmt"
    "runtime/debug"
)

var v string

func version() string {
    if v == "" {
        bi, ok := debug.ReadBuildInfo()
        if ok {
            v = bi.Main.Version
        } else {
            v = "dev"
        }
    }
    return v
}

func main() {
    go func() {
        version()
    }()
    fmt.Println(version())
}

Now we can run it with the -race flag to enable the race detector:

➜ go run -race .                               
==================
WARNING: DATA RACE
Write at 0x000104a16b90 by main goroutine:
  main.version()
      main.go:14 +0x78
  main.main()
      main.go:27 +0x30

Previous read at 0x000104a16b90 by goroutine 7:
  main.version()
      main.go:11 +0x2c
  main.main.func1()
      main.go:24 +0x24

Goroutine 7 (finished) created at:
  main.main()
      main.go:23 +0x2c
==================
(devel)
Found 1 data race(s)
exit status 66

As you can see, a data race is detected. If we analyze the output, we can see that we simultaneously read and write to the v variable. This is what we call a data race. It’s called a data race because both goroutines are “racing” to access the same data.

A visual representation of the race detector output

Copying structs from the sync package

I did find some real-world examples on GitHub, but none was significant enough to mention here. Instead, I’ll explain this based on a sample I made. So here it goes:

package main

import "sync"

type User struct {
    lock sync.RWMutex
    Name string
}

func doSomething(u User) {
    u.lock.RLock()
    defer u.lock.RUnlock()
    // do something with `u`
}

func main() {
    u := User{Name: "John"}
    doSomething(u)
}

The User struct contains two properties: a read/write lock and a string. When the doSomething function is called, the variable u is copied on the stack (also known as being passed by value), including its fields. This is an issue because as the documentation for the sync package states:

Package sync provides basic synchronization primitives such as mutual exclusion locks. Other than the Once and WaitGroup types, most are intended for use by low-level library routines. Higher-level synchronization is better done via channels and communication.

Values containing the types defined in this package should not be copied.

When the doSomething function is evaluated, running RLock/RUnlock will not affect the original lock in the User struct rendering it useless.

The solution

Use a pointer to the lock instead. The pointer will be copied and points to the same value. The updated version looks like this:

type User struct {
    lock *sync.RWMutex
    Name string
}

How to prevent it

Use the copylock analyzer to show a warning when types from the sync package are copied. The easiest way is to run go vet before releasing your code. Running this on the original code results in the following output:

➜ go vet .
# data-synchronization
./main.go:10:20: doSomething passes lock by value: data-synchronization.User contains sync.RWMutex
./main.go:20:14: call of doSomething copies lock value: data-synchronization.User contains sync.RWMutex

Using time.After

While searching on GitHub, I found a pull request in the Raft implementation by Hashicorp (a distributed consensus algorithm), which we can use to demonstrate the following problem. Let’s start by showing the code (at api.go):

var timer <-chan time.Time
if timeout > 0 {
    timer = time.After(timeout)
}

// Perform the restore.
restore := &userRestoreFuture{
    meta:   meta,
    reader: reader,
}
restore.init()
select {
case <-timer:
    return ErrEnqueueTimeout
case <-r.shutdownCh:
    return ErrRaftShutdown
case r.userRestoreCh <- restore:
    // If the restore is ingested then wait for it to complete.
    if err := restore.Error(); err != nil {
        return err
    }
}

This piece of code is from the Restore method. The select statement waits for one of the following cases: the timer (used for when a timeout is defined), a shutdown channel, or when the restore operation is finished. It’s pretty straightforward, so what is the issue?

The time.After function looks like this:

func After(d Duration) <-chan Time {
    return NewTimer(d).C
}

So it’s nothing more than a shorthand for time.NewTimer, but it “leaks” the timer (as there is no call to timer.Stop). The documentation says the following about it:

After waits for the duration to elapse and then sends the current time on the returned channel. It is equivalent to NewTimer(d).C. The underlying Timer is not recovered by the garbage collector until the timer fires. If efficiency is a concern, use NewTimer instead and call Timer.Stop if the timer is no longer needed.

I genuinely don’t understand how a function that intentionally “leaks” the timer (resulting in a potential long-lived allocation, depending on the duration) ends up in the standard library…

The solution

Instead of using time.After, we can create the timer manually. This is what it looks like:

var timerCh <-chan time.Time
if timeout > 0 {
    timer := time.NewTimer(timeout)
    defer timer.Stop()
    timerCh = timer.C
}

// Perform the restore.
restore := &userRestoreFuture{
    meta:   meta,
    reader: reader,
}
restore.init()
select {
case <-timerCh:
    return ErrEnqueueTimeout
case <-r.shutdownCh:
    return ErrRaftShutdown
case r.userRestoreCh <- restore:
    // If the restore is ingested then wait for it to complete.
    if err := restore.Error(); err != nil {
        return err
    }
}

When the function is finished, the timer is cleaned up even if it didn’t fire.

How to prevent it

I wouldn’t use time.After in any codebase. There is no real advantage other than saving one or two lines of code, while it can give quite some issues, mainly when it’s used in the hot paths of your code.

Conclusion

You can quickly write concurrent software with Go’s built-in support for concurrency. However, it leaves it up to the user to ensure data is synchronized correctly and tools from the standard library are used as intended. This, combined with the simplicity of Go, makes it hard to write stable, bug-free, concurrent software.

Memory Alignment

👨‍💻 Dillen Meijboom — Mon, 22 Aug 2022 07:04:00 +0000

Today we're going to talk about memory alignment. Before we dive into it, let's start with a practical example in Rust to show why this is relevant:

use std::mem;

struct Member {
    active: bool,
    age: i32,
}

fn main() {
    println!("bool: {} bytes", mem::size_of::<bool>());
    println!("i32: {} bytes", mem::size_of::<i32>());
    println!("Member: {} bytes", mem::size_of::<Member>());
}

We defined a struct called Member, which includes two fields. Then we print the memory size of all of the types. The size of a bool in rust is 1 byte, and the size of a 32-bit integer is 4 bytes; thus, the total size of our struct should be 5 bytes, right?

➜ cargo run
    Finished dev [unoptimized + debuginfo] target(s) in 0.00s
     Running `target/debug/memory-alignment`
bool: 1 bytes
i32: 4 bytes
Member: 8 bytes

What kind of dark magic is this... Where do these extra three bytes come from?

CPU and memory

To understand how this works, we need to understand how the CPU reads the memory. The CPU sends the address of the memory it wants to read to the address bus. Then it sends the “read” command to the memory on the control bus, and finally, the memory will send the data to the data bus.

Overview of the system bus (I/O not included)

The amount of data transferred is often the same size as a single word (a unit specific for processors). On most 64-bit CPUs, the word size equals 8 bytes (=64 bits), whereas, on most 32-bit CPUs, this would be 4 bytes (=32 bits). Unaligned memory usually hurts performance as more CPU instructions are required. This is where memory alignment comes into place.

Back to our code

Remember that our Member struct has a size of 8 bytes while its fields combined only take up 5 bytes? This is because the compiler automatically aligns our memory. To do so, it adds three extra bytes of padding.

Memory layout of our struct on x86_64

The amount of padding is based on the field type, struct size, and CPU properties (such as the word size).

Field order

The order of the fields in C, C++, Go, and possible other programming languages matter because extra padding will be used. However, in Rust, struct fields will be re-ordered by default to get the smallest possible size. The compiler is allowed to do so because, by default, Rust makes no guarantees for struct types.

To demonstrate, we can use the C representation, which will use a type layout interoperable with the C Language. Let's add another boolean field to our struct:

use std::mem;

#[repr(C)]
struct Member {
    active: bool,
    age: i32,
    admin: bool,
}

fn main() {
    println!("Member: {} bytes", mem::size_of::<Member>());
}

The repr(C) attribute enables the C representation. This way, the fields won't be re-ordered. Let’s execute it to see the result:

➜ cargo run
   Compiling memory-alignment v0.1.0 
    Finished dev [unoptimized + debuginfo] target(s) in 0.53s
     Running `target/debug/memory-alignment`
Member: 12 bytes

We can now “optimize” our Member struct by re-ordering the fields manually. To get the memory size back to 8 bytes, we have to move the age field to be the first field in the struct:

use std::mem;

#[repr(C)]
struct Member {
    age: i32,
    active: bool,
    admin: bool,
}

fn main() {
    println!("Member: {} bytes", mem::size_of::<Member>());
}

To verify if this has the expected result, we need to execute our program again:

➜ cargo run
   Compiling memory-alignment v0.1.0 
    Finished dev [unoptimized + debuginfo] target(s) in 0.42s
     Running `target/debug/memory-alignment`
Member: 8 bytes

To understand how this works, we can look at the memory layout for our Member struct both before and after re-ordering the fields.

Memory layout on x86_64 using the C representation with and without ordering fields

Tooling

As mentioned earlier, tooling is unnecessary when using Rust, as you most likely don't have to manually re-order fields. However, when you use Go, you can configure the fieldalignment analyzer with golangci-lint to warn about “unoptimized” structures.

I’m not aware of any tooling for C or C++ so let me know if you have any suggestions.

Practical Bloom Filters

👨‍💻 Dillen Meijboom — Fri, 19 Aug 2022 14:50:00 +0000

A couple of years ago I wanted to learn more about different types of commonly used data structures. It’s one thing to have used them, but knowing how they work or building them from scratch is something else. In this article, we’re doing a deep dive into bloom filters including some code examples and use-cases.

What is a Bloom Filter?

According to Wikipedia, a bloom filter is:

A space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970, that is used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not.

So in its essence, a bloom filter is an array of bits (1/8 of a byte) where initially all bits are set to 0. To add an element to the bloom filter a hashing function is required to “map” the element to a specific position in the bit array. Two or more elements can be mapped to the same position which can result in false positives (which is why it's called probabilistic). However, if the bit at the position of the element is 0 we know for sure that it's not included in the set.

In short:

A bloom filter can be used to efficiently check if an element is not included in a set.

Real-world usage

CRLite

In 2020 Mozilla announced that they are working on an alternative for validating revoked certificates in Firefox which is called CRLite. At the time a collection of all unexpired revoked certificates compromised 6.7GB on disk which was compressed to a ~ 1.3MB bloom filter. Verifying if a certificate is revoked is cheap for valid certificates as it only requires hashing the certificate serial number to get the position of the bit and verifying if it's set to 0.

Cassandra

Apache Cassandra uses bloom filters to determine whether an SSTable has data for a particular partition. Verifying if the SSTable has data for a partition is cheap as it doesn’t need to read its content (avoiding IO operations).

Building one from scratch

We’re going to use Rust to create our bloom filter. Let’s start with a simple structure that includes the bit array:

struct BloomFilter<const N: usize> {
    bytes: [u8; N],
}

impl<const N: usize> BloomFilter<N> {
    fn new() -> Self {
        Self { bytes: [0; N] }
    }
}


fn main() {
    let filter = BloomFilter::<10>::new();
}

Now we have a basic structure that holds our bit set and sets all bits to 0 when the bloom filter is created. Since there is no way to represent a single bit as a type our bit array is defined as an array of bytes. Thus size N in this example is the size in bytes (as u8 is the data type for a byte in Rust), not bits.

The first thing we’re going to implement is adding a new element to our bloom filter. We need to hash the value to get a numeric value, get the position of the byte, get the position of the bit inside the byte, and set it to 1. We’re going to use strings for our elements and use the DefaultHasher as our hashing function.

use std::collections::hash_map::DefaultHasher;
use std::hash::{Hash, Hasher};

fn hash(value: &str) -> u64 {
    let mut s = DefaultHasher::new();
    value.hash(&mut s);
    s.finish()
}

struct BloomFilter<const N: usize> {
    bytes: [u8; N],
}

impl<const N: usize> BloomFilter<N> {
    fn new() -> Self {
        Self { bytes: [0; N] }
    }
    fn add(&mut self, key: &str) {
        let bit_size = N * 8;
        let pos = hash(key) % (bit_size as u64);
        let (byte_idx, bit_idx) = (pos / 8, pos % 8);
        self.bytes[byte_idx as usize] |= 1 << bit_idx;
    }
}

There is a lot to unpack here. To get the absolute bit position, the element is hashed to get a numeric value and a modulo operation is used against the size of the bit array so that we end up with a valid position. Then we need to find the position of the byte and calculate the relative bit position. At last, we set the bit by using a bitwise operation.

Adding an element where pos=20

The last step is to implement a method that checks if an element is not included in the set. The process is similar to adding an element but instead of setting the bit we need to check its value.

use std::collections::hash_map::DefaultHasher;
use std::hash::{Hash, Hasher};

fn hash(value: &str) -> u64 {
    let mut s = DefaultHasher::new();
    value.hash(&mut s);
    s.finish()
}

struct BloomFilter<const N: usize> {
    bytes: [u8; N],
}

impl<const N: usize> BloomFilter<N> {
    fn new() -> Self {
        Self { bytes: [0; N] }
    }

    fn get_positions(&self, key: &str) -> (usize, u64) {
        let bit_size = N * 8;
        let pos = hash(key) % (bit_size as u64);
        ((pos / 8) as usize, pos % 8)
    }

    fn add(&mut self, key: &str) {
        let (byte_idx, bit_idx) = self.get_positions(key);
        self.bytes[byte_idx] |= 1 << bit_idx;
    }

    fn contains(&self, key: &str) -> bool {
        let (byte_idx, bit_idx) = self.get_positions(key);
        self.bytes[byte_idx] & (1 << bit_idx) != 0
    }
}

Most of the logic is moved to the get_positions method which calculates the byte index and bit position. Let’s also add some test code to see if it works as intended:

fn main() {
    let mut filter = BloomFilter::<10>::new();
    filter.add("test1");
    filter.add("test2");
    println!("test1: {}", filter.contains("test1"));
    println!("test2: {}", filter.contains("test2"));
    println!("test3: {}", filter.contains("test3"));
}

On my machine this results in the following output:

➜ cargo run
   Compiling bloom-filter v0.1.0
    Finished dev [unoptimized + debuginfo] target(s) in 0.14s
     Running `target/debug/bloom-filter`
test1: true
test2: true
test3: false

Remember that we can only guarantee that test3 is not included in the set. We can’t be sure that either test1 or test2 are included in the set as these could be false positives. The source code can be found on GitHub.

Closing remarks

In our bloom filter implementation, we choose a random size of 10 bytes (=80 bits). In the real world, the size should be based on your dataset and the expected probability rate of false positives. Choosing a size that’s too small can have negative effects on performance as there will be too many false positives. The best way to determine the properties of your bloom filter is by running performance tests and using the bloom filter calculator.