YYCache

大體結(jié)構(gòu)

NSCache

特性:

• 線程安全
• NSCache 底層并沒有用 NSDictionary 等已有的類，而是直接調(diào)用了 libcache.dylib，線程安全由 pthread_mutex 完成的。
• 性能和 key 的相似度有關(guān)，如果有大量相似的 key (比如 "1", "2", "3", ...) ，NSCache 的存取性能會(huì)劇烈下降，大量的時(shí)間被消耗在 CFStringEqual() 上
• 收到內(nèi)存警告時(shí), 馬上清空所有緩存, 無法精準(zhǔn)控制

YYMemoryCache

特征:

• LRU淘汰算法
• 收到內(nèi)存警告時(shí)可精準(zhǔn)控制行為
• 對(duì)象數(shù)量限制, 總?cè)萘肯拗? 存活時(shí)間限制
• 查詢和插入時(shí), 并不是通過遍歷雙向鏈表, 而是使用字典hash表快速查找到指定結(jié)點(diǎn), 保證效率

主要手段:

• CFMutableDictionaryRef來實(shí)現(xiàn)數(shù)據(jù)的實(shí)際存儲(chǔ)；
• 使用OSSpinLockLock來保證線程的安全 (之后改為pthread_mutex_lock)
• 使用_YYLinkedMapNode和_YYLinkedMap來組織數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)
• 使用YYMemoryCache來組織對(duì)數(shù)據(jù)的各種操作

性能對(duì)比 (QPS)

NSDictionary線程不安全, 表現(xiàn)最佳
YYCache表現(xiàn)優(yōu)于NSCache

性能對(duì)比

數(shù)據(jù)結(jié)構(gòu)的圖表 (LRU:Least Recently Used近期最少使用算法)

淘汰算法

數(shù)據(jù)結(jié)構(gòu)

Cache的操作共3種

• 插入：當(dāng)Cache未滿時(shí)，新的數(shù)據(jù)項(xiàng)只需插到雙鏈表頭部即可
• 替換：當(dāng)Cache已滿時(shí)，將新的數(shù)據(jù)項(xiàng)插到雙鏈表頭部，并刪除雙鏈表的尾結(jié)點(diǎn)即可
• 查找：每次數(shù)據(jù)項(xiàng)被查詢到時(shí)，都將此數(shù)據(jù)項(xiàng)移動(dòng)到鏈表頭部

鏈表

關(guān)于鎖的使用

用于內(nèi)存的鎖 (自旋鎖)

OSSpinLock 自旋鎖，性能最高的鎖。一直 do while 忙等。缺點(diǎn)是等待時(shí)消耗大量 CPU 資源，不適用于較長時(shí)間的任務(wù)。對(duì)于內(nèi)存緩存的存取來說，它非常合適。
根據(jù)大神博客, OSSPinLock有風(fēng)險(xiǎn), 蘋果的線程QoS會(huì)造成優(yōu)先級(jí)反轉(zhuǎn)
結(jié)論，除非開發(fā)者能保證訪問鎖的線程全部都處于同一優(yōu)先級(jí)，否則 iOS 系統(tǒng)中所有類型的自旋鎖都不能再使用了。
舊版本

- (void)setObject:(id)object forKey:(id)key withCost:(NSUInteger)cost {
    OSSpinLockLock(&_lock);
    _YYLinkedMapNode *node = CFDictionaryGetValue(_lru->_dic, (__bridge const void *)(key));
      if (node) {
        //移動(dòng)到頭結(jié)點(diǎn)
        [_lru bringNodeToHead:node];
    } else {
        //添加到頭部
        [_lru insertNodeAtHead:node];
    }
    OSSpinLockUnlock(&_lock);
}

鎖性能對(duì)比

新版本

- (void)setObject:(id)object forKey:(id)key withCost:(NSUInteger)cost {
    pthread_mutex_lock(&_lock);
    _YYLinkedMapNode *node = CFDictionaryGetValue(_lru->_dic, (__bridge const void *)(key));
    if (node) {
        //移動(dòng)到頭結(jié)點(diǎn)
        [_lru bringNodeToHead:node];
    } else {
        //添加到頭部
        [_lru insertNodeAtHead:node];
    }
    pthread_mutex_unlock(&_lock);
}

用于磁盤的鎖 (互斥鎖)

dispatch_semaphore 信號(hào)量，

• 沒有等待情況出現(xiàn)時(shí)，性能比 pthread_mutex 還要高，但有等待情況時(shí)，性能會(huì)下降許多
• 相對(duì)于 OSSpinLock ，優(yōu)勢在于等待時(shí)不會(huì)消耗 CPU 資源。更適合耗時(shí)較大的磁盤IO

YYDiskCache

tricky的地方

• 單條數(shù)據(jù)小于 20K 時(shí)，SQLite讀取性能越高
• 單條數(shù)據(jù)大于 20K 時(shí)，寫文件更快

最佳實(shí)踐

• SQLite 和文件存儲(chǔ)結(jié)合起來：key-value 元數(shù)據(jù)保存在 SQLite 中，而 value 數(shù)據(jù)則根據(jù)大小不同選擇 SQLite 或文件存儲(chǔ)。

結(jié)尾

自動(dòng)清理緩存

• 為什么要指定在主線程清理緩存呢?
• 這里為什么是pthread_mutex_trylock

- (void)_trimToCost:(NSUInteger)costLimit {
    /*
        costlimit為0時(shí), 直接清空所有并return
    */
    NSMutableArray *holder = [NSMutableArray new];
    BOOL finish = NO;

    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
        });
    }
}

更多關(guān)于鎖的問題