1.簡介

LRU （英文：Least Recently Used）, 意為最近最少使用闷板，這個算法的精髓在于如果一塊數(shù)據(jù)最近被訪問技扼，那么它將來被訪問的幾率也很高铸本，根據(jù)數(shù)據(jù)的歷史訪問來淘汰長時間未使用的數(shù)據(jù)硕糊。

這篇文章主要分享一下關(guān)于內(nèi)存緩存在iOS 中運用峦嗤，主要分析一下第三方框架中LRU的運用蕊唐，包括 Lottie 和 YYCache.

2.算法實現(xiàn)

緩存淘汰算法

1.新添加的數(shù)據(jù)放在頭部 2.被訪問到的數(shù)據(jù)放在頭部3.超過最大緩存量的數(shù)據(jù)將被移除。

3.運用

1.Lottie

Lottie

LOTAnimationCache 這個類是LRU的最簡單的使用烁设，主要是緩存動畫，分別看一下 .h .m 文件的實現(xiàn)。

/// Global Cache 單例類
+ (instancetype)sharedCache;

/// Adds animation to the cache  主要添加對象API
- (void)addAnimation:(LOTComposition *)animation forKey:(NSString *)key;

/// Returns animation from cache.  獲取緩存
- (LOTComposition * _Nullable)animationForKey:(NSString *)key;

/// Removes a specific animation from the cache 移除緩存
- (void)removeAnimationForKey:(NSString *)key;

/// Clears Everything from the Cache 清除緩存
- (void)clearCache;

/// Disables Caching Animation Model Objects 銷毀緩存模型
- (void)disableCaching;

通過上面主要接口的API,我們可以發(fā)現(xiàn) 一個緩存類的實現(xiàn)無非以上這幾個接口装黑，主要實現(xiàn)起來也特別簡單副瀑。

//首先這是定義一個最大的緩存數(shù)量
static const NSInteger kLOTCacheSize = 50;

//類實現(xiàn)中主要維護(hù)兩張表，字典通過key-value pair存儲動畫,用數(shù)組存儲key
@implementation LOTAnimationCache {
  NSMutableDictionary *animationsCache_;// 儲存動畫
  NSMutableArray *lruOrderArray_; //保存key
}
//單例的實現(xiàn)恋谭，會iOS 的都會寫
+ (instancetype)sharedCache {
  static LOTAnimationCache *sharedCache = nil;
  static dispatch_once_t onceToken;
  dispatch_once(&onceToken, ^{
    sharedCache = [[self alloc] init];
  });
  return sharedCache;
}
//本類初始化的時候糠睡，初始化數(shù)組和字典
- (instancetype)init {
  self = [super init];
  if (self) {
    animationsCache_ = [[NSMutableDictionary alloc] init];
    lruOrderArray_ = [[NSMutableArray alloc] init];
  }
  return self;
}
//這是最主要的方法
- (void)addAnimation:(LOTComposition *)animation forKey:(NSString *)key{
//清除超過最大緩存量的值
 if (lruOrderArray_.count >= kLOTCacheSize) {
        //數(shù)組第一個key就是最早存入數(shù)組
        NSString *oldKey = lruOrderArray_.firstObject;
       //移除舊key
        [lruOrderArray_ removeObject:oldKey];
       //移除值
        [animationsCache_ removeObjectForKey:oldKey];
    }
    //移除舊key
    [lruOrderArray_ removeObject:key];
    //添加新key
    [lruOrderArray_ addObject:key];
    //存儲值
    [animationsCache_ setObject:animation forKey:key];
}
//通過key 獲取 value
- (LOTComposition *)animationForKey:(NSString *)key {
  if (!key) {
    return nil;
  }
//從 字典中獲取 value
  LOTComposition *animation = [animationsCache_ objectForKey:key];
//更新數(shù)組key
  [lruOrderArray_ removeObject:key];
  [lruOrderArray_ addObject:key];
  return animation;
}
//清除緩存 ，一般在收到內(nèi)存警告的時候執(zhí)行此操作疚颊，也是一個緩存類必須提供的接口
- (void)clearCache {
  [animationsCache_ removeAllObjects];
  [lruOrderArray_ removeAllObjects];
}
// 移除對應(yīng)key 的緩存
- (void)removeAnimationForKey:(NSString *)key {
  [lruOrderArray_ removeObject:key];
  [animationsCache_ removeObjectForKey:key];
}
// 銷毀整個緩存
- (void)disableCaching {
  [self clearCache];
  animationsCache_ = nil;
  lruOrderArray_ = nil;
}

