最近翻阅了几本跟Redis相关的书籍，比方《Redis规划与完成第二版》和钱老师的《Redis深度历险：核心原理与运用实践》，想着Redis的核心功用无非便是操作数据嘛，就像做一个Go言语版的Redis，不仅提升了对Redis源码的了解，也提高了Go言语的编码能力，说干就干。

代码地址：JaricY/miniRedis (github.com)

选用Go的原因是因为Go相关于C言语供给了更多的高级特性，例如并发编程和内存管理。因为Go言语具有杰出的并发特性，能够方便的完成单线程的多协程操作，提高miniRedis的功能，并且Go言语供给了内存安全确保，能够有用防止内存溢出和数组越界等常见问题。

这个手写的Redis是依据Redis6.0.18版本进行完成的，我将其称为miniRedis。

此代码参考了大佬的godis。godis是一个十分值得学习的项目！！！

大佬的博客：Finley (cnblogs.com)

大佬的源码：github.com/hdt3213/god…

估计完成的功用包含：

支撑String、List、Hash、Set、Sorted Set数据结构
支撑AOF持久化
支撑过期策略
支撑Mult指令开启事务机制

数据结构

到这篇文章发布时已完成和未完成的基本数据结构：

sds数据类型
dict字典
list链表结构
skiplist跳表
sorted set和set类型

这些数据类型因为篇幅原因只放上结构体，详细绑定的办法请自行检查源码

1.sds数据类型

SDS（Simple Dynamic Strings）可谓是Redis中最为重要的数据结构之一了。Redis是一个内存数据库，因而它的数据存储办法关于功能和内存运用状况有着至关重要的影响。

SDS是一个高效的字符串存储数据结构，它在Redis中被广泛运用，能够作为键和值存储在内存中。SDS在存储字符串时具有杰出的内存利用率，并且能够方便地完成字符串的拼接、分割等操作，进一步提高Redis的功能。

在Redis源码中，SDS的相关结构体界说在sds.c和sds.h。

（下图是sds.h文件中与sds相关的部分代码）

sdshdr是sds字符串方针的头部结构体，用于记载 sds 的长度和空余空间等信息

unsigned int len; 记载 buf 数组中已运用字节的数量

unsigned int free; 记载 buf 数组中未运用字节的数量

char buf[];字节数组，用于保存字符串值

char *sds 是一个指向buf首地址的指针

之所以运用SDS结构是因为SDS具有以下的优点：

动态分配：SDS能够动态分配内存，且能够依据字符串的长度实时调整所占用的内存，防止了固定大小的内存分配和浪费。
二进制安全：SDS采用相似于C字符串的办法保存数据，但与C字符串不同的是，它对二进制数据也具有杰出的支撑，防止了C字符串在处理二进制数据时呈现的问题。
优化字符串操作：SDS的完成对字符串的操作进行了优化，如长度计算、字符串拼接、截取等操作都是O(1)复杂度，这些操作在C字符串中一般都是O(n)复杂度。
兼容C字符串：SDS的完成与C字符串的运用办法十分相似，这使得Redis能够在不影响现有C字符串操作的前提下，逐渐替换C字符串为SDS。

在MiniRedis中，运用字符切片代替SDS的数据类型，因为切片类型同样能够动态的调整长度大小，一起也是二进制安全的。可是只能在切片结尾追加或许删去元素。

2.dict字典

在Redis中dict字典也十分重要，用于完成 Redis 的键值对存储以及完成 Redis 的哈希表数据结构。在 Redis 内部，很多运用了 dict 来支撑诸如键值对存储、快速查找等功用。详细来说，dict 是一个依据哈希表完成的字典，用于存储键值对，能够支撑 O(1) 的键值对查找和刺进操作。

在Redis源码中，dict字典的内容主要在dict.c和dict.h中

（下图是dict.h中与dict相关的内容）

其间：

dictEntry: 表明字典中的一个键值对，包含 key 和 value 以及下一个键值对的指针。

dictType: 表明字典类型的一些办法，包含 hash 函数、键仿制函数、值仿制函数、键比较函数、键开释函数、值开释函数。

dict: 表明字典的结构体，包含字典类型、私有数据、两个哈希表（一个旧的哈希表，一个新的哈希表，用于 rehash 操作）、rehashidx（表明当时是否在进行 rehash 操作）、iterators（表明当时正在遍历的迭代器数量）等字段。

为什么要有两个HT？什么是Rehash？

当添加一个元素时，假如当时哈希表现已到达了负载因子 load_factor，就会触发扩容操作，即会新建一个大小是原来的两倍的哈希表，然后将原哈希表中的一切元素从头散列到新哈希表中，完成后将新哈希表作为原哈希表持续运用。这个过程称为 rehash。

在rehash的过程中，体系会逐渐搬迁元素，每次搬迁一个元素，直到悉数搬迁完成。在 rehash 过程中，dict 结构体会一起持有两个哈希表，一个是正在被运用的哈希表，一个是正在 rehash 的哈希表，新的元素会被添加到正在被运用的哈希表中，罢了存在于原哈希表中的元素则会被逐渐地从原哈希表搬迁到新哈希表中。搬迁完成后，原哈希表被开释，新哈希表成为正在运用的哈希表。

Rehash会很耗费redis服务器的功能吗

假如每次都是需要等rehash完毕再进行操作的话肯定会很耗费服务器的功能。可是Redis采用了一种渐进式rehash。渐进式 rehash 操作经过将一次性履行的 rehash 操作分解成多个小过程履行，每次有拜访字典的时分就履行一次rehash的小过程，这样就能够分散每个过程对 Redis 服务器的影响，默许状况下每个小过程是处理500个哈希槽

在进行渐进式rehash的过程中，新添加的键值对会一起存在于两个哈希表中。关于查询操作，会先在第一个哈希表中进行查找，假如没找到就会在第二个哈希表中查找。关于新增、修正、删去操作，会在两个哈希表中一起进行操作，以确保数据的一致性。

在miniRedis中，是运用了如下的结构体完成dict

（datastruct/dict/dict.go）

package dict
// Consumer 是用于遍历Dict的函数，详细的由用户传入。假如返回了false则说明遍历中断
type Consumer func(key string, val interface{}) bool
// Dict 这儿界说的Dict是一个接口，界说了Dict需要完成的办法
type Dict interface {
   Get(key string) (val interface{}, exists bool)
   Len() int
   Put(key string, val interface{}) (result int)
   PutIfAbsent(key string, val interface{}) (result int)
   PutIfExists(key string, val interface{}) (result int)
   Remove(key string) (result int)
   ForEach(consumer Consumer)
   Keys() []string
   RandomKeys(limit int) []string
   RandomDistinctKeys(limit int) []string
   Clear()
}

（datastruct/dict/simple.go）

// SimpleDict 包装了一个map映射，不是线程安全的
type SimpleDict struct {
   m map[string]interface{}
}
func MakeSimple() *SimpleDict {
   return &SimpleDict{
      m: make(map[string]interface{}),
   }
}

（datastruct/dict/simple.go）

// ConcurrentDict 运用读写锁确保每个分片的安全
type ConcurrentDict struct {
   table      []*shard // 适当所以一个哈希表
   count      int32    // 表明一共有的键值对
   shardCount int      //字典分片的长度
}
type shard struct { // 字典分片，适当所以DictEntry
   m     map[string]interface{}
   mutex sync.RWMutex // 确保了m的读写操作的并发性
}

3.List链表

List是一个有序的字符串链表，链表能够存储一个有序的字符串列表。它支撑在链表的两头进行刺进、删去、查找等操作，因而能够完成行列（先进先出）、栈（后进先出）等数据结构。在Redis中，list能够存储的数据类型不仅仅是字符串，还能够是数字、JSON等等。

在Redis源码中，List结构主要存储在adlist.h中

listNode：链表节点，包含指向前驱和后继节点的指针，以及存储值的指针。

listIter：链表迭代器，包含指向下一个节点的指针以及遍历方向（正向或反向）。

list：链表结构体，包含指向头节点和尾节点的指针、链表长度、仿制、开释和匹配值的函数指针。

在miniRedis中链表的完成是这样的：

（datastruct/list/interface.go，界说了List接口）

package list
// Expected 检查给定项是否与期望值一致
type Expected func(a interface{}) bool
// Consumer 遍历链表.
type Consumer func(i int, v interface{}) bool
type List interface {
   Add(val interface{})
   Get(index int) (val interface{})
   Set(index int, val interface{})
   Insert(index int, val interface{})
   Remove(index int) (val interface{})
   RemoveLast() (val interface{})
   RemoveAllByVal(expected Expected) int
   RemoveByVal(expected Expected, count int) int
   ReverseRemoveByVal(expected Expected, count int) int
   Len() int
   ForEach(consumer Consumer)
   Contains(expected Expected) bool
   Range(start int, stop int) []interface{}
}

（datastruct/list/linked.go，完成了list的interface接口）

type LinkedList struct {
   first *node
   last  *node
   size  int
}
type node struct {
   val  interface{}
   prev *node
   next *node
}
func Make(vals ...interface{}) *LinkedList {
   list := LinkedList{}
   for _, v := range vals {
      list.Add(v)
   }
   return &list
}

4.Set调集

在Redis中，Set调集是由一个无序的字符串元素组成的调集，它的底层完成运用了两种数据结构：哈希表和整数调集。当调集的元素较少或许悉数都是整数时，会运用整数调集作为底层完成，而当调集的元素较多或许有一些元素是字符串时，会运用哈希表作为底层完成。

这是在server.h的源码中检查到的Set迭代器的界说：

subject: 指向被迭代的 set 调集方针的指针

encoding: 表明被迭代的调集方针的编码办法，能够是 REDIS_ENCODING_INTSET 或 REDIS_ENCODING_HT，别离表明运用整数调集和哈希表两种数据结构来完成 set 调集。

ii: 表明整数调集迭代器的当时索引位置，当 encoding 为 REDIS_ENCODING_INTSET 时有用。

di: 指向哈希表迭代器的指针，当 encoding 为 REDIS_ENCODING_HT 时有用。

在MiniRedis中就只运用dict字典作为set调集的底层完成：

（datastruct/set/set.go）

// Set 是一组依据哈希表的元素
type Set struct {
   dict dict.Dict
}
func Make(members ...string) *Set {
   set := &Set{
      dict: dict.MakeSimple(),
   }
   for _, member := range members {
      set.Add(member)
   }
   return set
}

5.skipList跳表

Redis中的跳表（Skip List）是一种依据有序链表的数据结构，它利用概率的思想在有序链表的基础上添加多级索引，以到达快速查找的意图。跳表能够用于完成有序调集，当调集中的元素比较多时，跳表的功能优于红黑树，但关于少量元素的状况，红黑树更加高效。

跳表由多层结构组成，每一层都是一个有序的链表，最底层的链表包含一切元素。每一层的链表都是前一层链表的一个子集，即一层链表中的元素鄙人一层链表中必定呈现。

跳表中每个节点包含一个元素和若干个指向其他节点的指针，这些指针称为跳表的“跳动指针”。节点的跳动指针能够指向当时节点下面的节点，也能够指向下一层中对应的节点，这样能够在多层链表中快速地查找元素。

跳表经过随机化的办法树立索引，不仅能够确保查询功率，还能确保刺进和删去操作的功率。在刺进和删去元素时，跳表经过调整节点的跳动指针来维护跳表的结构，使其坚持有序性和平衡性。

跳表经过在底层链表的基础上添加多级索引，能够提高查找的功率，完成快速查询。跳表中，每一层都是一个有序的链表，每个节点保存了指向下一层的指针。因为每一层都是有序的，因而能够经过比较当时节点的值与方针值的大小，来确认在哪一层持续查找。

经过在跳表中添加多级索引，能够防止遍历整个链表查找方针节点的状况，然后提高查找的功率。当需要查找一个节点时，能够从最高层开始查找，直到找到对应的节点为止。假如当时层的下一个节点大于方针值，就切换到下一层持续查找；假如当时层的下一个节点小于方针值，就持续向当时层的下一个节点查找，直到找到对应的节点。

经过跳表，能够完成快速查找、刺进和删去，时间复杂度均为 O(log n)。这使得跳表成为了一种高效的数据结构，被广泛运用于各种范畴，如：

Redis中的有序调集zset
LevelDB、RocksDB、HBase中Memtable
ApacheLucene中的TermDictionary、Posting List

在Redis的源码中，skipList的相关信息在server.h中有提及

其间 zskiplistNode 表明跳表中的节点，包含了成员（ele）和分值（score）两个字段，还包含了一个 backward 指针和一个 level 数组，level 数组是一个伸缩性的数组，表明了每个节点在不同层级上的状况，这个 level 数组是依据概率分布函数随机生成的。

zskiplist 则是跳表的主体结构，包含了 header 和 tail 两个指针，表明跳表的头尾节点，length 表明跳表的长度，level 表明当时跳表中节点的最大层级。

