Fun With Bits

programming blog covering OS internals, game dev, etc...

C++ Framework for Writing Servers Which Are as Fast as Usain Bolt

Prerequisite: C++

What if I tell you that there’s a framework out there that allows you to write servers that are as fast as the fastest man alive? Let me introduce you to Seastar. It’s a framework written in modern C++ that provides its user with a set of tools to extract the most from modern hardware.

Look at the chart below which compares Seastar memcached vs stock memcached: alt text

And it’s not only throughput. It has also proven to improve P99 latency considerably. Other example of applications that benefit from Seastar are ScyllaDB, a distributed database compatible with Apache Cassandra, and Pedis, a drop-in replacement for Redis.

What makes Seastar so fast?

Let’s go through some of its features and I expect that you will understand its power by the end of the list. Here we go:

1. One of its most interesting features is the shared-nothing architecture. What exactly is that? Basically, there will be only one thread for each core (or shard[1] in Seastar terminology) available to the application. And it also means that each thread will have its own set of resources (files, memory, etc) that will not be shared. By doing that, we eliminate the need to use locks because resources are no longer shared by threads. Communication between threads must be done explicitly through message passing, or else, we would need some locking mechanism.

[1]: In seastar, a shard is a thread assigned to a CPU core that acts like an isolated machine.

A common multi-threaded application usually looks like the left picture because you have threads accessing shared resources, whereas a Seastar application will look like the right picture because of its shared-nothing design, look:

images

2. Each Seastar thread will have its own scheduler for small asynchronous tasks (usually stored in std::function), which is called The Reactor. It’s important to keep in mind that all tasks should be asynchronous. That’s because if a thread blocks (waiting for I/O, for example), the reactor will not be able to run other tasks waiting to run.

Let me throw at you another example. What happens if a syscall is called which involves blocking the calling thread until the requested resource (for example, sys_read) is satisfied? The CPU would sit idle while waiting for I/O. From the perspective of a server, it would mean not handling any requests. So when you’re writing code for Seastar, you must make sure that you only use asynchronous API either provided by Linux or Seastar. All I/O in Seastar is done through asynchronous mechanisms provided by Linux such as aio.

Seastar API is very well documented, and it can be found here: http://docs.seastar-project.org/master/index.html

3. Because of the issue mentioned above, Seastar needs some mechanism to make it easier the task of writing fully-asynchronous code. And that’s done using the concept of futures and promises.

Let me explain how future is used in Seastar with code. Let’s say that you want to call a function to sleep for 1 second. Usually, you would only call a sleep function with 1 as parameter, and then the calling thread will sleep for 1 second and continue from when it left off. In Seastar, you shouldn’t block the current thread due to performance reasons, but you can block the task (also known as fiber). So you’d need to call a Seastar function which promises to wake up the task after 1 second.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include "core/app-template.hh"
#include "core/sleep.hh"
#include <iostream>

int main(int argc, char** argv) {
    app_template app;
    app.run(argc, argv, [] {
        std::cout << "Sleeping... " << std::flush;
        using namespace std::chrono_literals;
        return sleep(1s).then([] {
            std::cout << "Done.\n";
        });
    });
}

All functions that need to wait for something (like data from disk or network, time, etc) return a future type. Those futures can be consumed using future::then(), which takes a function that will run when the time has come. In the example above, sleep() returns a future type, which will be waited using future::then(). So the program above should print ‘Done.’ after 1 second. The chain of functions (also known as continuations) can grow as you want. So after the print, the program could sleep again for N seconds, write to a file, send a command over the network, whatever you want, all asynchronously! Please take a look here to know more about futures and promises in Seastar.

The list is getting long, so I’ll tell you quickly what else Seastar provides:

  • DPDK support
  • userspace TCP/IP stack
  • userspace I/O scheduler for fairness among components in the same thread
  • and much more!

Getting started

First of all, you should fork the project, which can be found here. Take a look at the README file for instructions on how to install deps and compile the project.

If you’re interested in knowing more about Seastar, I’d advise you to read this tutorial written by Nadav Har'El and Avi Kivity. If you’re willing to delve into some Seastar apps, please go to: https://github.com/scylladb/seastar/tree/master/apps

If you need help, send an e-mail to the project’s mailing list: seastar-dev@googlegroups.com

That’s it…

Seastar is very complex and it’s very hard to cover many of its aspects in a single article. At least, I hope I succeeded to help people understand what Seastar is about and how to get started. I intend to write more articles about it in the future covering more real-world examples. For example, how to write a simple server.

Thank you for your time and stay tuned!

Handling Game States

Prerequisite: basic C++ and game programming knowledge

When you start any game, you expect to see a loading screen, followed by the main menu which has a button that allows you to play the game. When you start playing the game, it’s also expected that you’ll be able to go back to main menu and possibly pause and resume the game. All these different stages of the game are known as game states.

Handling game states is a very difficult task, especially to newbies to game programming like myself. Today, I was looking for an efficient way to switch back and forth between all available states of my simple game.

The simplest way to do it would be using a switch statement, as follow:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
enum game_states {
    MENU,
    GAME,
    ...
}

