preface
When I was learning Redis, I read a lot of articles and bought a lot of books, but I forgot a lot of knowledge just after I read it. I read it repeatedly and forgot it repeatedly. And a lot of things to see also just remember, but actually did not really understand it. The so-called paper come zhongjue shallow, must know this to practice, so decided to refer to Redis source code, step by step to achieve a simple version of Redis, deepen understanding.
The whole project of Redis is relatively large. In the first stage, we first put together the framework of the whole core, which can execute simple GET and set commands, and then implement various functions based on this framework.
The whole project refers to Redis 3.0 implementation and uses Golang as the development language
Original link:Juejin. Cn/post / 695135…
Let’s take a look at our implementation:
The project structure
The whole Redis project can be divided into the following chunks:
The data structure
Mainly the realization of data structure, including:
- SDS dynamic string implementation
- Implementation of adList double – ended linked list
- The implementation of dict dictionaries
- Zskiplist skiplist implementation
- Ziplist Implements zipmap compression tables and fields
- Hyperloglog Implementation of Hyperloglogr
The data type
- Object Redis object (type) system implementation.
- T_string Implementation of the string key.
- T_list list key implementation.
- T_hash hash key implementation.
- T_set set key implementation.
- T_zset ordered set key implementation.
- Hyperloglog Implementation of the Hyperloglog key
The database
Db Redis database notify database notification RDB RDB persistence AOF AOF persistence
The client is related to the server
Ae * Redis event handler implementation, Redis own implementation of a set of event handlers based on the REACTOR pattern
Networking: A library used to send and receive commands, parse protocols, and create/destroy clients
Redis single Redis server implementation
The cluster related
Replication Implementation of the replication function Sentinel implementation of cluster Implementation of the cluster
This is the general breakdown of Redis functionality, with some of the more isolated and marginal features not listed, such as monitoring, slow queries, Lua scripting, transactions, and so on. When we implement our own Redis, we will divide our functions according to the above structure.
implementation
Let’s start now, to implement our own Redis, our first stage requirements are very simple: Redis client Redis – CLI can connect to our Redis server, and simple string get and set operations, as well as quit operation. There are many features and data structures that we will skip at this stage or simply use existing implementations in Golang instead.
In the following implementation process, if it involves some logic or principle that is not used in this function, we will skip it for the moment, and we will explain it in detail when we implement it later.
Data structure implementation
To implement string operations alone, we only need to implement a few necessary data structures, including SDS, dict, and robj.
SDS implementation
SDS is a customized string in Redis. SDS is actually a pointer to type char*, but it is preceded by a header SDSHDR, which contains two unsigned ints and a char[] to point to the actual char array.
typedef char *sds
struct sdshdr {
unsigned int len; // The actual size used in buF is 5
unsigned int free; // The free size in buf is 5
char buf[]; // Actual char array, ['H','E','L','L','O','\0',,,,,]
};
Copy the codeRelated source documents: SDS.h, SDS.c
Since Golang already has a complete string type, we will not implement SDS and use string instead:
sds.go
type sds string
Copy the codeDict implementation
Dict is a dictionary structure defined in Redis, which is used in many places. The data we store is actually stored in dict, which is mainly composed of three parts:
typedef struct dict// Contains twohashTables, one for storing data and one for progressiverehash
typedef struct dictht //hashTable,keythroughhashAfter the functionhashTable, in which each element is a linked listtypedef struct dictEntry// The actual storage object, a linked list structure, mainly including 'key`, `value` and `next'Pointer, and oneunionStructure is used to store additional data.Copy the codeRelated source files: dict.h, dict.c
If you are interested, you can directly read the source code, respectively in dict.h and dict.c. Without going into details here, we won’t implement the dict structure ourselves this time, but will use the Map in Golang directly, which will be explained later when we implement the data structure part.
dict.go
type dict map[interface{}]interface{}
// Find the element in the field
func (d dict) dictFind(key interface{}) interface{} {}
// Add a new element. If it already exists, err is returned. Ok is added successfully
func (d dict) dictAdd(key interface{}, val interface{}) int{}
// Replaces elements from the dict, if they already exist, and returns 0
// If it does not exist, add it and return 1
func (d dict) dictReplace(key interface{}, val interface{}) int{}
// Remove elements from the dict
func (d dict) dictDelete(key interface{}) {}
Copy the codeRobj implementation
Another important data structure in Redis is robj, which is a generic data structure that can actually point to different data structures, somewhat like Java Object (which is not). Robj defines:
#define REDIS_STRING 0 #define REDIS_LIST 1 #define REDIS_SET 2 #define REDIS_ZSET 3 #define REDIS_HASH 4 typedef struct redisObject { unsigned type:4; // Unsigned Encoding :4; Unsigned lRU :REDIS_LRU_BITS; //lru time int refcount; // Reference count, in some cases robj objects can be shared void * PTR; // Point to the underlying data structure of the implementation object} robj;Copy the codeRelated source files: redis. H, object.c
We also refer to its structure to implement our robj:
object.go
type robj struct {
rtype uint8
encoding uint8
lru uint32
refcount int
ptr interface{}}// Create the robj object
func createObject(t uint8, ptr interface{}) *robj{
return &robj {
rtype: t,
encoding: 0,
refcount: 1,
ptr: ptr,
lru: lruClock(),
}
}
Copy the codeThe list implementation
There is also a list, which we won’t use this time, but can be defined first:
rlist.go
type rlist list.List
func (l *rlist) Init() *rlist {
lt := (*list.List)(l).Init()
return (*rlist)(lt)
}
Copy the codeother
Other data structures will not be covered at all this time, so we will ignore them and implement them later.
The DB implementation
Next is the storage part, in Redis mainly use a redisDb structure for data storage, which contains two dictionaries: Dict and Expires are used to store key-value data and expiration time of a key, respectively.
db.go
// Store data structures
type redisDb struct{
dict *dict //dict is used to store k-v data, key = *robj, value = *robj
expires *dict // Expires, used to store a key with an expiration time, key = *robj, value = timestamp
id int //id
}
func (r *redisDb) setKey(key *robj, val *robj){
if r.lookupKey(key) == nil {
r.dbAdd(key, val)
}else {
//override
r.dbOverwrite(key, val)
}
val.refcount++
}
func (r *redisDb) lookupKey(key *robj) *robj {
//TODO expire if needed
return r.doLookupKey(key)
}
func (r *redisDb) setExpire(key *robj, expire uint64) {
kde := r.dict.dictFind(key.ptr)
ifkde ! =nil {
r.expires.dictAdd(key.ptr, expire)
}
}
Copy the codeServer-side implementation
The single server of Redis is mainly implemented in Redis. H and Redis. C, among which the most core is redisServer, redisClient and redisCommand.
redisServerIt mainly saves various configurations of the server (including network, persistence, cluster and other configuration information), maintains the storage structure (DB), maintains the status and data related to the network of Redis server (client connection, FD, Eventloop, etc.), and statistical data, etc.redisClientIt is mainly used to maintain client connection information, including DB, FD, request related data, response related data and a series of data and status.redisCommandIt mainly saves the command name of Redis and the corresponding command processor.
redis.go
//Redis server structure
type redisServer struct {
pid int //pid
db *redisDb //db
commands *dict //Redis command dictionary, key = SDS (commands, such as get/set), value = *redisCommand
clientCounter int // Store the client id counter
clients *dict // Client dictionary, key = id, value = *redisClient
port int / / port
tcpBacklog int
bindaddr string / / address
ipfdCount int
events *eventloop // Event handler
lruclock uint32
}
type redisClient struct {
id int
conn gnet.Conn // Client connection
db *redisDb //db
name *robj
argc int // Number of commands
argv []*robj / / command value
cmd *redisCommand // Command currently executed
lastcmd *redisCommand // The last command executed
reqtype int // Request type
queryBuf sds // Data read from the client
buf []byte // Prepare data to be sent back to the client
bufpos int // Pos of the data sent back to the client
sentlen int // Number of bytes sent
}
//reids command structure
type redisCommand struct {
name sds // Command name
redisCommandFunc func(client *redisClient)// Command handlers
}
Copy the codeIn fact, there are a lot of definitions of redisServer and redisClient in Redis, especially redisServer. Most of them are ignored here and we only care about what we need at present.
Next is the initialization of redisServer, which is divided into initialization configuration and initialization of server:
redis.go
// Initialize the server configuration
func initServerConfig(a) {
server.port = redisServerPort
server.tcpBacklog = redisTcpBacklog
server.events = &eventloop{}
populateCommandTable()
}
// Initialize the server
func initServer(a) {
server.pid = os.Getpid()
server.clients = &dict{}
// Initialize the event handler
server.events.react = dataHandler
server.events.accept = acceptHandler
//if server.ipfd == nil {
// os.Exit(1)
/ /}
// Initialize db
server.db = &redisDb{
dict: &dict{},
expires: &dict{},
id: 1,
}
createSharedObjects()
}
Copy the codeThere is also general processing logic for commands implemented here (more on this below) :
redis.go
// Process the command
func processCommand(client *redisClient) int {}
Copy the codeAt the time of processCommand, the parsed parameter data is already available in the redisClient, so you just need to process it. The data receiving, sending, client creation and protocol parsing are implemented in the network layer.
Networking implementation
Redis implements an event model based on the Reactor model instead of using the Libevent library: Typedef struct aeEventLoop{}, which supports epoll, SELECT, kqueue, and Solaris-based event ports, provides drivers for two event types: IO events (including READ/write events of IO) and timer events (one-time timer and cyclic timer).
Instead of implementing this by ourselves, we choose to use the open source framework GNET, a network library based on event-loop event-driven, and epoll and Kqueue system calls are also used in the bottom layer. If you’re interested, go to Github.
eventloop.go
type eventloop struct {
react func(frame []byte, c gnet.Conn) (out []byte, action gnet.Action)
accept func(c gnet.Conn) (out []byte, action gnet.Action)
*gnet.EventServer
}
// Read event handler
func (e *eventloop) React(frame []byte, c gnet.Conn) (out []byte, action gnet.Action) {
return e.react(frame, c)
}
// New connection processing
func (e *eventloop) OnOpened(c gnet.Conn) (out []byte, action gnet.Action) {
return e.accept(c)
}
/ / start
func elMain(a) {
addr := "tcp://" + server.bindaddr+":"+ strconv.Itoa(server.port)
log.Printf("listening at: %s", addr)
err := gnet.Serve(server.events, addr,
gnet.WithMulticore(false), gnet.WithNumEventLoop(1))
iferr ! =nil {
log.Fatal(err)
}
}
Copy the codeThere are two main events we care about here: React, which is a read event, and OnOpened, where a new connection is created. In networking. Go, the two event callbacks are registered in the EventLoop at server initialization.
networking.go
// When a new request is received, create a client to process the command and reply to the command
func acceptHandler(c gnet.Conn) (out []byte, action gnet.Action) {
client := createClient(c)
server.clients.dictAdd(client.id, client)
log.Printf("accept connection, client: %v", client)
return out, action
}
// Received the command from the client
func dataHandler(frame []byte, c gnet.Conn) (out []byte, action gnet.Action) {
// Find the corresponding client object
client := server.clients.dictFind(c.Context()).(*redisClient)
// Set the data to the client
client.queryBuf = sds(frame)
defer func(a) {
if err := recover(a); err ! =nil {
var buf [4096]byte
n := runtime.Stack(buf[:], false)
log.Print(err)
log.Printf("==> %s \n".string(buf[:n]))
}
}()
// Process data
processInputBuffer(client)
return out, action
}
Copy the codeYou can see that the logic is simple: when the connection creation event is triggered, we create a redisClient object and put it into the server. When the read event is triggered, we get the corresponding redisClient object from the server and then execute the logic to process the data.
networking.go
Func processInputBuffer(client *redisClient) {// Determine the command type if client.queryBuf[0] == '*' {client.reqType = redisReqMultibulk }else { client.reqtype = redisReqInline } log.Printf("client reqtype is : %v", client.reqType) // Protocol resolution if client.reqType == redisReqInline {if processInlineBuffer(client)! = nil { //error } } if client.reqtype == redisReqMultibulk { if processMultibulkBuffer(client) == redisErr { //error log.Printf("analysis protocol error") } }else { panic("Unknown request type") } if client.argc == 0 { resetClient(client) }else { if processCommand(client) ==redisErr { //error } resetClient(client) //server.currentClient = nil } }Copy the codeProcessing data is actually a parsing protocol, and the parsed parameters are put into redisClient for subsequent command processing. For example, we receive the following data: *3\r\n$3\r\nSET\r\n$5\r\nmykey\r\n$7\r\ nmyValue \r\n, formatted slightly:
*3
$3
SET
$5
mykey
$7
myvalue
Copy the codeArgc =3 and the actual parameter value (a robj array) : redisClient.argv=[SET,mykey, myValue]
IO /topics/prot…
When the command is processed, we need to return data to the client. The core method is addReply:
networking.go
func addReply(client *redisClient, robj *robj) {
log.Printf("add reply: %v", robj)
addReplyToBuffer(client, robj.ptr.(sds))
sendReplyToClient(client)
}
func addReplyToBuffer(client *redisClient, data sds) {
copy(client.buf[client.bufpos:], data)
client.bufpos = client.bufpos + len([]byte(data))
}
func sendReplyToClient(client *redisClient) int{
log.Printf("send reply to client: %v", client.buf[client.sentlen:client.bufpos])
err := client.conn.AsyncWrite(client.buf[client.sentlen:client.bufpos])
iferr ! =nil {
log.Printf("err: %v", err)
}
client.sentlen = client.bufpos
if client.flags & redisCloseAfterReply == 1 {
freeClient(client)
}
return redisOk
}
Copy the codeThe logic is also simple: write the data to the redisClient write buffer, then read the data from the buffer using the sendReplyToClient method and write it back to the client.
Why write so many moves to the buffer first? Because in the Redis implementation sendReplyToClient is registered in aeEventloop via IO write events, scheduled by AE, their data needs to be passed through the buffer of redisClient. Redis also has a number of clever designs for writing data. For example, it has an upper limit for each send: REDIS_MAX_WRITE_PER_EVENT = (1024*64), that is, the maximum number of bytes sent per IO write event is only 64K. This is due to its single-threaded design, which ensures that when a large amount of data needs to be sent (such as keys *), It can also receive other requests.
Command processing
Finally, let’s look at command processing. As mentioned above, common command processing logic is implemented in the server:
redis.go
// Process the command
func processCommand(client *redisClient) int {
if client.argv[0].ptr == "quit" {
client.flags |= redisCloseAfterReply
addReply(client, shared.ok)
return redisErr
}
client.cmd = lookupCommand(client.argv[0].ptr.(sds))
client.lastcmd = client.cmd
if client.cmd == nil {
log.Printf("client is empty,return err")
addReply(client, shared.err)
return redisOk
}
call(client, 0)
return redisOk
}
func lookupCommand(name sds) *redisCommand {
cmd := server.commands.dictFind(name)
log.Printf("lookup command: %v", cmd)
if cmd == nil {
return nil
}
return cmd.(*redisCommand)
}
//Call() is the core of Redis execution of a command
func call(client *redisClient, flag int) {
client.cmd.redisCommandFunc(client)
}
Copy the code- If the command is quit, reply OK and set the client flag to release the client.
- It then looks for the command and returns err if none exists
- If the corresponding command handler is found, it is executed
The actual command processor is stored in the Commands dictionary:
redis.go
var (
redisCommandTable = []*redisCommand{
{sds("get"), getCommand},
{sds("set"), setCommand},
}
)
Copy the codeWe define a global command mapping table, which implements only get and set handlers, both of which are string commands, so implement them in string datatypes:
t_string.go
//SET key value [NX] [XX] [EX <seconds>] [PX <milliseconds>]
// Save the key and value to db.dict
// If an expiration date is set, it will be saved in db.expires
func setCommand(client *redisClient) {
log.Print("starting set command")
var expire *robj = nil
flags := redisSetNoFlag
unit := unitSeconds
for i:=3; i < client.argc; i++ {
c := client.argv[i].ptr.(sds)
var next *robj = nil
if i < client.argc - 1 {
next = client.argv[i + 1]}// Handle NX XX EX PX
if (c[0] = ='n' || c[0] = ='N') && (c[1] = ='x' || c[1] = ='X') {
flags |= redisSetNx
}else if (c[0] = ='x' || c[0] = ='X') && (c[1] = ='x' || c[1] = ='X') {
flags |= redisSetXx
}else if (c[0] = ='e' || c[0] = ='E') && (c[1] = ='x' || c[1] = ='X') && next ! =nil {
unit = unitSeconds
expire = next
}else if (c[0] = ='p' || c[0] = ='P') && (c[1] = ='x' || c[1] = ='X') && next ! =nil {
unit = unitMilliseconds
expire = next
}else {
// The command is abnormal
addReply(client, shared.syntaxerr)
return
}
}
setGenericCommand(client, flags, client.argv[1], client.argv[2], expire, unit)
}
//GET key
func getCommand(client *redisClient) {
getGenericCommand(client)
}
// The get command is simple and returns a value directly from the db.dict based on the key
func getGenericCommand(client *redisClient) int {
o := client.db.lookupKey(client.argv[1])
if o == nil {
addReply(client, shared.ok)
return redisErr
}else {
addReplyBulk(client, o)
return redisOk
}
}
func setGenericCommand(client *redisClient, flags int, key *robj, val *robj, expire *robj, unit uint64) {
var milliseconds uint64 = 0
ifexpire ! =nil {
imsstr, _ := strconv.Atoi(string(expire.ptr.(sds)))
milliseconds = uint64(imsstr)
if milliseconds < 0 {
addReply(client, shared.err)
return}}if unit == unitSeconds {
milliseconds = milliseconds * 1000
}
if (flags&redisSetNx > 0&& client.db.lookupKey(key) ! =nil) ||
(flags&redisSetXx > 0&& client.db.lookupKey(key) ! =nil) {
addReply(client, shared.nullbulk)
}
client.db.setKey(key, val)
ifexpire ! =nil {
// Add a key to db.expires if expire is present
client.db.setExpire(key, mstime()+milliseconds)
}
addReply(client, shared.ok)
}
Copy the codeThe implementation logic of these two commands is simple. Set simply stores keys and values in the db.dict dictionary. If an expiration date is set, a db.expires file is required, but value is the expiration date. Get is to query the corresponding value from the db.dict and return it to the client.
Start the
At this point, the basic function has been implemented! Add startup logic to run our server:
redis.go
func Start(a) {
initServerConfig()
initServer()
elMain()
}
Copy the codemain.go
func main() {
redis.Start()
}
Copy the codeconclusion
Here is a simple Redis server even if the implementation is complete, although only a simple implementation of GET and set methods, but the shelf has been built up, all our subsequent functions will be based on this core logic to expand, the next article is expected to implement Redis key expiration strategy.
Full code: github.com/cadeeper/my…