redis基本

redis指南

安装配置

默认7.0

sudo apt install redis-server
sudo service redis-server start

dong@Acer_S3_Dong:~$ sudo service redis-server
Usage: /etc/init.d/redis-server {start|stop|restart|force-reload|status

redis-cli

Info server #服务器版本

redis-server

redis-server --port 6379
redis-server --port 6380

事务

正常事务

事务中出错：（为字符串value自增）

有序集合

与普通集合set类似，但每个元素关联一个score，并根据分值自动排序。

ZADD fruit-price 10 banana 20 apple
ZSCORE fruit-price apple
ZRANK fruit-price apple

命名规范

Redis 的命名规范清晰简洁，通过前缀快速定位功能模块，以下是部分常用前缀对应的模块：

字符串

redis字符串通过SDS对象表示，c字符串只只体现在字符串字面量。

两个应用场景。

1. 在redis数据库中，SDS对象用来保存字符串值。

比如，SET msg “helloworld” 在数据库创建一个键值对：

• 键是字符串对象，即SDS，SDS里面保存”msg”

• 值也是字符串对象，即SDS…

比如，RPUSH fruits “apple” “banana” “cherry” 向列表添加一些字符串。

• 键是字符串对象！ 内容是fruits
• 值是列表对象，每个元素是字符串对象

1. SDS用作缓冲区：比如AOF缓冲区，客户端状态的输入缓冲区。

SDS

struct sdshdr{
  int len;  
  int free;
  char buf[]; 
};

// 从c字符串创建sds
sdshdr* sdsnew(const char* s);
// 创建一个空sds
sdshdr* sdsempty();
// 释放sds
void sdsfree(sdshdr* sds);
// sds长度
int sdslen(const sdshdr* sds);
// sds空闲长度
int sdsavail(const sdshdr* sds);
// 返回一个sds副本,,copy
sdshdr* sdsdump(const sdshdr* sds);
// 情况sds字符串内容
void sdsclear(sdshdr* sds);
// 将C字符串拼接到SDS末尾
void sdscat(sdshdr* dest, const char* s);
// 将sds字符串拼接到sds末尾
void sdscatsds(sdshdr* dest, sdshdr* src);
// 将C字符串覆盖写入SDS
void sdscpy(sdshdr* dest, const char* s);
// 用空字符将SDS扩展到指定长度
void sdsgrowzero(sdshdr* sds);
// 保留SDS区间内数据，不在区间内的数据会覆盖或者清除？
void sdsrange(sdshdr* sds, int start, int end);
// 从SDS移除出现再C字符串中的字符
void sdstrim(sdshdr* sds, const char* s);
// 比较两个sds字符串相同
void sdscmp(const sdshdr* sds1, const sdshdr* sds2);

SDS与C字符串区别

C字符串使用N+1长度字符数组表示长度N字符串，最后字节是’\0’。

O(1)复杂度获取字符串长度

c字符串要想获取长度需要遍历字符串，O(N)。

redis字符串通过len属性直接获取。

至于，len属性的更新和设置是在调用SDS API时候自动完成。

比如，客户STRLEN 命令获取长度，为O(1)。

127.0.0.1:6379> STRLEN msg

(integer) 10

杜绝缓冲区溢出

因为C字符串不感知长度，例如strcat函数不安全，并不会检查源字符串，所以溢出。

而SDS字符串在修改时，会检查buf空间是否满足，如果不满足，自动扩展大小，再进行操作，不溢出。

比如，SDS中实现了sdscat。

字符串修改频繁带来的内存重分配策略

redis数据库会频繁修改数据修改字符串，不能够像C常规那样，每次修改都进行一次内存分配。

SDS通过free属性，实现空间预分配和惰性空间释放。

1. 空间预分配策略，用于字符串增长操作，操作之前，如果检查空间不够，则进行分配。

分配策略由下决定：

• 如果对SDS修改后，SDS的len值小于1MB，则分配len相同的free空间。比如，知道修改后len=13，那么free=13，buf=13+13+1
• 如果对SDS修改后，SDS的len值大于1MB，则分配1MB的free空间。比如，len=30MB，那么free=1MB，buf=30MB+1MB+1BYTE

1. 惰性空间（不）释放策略，用于字符串缩短操作，缩短SDS字符串时候，并不会直接回收一些字节，而是使用free属性记录下，以便将来使用。

比如，sdstrim(sds, “abc”）会从sds移除一些字符。

对于这些空间，也有API真正释放，而不会造成内存浪费。

字节安全

c字符串内部不能包含’\0’，否则会造成误读。c字符串通过’\0’判断字符串结束。

比如 redis’\0’cluster’\0’， redis通过len来判断字符串是否结束，不会造成歧义。

所以SDS的buf更多称为字节数组。

兼容C字符串

SDS可以兼容重用string.h一部分函数。

strcmp(sds->buf, "hello world");

链表

应用有：

• 当列表键值包含较多元素，或者元素都是较长字符串，redis就会使用链表作为列表键值的底层实现。
• 发布订阅、慢查询、监视器等用到了链表
• 服务器用链表保存多客户端信息，用链表构建客户端输出缓冲区等。

字典

字典应用：

• redis数据库底层就是字典实现的，比如增删改查。 SET msg “hello”
• 当哈希键包含键值对较多，或者键值对元素中是较长字符串，字典作为哈希键底层实现

实现

redis字典通过哈希表实现，每个哈希表节点保存一个字典键值对。

分别介绍redis哈希表、哈希表节点、字典。

哈希表：

typedef struct dictht {
  DictEntry** table; 
  unsigned long size; // table数组大小
  unsigned long sizemask; // 哈希表大小掩码，计算索引值，总是等于size-1
  unsigned long used; // 已用节点数
} DictHT;
 

哈希表节点：

每个哈希表节点保存一个键值对。

v属性表示的值可以是指针、u64、int64。

typedef struct dictEntry {
  void* key;
  union {
    void* val;
    uint64_t u64;
    int64_t s64;
  }v;
  DictEntry *next;
} DictEntry;

字典：

typedef struct dictType {
  unsigned int (*hashFunction)(const void* key);
  void* (*keyDup)(void* privdata, const void* key);
  void* (*valDup)(void* privdata, const void* obj);
  int (*keyCompare)(void* privdata, const void* key1, const void* key2);
  void (*keyDestructor)(void* privdata, void* key);
  void (*valDestructor)(void* privdata, void* val);
  
} DictType;
typedef struct dict {
  DictType* type;
  void* privdata;
 
  DictHT ht[2];
  int rehashidx; 
} Dict;

type和privdata属性是针对不同类型键值对，为创建多态字典创建

• type属性包含一簇函数指针， 操作键值对。 redis会为不同类型字典设置不同函数。
• privdata属性保存了需要传给那些多态函数的可选参数。

ht属性两个哈希表，一般只用ht[0]，另一个哈希表只在rehash时候使用。

rehashidx和ht[1]有关，记录了rehash目前进度，如果没有rehash，则为-1。

哈希算法

当要添加一个键值对到字典，先根据键计算哈希值和索引值，在放到指定索引。

计算哈希值和索引值：

hash = dict->type->hashFunction(key);
index = hash & dict->ht[x].sizemask;
 
redis字典作为数据库或者哈希键实现时候，使用Murmurhash2算法计算哈希值。

解决键冲突

dictEntry节点冲突时候，通过next解决，总是将新节点放在链表头部。

rehash

随着操作进行，需要让哈希负载因子维持合理，即需要对哈希表进行扩缩，通过rehash重新散列完成。

步骤如下：

1. 为ht[1]内存分配，空间大小取决于当前entry数量ht[0].used：
   • 如果扩展，大小为 ≥ ht[0].used*2的 最小二次幂。比如used为4，则为8
   • 如果缩小， 大小为 ≥ ht[0].used的最小二次幂。比如used为4，则为4，不变
2. 将所有ht[0]上的entry重散列到ht[1]，即重新计算hash和索引，并放到ht[1]
3. 完成rehash后，释放ht[0]，将ht[1]设置为ht[0]，为ht[1]重新创建一个ht，为下一次rehash准备

哈希表扩展的触发：

当任一条件被满足时，程序自动开始哈希表扩展：

• 服务器目前没有执行BGSAVE或者BGREWRITEAOF命令，且哈希表负载因子≥1
• 服务器正在执行BGSAVE或者BGREWRITEAOF命令，且负载因子≥5.

哈希负载因子 = ht[0].used / ht[0].size.

也就是说，负载因子维持合理即在不同命令下，要求不同。在BGSAVE或者BGREWRITEAOF命令时候，需要负载因子更大，即延迟禁止保护 哈希表的扩展。（比如100个used时候扩展，但现在500个used才能扩展）。这是因为，执行两个命令写RDB、AOF复制持久化文件时候，会fork子进程去做，会触发写时复制。比较写时复制时候进行扩展与否：

• 如果持久化时候进行扩展，主进程大量哈希表内存页修改，触发子进程复制原共享内存页，即为子进程创建大量内存，内存倍增！完成扩展后，子进程仍然面对的是原内存页，释放这些原内存页，子进程结束。父进程新哈希表。
• 如果持久化时候禁止扩展，共享内存页不变，子进程不创建新内存，子进程结束后。父进程在进行扩展等等。

哈希表收缩触发：

负载因子<0.5

渐进式rehash：

哈希表的扩缩不是一次性集中式完成的，而是分多次渐进式完成。如果有大量的rehash即计算、复制，导致服务器压力大。

渐进式通过dict.rehashidx记录，步骤如下：

1. Ht[1]分配内存，dict同时拥有两个哈希表，ht[0]作为旧哈希表不动，之后新数据插入
2. rehashidx设置为0，rehash工作开始
3. 在rehash期间，每次增删改查操作触发一个槽的rehash，这个槽索引为rehashidx，如果rehash完成，rehashidx+1。即从0-size，槽逐一rehash。
4. 最终，ht[0]成为空表，完成rehash，操作完成。

渐进式rehash期间的哈希表正常操作：增删改查

会在双表上进行，保持完整性。

插入：直接插入到ht[1]，ht[0]不进行插入操作。

删除：如果槽已经迁移，在ht[1]上删除操作。否则，ht[0]上操作。

查询：双表查询

跳跃表

定义：跳跃表是一个链表，每个节点包含不定数量的额外连接，节点第i个连接构成的单向链表跳过含有少于i个连接的节点。【算法：c语言实现第一部分-13.5】

跳跃表的每个节点维持多个其他节点指针，达到快速访问节点，平均O(logN)的查找。相较于链表，更能快速查找，这得益于一些额外的指针。在大部分情况下，跳跃表效率高于平衡树，很多情况，用跳跃表代替平衡树。

应用：

• 当有序集元素较多，或者成员是较长字符串，redis就会用跳跃表作为有序集合键的底层实现。
• 集群节点中用作内部数据结构。

实现

对象

redis并没有通过那些数据结构直接实现键值对数据库，而是通过这些数据结构创建一个对象系统，有五种类型对象：字符串对象、列表对象、哈希对象、集合对象和有序集合对象。每种对象都用到之前至少一种数据结构。

好处：

• 不同场景下可以给对象设置不同类型实现。
• 执行命令前，可以安全判断类型

此外，redis对象实现引用计数的内存回收机制，如果程序不再使用某个对象，就会自动释放内存；此外这还能对象共享机制？使得在适当条件，多数据库共享同一个对象来节约内存？

redis对象带有访问时间记录信息，这可以计算数据库键的空转时间，

对象类型和编码

redis使用对象表示数据库的键、值，每次创建一个键值对，至少创建两个对象，键对象和值对象。

typedef struct redisObject {
  unsigned type:4;    // 对象类型，例如字符串（REDIS_STRING）、列表（REDIS_LIST）
  unsigned encoding:4;  // 对象的编码方式，例如 RAW、INT 等
  unsigned lru:24;    // LRU 时间，用于记录对象的最近访问时间
  int refcount;      // 引用计数
  void* ptr;       // 指向对象具体数据的指针（底层数据结构）
} robj;

type 类型

共有五种对象类型。
数据库中键总是STRING对象，值可以是其中一类。所以，称“字符串键”指它的值是字符串对象，称“列表键”指它的值是列表对象。
enum robj_type{
  REDIS_STRING,
  REDIS_LIST, 
  REDIS_HASH, // 哈希
  REDIS_SET, // 集合
  REDIS_ZSET, // 有序集合
};

TYPE命令作用于键，返回值对象类型。

encoding 和 ptr 底层实现

encoding标识采用的数据结构，ptr指向具体数据。

enum robj_encoding{
  REDIS_ENCODING_INT, // long类型整数
  REDIS_ENCODING_EMBSTR, // embstr编码的sds
  REDIS_ENCODING_RAW, // sds
  REDIS_ENCODING_HT, // 字典
  REDIS_ENCODING_LINKEDLIST, // 双端链表
  REDIS_ENCODING_ZIPLIST, // 压缩列表
  REDIS_ENCODING_INTSET, // 整数集合
  REDIS_ENCODING_SKIPLIST // 跳跃表和字典
};
通过OBJECT ENCODING查看对象编码：

这极大提高了redis灵活性，可以为不同场景设置不同编码即不同底层实现。

比如，列表元素较少时候，使用压缩列表实现，压缩列表更少内存，且内存连续，更容易载入；列表元素较多时候，通过双端链表实现。

字符串对象

字符串对象encoding可以是：int、raw、embstr。

1. int：如果对象保存的是整数值，且能用long表示，void* ptr视为long ptr

1. raw：如果对象保存的是字符串值，且长度大于32字节，void* ptr视为sds* ptr

1. embstr：如果对象保存的是字符串值，且长度≤32字节。void* ptr视为sds* ptr。 但与raw编码不同的是，embstr只会调用一次内存连续存储robj和sds。

   • 这使得释放只要一次，
   • 由于连续内存，更容易缓存读取。

   

   

   注意的是，对于浮点类型，也是作为字符串对象存储的，编码就是raw或者embstr

字符串命令实现方法

列表对象

类型检查与命令多态

redis用于操作键的命令有两类：

1. 对任何类型键执行：DEL、EXPIRE、RENAME、TYPE、OBJECT
2. 对特定类型键执行：
   • 字符串键：SET、GET、APPEND、STRLEN
   • 哈希键：
   • 列表键：LLEN
   • 集合键
   • 有序集合键

因此，对于特定类型键命令，需要进行类型检查，如果不匹配，返回类型错误。

内存回收

通过robj.refcount引用计数自动回收。

refcount计数规则：

• 创建对象。值为1
• 需要对象时候，++。 比如添加到列表
• 不再被，值–。 比如从列表删除
• 计数值为0，回收。

涉及api：

对象共享

场景：键A和键B都创建保存了整数100的字符串键。

两种方法：1. 创建两个对象，两片内存。 2. 两个键指向同一个内存对象。

显然第二种更好，需要做的只是让值指向同一对象，对象引用计数+1.

因此，redis初始化会创建10000个字符串对象， 服务器最初共享对象。

可以通过OBJECT REFCOUNT查看。

2147483647（2^31 - 1）。

Redis 会对一些常见的小整数（例如 0、1、2、…、10000）创建共享对象。这些共享对象会在 Redis 启动时初始化，并在整个运行过程中被重用。为了避免共享对象被错误地释放，Redis 将这些对象的引用计数设置为一个很大的值（2147483647），表示它们永远不会被释放。

判断共享，需要验证类型、保存值等，为了复杂度，redis指对包含整数值的字符串对象进行了共享

对象空转

Robj.lru属性记录最后一次访问时间。

1. OBJECT IDLETIME命令计算空转时间

1. lru算法回收内存，如果排在maxmemory和lru算法，超过最大上限内存时候，空转时间较长的键优先释放，回收内存。