This is the sixth day of my participation in Gwen Challenge

Godis: a Redis server implemented in Go language. Support:

5 data structures (String, List, Hash, Set, sortedSet)
Automatic Expiration (TTL)
Publish and subscribe, location, persistence, and more

You may not need to implement the Redis service yourself, but are you tired of writing business code every day, trying to improve your programming skills, trying to write a project from scratch and opening the IDE only to find you can’t start?

Building wheels must be a good way to improve programming ability, the following will take you to start with Go to write a Redis server (Godis), from which you will learn:

How to write Go TCP server
Design and implement secure and reliable communication protocol (REDIS protocol)
How to develop highly concurrent programs using Go
Design and implement distributed clusters and distributed transactions
Familiar with linked list, hash table, skip table and time wheel and other common data structures

Do not worry about the content is too difficult, can not learn or have no Go language foundation!! Although the sample code is Go, it does not affect your understanding of the principles and underlying protocols of Redis and the secrets of high performance. Moreover, the author has optimized the technical explanation in order to cater to the broad audience. The sample code is simplified from the original project and commented line by line. For advanced players, please go directly to the project to read the source code:

Github.com/HDT3213/god…

The following text begins, let’s clear away the fog of Redis.

Write a TCP server

Redis is known as C/S model and uses TCP protocol for communication. The next step is to implement the TCP server. Golang, as a widely used server-side programming language, provides a very simple TCP interface, so it is very convenient to implement. Sample code:

func ListenAndServe(address string) {
    // bind the listener address
    listener, err := net.Listen("tcp", address)
    iferr ! =nil {
        log.Fatal(fmt.Sprintf("listen err: %v", err))
    }
    defer listener.Close()
    log.Println(fmt.Sprintf("bind: %s, start listening...", address))

    for {
        // Accept blocks until a new connection is established or listen breaks
        conn, err := listener.Accept()
        iferr ! =nil {
            // An error occurs when the listener is closed
            log.Fatal(fmt.Sprintf("accept err: %v", err))
        }
        // Open a new Goroutine to handle the connection
        go Handle(conn)
    }
}

func Handle(conn net.Conn) {
    reader := bufio.NewReader(conn)
    for {
        // ReadString blocks until the delimiter '\n' is encountered
        // When a delimiter is encountered, ReadString returns all data received since the last time it encountered the delimiter
        // If an exception occurs before the delimiter is encountered, ReadString returns the received data and an error message
        msg, err := reader.ReadString('\n')
        iferr ! =nil {
            // The usual error encountered is that the connection is broken or closed, denoted by io.eof
            if err == io.EOF {
                log.Println("connection close")}else {
                log.Println(err)
            }
            return
        }
        b := []byte(msg)
        // Send the received information to the client
        conn.Write(b)
    }
}

func main(a) {
    ListenAndServe(": 8000")}Copy the code

👌 so far only 40 lines of code to solve the server! After starting the TCP service, type Telnet 127.0.0.1 8000 in the terminal to connect to the server you just wrote and it will return the message you sent to you as is (so please don’t call it bad) :

The TCP server is very simple. The main coroutine calls accept to listen on the port and opens a Goroutine to handle a new connection. This simple blocking IO model is somewhat similar to the early Tomcat/Apache servers.

The blocking IO model uses one thread to process a connection, listening for the thread to block when no new data is received, and waking up to process the data when it is ready. The blocking IO model is inefficient because it requires opening a large number of threads and frequent context switches. The ePoll technology (IO multiplexing) used by Redis handles a large number of connections with a single thread, greatly increasing throughput. So will our TCP server be much slower than Redis?

Of course not. Golang encapsulates a Goroutine-per-Connection style minimalist interface by taking advantage of the fact that Goroutine scheduling is much cheaper than thread scheduling, and the NET/TCP library encapsulates epoll as blocking IO. Enjoy the high performance of ePoll while avoiding the complex asynchronous code required by the native EPoll interface.

On the author’s computer, Redis can respond to 10.6K pings per second, while Godis (complete code) has a throughput of 9.2 KQPS, not much different. To learn more about Golang’s high performance ㊙️ secrets, search the Go Netpoller or Go language Web Poller keyword

In addition, a qualified TCP server should not stop when it shuts down, but should do the necessary cleanup to respond to received requests, release TCP connections, and so on. This feature is commonly referred to as Graceful shutdown or graceful Shutdown.