Lottie 可能是我遇到最簡單的緩存類了狈孔，也是最容易入門LRU的緩存類,實現(xiàn)起來也是很容易的。

2.YYCache
YYCache 中主要使用雙向鏈表來實現(xiàn)內(nèi)存緩存材义，主要分析一下主要實現(xiàn)思路均抽，首先看一下簡介

 YYMemoryCache is a fast in-memory cache that stores key-value pairs.
 In contrast to NSDictionary, keys are retained and not copied.
 The API and performance is similar to `NSCache`, all methods are thread-safe.

YYMemoryCache 是一個用來key-value 鍵值對。
與NSDictionary 形成對比的的是keys 會被持有 但是不會被拷貝其掂。
API 和性能類似于NSCache油挥，所有的方法都是線程安全的。

 YYMemoryCache objects differ from NSCache in a few ways:
 
 * It uses LRU (least-recently-used) to remove objects; NSCache's eviction method
   is non-deterministic.
 * It can be controlled by cost, count and age; NSCache's limits are imprecise.
 * It can be configured to automatically evict objects when receive memory 
   warning or app enter background.
 
 The time of `Access Methods` in YYMemoryCache is typically in constant time (O(1)).

YYMemoryCache 有以下幾點不同于NSCache：
1.使用LRU(最近最少使用) 來移除對象款熬， NSCache 是不確定的
2.可以被 數(shù)量深寥，消耗 和日期來控制，NSCache 是不明確的
3.當(dāng)收到內(nèi)存警告或者進(jìn)入后臺的時候自動配置來移除對象贤牛。

