序文
、高性能なキャッシュフレームワークであり、 開発され、プロジェクトは、キャッシュソリューションとしてYYCacheを使用して、以下は、その実装の仕組みを分解し、その高いパフォーマンスの理由を説明することです、LRUアルゴリズムの実装、ロックの使用、およびキャッシュの削除タイミングなど、いくつかのフレームワークに加えて、私は問題があるかもしれないと思います。
YYMemoryCache の実装メカニズム
低周波数で使用される要素の除去を優先
Appleはまた、独自のキャッシュソリューションであるNSCacheを持っています。NSCacheは、システムメモリをあまり消費しないように、さまざまな自動削除ストラテジーを組み合わせており、システムメモリが逼迫しているときには、これらのストラテジーを自動的に実行してキャッシュからいくつかのオブジェクトを削除しますが、その順序は不確定です。
YYCacheは、低頻度のデータを優先的に削除するメカニズムを使っています。
YYCacheはYYMemoryCacheとYYDiskCacheに分かれています。
YYMemoryCacheは内部で_YYLinkedMapという双方向のリンクテーブルを保持しており、データを保存するたびにリンクテーブルの最初の部分にデータが保存され、メモリが逼迫している場合はリンクテーブルの最後から削除を開始することで、削除された要素が頻繁に使用されないようにし、ある程度の効率を向上させます。
双方向リンクテーブルと言われていますが、実際のキャリアは辞書のままで、_YYLinkedMapの構造は以下のようになっています：
@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;
}
CFMutableDictionaryRef実際のキャリアは _dic, で、NSMuatbleDictionary に対応する C レベルのミュータブル・ディクショナリです。
リンクされたテーブルの各ノードは_YYYLinkedMapNode型のオブジェクトで、以下の構造を持っています：
@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
prevと_nextはそれぞれ前のノードと次のノードを指します。
キャッシュを削除するタイミング
YYMemoryCache はキャッシュを制御するために3つの次元を提供します：
// キャッシュされるオブジェクトの数。デフォルトは NSUIntegerMax で、上限はない。
@property NSUInteger countLimit;
// キャッシュ・オーバーヘッド、デフォルトNSUIntegerMax、上限なし
@property NSUInteger costLimit;
// キャッシュする時間、デフォルトDBL_MAX，
@property NSTimeInterval ageLimit;
これらの値は自分で設定することができます。例えば、キャッシュオブジェクトの最大数を5に設定すると、キャッシュが5を超えた場合、キャッシュオブジェクトが5以下になるまで、YYCacheが自動的にオブジェクトを削除します。
これはどのような仕組みですか？
これらの属性のすぐ下には、別の属性があります：
// 制限を超えてキャッシュをクリアする操作の間隔、デフォルトは5秒。
@property NSTimeInterval autoTrimInterval;
YYMemoryCacheが初期化された後、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];
});
}
このメソッドは、現在のキャッシュが設定された制限を超えたかどうかをポーリングし、超えた場合はキャッシュを設定された制限まで解放します。
タイマーの他に、キャッシュをクリアするタイミングが2つあり、2つの通知に対応しています：
[[NSNotificationCenter defaultCenter] addObserver:self selector:@selector(_appDidReceiveMemoryWarningNotification) name:UIApplicationDidReceiveMemoryWarningNotification object:nil];
[[NSNotificationCenter defaultCenter] addObserver:self selector:@selector(_appDidEnterBackgroundNotification) name:UIApplicationDidEnterBackgroundNotification object:nil];
1つはシステムメモリが逼迫したときの通知、もう1つはアプリがバックグラウンドに入ったときの通知で、この2つの通知を受け取るとキャッシュをクリアします。
ちなみに、メインスレッドでキャッシュを削除することを特に指定しない場合、すべてのキャッシュクリア操作はサブスレッドで実行されます。
オブジェクトを非同期に解放するためのヒント
YYCacheは、オブジェクトのリリースを取るためにブロックの方法で行うには、ブロックにオブジェクトをキャプチャすることにより、ユーザーエクスペリエンスを向上させる、この小さなトリックも学ぶことができる、次の小さな例です：
NSArray *tmp = self.array;
self.array = nil;
dispatch_async(queue, ^{
[tmp class]; // この呼び出しは、コンパイラの警告を避けるためだけのものである。
});
costLimit 小さなバグ
しかし、costLimitには問題があります。costLimitはオブジェクトが渡されるときに指定され、指定されなければオブジェクトのコストはゼロになります：
- (void)setObject:(id)object forKey:(id)key {
[self setObject:object forKey:key withCost:0];
}
YYMemoryCache 使用ロック
YYMemoryCache と YYDiskCache はどちらもスレッドセーフで、それを保証するために異なるロックを使用しています。 YYMemoryCache は最初に OOSpinLock を使用して実装されました。これはスピンロックで、アクセスしたいリソースが占有されるとポーリングします。準備はできていますか？つまり、CPUはリソースが利用可能になるまで、リソースが準備できているかどうかを尋ね続けます。このスピンロックのメカニズムは優先順位の逆転の問題につながるため、iOSはもはやこのようなロックの使用を提唱していません。
OOSpinLockの代わりに、pthread_mutexはミューテックスロックです。 ミューテックスロックとスピンロックの最大の違いは、ミューテックスロックによってロックされたリソースが占有されると、システムはシステムリソースを消費せずにハングアップして待機することです。
iOSはまた、いくつかのロックを提供し、より高い性能はNSLockですが、実際にはそれはpthred_mutexのカプセル化であり、NSLockは、オブジェクトの呼び出し処理を実行する必要がありますので、pthread_mutexに比べてパフォーマンスが悪くなります。だから、YYMemoryCacheは直接pthred_mutexを使用して、すでにiOSのロックのパフォーマンスで利用可能です比較的最高ですが、ここでロックの内容については、特定の拡張ではありませんが、あなたが YYCache書いた ibireme見ることができるかどうかに興味がある ：スレッド同期スキーム。
YYDiskCache の実装メカニズム
データ保存方法
ディスクキャッシュは実際には2つの部分に分かれており、1つはデータベースキャッシュで、もう1つはファイルキャッシュです。 初期化時に境界を指定します。デフォルトは20KBで、つまり20KB以内のデータはデータベースに存在し、20KBを超えるデータはファイルに保存され、ディスクキャッシュ内の各オブジェクトはYYKVStorageItem型としてカプセル化されます：
@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
値が20KBより大きい場合は、ファイルにキャッシュされ、メタデータ、つまりYYKVStorageItemはデータベースに保存されます、
ファイルを直接保存する代わりにデータベースを使用する理由と、データベースとファイルの境界が20KBである理由は、YYCacheの作者自身がテストした結果です：
ファイルシステムに基づくファイルの読み書きを通じてデータをキャッシュする、つまり1つの値が1つのファイルに対応することの欠点は、拡張が不便であること、メタデータがないこと、より優れた消去アルゴリズムの実装が困難であること、データ統計が遅いことです。
データベースベースのキャッシュは、メタデータをサポートするために非常に良いことができ、拡張が容易で、データの統計が速く、それはまた、LRUまたは他の消去アルゴリズムを実装することは非常に簡単ですが、唯一の不確実性は、データベースの読み取りと書き込みのパフォーマンスであるため、私は実機でSQLiteのパフォーマンスを評価しました。 iPhone 6の64Gは、SQLiteの書き込み性能は、ファイルを直接読み取るよりも高いですが、読み取り性能は、データのサイズに依存します：一つのデータが20K以下の場合、ファイルに直接書き込んだ方が速い。
つまり、インベントリ・キャッシュはSQLiteとファイル・ストレージの組み合わせが理想的で、キー・バリューのメタデータはSQLiteに、バリュー・データはサイズに応じてSQLiteまたはファイル・ストレージのいずれかに保存されます。
この 記事 おきます。
YYDiskCacheは、システムの使用は、データベースを実装するためにsqlite3が付属しており、データベースへのアクセスコードについては、ここでは言うために開始されませんが、コードはYYKVStorage.mにあり、あなたが見るためにgithubからYYCacheのソースコードをダウンロードすることができます。
LRU
ディスク・キャッシュの削除タイミングは基本的にメモリ・キャッシュと同じですが、60秒の自動ポーリング時間があり、ディスク・キャッシュにも対応するcostLimit、countLimit、ageLimitがあります。
YYMemoryCacheはチェーンテーブルの末尾から優先的にデータを削除すると前述しましたが、YYDiskCacheの構造はデータベースであり、削除の根拠は何でしょうか？
ライブラリの各メタデータは、last_access_timeというパラメータを持ち、このメタデータの各操作は、現在の操作時間を記録し、削除する時間まで、この時間に基づいて、古いものから削除を開始します。
データベースのクエリーコマンドを見てください：
- (NSMutableArray *)_dbGetItemSizeInfoOrderByTimeAscWithLimit:(int)count {
// データベースから最後に読み込まれたデータ_access_time
NSString *sql = @"select key, filename, size from manifest order by last_access_time asc limit ?1;";
// ...
}
YYDiskCache 使用ロック
ここでは、ロックはセマフォで実装されています：
static dispatch_semaphore_t _globalInstancesLock;
簡単に言えば、セマフォは現在蓄積されている信号の数を値とするカウンタです。セマフォは、加算（up）と減算（down）の2つの演算をサポートしています：
ダウン 減算操作：
- セマフォの値が1以上かどうかを判断します。
- もしそうなら、セマフォの値を1だけ引いて、その行を進みます。
- それ以外の場合は、このセマフォで待機します。
加算操作：
- セマフォの値に1を加算
- スレッドの続き
重要なのは、ダウン操作とアップ操作は、複数のステップを含むにもかかわらず、互いに切り離すことのできないアトミック操作の集合であるということです。
セマフォの値を0と1に制限すると、 バイナリ・セマフォとしても知られるロックが得られます。操作方法は以下の通りです：
ダウン 減算操作：
- セマフォの値が1に変わるのを待ちます。
- セマフォの値を0に設定
- 実装の下に進みます
加算操作：
- セマフォの値を1に設定
- このセマフォで待機している最初のスレッドをウェイクアップします。
- スレッドの続き
バイナリ・セマフォは 0 と 1 の値しか取らないので、上記の手続きは同時に 2 つの手続きがクリティカル・ゾーンに入ることを防ぎます。これはロックの概念と同じで、YYDiskCache はバイナリ・セマフォを使っていますが、実は pthread_mutex で置き換えることも可能です。両者を比較すると、待ち状態がないときは、セマフォの性能は pthread_mutex よりも高いです。しかし、一旦待ち状態が発生すると性能は大きく落ちます。また、セマフォは待機中にCPUリソースを占有しないので、ディスクキャッシュには最適です。
引用記事
もはや安全ではないOSSpinLock
結論
欠点があれば遠慮なく指摘してください。
