Android cache mechanism & a cache framework recommendation

1. Recommend a lightweight caching framework — ACache (ASimpleCache)

ACache is introduced:

ACache is similar to SharedPreferences, but more powerful than SharedPreferences. SharedPreferences can only save some basic data types, Serializable, and Bundle data.

Acache can cache the following data:

Ordinary strings, JsonObject, JsonArray, Bitmap, Drawable, serialized Java objects, and Byte data.

Main features:

• 1: light, light to only a JAVA file.
• 2: configurable. You can configure the cache path, cache size, and cache quantity.
• 3: canIf you set the cache timeout period, the cache timeout period is automatically invalid and deleted.
• 4: Supports multiple processes.

Application Scenarios:

• 1. Replace SharePreference as the configuration file
• 2. It can cache network request data. For example, the Android client of OSChina can cache the NEWS content of HTTP request.
• For your information…

2. Android caching

Android caches are divided into memory caches and file caches (disk caches). In the early days, before image caching frameworks were popular, the commonly used memory caching methods were SoftReference and WeakReference, such as HashMap> imageCache; In this form. Starting from Android 2.3 (Level 9), garbage collectors tend to reclaim SoftReference or WeakReference objects, which makes SoftReference and WeakReference less practical and effective. At the same time, after Android 3.0 (Level 11), image data bitmaps are placed in the heap area of memory, which is managed by GC, so developers do not need to release image resources, but this also makes the release of image data unpredictable, which increases the possibility of OOM. Therefore, after Android3.1, Android introduced the in-memory caching class LruCache, and objects in LruCache are strongly referenced.

2.1 Memory Cache – Source analysis of LruCache

    2.1.1 LRU

LRU, which stands for Least Rencetly Used, is a common replacement algorithm that removes objects that have not been Used for the longest time. LRU page replacement algorithm in the operating system is widely used in our memory or buffer space is limited, when new to an object, cause we have cache space is insufficient, according to some algorithm of the cache is required at this time out of the original data of goods to delete, and LRU choose to unused objects for the longest time.

2.1.2 Implementation Principles of LruCache

According to the idea of LRU algorithm, the core to achieve LRU is to have a data structure that can store objects in the cache based on the access order, so that we can easily know which object is the most recently accessed, which object is the longest time not accessed. LruCache selects the LinkedHashMap data structure. The LinkedHashMap is a two-way circular linked list. When constructing the LinkedHashMap, a Boolean value is used to specify how to store data in the LinkedHashMap. One constructor for LinkedHashMap is as follows:

