投稿文章，作者：潘顯躍

YYCache是用於Objective-C中用於緩存的第三方框架。此文主要用來講解該框架的實現細節，性能分析、設計思路ibireme已經講得很清楚了，我這邊就不在分析了。

文件結構

• YYCache：同時實現內存緩存和磁盤緩存且是線程安全的

• YYMemoryCache：實現內存緩存，所有的API都是線程安全的，與其他緩存方式比較不同的是內部利用LRU淘汰算法（後面會介紹）來提高性能

• YYDiskCache：實現磁盤緩存，所有的API都是線程安全的，內部也采用了LRU淘汰算法，主要SQLite和文件存儲兩種方式

• YYKVStorage：實現磁盤存儲，不推薦直接使用該類，該類不是線程安全的

LRU

LRU(Least recently used，最近最少使用)算法，根據訪問的歷史記錄來對數據進行淘汰

簡單的來說3點：

• 有新數據加入時添加到鏈表的頭部

• 每當緩存命中（即緩存數據被訪問），則將數據移到鏈表頭部

• 當鏈表滿的時候，將鏈表尾部的數據丟棄

在YYMemoryCache中使用來雙向鏈表和NSDictionary實現了LRU淘汰算法，後面會介紹

關於鎖

YYCache 使用到兩種鎖

• OSSpinLock ：自旋鎖，上一篇博客也提及到pthread_mutex

• dispatch_semaphore：信號量，當信號量為1的時候充當鎖來用

內存緩存用的pthread_mutex：由於pthread_mutex相當於do while忙等，等待時會消耗大量的CPU資源

磁盤緩存使用的dispatch_semaphore：優勢在於等待時不會消耗CPU資源

簡單的科普就到這，現在來開始源碼的探索

_YYLinkedMap

@interface _YYLinkedMapNode : NSObject {
    @package
    __unsafe_unretained _YYLinkedMapNode *_prev; // retained by dic
    __unsafe_unretained _YYLinkedMapNode *_next; // retained by dic
    id _key;
    id _value;
    NSUInteger _cost;
    NSTimeInterval _time;
}
@end

_YYLinkedMapNode：鏈表的節點

• _prev、_next：分別表示指向上一個節點、下一個節點

• _key：緩存的key

• _value：緩存對象

• _cost：內存消耗

• _time：緩存時間

@interface _YYLinkedMap : NSObject {
    @package
    CFMutableDictionaryRef _dic; // do not set object directly
    NSUInteger _totalCost;
    NSUInteger _totalCount;
    _YYLinkedMapNode *_head; // MRU（最近最常使用算法）, do not change it directly
    _YYLinkedMapNode *_tail; // LRU（最近最少使用算法-清除較不常使用數據）, do not change it directly
    BOOL _releaseOnMainThread;
    BOOL _releaseAsynchronously;
}

_YYLinkedMap：鏈表

• _dic：用來保存節點

• _totalCost：總緩存開銷

• _head、_tail：頭節點、尾節點

• _releaseOnMainThread：是否在主線程釋放_YYLinkedMapNode

• _releaseAsynchronously：是否異步釋放_YYLinkedMapNode

雙向鏈表

• 插入節點到頭部

• 將除兩邊的節點移到頭部

• 移除除兩邊的節點

• 移除尾部節點

• 移除所有節點

看下移除所有節點的代碼：

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

這邊通過雙向鏈表來對數據進行操作，和NSDictionary實現了LRU淘汰算法。時間復雜度0（1），5種操作基本上都是對頭尾節點和鏈表節點的上一個節點和下一個節點進行操作，耐心看還是能簡單的，這邊就不分析了

YYMemoryCache

這邊介紹兩個主要的操作：添加緩存，查找緩存

添加緩存

