大数据

YYKit源码分析之YYCache

标题

最近YYKit在IOS各大论坛讨论得火热,其代码简单、高效令人惊叹。我也凑凑热闹,抱着学习为目的的心态解析下ibireme的代码。这里从比较简单的YYCache开始入手,下面是该目录结构。

YYCache目录结构

YYCache


  • github地址:https://github.com/ibireme/YYCache

  • YYCache是用于Objective-C中用于缓存的第三方框架。

  • YYMemoryCache:内存缓存,并且所有API都是线程安全的。

  • YYDiskCache:磁盘缓存,主要用SQLite和文件存储,并且所有API都是线程安全的

  • LRU算法:Least recently used,最近最少使用

LRU算法


在YYCache的YYMemoryCacheYYDiskCache中都采用LRU算法进行快速存取,主要是通过双向链表NSMutableDictionry来实现。下面这张图很好诠释了LRU算法。

LRU算法原理
  • 用双向链表来表示堆栈
  • 新加入的数据存在栈顶
  • 使用缓存的时候,从栈中查找,如果命中,就把数据移到栈顶
  • 可以设置栈最大长度,超过长度就把栈尾数据删除

通过以上的规则,一个简单的LRU算法就得以实现。

线程安全控制(锁)


分析YYCache的时候,我发现作者用了很多锁来保证线程安全。这是值得我学习的地方,因为以前我根本没有考虑过线程问题。

在这里YYCache主要用了2种锁:pthread_mutexdispatch_semaphore,下面是作者自己的分析:

OSSpinLock 自旋锁,性能最高的锁。原理很简单,就是一直 do while 忙等。它的缺点是当等待时会消耗大量 CPU 资源,所以它不适用于较长时间的任务。对于内存缓存的存取来说,它非常合适。

dispatch_semaphore 是信号量,但当信号总量设为 1 时也可以当作锁来。在没有等待情况出现时,它的性能比 pthread_mutex 还要高,但一旦有等待情况出现时,性能就会下降许多。相对于 OSSpinLock 来说,它的优势在于等待时不会消耗 CPU 资源。对磁盘缓存来说,它比较合适。

为此我也特地补了下课,pthread_mutex其实也是利用OSSpinLock实现的,还有其他的一些锁比如NSLock@synchronized,这些使用也很方便,网上资料也很多。我简单测试了下,OSSpinLock相对性能最高,@synchronized相对性能差些,具体的也可以自己实验一下。

线程安全就是说多线程访问同一代码,不会产生不确定的结果。如果在执行代码前加锁,只有等这段代码完成后才解锁,这样就不会出现因多线程而出现竞争资源等问题,从而实现线程安全。

双向链表结构


我们先来看下链表的节点,可以看出主要是上一个节点指针,下一个节点指针,key值value值,节点开销大小,缓存时间戳等部分

@interface _YYLinkedMapNode : NSObject {
    @package
    __unsafe_unretained _YYLinkedMapNode *_prev; // retained by dic 上一个节点
    __unsafe_unretained _YYLinkedMapNode *_next; // retained by dic 下一个节点
     id _key; //节点key值
     id _value; //节点value值
     NSUInteger _cost;//内存开销大小
     NSTimeInterval _time;//缓存时间
}

我们再来看下链表的结构,代码都添上了中文注释:

@interface _YYLinkedMap : NSObject {
        @package
         CFMutableDictionaryRef _dic; // 字典的Ref(理解成字典标示)
         NSUInteger _totalCost; //链表总开销
        NSUInteger _totalCount; //链表个数
         _YYLinkedMapNode *_head; // 链表首个节点指针
         _YYLinkedMapNode *_tail; // 链表末尾节点指针
         BOOL _releaseOnMainThread; //是否在主线程释放内存
         BOOL _releaseAsynchronously;//是否异步释放内存
    }

    /// 插入一个节点,并且更新链表总开销
    /// Node and node.key should not be nil.
    - (void)insertNodeAtHead:(_YYLinkedMapNode *)node;

    /// 将一个节点放到链表顶部
    /// Node should already inside the dic.
   - (void)bringNodeToHead:(_YYLinkedMapNode *)node;

    /// 移除一个节点
    /// Node should already inside the dic.
    - (void)removeNode:(_YYLinkedMapNode *)node;

    ///移除尾部节点,淘汰数据
    - (_YYLinkedMapNode *)removeTailNode;

    /// 移除所有节点
    - (void)removeAll;

    @end

下面这张图很好得解释了整个链表结构,如果有数据结构基础读懂这个双向链表应该很容易。

链表结构

YYMemoryCache


由于代码还是比较简单的,所以我打算用在源码上注释的方式解释,也就不画流程图了。