/* * initialize LinkedHashMap * first parameter: initialCapacity, initial size * second parameter: loadFactor, loadFactor =0.75f * third parameter: accessOrder=true, based on accessOrder; AccessOrder = false, Public LinkedHashMap(int initialCapacity, float loadFactor, Boolean accessOrder) {super(initialCapacity, float loadFactor, Boolean accessOrder) loadFactor); init(); this.accessOrder = accessOrder; }Copy the code

Obviously, accessOrder = true is selected in LruCache; At this point, when accessOrder is set to true, every time we update (call the PUT method) or visit (call the get method) a node in the map, the LinkedHashMap internally moves that node to the end of the list, so that at the end of the list is the most recently used node, The head of the list is the least recently used node. When we run out of cache space, we should keep removing the head of the list until there is room for new nodes.

As you can see, the LinkedHashMap completes the core functions of LruCache, so all that is left to do is define the total cache capacity of LruCache, the capacity that is currently used to save data, and provide put and GET methods.

    2.1.3 LruCache source code Analysis

After understanding the core principle of LruCache, you can begin to analyze the source code of LruCache.

(1) Key fields

According to the above analysis, the key fields of total capacity, used capacity and linkedHashMap are required first. LruCache provides the following three key fields:

Private final LinkedHashMap; Private int size; private int size; Private int maxSize;Copy the code

Note the size field, because map can store various types of data, the size of these data is also different. For example, the size of Bitmap data and String data must be calculated in different ways. Therefore, LruCache can calculate the size of the data in the method sizeOf. It simply returns 1, requiring us to rewrite the method and define how the data is measured. Therefore, we often see this approach when using LruCache:

private static final int CACHE_SIZE = 4 * 1024 * 1024; //4Mib LruCache bitmapCache = new LruCache(CACHE_SIZE){ @Override protected int sizeOf(String key, Bitmap value) { return value.getByteCount(); // Custom Bitmap data size calculation method}};Copy the code

(2) Construction method

public LruCache(int maxSize) { if (maxSize <= 0)="" {="" throw="" new="" illegalargumentexception("maxsize="" <="0");" }="" this.maxsize="maxSize;" This. The map = "new" linkedhashmap (0, 0.75 f, true); }Copy the code

LruCache has only one constructor. In the constructor, given the total size of cache space, the LinkedHashMap core data structure is initialized. The third parameter in the LinkedHashMap is set to true, which is accessOrder=true. Indicates that the LinkedHashMap will be sorted based on the order in which the data is accessed.

(3) sizeOf() and safeSizeOf() methods

According to the above explanation, since there are different standards for measuring the sizeOf various data types, the specific measurement method should be implemented by users. For example, a common implementation method given above is to overwrite sizeOf when implementing LruCache. LruCache encapsulates the sizeOf() call as follows: LruCache encapsulates the sizeOf() call as follows:

private int safeSizeOf(K key, V value) {
    int result = sizeOf(key, value);
    if (result < 0) {
        throw new IllegalStateException("Negative size: " + key + "=" + value);
    }
    return result;
}Copy the code

So what we’re doing is we’re calling sizeOf() and we’re returning the size that sizeOf computed.

The above is the basic content of LruCache, the following needs to provide the core functions of LruCache.

(4) The PUT method caches data

Let’s take a look at the source code implementation:

/** * caches value for the corresponding key and moves the value to the end of the list. */ public final V put(K key, V value) { if (key == null || value == null) { throw new NullPointerException("key == null || value == null"); } V previous; Synchronized (this) {// count putCount++; Size += safeSizeOf(key, value); /* * If there is a previous key, the new value overwrites the original data, and returns the previous key value * record in previous */ previous = map.put(key, value); // If there is a previous key, and the previous value is not null if (previous! Size -= safeSizeOf(key, previous); // If (key, previous); // If (key, previous); }} // If there is a previous key, and the previous value is not null if (previous! = null) {/* * previous is rejected, The value added as a new value for key * tells the custom entryRemoved method */ entryRemoved(false, key, previous, value); TrimToSize (maxSize);} trimToSize(maxSize); return previous; }Copy the code

As you can see, the put() method has the following steps:

1) The key and value are null, indicating that the LruCache cannot allow the key and value to be null.

2) Get the size of the data to be added to the object through safeSizeOf() and update the size of the current cached data;

3) Put the new object data into the cache, that is, call the LinkedHashMap put method, if the original key exists, directly replace the original value, and return the previous value, get the size of the previous value, update the size of the current cache data; If the key does not exist, add it to the cache.

4) Clear the cache space as follows;

(5) trimToSize() Clears cache space

To ensure that the current size of the cache does not exceed the total size we specify when we add a data (put), we call trimToSize() to manage the cache space. As follows:

