首页  

Redis内部存储结构     所属分类 redis 浏览量 141

8 大类型使用的内部存储结构 string sds list quicklist set dict zset 元素及value小于阈值 ziplist , 否则 zskiplist hash 元素及value小于阈值 ziplist ,否则 hash bitmap sds hyperloglog sds geo 元素及value小于阈值 ziplist , 否则 zskiplist
redisDb 数据库实例 , 每个 Redis 16 个 redisDb typedef struct redisDb { dict *dict; /* The keyspace for this DB */ dict *expires; /* Timeout of keys with a timeout set */ dict *blocking_keys; /* Keys with clients waiting for data (BLPOP)*/ dict *ready_keys; /* Blocked keys that received a PUSH */ dict *watched_keys; /* WATCHED keys for MULTI/EXEC CAS */ int id; /* Database ID */ long long avg_ttl; /* Average TTL, just for stats */ list *defrag_later; /* List of key names to attempt to defrag one by one, gradually. */ } redisDb; Dict typedef struct dict { dictType *type; void *privdata; dictht ht[2]; long rehashidx; /* rehashing not in progress if rehashidx == -1 */ unsigned long iterators; /* number of iterators currently running */ } dict; type 保存 hash 函数及 key/value 赋值、比较函数 ht[2] 存储数据的数组 ,默认使用 0 号数组,如果 0 号哈希表元素过多,则分配一个 2 倍 0 号哈希表大小的空间给 1 号哈希表,然后进行逐步迁移 rehashidx 迁移位置标志
Dictht & DictEntry typedef struct dictht { # 哈希表数组 dictEntry **table; # 哈希表大小 unsigned long size; #哈希表大小掩码 unsigned long sizemask; # 该哈希表已有节点的数量 unsigned long used; } dictht; typedef struct dictEntry { void *key; union { void *val; uint64_t u64; int64_t s64; double d; } v; struct dictEntry *next; } dictEntry; dictEntry key sds 字符串 value 存储各种数据类型的 redisObject
redisObject 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 数据类型 7 种类型 OBJ_STRING OBJ_LIST OBJ_SET OBJ_ZSET 有序集合 OBJ_HASH OBJ_MODULE 模块 OBJ_STREAM 消息队列/流 encoding 内部编码方式 10 种编码方式 OBJ_ENCODING_RAW OBJ_ENCODING_INT OBJ_ENCODING_HT OBJ_ENCODING_ZIPLIST OBJ_ENCODING_ZIPMAP OBJ_ENCODING_SKIPLIST OBJ_ENCODING_EMBSTR OBJ_ENCODING_QUICKLIST OBJ_ENCODING_STREAM OBJ_ENCODING_INTSET LRU LRU 时间 或 LFU 频率 或时间 refcount 引用计数 , 计数为 0 表明该对象没有被使用,会被释放,回收内存 ptr 指向存储数据的指针
sds simple dynamic string sdshdr5 sdshdr8 sdshdr16 sdshdr32 sdshdr64 根据实际长度,选择不同的数据结构 struct __attribute__ ((__packed__)) sdshdr5 { unsigned char flags; /* 3 lsb of type, and 5 msb of string length */ char buf[]; }; 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[]; }; 除了 sdshdr5 之外,其他的几个数据结构都包含 4 个字段: len 字符串长度 alloc 给字符串分配的内存大小 flags 当前字节数组的属性 buf 字符串值和结束符 \0 sds 三种编码方式 INT RAW EMBSTR INT ptr 直接指向具体的数据 #define OBJ_ENCODING_EMBSTR_SIZE_LIMIT 44 robj *createStringObject(const char *ptr, size_t len) { if (len <= OBJ_ENCODING_EMBSTR_SIZE_LIMIT) return createEmbeddedStringObject(ptr,len); else return createRawStringObject(ptr,len); } 字符串长度小于等于 44 , 使用 embstr 否则 RAW object encoding xxx embstr raw embstr 专门用于保存短字符串 raw编码 调用两次内存分配函数分别创建 redisObject 和 sdshdr embstr编码 调用一次内存分配函数分配一块连续的空间,空间中依次包含redisObject和sdshdr sds 主要作为字符串的内部数据结构,同时也是 hyperloglog、bitmap 类型的内部数据结构
ziplist(压缩列表) 节约内存,减少内存碎片 连续的内存空间 ziplist 包含 5 个部分 zlbytes ziplist占用的总内存 Zltail 尾节点到起始位置的字节数 Zllen 总共包含的节点/内存块数 Entry 各个数据节点 Zlend 魔数 255,用来标记压缩列表的结束 存储节点 zlentry typedef struct zlentry { unsigned int prevrawlensize; /* Bytes used to encode the previous entry len*/ unsigned int prevrawlen; /* Previous entry len. */ unsigned int lensize; /* Bytes used to encode this entry type/len. For example strings have a 1, 2 or 5 bytes header. Integers always use a single byte.*/ unsigned int len; /* Bytes used to represent the actual entry. For strings this is just the string length while for integers it is 1, 2, 3, 4, 8 or 0 (for 4 bit immediate) depending on the number range. */ unsigned int headersize; /* prevrawlensize + lensize. */ unsigned char encoding; /* Set to ZIP_STR_* or ZIP_INT_* depending on the entry encoding. However for 4 bits immediate integers this can assume a range of values and must be range-checked. */ unsigned char *p; /* Pointer to the very start of the entry, that is, this points to prev-entry-len field. */ } zlentry; prevRawLen 前置节点长度 preRawLenSize len 当前节点的长度 lensize encoding 当前节点编码类型 entryData 当前节点数据 ziplist 连续紧凑存储,没有冗余空间,插入新的元素需要 realloc 扩展内存, 如果占用空间太大,realloc 重新分配内存和拷贝的开销会很大, 所以 ziplist 不适合存储过多元素,也不适合存储过大的字符串 ziplist 是 hash、sorted set 的内部存储结构之一, hash 元素不超过 512 个 ,且值不超过 64个字节,使用 ziplist 作为内存存储结构, 由参数 hash-max-ziplist-entries hash-max-ziplist-value 控制 sorted set ,当元素个数不超过 128个并且值不超过 64 字节,使用 ziplist 来存储, zset-max-ziplist-entries zset-max-ziplist-value
quicklist(快速列表) quicklist 3.2 之后引入,用来替换 linkedlist linkedlist 每个节点有前后指针,要占用 16 字节,且每个节点独立分配内存,容易导致内存碎片化 typedef struct quicklist { quicklistNode *head; quicklistNode *tail; unsigned long count; /* total count of all entries in all ziplists */ unsigned long len; /* number of quicklistNodes */ int fill : 16; /* fill factor for individual nodes */ unsigned int compress : 16; /* depth of end nodes not to compress;0=off */ } quicklist; typedef struct quicklistNode { struct quicklistNode *prev; struct quicklistNode *next; unsigned char *zl; unsigned int sz; /* ziplist size in bytes */ unsigned int count : 16; /* count of items in ziplist */ unsigned int encoding : 2; /* RAW==1 or LZF==2 */ unsigned int container : 2; /* NONE==1 or ZIPLIST==2 */ unsigned int recompress : 1; /* was this node previous compressed? */ unsigned int attempted_compress : 1; /* node can't compress; too small */ unsigned int extra : 10; /* more bits to steal for future usage */ } quicklistNode; quicklist 基于 ziplist 的双向链表,数据分段存储到 ziplist,然后将这些 ziplist 用双向指针连接 quicklist 结构体说明 head tail 分别指向第一个和最后一个 ziplist 节点 count 总的元素个数 len ziplist 节点个数 compress LZF算法的压缩深度 quicklistNode prev/next 双向指针 ziplist 节点 ,单个 ziplist 节点可以存放多个元素 quicklist 是 list 列表的内部数据结构 头尾读写数据很快,时间复杂度 O(1) 支持从中间任意位置插入或读写元素,但速度较慢,时间复杂度 O(n)
zskiplist(跳跃表) 跳跃表是一种有序数据结构 通过在每个节点维持多个指向其他节点的指针,加速访问 大部分场景,跳跃表的效率和平衡树接近,跳跃表支持平均 O(logN) 和最差 O(n) 复杂度的节点查找, 并且跳跃表的实现比平衡树要简单 使用跳跃表两种场景 sorted set ,如果元素数较多或元素长度较大,使用跳跃表作为内部数据结构。 默认元素数超过 128 或者最大元素的长度超过 64,采用 zskiplist 存储 集群结点中用作内部数据结构 zskiplistNode zskiplist typedef struct zskiplistNode { sds ele; double score; struct zskiplistNode *backward; struct zskiplistLevel { struct zskiplistNode *forward; unsigned long span; } level[]; } zskiplistNode; typedef struct zskiplist { struct zskiplistNode *header, *tail; unsigned long length; int level; } zskiplist; typedef struct zset { dict *dict; zskiplist *zsl; } zset; 跳跃表 zskiplist 结构 header 头节点 tail 尾节点 length 长度,不包含表头节点的节点数量 level 除表头节点外的所有节点中,层数最大的那个节点的层数 zskiplistNode ele 节点元素 score 节点分数 backward 指向当前节点的前一个节点的指针 level forwad 前进指针 span 跨度, forward 指向的节点到当前节点的距离

上一篇     下一篇
jmx_prometheus_javaagent 使用

jmx_exporter JmxCollector 源码要点

jedis 获取 redis info 信息

kafka-topics.sh 无法获取topic列表及topic信息

kafka之broker-list bootstrap-server 和 zookeeper

Kafka 和 RocketMQ 底层存储简单比较