First, close the listener to stop accepting new connections
Then, all surviving connections are traversed and closed one by one

There is a lot of code that closes gracefully, so I won’t post it completely here.

Second, perspective Redis protocol

After solving the communication, the next step is to make clear the Protocol of Redis, which is actually a set of serialization Protocol, similar to JSON and Protocol Buffers.

Since Redis 2.0, communication is unified as Redis Serialization Protocol (RESP), which is easy to implement. This Protocol can not only be efficiently parsed by programs, but also be understood and debugged easily by human beings.

RESP is a binary secure text protocol that works over TCP. RESP is based on lines, and commands or data sent by clients and servers are all newlines with \r\ N (CRLF).

Binary security is the ability to allow arbitrary characters in a protocol without causing a failure. For example, a string in C that ends with \0 is not allowed to appear \0 in the middle of the string, while a string in Go is allowed to appear \0. We say that the string in Go is binary safe, but the string in C is not binary safe.

The binary security of RESP allows us to include special characters like \r or \n in key or value. Binary security is especially important when using Redis to store binary data such as Protobuf and MSGpack.

RESP defines five formats:

Simple String: Used by the server to return Simple results, such as “OK”, which is non-binary safe and does not allow line breaks
Error: The server returns simple Error messages, such as “ERR Invalid Synatx”, which is not binary safe and does not allow line breaks
Integer: a 64-bit signed Integer returned by commands such as llen and scard
Bulk String: Binary safe String, such as the return value of commands such as get
Array (also known as Multi Bulk Strings) : The format in which the client sends commands and responds to commands such as lrange

RESP uses the first character to indicate the format:

Simple strings: start with a “+”, e.g. “+OK\r\n”
Error: start with “-“, e.g. “-err Invalid Synatx\r\n”
Integer: starts with “:”, for example :” :1\r\n”
String: with$start
Array:*start

Let’s look at some practical examples to understand the protocol.

2.1 the string

The Bulk String has two lines. The first line is $+ the body length, and the second line is the actual content. Such as:

$3\r\nSET\r\n
Copy the code

The String Bulk String is binary safe, that is, it can contain the “\r\ N “character inside the Bulk String (CRLF at the end of the line is hidden) :

$4
a\r\nb
Copy the code

2.2 empty

$-1 means nil. For example, if you use get to query for a nonexistent key, the response is $-1.

2.3 an array

The Array format begins with “*”+ the length of the Array, followed by the corresponding number of Bulk Strings. For example, [“foo”, “bar”] :

*2
$3
foo
$3
bar
Copy the code

The client also uses the Array format to send instructions to the server. The command itself will be used as the first parameter, such as the RESP message of the SET key value instruction:

*3
$3
SET
$3
key
$5
value
Copy the code

Print out the newline:

*3\r\n$3\r\nSET\r\n$3\r\nkey\r\n$5\r\nvalue\r\n

2.4 Preparation for Parsing

After knowing the contents of common RESP packets, you can start parsing them. However, it is important to note that RESP is a binary-safe protocol that allows the use of \r\n characters in the body. For example, Redis can correctly receive and execute the SET “a\r\nb” helloGithub command. The correct message for this command would look like this:

*3  
$3
SET
$4
a\r\nb 
$11
hellogithub
Copy the code

ReadBytes will mistake the fifth line “a\r\nb\r\n” for two lines:

*3 $3 SET $4 a // wrong branch b // wrong branch $11 hellogithubCopy the code

So after the fourth line $4 is read, instead of continuing with ReadBytes(‘\n’) to read the next line, use the IO.ReadFull(reader, MSG) method to read the content of the specified length.

msg = make([]byte.4 + 2) // The body length is 4 + the newline length is 2
_, err = io.ReadFull(reader, msg)
Copy the code

2.5 Writing an RESP Protocol Parser

With the “\r\n” problem resolved, we can start writing the Redis protocol parser.

type Payload struct {
	Data redis.Reply
	Err  error
}

// ParseStream reads data through IO.Reader and returns the result to the caller via channel
// The streaming interface is suitable for client/server use
func ParseStream(reader io.Reader) <-chan *Payload {
	ch := make(chan *Payload)
	go parse0(reader, ch)
	return ch
}
Copy the code

Because of the large amount of code in the parser, the core flow is briefly described here.

