但是，上篇文章我們也挖了一個坑，說過現有的近似算法模拟效果還有待提高，今天這篇文章就是來填上這個坑，講一下在<code>redis 3.0</code>中對近似lru算法的優化，既提升了算法的性能也提升了模拟效果。
redis 3.0中主要做了如下優化：
<code>lru</code>時鐘的粒度從秒級提升為毫秒級
使用新的<code>api</code>來擷取lru替換時的采樣樣本
預設的lru采樣樣本數從3提升為5
使用<code>eviction pool</code>來選取需要淘汰的key
提升<code>lru時鐘</code>的粒度，主要是為了在測試lru算法性能時，能夠在更短的時間内擷取結果，更新lru時鐘的方法也有所變化，如果lru時鐘的時間粒度高于<code>servercron</code>重新整理的時間粒度，那麼就主動擷取最新的時間，否則使用server緩存的時間，
在源碼的<code>utils/lru</code>目錄下有測試腳本，測試前需要把<code>src/redis.h</code>中的<code>redis_lru_clock_resolution</code>宏設定為1，即lru時鐘的分辨率為<code>1ms</code>，然後重新編譯源碼，執行方式如下，
測試完成後會生成一個<code>html</code>頁面，包含測試結果，以及一個圖形化的插入淘汰流程
在<code>redis 2.8</code>中每次選取淘汰樣本時，都是調用<code>dictgetrandomkey</code>來随機擷取一個key，會根據<code>maxmemory-samples</code>配置的大小，多次調用。這個流程在<code>redis 3.0</code>中被優化為一次調用擷取指定數量的<code>key</code>，且不需要每次都調用随機函數，如下，
<code>dictgetsomekeys</code>會随機從db的某個起始位置開始，連續擷取指定數量的<code>key</code>，需要注意的是，如果<code>db</code>對應的字典正在做<code>rehash</code>，可能需要從兩個<code>hashtable</code>來擷取key。如果需要根據某種分布來随機擷取字典裡面的key，這種采樣方式可能是不合适的，但是如果隻是為了随機擷取一系列key來作為lru算法的淘汰樣本，這種方式是可行的。
采樣性能的提升帶來的好處就是，我們可以在不犧牲淘汰算法性能的情況下，提高采樣的樣本數，讓redis的近似lru算法更接近于嚴格lru算法，是以目前redis把超過<code>maxmemory</code>後預設的采樣樣本數從<code>3</code>個提升到<code>5</code>個。
eviction pool更新邏輯代碼如下，
當選取的淘汰政策和lru相關時（allkeys-lru或volatile-lru），<code>freememoryifneeded</code>會調用<code>evictionpoolpopulate</code>來更新eviction pool，然後淘汰掉eviction pool裡面的最後一個元素所對應的key，這樣的選取淘汰key的方式的好處是：假設說新随機選取的key的通路時間可能比曆史随機選取的key的通路時間還要新，但是在redis 2.8中，新選取的key會被淘汰掉，這和lru算法利用的通路局部性原理是相違背的，在redis 3.0中，這種情況被避免了。
此外，如果某個曆史選取的key的idle時間相對來說比較久，但是本次淘汰并沒有被選中，因為出現了idle時間更久的key，那麼在使用eviction pool的情況下，這種idle時間比較久的key淘汰機率增大了，因為它在eviction pool裡面被儲存下來，參與下輪淘汰，這個思路和<code>通路局部性原理</code>是契合的。
我們可以看到在前面1/2需要淘汰的key裡面（<code>淺灰色</code>的點），<code>redis 3.0</code>殘留下來的key明顯比redis 2.8少了很多，而且後面新插入的1/2的key裡面（<code>綠色</code>的點），redis 3.0沒有一個淘汰的key。
redis 3.0中對于<code>lru</code>替換算法的優化，在隻維護一個eviction pool帶來的少量開銷情況下，對算法效率的提升是比較明顯的，效率的提升帶來的是通路命中率的提升。同時，在目前3.4的unstable版本中我們也可以看見redis計劃實作<code>lfu</code>算法以支援更豐富的業務場景，阿裡雲redis服務團隊也會持續跟進。此外，對于<code>lirs</code>這種基于lru的改進算法，在不影響性能的前提下，我們也會研究在核心上做支援。