YYMemoryCache是YYCache中的內(nèi)存緩存模塊，是采用了LRU算法實現(xiàn)的經(jīng)典源碼。YYMemoryCache用一個字典對象來存取緩存數(shù)據(jù)，當緩存數(shù)據(jù)超過指定容量上限時，會刪除部分緩存。

1、LRU

LRU全稱是Least recently used，是一種常用的緩存淘汰算法，遵循最近最少使用原則，當發(fā)生內(nèi)存警告或者緩存值達到上限,會優(yōu)先淘汰時間戳靠前的對象,最近使用的不被淘汰。

常見的實現(xiàn)方式是使用雙鏈表配合哈希表來存儲緩存數(shù)據(jù)，哈希表保存key和節(jié)點，避免了遍歷鏈表的耗時，雙向鏈表控制節(jié)點順序，當位置需要更改時，可以直接更改節(jié)點，避免遍歷鏈表的耗時。

LRU結(jié)構(gòu)圖

當有新數(shù)據(jù)要緩存時，先將緩存數(shù)據(jù)包裝成一個節(jié)點，插入雙向鏈表的頭部。如果訪問鏈表中存在該緩存數(shù)據(jù)，將該數(shù)據(jù)對應的節(jié)點移動至鏈表的頭部。這樣的做法保證了被使用的數(shù)據(jù)（存儲/訪問）始終位于鏈表的前部。當緩存的數(shù)據(jù)總量超出容量時，先刪除末尾的緩存數(shù)據(jù)節(jié)點，因為末尾的數(shù)據(jù)最少被使用過。

根據(jù)這個算法的原理，我們探索下YYMemoryCache的源碼實現(xiàn)

2、YYMemoryCache

2.1 鏈表的實現(xiàn)

（1） _YYLinkMap

@interface _YYLinkedMap : NSObject {
    @package
    CFMutableDictionaryRef _dic; //哈希字典，存放緩存數(shù)據(jù)
    NSUInteger _totalCost; //緩存總大小
    NSUInteger _totalCount; //緩存節(jié)點總個數(shù)
    _YYLinkedMapNode *_head; //頭結(jié)點
    _YYLinkedMapNode *_tail; //尾結(jié)點
    BOOL _releaseOnMainThread; //在主線程釋放
    BOOL _releaseAsynchronously;//在異步線程釋放
}

_YYLinkMap負責實現(xiàn)緩存和LRU的功能，其中使用了C語言中的CFMutableDictionaryRef來替代了OC中的NSMutableDictionary，主要原因有二：

• 速度相對較快
• key無需遵守NSCopying協(xié)議

（2） _YYLinkedMapNode

@interface _YYLinkedMapNode : NSObject {
    @package
    __unsafe_unretained _YYLinkedMapNode *_prev; //前向前一個節(jié)點的指針
    __unsafe_unretained _YYLinkedMapNode *_next; //指向下一個節(jié)點的指針
    id _key; //緩存數(shù)據(jù)key
    id _value; //緩存數(shù)據(jù)value
    NSUInteger _cost; //節(jié)點占用大小
    NSTimeInterval _time; //節(jié)點操作時間戳
}

_YYLinkedMapNode封裝了緩存數(shù)據(jù)的信息

（3）添加新節(jié)點

// 將一個node對象插到隊列最前面
- (void)insertNodeAtHead:(_YYLinkedMapNode *)node {
    CFDictionarySetValue(_dic, (__bridge const void *)(node->_key), (__bridge const void *)(node)); //存入字典中
    _totalCost += node->_cost; //更新總大小
    _totalCount++; //更新總數(shù)
    if (_head) { //節(jié)點置于鏈表頭部
        node->_next = _head;
        _head->_prev = node;
        _head = node;
    } else {
        _head = _tail = node;
    }
}

（4） 移動節(jié)點

// 將一個node放到隊列最前面
- (void)bringNodeToHead:(_YYLinkedMapNode *)node {
    if (_head == node) return;//如果當前節(jié)點是表頭
    
    if (_tail == node) {//如果當前節(jié)點是尾節(jié)點
        _tail = node->_prev;//將node的前驅(qū)結(jié)點指向尾節(jié)點
        _tail->_next = nil;//將尾節(jié)點的后繼節(jié)點置空
    } else {
        node->_next->_prev = node->_prev;//將node指向的下一個節(jié)點的前驅(qū)節(jié)點,指向node的前驅(qū)節(jié)點
        node->_prev->_next = node->_next;//將node指向的上一個節(jié)點的后繼節(jié)點,指向node的后繼節(jié)點,從鏈表中剝離出node
    }
    node->_next = _head;//將node的后繼節(jié)點指向當前頭節(jié)點
    node->_prev = nil;//將node的前驅(qū)節(jié)點置空
    _head->_prev = node;//此時的頭節(jié)點的前驅(qū)指向node
    _head = node;//將此時的node置為頭節(jié)點
}

