From YYCache source Get to how to design a good cache

preface

Caches are always used in iOS development, but have you thought about what makes a good cache or what makes a good cache?

Close your eyes and think about what you would say if the interviewer asked you to design a cache.

This article will be combined with YYCache source gradually take you to find the answer.

YYCache is a thread-safe, high-performance key-value cache (this project is one of the YYKit components). YYKit was released to Github in 2015, due to the high quality of its code, it gained a large number of stars in a short period of time (now it has 1W + Star), and has been widely echoed in the iOS community, Google is also full of praise.

YYKit author is @ibireme, formerly known as Guo Yaoyuan (guess YY prefix comes from yaoyuan?) , is my personal very like Chinese developers (more than like, it is a fan brother 😘).

YYCache code logic is clear, detailed annotation, plus its own not too large code volume makes it very easy to read, more commendable is its performance is very high.

My assessment is that it is small and beautiful, and this small and beautiful cache source is perfect for today’s topic (YYCache source version is V1.0.4 in this article).

The index

• YYCache profile
• YYMemoryCache details
• YYDiskCache details
• What makes a good cache
• conclusion

YYCache profile

Simple YYCache from beginning to end, the biggest feeling is that the code style is clean and clean, the code idea is clear.

Because the overall difficulty of reading the code is not very large, this article will not go to the word-for-word interpretation of the source code, but extract YYCache as a small and beautiful cache to achieve what cache should have the characteristics of the cache, and analyze the implementation details.

Let’s take a brief look at the code structure of YYCache. YYCache consists of YYMemoryCache and YYDiskCache. YYMemoryCache is used as a high-speed memory cache, while YYDiskCache is used as a low-speed disk cache.

Usually, a cache is composed of memory cache and disk cache. Memory cache provides low-capacity but high-speed access function, while disk cache provides large-capacity but low-speed persistent storage.

@interface YYCache : NSObject

@property (copy.readonly) NSString *name;
@property (strong.readonly) YYMemoryCache *memoryCache;
@property (strong.readonly) YYDiskCache *diskCache;

- (BOOL)containsObjectForKey:(NSString *)key;
- (nullable id<NSCoding>)objectForKey:(NSString *)key;
- (void)setObject:(nullable id<NSCoding>)object forKey:(NSString *)key;
- (void)removeObjectForKey:(NSString *)key;

@end
Copy the code

I have simplified the above code, keeping only the basic code (I think the author probably provided only these basic interfaces when designing the prototype of YYCache), and the rest of the interface is simply made by calling the basic interface and attaching the corresponding processing code.

Note: NS_ASSUME_NONNULL_BEGIN and NS_ASSUME_NONNULL_END are used to detect whether an input parameter is null by the compiler layer and give warnings. See Nullability and Objective-C.

There are many other coding tips like the one above, and I don’t want to share the one I got, but it just doesn’t seem to fit the topic of this article. I’m going to write an article later to share some coding tips THAT I’ve picked up while reading various source libraries (follow me if you’re interested).

From the code we can see that YYCache holds YYMemoryCache and YYDiskCache and provides some interfaces externally. These interfaces are basically designed based on keys and values, similar to the native dictionary interface of iOS (add, delete, change and search).

YYMemoryCache details

YYMemoryCache is a high-speed memory cache for storing key-value pairs. It is the opposite of NSDictionary in that the Key is retained and not copied. The API and performance are similar to NSCache, and all methods are thread-safe.

YYMemoryCache objects differ from NSCache in that:

• YYMemoryCache uses the LEast-recently-used (LRU) algorithm to expel objects. The expulsion mode of NSCache is non-deterministic.
• YYMemoryCache can be controlled by age, cost, and count. The way NSCache is controlled is imprecise.
• YYMemoryCache can be configured to automatically eject objects when a memory warning is received or the App enters the background.

Note: The Access Methods consumption time in YYMemoryCache is usually stable (O(1)).

@interface YYMemoryCache : NSObject

#pragma mark - Attribute
@property (nullable.copy) NSString *name; // Cache name, default nil
@property (readonly) NSUInteger totalCount; // Total number of cached objects
@property (readonly) NSUInteger totalCost; // Total overhead for caching objects


#pragma mark - Limit
@property NSUInteger countLimit; // A limit on the number of cached objects. By default, there is no limit. If the limit is exceeded, some objects will be exported in the background to meet the limit
@property NSUInteger costLimit; // A limit on the amount of cache overhead. By default, there is no limit. If the limit is exceeded, objects will be exported in the background to meet the limit
@property NSTimeInterval ageLimit; // The cache time limit is unlimited by default. If the limit is exceeded, some objects will be exported in the background to meet the limit

