1.前言

• NSCache是苹果提供的一个用于内存缓存的工具；我们可以看到一些优秀的三方框架（例如：SDWebImage）也会用到这个类；
• 通过阅读GNU的源码，了解到它内部是有用到LRU、LFU这些淘汰算法来处理当内存达到设定的阀值的时候去自动淘汰掉数据

补充2个概念

• LRU

Least Recently Used的缩写，即最近最少使用，是一种常用的数据置换算法，选择最近最久未使用的数据予以淘汰

• LFU

Least Frequently Used,最不经常使用策略,在一段时间内,数据被使用频次最少的,优先被淘汰

本文就跟大家一起通过源码和例子来学习内部是如何实现的；GNU的源码实现不一定就是Foundation中的真实实现，不过还是有学习的参考价值的

2.基本使用

2.1 我们设置一个countLimit为5的cache，查看当元素超过限制之后的表现

@interface NSCacheTest () <NSCacheDelegate>

@property (nonatomic, strong) NSCache *memoryCache;

@end

@implementation NSCacheTest

- (instancetype)init {
    self = [super init];
    if (self) {
        _memoryCache = [[NSCache alloc] init];
        _memoryCache.countLimit = 5;
        _memoryCache.totalCostLimit = 1024;
        _memoryCache.delegate = self;
    }
    
    return self;
}

- (void)test {
    [self testOverlimit];
}

#pragma mark - NSCacheDelegate
- (void)cache:(NSCache *)cache willEvictObject:(id)obj {
    // 我们设置了代理，当有对象要被淘汰掉的时候就会触发该代理函数，通过打印我们来看数据是怎么被淘汰的
    NSLog(@"willEvictObject = %@", obj);
}

#pragma mark - Private Method

- (void)testOverlimit {
    NSInteger loopCount = 10;
    for (NSInteger i = 0; i < loopCount; i++) {
        NSString *urlString = [NSString stringWithFormat:@"https://www.test.%ld", (long)i];
        NSURL *obj = [NSURL URLWithString:urlString];
        [self.memoryCache setObject:obj forKey:@(i).stringValue];
    }
    
    // loopCount == 10的时候当执行之后会输出：
    // RuntimeLearning[19309:858051] willEvictObject = https://www.test.0
    // RuntimeLearning[19309:858051] willEvictObject = https://www.test.1
    // RuntimeLearning[19309:858051] willEvictObject = https://www.test.2
    // RuntimeLearning[19309:858051] willEvictObject = https://www.test.3
    // RuntimeLearning[19309:858051] willEvictObject = https://www.test.4
    // 可以看到先加入cache的元素被移除了
    [self logAllCachedData];
    /*
     RuntimeLearning[19858:902352] (
         "https://www.test.5",
         "https://www.test.6",
         "https://www.test.7",
         "https://www.test.8",
         "https://www.test.9"
     )
     */
    // 清除数据
    [self.memoryCache removeAllObjects];
}

• 我们设置了代理_memoryCache.delegate = self，当有对象要被淘汰掉的时候就会触发代理函数- (void)cache:(NSCache *)cache willEvictObject:(id)obj，通过打印我们来看数据是怎么被淘汰的
• 我们发现当cache中添加的元素个数大于countLimit的时候，就会淘汰掉数据；并且看到是先加入的数据先被淘汰了，输出结果可参照代码中的打印信息，有点那个先进先出的意思

2.2 真机调试时app切换到后台看看表现

• 打个符号断点

  
  
  图片.png

• app切换到后台

  
  
  图片.png
  
  

  看到退到后台之后，cache清空了数据

3.LRU

优先淘汰最近最久未使用的