- (void)setObject:(id)object forKey:(id)key withCost:(NSUInteger)cost {
    if (!key) return;
    if (!object) {
        // 緩存對象為nil，直接移除
        [self removeObjectForKey:key];
        return;
    }
    // 為了保證線程安全，數據操作前進行加鎖
    pthread_mutex_lock(&_lock);
    // 查找緩存
    _YYLinkedMapNode *node = CFDictionaryGetValue(_lru->_dic, (__bridge const void *)(key));
    // 當前時間
    NSTimeInterval now = CACurrentMediaTime();
    if (node) {
        // 緩存對象已存在，更新數據，並移到棧頂
        _lru->_totalCost -= node->_cost;
        _lru->_totalCost += cost;
        node->_cost = cost;
        node->_time = now;
        node->_value = object;
        [_lru bringNodeToHead:node];
    } else {
        // 緩存對象不存在，添加數據，並移到棧頂
        node = [_YYLinkedMapNode new];
        node->_cost = cost;
        node->_time = now;
        node->_key = key;
        node->_value = object;
        [_lru insertNodeAtHead:node];
    }
    // 判斷當前的緩存進行是否超出了設定值，若超出則進行整理
    if (_lru->_totalCost > _costLimit) {
        dispatch_async(_queue, ^{
            [self trimToCost:_costLimit];
        });
    }
    // 每次添加數據僅有一個，數量上超出時，直接移除尾部那個object即可
    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);
}

異步線程釋放

裡面很多都用到類似的方法，將一個對象在異步線程中釋放，來分析下：

- p

1. 首先通過node來對其進行持有，以至於不會在方法調用結束的時候被銷毀

2. 我要要在其他線程中進行銷毀，所以將銷毀操作放在block中，block就會對其進行持有

3. 這邊在block中隨便調用了個方法，保證編譯器不會優化掉這個操作

4. 當block結束後，node沒有被持有的時候，就會在當前線程被release掉了

添加緩存

// 這邊從memory中取數據時，根據LRU原則，將最新取出的object放到棧頭
- (id)objectForKey:(id)key {
    if (!key) return nil;
    pthread_mutex_lock(&_lock);
    _YYLinkedMapNode *node = CFDictionaryGetValue(_lru->_dic, (__bridge const void *)(key));
    if (node) {
        node->_time = CACurrentMediaTime();
        [_lru bringNodeToHead:node];
    }
    pthread_mutex_unlock(&_lock);
    return node ? node->_value : nil;
}

YYKVStorage

該文件主要以兩種方式來實現磁盤存儲：SQLite、File，使用兩種方式混合進行存儲主要為了提高讀寫效率。寫入數據時，SQLite要比文件的方式更快；讀取數據的速度主要取決於文件的大小。據測試，在iPhone6中，當文件大小超過20kb時，File要比SQLite快的多。所以當大文件存儲時建議用File的方式，小文件更適合用SQLite。

下邊分別對Save、Remove、Get分別進行分析

Save

- (BOOL)saveItemWithKey:(NSString *)key value:(NSData *)value filename:(NSString *)filename extendedData:(NSData *)extendedData {
    // 條件不符合
    if (key.length == 0 || value.length == 0) return NO;
    if (_type == YYKVStorageTypeFile && filename.length == 0) {
        return NO;
    }
    if (filename.length) {    // filename存在 SQLite File兩種方式並行
        // 用文件進行存儲
        if (![self _fileWriteWithName:filename data:value]) {
            return NO;
        }
        // 用SQLite進行存儲
        if (![self _dbSaveWithKey:key value:value fileName:filename extendedData:extendedData]) {
            // 當使用SQLite方式存儲失敗時，刪除本地文件存儲
            [self _fileDeleteWithName:filename];
            return NO;
        }
        return YES;
    } else {               // filename不存在 SQLite
        if (_type != YYKVStorageTypeSQLite) {
            // 這邊去到filename後，刪除filename對應的file文件
            NSString *filename = [self _dbGetFilenameWithKey:key];
            if (filename) {
                [self _fileDeleteWithName:filename];
            }
        }
        // SQLite 進行存儲
        return [self _dbSaveWithKey:key value:value fileName:nil extendedData:extendedData];
    }
}

Remove

