数据结构
源码如下:
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)
对象类型源码定义如下:
/* 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. */ /* The "module" object type is a special one that signals that the object * is one directly managed by a Redis module. In this case the value points * to a moduleValue struct, which contains the object value (which is only * handled by the module itself) and the RedisModuleType struct which lists * function pointers in order to serialize, deserialize, AOF-rewrite and * free the object. * * Inside the RDB file, module types are encoded as OBJ_MODULE followed * by a 64 bit module type ID, which has a 54 bits module-specific signature * in order to dispatch the loading to the right module, plus a 10 bits * encoding version. */ #define OBJ_MODULE 5 /* Module object. */ #define OBJ_STREAM 6 /* Stream object. */
对应 type 命令,主要是用来存储 redis 对象的类型
举个例子,查询 key 对应的 redis 数据类型:
对象编码(encoding)
对象的 ptr 指针指向对象的底层数据结构,这些数据结构由对象的 encoding 属性决定。
encoding 属性就了对象使用的编码,也就是说这个对象使用了什么数据结构作为对象的实现,这个属性值如下表所列出的常量中的其中一个:
/* Objects encoding. Some kind of objects like Strings and Hashes can be * internally represented in multiple ways. The 'encoding' field of the object * is set to one of this fields for this object. */ // 简单动态字符串 #define OBJ_ENCODING_RAW 0 /* Raw representation */ // long 类型的整数 #define OBJ_ENCODING_INT 1 /* Encoded as integer */ // 字典 #define OBJ_ENCODING_HT 2 /* Encoded as hash table */ // 压缩map #define OBJ_ENCODING_ZIPMAP 3 /* Encoded as zipmap */ // 双端链表 #define OBJ_ENCODING_LINKEDLIST 4 /* No longer used: old list encoding. */ // 压缩链表 #define OBJ_ENCODING_ZIPLIST 5 /* Encoded as ziplist */ // 整数集合 #define OBJ_ENCODING_INTSET 6 /* Encoded as intset */ // 跳跃表 #define OBJ_ENCODING_SKIPLIST 7 /* Encoded as skiplist */ #define OBJ_ENCODING_EMBSTR 8 /* Embedded sds string encoding */ // 快表 #define OBJ_ENCODING_QUICKLIST 9 /* Encoded as linked list of listpacks */ #define OBJ_ENCODING_STREAM 10 /* Encoded as a radix tree of listpacks */ #define OBJ_ENCODING_LISTPACK 11 /* Encoded as a listpack */
每种类型的对象至少使用了两种不同的编码,会在创建对象的时候进行选择
Object encoding 对不通过编码输出如下代码所示
char *strEncoding(int encoding) { switch(encoding) { case OBJ_ENCODING_RAW: return "raw"; case OBJ_ENCODING_INT: return "int"; case OBJ_ENCODING_HT: return "hashtable"; case OBJ_ENCODING_QUICKLIST: return "quicklist"; case OBJ_ENCODING_ZIPLIST: return "ziplist"; case OBJ_ENCODING_LISTPACK: return "listpack"; case OBJ_ENCODING_INTSET: return "intset"; case OBJ_ENCODING_SKIPLIST: return "skiplist"; case OBJ_ENCODING_EMBSTR: return "embstr"; case OBJ_ENCODING_STREAM: return "stream"; default: return "unknown"; } }
LRU 和 LFU
Lru: 记录的都是对象最后一次被命令访问的时间,当使用 objectidletime 命令,通过对比 lru 时间与当前时间,可以计算某个对象的空转时间,不会改变对象的 lru 值,另外还与 Redis 的 内存回收 有关,如果 redis 打开了 maxmemory 选项,并且内存回收算法选择的是 volatile-lru 或者 allkey-lru。 那么当 Redis 占用内存超过 maxmemory 制定的值时, Redis 会优先选择空转时间最长的对象进行释放。
robj *createObject(int type, void *ptr) { robj *o = zmalloc(sizeof(*o)); o->type = type; o->encoding = OBJ_ENCODING_RAW; o->ptr = ptr; o->refcount = 1; /* Set the LRU to the current lruclock (minutes resolution), or * alternatively the LFU counter. */ // 区分 LRU 和 LFU if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) { o->lru = (LFUGetTimeInMinutes()<<8) | LFU_INIT_VAL; } else { o->lru = LRU_CLOCK(); } return o; }
lfu : 使用 objectfreq 命令, 可以查看对戏那个的使用次数,针对计数器, redis 采用了基于概率的对数计数器,使用。8 位足够记录很高的方位频率。
此时时间计算和 LRU 不在相同 -- 取的是分钟时间戳对 2^16 进行取模
/* Return the current time in minutes, just taking the least significant * 16 bits. The returned time is suitable to be stored as LDT (last decrement * time) for the LFU implementation. */ unsigned long LFUGetTimeInMinutes(void) { return (server.unixtime/60) & 65535; } /* Given an object last access time, compute the minimum number of minutes * that elapsed since the last access. Handle overflow (ldt greater than * the current 16 bits minutes time) considering the time as wrapping * exactly once. */ unsigned long LFUTimeElapsed(unsigned long ldt) { unsigned long now = LFUGetTimeInMinutes(); if (now >= ldt) return now-ldt; return 65535-ldt+now; }
refcount
对应 object refcount 命令,redis 共享的对象都放在结构体 sharedObjectsStruct. 中 具体见 createShareObjects 函数,如常见的字符串、以及 10000 个字符串对象,分别是 [0-9999] 的整数值,点那个 redis 需要使用职位 0 - 9999 的字符对象时,可以直接使用这些共享对象。 10000 这个字符数字可以通过调整参数 REDIS_SHARED_INTEGERS 的值进行改变。
但是共享对象池与 maxmemory + lru 策略冲突,因为共享对象,lru 也是共享的,只有整数对象池,因为整数对象池复用几率大,而且字符串判断相等性,时间复杂度变为 O(n), 特别是长字符串更加消耗性能(浮点数在 Redis 内部使用字符串存储)。
补充说明
位域
在 redisObject 数据结构中,采用了 C 中的位域来节省内存,位域操作非常方便。
需要注意的就是它的移植性,比如某些嵌入式中 1 个字节不是8位,还有比如你的类型
跨2个字节了,这样的话,可能会导致不是预期的结果,因此适当填充 0 是必要的。
时间计算
获取时间的函数属于系统调用,比较耗费资源,因此 redis 采用缓存的方式,在定期更新见 serverCorn 函数。
int serverCron(struct aeEventLoop *eventLoop, long long id, void *clientData) { // ... /* Update the time cache. */ updateCachedTime(1); // ... }
redisServer 对象中的 ustime, estime
redis 对象中的 lrulock
需要注意的是在 lrulock 中使用了 atomicGet 是因为可能在别的线程中也会用到该时间,比如集群状态。