Public void trimToSize(int maxSize) {/* * Loop LRU until the current size does not exceed the specified total size */ while (true) {K key; V value; Synchronized (this) {/ / some abnormal situation to deal with the if (size < 0 | | (map) isEmpty () && size! = 0)) { throw new IllegalStateException( getClass().getName() + ".sizeOf() is reporting inconsistent results!" ); } // Determine whether the current cache size exceeds the total size of the specified cache space. If there is no more than, can also be stored in the data in the cache, directly out of circulation, cleared the if (size < = maxsize = "" | | =" "map. Isempty ()) =" "{=" "break; =""}="" **="" *="" "**="" if this command is executed, the current cache data has exceeded the total capacity, and you need to run LRU to clear the least recently used data until the cache space does not exceed the limit. Map.entry toEvict = map.entryset ().iterator().next(); key = toEvict.getKey(); value = toEvict.getValue(); map.remove(key); Size -= safeSizeOf(key, value); // update the number of nodes removed evictionCount++; } /* * Removes a node, similar to the callback */ entryRemoved(true, key, value, null); }}Copy the code

    (6) Get method to obtain cached data

The get method is as follows:

/** * Query the cache by key. If the value of the key exists in the cache, return value. * When this node is accessed, LinkHashMap moves it to the end of the bidirectional circular list. * If there is no cached value, null is returned. (If the developer overwrites create(), Public final V get(K key) {if (key == null) {throw new NullPointerException("key == null"); } V mapValue; Synchronized (this) {// synchronized (this) {// synchronized (this) {// synchronized (this) {// LinkHashMap; If (mapValue! = null) { hitCount++; return mapValue; } // count the lost times missCount++; } /* * Official explanation: * Attempts to create a value, which may take a long time, and the Map may differ in the value returned by create(). If the put method is executed with this key * when create() is executed, then a conflict occurs, and we delete the created value in the Map, release the created value, and keep the put value. */ V createdValue = create(key); if (createdValue == null) { return null; } / * * * * * * * * * * * * * * * * * * * * * * * * * * * * don't overwrite the create method can't go below * * * * * * * * * * * * * * * * * * * * * * * * * * * * / / normal couldn't get here * * * go that implements the custom here Create (K key) * Because the default create(K key) logic is null */ synchronized (this) { MapValue = map.put(key, createdValue); // Add the value created by the custom create to the LinkedHashMap. // If the value of the same key exists before, there is a conflict. if (mapValue ! = null) {/* * there is a conflict * so undo the operation * put the same key back */ map.put(key, mapValue); } else {// get the key pair, calculate the relative length in the capacity, then add size += safeSizeOf(key, createdValue); } // if (mapValue! < span style = "box-sizing: border-box; color: RGB (74, 74, 74); The original value of the same key was added back * to tell the custom entryRemoved method */ entryRemoved(false, key, createdValue, mapValue); return mapValue; TrimToSize (maxSize); trimToSize(maxSize); return createdValue; }}Copy the code

1) Try to obtain value from the map cache, i.e. MapVaule = map.get(key); If mapVaule! = null, indicating that the object exists in the cache.

2) If mapVaule == NULL, the object does not exist in the cache. In most cases, null is returned. But if we override the create() method and create one ourselves when the cache doesn’t have the data, we’ll continue down the path, and there might be conflicts. Look at the comment;

3) Note: When we do get(key) or put(key,value) via LinkedHashMap, we adjust the list, placing the node that just accessed GET or added put at the end of the list.

    (7) entryRemoved ()

The source code for entryRemoved is as follows:

/** * 1. Called when recycled or deleted. This method is called by remove * when a value is reclaimed to free storage or put when an item value is replaced. The default implementation does nothing. * 2. This method is not called synchronously and will be executed if another thread accesses the cache. * 4. NewValue! =null, then put() or get() is called. */ protected void entryRemoved(boolean evicted, K key, V oldValue, V newValue) { }Copy the code

The entryRemoved method is an empty method, indicating that it was also left to the developer to rewrite as needed. An entryRemoved() is a callback to developers when node data values need to be removed or removed. Developers can implement some of their own logic in this method:

(1) Resources can be recycled;

(2) Two-level memory cache can be realized to further improve performance. The idea is as follows: Rewrites LruCache’s entryRemoved() function to store the removed item again in another LinkedHashMap. This data structure acts as a secondary cache. Each time an image is retrieved, check whether it is cached in LruCache. Then check if there is any in the level 2 cache, if there is no more from sdcard. If it’s not on the SDcard, pull it from the web server.

EntryRemoved () is called in four places in LruCache: put(), get(), trimToSize(), and remove().

(8) Thread safety of LruCache

LruCache is thread-safe because synchronized is added to the PUT, GET, trimToSize, and remove methods.

2.1.4 Use of LruCache

The above is the core principle and method of the whole LruCache. For LruCache users, we mainly pay attention to the following points:

(1) Provide a total cache size when constructing LruCache;

(2) rewrite the sizeOf method to customize the sizeOf the data stored in map;

(3) Determine whether to rewrite the entryRemoved() method as needed;

(4) Use the PUT and GET methods provided by LruCache to cache data

Summary:

2.2 Disk cache(The file cache) – DiskLruCache analysis

LruCache is a memory caching strategy, but when there are a large number of images, the specified cache memory space may be used up soon. At this time, LruCache will frequently perform trimToSize() operation to continuously remove the least recently used data. When the data is needed again, It had to be reloaded from the network. To this end, Google provides a solution for disk caching called DiskLruCache (DiskLruCache is not integrated into the Android source code, as described in the Android Doc example).

    2.2.1 Implementation Principles of DiskLruCache

Let’s take a look at the cache directory of an APP using the DiskLruCache cache policy.

    

As you can see, there are a bunch of files with very long names in the cache directory. These files are the image data that we cache. At the end, there is a file named journal, which is a log file of DiskLruCache, that is, the operation record of each cached image. The Journal file is at the heart of implementing DiskLruCache. The presence of a Journal file basically indicates that the APP is using the DiskLruCache cache policy.