func parse0(reader io.Reader, ch chan<- *Payload) {
    // Initialize the read state
    readingMultiLine := false
    expectedArgsCount := 0
    var args [][]byte
    var bulkLen int64
    for {
        // We mentioned above that RESP is an action unit
        // Since rows are divided into simple strings and binary safe BulkStrings, we need to encapsulate a readLine function to be compatible
        line, err = readLine(reader, bulkLen)
        iferr ! =nil { 
            // Processing error
            return
        }
        // Next we parse the row we just read
        // We simply divide Reply into two categories:
        // Single line: StatusReply, IntReply, ErrorReply
        // Multiline: BulkReply, MultiBulkReply

        if! readingMultiLine {if isMulitBulkHeader(line) {
                // We received the first line of MulitBulkReply
                // Get the number of BulkStrings in MulitBulkReply
                expectedArgsCount = parseMulitBulkHeader(line)
                // Wait for the next line of MulitBulkReply
                readingMultiLine = true
            } else if isBulkHeader(line) {
                // We received the first line of BulkReply
                // Get the length of the second line of BulkReply, using bulkLen to tell readLine the length of the next line of BulkString
                bulkLen = parseBulkHeader()
                // There is a BulkString in this Reply
                expectedArgsCount = 1 
                // Wait for the next line of BulkReply
                readingMultiLine = true
            } else {
                // Handle StatusReply, IntReply, ErrorReply, etc
                reply := parseSingleLineReply(line)
                // Return the result through ch
                emitReply(ch)
            }
        } else {
            // Entering this branch indicates that we are waiting for the following lines of MulitBulkReply or BulkReply
            // MulitBulkReply has two subsequent lines, BulkHeader or BulkString
            if isBulkHeader(line) {
                bulkLen = parseBulkHeader()
            } else {
                // We are reading a BulkString, which may be MulitBulkReply or BulkReply
                args = append(args, line)
            }
            if len(args) == expectedArgsCount { // We have read all subsequent lines
                // Return the result through ch
                emitReply(ch)
                // Reset the state, ready to parse the next Reply
                readingMultiLine = false
                expectedArgsCount = 0
                args = nil
                bulkLen = 0}}}}Copy the code

Three, the implementation of memory database

Now that we’ve taken care of receiving and parsing the data, where do we store the data?

Regardless of the persistence part, all data of Redis, the KV database based on memory, needs to be stored in an in-memory hash table, and this hash table is the last component we need to write today.

Unlike single-threaded Redis, our implementation of Redis (Godis) works in parallel, so we have to consider various concurrency safety issues. There are several common concurrent secure hash table designs:

Sync. map: A concurrent hash table officially provided by Golang, suitable for scenarios with more reads and less writes. However, m. search will be copied to the new M. search after M. search is just promoted. In the case of a large amount of data, the replication operation will block all coroutines, which has a great hidden danger.
Juc.ConcurrentHashMap: Java’s concurrent hash table is implemented with segmented locking. Any thread that accesses the hash table during expansion will assist in the rehash operation, and all read and write operations will block until the rehash completes. Because of the large number of key-value pairs in a cached database and the high response time requirements for read and write operations, a JUC strategy is not appropriate.
Memcached hashtable: During a background thread rehash operation, the main thread determines whether the hash slot to be accessed has been rehashed to determine whether to operate old_hashtable or new_hashtable. This design is called progressive Rehash and has the advantage that rehash operations rarely block reads or writes to the main thread, making it ideal.

However, the implementation of progressive Rehash is very complex, so Godis adopts the segmented locking strategy (not the three above) widely used by the Golang community, which disperates the key into a fixed number of shards to avoid the whole rehash operation. A shard is a lock-protected map. When a shard rehashes, read and write operations are blocked, but other shards are not affected.

The code is as follows:

type ConcurrentDict struct {
    table []*Shard
    count int32
}

type Shard struct {
    m     map[string]interface{}
    mutex sync.RWMutex
}

func (dict *ConcurrentDict) spread(hashCode uint32) uint32 {
	tableSize := uint32(len(dict.table))
	return (tableSize - 1) & uint32(hashCode)
}

func (dict *ConcurrentDict) getShard(index uint32) *Shard {
	return dict.table[index]
}

func (dict *ConcurrentDict) Get(key string) (val interface{}, exists bool) {
	hashCode := fnv32(key)
	index := dict.spread(hashCode)
	shard := dict.getShard(index)
	shard.mutex.RLock()
	defer shard.mutex.RUnlock()
	val, exists = shard.m[key]
	return
}