void game::update() {
    switch(_current_game_state) {
        case MENU:
            // show game options
            // update current state to PLAY if user clicks on play button.
            ...
            break;
        case PLAY:
            ...
    }
}

That’s indeed very simple, but it would be a nightmare to maintain this code when the number of states increases considerably. It turned out that a Finite State Machine (FSM) is exactly what I was looking for. It’s said that FSM is an abstract machine that can be in exactly one of a finite number of states at any given time.

To implement a state machine that handle different types of game states, I took advantage of polymorphism. Each game state will derive from an abstract class called game_state; follow its definition:

1
2
3
4
5
6
class game_state {
public:
    virtual void on_enter() = 0;
    virtual void on_exit() = 0;
    virtual void update() = 0;
};

The first two methods will be used for loading and cleaning the game state, respectively. game_state::update() will be used for a given state to react to user’s input and possibly switch to another state. For example, when an user clicks on play button, the state machine will switch from menu to play state.

Now our state machine will be able to work with all different types of game states in the same way. To make the transition between stages more efficient, the machine will work in the same way a stack does. For example, a new state will be pushed to the back of container storing the game states. And more importantly, the active state is the one that was last pushed to the container. That’s how my implementation of game state machine turned out:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class game_state_machine {
    std::vector<std::unique_ptr<game_state>> _game_states;
public:
    void push(std::unique_ptr<game_state> state) {
        state->on_enter();
        _game_states.push_back(std::move(state));
    }

    void pop() {
        if (!_game_states.empty()) {
            _game_states.back()->on_exit();
            _game_states.pop_back();
        }
    }

    void update() {
        if(!_game_states.empty()) {
            _game_states.back()->update();
        }
    }
};

Note that game_state_machine::update() will only call update on behalf of the active state, and that’s essential for the machine to work as expected.

I showed the implementation of abstract class for game state, but it’s also important to understand how an actual game state could be implemented by deriving from it. Check it out:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class menu : public game_state {
public:
    void on_enter() override {
        // load menu sprites
        ...
    }
    void on_exit() override {
        // clean up goes here
        ...
    }

    void update() override {
        // if user clicked on play button, switch to play state.
        if ( ... ) {
            ...
            game_state_machine.push(std::make_unique<play>());
        }
    }
};

Very easy, no?! If we’re in play state, and want to go back to menu, all we need to do is to call game_state_machine::pop().

This was the most efficient way I found to handle game states in my own game. If you know a better way to do it, please leave a comment!

PS: the comment section only shows up when you click on the blog post’s title.

See you,

Ready to Have Fun With Bits?!

Hi everyone. I’m really glad that I finally launched this blog. Fun With Bits.

Special thanks goes to Peteris Krumins who shared some invaluable insights about blogging.

TL;DR: Bla bla bla about who I am. In this blog, I’ll talk about software development techniques, low-level hacks, game development, kernel, among other interesting topics I feel it’s worth sharing with my readers.

I don’t expect people to know me prior to reading my blog, so I’m going to introduce myself.

I think that my father (unfortunately, he’s no longer around us) is the main reason behind my interest in computers. When I was about 10 years old, he taught me how to use commands to interact with MS DOS. I remember the most important commands were to edit texts, execute programs, and navigate through the file system. I don’t know how many times I messed up with the operating system, making impossible to boot it. I had a lot of fun doing it though. After that, I was able to create my own websites using HTML and CSS. I didn’t even know what programming actually was at that time. I was just curious and wanted to do interesting things with my computer.

I actually started with programming after I got interested in creating my own alternative server for a MMORPG called Tibia. Of course, I didn’t create the server, but the experience made me learn how to host a server, manage my website and consequently a database which stored players' data, and also how to write scripts using LUA programming language for custom systems, like quests and spells.

At that time, I wasn’t even thinking of computer science as a career. I was just having fun with bits. Pun intended :-) But I changed my mind and joined a local university for a computer science degree. It helped me a lot because I wanted to be the best programmer among my peers. I worked really hard. A friend of mine a.k.a. kov introduced me to the open source world. He told me about the job opportunities I could get if I started helping relevant open source projects out there. IIRC, Linux kernel was the first open source project I contributed to. The change was to slightly improve the PID allocation code. I will not lie. It was extremely hard to find something to do, but the experience taught me a lot. I was really obsessed with kernel. I often found myself whispering the word ‘kernel’ while showing or walking down the streets. I wanted to better understand how computers worked, from boot to application initialization.

As I was gaining more experience, I contributed to other projects until I got my first job opportunity at an israeli startup called Cloudius Systems. It was working on creation of a project called OSv. In OSv, I worked with file systems. Mostly on improving ZFS support. I’m working for the same company, but now on creation of a distributed database called ScyllaDB.

I think I’m considerably better than myself of 5 years ago, but there’s a long way to go until I can say I’m really good with computers. By the time being, I’ll keep repeating this ZEN poem to myself: “To follow the path, look to the master, follow the master, walk with the master, see through the master, become the master.”

I’ll do my best to share interesting stuff with all of you.

Stay tuned!