文 | zxszcaijin

本文轉(zhuǎn)載自:blog.chinaunix.net

在使用redis作為緩存的場(chǎng)景下,內(nèi)存淘汰策略決定的redis的內(nèi)存使用效率.在大部門場(chǎng)景下,我們會(huì)采用LRU(Least Recently Used)來(lái)作為redis的淘汰策略.本文將由淺入深的介紹redis lru策略的具體實(shí)現(xiàn).

首先我們來(lái)科普下,什么是LRU ?(以下來(lái)自維基百科)

Discards the least recently used items first. This algorithm requires keeping track of what was used when, which is expensive if one wants to make sure the algorithm always discards the least recently used item. General implementations of this technique require keeping "age bits" for cache-lines and track the "Least Recently Used" cache-line based on age-bits. In such an implementation, every time a cache-line is used, the age of all other cache-lines changes.

簡(jiǎn)而言之,就是每次淘汰最近最少使用的元素 .一般的實(shí)現(xiàn),都是采用對(duì)存儲(chǔ)在內(nèi)存的元素采用 'age bits’ 來(lái)標(biāo)記該元素從上次拜訪到現(xiàn)在為止的時(shí)長(zhǎng),從而在每次用LRU淘汰時(shí),淘汰這些最長(zhǎng)時(shí)間未被拜訪的元素.

這里我們先實(shí)現(xiàn)一個(gè)簡(jiǎn)單的LRU Cache,以便于后續(xù)內(nèi)容的理解 .(來(lái)自leetcot,不外這里我重新用Python語(yǔ)言實(shí)現(xiàn)了)實(shí)現(xiàn)該緩存滿足如下兩點(diǎn):

1.get(key) - 如果該元素(總是正數(shù))存在,將該元素移動(dòng)到lru頭部,并返回該元素的值,不然返回-1.

2.set(key,value) - 設(shè)置一個(gè)key的值為value(如果該元素存在),并將該元素移動(dòng)到LRU頭部.不然插入一個(gè)key,且值為value.如果在設(shè)置前檢查到,該key插入后,會(huì)超過cache的容量,則根據(jù)LRU策略,刪除最近最少使用的key.

闡發(fā)

這里我們采用雙向鏈表來(lái)實(shí)現(xiàn)元素(k-v鍵值對(duì))的存儲(chǔ),同時(shí)采用hash表來(lái)存儲(chǔ)相關(guān)的key與item的對(duì)應(yīng)關(guān)系.這樣,我們既能在O(1)的時(shí)間對(duì)key進(jìn)行操作,同時(shí)又能利用Double LinkedList的添加和刪除節(jié)點(diǎn)的方便性.(get/set都能在O(1)內(nèi)完成).

具體實(shí)現(xiàn)(Python語(yǔ)言)

1. class Node:

2. key=None

3. value=None

4. pre=None

5. next=None

7. def __init__(self,key,value):

8. self.key=key

9. self.value=value

11. class LRUCache:

12. capacity=0

13. map={} # key is string ,and value is Node object

14. head=None

15. end=None

17. def __init__(self,capacity):

18. self.capacity=capacity

20. def get(self,key):

21. if key in self.map:

22. node=self.map[key]

23. self.remove(node)

24. self.setHead(node)

25. return node.value

26. else:

27. return -1

29. def getAllKeys(self):

30. tmpNode=None

31. if self.head:

32. tmpNode=self.head

33. while tmpNode:

34. print (tmpNode.key,tmpNode.value)

35. tmpNode=tmpNode.next

37. def remove(self,n):

38. if n.pre:

39. n.pre.next=n.next

40. else:

41. self.head=n.next

43. if n.next:

44. n.next.pre=n.pre

45. else:

46. self.end=n.pre

48. def setHead(self,n):

49. n.next=self.head

50. n.pre=None

52. if self.head:

53. self.head.pre=n

55. self.head=n

57. if not self.end:

58. self.end=self.head

60. def set(self,key,value):

61. if key in self.map:

62. oldNode=self.map[key]

63. oldNode.value=value

64. self.remove(oldNode)

65. self.setHead(oldNode)

66. else:

67. node=Node(key,value)

68. if len(self.map) >= self.capacity:

69. self.map.pop(self.end.key)

70. self.remove(self.end)

71. self.setHead(node)

72. else:

73. self.setHead(node)

75. self.map[key]=node

78. def main():

79. cache=LRUCache(100)

81. #d->c->b->a