添加数据

 - (void)setObject:(id)object forKey:(id)key withCost:(NSUInteger)cost {
    if (!key) return;
    if (!object) {
        [self removeObjectForKey:key];
        return;
    }

       //这里开始加锁
       pthread_mutex_lock(&_lock);

        //这句话代码其实就是相当于 NSMutableDictionary objecyForKey,取出链表节点,这个NSMutableDictionary里面装的是<_YYLinkedMapNode *>
        _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];
            });
        }
            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));

        if (node) {
        //如果存在就取出,并把节点添加到链表头部
        node->_time = CACurrentMediaTime();
           [_lru bringNodeToHead:node];
        }
        //解锁
        pthread_mutex_unlock(&_lock);
        //没有返回Nil
    return node ? node->_value : nil;
}

定时清理

这里就是区别普通NSDictionary缓存的地方之一,不断在后台更新缓存数据,清理过去数据,只要设置一个_autoTrimInterval时间间隔就好。

- (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];
            [self _trimRecursively];
        });
    }

- (void)_trimInBackground {
        dispatch_async(_queue, ^{
            //清理直到达到大小限制
           [self _trimToCost:self->_costLimit];
           //清理直到达到个数限制
            [self _trimToCount:self->_countLimit];
            //清理直到达到时间限制
            [self _trimToAge:self->_ageLimit];
        });
    }

YYKVStorage


要解析YYDiskCache首先得解析YYKVStorage,我发现这里主要用了2种存储方式,sqlLite文件存储。一开始并不明白为何这么做,后来参考网上资料:

该文件主要以两种方式来实现磁盘存储:SQLite、File,使用两种方式混合进行存储主要为了提高读写效率。写入数据时,SQLite要比文件的方式更快;读取数据的速度主要取决于文件的大小。据测试,在iPhone6中,当文件大小超过20kb时,File要比SQLite快的多。所以当大文件存储时建议用File的方式,小文件更适合用SQLite。

所以,主要还是要顾及到存储速度吧。

添加数据

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

获取数据

- (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和sqlLite方式进行存储。

YYDiskCache


YYDiskCache的核心内容就是 YYKVStorage,它是YYKVStorage的拓展。

存储

- (void)setObject:(id)object forKey:(NSString *)key {
        if (!key) return;
        if (!object) {
            [self removeObjectForKey:key];
         return;
    }
//获取要扩展的数据信息(就是后面跟一段数据)
        NSData *extendedData = [YYDiskCache getExtendedDataFromObject:object];

        NSData *value = nil;
        if (_customArchiveBlock) {
           //如果有定义customArchiveBlock这个block就回调
            value = _customArchiveBlock(object);
    } else {
    @try {
        //将数据对象解析成NSData
        value = [NSKeyedArchiver archivedDataWithRootObject:object];
    }
    @catch (NSException *exception) {
        // nothing to do...
    }
}
    if (!value) return;
    NSString *filename = nil;

    //这里的_kv就是上面提到的YYKVStorage类型
    if (_kv.type != YYKVStorageTypeSQLite) {
        if (value.length > _inlineThreshold) {
        //如果数据长度达到一定条件就sqlite和文件存储2种方式同时进行,这里的filename就是关键字md5加密
            filename = [self _filenameForKey:key];
        }
    }
    //设置锁,这里的Lock是宏定义用的是dispatch_semaphore_wait
    Lock();
    //用YYKVStorage存储
    [_kv saveItemWithKey:key value:value filename:filename extendedData:extendedData];
    //解锁
    Unlock();
}

#pragma mark 用runtime添加扩展属性
+ (NSData *)getExtendedDataFromObject:(id)object {
        if (!object) return nil;
        return (NSData *)objc_getAssociatedObject(object, &extended_data_key);
}

+ (void)setExtendedData:(NSData *)extendedData toObject:(id)object {
        if (!object) return;
        objc_setAssociatedObject(object, &extended_data_key, extendedData, OBJC_ASSOCIATION_RETAIN_NONATOMIC);
}

获取数据

- (id)objectForKey:(NSString *)key {
         if (!key) return nil;
        Lock();
       YYKVStorageItem *item = [_kv getItemForKey:key];
       Unlock();
     if (!item.value) return nil;

       id object = nil;
       if (_customUnarchiveBlock) {
         object = _customUnarchiveBlock(item.value);
        } else {
            @try {
                object = [NSKeyedUnarchiver unarchiveObjectWithData:item.value];
             }
            @catch (NSException *exception) {
            // nothing to do...
            }
       }
        if (object && item.extendedData) {
            [YYDiskCache setExtendedData:item.extendedData toObject:object];
     }
        return object;
}

总结


YYCache还是比较简单的,解析起来并不难。也有很多值得学习的地方,比如线程安全sqlLite和文件并行存储LRU算法的实现

参考文献

http://www.cocoachina.com/ios/20160810/17335.html

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

我是翻滚的牛宝宝,欢迎大家评论交流~