本文研究的主要是高吞吐、線程安全的LRU緩存的相關(guān)內(nèi)容，具體介紹如下。

幾年以前，我實(shí)現(xiàn)了一個(gè)LRU緩存用來為關(guān)鍵字來查找它的id。數(shù)據(jù)結(jié)構(gòu)非常有意思，因?yàn)橐蟮耐掏潞艽笞阋韵罅渴褂?code>locks和synchronized關(guān)鍵字帶來的性能問題，應(yīng)用是用java實(shí)現(xiàn)的。

我想到一連串的原子引用分配會(huì)在ConcurrentHashMap中保持LRU保持LRU順序，開始的時(shí)候我把value包裝到entry中去，entry在雙鏈表的LRU鏈中有一個(gè)節(jié)點(diǎn)，鏈的尾部保持的是最近使用的entry，頭節(jié)點(diǎn)中存放的是當(dāng)緩存達(dá)到一定的大小的時(shí)候可能會(huì)清空的entry。每一個(gè)節(jié)點(diǎn)都指向用來查找的entry。

當(dāng)你通過key查找值的時(shí)候，緩存首先要查找map看看是否有這個(gè)value存在，如果不存在的話，它將依賴于加載器將value從數(shù)據(jù)源中以read-through的方式讀出來并且以“如果缺失則添加”的方式添加的map中去。確保高吞吐的挑戰(zhàn)是有效的維護(hù)LRU鏈。這個(gè)并發(fā)的哈希map是分段的而且在線程的水平在一定水平（當(dāng)你構(gòu)建map的時(shí)候你可以指定并發(fā)的水平）情況下的時(shí)候不會(huì)經(jīng)歷太多的線程競爭。但是LRU鏈不能以同樣的方式被劃分嗎，為了解決這個(gè)問題，我引入了輔助的隊(duì)列用來清除操作。

在cache中有六個(gè)基本的方法。對(duì)于緩存命中，查找包含兩個(gè)基本操作：get和offer，對(duì)于換粗丟失包含四個(gè)基本的方法get、load、put和offer。在put方法上，我們也許需要追蹤清空操作，在緩存命中的情況下get，我們在LRU鏈上被動(dòng)的做一些清空叫做凈化操作。

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

清空操作和凈化操作都是大批量的處理數(shù)據(jù)，我們來看一下每個(gè)操作的細(xì)節(jié)

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 e.v 

如果key存在，我們在LRU鏈的尾部提供一個(gè)新的節(jié)點(diǎn)來表明，這是一個(gè)最近使用的值。get和offer的執(zhí)行并不是原子操作（這里沒有l(wèi)ock），所以我們不能說這個(gè)offered 節(jié)點(diǎn)指向最近使用的實(shí)體，但是肯定是當(dāng)我們并發(fā)執(zhí)行時(shí)獲得的最近使用的實(shí)體。我們沒有強(qiáng)制get和offer對(duì)在線程間執(zhí)行的順序，因?yàn)檫@可能會(huì)限制吞吐量。在offer一個(gè)節(jié)點(diǎn)之后，我們嘗試著做一些清除和返回value的操作。下邊我們詳細(xì)看一下這offer和purge操作。

如果緩存丟失發(fā)生了，我們將調(diào)用加載器為這個(gè)key加載value，創(chuàng)建一個(gè)新的實(shí)體并把它放入到map中去，put操作如下：

put(E) -> E 
 
existing entry ex <- map.putIfAbsent(e.k, 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 

正如你所見的一樣，有兩個(gè)或這兩個(gè)以上的線程把一個(gè)實(shí)體放入map的時(shí)候可能存在競爭，但是只允許一個(gè)成功并且會(huì)調(diào)用offer。在LRU鏈的尾部提供一個(gè)節(jié)點(diǎn)之后，我們需要檢查是否緩存已經(jīng)達(dá)到了它的闕值的大小，闕值是我們用來出發(fā)批量清空操作的標(biāo)識(shí)。在這個(gè)特定的應(yīng)用的場景下，闕值的設(shè)置要比容量的大小要小。清空操作小批量的發(fā)生而不是每一個(gè)實(shí)體加進(jìn)來的時(shí)候都會(huì)發(fā)生，多線程或許會(huì)參與到清空操作中去，直到緩存的容量達(dá)到它的容量。上鎖很容易但是線程卻能是安全的。清空需要移除LRU鏈的頭節(jié)點(diǎn)，這需要依賴細(xì)心的原子操作來避免在map中多線程的移除操作。

這個(gè)offer操作非常有意思，它總是嘗試著創(chuàng)建一個(gè)節(jié)點(diǎn)但是并不試圖在LRU中立即移除和刪除那些不再使用的節(jié)點(diǎn)。

offer(E) 
 
if tail node doesn't refer to entry e 
  assign current node c <- e.n 
  create a new node n(e), new node refers to entry e 
  if atomic compare-and-set node e.n, expect c, assign n 
    add node n to tail of LRU list 
    if node c not null 
      set entry c.e to null, c now has a hole 
      add node c to cleanup queue 
    end 
  end 
end 

首先它會(huì)檢查，鏈中尾部的節(jié)點(diǎn)沒有指向已經(jīng)訪問的實(shí)體，這并沒有什么不同除非所有的線程頻繁的訪問同樣的鍵值對(duì)，它將會(huì)鏈部的尾的實(shí)體創(chuàng)建一個(gè)新的節(jié)點(diǎn)當(dāng)這個(gè)實(shí)體不同的時(shí)候，在提供新的節(jié)點(diǎn)之前，它嘗試為實(shí)體進(jìn)一個(gè)比較和設(shè)置的操作，這將阻止多線程做同樣的事情。

成功的分配節(jié)點(diǎn)的線程在LRU鏈的尾部提供了一個(gè)新的節(jié)點(diǎn)，這個(gè)操作和ConcurrentLinkedQueue中的find一樣，依賴的算法在下邊的文章中有描述 Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms。線程然后會(huì)檢查實(shí)體之前是否和其他的節(jié)點(diǎn)有相關(guān)連，如果是這樣的話，老的節(jié)點(diǎn)不會(huì)立即刪除，但是會(huì)被標(biāo)記為一個(gè)hole（它的實(shí)體的引用會(huì)被設(shè)置為空）

總結(jié)

以上就是本文關(guān)于高吞吐、線程安全的LRU緩存詳解的全部內(nèi)容，希望對(duì)大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站其他相關(guān)專題，如有不足之處，歡迎留言指出。感謝朋友們對(duì)本站的支持！

最新評(píng)論