82. cache.set('a','1')

83. cache.set('b','2')

84. cache.set('c',3)

85. cache.set('d',4)

87. #遍歷lru鏈表

88. cache.getAllKeys()

90. #改動(dòng)('a','1') ==> ('a',5),使該節(jié)點(diǎn)從LRU尾端移動(dòng)到開頭.

91. cache.set('a',5)

92. #LRU鏈表變?yōu)?a->d->c->b

94. cache.getAllKeys()

95. #拜訪key='c'的節(jié)點(diǎn),是該節(jié)點(diǎn)從移動(dòng)到LRU頭部

96. cache.get('c')

97. #LRU鏈表變?yōu)?c->a->d->b

98. cache.getAllKeys()

100. if __name__ == '__main__':

101. main()

通過上面簡(jiǎn)單的介紹與實(shí)現(xiàn),現(xiàn)在我們基本已經(jīng)了解了什么是LRU,下面我們來(lái)看看LRU算法在redis 內(nèi)部的實(shí)現(xiàn)細(xì)節(jié),以及其會(huì)在什么情況下帶來(lái)問題.在redis內(nèi)部,是通過全局結(jié)構(gòu)體redisServer 保留redis啟動(dòng)之后相關(guān)的信息.比如:

1. struct redisServer {

2. pid_t pid; /* Main process pid. */

3. char *configfile; /* Absolute config file path, or NULL */

4. …..

5. unsigned lruclock:LRU_BITS; /* Clock for LRU eviction */

6. ...

7. };

serverCron運(yùn)行頻率hz等lruclock:LRU_BITS,此中存儲(chǔ)了服務(wù)器自啟動(dòng)之后的lru時(shí)鐘,該時(shí)鐘是全局的lru時(shí)鐘.該時(shí)鐘100ms(可以通過hz來(lái)調(diào)整,默認(rèn)情況hz=10,因此每1000ms/10=100ms執(zhí)行一次定時(shí)任務(wù))更新一次.

接下來(lái)我們看看LRU時(shí)鐘的具體實(shí)現(xiàn):

1. server.lruclock = getLRUClock();

2. getLRUClock函數(shù)如下:

3. #define LRU_CLOCK_RESOLUTION 1000 /* LRU clock resolution in ms */

4. #define LRU_BITS 24

5. #define LRU_CLOCK_MAX ((1<<LRU_BITS)-1) /* Max value of obj->lru */

6. /* Return the LRU clock, based on the clock resolution. This is a time

7. * in a reduced-bits format that can be used to set and check the

8. * object->lru field of redisObject structures. */

10. unsigned int getLRUClock(void) {

11. return (mstime()/LRU_CLOCK_RESOLUTION) & LRU_CLOCK_MAX;

12. }

因此lrulock最大能到(2**24-1)/3600/24 = 194天,如果跨越了這個(gè)時(shí)間,lrulock重新開始.

對(duì)于redis server來(lái)說,server.lrulock表示的是一個(gè)全局的lrulock,那么對(duì)于每個(gè)redisObject都有一個(gè)本身的lrulock.這樣每redisObject就可以根據(jù)本身的lrulock和全局的server.lrulock比較,來(lái)確定是否能夠被淘汰掉.

redis key對(duì)應(yīng)的value的寄存對(duì)象:

1. typedef struct redisObject {

2. unsigned type:4;

3. unsigned encoding:4;

4. unsigned lru:LRU_BITS; /* LRU time (relative to server.lruclock) or

5. * LFU data (least significant 8 bits frequency

6. * and most significant 16 bits decreas time). */

7. int refcount;

8. void *ptr;

9. } robj

那么什么時(shí)候,lru會(huì)被更新呢 ?拜訪該key,lru都會(huì)被更新,這樣該key就能及時(shí)的被移動(dòng)到lru頭部,從而避免從lru中淘汰.下面是這一部分的實(shí)現(xiàn):

/* Low level key lookup API, not actually called directly from commands

1. * implementations that should instead rely on lookupKeyRead(),

2. * lookupKeyWrite() and lookupKeyReadWithFlags(). */