（5）刪除節(jié)點

//移除掉指定node，前提是node為鏈表中的一個節(jié)點
- (void)removeNode:(_YYLinkedMapNode *)node {
    CFDictionaryRemoveValue(_dic, (__bridge const void *)(node->_key));
    _totalCost -= node->_cost;//調(diào)整總開銷
    _totalCount--;//調(diào)整總緩存數(shù)
    if (node->_next) node->_next->_prev = node->_prev;//如果node 存在后繼節(jié)點,則將node的后繼節(jié)點的前驅(qū)指向node的前驅(qū)結(jié)點
    if (node->_prev) node->_prev->_next = node->_next;//如果node 存在前驅(qū)節(jié)點,則將node的前驅(qū)節(jié)點的后繼指向node的后繼節(jié)點
    if (_head == node) _head = node->_next;//如果node是頭節(jié)點,則將node的后繼節(jié)點置為頭節(jié)點
    if (_tail == node) _tail = node->_prev;//如果node是尾節(jié)點, 則將node的前驅(qū)結(jié)點置為尾節(jié)點
}

（6）刪除尾結(jié)點

//將最后一個node移除
- (_YYLinkedMapNode *)removeTailNode {
    if (!_tail) return nil;
    _YYLinkedMapNode *tail = _tail;
    CFDictionaryRemoveValue(_dic, (__bridge const void *)(_tail->_key));
    _totalCost -= _tail->_cost;
    _totalCount--;
    if (_head == _tail) {
        _head = _tail = nil;
    } else {
        _tail = _tail->_prev;
        _tail->_next = nil;
    }
    return tail;
}

（7）清除鏈表

- (void)removeAll {
    _totalCost = 0;
    _totalCount = 0;
    _head = nil;
    _tail = nil;
    if (CFDictionaryGetCount(_dic) > 0) {
        CFMutableDictionaryRef holder = _dic;
        _dic = CFDictionaryCreateMutable(CFAllocatorGetDefault(), 0, &kCFTypeDictionaryKeyCallBacks, &kCFTypeDictionaryValueCallBacks);
        
        if (_releaseAsynchronously) {
            dispatch_queue_t queue = _releaseOnMainThread ? dispatch_get_main_queue() : YYMemoryCacheGetReleaseQueue();
            dispatch_async(queue, ^{
                CFRelease(holder); // hold and release in specified queue
            });
        } else if (_releaseOnMainThread && !pthread_main_np()) {
            dispatch_async(dispatch_get_main_queue(), ^{
                CFRelease(holder); // hold and release in specified queue
            });
        } else {
            CFRelease(holder);
        }
    }
}

2.2 鏈表的使用

2.2.1 鎖

（1）為什么要用鎖
多線程很容易引起資源的搶奪，所以開放時都需要用到鎖來保證線程安全

iOS鎖性能

在YYCache中前期使用的是OSSpinLock，但由于iOS系統(tǒng)的更新迭代，系統(tǒng)維護了 5 個不同的線程優(yōu)先級/QoS: background，utility，default，user-initiated，user-interactive。高優(yōu)先級線程始終會在低優(yōu)先級線程前執(zhí)行，一個線程不會受到比它更低優(yōu)先級線程的干擾。這種線程調(diào)度算法會產(chǎn)生潛在的優(yōu)先級反轉(zhuǎn)問題，從而破壞了 spin lock。(具體查看不再安全的 OSSpinLock），所以現(xiàn)在采用的是pthread_mutex。

（2）pthread_mutex
pthread_mutex是互斥鎖，當涉及多線程執(zhí)行代碼的情況下，通過pthread_mutex_lock(&_lock)方法給下面的代碼塊加互斥鎖，這樣其它線程會被阻塞，直到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。

2.2.2 使用

（1）初始化

- (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;
    _shouldRemoveAllObjectsOnMemoryWarning = YES;
    _shouldRemoveAllObjectsWhenEnteringBackground = YES;
    
    [[NSNotificationCenter defaultCenter] addObserver:self selector:@selector(_appDidReceiveMemoryWarningNotification) name:UIApplicationDidReceiveMemoryWarningNotification object:nil];
    [[NSNotificationCenter defaultCenter] addObserver:self selector:@selector(_appDidEnterBackgroundNotification) name:UIApplicationDidEnterBackgroundNotification object:nil];
    
    [self _trimRecursively];
    return self;
}

- (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]; //在異步隊列中執(zhí)行邊界檢測
        [self _trimRecursively]; //循環(huán)調(diào)用本方法
    });
}