According to the analysis of LruCache, to achieve LRU, the most important thing is to have a data structure that can store objects in the cache based on the access order. LinkedHashMap is a very suitable data structure. For this reason, DiskLruCache also selects LinkedHashMap as the data structure to maintain the access order. However, for DiskLruCache, LinkedHashMap alone is not enough because we cannot do what LruCache does, Put the data directly into the LinkedHashMap value, that is, in memory. In DiskLruCache, the data is cached in a local file. In this case, the LinkedHashMap value only holds a brief Entry of the value. Such as unique file name, size, readable information, such as:

private final class Entry {
    private final String key;
    /** Lengths of this entry's files. */
    private final long[] lengths;
    /** True if this entry has ever been published */
    private boolean readable;
    /** The ongoing edit or null if this entry is not being edited. */
    private Editor currentEditor;
    /** The sequence number of the most recently committed edit to this entry. */
    private long sequenceNumber;
    private Entry(String key) {
        this.key = key;
        this.lengths = new long[valueCount];
    }
    public String getLengths() throws IOException {
        StringBuilder result = new StringBuilder();
        for (long size : lengths) {
            result.append(' ').append(size);
    }
    return result.toString();
}

    /**
     * Set lengths using decimal numbers like "10123".
     */
    private void setLengths(String[] strings) throws IOException {
        if (strings.length != valueCount) {
            throw invalidLengths(strings);
        }

        try {
            for (int i = 0; i < strings.length; i++) {
                lengths[i] = Long.parseLong(strings[i]);
            }
        } catch (NumberFormatException e) {
            throw invalidLengths(strings);
        }
    }

    private IOException invalidLengths(String[] strings) throws IOException {
        throw new IOException("unexpected journal line: " + Arrays.toString(strings));
    }

    public File getCleanFile(int i) {
        return new File(directory, key + "." + i);
    }

    public File getDirtyFile(int i) {
        return new File(directory, key + "." + i + ".tmp");
    }
}Copy the code

The definition of LinkedHashMap in DiskLruCache is as follows:

Private final LinkedHashMap lruEntries= new LinkedHashMap(0, 0.75f, true);Copy the code