3. robj *lookupKey(redisDb *db, robj *key, int flags) {

4. dictEntry *de = dictFind(db->dict,key->ptr);

5. if (de) {

6. robj *val = dictGetVal(de);

8. /* Update the access time for the ageing algorithm.

9. * Don't do it if we have a saving child, as this will trigger

10. * a copy on write madness. */

11. if (server.rdb_child_pid == -1 &&

12. server.aof_child_pid == -1 &&

13. !(flags & LOOKUP_NOTOUCH))

14. {

15. if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {

16. unsigned long ldt = val->lru >> 8;

17. unsigned long counter = LFULogIncr(val->lru & 255);

18. val->lru = (ldt << 8) | counter;

19. } else {

20. val->lru = LRU_CLOCK();

21. }

22. }

23. return val;

24. } else {

25. return NULL;

26. }

27. }

接下來(lái),我們?cè)趤?lái)闡發(fā),key的lru淘汰策略如何實(shí)現(xiàn),分別有哪幾種:

1. # MAXMEMORY POLICY: how Redis will select what to remove when maxmemory

2. # is reached. You can select among five behaviors:

3. #

4. # volatile-lru -> Evict using approximated LRU among the keys with an expire set. //在設(shè)置了過期光陰的key中,使用近似的lru淘汰策略

5. # allkeys-lru -> Evict any key using approximated LRU. //所有的key均使用近似的lru淘汰策略

6. # volatile-lfu -> Evict using approximated LFU among the keys with an expire set. //在設(shè)置了過期光陰的key中,使用lfu淘汰策略

7. # allkeys-lfu -> Evict any key using approximated LFU. //所有的key均使用lfu淘汰策略

8. # volatile-random -> Remove a random key among the ones with an expire set. //在設(shè)置了過期光陰的key中,使用隨機(jī)淘汰策略

9. # allkeys-random -> Remove a random key, any key. //所有的key均使用隨機(jī)淘汰策略

10. # volatile-ttl -> Remove the key with the nearest expire time (minor TTL) //使用ttl淘汰策略

11. # noeviction -> Don't evict anything, just return an error on write operations . //不允許淘汰,在寫操作發(fā)生,但內(nèi)存不夠時(shí),將會(huì)返回差錯(cuò)

12. #

13. # LRU means Least Recently Used

14. # LFU means Least Frequently Used

15. #

16. # Both LRU, LFU and volatile-ttl are implemented using approximated

17. # randomized algorithms.

這里暫不討論LFU,TTL淘汰算法和noeviction的情況,僅僅討論lru所有場(chǎng)景下的,淘汰策略具體實(shí)現(xiàn).(LFU和TTL將在下一篇文章中詳細(xì)闡發(fā)).

LRU淘汰的場(chǎng)景:

1.主動(dòng)淘汰.

1.1 通過定時(shí)任務(wù)serverCron按期的清理過期的key.

2.被動(dòng)淘汰

2.1 每次寫入key時(shí),發(fā)現(xiàn)內(nèi)存不夠,調(diào)用activeExpireCycle釋放一部門內(nèi)存.

2.2 每次拜訪相關(guān)的key,如果發(fā)現(xiàn)key過期,直接釋放掉該key相關(guān)的內(nèi)存.

首先我們來(lái)闡發(fā)LRU主動(dòng)淘汰的場(chǎng)景:

serverCron每間隔1000/hz ms會(huì)調(diào)用databasesCron辦法來(lái)檢測(cè)并淘汰過期的key.

1. void databasesCron(void){

2. /* Expire keys by random sampling. Not required for slaves

3. * as master will synthesize DELs for us. */

4. if (server.active_expire_enabled && server.masterhost == NULL)

5. activeExpireCycle(ACTIVE_EXPIRE_CYCLE_SLOW);

6. …..

7. }

主動(dòng)淘汰是通過activeExpireCycle 來(lái)實(shí)現(xiàn)的,這部門的邏輯如下:

1. 遍歷至多16個(gè)DB .【由宏CRON_DBS_PER_CALL界說,默認(rèn)為16】

2. 隨機(jī)挑選20個(gè)帶過期時(shí)間的key.【由宏ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP界說,默認(rèn)20】

3. 如果key過時(shí),則將key相關(guān)的內(nèi)存釋放,或者放入失效隊(duì)列.

4. 如果操作時(shí)間超過允許的限定時(shí)間,至多25ms.(timelimit = 1000000*ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC/server.hz/100,,ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC=25,server.hz默認(rèn)為10), 則此次淘汰操作結(jié)束返回,不然進(jìn)入5.

5. 如果該DB下,有超過5個(gè)key (ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP/4=5) 實(shí)際失效,則進(jìn)入 2,不然選擇下一個(gè)DB,再次進(jìn)入2.

6. 遍歷完成,結(jié)束.