// 最近未使用原则
- (void)checkIfHasLRU {
    NSInteger loopCount = 5;
    for (NSInteger i = 0; i < loopCount; i++) {
        NSString *urlString = [NSString stringWithFormat:@"https://www.test.%ld", (long)i];
        NSURL *obj = [NSURL URLWithString:urlString];
        [self.memoryCache setObject:obj forKey:@(i).stringValue];
    }
    [self.memoryCache objectForKey:@"0"];
    [self.memoryCache objectForKey:@"3"];
    [self logAllCachedData];
    NSString *urlString = @"https://www.test.6";
    NSURL *obj = [NSURL URLWithString:urlString];
    [self.memoryCache setObject:obj forKey:@"6"];
    // RuntimeLearning[19541:877142] willEvictObject = https://www.test.1
    NSString *urlString1 = @"https://www.test.7";
    NSURL *obj1 = [NSURL URLWithString:urlString1];
    [self.memoryCache setObject:obj1 forKey:@"7"];
    // RuntimeLearning[19541:877142] willEvictObject = https://www.test.2
    // RuntimeLearning[19541:877142] willEvictObject = https://www.test.2
    NSString *urlString2 = @"https://www.test.8";
    NSURL *obj2 = [NSURL URLWithString:urlString2];
    [self.memoryCache setObject:obj2 forKey:@"8"];
    // RuntimeLearning[19541:877142] willEvictObject = https://www.test.4
    // 清除数据
    [self.memoryCache removeAllObjects];
}

• 我们通过调用objectForKey来使用cache中的数据；这样本来最先插入的key为0的数据就不是最近未使用的了

[self.memoryCache objectForKey:@"0"];
[self.memoryCache objectForKey:@"3"];

• 此时我们向cache中加入数据，发现跟一开始打印的不一样，key为0的没有被淘汰，而是key为1的数据被淘汰了

NSString *urlString = @"https://www.test.6";
NSURL *obj = [NSURL URLWithString:urlString];
[self.memoryCache setObject:obj forKey:@"6"];
//输出： RuntimeLearning[19541:877142] willEvictObject = https://www.test.1

4.LFU

最不经常使用淘汰策略

// 最不经常使用原则
- (void)checkIfHasLFU {
    NSInteger loopCount = 5;
    for (NSInteger i = 0; i < loopCount; i++) {
        NSString *urlString = [NSString stringWithFormat:@"https://www.test.%ld", (long)i];
        NSURL *obj = [NSURL URLWithString:urlString];
        [self.memoryCache setObject:obj forKey:@(i).stringValue];
    }
    [self.memoryCache objectForKey:@"1"];
    [self.memoryCache objectForKey:@"1"];
    [self.memoryCache objectForKey:@"3"];
    [self.memoryCache objectForKey:@"3"];
    [self.memoryCache objectForKey:@"4"];
    [self.memoryCache objectForKey:@"0"];
    [self logAllCachedData];
    /*
     RuntimeLearning[19795:898814] (
         "https://www.test.2",
         "https://www.test.0",
         "https://www.test.3",
         "https://www.test.1",
         "https://www.test.4"
     )
     */
    NSString *urlString = @"https://www.test.6";
    NSURL *obj = [NSURL URLWithString:urlString];
    [self.memoryCache setObject:obj forKey:@"6"];
    // RuntimeLearning[19628:885142] willEvictObject = https://www.test.2
    NSString *urlString1 = @"https://www.test.7";
    NSURL *obj1 = [NSURL URLWithString:urlString1];
    [self.memoryCache setObject:obj1 forKey:@"7"];
    // RuntimeLearning[19628:885142] willEvictObject = https://www.test.4
    NSString *urlString2 = @"https://www.test.8";
    NSURL *obj2 = [NSURL URLWithString:urlString2];
    [self.memoryCache setObject:obj2 forKey:@"8"];
    // RuntimeLearning[19628:885142] willEvictObject = https://www.test.0
    NSString *urlString3 = @"https://www.test.9";
    NSURL *obj3 = [NSURL URLWithString:urlString3];
    [self.memoryCache setObject:obj3 forKey:@"9"];
    // RuntimeLearning[19628:885142] willEvictObject = https://www.test.6
    // 这里看起来好像使用频次的优先级会高于最近使用
}

• 我们通过控制调用objectForKey的次数，来实现元素的使用次数的不同，这里key为1、3的使用次数为2，key为4、0的使用次数为1

[self.memoryCache objectForKey:@"1"];
[self.memoryCache objectForKey:@"1"];
[self.memoryCache objectForKey:@"3"];
[self.memoryCache objectForKey:@"3"];
[self.memoryCache objectForKey:@"4"];
[self.memoryCache objectForKey:@"0"];