public static DiskLruCache open(File directory, int appVersion, int valueCount, long maxSize) throws IOException { if (maxSize <= 0)="" {="" throw="" new="" illegalargumentexception("maxsize="" < = "0");" }="" if="" (valuecount="" illegalargumentexception("valuecount="" prefer="" to="" pick="" up="" where="" we="" left="" off="" disklrucache="" cache="new" disklrucache(directory,="" appversion,="" valuecount,="" maxsize); ="" (cache.journalfile.exists())="" try="" cache.readjournal(); ="" cache.processjournal(); ="" cache.journalwriter="new" bufferedwriter(new="" filewriter(cache.journalfile,="" true),io_buffer_size); ="" return="" cache; ="" catch="" (ioexception="" journaliscorrupt)="" system.logw("disklrucache="" "="" +="" directory="" is="" corrupt:="" journaliscorrupt.getmessage()="" ",="" removing"); ="" cache.delete(); ="" create="" a="" empty="" directory.mkdirs(); ="" cache.rebuildjournal(); ="" }<="" code="">Copy the code

It is to read the Journal log file, set up the initial data in the map, and maintain the cache file.

A standard Journal log file contains the following information:

The first five lines are called the header of the journal log file, and each of the following lines begins with one of four prefixes: DIRTY, CLEAN, REMOVE, and READ.

Starts with a DIRTY prefix, followed by the cache image key. Starting with the prefix DIRTY means it’s DIRTY data. Every time we call the Edit () method of DiskLruCache, we write a DIRTY record to the journal file, indicating that we are about to write a cache without knowing what the result is. The commit() method is called to indicate a successful write to the cache, and a CLEAN record is written to the Journal, meaning the dirty data is “cleaned.” The abort() method is called to indicate a failed write to the cache, and a REMOVE record is written to the Journal. Each DIRTY key must be followed by a CLEAN or REMOVE key. Otherwise, the DIRTY key is automatically deleted.

The CLEAN prefix and key are followed by a number that represents the size of the cached data.

Thus, we can summarize the workflow in DiskLruCache:

1) Initialization: use the open() method to get the instance of DiskLruCache, in the open method through readJournal(); Methods The journal log file was read and the initial data in map was established according to the journal log file information. Then call processJournal(); Method To analyze the newly established map data, one is to calculate the size of the current valid cache files (i.e. CLEAN), the other is to CLEAN the useless cache files;

2) Data cache and access cache: after the above initialization work is completed, we can carry out the data cache function and access cache function in the program;

This class is also not new. You need to call DiskLruCache’s edit() method to get an instance, as shown below:

  public Editor edit(String key) throws IOException

new Thread(new Runnable() { @Override public void run() { try { String imageUrl = "http://img.my.csdn.net/uploads/201309/01/1378037235_7476.jpg"; String key = hashKeyForDisk(imageUrl); DiskLruCache.Editor Editor = mDiskLruCache. Edit (key); If (Editor! = null) { OutputStream outputStream = editor.newOutputStream(0); If (downloadUrlToStream(imageUrl, outputStream)) {// The downloadUrlToStream method is a method to download an image and outputStream editor.mit ();  } else {editor.abort(); // Commit (). }} mDiskLruCache. Flush ();}} mDiskLruCache. } catch (IOException e) {e.prinintStackTrace ();} catch (IOException e) {e.prinintstackTrace (); } } }).start();Copy the code

Note that each time edit() is called, a record prefixed with DIRTY is written to the journal log file; Commit () also writes a CLEAN record to the journal. If abort() fails, abort() writes a REMOVE record to the journal.

Fetching cached data is done using the get() method, as shown in a simple example:

try { String imageUrl = "http://img.my.csdn.net/uploads/201309/01/1378037235_7476.jpg"; String key = hashKeyForDisk(imageUrl); //MD5 encrypts the url to obtain a unified 16-bit character // Get the Snapshot of the value, which encapsulates the input stream, key and other information. DiskLruCache.Snapshot Snapshot = mDiskLruCache. Get (key); if (snapShot ! = null) { InputStream is = snapShot.getInputStream(0); Bitmap bitmap = BitmapFactory.decodeStream(is); mImage.setImageBitmap(bitmap); } } catch (IOException e) { e.printStackTrace(); }Copy the code

3) Flush where appropriate ()

When caching or retrieving the journal, call different methods to write a line with a different prefix to the journal. The write is written by Writer under IO. To make the write effect effective, call Writer’s flush() method. Flush () in DiskLruCache encapsulates writer.flush(), so we only need to call flush() in DiskLruCache where appropriate. This is an inefficient IO operation. Instead of calling flush every time you write data to a journal, use onPause() to flush the Activity.

Summary & Note:

(1) We can detect memory cache in THE UI thread, that is, we can use LruCache directly in the main thread;

(2) When using DiskLruCache, because the cache or obtain need to operate on the local file, so need to open another thread, in the child thread to detect the disk cache, save cached data, disk operations should never be implemented in the UI thread;

(3) The core of LruCache memory cache is LinkedHashMap, while the core of DiskLruCache is LinkedHashMap and Journal log file, which is equivalent to treating Journal as a piece of “memory”. The value of the LinkedHashMap only holds brief information about the file, and all operations on the cached file are recorded in the Journal log file.

Possible optimizations for DiskLruCache:

DiskLruCache is based on the journal file, which determines that every operation on the cached file needs to be recorded in the journal file. We can use the journal file to access the cached file directly from the program when we first construct DiskLruCache. The access time of each cache file is recorded in the value of the map as the initial value. Each time the cache is accessed or saved, the access time of the cache file corresponding to the corresponding key is updated. In this way, frequent I/O operations are avoided. The Acache lightweight data caching class above does just that.

2.3 Level 2 Cache

LruCache memory caching works well when the amount of data is not large. When the data is large, the bitmap needs to load a large number of images, and the cache capacity specified by LruCache may be exhausted quickly. At this time, LruCache frequently replaces and removes files and makes network requests, and OOM is likely to occur. In the case of a large amount of data, we can use the disk cache DiskLruCache as a secondary cache mode to optimize the cache scheme.

The process is,

(1) When we need to cache data, we cache both in memory and file to disk;

(2) When obtaining the cache file, first try to obtain from the memory cache, if there is, then directly return the file; If the data does not exist, it is obtained from the disk cache. If it does not exist, it can only be obtained from the network. After obtaining the data, it is cached both in memory and on disk.

The next article is ready to write a lightweight data caching framework according to the above content, the framework will be designed with the combination of LruCache and DiskLruCache strategy, please look forward to.

Reference article: