分类默认分类下的文章

> 分析的Redis版本基于6.0
## Redis Hash
#### 应用场景
哈希列表结构是一般在编程上非常重要的结构，因为它的查询性能接近O(1)，所以是一种非常高效的数据结构。我们平时用的字典（dict）往往都是通过哈希列表去实现的，而redis中自己实现的hash结构也非常重要。在redis中所有的键值都是通过hash结构去管理的，比如我们键入命令set a hello时，其实在redis server用结构redisDb->dict来进行维护，其键和值都是redisObject：
```c
typedef struct redisDb {
    dict *dict;                 /* The keyspace for this DB */
    dict *expires;              /* Timeout of keys with a timeout set */
	...
} redisDb;
```

#### Hash结构
redis hash结构和普通的hash结构还是非常像的，但是因为它有一个渐进式hash过程（下面会讲），所以它其实有两个hash table。
```c
//字典采用链表处理冲突，而且在数据过多的时候会自动进行渐进式重新hash
typedef struct dict {
	//一些函数指针
    dictType *type;
	
    void *privdata;
	
	//rehash的oldhash和newhash
    dictht ht[2];
	
	//rehash的进度(hash槽索引), 如果是-1, 则表示没有进行rehash, 否则就是在rehash
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

typedef struct dictht {
	//指向hash槽的头部
    dictEntry **table;
	
	//分配的hash槽总数量
    unsigned long size;
	
	//计算hash槽的掩码值, 它等于size - 1
    unsigned long sizemask;
	
	//在用的hash槽数量
    unsigned long used;
} dictht;

//字典的每个元素
typedef struct dictEntry {
	//元素的健
    void *key;
	
	//指向的值,或是指向一个对象，或者数值...
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
	
	//采用链表的方式，next指向hash槽内的下个元素
    struct dictEntry *next;
} dictEntry;
```
比如size=6的hash表按照字母顺序进行编码（比如a:1,b:2,c:3,d:4,e:5,f:6,g:1...)，并且插入到hash列表中后的图示如下：
![](https://chenxf.org/usr/uploads/2022/02/3822166739.png)
#### 键冲突处理
我们知道所有的hash列表都会冲突，冲突是由于key被hash到一个bucket（有些资料里叫hash槽）里引起的。Redis采用如下的技术处理键的冲突：
- 选择好的Hash函数,尽量让键分布均匀
- 用拉链的方式处理冲突，即使键值过载，也会被分散到bucket内的链表里
- 设定一个阈值，如果元素过载，则会进行自动扩容

散列表的处理冲突方式一般有两种，开放定址和拉链法，而Redis采用的是拉链法，实现上用链表来管理冲突的键值对。Redis在Hash函数的选取上则用的是SipHash，这种算法有较强的安全性，可以用来防御“Hash-flooding”。

#### 扩容/缩容
当随着元素的增加，如果Hash列表不进行扩张，则必然会增加单个Bucket的元素数量，而这会导致命中该Bucket的检索操作退化到查询列表的操作，而这是不能被接受的，所以Redis设计了自动扩容的机制。
扩容是在添加操作完成的，当元素使用比例过了设定的阈值，则进行自动扩容：
```c
//超过阈值，开始进行hash扩展，扩展长度为两倍，里面会进行微调整
    if (d->ht[0].used >= d->ht[0].size &&
        (dict_can_resize ||
         d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
    {
        return dictExpand(d, d->ht[0].used*2);
    }
```
Redis扩容本身并不复杂，它会把散列的空间扩大到现有元素的2倍左右大小。相比扩容，缩容采用了更加主动的方式，采用定时器进行周期性的空间回收，具体操作在tryResizeHashTables函数，收缩的条件为空间利用率下降为10%，就会进行一次收缩，收缩过后的大小刚好大于原有键值对数量的2的n次。([dictResize](https://github.com/redis/redis/blob/6.0/src/dict.c#L135 "dictResize"))
```c
//低于10%的时候，会进行缩容
int htNeedsResize(dict *dict) {
    long long size, used;

size = dictSlots(dict);
    used = dictSize(dict);
	//use/size < 0.10
    return (size > DICT_HT_INITIAL_SIZE &&
            (used*100/size < HASHTABLE_MIN_FILL));
}
```
#### 渐进式Rehash
作为hash列表，已有的功能都是完整的，但是作为高性能的Redis服务器如果只是容许暂停服务进行rehash，那将是不可承受的。Redis在设计上采用了渐进式的结构，也就是在rehash阶段，会有两个散列表存在，一个用来存目前用的健值对ht1，另外一个则是新扩张后的ht2。在这个阶段两个ht都需要去查找和更新，当完成这个阶段只需要考虑ht1。
可以用一个例子来图示一下，假设为了方便演示，resize比例为1的时候就进行扩张，初始化hash大小为2个Bucket，插入3个键值对后的hash状态如下：
![](https://chenxf.org/usr/uploads/2022/02/2878736334.png)
这时候，其实hash列表里的键值对已经达到扩容的零界点，当请求插入l=33的时候，根据used/size=4/2=2>1(dict_force_resize_ratio )，所以会分配一个2倍空间(2*used)大小给新的ht1，并且启动**渐进式hash迁移**。而在hash迁移期间，所有的插入请求的键值对都会放到新的ht1。
![](https://chenxf.org/usr/uploads/2022/02/4075936131.png)
当我们请求删除e为健的键值对时，其实它会进行两步操作(其实如果一旦进入hash迁移，则对于查找/添加/替换都会有下面的第一步)：
1. 依次获取ht0的一个bucket，并且迁移到ht1中
2. 在ht0和ht1中查找是否有健，如果找到的话进行删除
![](https://chenxf.org/usr/uploads/2022/02/3697740524.png)
*图画的不是很好，表达的是2个键值对迁移过来后，其中一个被删除（画叉的是被删除，画加号的是被正常迁移过来，顺序是先迁移，后删除）*

这时候如果来个检索操作，比如检索b为健的值是多少，同样检索操作也需要执行一次迁移操作，也即：
1. 依次获取ht0的一个bucket，并且迁移到ht1中
2. 在ht0和ht1中查找是否有健，如果找到的话返回
对于这里的例子，本次操作会迁移Bucket2，操作后会使ht0没有键值对（used==0）。而当ht0为空时候，ht1被作为新的ht0(ht1指针给ht0)，ht1清空作为下一次迁移用，本轮迁移标记rehashidx置空。
![](https://chenxf.org/usr/uploads/2022/02/3142013963.png)

需要说明的是如果在迁移阶段进行检索，并且第一步之后迁移也没有完成，则查找的时候会对h0和h1两个hash表都进行检索，因为键值有可能在h0也有可能在h1。
最后再补充一点，渐进式迁移不光光在查找/添加/替换等操作里有，而且在定时任务里也会给予一定的时间（1ms）进行迁移。

### 参考
《算法》散列表部分
《数据结构与算法之美》散列表部分

Redis Sds原理

作者: nbboy
时间: 2022-02-24
分类: 默认分类,C
评论

> 分析的Redis版本基于6.0

## Redis Sds
#### 应用场景
sds会应用在很多地方，可以说在redis中所有需要用到string的地方都会用到sds。特别的，我们会想到字符串命令的key和value底层都是用sds存储的[(stringCommand)][1]。可以先来看一个redis命令:
```bash
set a hello
```
其实该命令会在服务端接受后被存储到robj对象中，key和value都是如此，该结构有如下的结构：
```c
/* The actual Redis Object */
#define OBJ_STRING 0    /* String object. */
#define OBJ_LIST 1      /* List object. */
#define OBJ_SET 2       /* Set object. */
#define OBJ_ZSET 3      /* Sorted set object. */
#define OBJ_HASH 4      /* Hash object. */

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits access time). */
    int refcount;
    void *ptr;
} robj;
```
其中type就表示的是什么类型，对于字符串命令就是0，当然还有很多类型，定义在OBJ_XXX常量里，这里不做展开。Redis是C语言开发的，而对于C给带来高性能的同时也会带来一些字符串安全的问题，很多0Day都是通过栈空间的溢出来做文章，所以作者在设计sds的时候考虑到了内存安全性，后面会具体看到这部分设计。
#### Sds的结构
当用户键入上面set a hello命令的时候，值会存入sds最终如下图所示：
![](https://chenxf.org/usr/uploads/2022/02/4228211705.png)
Buf指向的值才是最终的字符串内容，并且以\0作为结束，这个和C语言的字符串是一样的。Len就是Buf指向的字符串的长度，所以如果计算字符串长度不需要每次调用strlen,而是直接返回Len就可以，计算成本为O(1)！Alloc为sds预分配的长度，一般情况下它比Len要大一点，具体细节下面会说。
sds根据不同的字符串长度，会使用不同的结构去管理，比如用32位可以表示的长度则为sdshdr32，其他结构也是类似的:
```c
struct __attribute__ ((__packed__)) sdshdr32 {
	//字符串分配出去的长度
    uint32_t len; /* used */
	
	//分配的总长度
    uint32_t alloc; /* excluding the header and null terminator */
	
	//各种类型, sdshdr*
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
	
	//字符串真正的指向
    char buf[];
};
```

#### Sds的扩容和缩容
Sds的扩容也是会根据字符串的大小进行按需扩容，而且每次扩容都是按两倍大小进行扩容，用伪代码描述为：
![](https://chenxf.org/usr/uploads/2022/02/228956695.png)
当然有扩容也会有缩容，用户可以主动请求缩容，容量会缩小为刚好可以容下字符串大小，其过程类似，它是由sdsRemoveFreeSpace实现。

#### 内存安全性
因为sds不是以\0作为字符串的结束，而是以len来表示字符串的长度，所以它可以包含任何的二进制数据（包括\0）。

## 参考的资料
《Redis设计与实现》
[1]: https://redis.io/commands#string "string command"

TimeWheel一种实现方式

作者: nbboy
时间: 2022-02-23
分类: 默认分类,软件架构,Golang
评论

> 时间轮是一种应用于定时器的有效数据结构，只需要一个系统时钟定时器就搞定非常多的定时策略，常常应用于**延时任务**等场景

现在实现上主要有两种时间轮，Hash时间轮和分层时间轮，Hash时间轮又有可以实现为排序和非排序的，但是主要原理基本一致。

### Hash时间轮
hash时间轮可以用hash加上双向链表来实现，当然双向链表可以替换成其他类似的数据结构，比如数组，有序列表等等。其大致结构如下图所示：

每个系统时钟周期内都走动一个hash槽，在这个槽内task都是以双链表形式构建，并且每个task中有代表第几轮的circle和代表在第几个hash槽中的slot。如果circle是0，那就意味着当前可以调度，反之就该把circle减去1。具体看代码可能比较清楚。
```go
	for e := slot.Front(); e != nil; e = e.Next() {
		tasker := e.Value.(*task)
		if tasker.circle > 0 {
			tasker.circle -= 1
			continue
		} else {
			tw.removeTime(&removingTasker{key: tasker.key})
			go func() {
				defer func() {
					if err := recover(); err != nil {
						log.Printf("tasker error: %v\n", err)
					}
				}()

tasker.fn()
			}()
		}
	}
```
### 分层时间轮

分层时间轮是hash时间轮的一种优化，在原来论文里写得也比较清楚，假如说定时时间跨度很大，则采用hash时间轮就不是很理想。分层时间轮基于相当于十进制中的进位理念一样，或者类似现实中的时钟工作机制。结构如下图所示。
![](https://chenxf.org/usr/uploads/2022/02/1122728468.png)hierarchical-timing-wheel.pn
###### 设置定时时间

先计算出，给定的定时时间需要用几个轮子来表示，当前轮子不能表示就再加入一个。

###### 周期调度

每个系统时钟周期都是调度低位的轮子，走动一个时间槽，当走完当前轮的所有时间槽，则在比其高一级的轮子中走动一个时间槽。走动的时间槽里包含设定的定时时间，则把该时间移动到下一级轮子中，其位置很容易计算，和最开始设定定时时间的计算方式是一样的。当然，如果当前级别的轮子是最后一级，则需要去调度了。

### 总结

实现上，可以采用很多的实现方式，可以参考kafka,libevent,nginx等等源码都有实现，看具体需求做trade-off，我实现了简单的hash时间轮体验了一把，它存放在：https://github.com/x-debug/tw