4. YYMemoryCache `Access Methods 時間復(fù)雜度是O(1).

主要的方法

#pragma mark - Access Methods

/**
 Returns a Boolean value that indicates whether a given key is in cache.
 */
//判斷cache 中是否包含key
- (BOOL)containsObjectForKey:(id)key;

/**
 Returns the value associated with a given key.
 */
//返回給定的key 對用的值
- (nullable id)objectForKey:(id)key;

/**
 Sets the value of the specified key in the cache (0 cost).
 */
//賦值 key-value  0消耗
- (void)setObject:(nullable id)object forKey:(id)key;

/**
 Sets the value of the specified key in the cache, and associates the key-value 
 pair with the specified cost.
 */
//賦值 key-value  cost消耗
- (void)setObject:(nullable id)object forKey:(id)key withCost:(NSUInteger)cost;

/**
 Removes the value of the specified key in the cache.
 */
// 移除指定key 對應(yīng)的值
- (void)removeObjectForKey:(id)key;

/**
 Empties the cache immediately.
 */
//移除所有的值
- (void)removeAllObjects;

// 淘汰算法
#pragma mark - Trim
/**
 Removes objects from the cache with LRU, until the `totalCount` is below or equal to
 the specified value.
 */
//對count 數(shù)量 移除緩存
- (void)trimToCount:(NSUInteger)count;

/**
 Removes objects from the cache with LRU, until the `totalCost` is or equal to
 */
//對cost  移除緩存
- (void)trimToCost:(NSUInteger)cost;

/**
 Removes objects from the cache with LRU, until all expiry objects removed by the
 specified value.
 */
// 對age(緩存時間) 移除緩存
- (void)trimToAge:(NSTimeInterval)age;

首先看一下底層鏈表的實現(xiàn):
1.定義一個節(jié)點類
主要包括 前后節(jié)點指針惋鹅，key 和 value 以及_cost _time

@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

@implementation _YYLinkedMapNode

- (void)dealloc{
  
    printf("本類_YYLinkedMapNode已經(jīng)釋放掉了");
}
@end

_YYLinkedMap

接下來看一下雙向鏈表的實現(xiàn),
主要包括一個字典負(fù)責(zé)存儲，頭結(jié)點和尾節(jié)點殉簸，總消耗和總數(shù)量

@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
}

/// Insert a node at head and update the total cost.
// 插入一個節(jié)點到頭結(jié)點
- (void)insertNodeAtHead:(_YYLinkedMapNode *)node;

/// Bring a inner node to header.
//將內(nèi)部的一個節(jié)點放到頭部
- (void)bringNodeToHead:(_YYLinkedMapNode *)node;

/// Remove a inner node and update the total cost.
// 移除一個節(jié)點并更新總數(shù)
- (void)removeNode:(_YYLinkedMapNode *)node;

/// Remove tail node if exist.
//如果存在尾節(jié)點 移除
- (_YYLinkedMapNode *)removeTailNode;

/// Remove all node in background queue.
//移除所有
- (void)removeAll;

@end

初始化一個鏈表,初始化的時候創(chuàng)建一個字典

@implementation _YYLinkedMap

- (instancetype)init {
    self = [super init];
    
  //初始化一個字典
    _dic = CFDictionaryCreateMutable(CFAllocatorGetDefault(), 0, &kCFTypeDictionaryKeyCallBacks, &kCFTypeDictionaryValueCallBacks);
 
    return self;
}
- (void)dealloc {
    CFRelease(_dic);
}

插入一個節(jié)點到頭部
這個方法等同于第一步 => 添加新數(shù)據(jù)

- (void)insertNodeAtHead:(_YYLinkedMapNode *)node{
//存入字典表中
  CFDictionarySetValue(_dic, (__bridge const void *)(node->_key), (__bridge const void *)(node->_value));
如果存在則將當(dāng)前node 的置為首位负饲，不存在的話，初始化
    if (_head) {
        node->_next = _head;
        _head->_prev = node;
        _head = node;
    }
    else {
        _head = _tail = node;
    }
}

將任意一個節(jié)點添加到頭部
這個方法等同于第二步 => 被訪問的數(shù)據(jù)移到頭部

- (void)bringNodeToHead:(_YYLinkedMapNode *)node {
    if (_head == node) return; // 如果本身是 head ,return 
    //如果是尾節(jié)點喂链，重新賦值尾節(jié)點
    if (_tail == node) {
        _tail = node->_prev;
        _tail->_next = nil;
    } else {
//如果是中間的節(jié)點返十，重新賦值 prev next 指針
        node->_next->_prev = node->_prev;
        node->_prev->_next = node->_next;
    }
//將拿到的節(jié)點添加到頭部
    node->_next = _head;
    node->_prev = nil;
    _head->_prev = node;
    _head = node;
}

移除一個節(jié)點
用于緩存淘汰算法

- (void)removeNode:(_YYLinkedMapNode *)node {
    CFDictionaryRemoveValue(_dic, (__bridge const void *)(node->_key));
    _totalCost -= node->_cost;
    _totalCount--;
   // 源碼的作者這一段寫的是精華中的精華代碼，思路嚴(yán)謹(jǐn)椭微，也是體現(xiàn)使用__unsafe_unretained精華所在洞坑，執(zhí)行效率很高，各位可以好好體會
    if (node->_next) node->_next->_prev = node->_prev;
    if (node->_prev) node->_prev->_next = node->_next;
    if (_head == node) _head = node->_next;
    if (_tail == node) _tail = node->_prev;
}

移除尾部節(jié)點并返回這個節(jié)點蝇率，這是很多第三方接口設(shè)計之精華

- (_YYLinkedMapNode *)removeTailNode {
    if (!_tail) return nil;
    _YYLinkedMapNode *tail = _tail;
    CFDictionaryRemoveValue(_dic, (__bridge const void *)(_tail->_key));
    _totalCost -= _tail->_cost;
    _totalCount--;
   // 如果只有一個節(jié)點 迟杂，直接nil
    if (_head == _tail) {
        _head = _tail = nil;
    } else {
        _tail = _tail->_prev;
        _tail->_next = nil;
    }
    return tail;
}

移除所有節(jié)點

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

接下面看一下緩存淘汰的一些算法
包括 Cost Count Age 這三種Limit 來淘汰緩存

- (void)_trimToCost:(NSUInteger)costLimit{
// 判斷臨界條件 costLimit = 0 全部移除
// 如果 <= 什么也不需要做
 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;
    
    //這里采用while 循環(huán)的方式移除尾節(jié)點排拷，直至滿足條件
    //這里有一個小技巧是，將移除的節(jié)點添加到一個數(shù)組中锅尘，然后在子線程釋放
    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)_trimToAge:(NSTimeInterval)ageLimit
- (void)_trimToCount:(NSUInteger)countLimit

接下來看一下YYMemoryCache 主要的緩存API 接口的實現(xiàn)布蔗，主要是基于底層鏈表的實現(xiàn)

存儲方法key - value pair

- (void)setObject:(id)object forKey:(id)key withCost:(NSUInteger)cost {
    //容錯判斷
    if (!key) return;
    if (!object) {
        [self removeObjectForKey:key];
        return;
    }
    
    pthread_mutex_lock(&_lock);
// 拿到一個節(jié)點
    _YYLinkedMapNode *node = CFDictionaryGetValue(_lru->_dic, (__bridge const void *)(key));
    NSTimeInterval now = CACurrentMediaTime();
    if (node) {
  //節(jié)點存在
        _lru->_totalCost -= node->_cost;
        _lru->_totalCost += cost;
        node->_cost = cost;
        node->_time = now;
        node->_value = object;
        [_lru bringNodeToHead:node];
    } else {
        // 節(jié)點不存在 -> 直接添加到頭部
        node = [_YYLinkedMapNode new];
        node->_cost = cost;
        node->_time = now;
        node->_key = key;
        node->_value = object;
        [_lru insertNodeAtHead:node];
    }
   //做一次數(shù)據(jù)的剪枝
  // 超過最大容量，清理內(nèi)存
    if (_lru->_totalCost > _costLimit) {
        dispatch_async(_queue, ^{
            [self trimToCost:_costLimit];
        });
    }
 // 超過最大數(shù)量浪腐，清理內(nèi)存
 // 小技巧同樣是異步釋放內(nèi)存
    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);
}

接下來是獲取值

- (id)objectForKey:(id)key {
    if (!key) return nil;
    pthread_mutex_lock(&_lock);
    _YYLinkedMapNode *node = CFDictionaryGetValue(_lru->_dic, (__bridge const void *)(key));
   //獲取到該節(jié)點更新時間 并放置于鏈表的頭部
    if (node) {
        node->_time = CACurrentMediaTime();
        [_lru bringNodeToHead:node];
    }
    pthread_mutex_unlock(&_lock);
    return node ? node->_value : nil;
}

移除key 對應(yīng)的 value

- (void)removeObjectForKey:(id)key {
    if (!key) return;
    pthread_mutex_lock(&_lock);
 //思路跟上面一樣
    _YYLinkedMapNode *node = CFDictionaryGetValue(_lru->_dic, (__bridge const void *)(key));
    if (node) {
        [_lru removeNode:node];
        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);
}

移除所有的數(shù)據(jù)

- (void)removeAllObjects {
    pthread_mutex_lock(&_lock);
    [_lru removeAll];
    pthread_mutex_unlock(&_lock);
}

以上是YYMemoryCache 利用 LRU 緩存淘汰算法實現(xiàn)的內(nèi)存緩存纵揍，當(dāng)然源碼作者使用了很多方法來處理性能，例如在YYMemoryCache 在初始的時候议街，便開始5s遞歸剪枝泽谨，存儲的時候也檢查變量進(jìn)行剪枝，個人認(rèn)為在存儲的時候可以不用特漩，這方面也可提升性能吧雹，沒必要頻繁的去剪枝緩存淘汰數(shù)據(jù)。
在YYDiskCache 存儲中也使用了LRU緩存淘汰算法涂身，基本的原理和實現(xiàn)都是一樣的雄卷，YYDiskCache 主要是使用 SQLite 和 File System來進(jìn)行緩存，后面有時間也可以和大家分享一下访得。