/* quicklist is a 40 byte struct (on 64-bit systems) describing a quicklist. * 'count' is the number of total entries. * 'len' is the number of quicklist nodes. * 'compress' is: -1 if compression disabled, otherwise it's the number * of quicklistNodes to leave uncompressed at ends of quicklist. * 'fill' is the user-requested (or default) fill factor. */ typedefstructquicklist { quicklistNode *head; quicklistNode *tail; unsignedlong count; /* total count of all entries in all ziplists */ unsignedlong len; /* number of quicklistNodes */ intfill : 16; /* fill factor for individual nodes */ unsignedint compress : 16; /* depth of end nodes not to compress;0=off */ } quicklist;
/* 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. * attempted_compress: 1 bit, boolean, used for verifying during testing. * extra: 12 bits, free for future use; pads out the remainder of 32 bits */ typedefstructquicklistNode { structquicklistNode *prev; structquicklistNode *next; unsignedchar *zl; unsignedint sz; /* ziplist size in bytes */ unsignedint count : 16; /* count of items in ziplist */ unsignedint encoding : 2; /* RAW==1 or LZF==2 */ unsignedint container : 2; /* NONE==1 or ZIPLIST==2 */ unsignedint recompress : 1; /* was this node previous compressed? */ unsignedint attempted_compress : 1; /* node can't compress; too small */ unsignedint extra : 10; /* more bits to steal for future usage */ } quicklistNode;
#0 activeExpireCycle (type=1) at expire.c:97 #1 0x0002fa6c in beforeSleep (eventLoop=<optimized out>) at server.c:1190 #2 0x0002d01c in aeMain (eventLoop=0x40812150) at ae.c:463 #3 0x0002a018 in main (argc=<optimized out>, argv=<optimized out>) at server.c:3844
#0 activeExpireCycle (type=0) at expire.c:97 #1 0x00030c70 in databasesCron () at server.c:878 #2 0x00033204 in serverCron (eventLoop=<optimized out>, id=<optimized out>, clientData=0x0) at server.c:1032 #3 0x0002cdc4 in processTimeEvents (eventLoop=0x40812150) at ae.c:323 #4 aeProcessEvents (eventLoop=0x40812150, flags=11) at ae.c:432 #5 0x0002d028 in aeMain (eventLoop=0x40812150) at ae.c:464 #6 0x0002a018 in main (argc=<optimized out>, argv=<optimized out>) at server.c:3844
typedefstructredisDb { 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 */ longlong avg_ttl; /* Average TTL, just for stats */ } redisDb;
其中expires存储了带有过期时间key的hash表,dict是存储了所有的key的hash表 先简单谈下LRU和LFU,两个常用的缓存evication算法,分别是Least Recent Usage 和 Least Frequency Usage,当redis中数据超过设置的最大内存,且使用内存超过最大内存,但是又没有能过期的数据的时候,server需要删除一批数据来保证能够继续运行,具体的步骤是 在server.c每次处理命令的时候,会调用 evic.c 里面的 freeMemoryIfNeeded 函数,这个里面会调用 evictionPoolPopulate 函数来释放内存(当内存使用超过 maxmemory 的时候),这个过程也是随机选一些key然后来选出上次更新时间最早的,或者访问次数最少的,来释放内存,知道内存恢复到小于最大内存 注意这个过程有个时间控制,当key的上次访问时间超过 lfu_decay_time 的时候,它的LFU次数是要清零的,也就是那种之前访问了很多次,但是最近没咋访问的,这也很好的在lru字段中展现了出来
1 2 3 4 5 6 7 8 9
typedefstructredisObject { 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;
* We have 24 total bits of space in each object in order to implement * an LFU (Least Frequently Used) eviction policy, since we re-use the * LRU field for this purpose. * * We split the 24 bits into two fields: * * 16 bits 8 bits * +----------------+--------+ * + Last decr time | LOG_C | * +----------------+--------+ * * LOG_C is a logarithmic counter that provides an indication of the access * frequency. However this field must also be decremented otherwise what used * to be a frequently accessed key in the past, will remain ranked like that * forever, while we want the algorithm to adapt to access pattern changes.
noeviction: return errors when the memory limit was reached and the client is trying to execute commands that could result in more memory to be used (most write commands, but DEL and a few more exceptions).
allkeys-lru: evict keys by trying to remove the less recently used (LRU) keys first, in order to make space for the new data added.
volatile-lru: evict keys by trying to remove the less recently used (LRU) keys first, but only among keys that have an expire set, in order to make space for the new data added.
allkeys-random: evict keys randomly in order to make space for the new data added. volatile-random: evict keys randomly in order to make space for the new data added, but only evict keys with an expire set.
volatile-ttl: evict keys with an expire set, and try to evict keys with a shorter time to live (TTL) first, in order to make space for the new data added.
做lru数据过期的堆栈代码如下:
1 2 3 4 5 6
#0 freeMemoryIfNeeded () at evict.c:377 #1 0x0002da18 in processCommand (c=0x16d1d4) at server.c:2368 #2 0x0003d344 in processInputBuffer (c=0x16d1d4) at networking.c:1330 #3 0x00027bd4 in aeProcessEvents (eventLoop=0x134f54, flags=11) at ae.c:421 #4 0x00027f8c in aeMain (eventLoop=0x134f54) at ae.c:464 #5 0x000250c4 in main (argc=<optimized out>, argv=<optimized out>) at server.c:3844
if (ZIP_IS_STR(encoding)) { /* Although encoding is given it may not be set for strings, * so we determine it here using the raw length. */ if (rawlen <= 0x3f) { if (!p) return len; buf[0] = ZIP_STR_06B | rawlen; } elseif (rawlen <= 0x3fff) { len += 1; if (!p) return len; buf[0] = ZIP_STR_14B | ((rawlen >> 8) & 0x3f); buf[1] = rawlen & 0xff; } else { len += 4; if (!p) return len; buf[0] = ZIP_STR_32B; buf[1] = (rawlen >> 24) & 0xff; buf[2] = (rawlen >> 16) & 0xff; buf[3] = (rawlen >> 8) & 0xff; buf[4] = rawlen & 0xff; } }
@Override public List<T> next(){ if (!hasNext()) { thrownew NoSuchElementException(); } Object[] array = new Object[size]; int count = 0; for (; count < size && iterator.hasNext(); count++) { array[count] = iterator.next(); } for (int i = count; i < size; i++) { array[i] = null; // for GWT }
@SuppressWarnings("unchecked") // we only put Ts in it List<T> list = Collections.unmodifiableList((List<T>) Arrays.asList(array)); return (pad || count == size) ? list : list.subList(0, count); } }; }