- (BOOL)removeItemForKey:(NSString *)key {
    if (key.length == 0) return NO;
    switch (_type) {
        case YYKVStorageTypeSQLite: {
            // 刪除SQLite文件
            return [self _dbDeleteItemWithKey:key];
        } break;
        case YYKVStorageTypeFile:
        case YYKVStorageTypeMixed: {
            // 獲取filename
            NSString *filename = [self _dbGetFilenameWithKey:key];
            if (filename) {
                // 刪除filename對的file
                [self _fileDeleteWithName:filename];
            }
            // 刪除SQLite文件
            return [self _dbDeleteItemWithKey:key];
        } break;
        default: return NO;
    }
}

Get

- (NSData *)getItemValueForKey:(NSString *)key {
    if (key.length == 0) return nil;
    NSData *value = nil;
    switch (_type) {
        case YYKVStorageTypeFile: { //File
            NSString *filename = [self _dbGetFilenameWithKey:key];
            if (filename) {
                // 根據filename獲取File
                value = [self _fileReadWithName:filename];
                if (!value) {
                    // 當value不存在，用對應的key刪除SQLite文件
                    [self _dbDeleteItemWithKey:key];
                    value = nil;
                }
            }
        } break;
        case YYKVStorageTypeSQLite: {
            // SQLite 方式獲取
            value = [self _dbGetValueWithKey:key];
        } break;
        case YYKVStorageTypeMixed: {
            NSString *filename = [self _dbGetFilenameWithKey:key];
            // filename 存在文件獲取，不存在SQLite方式獲取
            if (filename) {
                value = [self _fileReadWithName:filename];
                if (!value) {
                    [self _dbDeleteItemWithKey:key];
                    value = nil;
                }
            } else {
                value = [self _dbGetValueWithKey:key];
            }
        } break;
    }
    if (value) {
        // 更新文件操作時間
        [self _dbUpdateAccessTimeWithKey:key];
    }
    return value;
}

File方式主要使用的writeToFile進行存儲，SQLte直接使用的sqlite3來對文件進行操作，具體數據庫相關的操作這邊就不在進行分析了，感興趣的自己可以閱讀下

YYDiskCache

YYDiskCache是對YYKVStorage進行的一次封裝，是線程安全的，這邊使用的是dispatch_semaphore_signal來確保線程的安全。另外他結合LRU算法，根據文件的大小自動選擇存儲方式來達到更好的性能。

- (instancetype)initWithPath:(NSString *)path
             inlineThreshold:(NSUInteger)threshold {
    self = [super init];
    if (!self) return nil;
    // 獲取緩存的 YYDiskCache
    YYDiskCache *globalCache = _YYDiskCacheGetGlobal(path);
    if (globalCache) return globalCache;
    // 確定存儲的方式
    YYKVStorageType type;
    if (threshold == 0) {
        type = YYKVStorageTypeFile;
    } else if (threshold == NSUIntegerMax) {
        type = YYKVStorageTypeSQLite;
    } else {
        type = YYKVStorageTypeMixed;
    }
    // 初始化 YYKVStorage
    YYKVStorage *kv = [[YYKVStorage alloc] initWithPath:path type:type];
    if (!kv) return nil;
    // 初始化數據
    _kv = kv;
    _path = path;
    _lock = dispatch_semaphore_create(1);
    _queue = dispatch_queue_create("com.ibireme.cache.disk", DISPATCH_QUEUE_CONCURRENT);
    _inlineThreshold = threshold;
    _countLimit = NSUIntegerMax;
    _costLimit = NSUIntegerMax;
    _ageLimit = DBL_MAX;
    _freeDiskSpaceLimit = 0;
    _autoTrimInterval = 60;
    // 遞歸的去整理文件
    [self _trimRecursively];
    // 對當前對象進行緩存
    _YYDiskCacheSetGlobal(self);
    // 通知 APP即將被殺死時
    [[NSNotificationCenter defaultCenter] addObserver:self selector:@selector(_appWillBeTerminated) name:UIApplicationWillTerminateNotification object:nil];
    return self;
}

其他的一些操作基本上都是對YYKVStorage的一些封裝，這邊就不一一分析了。

參考文獻

http://blog.ibireme.com/2015/10/26/yycache/

http://blog.csdn.net/yunhua_lee/article/details/7599671