• 此时向cache中添加元素，看淘汰的现象；可以看到key为2没有使用它最先被淘汰了，其次开始淘汰了使用一次的key为4、0的

    NSString *urlString = @"https://www.test.6";
    NSURL *obj = [NSURL URLWithString:urlString];
    [self.memoryCache setObject:obj forKey:@"6"];
    // RuntimeLearning[19628:885142] willEvictObject = https://www.test.2
    NSString *urlString1 = @"https://www.test.7";
    NSURL *obj1 = [NSURL URLWithString:urlString1];
    [self.memoryCache setObject:obj1 forKey:@"7"];
    // RuntimeLearning[19628:885142] willEvictObject = https://www.test.4
    NSString *urlString2 = @"https://www.test.8";
    NSURL *obj2 = [NSURL URLWithString:urlString2];
    [self.memoryCache setObject:obj2 forKey:@"8"];
    // RuntimeLearning[19628:885142] willEvictObject = https://www.test.0

• 至此继续添加元素，本来以为是会把使用次数为2的元素淘汰，结果发现是新加入的元素被淘汰了；这里看起来使用频次高的数据优先级会高于最近未使用的

    NSString *urlString3 = @"https://www.test.9";
    NSURL *obj3 = [NSURL URLWithString:urlString3];
    [self.memoryCache setObject:obj3 forKey:@"9"];
    // RuntimeLearning[19628:885142] willEvictObject = https://www.test.6
    // 这里看起来好像使用频次的优先级会高于最近使用

5. GNU源码分析

被缓存的对象内部结构
我们缓存对象的时候，内部会封装成一个_GSCachedObject的对象，记录了对象的大小、key、使用次数等信息

/**
 * _GSCachedObject is effectively used as a structure containing the various
 * things that need to be associated with objects stored in an NSCache.  It is
 * an NSObject subclass so that it can be used with OpenStep collection
 * classes.
 */
@interface _GSCachedObject : NSObject
{
    // 内部存储的数据结构
@public
    id object; // 缓存的对象
    NSString *key; // 缓存的对象的key
    int accessCount; // 实现LFU 全称是:Least Frequently Used,最不经常使用策略,在一段时间内,数据被使用频次最少的,优先被淘汰
    NSUInteger cost; // 对象的大小
    BOOL isEvictable; // 对象能否被收回
}
@end

• int accessCount实现LFU ，当我们通过objectForKey访问某个key对于的数据时，这个值会++

如何实现LRU

• 初始化的时候，内部会初始化一个可变数组_accesses

- (id) init
{
    if (nil == (self = [super init]))
    {
        return nil;
    }
    ASSIGN(_objects,[NSMapTable strongToStrongObjectsMapTable]);
    _accesses = [NSMutableArray new]; // 实现LRU；每次添加新的都放到数组的尾部，当需要删除的时候从头开始遍历，当使用了对象的时候[objectForKey：]则先将数据删除再添加到数组的尾部;
    return self;
}

• 当调用objectForKey的时候，这个时候元素的使用状态就变化了；这里的做法就是把用到的元素从_accesses中移除，然后在添加到数组的尾部；同时可以看到这里也对缓存对象的accessCount和一个记录总使用次数的_totalAccesses做了++操作；

- (id) objectForKey: (id)key
{
    _GSCachedObject *obj = [_objects objectForKey: key];
    
    if (nil == obj)
    {
        return nil;
    }
    if (obj->isEvictable)
    {
        // Move the object to the end of the access list.
        [_accesses removeObjectIdenticalTo: obj];
        [_accesses addObject: obj];
    }
    obj->accessCount++;
    _totalAccesses++;
    return obj->object;
}

• 当我们向缓存中增加数据的时候，如果超过限制了就会触发淘汰数据的方法

- (void) setObject: (id)obj forKey: (id)key cost: (NSUInteger)num
{
    _GSCachedObject *oldObject = [_objects objectForKey: key];
    _GSCachedObject *newObject;
    
    if (nil != oldObject)
    {
        [self removeObjectForKey: oldObject->key];
    }
    [self _evictObjectsToMakeSpaceForObjectWithCost: num];
    newObject = [_GSCachedObject new];
    // Retained here, released when obj is dealloc'd
    newObject->object = RETAIN(obj);
    newObject->key = RETAIN(key);
    newObject->cost = num;
    if ([obj conformsToProtocol: @protocol(NSDiscardableContent)])
    {
        newObject->isEvictable = YES;
        [_accesses addObject: newObject];
    }
    [_objects setObject: newObject forKey: key];
    RELEASE(newObject);
    _totalCost += num;
}

