Redis

String 介绍 最基本的数据类型，一个 key 对应一个 value 底层结构 SDS 应用场景 缓存 计数器 常用命令 命令 描述 SET key value 设置 key 对应的值为 value GET key 获取 key 对应的值 DEL key 删除 key 对应的值 INCR key key 对应的值加 1 DECR key key 对应的值减 1 INCRBY key increment key 对应的值加 increment DECRBY key decrement key 对应的值减 decrement List 介绍 双端链表，支持从两端插入和删除 底层结构 QuickList 应用场景 消息队列 常用命令 命令 描述 LPUSH key value1 [value2 … valueN] 从左边插入一个或多个值 RPUSH key value1 [value2 … valueN] 从右边插入一个或多个值 LPOP key 从左边删除一个值 RPOP key 从右边删除一个值 LINDEX key index 获取指定索引的值 LRANGE key start stop 获取指定范围的值 Hash 介绍 哈希表，类似于 Java 中的 HashMap...

结构 /* ZSETs use a specialized version of Skiplists */ typedef struct zskiplistNode { sds ele; double score; struct zskiplistNode *backward; struct zskiplistLevel { struct zskiplistNode *forward; unsigned int span; } level[]; } zskiplistNode; typedef struct zskiplist { struct zskiplistNode *header, *tail; unsigned long length; int level; } zskiplist; ele: 持有数据，是一个 sds 结构 score: 分值 backward: 指向前一个节点 level: 层级，包含 forward 和 span 两个字段 forward: 指向下一个节点 span: 记录跨度，即当前节点到下一个节点的距离 优势 插入、删除、查找的时间复杂度都是 O(logN) 有序，可以使用跳表进行范围查询

结构 typedef struct dict { dictEntry **table; unsigned long size; unsigned long sizemask; unsigned long used; } dict; typedef struct dictEntry { void *key; union { void *val; uint64_t u64; int64_t s64; } v; struct dictEntry *next; } dictEntry; key: 键 val: 值，值可以是一个指针，也可以是 uint64_t 或 int64_t 类型的整数 next: 指向下一个节点，形成链表 哈希算法 // 使用字典设置的哈希函数，计算键 key 的哈希值 hash = dict->type->hashFunction(key); // 使用哈希表的 sizemask 属性和第一步得到的哈希值，计算索引值 index = hash & dict->ht[x].sizemask; 关注点 解决哈希冲突：拉链表，使用 *next 指向下一个具有相同索引值的哈希表节点 扩容和缩容：根据原哈希表已使用的空间扩大一倍或缩小一半 扩容条件： 没有执行 BGSAVE 或 BGREWRITEAOF 命令，且负载因子大于 1 在执行 BGSAVE 或 BGREWRITEAOF 命令，负载因子大于 5 渐进式 rehash：在 rehash 的过程中，新哈希表和旧哈希表同时存在，查询时先查询新哈希表，再查询旧哈希表，写入时只写入新哈希表

结构 双向链表，每一个节点都是一个 ziplist /* Node, quicklist, and Iterator are the only data structures used currently. */ /* quicklistNode is a 32 byte struct describing a ziplist for a quicklist. * We use bit fields keep the quicklistNode at 32 bytes. * count: 16 bits, max 65536 (max zl bytes is 65k, so max count actually < 32k). * encoding: 2 bits, RAW=1, LZF=2. * container: 2 bits, NONE=1, ZIPLIST=2. * recompress: 1 bit, bool, true if node is temporarry decompressed for usage....

介绍 SDS 全称为 Simple Dynamic String，用于存储二进制数据的一种结构，具有动态扩容、空间预分配、二进制安全等特性。Redis 中的字符串对象就是使用 SDS 结构实现的。 总体结构 struct __attribute__ ((__packed__)) sdshdr8 { uint8_t len; /* used */ uint8_t alloc; /* excluding the header and null terminator */ unsigned char flags; /* 3 lsb of type, 5 unused bits */ char buf[]; }; struct __attribute__ ((__packed__)) sdshdr16 { uint16_t len; /* used */ uint16_t alloc; /* excluding the header and null terminator */ unsigned char flags; /* 3 lsb of type, 5 unused bits */ char buf[]; }; struct __attribute__ ((__packed__)) sdshdr32 { uint32_t len; /* used */ uint32_t alloc; /* excluding the header and null terminator */ unsigned char flags; /* 3 lsb of type, 5 unused bits */ char buf[]; }; struct __attribute__ ((__packed__)) sdshdr64 { uint64_t len; /* used */ uint64_t alloc; /* excluding the header and null terminator */ unsigned char flags; /* 3 lsb of type, 5 unused bits */ char buf[]; }; len：记录 buf 中已使用的字节数 alloc：记录 buf 中已分配的字节数 flags：记录 buf 的类型，低 3 位表示类型，高 5 位未使用 buf：存储字符串的字节数组 优势 常数复杂度获取字符串长度：读取 len 字段即可，不需要遍历整个字符串 不存在缓冲区溢出问题：根据 len 和 alloc 字段，判断是否需要扩容 空间预分配，减少内存重分配次数：每次扩容都会多分配一些内存，减少内存重分配次数 二进制安全，可以存储任意二进制数据：以 len 字段的长度来判断字符串的结束，而不是以空字符 \0 来判断 兼容部分 C 字符串函数：遵从每个字符串的最后一个字节是空字符 \0 的惯例，可以使用部分 C 字符串函数 空间预分配 当执行字符串拼接操作时，如果字符串的长度超过了已分配的内存，Redis 会对字符串进行扩容。扩容的规则如下：...