概述
上一篇主要講解了YYCache的文件結(jié)構(gòu)永脓，分析了YYCache類的相關(guān)方法迟赃，本章主要分析內(nèi)存緩存類YYMemoryCache秒旋。該對(duì)象內(nèi)部維護(hù)一個(gè)字典對(duì)象來存取緩存數(shù)據(jù)痴柔，同時(shí)支持緩存容量的限制，當(dāng)緩存數(shù)據(jù)超過指定的內(nèi)存容量大小的時(shí)候咐吼，會(huì)刪除部分緩存數(shù)據(jù)吹缔。這主要是通過LRU算法實(shí)現(xiàn)的。
LRU
LRU全稱是Least recently used锯茄，基于最近最少使用的原則厢塘，屬于一種緩存淘汰算法。實(shí)現(xiàn)思路是維護(hù)一個(gè)雙向鏈表數(shù)據(jù)結(jié)構(gòu)肌幽，每次有新數(shù)據(jù)要緩存時(shí)晚碾，將緩存數(shù)據(jù)包裝成一個(gè)節(jié)點(diǎn)，插入雙向鏈表的頭部牍颈，如果訪問鏈表中的緩存數(shù)據(jù)，同樣將該數(shù)據(jù)對(duì)應(yīng)的節(jié)點(diǎn)移動(dòng)至鏈表的頭部琅关。這樣的做法保證了被使用的數(shù)據(jù)（存儲(chǔ)/訪問）始終位于鏈表的前部煮岁。當(dāng)緩存的數(shù)據(jù)總量超出容量時(shí)，先刪除末尾的緩存數(shù)據(jù)節(jié)點(diǎn)涣易，因?yàn)槟┪驳臄?shù)據(jù)最少被使用過画机。如下圖：
YYMemoryCache內(nèi)部維護(hù)了一個(gè)_YYLinkMap對(duì)象，_YYLinkMap對(duì)象負(fù)責(zé)實(shí)現(xiàn)緩存和LRU的功能新症。下面是代碼注釋：
@interface _YYLinkedMap : NSObject {
@package
CFMutableDictionaryRef _dic; //哈希字典步氏，存放緩存數(shù)據(jù)
NSUInteger _totalCost; //緩存總大小
NSUInteger _totalCount; //緩存節(jié)點(diǎn)總個(gè)數(shù)
_YYLinkedMapNode *_head; //頭結(jié)點(diǎn)
_YYLinkedMapNode *_tail; //尾結(jié)點(diǎn)
BOOL _releaseOnMainThread; //在主線程釋放
BOOL _releaseAsynchronously;//在異步線程釋放
}
@end
_dic是哈希字典，負(fù)責(zé)存放緩存數(shù)據(jù)徒爹，_head和_tail分別是雙鏈表中指向頭節(jié)點(diǎn)和尾節(jié)點(diǎn)的指針荚醒，鏈表中的節(jié)點(diǎn)單元是_YYLinkedMapNode對(duì)象芋类，該對(duì)象封裝了緩存數(shù)據(jù)的信息。
@interface _YYLinkedMapNode : NSObject {
@package
__unsafe_unretained _YYLinkedMapNode *_prev; //前向前一個(gè)節(jié)點(diǎn)的指針
__unsafe_unretained _YYLinkedMapNode *_next; //指向下一個(gè)節(jié)點(diǎn)的指針
id _key; //緩存數(shù)據(jù)key
id _value; //緩存數(shù)據(jù)value
NSUInteger _cost; //節(jié)點(diǎn)占用大小
NSTimeInterval _time; //節(jié)點(diǎn)操作時(shí)間戳
}
@end
下面分析一下_YYLinkedMap對(duì)象的主要方法：
-
insertNodeAtHead:方法
該方法首先將需要新插入的數(shù)據(jù)節(jié)點(diǎn)存入字典中界阁，以節(jié)點(diǎn)中的key作為字典的key侯繁。然后更新總大小_totalCost和節(jié)點(diǎn)總個(gè)數(shù)_totalCount，將節(jié)點(diǎn)置于鏈表頭部泡躯。
- (void)insertNodeAtHead:(_YYLinkedMapNode *)node { CFDictionarySetValue(_dic, (__bridge const void *)(node->_key), (__bridge const void *)(node)); //存入字典中 _totalCost += node->_cost; //更新總大小 _totalCount++; //更新總數(shù) if (_head) { //節(jié)點(diǎn)置于鏈表頭部 node->_next = _head; _head->_prev = node; _head = node; } else { _head = _tail = node; } } -
bringNodeToHead:方法
該方法將節(jié)點(diǎn)移動(dòng)至鏈表的頭部贮竟，因?yàn)檎{(diào)用該方法的場(chǎng)景是節(jié)點(diǎn)已經(jīng)存在于字典中，所以不需要新加入字典中较剃。
- (void)bringNodeToHead:(_YYLinkedMapNode *)node { if (_head == node) return; if (_tail == node) { _tail = node->_prev; _tail->_next = nil; } else { node->_next->_prev = node->_prev; node->_prev->_next = node->_next; } node->_next = _head; node->_prev = nil; _head->_prev = node; _head = node; } -
removeNode方法和removeTailNode方法
removeNode方法將數(shù)據(jù)節(jié)點(diǎn)從字典和鏈表中刪除咕别，同時(shí)更新總大小_totalCost和節(jié)點(diǎn)總個(gè)數(shù)_totalCount。removeTailNode方法將鏈表中的尾部節(jié)點(diǎn)刪除写穴，同時(shí)從字典中刪除節(jié)點(diǎn)惰拱。
-
removeAll方法
該方法刪除鏈表中所有節(jié)點(diǎn)，同時(shí)從字典中刪除所有節(jié)點(diǎn)确垫。
YYMemoryCache
YYMemoryCache實(shí)現(xiàn)了內(nèi)存緩存的功能弓颈，下面是其維護(hù)的成員變量：
pthread_mutex_t _lock;
_YYLinkedMap *_lru;
dispatch_queue_t _queue;
_lock是互斥所，當(dāng)涉及多線程執(zhí)行代碼的情況下删掀，通過pthread_mutex_lock(&_lock)方法給下面的代碼塊加互斥鎖翔冀，這樣其它線程會(huì)被阻塞，直到pthread_mutex_unlock(&_lock)被調(diào)用披泪。如下：
pthread_mutex_lock(&_lock);
//代碼塊1
pthread_mutex_unlock(&_lock);
pthread_mutex_lock(&_lock);
//代碼塊2
pthread_mutex_unlock(&_lock);
線程A執(zhí)行代碼塊1纤子，線程B執(zhí)行代碼塊2，如果線程A先執(zhí)行代碼塊1款票，_lock被鎖住控硼，這樣線程B被阻塞，直到線程A執(zhí)行完代碼塊1后艾少，調(diào)用pthread_mutex_unlock(_lock)卡乾，線程B開始執(zhí)行代碼塊2。由于執(zhí)行緩存的操作很容易涉及到多線程調(diào)用缚够，所以需要通過pthread_mutex_lock來控制幔妨，關(guān)于各種鎖性能的測(cè)試，YYCache的作者ibireme大神在他的博客中進(jìn)行了闡述谍椅。
_lru用來做數(shù)據(jù)緩存误堡，實(shí)現(xiàn)了lru算法。下面分析一下YYMemoryCache主要的方法：
-
初始化
調(diào)用init方法進(jìn)行初始化雏吭，創(chuàng)建了lru對(duì)象锁施，進(jìn)行了一些參數(shù)設(shè)置，包括緩存節(jié)點(diǎn)個(gè)數(shù)限制，總cost限制悉抵，時(shí)間戳界限肩狂，進(jìn)行邊界檢測(cè)的間隔時(shí)長(zhǎng)等等。如下：
- (instancetype)init { self = super.init; pthread_mutex_init(&_lock, NULL); _lru = [_YYLinkedMap new]; _queue = dispatch_queue_create("com.ibireme.cache.memory", DISPATCH_QUEUE_SERIAL); _countLimit = NSUIntegerMax; _costLimit = NSUIntegerMax; _ageLimit = DBL_MAX; _autoTrimInterval = 5.0; ... [self _trimRecursively]; return self; }這些limit參數(shù)如果不設(shè)置基跑，默認(rèn)值都是最大婚温，且這些參數(shù)以及_trimRecursively方法是用來做緩存空間的邊界檢測(cè)，在下文中提到媳否。
-
存儲(chǔ)數(shù)據(jù)
調(diào)用setObject: forKey:方法存儲(chǔ)緩存數(shù)據(jù)栅螟，代碼如下：
- (void)setObject:(id)object forKey:(id)key withCost:(NSUInteger)cost { if (!key) return; if (!object) { [self removeObjectForKey:key]; return; } pthread_mutex_lock(&_lock); //上鎖 _YYLinkedMapNode *node = CFDictionaryGetValue(_lru->_dic, (__bridge const void *)(key)); //從字典中取節(jié)點(diǎn) NSTimeInterval now = CACurrentMediaTime(); if (node) { //如果能取到，說明鏈表中之前存在key對(duì)應(yīng)的緩存數(shù)據(jù) //更新totalCost _lru->_totalCost -= node->_cost; _lru->_totalCost += cost; node->_cost = cost; node->_time = now; //更新節(jié)點(diǎn)的訪問時(shí)間 node->_value = object; //更新節(jié)點(diǎn)中存放的緩存數(shù)據(jù) [_lru bringNodeToHead:node]; //將節(jié)點(diǎn)移至鏈表頭部 } else { //如果不能取到篱竭，說明鏈表中之前不存在key對(duì)應(yīng)的緩存數(shù)據(jù) node = [_YYLinkedMapNode new]; //創(chuàng)建新的節(jié)點(diǎn) node->_cost = cost; node->_time = now; //設(shè)置節(jié)點(diǎn)的時(shí)間 node->_key = key; //設(shè)置節(jié)點(diǎn)的key node->_value = object; //設(shè)置節(jié)點(diǎn)中存放的緩存數(shù)據(jù) [_lru insertNodeAtHead:node]; //將新的節(jié)點(diǎn)加入鏈表頭部 } if (_lru->_totalCost > _costLimit) { dispatch_async(_queue, ^{ [self trimToCost:_costLimit]; }); } if (_lru->_totalCount > _countLimit) { _YYLinkedMapNode *node = [_lru removeTailNode]; ... } pthread_mutex_unlock(&_lock); //解鎖 }首先判斷key和object是否為空力图，object如果為空，刪除緩存中key對(duì)應(yīng)的數(shù)據(jù)掺逼。然后從字典中查找key對(duì)應(yīng)的緩存數(shù)據(jù)吃媒，分為兩種情況，如果訪問到節(jié)點(diǎn)吕喘，說明緩存數(shù)據(jù)存在赘那，則根據(jù)最近最少使用原則，將本次操作的節(jié)點(diǎn)移動(dòng)至鏈表的頭部氯质，同時(shí)更新節(jié)點(diǎn)的訪問時(shí)間募舟。如果訪問不到節(jié)點(diǎn)，說明是第一次添加key和數(shù)據(jù)闻察，需要?jiǎng)?chuàng)建一個(gè)新的節(jié)點(diǎn)拱礁，把節(jié)點(diǎn)存入字典中，并且加入鏈表頭部辕漂。cost是指定的呢灶，默認(rèn)是0。
-
訪問數(shù)據(jù)
調(diào)用objectForKey:方法訪問緩存數(shù)據(jù)钉嘹，代碼注釋如下：
- (id)objectForKey:(id)key { if (!key) return nil; pthread_mutex_lock(&_lock); _YYLinkedMapNode *node = CFDictionaryGetValue(_lru->_dic, (__bridge const void *)(key)); //從字典中讀取key相應(yīng)的節(jié)點(diǎn) if (node) { node->_time = CACurrentMediaTime(); //更新節(jié)點(diǎn)訪問時(shí)間 [_lru bringNodeToHead:node]; //將節(jié)點(diǎn)移動(dòng)至鏈表頭部 } pthread_mutex_unlock(&_lock); return node ? node->_value : nil; }該方法從字典中獲取緩存數(shù)據(jù)鸯乃，如果key對(duì)應(yīng)的數(shù)據(jù)存在，則更新訪問時(shí)間跋涣，根據(jù)最近最少使用原則缨睡，將本次操作的節(jié)點(diǎn)移動(dòng)至鏈表的頭部。如果不存在仆潮，則直接返回nil宏蛉。
-
邊界檢測(cè)
YYCache通過LRU算法處理緩存數(shù)據(jù)是否超出容量的情況遣臼。首先在初始化時(shí)性置，調(diào)用_trimRecursively方法，通過dispatch_after方法默認(rèn)每隔5秒重新調(diào)用揍堰。下面是代碼注釋：
- (void)_trimRecursively { __weak typeof(self) _self = self; dispatch_after(dispatch_time(DISPATCH_TIME_NOW, (int64_t)(_autoTrimInterval * NSEC_PER_SEC)), dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_LOW, 0), ^{ __strong typeof(_self) self = _self; if (!self) return; [self _trimInBackground]; //在異步隊(duì)列中執(zhí)行邊界檢測(cè) [self _trimRecursively]; //遞歸調(diào)用本方法 }); }_trimInBackground分別調(diào)用_trimToCost鹏浅、_trimToCount和_trimToAge方法檢測(cè)嗅义。
_trimToCost方法判斷鏈表中所有節(jié)點(diǎn)占用大小之和totalCost是否大于costLimit，如果超過隐砸，則從鏈表末尾開始刪除節(jié)點(diǎn)之碗，直到totalCost小于等于costLimit為止。代碼注釋如下：
- (void)_trimToCost:(NSUInteger)costLimit { BOOL finish = NO; ... NSMutableArray *holder = [NSMutableArray new]; while (!finish) { if (pthread_mutex_trylock(&_lock) == 0) { if (_lru->_totalCost > costLimit) { _YYLinkedMapNode *node = [_lru removeTailNode]; //刪除末尾節(jié)點(diǎn) if (node) [holder addObject:node]; } else { finish = YES; //totalCost<=costLimit,檢測(cè)完成 } pthread_mutex_unlock(&_lock); } else { usleep(10 * 1000); //10 ms } } ... }其中每個(gè)節(jié)點(diǎn)的cost是人為指定的季希，默認(rèn)是0褪那，且costLimit默認(rèn)是NSUIntegerMax，所以在默認(rèn)情況下式塌，_trimToCost方法不會(huì)刪除末尾的節(jié)點(diǎn)博敬。
_trimToCount方法判斷鏈表中的所有節(jié)點(diǎn)個(gè)數(shù)之和是否大于countLimit，如果超過峰尝，則從鏈表末尾開始刪除節(jié)點(diǎn)偏窝，直到個(gè)數(shù)之和小于等于countLimit為止。代碼注釋如下：
- (void)_trimToCount:(NSUInteger)countLimit { BOOL finish = NO; ... NSMutableArray *holder = [NSMutableArray new]; while (!finish) { if (pthread_mutex_trylock(&_lock) == 0) { if (_lru->_totalCount > countLimit) { _YYLinkedMapNode *node = [_lru removeTailNode]; //刪除末尾節(jié)點(diǎn) if (node) [holder addObject:node]; } else { finish = YES; //totalCount<=countLimit,檢測(cè)完成 } pthread_mutex_unlock(&_lock); } else { usleep(10 * 1000); //10 ms } } ... }初始化時(shí)countLimit默認(rèn)是NSUIntegerMax武学，如果不指定countLimit祭往，節(jié)點(diǎn)的總個(gè)數(shù)永遠(yuǎn)不會(huì)超過這個(gè)限制，所以_trimToCount方法不會(huì)刪除末尾節(jié)點(diǎn)火窒。
_trimToAge方法遍歷鏈表中的節(jié)點(diǎn)硼补，刪除那些和now時(shí)刻的時(shí)間間隔大于ageLimit的節(jié)點(diǎn)，代碼如下：
- (void)_trimToAge:(NSTimeInterval)ageLimit { BOOL finish = NO; ... NSMutableArray *holder = [NSMutableArray new]; while (!finish) { if (pthread_mutex_trylock(&_lock) == 0) { if (_lru->_tail && (now - _lru->_tail->_time) > ageLimit) { //間隔大于ageLimit _YYLinkedMapNode *node = [_lru removeTailNode]; //刪除末尾節(jié)點(diǎn) if (node) [holder addObject:node]; } else { finish = YES; } pthread_mutex_unlock(&_lock); } else { usleep(10 * 1000); //10 ms } } ... }由于鏈表中從頭部至尾部的節(jié)點(diǎn)沛鸵，訪問時(shí)間由晚至早括勺，所以尾部節(jié)點(diǎn)和now時(shí)刻的時(shí)間間隔較大，從尾節(jié)點(diǎn)開始刪除曲掰。ageLimit的默認(rèn)值是DBL_MAX疾捍，如果不人為指定ageLimit，則鏈表中節(jié)點(diǎn)不會(huì)被刪除栏妖。
-
線程同步
YYCache通過在方法中添加互斥所的邏輯乱豆，來保證多線程操作緩存時(shí)數(shù)據(jù)的同步。例如在setObject:forKey:withCost:方法和objectForKey:中添加代碼：
- (void)setObject:(id)object forKey:(id)key withCost:(NSUInteger)cost { pthread_mutex_lock(&_lock); //操作鏈表吊趾，寫緩存數(shù)據(jù) pthread_mutex_unlock(&_lock); } - (id)objectForKey:(id)key { pthread_mutex_lock(&_lock); //訪問緩存數(shù)據(jù) pthread_mutex_unlock(&_lock); }如果存在線程A和B宛裕，線程A在寫緩存的時(shí)候，上鎖论泛，線程B讀取緩存數(shù)據(jù)時(shí)揩尸，被阻塞，需要等到線程A執(zhí)行完寫緩存的操作屁奏，調(diào)用pthread_mutex_unlock后岩榆，線程B才能讀緩存數(shù)據(jù)，這個(gè)時(shí)候新的緩存數(shù)據(jù)已經(jīng)寫完，保證了操作的數(shù)據(jù)的同步勇边。
YYCache在每一個(gè)操作的緩存的方法中都是用了互斥所來保證多線程訪問數(shù)據(jù)的同步性犹撒，保證代碼執(zhí)行過程中的安全性。
總結(jié)
YYMemoryCache操作了內(nèi)存緩存粒褒，相較于硬盤緩存需要進(jìn)行I/O操作识颊，在性能上快很多，因此YYCache訪問緩存時(shí)奕坟，優(yōu)先用的是YYMemoryCache祥款。