在miniRedis中，是运用了如下的结构体来完成跳表结构：

(datastruct/sortedset/skiplist.go)

// Element 保存了元素的内容和分值
type Element struct {
   Member string
   Score  float64
}
// Level 表明层级 ，适当所以zskiplistLevel结构体
type Level struct {
   // 前驱指针
   forward *node
   // 与前一个点的跨度
   span int64
}
// 表明一个结点，适当所以zskiplistNode
type node struct {
   // 元素值和分数
   Element
   // 后驱指针
   backward *node
   level    []*Level // level[0] 是最底层
}
// 跳表结构
type skiplist struct {
   header *node
   tail   *node
   // 具有的元素个数
   length int64
   // 最高层级
   level int16
}

6.sorted set 有序调集

Redis中的Sorted Set（有序调集）是一个十分有用的数据结构，它相似于Set（调集），可是每个元素都会相关一个分数（score），依据这个分数对元素进行排序，使得调集中的元素是有序的。Sorted Set中每个元素的值是仅有的，但分数能够重复。

Sorted Set支撑多种操作，包含添加、删去、查找、遍历和范围查询等。运用Sorted Set能够轻松地完成一些常见的问题，比方排行榜、计数器、最高分查询等。内部完成是依据跳动表（Skip List）的数据结构，这种数据结构能够快速地查找、刺进和删去元素，一起也能够维护元素的顺序。

Redis的有序调集是经过跳动表（skiplist）和哈希表两种数据结构完成的。

在Redis源码中，sorted set是运用zset结构体表明的，界说在server.h中

在MiniRedis中运用如下的结构体来表明sorted set

(datastruct/sortedset/sortedset.go)

type SortedSet struct {
   dict     map[string]*Element
   skiplist *skiplist
}
func Make() *SortedSet {
   return &SortedSet{
      dict:     make(map[string]*Element),
      skiplist: makeSkiplist(),
   }
}

下一遍传送门：运用Go从零完成一个Redis（二）：创建TCP服务器 – ()

使用Go从零实现一个Redis（一）：基本数据结构

数据结构

这些数据类型因为篇幅原因只放上结构体，详细绑定的办法请自行检查源码

1.sds数据类型

2.dict字典

为什么要有两个HT？什么是Rehash？

Rehash会很耗费redis服务器的功能吗

在miniRedis中，是运用了如下的结构体完成dict

（datastruct/dict/dict.go）

（datastruct/dict/simple.go）

（datastruct/dict/simple.go）

3.List链表

在miniRedis中链表的完成是这样的：

（datastruct/list/interface.go，界说了List接口）

（datastruct/list/linked.go，完成了list的interface接口）

4.Set调集

在MiniRedis中就只运用dict字典作为set调集的底层完成：

（datastruct/set/set.go）

5.skipList跳表

在miniRedis中，是运用了如下的结构体来完成跳表结构：

(datastruct/sortedset/skiplist.go)

6.sorted set 有序调集

在MiniRedis中运用如下的结构体来表明sorted set

(datastruct/sortedset/sortedset.go)

作者信息

使用Go从零实现一个Redis（一）：基本数据结构

数据结构

这些数据类型因为篇幅原因只放上结构体，详细绑定的办法请自行检查源码

1.sds数据类型

2.dict字典

为什么要有两个HT？什么是Rehash？

Rehash会很耗费redis服务器的功能吗

在miniRedis中，是运用了如下的结构体完成dict

（datastruct/dict/dict.go）

（datastruct/dict/simple.go）

（datastruct/dict/simple.go）

3.List链表

在miniRedis中链表的完成是这样的：

（datastruct/list/interface.go，界说了List接口）

（datastruct/list/linked.go，完成了list的interface接口）

4.Set调集

在MiniRedis中就只运用dict字典作为set调集的底层完成：

（datastruct/set/set.go）

5.skipList跳表

在miniRedis中，是运用了如下的结构体来完成跳表结构：

(datastruct/sortedset/skiplist.go)

6.sorted set 有序调集

在MiniRedis中运用如下的结构体来表明sorted set

(datastruct/sortedset/sortedset.go)

相关文章

这篇文章汇聚33个BUG！来挑战一下，看看你能找出来几个？

为Android构建现代应用——应用架构

JS基础-面向对象

Java 集合框架中的 List

作者信息