可以看到做数据淘汰的关键函数就是_evictObjectsToMakeSpaceForObjectWithCost

- (void)_evictObjectsToMakeSpaceForObjectWithCost: (NSUInteger)cost
{
    NSUInteger spaceNeeded = 0;
    NSUInteger count = [_objects count];
    // 判断是否需要释放空间【超过了内存限制】
    if (_costLimit > 0 && _totalCost + cost > _costLimit)
    {
        spaceNeeded = _totalCost + cost - _costLimit;
    }
    
    // Only evict if we need the space. 当个数超出限制或者空间超限制的时候就需要需释放
    if (count > 0 && (spaceNeeded > 0 || count >= _countLimit))
    {
        NSMutableArray *evictedKeys = nil;
        // Round up slightly.
        NSUInteger averageAccesses = (_totalAccesses / count * 0.2) + 1; // 计算平均使用次数，用于LFU规则
        NSEnumerator *e = [_accesses objectEnumerator];
        _GSCachedObject *obj;
        
        if (_evictsObjectsWithDiscardedContent)
        {
            evictedKeys = [[NSMutableArray alloc] init];
        }
        while (nil != (obj = [e nextObject]))
        {
            // Don't evict frequently accessed objects.不频繁使用并且没有标记为可收回
            if (obj->accessCount < averageAccesses && obj->isEvictable)
            {
                [obj->object discardContentIfPossible];
                if ([obj->object isContentDiscarded])
                {
                    NSUInteger cost = obj->cost;
                    
                    // Evicted objects have no cost.
                    obj->cost = 0;
                    // Don't try evicting this again in future; it's gone already.
                    obj->isEvictable = NO;
                    // Remove this object as well as its contents if required
                    if (_evictsObjectsWithDiscardedContent)
                    {
                        [evictedKeys addObject: obj->key];
                    }
                    _totalCost -= cost;
                    // If we've freed enough space, give up;当满足空间需要之后就退出循环
                    if (cost > spaceNeeded)
                    {
                        break;
                    }
                    spaceNeeded -= cost;
                }
            }
        }
        // Evict all of the objects whose content we have discarded if required
        if (_evictsObjectsWithDiscardedContent)
        {
            NSString *key;
            
            e = [evictedKeys objectEnumerator];
            while (nil != (key = [e nextObject]))
            {
                [self removeObjectForKey: key];
            }
        }
        [evictedKeys release];
    }
}

其中遍历的时候用的是NSEnumerator *e = [_accesses objectEnumerator]，上面我们分析了由于新访问的数据会被加到数组的尾部，那么在淘汰的时候从前到后遍历，淘汰的数据就是越久远未被使用的数据了，那么就实现了LRU

如何实现LFU

• 被缓存对象的accessCount记录了对象被访问的次数
• _totalAccess记录了缓存的对象的总访问次数

分析_evictObjectsToMakeSpaceForObjectWithCost函数发现有个
平均使用次数averageAccesses；定义如下：

NSUInteger averageAccesses = (_totalAccesses / count * 0.2) + 1; // 计算平均使用次数，用于LFU规则

那么就很清晰了，内部得到平均使用次数，然后拿对象的使用次数跟这个平均值做比较，就能达到优先淘汰使用不频繁的数据了；代码实现如下：

while (nil != (obj = [e nextObject]))
{
            // Don't evict frequently accessed objects.不频繁使用并且没有标记为可收回
            if (obj->accessCount < averageAccesses && obj->isEvictable)
            {
            }
}

到这里我们基本学习了代码的整体实现了。

6. 总结

• GNU的源码可以发现，他实现LRU用的是数组，当然也可以使用链表；可以参照YYMemoryCache的实现
• NSCache内部是没有做收到内存警告就清除数据的逻辑；我们看SDWebImage内部内存缓存也用的NSCache，但加了个收到内存警告的通知；处理内存警告的时候移除掉内存缓存的内容
• NSCache主要是做内存缓存，假如做多级缓存比如：内存+本地的方式，当内存警告时，如果移除了内存中的数据，那么下次读缓存的时候，就会触发磁盘读数据了；关于这一点的优化也可以参照SDWebImage的weakCache。

7.参考

GNU NSCache源码