下面由Redis教學專欄給大家詳解Redis的LRU演算法,希望對需要的朋友有幫助!
LRU演算法背後的想法在電腦科學中無所不在,它與程式的"局部性原理"很相似。在生產環境中,雖然有Redis記憶體使用警告,但是了解Redis的快取使用策略還是很有好處的。以下是生產環境下Redis使用策略:最大可用記憶體限制為4GB,採用 allkeys-lru 刪除策略。所謂刪除策略:當redis使用已經達到了最大內存,例如4GB時,如果這時候再往redis裡面添加新的Key,那麼Redis將選擇一個Key刪除。那如何選擇適合的Key刪除呢?
CONFIG GET maxmemory
- "maxmemory"
- "4294967296"
#CONFIG GET maxmemory-policy
- #"maxmemory-policy"
- "allkeys-lru"
在官方文件Using Redis as an LRU cache描述中,提供了好幾種刪除策略,如allkeys-lru、volatile-lru等。在我看來按選擇時考慮三個因素:隨機、Key最近被訪問的時間、Key的過期時間(TTL)
例如:allkeys-lru,"統計一下所有的"Key歷史訪問的時間,把"最老"的那個Key移除。注意:我在這裡加了引號,其實在redis的具體實作中,要統計所有的Key最近的訪問時間代價是很大的。想想,如何做到呢?
evict keys by trying to remove the less recently used (LRU) keys first, in order to make space for the new data added.
再例如:allkeys- random,就是隨機選擇一個Key,將之移除。
evict keys randomly in order to make space for the new data added.
再例如:volatile-lru,它只移除那些使用expire 指令設定了過期時間的Key,根據LRU演算法來移除。
evict keys by trying to remove the less recently used (LRU) keys first, but only among keys that have an expire set, in order to make space for the new dataspace for the new data added.
再例如:volatile-ttl,它只移除那些使用expire 指令設定了過期時間的Key,哪個Key的存活時間(TTL KEY 越小)越短,就優先移除。
evict keys with an expire set, and try to evict keys with a shorter time to live (TTL) first, in order to make space for the new data added.
volatile 策略(eviction methods) 作用的Key 是那些設定了過期時間的Key。在redisDb結構體中,定義了一個名為expires 字典(dict)保存所有的那些用expire指令設定了過期時間的key,其中expires字典的鍵指向redis 資料庫鍵空間(redisServer-- ->redisDb--->redisObject)中的某個鍵,而expires字典的值則是這個鍵的過期時間(long型別整數)。
額外提一下:redis 資料庫鍵空間是指:在結構體redisDb中定義的一個名為"dict",類型為hash字典的一個指針,它用來保存該redis DB中的每一個鍵物件、以及對應的值物件。
既然有這麼多策略,那我用哪個好呢?這就涉及到Redis中的Key的訪問模式了(access-pattern),access-pattern與代碼業務邏輯相關,比如說符合某種特徵的Key經常被訪問,而另一些Key卻不怎麼用到。如果所有的Key都可能機會均等地被我們的應用程式訪問,那麼它的訪問模式服從均勻分佈;而大部分情況下,訪問模式服從冪指分佈(power-law distribution),另外Key的存取模式也有可能是隨著時間變化的,因此需要一種合適的刪除策略能夠catch 住(捕獲住)各種情形。而在冪指分佈下,LRU是一種很好的策略:
While caches can't predict the future, they can reason in the following way: keys that are likely to be requested again are keys that were recently requested often. Since usually access patterns don't change very suddenly, this is an effective strategy.
The LRU algorithm evicts the Least Recently Used key, which means the one with the greatest idle time.
如A、B、C 、D四個Key,A每5s訪問一次,B每2s訪問一次,C和D每10s訪問一次。 (一個波浪號代表1s),從上圖可看出:A的空閒時間是2s,B的idle time是1s,C的idle time是5s,D剛剛訪問了所以idle time是0s
這裡,用一個雙向鍊錶(linkedlist)把所有的Key鍊錶起來,如果一個Key被訪問了,將就這個Key移到鍊錶的表頭,而要移除Key時,直接從錶尾移除。
It is simple to implement because all we need to do is to track the last time a given key was accessed, or sometimes this is not even needed: we may just have all the objects is not even needed: we may just have all the obant towe evict linked in a linked list.
但是在redis中,並沒有採用這種方式實現,它嫌LinkedList佔用的空間太大了。 Redis並不是直接基於字串、鍊錶、字典等資料結構來實作KV資料庫,而是在這些資料結構上創建了一個物件系統Redis Object。在redisObject結構體中定義了一個長度24bit的unsigned類型的字段,用來儲存物件最後一次被命令程式存取的時間:
By modifying a bit the Redis Object structure I was able to make 24 bits of space. There was no room for linking the objects in a linked list (fat pointers!)
畢竟,並不需要一個完全準確的LRU演算法,就算移除了一個最近訪問過的Key,影響也不太。
隨機選三個Key,把idle time最大的那個Key移除。後來,把3改成可設定的參數,預設為N=5:To add another data structure to take this metadata was not an option, however since LRU is itself an approximation of what we want to achieve, what about #roximating LRU its#p? ##最初Redis是這樣實現的:
maxmemory-samples 5
when there is to evict a key, select 3 random keys, and evict the one with the highest idle time
。在每一回合移除(evict)一個Key時,隨機從N個裡面選一個Key,移除idle time最大的那個Key;下一輪又是隨機從N個裡面選一個Key...有沒有想過:在上一輪移除Key的過程中,其實是知道了N個Key的idle time的情況的,那我能不能在下一輪移除Key時,利用好上一輪知曉的一些資訊?就是這麼簡單,簡單得讓人不敢相信了,而且十分有效。但它還是有缺點的:每次隨機選擇的時候,並沒有利用
歷史資訊
However if you think at this algorithm
acrossits executions, you can see how we are trashing a lot of interesting data. Maybe when sampling the N keys, lotwe encounter a lotwe of good candidates, but we then just evict the best, and start from scratch again the next cycle.當每一輪移除Key時,拿到了這個N個Key的idle time,如果它的idle time比pool 裡面的Key的idle time還要大,就把它加到pool裡面去。這樣一來,每次移除的Key並不僅僅是隨機選擇的N個Key裡面最大的,而且還是pool裡面idle time最大的,並且:pool 裡面的Key是經過多輪比較篩選的,它的idle time 在機率上比隨機取得的Key的idle time要大,可以這麼理解:pool 裡面的Key 保留了"歷史經驗資訊"。start from scratch太傻了。於是Redis又做了改進:採用緩衝池(pooling)
Basically when the N keys sampling was performed, it was used to populate a larger pool of keys (just 16 keys by default). This pool has the keys sor by idle time, default enter the pool when they have an idle time greater than one key in the pool or when there is empty space in the pool.
至此,基於LRU的移除策略就分析完了。 Redis裡面還有一個基於LFU(訪問頻率)的移除策略,後面還有時間再說。#採用"pool",把一個全局排序問題轉化成為了局部的比較問題。 (儘管排序本質上也是比較,囧)。要知道idle time 最大的key,精確的LRU需要對全域的key的idle time排序,然後就能找出idle time最大的key了。但可以採用一種近似的思想,即隨機採樣(samping)若干個key,這若干個key就代表著全局的key,把samping得到的key放到pool裡面,每次採樣之後更新pool,使得pool裡面總是保存著隨機選擇過的key的idle time最大的那些key。需要evict key時,直接從pool裡面取出idle time最大的key,將之evict掉。這種想法是很值得借鏡的。
JDK中的LinkedHashMap實作了LRU演算法,使用以下建構方法,accessOrder 表示"最近最少未使用"的衡量標準。例如accessOrder=true,當執行java.util.LinkedHashMap#get元素時,就表示這個元素最近被存取了。
/** * Constructs an empty <tt>LinkedHashMap</tt> instance with the * specified initial capacity, load factor and ordering mode. * * @param initialCapacity the initial capacity * @param loadFactor the load factor * @param accessOrder the ordering mode - <tt>true</tt> for * access-order, <tt>false</tt> for insertion-order * @throws IllegalArgumentException if the initial capacity is negative * or the load factor is nonpositive */ public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder = accessOrder; }
再重寫:java.util.LinkedHashMap#removeEldestEntry方法即可。
The {@link #removeEldestEntry(Map.Entry)} method may be overridden to impose a policy for removing stale mappings automatically when new mappings are added to the map.
為了確保線程安全,用Collections.synchronizedMap將LinkedHashMap物件包裝起來:
Note that this implementation is not synchronized. If multiple threads access a linked hash map concurrently, and at l east one of the least one of the least map concurrently, and at l east one of the least one of the least com threads modifies the map structurally, it must be synchronized externally. This is typically accomplished by synchronizing on some object that naturally encapsulates the map.search. #
final Map<Long, TimeoutInfoHolder> timeoutInfoHandlers = Collections.synchronizedMap(new LinkedHashMap<Long, TimeoutInfoHolder>(100, .75F, true) { @Override protected boolean removeEldestEntry(Map.Entry eldest) { return size() > 100; } });當容量超過100時,開始執行LRU策略:將最近最少未使用的TimeoutInfoHolder 物件 evict 掉。
參考連結:
Random notes on improving the Redis LRU algorithmUsing Redis as an LRU cache以上是詳解Redis的LRU演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章!