- (void)_trimInBackground {
    dispatch_async(_queue, ^{
        [self _trimToCost:self->_costLimit];
        [self _trimToCount:self->_countLimit];
        [self _trimToAge:self->_ageLimit];
    });
}

初始化中，創(chuàng)建了lru對象，設置了基本參數(shù)，添加了內(nèi)存警告和進入后臺通知，_trimRecursively是緩存空間邊界檢測

（2）邊界檢測

- (void)_trimToCost:(NSUInteger)costLimit {
    BOOL finish = NO;
    pthread_mutex_lock(&_lock);
    if (costLimit == 0) {
        [_lru removeAll];
        finish = YES;
    } else if (_lru->_totalCost <= costLimit) {
        finish = YES;
    }
    pthread_mutex_unlock(&_lock);
    if (finish) return;
    
    NSMutableArray *holder = [NSMutableArray new];
    while (!finish) {
        if (pthread_mutex_trylock(&_lock) == 0) {
            if (_lru->_totalCost > costLimit) {
                _YYLinkedMapNode *node = [_lru removeTailNode];
                if (node) [holder addObject:node];
            } else {
                finish = YES;
            }
            pthread_mutex_unlock(&_lock);
        } else {
            usleep(10 * 1000); //10 ms
        }
    }
    if (holder.count) {
        dispatch_queue_t queue = _lru->_releaseOnMainThread ? dispatch_get_main_queue() : YYMemoryCacheGetReleaseQueue();
        dispatch_async(queue, ^{
            [holder count]; // release in queue
        });
    }
}

- (void)_trimToCount:(NSUInteger)countLimit {
    BOOL finish = NO;
    pthread_mutex_lock(&_lock);
    if (countLimit == 0) {
        [_lru removeAll];
        finish = YES;
    } else if (_lru->_totalCount <= countLimit) {
        finish = YES;
    }
    pthread_mutex_unlock(&_lock);
    if (finish) return;
    
    NSMutableArray *holder = [NSMutableArray new];
    while (!finish) {
        if (pthread_mutex_trylock(&_lock) == 0) {
            if (_lru->_totalCount > countLimit) {
                _YYLinkedMapNode *node = [_lru removeTailNode];
                if (node) [holder addObject:node];
            } else {
                finish = YES;
            }
            pthread_mutex_unlock(&_lock);
        } else {
            usleep(10 * 1000); //10 ms
        }
    }
    if (holder.count) {
        dispatch_queue_t queue = _lru->_releaseOnMainThread ? dispatch_get_main_queue() : YYMemoryCacheGetReleaseQueue();
        dispatch_async(queue, ^{
            [holder count]; // release in queue
        });
    }
}

- (void)_trimToAge:(NSTimeInterval)ageLimit {
    BOOL finish = NO;
    NSTimeInterval now = CACurrentMediaTime();
    pthread_mutex_lock(&_lock);
    if (ageLimit <= 0) {
        [_lru removeAll];
        finish = YES;
    } else if (!_lru->_tail || (now - _lru->_tail->_time) <= ageLimit) {
        finish = YES;
    }
    pthread_mutex_unlock(&_lock);
    if (finish) return;
    
    NSMutableArray *holder = [NSMutableArray new];
    while (!finish) {
        if (pthread_mutex_trylock(&_lock) == 0) {
            if (_lru->_tail && (now - _lru->_tail->_time) > ageLimit) {
                _YYLinkedMapNode *node = [_lru removeTailNode];
                if (node) [holder addObject:node];
            } else {
                finish = YES;
            }
            pthread_mutex_unlock(&_lock);
        } else {
            usleep(10 * 1000); //10 ms
        }
    }
    if (holder.count) {
        dispatch_queue_t queue = _lru->_releaseOnMainThread ? dispatch_get_main_queue() : YYMemoryCacheGetReleaseQueue();
        dispatch_async(queue, ^{
            [holder count]; // release in queue
        });
    }
}

