LRUキャッシュとしてのRedis
RedisはList機能など、いろいろ高機能っぽいのでちょっとリッチなLRUキャッシュとして使ってみようと考え始めて見た
memoryがしきい値を超えたときの説明は
http://siguniang.wordpress.com/2012/03/19/redis%E3%81%AEmaxmemory-policy/
に詳しく書いてあるのでそちらを参照
ここで候補に挙がるのは以下の2つ
- volatile-lru
- allkeys-lru
ちょっとソース追っかけながら見てみる。
メモリの解放処理とかをやってるのはこの辺
http://doublefree.org:8080/source/xref/redis-2.4.13/src/redis.c#1541
1586 if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU || 1587 server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM) 1588 { 1589 dict = server.db[j].dict; 1590 } else { 1591 dict = server.db[j].expires; 1592 } 1593 if (dictSize(dict) == 0) continue;
expiresを追っかけてみると
http://doublefree.org:8080/source/xref/redis-2.4.13/src/redis.h#300
300 dict *expires; /* Timeout of keys with a timeout set */
http://doublefree.org:8080/source/xref/redis-2.4.13/src/db.c#448
448void setExpire(redisDb *db, robj *key, time_t when) { 449 dictEntry *de; 450 451 /* Reuse the sds from the main dict in the expire dict */ 452 de = dictFind(db->dict,key->ptr); 453 redisAssert(de != NULL); 454 dictReplace(db->expires,dictGetEntryKey(de),(void*)when); 455} 456
どうもexpire時間がセットされているkeyは通常のdictionary(dict)とは別のdictionary(expires)にもsetされるみたい。
ちなみに、replaceDictは
160static int dictReplace(dict *ht, void *key, void *val) { 161 dictEntry *entry, auxentry; 162 163 /* Try to add the element. If the key 164 * does not exists dictAdd will suceed. */ 165 if (dictAdd(ht, key, val) == DICT_OK) 166 return 1; 167 /* It already exists, get the entry */ 168 entry = dictFind(ht, key); 169 /* Free the old value and set the new one */ 170 /* Set the new value and free the old one. Note that it is important 171 * to do that in this order, as the value may just be exactly the same 172 * as the previous one. In this context, think to reference counting, 173 * you want to increment (set), and then decrement (free), and not the 174 * reverse. */ 175 auxentry = *entry; 176 dictSetHashVal(ht, entry, val); 177 dictFreeEntryVal(ht, &auxentry); 178 return 0; 179}
keyがあれば上書きして、なければaddするだけ。dictからexpiresにkeyを移している訳じゃない
expireに関するredisのdocumentを参照してみると
http://redis.io/commands/expire
ふむ。expireというコマンドを秒数指定で既存のkeyに打つのか。
実際にsetExpireが呼ばれているのも以下のコードから分かるようにexpireコマンドから
http://doublefree.org:8080/source/xref/redis-2.4.13/src/db.c#528
528void expireGenericCommand(redisClient *c, robj *key, robj *param, long offset) { 529 dictEntry *de; 530 long seconds; 531 532 if (getLongFromObjectOrReply(c, param, &seconds, NULL) != REDIS_OK) return; 533 534 seconds -= offset; 535 536 de = dictFind(c->db->dict,key->ptr); 537 if (de == NULL) { 538 addReply(c,shared.czero); 539 return; 540 } 541 /* EXPIRE with negative TTL, or EXPIREAT with a timestamp into the past 542 * should never be executed as a DEL when load the AOF or in the context 543 * of a slave instance. 544 * 545 * Instead we take the other branch of the IF statement setting an expire 546 * (possibly in the past) and wait for an explicit DEL from the master. */ 547 if (seconds <= 0 && !server.loading && !server.masterhost) { 548 robj *aux; 549 550 redisAssert(dbDelete(c->db,key)); 551 server.dirty++; 552 553 /* Replicate/AOF this as an explicit DEL. */ 554 aux = createStringObject("DEL",3); 555 rewriteClientCommandVector(c,2,aux,key); 556 decrRefCount(aux); 557 signalModifiedKey(c->db,key); 558 addReply(c, shared.cone); 559 return; 560 } else { 561 time_t when = time(NULL)+seconds; 562 setExpire(c->db,key,when); 563 addReply(c,shared.cone); 564 signalModifiedKey(c->db,key); 565 server.dirty++; 566 return; 567 } 568} 569 570void expireCommand(redisClient *c) { 571 expireGenericCommand(c,c->argv[1],c->argv[2],0); 572} 573 574void expireatCommand(redisClient *c) { 575 expireGenericCommand(c,c->argv[1],c->argv[2],time(NULL)); 576}
なんか、volatile-lruが求めているものに近いなぁと思ったけど、これだとallkeys-lruの方が近い気がする。
でも、allkeys-lruだと、
http://doublefree.org:8080/source/xref/redis-2.4.13/src/redis.c#1604
1604 else if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||
1605 server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)
1606 {
1607 for (k = 0; k < server.maxmemory_samples; k++) {
1608 sds thiskey;
1609 long thisval;
1610 robj *o;
1611
1612 de = dictGetRandomKey(dict);
1613 thiskey = dictGetEntryKey(de);
1614 /* When policy is volatile-lru we need an additonal lookup
1615 * to locate the real key, as dict is set to db->expires. */
1616 if (server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)
1617 de = dictFind(db->dict, thiskey);
1618 o = dictGetEntryVal(de);
1619 thisval = estimateObjectIdleTime(o);
1620
1621 /* Higher idle time is better candidate for deletion */
1622 if (bestkey == NULL || thisval > bestval) {
1623 bestkey = thiskey;
1624 bestval = thisval;
1625 }
1626 }
1627 }
1628
maxmemory_samplesの数(defaultで3)だけrandomに抽出してそのなかでLRUが一番古い(大きい)keyを消去対象として選出している
これだと運が良くないと、結構新しいkeyがどんどんevictされていっちゃうので、memcached的なLRUと結構違う。keyの管理方法の問題だけど、これだとなかなか悩ましい。maxmemory_samplesの値を調整するともうちょっとまともにならないか、試してみようと思う。