流程圖如下

注：(圖中年夜于等于%5的可以是實(shí)際過期的,應(yīng)改為年夜于等于%25的key是實(shí)際過期的.iteration++是在遍歷20個(gè)key的時(shí)候,每次加1).

被動(dòng)淘汰 - 內(nèi)存不夠,挪用activeExpireCycle釋放

該步調(diào)的實(shí)現(xiàn)方式如下:

1. processCommand 函數(shù)關(guān)于內(nèi)存淘汰策略的邏輯:

2. /* Handle the maxmemory directive.

3. *

4. * First we try to free some memory if possible (if there are volatile

5. * keys in the dataset). If there are not the only thing we can do

6. * is returning an error. */

7. if (server.maxmemory) {

8. int retval = freeMemoryIfNeeded();

9. /* freeMemoryIfNeeded may flush slave output buffers. This may result

10. * into a slave, that may be the active client, to be freed. */

11. if (server.current_client == NULL) return C_ERR;

13. /* It was impossible to free enough memory, and the command the client

14. * is trying to execute is denied during OOM conditions? Error. */

15. if ((c->cmd->flags & CMD_DENYOOM) && retval == C_ERR) {

16. flagTransaction(c);

17. addReply(c, shared.oomerr);

18. return C_OK;

19. }

20. }

每次執(zhí)行命令前,都會(huì)調(diào)用freeMemoryIfNeeded來(lái)檢查內(nèi)存的情況,并釋放相應(yīng)的內(nèi)存,如果釋放后,內(nèi)存仍然不夠,直接向哀求的客戶端返回OOM.

具體的步調(diào)如下:

1. 獲取redis server當(dāng)前已經(jīng)使用的內(nèi)存mem_reported.

2. 如果mem_reported < server.maxmemory ,則返回ok.不然mem_used=mem_reported,進(jìn)入步驟3.

3. 遍歷該redis的所slaves,mem_used減去所有slave占用的ClientOutputBuffer.

4. 如果配置了AOF,mem_used減去AOF占用的空間.sdslen(server.aof_buf)+aofRewriteBufferSize().

5. 如果mem_used < server.maxmemory,返回ok.不然進(jìn)入步驟6.

6. 如果內(nèi)存策略配置為noeviction,返回錯(cuò)誤.不然進(jìn)入7.

7. 如果是LRU策略,如果是VOLATILE的LRU,則每次從可失效的數(shù)據(jù)集中,每次隨機(jī)采樣maxmemory_samples(默認(rèn)為5)個(gè)key,從中選取idletime最大的key進(jìn)行淘汰.不然,如果是ALLKEYS_LRU則從全局?jǐn)?shù)據(jù)中進(jìn)行采樣,每次隨機(jī)采樣maxmemory_samples(默認(rèn)為5)個(gè)key,并從中選擇idletime最大的key進(jìn)行淘汰.

8. 如果釋放內(nèi)存之后,還是跨越了server.maxmemory,則繼續(xù)淘汰,只到釋放后剩下的內(nèi)存小于server.maxmemory為止.

被動(dòng)淘汰 - 每次拜訪相關(guān)的key,如果發(fā)現(xiàn)key過期,直接釋放掉該key相關(guān)的內(nèi)存:

每次拜訪key,都會(huì)調(diào)用expireIfNeeded來(lái)判斷key是否過期,如果過期,則釋放掉,并返回null,否則返回key的值.

總結(jié)

1.redis做為緩存,經(jīng)常采納LRU的策略來(lái)淘汰數(shù)據(jù),所以如果同時(shí)過期的數(shù)據(jù)太多,就會(huì)導(dǎo)致redis發(fā)起主動(dòng)檢測(cè)時(shí)耗費(fèi)的時(shí)間過長(zhǎng)(最大為250ms),從而導(dǎo)致最大應(yīng)用超時(shí) >= 250ms.

• timelimit = 1000000*ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC/server.hz/100

• ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC=25

• server.hz>=1(默認(rèn)為10)

• timelimit <= 250ms

2.內(nèi)存使用率過高,則會(huì)導(dǎo)致內(nèi)存不夠,從而發(fā)起被動(dòng)淘汰策略,從而使應(yīng)用拜訪超時(shí).

3.合理的調(diào)整hz參數(shù),從而控制每次主動(dòng)淘汰的頻率,從而有效的緩解過時(shí)的key數(shù)量太多帶來(lái)的上述超時(shí)問題.