• _trimToCost 方法判斷了鏈表中所有節(jié)點占用大小之和totalCost是否大于costLimit，如果超過，則從鏈表末尾開始刪除節(jié)點，直到totalCost小于等于costLimit為止
• _trimToCount 方法判斷鏈表中的所有節(jié)點個數(shù)之和是否大于countLimit，如果超過，則從鏈表末尾開始刪除節(jié)點，直到個數(shù)之和小于等于countLimit為止
• _trimToAge 方法遍歷鏈表中的節(jié)點，刪除那些和now時刻的時間間隔大于ageLimit的節(jié)點
• 這里作者還使用了pthread_mutex_trylock，這個函數(shù)是非阻塞鎖，如果沒有獲取到鎖就會立刻返回不會阻塞當前線程,獲取鎖成功會返回0,否則返回其他值來說明鎖的狀態(tài).但是pthread_mutex_lock如果沒有獲取到鎖會一直等待從而發(fā)生阻塞.

（3）讀寫數(shù)據(jù)

- (id)objectForKey:(id)key {
    if (!key) return nil;
    pthread_mutex_lock(&_lock);
    _YYLinkedMapNode *node = CFDictionaryGetValue(_lru->_dic, (__bridge const void *)(key)); //從字典中讀取key相應的節(jié)點
    if (node) {
        node->_time = CACurrentMediaTime(); //更新節(jié)點訪問時間
        [_lru bringNodeToHead:node]; //將節(jié)點移動至鏈表頭部
    }
    pthread_mutex_unlock(&_lock);
    return node ? node->_value : nil;
}

- (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é)點
    NSTimeInterval now = CACurrentMediaTime();
    if (node) { //如果能取到，說明鏈表中之前存在key對應的緩存數(shù)據(jù)
         //更新totalCost 
        _lru->_totalCost -= node->_cost;
        _lru->_totalCost += cost;
        node->_cost = cost;
        node->_time = now; //更新節(jié)點的訪問時間
        node->_value = object; //更新節(jié)點中存放的緩存數(shù)據(jù)
        [_lru bringNodeToHead:node]; //將節(jié)點移至鏈表頭部
    } else { //如果不能取到，說明鏈表中之前不存在key對應的緩存數(shù)據(jù)
        node = [_YYLinkedMapNode new]; //創(chuàng)建新的節(jié)點
        node->_cost = cost;
        node->_time = now; //設置節(jié)點的時間
        node->_key = key; //設置節(jié)點的key
        node->_value = object; //設置節(jié)點中存放的緩存數(shù)據(jù)
        [_lru insertNodeAtHead:node]; //將新的節(jié)點加入鏈表頭部
    }
    if (_lru->_totalCost > _costLimit) {
        dispatch_async(_queue, ^{
            [self trimToCost:_costLimit];
        });
    }
    if (_lru->_totalCount > _countLimit) {
        _YYLinkedMapNode *node = [_lru removeTailNode];
        if (_lru->_releaseAsynchronously) {
            dispatch_queue_t queue = _lru->_releaseOnMainThread ? dispatch_get_main_queue() : YYMemoryCacheGetReleaseQueue();
            dispatch_async(queue, ^{
                [node class]; //hold and release in queue
            });
        } else if (_lru->_releaseOnMainThread && !pthread_main_np()) {
            dispatch_async(dispatch_get_main_queue(), ^{
                [node class]; //hold and release in queue
            });
        }
    }
    pthread_mutex_unlock(&_lock); //解鎖
}

每次YYMemoryCache在進行讀寫的時候都會添加互斥鎖，更新對應的linkedMapNode對象的時間戳屬性,并且把該對象放到隊列的最前面,從而調(diào)整了緩存中對象的順序。

（4）異步線程釋放

static inline dispatch_queue_t YYMemoryCacheGetReleaseQueue() {
    return dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_LOW, 0);
}

dispatch_queue_t queue = _lru->_releaseOnMainThread ? dispatch_get_main_queue() : YYMemoryCacheGetReleaseQueue();
    dispatch_async(queue, ^{
       [holder count]; // release in queue
    });

其實認真看可以發(fā)現(xiàn)源碼中很多地方都有諸如這樣的異步線程，這其實是個非常巧妙的做法（具體可以查看iOS 保持界面流暢的技巧）

Note: 對象的銷毀雖然消耗資源不多，但累積起來也是不容忽視的。通常當容器類持有大量對象時，其銷毀時的資源消耗就非常明顯。同樣的，如果對象可以放到后臺線程去釋放，那就挪到后臺線程去。這里有個小 Tip：把對象捕獲到 block 中，然后扔到后臺隊列去隨便發(fā)送個消息以避免編譯器警告，就可以讓對象在后臺線程銷毀了。

YYMemoryCacheGetReleaseQueue 是一個低優(yōu)先級DISPATCH_QUEUE_PRIORITY_LOW的全局隊列，這實際上是為了讓銷毀線程不占用主要的CPU使用時間，在相對空閑時進行銷毀，提升性能。