func (dict *ConcurrentDict) Put(key string, val interface{}) (result int) {
	if dict == nil {
		panic("dict is nil")
	}
	hashCode := fnv32(key)
	index := dict.spread(hashCode)
	shard := dict.getShard(index)
	shard.mutex.Lock()
	defer shard.mutex.Unlock()

	if _, ok := shard.m[key]; ok {
		shard.m[key] = val
		return 0
	} else {
		shard.m[key] = val
		dict.addCount()
		return 1}}Copy the code

ConcurrentDict can guarantee concurrent security for a single key operation, but it still cannot meet the requirements of concurrent security. For example:

The Incr command needs to:Read -> Add -> WriteThree-step operation, read and write two-step operation is not atomic
The MSETNX command sets the value of all given keys if and only if all given keys do not exist. We need to ensure atomicity of the “check for multiple keys” and “write multiple keys” operations

So we need to implement db.Locker to lock a key or set of keys until we’re done.

The most straightforward idea for db.Locker is to use a map[string]* sync.rwmutex

The locking process is divided into two steps: initialize mutex -> lock
The unlocking process is also divided into two steps: Unlock -> release mutex

Then there is an unsolvable concurrency problem:

time	Coroutines a.	Coroutines B
1		locker[“a”].Unlock()
2	locker[“a”] = &sync.RWMutex{}
3		delete(locker[“a”])
4	locker[“a”].Lock()

Since coroutine B released the lock at t3, coroutine A failed to lock at T4. This exception can be avoided if coroutine B is unlocked without delete(locker[” A “]), but this can cause a serious memory leak.

We notice that the number of hash slots is much smaller than the number of keys, and conversely, multiple keys can share a hash slot. So instead of locking the key directly, we can lock the hash slot where the key is located to ensure security. On the other hand, there are fewer hash slots and they don’t consume too much memory even if they are not released.

type Locks struct {
    table []*sync.RWMutex
}

func Make(tableSize int) *Locks {
    table := make([]*sync.RWMutex, tableSize)
    for i := 0; i < tableSize; i++ {
        table[i] = &sync.RWMutex{}
    }
    return &Locks{
        table: table,
    }
}

func (locks *Locks)Lock(key string) {
    index := locks.spread(fnv32(key))
    mu := locks.table[index]
    mu.Lock()
}

func (locks *Locks)UnLock(key string) {
    index := locks.spread(fnv32(key))
    mu := locks.table[index]
    mu.Unlock()
}
Copy the code

When locking multiple keys, note that if coroutine A holds the lock of key A and tries to acquire the lock of key B, A deadlock will occur if coroutine B holds the lock of key B and tries to acquire the lock of key A.

The solution is for all coroutines to be locked in the same order. If both coroutines want to acquire the lock on key A and key B, they must acquire the lock on key A before acquiring the lock on key B, thus avoiding a loop of waiting.

Now that we have the basic components to build a Redis server, we just need to assemble the TCP server, protocol parser, and hash table and our Redis server is ready to go.

Finally, all of the above code simplifies Godis, an open source project written by myself: a Redis server implemented in Go language. Looking forward to your attention and Star:

Project address: github.com/HDT3213/god…

conclusion

Many friends’ daily work is mainly to write business code, for the framework, database, middleware, these “architecture”, “bottom code” have some fear.

But in this article, we only wrote three components and a few hundred lines of code to implement a basic Redis server. So the underlying technology is not difficult, as long as you are interested in the technology from the simple to the complex, the “underlying code” is not mysterious.

Interest is the best teacher, HelloGitHub found programming fun

Follow the HelloGitHub official account to receive updates as soon as possible.

There are more open source projects and treasure projects waiting to be discovered.

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

Write a Redis server with Go freehand (Godis)

Write a TCP server

Second, perspective Redis protocol

2.1 the string

2.2 empty

2.3 an array

2.4 Preparation for Parsing

2.5 Writing an RESP Protocol Parser

Three, the implementation of memory database

conclusion

Write a Redis server with Go freehand (Godis)

Write a TCP server

Second, perspective Redis protocol

2.1 the string

2.2 empty

2.3 an array

2.4 Preparation for Parsing

2.5 Writing an RESP Protocol Parser

Three, the implementation of memory database

conclusion

Related Posts

Elasticsearch – Part 1: Introduction and installation

The main types of dependency injection

Spring Boot annotation overview (1) : @bean