@property NSTimeInterval autoTrimInterval; // Cache automatic clearing interval (5s by default)

@property BOOL shouldRemoveAllObjectsOnMemoryWarning; // Whether all cached objects should be deleted when a memory warning is received
@property BOOL shouldRemoveAllObjectsWhenEnteringBackground; // Whether all cached objects should be deleted when the App enters the background

@property (nullable.copy) void(^didReceiveMemoryWarningBlock)(YYMemoryCache *cache); // I think this is a hook so that we can customize the processing cache when we receive a memory warning
@property (nullable.copy) void(^didEnterBackgroundBlock)(YYMemoryCache *cache); // I think this is a hook, so that we can customize the processing cache when we receive the App into the background

@property BOOL releaseOnMainThread; The default is NO. Some objects (such as UIView/CALayer) should be freed on the main thread
@property BOOL releaseAsynchronously; // Whether to release objects asynchronously. The default is YES

- (BOOL)containsObjectForKey:(id)key;

- (nullable id)objectForKey:(id)key;

- (void)setObject:(nullable id)object forKey:(id)key;
- (void)setObject:(nullable id)object forKey:(id)key withCost:(NSUInteger)cost;
- (void)removeObjectForKey:(id)key;
- (void)removeAllObjects;


#pragma mark - Trim
- (void)trimToCount:(NSUInteger)count; // Delete objects with the LRU algorithm until totalCount <= count
- (void)trimToCost:(NSUInteger)cost; // Delete objects with the LRU algorithm until totalCost <= cost
- (void)trimToAge:(NSTimeInterval)age; // Delete objects with the LRU algorithm until all expired objects are deleted

@end
Copy the code

YYMemoryCache definition code is relatively simple ~ the annotations I have added to the above, here I am going to carry out the implementation of the LRU algorithm to the back and (_YYLinkedMapNode and _YYLinkedMap) together. Let’s just focus on how YYMemoryCache is thread-safe.

How is YYMemoryCache thread-safe

@implementation YYMemoryCache {
    pthread_mutex_t _lock; // A thread lock is designed to keep YYMemoryCache threads safe
    _YYLinkedMap *_lru; // _YYLinkedMap, YYMemoryCache indirectly operates on the cache object
    dispatch_queue_t _queue; // Serial queue for THE TRIM operation of YYMemoryCache
}
Copy the code

Yes, here ibireme has chosen to use the pthread_mutex thread lock to ensure the thread-safety of YYMemoryCache.

Interestingly, ibireme’s use of pthread_mutex here has a little story. The OSSpinLock used in YYMemoryCache is the spin lock of OSSpinLock (see YYCache design Notes – about locks). Later, someone raised issue to the author on Github that OSSpinLock is unsafe. Pthread_mutex was selected to replace OSSpinLock after the author’s confirmation (see OSSpinLock is no longer safe).

Here is a simple performance test ibireme did to find an alternative to OSSpinLock after confirming that it was no longer safe. In the comments at the end of OSSpinLock, which is no longer safe, I found the author’s reason for using pthread_mutex.

ibireme: – Apple staff say that libobJC spinlock uses some proprietary method (mach_thread_switch) to contribute high thread priority to avoid priority inversion, but I can’t find any logic in libDispatch source code. Or maybe I missed something. In some of my tests, neither OSSpinLock nor Dispatch_semaphore produced particularly noticeable deadlocks, so I wasn’t sure whether it was right to replace OSSpinLock with dispatch_semaphore. To be sure, pthread_mutex is safe.

_YYLinkedMapNode 与 _YYLinkedMap

YYMemoryCache is introduced above. In fact, YYMemoryCache does not directly operate cache objects, but indirectly operates cache objects through its internal _YYLinkedMapNode and _YYLinkedMap. These two classes are crucial to understanding the LRU caching algorithm mentioned above, so I’ll separate them out and explain them in detail here.

