本文研究的主要是高吞吐、線程安全的LRU緩存的相關內容,具體介紹如下。
幾年以前,我實現了一個LRU緩存用來為關鍵字來查找它的id。數據結構非常有意思,因為要求的吞吐很大足以消除大量使用locks和synchronized關鍵字帶來的性能問題,應用是用java實現的。
我想到一連串的原子引用分配會在ConcurrentHashMap中保持LRU保持LRU順序,開始的時候我把value包裝到entry中去,entry在雙鍊錶的LRU鏈中有一個節點,鏈的尾部保持的是最近使用的entry,頭節點中存放的是當緩存達到一定的大小的時候可能會清空的entry。每一個節點都指向用來查找的entry。
當你通過key查找值的時候,緩存首先要查找map看看是否有這個value存在,如果不存在的話,它將依賴於加載器將value從數據源中以read-through的方式讀出來並且以“如果缺失則添加”的方式添加的map中去。確保高吞吐的挑戰是有效的維護LRU鏈。這個並發的哈希map是分段的而且在線程的水平在一定水平(當你構建map的時候你可以指定並發的水平)情況下的時候不會經歷太多的線程競爭。但是LRU鏈不能以同樣的方式被劃分嗎,為了解決這個問題,我引入了輔助的隊列用來清除操作。
在cache中有六個基本的方法。對於緩存命中,查找包含兩個基本操作:get和offer,對於換粗丟失包含四個基本的方法get、load、put和offer。在put方法上,我們也許需要追踪清空操作,在緩存命中的情況下get,我們在LRU鏈上被動的做一些清空叫做淨化操作。
get : lookup entry in the map by key
load : load value from a data source
put : create entry and map it to key
offer: append a node at the tail of the LRU list that refers to a recently accessed entry
evict: remove nodes at the head of the list and associated entries from the map (after the cache reaches a certain size)
purge: delete unused nodes in the LRU list -- we refer to these nodes as holes, and the cleanup queue keeps track of these
清空操作和淨化操作都是大批量的處理數據,我們來看一下每個操作的細節
get操作是按如下方式工作的:
get(K) -> V lookup entry by key k if cache hit, we have an entry e offer entry e try purge some holes else load value v for key k create entry e <- (k,v) try put entry e end return value ev
如果key存在,我們在LRU鏈的尾部提供一個新的節點來表明,這是一個最近使用的值。 get和offer的執行並不是原子操作(這裡沒有lock),所以我們不能說這個offered 節點指向最近使用的實體,但是肯定是當我們並發執行時獲得的最近使用的實體。我們沒有強制get和offer對在線程間執行的順序,因為這可能會限制吞吐量。在offer一個節點之後,我們嘗試著做一些清除和返回value的操作。下邊我們詳細看一下這offer和purge操作。
如果緩存丟失發生了,我們將調用加載器為這個key加載value,創建一個新的實體並把它放入到map中去,put操作如下:
put(E) -> E existing entry ex <- map.putIfAbsent(ek, e) if absent offer entry e; if size reaches evict-threshold evict some entries end return entry e else, we have an existing entry ex return entry ex end
正如你所見的一樣,有兩個或這兩個以上的線程把一個實體放入map的時候可能存在競爭,但是只允許一個成功並且會調用offer。在LRU鏈的尾部提供一個節點之後,我們需要檢查是否緩存已經達到了它的闕值的大小,闕值是我們用來出發批量清空操作的標識。在這個特定的應用的場景下,闕值的設置要比容量的大小要小。清空操作小批量的發生而不是每一個實體加進來的時候都會發生,多線程或許會參與到清空操作中去,直到緩存的容量達到它的容量。上鎖很容易但是線程卻能是安全的。清空需要移除LRU鏈的頭節點,這需要依賴細心的原子操作來避免在map中多線程的移除操作。
這個offer操作非常有意思,它總是嘗試著創建一個節點但是並不試圖在LRU中立即移除和刪除那些不再使用的節點。
offer(E) if tail node doesn't refer to entry e assign current node c <- en create a new node n(e), new node refers to entry e if atomic compare-and-set node en, expect c, assign n add node n to tail of LRU list if node c not null set entry ce to null, c now has a hole add node c to cleanup queue end end end
首先它會檢查,鏈中尾部的節點沒有指向已經訪問的實體,這並沒有什麼不同除非所有的線程頻繁的訪問同樣的鍵值對,它將會鏈部的尾的實體創建一個新的節點當這個實體不同的時候,在提供新的節點之前,它嘗試為實體進一個比較和設置的操作,這將阻止多線程做同樣的事情。
成功的分配節點的線程在LRU鏈的尾部提供了一個新的節點,這個操作和ConcurrentLinkedQueue中的find一樣,依賴的算法在下邊的文章中有描述Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms。線程然後會檢查實體之前是否和其他的節點有相關連,如果是這樣的話,老的節點不會立即刪除,但是會被標記為一個hole (它的實體的引用會被設置為空)
以上就是本文關於高吞吐、線程安全的LRU緩存詳解的全部內容,希望對大家有所幫助。感興趣的朋友可以繼續參閱本站其他相關專題,如有不足之處,歡迎留言指出。感謝朋友們對本站的支持!