/** _YYLinkedMap a node. Normally we should not use this class. * /
@interface _YYLinkedMapNode : NSObject {
    @package
    __unsafe_unretained _YYLinkedMapNode *_prev; __unsafe_unretained for performance optimization, the node is strongly referenced by _DIC of _YYLinkedMap
    __unsafe_unretained _YYLinkedMapNode *_next; __unsafe_unretained for performance optimization, the node is strongly referenced by _DIC of _YYLinkedMap
    id _key;
    id _value;
    NSUInteger _cost; // Record the cost, corresponding to the cost control provided by YYMemoryCache
    NSTimeInterval _time; // Record the time corresponding to the AGE control provided by YYMemoryCache
}
@end


/** YYMemoryCache is a linked list. _YYLinkedMap is not a thread-safe class, and it does not validate parameters. Normally we should not use this class. * /
@interface _YYLinkedMap : NSObject {
    @package
    CFMutableDictionaryRef _dic; // Do not set this object directly
    NSUInteger _totalCost;
    NSUInteger _totalCount;
    _YYLinkedMapNode *_head; // MRU, the most common node, do not modify it directly
    _YYLinkedMapNode *_tail; // LRU, minimum use of nodes, do not modify it directly
    BOOL _releaseOnMainThread; // releaseOnMainThread corresponding to YYMemoryCache
    BOOL _releaseAsynchronously; // releaseAsynchronously corresponding to YYMemoryCache
}

// The interface name does not need to be commented
- (void)insertNodeAtHead:(_YYLinkedMapNode *)node;
- (void)bringNodeToHead:(_YYLinkedMapNode *)node;
- (void)removeNode:(_YYLinkedMapNode *)node;
- (_YYLinkedMapNode *)removeTailNode;
- (void)removeAll;

@end

Copy the code

For your convenience, I have annotated the necessary Chinese notes. In fact, the data structure and algorithm is not unfamiliar students should see the essence of _YYLinkedMapNode and _YYLinkedMap. Yes, it’s a bidirectional list node and a bidirectional list.

As a bidirectional linked list node, _YYLinkedMapNode not only has the basic _prev and _NEXT, but also has the basic _key and _value of key and value cache. We can understand _YYLinkedMapNode as a cache object in YYMemoryCache.

As a bidirectional linked list of _YYLinkedMapNode nodes, _YYLinkedMapNode is stored using CFMutableDictionaryRef _DIC dictionary. This ensures that _YYLinkedMapNode is strongly referenced and that the dictionary Hash can be used to quickly locate the cache object to be accessed by the user, which not only complies with the concept of key-value cache but also saves the trouble of implementation (laughter).

In general, YYMemoryCache operates on the _YYLinkedMapNode cache object node using the _YYLinkedMap bidirectional list.

Implementation of LRU(least-recently-Used) algorithm

It has been recognized above that _YYLinkedMap and _YYLinkedMapNode are bidirectional linked lists and linked list nodes in essence. Here we will briefly talk about how YYMemoryCache uses bidirectional linked lists to implement LRU(least-Recently-used) algorithm.

Cache replacement strategy

First, LRU is a type of Cache replacement policies. There are many other Cache replacement policies such as:

• First In First Out (FIFO)
• Last In First Out (LIFO)
• Time aware Least Recently Used (TLRU)
• Most Recently Used (MRU)
• Pseudo-LRU (PLRU)
• Random Replacement (RR)
• Segmented LRU (SLRU)
• Least-Frequently Used (LFU)
• Least Frequent Recently Used (LFRU)
• LFU with Dynamic Aging (LFUDA)
• Low Inter-reference Recency Set (LIRS)
• Adaptive Replacement Cache (ARC)
• Clock with Adaptive Replacement (CAR)
• Multi Queue (MQ) caching algorithm|Multi Queue (MQ)
• Pannier: Container-based caching algorithm for compound objects

Are you fooled? Don’t worry, I’m going to make it as easy as possible.

Cache hit ratio

Why are there so many cache replacement strategies, or what is the point of all this fuss?

The answer is to increase cache hit ratio, but what is cache hit ratio?

There are plenty of explanations to Google, of course, but many of them are Web-related and nonverbal (and hard to understand), and I personally hate all sorts of nonverbal “deep” abstractions.

It takes quite a bit of trepidity to get into my understanding of cache hit ratio (limited to YYCache and iOS development).

• Cache hit = The cache object to be accessed by the user is in the cache and we Hash it directly in the cache and return it to the user.
• Cache hit ratio = the probability that the cache object that the user wants to access will be accessed by us in the cache.

Speaking of my own understanding, I must say enough.

• Cache miss = due to limited caching (occupy memory, etc.), so a user to access the cached objects are likely to be we eliminated from limited caching, we may store it in the low speed of disk cache (if there is resource disk cache), then from the disk cache access to the cache object to return to the user, This is what I interpret as a (cache) miss, or cache loss (not really that we’ve dropped it, but that we’ve definitely eliminated it from the cache).

A cache hit is a cache-hit, so if you’re playing a game, it’s a hit miss.

LRU

So let’s start with the concept of LRU just to give you a basic idea. LRU(least-recently-used) translates to “least recently used.” As the name suggests, this cache replacement strategy is based on the cache objects that the user has accessed recently.

In my opinion, the core idea of LRU cache replacement strategy is: LRU considers the cache object that the user has recently used (accessed) as a high-frequency cache object, that is, the user is likely to use (access) this cache object again. On the other hand, a cache object that a user has used (accessed) a long time ago (and has not accessed it again) is a low-frequency cache object, meaning that the user is likely not to use (access) the cache object again and usually releases the low-frequency cache object when the resource is insufficient.

_YYLinkedMapNode 与 _YYLinkedMapRealize the LRU

YYCache author through _YYLinkedMapNode and _YYLinkedMap bidirectional linked list to achieve LRU cache replacement strategy is actually very simple and clear, we look at step by step.

A bidirectional list has a head node and a tail node:

• Header = the cache object node, MRU, that was last used (accessed) by the user in the linked list.
• Tail node = a cache object node in the linked list that the user has not used (accessed) again for a long time, LRU.

How do we get the head and tail nodes to point to the cache object nodes that we want to point to? Let’s look at the code:

• Update the cache node information when the user uses (accesses) and move it to the bidirectional linked list header.

- (id)objectForKey:(id)key {
    // Determine the input parameter
    if(! key)return nil;
    pthread_mutex_lock(&_lock);
    // Find the corresponding cache node
    _YYLinkedMapNode *node = CFDictionaryGetValue(_lru->_dic, (__bridge const void *)(key));
    if (node) {
        // Update the cache node time and move it to the bidirectional list header
        node->_time = CACurrentMediaTime(a); [_lru bringNodeToHead:node]; } pthread_mutex_unlock(&_lock);// Returns the cache node value found
    return node ? node->_value : nil;
}
Copy the code

• When the user sets the cache object, check whether the cache object node corresponding to the input key exists. If it exists, the cache object node is updated and moved to the linked list header node; If not, a new cache object node is generated from the input parameter and inserted into the linked list header.

- (void)setObject:(id)object forKey:(id)key withCost:(NSUInteger)cost {
    // check the input parameter, omit. pthread_mutex_lock(&_lock);// Check whether the cache object node corresponding to the input key exists
    _YYLinkedMapNode *node = CFDictionaryGetValue(_lru->_dic, (__bridge const void *)(key));
    NSTimeInterval now = CACurrentMediaTime(a);if (node) {
        // Update the cache object node and move it to the linked list header
        _lru->_totalCost -= node->_cost;
        _lru->_totalCost += cost;
        node->_cost = cost;
        node->_time = now;
        node->_value = object;
        [_lru bringNodeToHead:node];
    } else {
        // If not, generate a new cache object node based on the input parameter and insert the linked list header
        node = [_YYLinkedMapNode new];
        node->_cost = cost;
        node->_time = now;
        node->_key = key;
        node->_value = object;
        [_lru insertNodeAtHead:node];
    }
    // Check whether the limit cost and count are exceeded after node insertion and update. If so, trim is omitted. pthread_mutex_unlock(&_lock); }Copy the code

• When resources are insufficient, the cache is cleared from the end of the list (LRU) to release resources.

// Use the count resource as an example
- (void)_trimToCount:(NSUInteger)countLimit {
    // If countLimit is 0, all caches will be cleared
    _lru->_totalCount <= countLimit.NSMutableArray *holder = [NSMutableArray new];
    while(! finish) {if (pthread_mutex_trylock(&_lock) == 0) {
            if (_lru->_totalCount > countLimit) {
                // Clear the cache from the end of the list (LRU) to free resources
                _YYLinkedMapNode *node = [_lru removeTailNode];
                if (node) [holder addObject:node];
            } else {
                finish = YES;
            }
            pthread_mutex_unlock(&_lock);
        } else {
            // Use usleep to suspend threads in microseconds at short intervals
            Use usleep to make better use of CPU time than sleep
            usleep(10 * 1000); //10 ms}}// Determine whether to free the cache object in the main thread
    if (holder.count) {
        dispatch_queue_t queue = _lru->_releaseOnMainThread ? dispatch_get_main_queue() : YYMemoryCacheGetReleaseQueue();
        dispatch_async(queue, ^{
            // Asynchronous release
            [holder count]; // release in queue}); }}Copy the code

Is it easy to knock? The above code removed may distract your attention to the code, we only discuss here the implementation of LRU, the rest of the specific implementation of the source code is very simple, I think there is no need to post out separate explanation, interested students can go to YYCache download source code.

Asynchronous release technique

The above asynchronous release cache object code, I think it is necessary to separate out to talk about:

dispatch_queue_t queue = _lru->_releaseOnMainThread ? dispatch_get_main_queue() : YYMemoryCacheGetReleaseQueue();
dispatch_async(queue, ^{
    // Asynchronous release
    [holder count]; // release in queue
});
Copy the code

Ibireme mentioned this technique in his other post on how to keep the iOS interface smooth:

Note: Object destruction is not a huge resource, but it adds up. Usually when a container class holds a large number of objects, the resource cost of their destruction becomes apparent. Similarly, if an object can be released in a background thread, move it to the background thread. Here’s a little Tip: Capture an object in a block, throw it on a background queue, send a random message to avoid compiler warnings, and let the object be destroyed in the background thread.

The code above YYMemoryCacheGetReleaseQueue the queue of the source code is:

// static inline dispatch_queue_t
static inline dispatch_queue_t YYMemoryCacheGetReleaseQueue() {
    return dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_LOW, 0);
}
Copy the code

You can see in the source YYMemoryCacheGetReleaseQueue is a low priority DISPATCH_QUEUE_PRIORITY_LOW queue, speculation is the cause of this design can let the iOS release in the system is relatively free to asynchronous cache object.

YYDiskCache details

YYDiskCache is a thread-safe disk cache for storing key-value pairs supported by SQLite and file systems (similar to NSURLCache’s disk cache).

YYDiskCache has the following functions:

• It uses LRU(least-recently-used) to delete objects.
• Supports cost, count, and age control.
• It can be configured to automatically expel cache objects when no disk space is available.
• It can automatically choose the storage type of each cached object (SQLite /file) to provide better performance.

Note: You can compile the latest version of SQLite and ignore libsqlite3. Dylib in iOS to get 2x ~ 4x speed improvements.

@interface YYDiskCache : NSObject

#pragma mark - Attribute
@property (nullable.copy) NSString *name; // Cache name, default nil
@property (readonly) NSString *path; // Cache path

@property (readonly) NSUInteger inlineThreshold; // Threshold. If the value is greater than the threshold, the storage type is file. Otherwise, the storage type is SQLite

@property (nullable.copy) NSData *(^customArchiveBlock)(id object); // Replace NSKeyedArchiver, which you can use to support objects that do not conform 'NSCoding'
@property (nullable.copy) id (^customUnarchiveBlock)(NSData *data); // Replace NSKeyedUnarchiver, which you can use to support objects that do not conform 'NSCoding'

@property (nullable.copy) NSString *(^customFileNameBlock)(NSString *key); // This code block is used to generate the specified file name when an object is to be saved as file. If it is nil, md5(key) is used as the file name by default

#pragma mark - Limit
@property NSUInteger countLimit; // A limit on the number of cached objects. By default, there is no limit. If the limit is exceeded, some objects will be exported in the background to meet the limit
@property NSUInteger costLimit; // A limit on the amount of cache overhead. By default, there is no limit. If the limit is exceeded, objects will be exported in the background to meet the limit
@property NSTimeInterval ageLimit; // The cache time limit is unlimited by default. If the limit is exceeded, some objects will be exported in the background to meet the limit
@property NSUInteger freeDiskSpaceLimit; // The minimum amount of free disk space (in bytes) that the cache should retain. By default, there is no limit, and objects beyond this limit are evicted in the background to meet the limit

@property NSTimeInterval autoTrimInterval; // Cache automatic clearing interval. Default: 60 seconds
@property BOOL errorLogsEnabled; // Whether to enable error logging

#pragma mark - Initializer
- (nullable instancetype)initWithPath:(NSString *)path
                      inlineThreshold:(NSUInteger)threshold NS_DESIGNATED_INITIALIZER;

- (BOOL)containsObjectForKey:(NSString *)key;

- (nullable id<NSCoding>)objectForKey:(NSString *)key;

- (void)setObject:(nullable id<NSCoding>)object forKey:(NSString *)key;

- (void)removeObjectForKey:(NSString *)key;
- (void)removeAllObjects;
                                 
- (NSInteger)totalCount;
- (NSInteger)totalCost;

#pragma mark - Trim
- (void)trimToCount:(NSUInteger)count;
- (void)trimToCost:(NSUInteger)cost;
- (void)trimToAge:(NSTimeInterval)age;

#pragma mark - Extended Data
+ (nullable NSData *)getExtendedDataFromObject:(id)object;
+ (void)setExtendedData:(nullable NSData *)extendedData toObject:(id)object;

@end
Copy the code

The structure of YYDiskCache is similar to that of YYMemoryCache. As many interfaces are extended based on basic interfaces, some interfaces are omitted in the code here. As always, the code is clean and concise, I believe you can understand.

YYDiskCache is a disk cache based on SQLite and File. Our cache objects can freely choose the storage type. Here is a simple comparison:

• Sqlite: Access efficiency for small data (such as NSNumber) is significantly higher than file.
• File: More efficient than SQLite for accessing large data, such as high-quality images.

Therefore, YYDiskCache uses the combination of the two to flexibly store data to improve performance.

NSMapTable

NSMapTable is a collection similar to dictionaries, but with broader semantics of available memory. NSMapTable is a class introduced after iOS6 that is modeled based on NSDictionary, but with the following differences:

• ‘Keys and values can be held as’ weakly’ so that they can be removed when one of the objects is recovered.
• It can contain any pointer (its contents are not constrained as objects).
• You can configure the NSMapTable instance to operate on any pointer, not just objects.

Note: When configuring the mapping table, please Note that only the options listed in NSMapTableOptions will make the rest of the API work, including copy, archive, and fast enumeration. While other NSPointerFunctions options are used for some configurations, such as holding arbitrary Pointers, not all combinations of options are valid. With some combinations, NSMapTableOptions may not work properly and may not even be properly initialized.

For more information, see the official NSMapTable document.

It should be noted that YYDiskCache is internally managed based on a singleton NSMapTable, which is different from YYMemoryCache.

static NSMapTable *_globalInstances; // Manage all YYDiskCache instances
static dispatch_semaphore_t _globalInstancesLock; // YYDiskCache uses dispatch_semaphore to ensure the security of the NSMapTable thread

static void _YYDiskCacheInitGlobal() {
    static dispatch_once_t onceToken;
    dispatch_once(&onceToken, ^{
        _globalInstancesLock = dispatch_semaphore_create(1);
        _globalInstances = [[NSMapTable alloc] initWithKeyOptions:NSPointerFunctionsStrongMemory valueOptions:NSPointerFunctionsWeakMemory capacity:0];
    });
}

static YYDiskCache *_YYDiskCacheGetGlobal(NSString *path) {
    if (path.length == 0) return nil;
    _YYDiskCacheInitGlobal();
    dispatch_semaphore_wait(_globalInstancesLock, DISPATCH_TIME_FOREVER);
    id cache = [_globalInstances objectForKey:path];
    dispatch_semaphore_signal(_globalInstancesLock);
    return cache;
}

static void _YYDiskCacheSetGlobal(YYDiskCache *cache) {
    if (cache.path.length == 0) return;
    _YYDiskCacheInitGlobal();
    dispatch_semaphore_wait(_globalInstancesLock, DISPATCH_TIME_FOREVER);
    [_globalInstances setObject:cache forKey:cache.path];
    dispatch_semaphore_signal(_globalInstancesLock);
}
Copy the code

Whenever YYDiskCache is initialized, NSMapTable is used to obtain the instance of YYDiskCache corresponding to path. If the instance cannot be obtained, NSMapTable is used to initialize an instance of YYDiskCache. And reference it in NSMapTable, which also improves performance.

- (instancetype)initWithPath:(NSString *)path
             inlineThreshold:(NSUInteger)threshold {
    // Check whether initialization can be successful, omit.// Obtain the YYDiskCache instance from the NSMapTable singleton according to path. If yes, return the instance directly
    YYDiskCache *globalCache = _YYDiskCacheGetGlobal(path);
    if (globalCache) return globalCache;
    
    // If not, initialize a YYDiskCache instance
    To initialize a YYDiskCache, you must first initialize a YYKVStorage
    YYKVStorage *kv = [[YYKVStorage alloc] initWithPath:path type:type];
    if(! kv)return nil;
    
    // Initialize a YYDiskCache instance based on the kv and path input parameters.// If recursive cleaning is enabled, YYDiskCache trim is configured according to _autoTrimInterval
    [self _trimRecursively];
    // Register the newly generated YYDiskCache instance with the NSMapTable singleton
    _YYDiskCacheSetGlobal(self);
    
    // App lifecycle notification code is omitted.return self;
}
Copy the code

The author uses dispatch_semaphore as YYDiskCache lock.

Dispatch_semaphore is a semaphore, but can also be used as a lock if the total number of signals is set to 1. It performs even better than pthread_mutex when there are no wait conditions, but much worse when there are wait conditions. Its advantage over OSSpinLock is that it does not consume CPU resources while waiting. It is suitable for disk caching.

YYKVStorageItem and YYKVStorage

Just now in YYDiskCache initialization source, we can easily find a class YYKVStorage. In contrast to YYMemoryCache, YYDiskCache does not directly operate cache objects (SQlite /file), but indirectly operates cache objects through YYKVStorage.

From this point, it is not difficult to find that YYKVStorage is equivalent to the bidirectional linked list _YYLinkedMap in YYMemoryCache, and corresponding to the node _YYLinkedMapNode in _YYLinkedMap. YYKVStorage also has a class YYKVStorageItem that acts as a one-to-one buffer object.

// YYKVStorageItem is the class used to store key-value pairs and metadata in YYKVStorage
// In general, we should not use this class directly
@interface YYKVStorageItem : NSObject
@property (nonatomic.strong) NSString *key;                ///< key
@property (nonatomic.strong) NSData *value;                ///< value
@property (nullable.nonatomic.strong) NSString *filename; ///< filename (nil if inline)
@property (nonatomic) int size;                             ///< value's size in bytes
@property (nonatomic) int modTime;                          ///< modification unix timestamp
@property (nonatomic) int accessTime;                       ///< last access unix timestamp
@property (nullable.nonatomic.strong) NSData *extendedData; ///< extended data (nil if no extended data)
@end


/** YYKVStorage is a key-value storage based on SQLite and file system. In general, we should not use this class directly. The @warning class instance is * non-* thread-safe, and you need to make sure that only one thread can access the instance at the same time. If you really need to process large amounts of data in multiple threads, you should split the data into multiple KVStorage instances (sharding). * /
@interface YYKVStorage : NSObject

#pragma mark - Attribute
@property (nonatomic.readonly) NSString *path;        / / / storage path
@property (nonatomic.readonly) YYKVStorageType type;  / / / storage type
@property (nonatomic) BOOL errorLogsEnabled;           // whether to enable error logging

#pragma mark - Initializer
- (nullable instancetype)initWithPath:(NSString *)path type:(YYKVStorageType)type NS_DESIGNATED_INITIALIZER;

#pragma mark - Save Items
- (BOOL)saveItem:(YYKVStorageItem *)item; .#pragma mark - Remove Items
- (BOOL)removeItemForKey:(NSString*)key; .#pragma mark - Get Items
- (nullable YYKVStorageItem *)getItemForKey:(NSString*)key; .#pragma mark - Get Storage Status
- (BOOL)itemExistsForKey:(NSString *)key;
- (int)getItemsCount;
- (int)getItemsSize;

@end
Copy the code

Code beauty cry there is no! ? This code doesn’t need to be translated at all, and I feel more comfortable looking at the code rather than translating it line by line. Here we just need to look at the enumeration of YYKVStorageType, which determines the storage type of YYKVStorage.

YYKVStorageType

/** Storage type, indicating where yykvStorageItem. value is stored. @discussion In general, writing data to SQLite is faster than external files, but read performance depends on the data size. In my tests (environment iPhone 6 64G), reading data from external files was faster when the data was large (over 20KB) than SQLite. * /
typedef NS_ENUM(NSUInteger, YYKVStorageType) {
    YYKVStorageTypeFile = 0.// Value is stored as a file in the file system
    YYKVStorageTypeSQLite = 1.// Value is stored in binary form in SQLite
    YYKVStorageTypeMixed = 2.// The value will be mixed based on the above two forms depending on your choice
};
Copy the code

YYKVStorageType in the annotation mark the author wrote YYCache when the test conclusion, we can also test and verify the author’s statement based on their own environment (this point can be discussed, We can set the inlineThreshold in YYDiskCache based on our own tests).

For more information, click on Internal Versus External BLOBs in SQLite to check out the official SQLite documentation.

YYKVStorage performance optimization details

YYKVStorage can do disk storage based on SQLite and file system, here are some more interesting details I read the source code found:

@implementation YYKVStorage {...CFMutableDictionaryRef _dbStmtCache; // Focus here. }Copy the code

You can see CFMutableDictionaryRef _dbStmtCache; Is a private member of YYKVStorage, which is a mutable dictionary that acts as the sqlite3_STMT cache.

- (sqlite3_stmt *)_dbPrepareStmt:(NSString *)sql {
    if(! [self _dbCheck] || sql.length == 0| |! _dbStmtCache)return NULL;
    // Try to fetch the cached sqlite3_stmt from _dbStmtCache based on the input parameter SQL
    sqlite3_stmt *stmt = (sqlite3_stmt *)CFDictionaryGetValue(_dbStmtCache, (__bridge const void *)(sql));
    if(! stmt) {// Create a new sqlite3_stmt if there is no cache
        int result = sqlite3_prepare_v2(_db, sql.UTF8String, - 1, &stmt, NULL);
        // If the generated result is abnormal, logs are printed according to the error log function
        if(result ! = SQLITE_OK) {if (_errorLogsEnabled) NSLog(@"%s line:%d sqlite stmt prepare error (%d): %s", __FUNCTION__, __LINE__, result, sqlite3_errmsg(_db));
            return NULL;
        }
        // If it succeeds, it is placed in _dbStmtCache
        CFDictionarySetValue(_dbStmtCache, (__bridge const void *)(sql), stmt);
    } else {
        sqlite3_reset(stmt);
    }
    return stmt;
}
Copy the code

This saves some of the overhead of repeatedly generating SQLITe3_STMT.

Sqlite3_stmt: An instance of this object represents a single SQL statement that has been compiled into binary form and is ready for execution.

More information about SQLite can be found in the SQLite documentation.

What makes a good cache

Back to the original question, what makes a good cache?

If you follow the article step by step, I believe it is easy to cite the following points:

• Memory cache and disk cache
• Thread safety
• The cache control
• Cache replacement strategy
• Cache hit ratio
• performance

We simply summarize YYCache source code is how to reflect these characteristics.

Memory cache and disk cache

YYCache is composed of the memory cache YYMemoryCache and the disk cache YYDiskCache. The memory cache provides low-capacity but high-speed access, and the disk cache provides large-capacity but low-speed persistent storage. This design allows users to have a good experience caching different objects.

When an interface is used to access a cache object in YYCache, the first attempt is made to access it from the memory cache YYMemoryCache. YYDiskCache is accessed from YYDiskCache only if it cannot be accessed (the object has not been cached with this key or has been eliminated from YYMemoryCache with limited capacity). If it is accessed (the object has been cached with this key before, This object has been eliminated from the limited YYMemoryCache.) The access information of the cache object is updated in the YYMemoryCache before being returned to the interface.

Thread safety

If YYCache is a purely logic-level cache class, then YYMemoryCache and YYDiskCache do something about it. The most obvious is that YYMemoryCache and YYDiskCache are thread-safe for YYCache.

YYMemoryCache uses pthread_mutex thread locks to ensure thread-safety, whereas YYDiskCache uses dispatch_semaphore, which is more suitable for YYDiskCache. The reasons for these locks have been given above.

The cache control

YYCache provides three control dimensions: cost, count, and age. This meets the needs of most developers, and we can also provide appropriate controls for our own use of caches when designing them.

Cache replacement strategy

In the above analysis of YYCache source, introduced the concept of cache replacement strategy and listed a lot of classic strategies. YYCache uses bidirectional linked lists (_YYLinkedMapNode and _YYLinkedMap) to implement LRU(least-recently-used) strategy, aiming to improve the cache hit ratio of YYCache.

Cache hit ratio

This concept was introduced in the previous section of parsing _YYLinkedMapNode and _YYLinkedMap. We do not need to use LRU strategy when designing our cache. We can choose the most suitable cache replacement strategy according to our actual use environment.

performance

In fact, performance is invisible and ubiquitous (laughter). It was brought in from the very beginning when we were designing a cache architecture, all the way through to the specifics of our implementation, and ultimately became the determining factor for the quality of the cache we were designing.

The implementation details of YYCache’s performance improvement have been dissected above:

• Asynchronously release the cache object
• The choice of the lock
• YYDiskCache managed using NSMapTable singleton
• In the YYKVStorage_dbStmtCache
• Even using CoreFoundation in exchange for minimal performance gains

Did you see this suddenly, how does the performance come? This is the ultimate pursuit of every detail bit by bit out of the bottom.

conclusion

• Article system interpretation of YYCache source, I believe that you can let readers have a clear understanding of the overall structure of YYCache.
• The article combined with the author YYCache design ideas of the content of YYCache specific function points to realize the source code to do an in-depth analysis, and then expressed with my own understanding, I hope to provide help for readers to understand the realization of the specific function of YYCache.
• According to my own understanding of the source code, I think do a good performance of the source code details carried out separately to make a detailed analysis.
• Summarize “What makes a good cache?” The answer to this question is something you should be comfortable with if you’re asked a question like “How do YOU design a cache?” Well, at least that will give you some ideas to answer. (Laughter)

The article is written carefully (it is my personal original article, please indicate lision. Me/for reprinting). If any mistakes are found, it will be updated in my personal blog first, and I also recommend everyone to go there to communicate with me (well, it seems that I have not opened the comment 😓).

Hope my article can bring value for you ~ also hope can move finger to help me share out 😁

---

Supplement ~ I set up a technical exchange wechat group, want to know more friends in it! If you have any questions about the article or encounter some small problems in your work, you can find me or other friends in the group to communicate and discuss. Looking forward to your joining us

Emmmmm.. Because the number of wechat group is over 100, it is not possible to scan the code into the group, so please scan the qr code above to pay attention to the public number into the group.